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


«Учебник по дискретной математике. Представление логических функций в виде СДНФ (СКНФ)»

Файл: 4 КБ
Поделиться:

Будем использовать логическую функцию “эквивалентность”, записанную в виде ху. Напомним, что 00= 1; 01=0; 10= 0; 11= 1.Таким образом, ху = 1 тогда и только тогда, когда х = у.

ЛеммаЛюбая логическая функция f(x1x2xnможет быть представлена в виде дизъюнкции 2п дизъюнктных слагаемыхпричем дизъюнкция берется по всевозможным наборам из EnЭтот факт будем записывать следующим образом:

(*)

где дизъюнкция проводится по всевозможным наборам (s1, s2, …, sпиз Еп.

Доказательство леммы.

а) Пусть f(x1x2xn)= 1. Тогда слева в формуле (* ) стоит 1. Докажем, что и справа в этом случае стоит 1, для чего достаточно указать одно дизъюнктное слагаемое, равное 1. Но среди всех наборов (s1, s2,  sп) имеется набор sх1, sх2, sп хп. Очевидно, что для этого набора слагаемое    равно 1 (так как и  .

б) Пусть f(x1x2xn) = 0. Предположим, что справа стоит не ноль, а единица, тогда какое-то слагаемое тоже должно равняться 1, т. е. для некоторого набора

Это означает (по свойствам конъюнкции), что    , откуда следует, что х1=s1,  х2=s2  ,хп=sn, но в этом случае   f ( s1, s2, ..., snf(x1,x2,xn) = 0 и, значит, справа нет слагаемого, равного 1, т. е. в этом случае и справа и слева в формуле (* ) стоит 0. Лемма доказана.

Теорема. Если булева функция не равна тождественному нулюто ее можно представить в виде СДНФ по ее таблице истинности следующим образомберем только те наборы переменных (х1,х2, ,хn)для которых f(х1,х2,хn) =1, и составляемпростую конъюнкцию для этого набора такесли хi = 0, то берем в этой конъюнкции , если хi = 1, то берем хi. Составляя дизъюнкцию этих простых конъюнкцийпридем к СДНФ.

Доказательство. Пусть f(x1,x2,,xn) не равна тождественному нулю, тогда в дизъюнкции можно не записывать слагаемые, равные нулю, а из формулы (* ) следует следующее представление для данной функции

Запись означает, что дизъюнкция берется по всем наборам ( s1, s2, ..., sn) , для которых  f ( s1, s2, ..., sn) = 1. Так как  (если s1=0), из формулы (**) следует утверждение теоремы.

Следствие. Любую логическую (булевуфункцию можно выразить через три логические функцииконъюнкциюдизъюнкцию и отрицание.

Из предыдущей теоремы видно, что следствие верно для любой функции, не равной тождественному нулю. Однако если f(x1x2,xn) =0, то ее также можно выразить через конъюнкцию, дизъюнкцию и отрицание, например, так:   f(x1x2,xn) =  x1      ,и, несмотря на то, что последнее выражение не является простой конъюнкцией (и, значит, не является СДНФ), тем не менее тождественный ноль также выражен через нужные три функции.

Набор функций, через которые можно выразить любые другие функции, называется полным набором (более точные формулировки даны в разд. 7). Таким образом, конъюнкциядизъюнкция и отрицание являются полным набором.

По аналогии с представлением любой функции (не равной тождественному нулю) в виде СДНФ можно функцию (не равную тождественной 1) представить в виде СКНФ: простая дизъюнкция составляется для тех наборов переменных (х1х2хп), длякоторых f(x1x2,xn) = 0, причем если хi = 1, то в этой дизъюнкции берем , если же хi = 0, то берем хi.

Пример. Составить для импликации и сложения по модулю 2 СДНФ и СКНФ.

 

х

 

у

 

х® у

х + у

0

0

1

0

0

1

1

1

1

0

0

1

1

1

1

0

Тогда СДНФ для этих функций:

СКНФ для этих функций: