Булева алгебра (стр. 3 )

4.  Определение формулы

Обозначим буквой D множество, состоящее из элементарных функций, то есть элементами множества D будут функции.

D={0,1,x,,xy, xy, xy, x→y, x~y, x↙y, x/y}

1. Любая из элементарных функций, логическая переменная x, а также константы 0 и 1 являются формулами над множеством функций D.

2. Тогда любое выражение вида X*Y, где X и Y формулы, а символ звёздочка заменяет одну из логических связок {,,Å,→,~,↙ ,/} также является формулой.

Разберем несколько примеров.

Дано выражение . Используя наше определение убедимся, что оно представляет собой формулу.

Для этого разобьем выражение X и Y.

Положим , , операция дизъюнкции соответствует * в определении. Получили X*Y. Всё выражение формулой, если мы сможем доказать, что X и Y – формула. Рассмотрим сначала Y. Это выражение является формулой, так как представляет собой элементарную функцию «сложение по модулю два». Выражение необходимо разбить на две части. Переобозначим X=(x1~x2) и Y=x3, в качестве * - логическая связка конъюнкции. Выражение X=(x1~x2) является формулой так как представляет собой элементарную функцию «эквиваленция», которая входит во множество Y=x3 является формулой, так как представляет собой логическую переменную и согласно пункту 1 является формулой.

Всякая формула представляет собой булеву функцию. Теперь мы знаемдва способа задания булевых функций: первый с помощью таблицы истинности, второй с помощью формулы. Чтобы ещё лучше вникнуть в понятие формулы приведем несколько примеров выражений не являющихся формулами. это не формула так как в множестве D нет функции, сумма по модулю два это функция всегда зависящая от двух аргументов. Скобки играют очень важную роль при построении формул. В зависимости от расстановки скобок в формуле мы будем получать различные функции.

Пусть дано выражение (это ещё не формула). Попробуем получить всевозможные формулы, расставляя скобки.

.

Получи ли пять различных формул. Напомним, что первыми

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

1.

2.

3.

4. .

Упражнение №1:

Получить все возможные формулы, расставляя скобки в выражении

.

Упражнение №2:

Получить все возможные формулы, расставляя скобки в выражении

.

5.  Тождества булевой алгебры

В этом разделе будут приведены тождества, или законы, позволяющие упрощать формулы.

Формулы называются эквивалентными, если они представляют равные функции.

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

1. Ассоциативный закон.

2. Коммутативный закон.

3. Дистрибутивный закон.

4.Правила де Моргана.

5. Свойства дизъюнкции и конъюнкции:

1. 4. 7.

2. 5. 8.

3. 6.

6. Операция поглощения:

1.

2.

7. Простое склеивание:

8. Обобщенное склеивание:

9.

10.

11.

12.

13. .

6.  Получение эквивалентных формул

Определение. Любое подвыражение формулы представляющее собой формулу будем называть подформулой.

Например, в выражении есть две подформулы и .

Пусть в формуле А содержится подформула В, заменим всякое вхождение формулы В на эквивалентную ей формулу В1, тогда новая формула А1, будет эквивалентна формуле А.

Для получения эквивалентных формул будем использовать вышеперечисленные тождества.

Пример. Требуется доказать, что формула

А = эквивалентна формуле .

А = = (по свойству 10) = =

(теперь используем дистрибутивный закон для раскрытия скобок)=

( по закону простого склеивания) = ( по закону поглощения )

Эквивалентные формулы представляют равные функции.

Упражнение : Докажите, что формула А эквивалентна формуле В.

1.  A=(x/y)/x; B=x→y

2. A=(x/y)/(x/y); B=xy

3. A=xyxy; B=xy.

7. Дизъюнктивные и конъюнктивные нормальные формы

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

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

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

Например: - ДНФ.

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

Например: - КНФ.

Для каждой формулы алгебры высказываний (булевых формул) можно найти множество дизъюнктивных и конъюнктивных нормальных форм.

Например, выражения

АВС;
АСD;
АВС

представлены в ДНФ,

а формула АВ(С) к ДНФ не относится,

так как второе слагаемое не является ни отдельным аргументом, ни конъюнкцией переменных.

Например, выражения

(А)(СD);

АВ(СD)

записаны в КНФ,

а формула (АС)(DЕ) КНФ не является,

поскольку первый сомножитель (в скобках) содержит конъюнкцию С.

Выражение, представленное отдельным аргументом или его инверсией, одновременно входит в класс ДНФ и КНФ.

Любую булеву функцию, можно представить в виде суперпозиции дизъюнкции, конъюнкции и инверсии. Для этого можно использовать тождества булевой алгебры.

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

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

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

Совершенной дизъюнктивной нормальной формой (СДНФ) формулы алгебры высказываний называется ее ДНФ, обладающая следующими свойствами:

1.  ДНФ не содержит двух одинаковых коньюнкций.

2.  Ни одна конъюнкция не содержит одновременно двух одинаковых переменных.

3.  Ни одна конъюнкция не содержит одновременно некоторую переменную и ее отрицание.

4.  Каждая конъюнкция содержит либо переменную , либо ее отрицание для всех переменных, входящих в формулу.

Построение СДНФ по таблице истинности.

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

xyz	f
000 001 010 011 100 101 110 111	0 1 0 1 0 0 1 1	* * * *

Правило конъюнкции: если переменной соответствует 0,то переменная берётся с инверсией, если 1 то без. Первому отмеченному набору 001 соответствует конъюнкция .

0 0 1

↓ ↓ ↓

Набору 011 соответствует конъюнкция ,

Набору 110 соответствует конъюнкция,

Набору 111 соответствует конъюнкция.

Теперь соединяем все полученные конъюнкции с помощью дизъюнкции

- получили СДНФ.

Приведем ещё один пример построения СДНФ для функции от четырёх переменных. Функция задана вектором значений Строим таблицу истинности.

x	y	z	u	f
0	0	0	0	1	*
0	0	0	1	0
0	0	1	0	0
0	0	1	1	0
0	1	0	0	1	*
0	1	0	1	0
0	1	1	0	1	*
0	1	1	1	1	*
1	0	0	0	0
1	0	0	1	0
1	0	1	0	0
1	0	1	1	0
1	1	0	0	1	*
1	1	0	1	0
1	1	1	0	1	*
1	1	1	1	0

СДНФ примет вид .