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

1.

Федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
«Ижевский государственный технический университет
имени М. Т. Калашникова»
Кафедра «АСОИУ»
Курс «Математическая логика и теория алгоритмов»
Тема «Совершенная дизъюнктивная нормальная форма.
Совершенная конъюнктивная нормальная форма»
Автор Исенбаева Е.Н., старший преподаватель
Ижевск
2013

2. РАЗЛИЧНЫЕ ФОРМЫ БУЛЕВЫХ ФУНКЦИЙ

f(x1,x2,…,xn) - булева функция – двоичная
функция двоичных переменных.
Булева функция:
-определена на множестве{0,1} ;
-принимает значения из множества {0,1} .
n
2
2 ;
Всего
логических
функций
определены они на множестве вершин n –
мерного куба.
Курс «Математическая логика и теория алгоритмов»
Тема «Совершенная дизъюнктивная нормальная форма. Совершенная конъюнктивная нормальная форма»
2

3. ФОРМЫ ЗАПИСИ БУЛЕВЫХ ФУНКЦИЙ

Знак- отдельная буква или буква с отрицанием.
Элементарное произведение – произведение, в
котором каждый сомножитель – знак.
ДНФ – дизъюнктивная нормальная форма –
сумма элементарных произведений.
Курс «Математическая логика и теория алгоритмов»
Тема «Совершенная дизъюнктивная нормальная форма. Совершенная конъюнктивная нормальная форма»
3

4. ФОРМЫ ЗАПИСИ БУЛЕВЫХ ФУНКЦИЙ

Элементарная сумма – сумма,
в которой каждое слагаемое – знак.
КНФ – конъюнктивная нормальная
форма – произведение элементарных
сумм.
Курс «Математическая логика и теория алгоритмов»
Тема «Совершенная дизъюнктивная нормальная форма. Совершенная конъюнктивная нормальная форма»
4

5. ФОРМЫ ЗАПИСИ БУЛЕВЫХ ФУНКЦИЙ

Произведение
называется
совершенным произведением, если:
1. Содержит точно n знаков
2. Содержит все n переменных,
входящих в функцию
3.Не
содержит
одинаковых
переменных
Курс «Математическая логика и теория алгоритмов»
Тема «Совершенная дизъюнктивная нормальная форма. Совершенная конъюнктивная нормальная форма»
5

6. ФОРМЫ ЗАПИСИ БУЛЕВЫХ ФУНКЦИЙ

СДНФ
–
совершенная
дизъюнктивная
нормальная
форма- сумма совершенных
произведений.
Курс «Математическая логика и теория алгоритмов»
Тема «Совершенная дизъюнктивная нормальная форма. Совершенная конъюнктивная нормальная форма»
6

7. ФОРМЫ ЗАПИСИ БУЛЕВЫХ ФУНКЦИЙ

Сумма
называется
суммой, если:
совершенной
1. Содержит точно n знаков
2. Содержит все n переменных
3. Нет одинаковых переменных
Курс «Математическая логика и теория алгоритмов»
Тема «Совершенная дизъюнктивная нормальная форма. Совершенная конъюнктивная нормальная форма»
7

8. ФОРМЫ ЗАПИСИ БУЛЕВЫХ ФУНКЦИЙ

СКНФ–
совершенная
конъюнктивная
нормальная
форма
–
произведение
совершенных сумм.
Курс «Математическая логика и теория алгоритмов»
Тема «Совершенная дизъюнктивная нормальная форма. Совершенная конъюнктивная нормальная форма»
8

9. ФОРМЫ ЗАПИСИ БУЛЕВЫХ ФУНКЦИЙ

Алгоритм приведения функции к
СДНФ:
-упростить формулу;
-преобразовать, используя законы
0,1:
а&1=а;
1=а+¬а.
Курс «Математическая логика и теория алгоритмов»
Тема «Совершенная дизъюнктивная нормальная форма. Совершенная конъюнктивная нормальная форма»
9

10. ФОРМЫ ЗАПИСИ БУЛЕВЫХ ФУНКЦИЙ

Алгоритм приведения функции к
СКНФ:
-упростить формулу;
-преобразовать, используя законы
0,1:
а+0=а;
0=а&¬а.
Курс «Математическая логика и теория алгоритмов»
Тема «Совершенная дизъюнктивная нормальная форма. Совершенная конъюнктивная нормальная форма»
10

11. ФОРМЫ ЗАПИСИ БУЛЕВЫХ ФУНКЦИЙ

Курс «Математическая логика и теория алгоритмов»
Тема «Совершенная дизъюнктивная нормальная форма. Совершенная конъюнктивная нормальная форма»
11

12. ФОРМЫ ЗАПИСИ БУЛЕВЫХ ФУНКЦИЙ

Построение
СДНФ
по
таблице
истинности:
-выбирают из таблицы строки(двоичные
наборы), где функция F=1;
-если двоичная переменная х=1,
то она входит в совершенное
произведение без отрицания х,
иначе с отрицанием ¬х.
Курс «Математическая логика и теория алгоритмов»
Тема «Совершенная дизъюнктивная нормальная форма. Совершенная конъюнктивная нормальная форма»
12

13. ФОРМЫ ЗАПИСИ БУЛЕВЫХ ФУНКЦИЙ

Построение
СКНФ
по
таблице
истинности:
-выбирают из таблицы строки(двоичные
наборы), где функция F=0;
-если двоичная переменная х=0,
то она входит в совершенную
сумму без отрицания х,
иначе с отрицанием ¬х.
Курс «Математическая логика и теория алгоритмов»
Тема «Совершенная дизъюнктивная нормальная форма. Совершенная конъюнктивная нормальная форма»
13

14. ПРИМЕР. ПОСТРОЕНИЕ СДНФ И СКНФ

x
y
z
x∨y
xz
f
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
0
0
1
1
1
1
1
1
0
0
0
0
0
1
0
1
1
1
0
0
0
1
0
1
Курс «Математическая логика и теория алгоритмов»
Тема «Совершенная дизъюнктивная нормальная форма. Совершенная конъюнктивная нормальная форма»
14

15. ПРИМЕР. ПОСТРОЕНИЕ СДНФ И СКНФ

Курс «Математическая логика и теория алгоритмов»
Тема «Совершенная дизъюнктивная нормальная форма. Совершенная конъюнктивная нормальная форма»
15

16. ПРИМЕР. ПОСТРОЕНИЕ СДНФ И СКНФ

Курс «Математическая логика и теория алгоритмов»
Тема «Совершенная дизъюнктивная нормальная форма. Совершенная конъюнктивная нормальная форма»
16

17. ПРИМЕР. ПОСТРОЕНИЕ СДНФ И СКНФ

Курс «Математическая логика и теория алгоритмов»
Тема «Совершенная дизъюнктивная нормальная форма. Совершенная конъюнктивная нормальная форма»
17

18. ПРИМЕР. ПОСТРОЕНИЕ СДНФ И СКНФ

Курс «Математическая логика и теория алгоритмов»
Тема «Совершенная дизъюнктивная нормальная форма. Совершенная конъюнктивная нормальная форма»
18

19.

СПАСИБО ЗА ВНИМАНИЕ
© ФГБОУ ВПО ИжГТУ имени М.Т. Калашникова, 2013
© Исенбаева Елена Насимьяновна, 2013