РАЗЛИЧНЫЕ ФОРМЫ БУЛЕВЫХ ФУНКЦИЙ
ФОРМЫ ЗАПИСИ БУЛЕВЫХ ФУНКЦИЙ
ФОРМЫ ЗАПИСИ БУЛЕВЫХ ФУНКЦИЙ
ФОРМЫ ЗАПИСИ БУЛЕВЫХ ФУНКЦИЙ
ФОРМЫ ЗАПИСИ БУЛЕВЫХ ФУНКЦИЙ
ФОРМЫ ЗАПИСИ БУЛЕВЫХ ФУНКЦИЙ
ФОРМЫ ЗАПИСИ БУЛЕВЫХ ФУНКЦИЙ
ФОРМЫ ЗАПИСИ БУЛЕВЫХ ФУНКЦИЙ
ФОРМЫ ЗАПИСИ БУЛЕВЫХ ФУНКЦИЙ
ФОРМЫ ЗАПИСИ БУЛЕВЫХ ФУНКЦИЙ
ФОРМЫ ЗАПИСИ БУЛЕВЫХ ФУНКЦИЙ
ФОРМЫ ЗАПИСИ БУЛЕВЫХ ФУНКЦИЙ
ПРИМЕР. ПОСТРОЕНИЕ СДНФ И СКНФ
ПРИМЕР. ПОСТРОЕНИЕ СДНФ И СКНФ
ПРИМЕР. ПОСТРОЕНИЕ СДНФ И СКНФ
ПРИМЕР. ПОСТРОЕНИЕ СДНФ И СКНФ
ПРИМЕР. ПОСТРОЕНИЕ СДНФ И СКНФ
2.65M
Category: mathematicsmathematics

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

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
English     Русский Rules