Опр. 1. (первая теорема о представлении булевых функций)

(первая теорема о представлении булевых функций). Пусть f (X₁ ,…, X_k) – k-местная булева функция (k 1). Если f не равна тождественно 0, то такая формула F, зависящая от списка переменных <X₁, …, X_k> и находящаяся в СДНФ относительного этого списка, что F выражает собой функцию f. формула F определена однозначно с точностью до перестановки дизъюнктивных членов.

Докажем сначала вспомогательное утверждение. При s = 1под А^s будем подразумевать формулу А, а при s = 0 –формулу А. с каждой оценкой списка переменных <s₁, …, s_k>, будем ассоциировать элементарную конъюнкцию Х₁^s1 … Х_k^sk.

Лемма.

Конъюнкция Х₁^s1 … Х_k^sk ассоциированная с оценкой <s₁, …, s_k>, обращается в 1 на одной и только на одной оценке списка переменных <X₁, …, X_k>, а именно на оценке <s₁, …, s_k>.

И в самом деле, на оценке <s₁, …, s_k> формула Х₁^s1 … Х_k^sk принимает значение 1, так как каждый ее конъюнктивный член Х_l^sl принимает значение 1. Действительно, возможны два случая: либо s_l(1 l k) есть 1, и тогда Х_l^sl есть Х_l, либо s_l есть 0, и тогда Х_l^sl есть Х_l. в каждом из этих случаев Х_l^sl на оценке <s₁, …, s_k> принимает значение 1.

С другой стороны, пусть оценка <t₁, …, t_k> не совпадает с оценкой <s₁, …, s_k>. Тогда при некотором l (1 l k) s_l t_l.

Возможны два случая:

1) s_l = 1, t_l = 0

2) s_l = 0, t_l = 1

В первом случае Х_l^sl есть Х_l, а во втором Х_l^sl_­ – Х_l. В любом случае Х_l^si на оценке <t₁, …, t_k> принимает значение 0, а значит, и вся элементарная конъюнкция Х₁^s1 … Х_k^sk принимает значение 0. Лемма доказана.

Пусть теперь функция f (X₁ ,…, X_k) задана таблицей. Выберем из таблицы все строки, соответствующие оценкам, на которых f принимает значение 1.

Для оценки списка переменных в каждой выбранной строке построим ассоциированную с ней элементарную конъюнкцию. Составим дизъюнкцию всех элементарных конъюнкций. Полученная формула будет искомой.

Поиск по сайту: