Свойства конъюнкции, дизъюнкции и отрицания

Особая роль двух функций (из этих трех) определяется тем обстоятельством, что определение этих функций легко может быть перенесено на любое число переменных:

Конъюнкцией n переменных f (x1, x2, …, xn) = x1 x2… xn называется функция, которая принимает значение 1, если и только если все переменные равны 1 (и, значит, равна 0, если хотя бы одна из этих переменных равна 0).

Дизъюнкцией n переменных f (x1, x2, …, xn) = x1? x2 …? xn называется такая функция, которая равна 0 если и только если все переменные равны 0 (и, значит, равна 1 тогда и только тогда, когда хотя бы одна переменная равна 1).

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

Будем обозначать через f (x1, x2, …, xn) новую функцию, которая на наборе переменных x1, x2, …, xn принимает значение, противоположное f (x1, x2,…, xn).

Заметим, что в перечисленных далее свойствах в роли x, y, z может выступать любая логическая функция. Все свойства легко могут быть доказаны из приведенных выше определений этих функций.

1. Универсальные границы:

x?1 = 1; x? 0 = х; х1 = х; х0 = 0.

2. Ассоциативность конъюнкции и дизъюнкции:

x (yz) = (xy)z; x? (y? z) = (x ?y)? z.

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

3. Поглощение («целое поглощает часть»):

х? ху = х (1? у) = х.

4. Распределительные законы:

х (y? z) = x y? x z; х? (y z) = (x? y)(x? z),.

5. Правила де Моргана оба эти правила обобщаются на любое число переменных.

Простой конъюнкцией называется конъюнкция одной или нескольких переменных, при этом каждая переменная встречается не более одного раза (либо сама, либо ее отрицание).

Например, x? y? z является простой конъюнкцией.

Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция простых конъюнкций. Например, выражение x? y? y? z является ДНФ.

Совершенной дизъюнктивной нормальной формой (СДНФ) называется такая дизъюнктивная нормальная форма, у которой в каждую конъюнкцию входят все переменные данного списка (либо сами, либо их отрицания), причем в одном и том же порядке. Например, выражение x? y? z является ДНФ, но не СДНФ. Выражение x? y? z? x? y? z? x? y? z является СДНФ.

Аналогичные определения (с заменой конъюнкции на дизъюнкцию и наоборот) верны для КНФ и СКНФ. Приведем точные формулировки. Простой дизъюнкцией называется дизъюнкция одной или нескольких переменных, при этом каждая переменная входит не более одного раза (либо сама, либо ее отрицание). Например, выражение x? y? z — простая дизъюнкция.

Конъюнктивной нормальной формой (КНФ) называется конъюнкция простых дизъюнкций.

Например, выражение (x? y? z)? (x? z)? (y? z) — КНФ.

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

Например, выражение (x? y? z)? (x? z)? (y? z) является СКНФ.