Дизъюнктивные и конъюнктивные нормальные формы. Полином Жегалкина. Двойственные и самодвойственные функции. 1 страница

Основные элементарные булевы функции. Основные свойства. Существенные и фиктивные переменные. Способы задания.

Функции алгебры логики.

Часть 1

Опр1. Функция , определенная на множестве и принимающая значения из

множества {0,1}, называется функцией алгебры логики или булевой функцией.

Множество всех булевых функций обозначается .

Элементарные булевы функции:

- одной переменной:

1. - нуль функция; 2. - единичная функция;

3. { ; 4. - тождественная функция;

Таблица 1.

x	0	1	x
0	0	1	0	1
1	0	1	1	0

-двух переменных:

5. 6.

7. 8.

9. 10.

11. 12.

Функциональные символы:

& - конъюнкция; V - дизъюнкция; - сумма по модулю 2; ~ - эквивалентность; - импликация; - стрелка Пирса; | - штрих Шеффера; - функция Вебба.

Основные свойства элементарных функций:

1. Коммутативность:

; ; ; ; ; .

2. Ассоциативность:

; ; ;

.

3. Дистрибутивность:

- конъюнкция относительно дизъюнкции;

- дизъюнкция относительно конъюнкции;

- конъюнкция относительно смещения по модулю 2.

4. Принципы де Моргана:

5. Операция отрицания:

6.

Опр2. a) Пусть H P. Формулой будем называть любую функцию из множества .

Например, любая элементарная функция - формула.

b) Рассмотрим набор функций и рассмотрим функцию

- формула

Формула представляет собой некоторую булеву функцию от совокупного множества переменных.

Опр3. Формула называется тождественно истинной (тождественно ложной), если реализуемая ею функция равна 1 (соответственно 0).

Опр4. Пусть заданна функция - функция от n переменных. Переменная называется существенной, если существует такой набор (из 0 и 1) значений переменных , для которого . В противном случае переменная называется фиктивной.

Функция задается тремя способами:

1) табличный, например таблица 1;

2) с помощью формул, например:

3) векторно, например:

1.1.Выяснить, какие из перечисленных выражений являются формулами:

1)

Решение: - формула, т.к. это элементарная функция.

2)

Решение: - не формула, т.к. - не функциональный символ.

3) 4) 5) 6)

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

формулами:

1)

Решение: пользуюсь определениями элементарных функций, строим истинностную таблицу.

2) 3) 4)

1.3. Какие из перечисленных формул являются тождественно истинными или тождест-

венно ложными:

1)

Решение: строим истинностную таблицу для заданной функции.

Ответ: данная формула тождественно истинная.

2) 3)

4) 5)

6)

1.4. Перечислить существенные и фиктивные переменные следующих функций:

1)

Проверим переменную : - существенная переменная.

Проверим переменную :

- фиктивная переменная

Проверим переменную :

- фиктивная переменная

2) 3)

4) 5)

6)

1.5. Показать, что является фиктивной переменной функции (выразив формулой, в которую не входит явно):

1)

Решение: строим истинностную таблицу

- фиктивная перем. - фиктивная перем.

2)

3)

1.6. От каких переменных функция зависит существенно.

1) 2)

3) 4)

1.7. Выяснить для каких зависят существенно от всех своих переменных следующие функции:

1)

2)

3)

1.8. Эквивалентны ли формулы и :

1)

Решение: строим истинностную таблицу для функций и

Ответ: и - не эквивалентны.

2)

3)

4)

1.9. Проверить, справедливы ли следующие соотношения. Указание: справедливость данных соотношений проверяется составлением истинностных таблиц.

1) 2)

3) 4)

5) 6)

7)

1.10. Используя основные эквивалентности, доказать эквивалентность формул и , если:

1)

2)

3)

1.11. Реализовать функцию формулой над множеством связок , если:

1)

Решение: функцию надо выразить через суперпозицию функций отрицание и дизъюнкцию:

2) 3) 4)

Обозначим:

Если , то , если , то .

Опр 1. Формула вида называется совершенной дизъюнктивной нормальной формой (с.д.н.ф.)

Опр 2. Формула вида называется совершенной конъюнктивной нормальной формой.

Опр 3. Формула вида , где называется полиномом Жегалкина.

Опр 4. Пусть . Тогда называется двойственной к функции .

2.1. Построить СДНФ и СКНФ для следующих функций:

1)

Решение: строим истинностную таблицу для данной функции:

Строим СДНФ:

Строим СКНФ:

2)

3)

4)

2.2. Используя основные логические законы, привести к с.д.н.ф. и с.к.н.ф.

1)

Дата добавления: 2014-12-27