Множества. Комбинаторика. Отношения (стр. 8 )

Пример. Упростить

Решение.

Упражнения

Задание: упростить следующие формулы:

1)  . Ответ: .

2)  . Ответ: xy

3)  . Ответ:

4)  . Ответ: .

5)  . Ответ:

6)  . Ответ: z.

2.1.6. Элементарная конъюнкция. Элементарная дизъюнкция

В силу ассоциативности конъюнкции в выражениях (x & y) & z и x & (y & z) скобки можно не писать, поэтому считаем запись x & y & z, имеющей смысл. Индуктивно получает смысл запись x1&…&xn. Аналогично, считаем имеющей смысл и запись x1Ú x1Ú…Úxn (т. е. из двуместных операций получены с помощью свойства ассоциативности n-местные). Будем полагать, что:

Выражение будем называть буквой, а &…&– конъюнкцией букв, Ú…Ú– дизъюнкцией букв.

ТЕОРЕМА. Конъюнкция букв тождественно ложна тогда и только тогда, когда в нее входит хотя бы одна переменная вместе со своим отрицанием.

Доказательство. Þ. Пусть конъюнкция букв тождественно ложна, но такой переменной в ней нет. Придадим переменным, которые входят в эту конъюнкцию, значение 1, а тем переменным, которые входят в нее под знаком отрицания, 0. На этом наборе значений переменных конъюнкция примет значение 1, а это противоречит условию, т. е. наше предположение неверно.

Ü. Пусть в конъюнкцию К входит переменная t вместе со своим отрицанием. Применив закон коммутативности конъюнкции, мы приведем ее к виду:

К && К1 º 0 & K1 º 0. <

ТЕОРЕМА. Дизъюнкция букв тождественно ложна тогда и только тогда, когда существует хотя бы одна переменная, которая входит в нее вместе со своим отрицанием.

Доказывается аналогично. <

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

Упражнение

1)  Докажите: xs = 1 ó x = s, .

2.1.7. Совершенная дизъюнктивная нормальная форма

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

ТЕОРЕМА. Число всех различных ДНФ от n переменных равно .

Доказательство. В ЭК переменная может входить под знаком отрицания (ситуации присваивает код 0), может входить сама (код 1); может не входить ни сама, ни под знаком отрицания (код 2).Таким образом, каждой ЭК от n переменных ставится во взаимооднозначное соответствие размещение с повторениями из трех элементов 0, 1, 2 по n местам. Таких размещений 3n, а поэтому и ЭК столько же. Любое подмножество ЭК из множества всех 3n ЭК определяет ДНФ, а число всех подмножеств этого множества равно . <

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

ТЕОРЕМА о разложении булевой функции по одной переменной.

Доказательство. Проверяем, какие значения принимают функции, стоящие справа и слева, вначале на любом наборе значений переменных, начинающимся с нуля, а затем на наборе, начинающимся с единицы. <

ТЕОРЕМА о разложении булевой функции по двум переменным.

Доказательство. Применить дважды предыдущую теорему. Можно доказать также, проверяя какие значения принимают функции, стоящие справа и слева, вначале на любом наборе значений переменных, начинающимся с двух нулей, затем на наборе вида , затем на наборе вида , а затем на наборе вида . <

ТЕОРЕМА о разложении булевой функции по переменным. Любую булеву функцию можно представить в виде:

, (1)

где знак сокращенной дизъюнкции берется по всем двоичным наборам .

Доказательство. Можно провести индукцию по s. А можно проверить равенство непосредственно на всех наборах значений переменных. Для этого заметим, что

, где

;

;

<.

ТЕОРЕМА. Для любой функции, не являющейся тождественно ложной, существует и притом единственная СДНФ.

Доказательство. Из теоремы о разложении булевой функции по переменным при s = n следует:

. (2)

Но равно 0 или 1. Если нулю, то соответствующее слагаемое из дизъюнкции удаляется, а если 1, то слагаемое приобретает вид . Отсюда:

. (3)

Следовательно, мы представили булеву функцию в виде СДНФ. Так как числа различных n-местных булевых функций и СДНФ совпадают, то представление булевой функции в виде СДНФ возможно лишь единственным образом. <

СЛЕДСТВИЕ. Любую булеву функцию, не являющуюся тождественно ложной можно представить в виде суперпозиции &,Ú,Ø, причем отрицание относится только к переменным.

Формула (3) позволяет по таблице истинности булевой функции строить ее СДНФ.

Пример. Привести к СДНФ функцию f = (10001110).

Построим таблицу истинности:

x	y	z	F(x, y, z)
0	0	0	1
0	0	1	0
0	1	0	0
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	1
1	1	1	0

.

Алгоритм приведения булевой функции к ДНФ:

1)С помощью эквивалентностей:

, , , ,