Математическая логика и теория алгоритмов. Галуев Г.А. - 9 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

Составители: 

Рубрика: 

Математическая Логика и Теория Алгоритмов стр. 9 из 64
© 2003 Галуев Геннадий Анатольевич
(*) )X,...,X,,...,(FX...X)X,...,X,X,...,X(F
n1mm1m1
),...,(
n1mm1
m1
m1
++
&&&=
∨
σσ
σσ
σσ
где m – любое целое число из {1,...,n}; дизъюнкция берётся по всем возможным на-
борам значений
),...,(
m1
σ
σ
переменных (X
1
,...,X
m
);
⎩
⎨
⎧
=⎤
=
=
0 если X
1 если X
X
σ
σ
σ
Такое представление функции называют разложением по m переменным.
Доказательство.
Рассмотрим произвольный набор
),...,(
n1
α
α
значений переменных (X
1
,...,X
n
) и по-
кажем, что обе части выражения (*) принимают на этом наборе одно и то же значе-
ние. Левая часть выражения (*) принимает значение F
),...,(
n1
α
α
, что очевидно. Пра-
вая часть выражения (*) принимает следующее значение:
),...,(F),...,,,...,(F
...),...,,,...,(F...
n1
9.2
n1mm1
m1
9.2
n1mm1m1
),...,(
m1m1
m1
αααααα
αααασσαα
σσσσ
σσ
⎯→←&
&&&⎯→←&&&
+
+
∨
Это следует из того, что
⎩
⎨
⎧
=⎤
=
=
0 если (1) 0
1 если 1
α
α
α
α
(по определению
σ
X ) и
⎩
⎨
⎧
=
=⎤
=
⎤
0 если 0
1 если (0) 1
α
α
α
α
В случае когда m=n из (*) получаем:
1),...,F(
(**) X...X),...,(FX...X)X,...,X(F
n1
n1
),...,(
n1n1
),...,(
n1
n1
n1
n1
n1
=
&&=&&&=
∨∨
σσ
σσ
σσ
σσ
σσ
σσ
Разложение (**) называют совершенной дизъюнктивной нормальной формой
(СДНФ) булевой функции F(X
1
,...,X
n
). Здесь в разложении функции участвуют все n её
переменных X
1
,...,X
n
.
Из полученного выражения (**) для СДНФ вытекает теорема о полноте набора
{&,
∨ , ⎤} логических функций.
Теорема. Любая истинностная функций может быть представлена пропозицион-
ной формой, содержащей логические операции только из набора {&,
∨ , ⎤}.
Доказательство. Если функция F(X
1
,...,X
n
) есть константа 0, то её можно предста-
вить формой X
1
&⎤X
1
. Если функция F(X
1
,...,X
n
) не константа 0, то её можно предста-
вить в виде (**). Следовательно, в любом случае произвольную функцию можно
представить пропозиционной формой, содержащей только &,
∨ , ⎤.
Из этой теоремы и формулы (**) вытекает правило построения СДНФ для любой
булевой функции, отличной от константы 0:
По таблице истинности для каждой строки, где
1),...,(F
n1
=
σ
σ
строим конъюнкцию
всех её переменных, причём i переменная входит в конъюнкцию своим прямым зна-
чением X
i
, если
1
i
=
σ
и инверсным ⎤X
i
– если
0
i
=
σ
. Полученные конъюнкции затем
объединяют знаком дизъюнкции
∨
.
Это правило даёт возможность получения пропозиционной формы для любой ис-
тинностной функции по её таблице истинности.
Пример. Пусть функция F(X
1
,X
2
) задана таблицей истинности вида
X
1
0 0 1 1
X
2
0 1 0 1
F(X
1
,X
2
) 0 1 1 1
Тогда можно записать соответствующую этой функции СДНФ в виде:
⎤X
1
&X
2
∨ X
1
&⎤X
2
∨ X
1
&X
2

Страницы