Similar presentations:
Совершенная дизъюнктивная нормальная форма. Совершенная конъюнктивная нормальная форма
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. ПРИМЕР. ПОСТРОЕНИЕ СДНФ И СКНФ
xy
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