math_logic_lectures (1)
.pdf
Лекции по математической логике
Леонид Шалагинов
Леонид
Шалагинов
Нормальные
формы
Полнота и замкнутость
Минимизация
ДНФ
Челябинский государственный университет
21 февраля 2014 г.
элементарные коньюнкции и дизъюнкции
Элементарной коньюнкцией от переменных 1, 2, . . . , будем называть коньюнкцию этих переменных или их отрицаний.
Примеры:
1.1
2.1 3
3.1 2 3 5 1
Леонид
Шалагинов
Нормальные
формы
Полнота и замкнутость
Минимизация
ДНФ
элементарные коньюнкции и дизъюнкции
Элементарной коньюнкцией от переменных 1, 2, . . . , будем называть коньюнкцию этих переменных или их отрицаний.
Примеры:
1.1
2.1 3
3.1 2 3 5 1
Элементарной дизъюнкцией от переменных 1, 2, . . . , будем называть дизъюнкцию этих переменных или их отрицаний.
Примеры:
1.2
2.3 5
3.2 1 3 5 1
Леонид
Шалагинов
Нормальные
формы
Полнота и замкнутость
Минимизация
ДНФ
Определение
Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция элементарных коньюнкций 1 2 . . . .
Коньюнктивной нормальной формой (КНФ) называется коньюнкция элементарных дизъюнкций 1 2 . . . .
Примеры:
1.( 2 3)( 1 2 1)( 2 3 1) — КНФ от переменных
1, 2, 3.
2.3 4 1 2 5 —ДНФ от переменных 1, 2, 3, 4, 5.
Леонид
Шалагинов
Нормальные
формы
Полнота и замкнутость
Минимизация
ДНФ
Представление функций
Теорема Всякая булева функция может быть представлена как суперпозиция коньюнкции, дизъюнкции и отрицания, причем так что знак отрицания стоит только непосредственно перед переменными.
Следствие Для всякой булевой функции существует равная ей ДНФ (КНФ).
{
Степенной функцией называется функция = , = 1
, = 0
Для булевой функции ( 1, 2, . . . , ) положим
0( ) = { {0, 1} | ( ) = 0}.1( ) = { {0, 1} | ( ) = 1}.
Заметим, что 0 1 = {0, 1} и 0 1 = .
Леонид
Шалагинов
Нормальные
формы
Полнота и замкнутость
Минимизация
ДНФ
СДНФ и СКНФ
Теорема (об СДНФ)
Всякая булева функция ( 1, 2, . . . , ) может быть представлена в виде
( 1, 2,..., |
1 |
1 |
|
2 |
|
|
( 1, 2, . . . , ) = |
|
|
|
2 |
. . . |
. |
|
|
1 |
|
|
|
|
) |
( ) |
|
|
|
|
|
Такая ДНФ функции называется совершенной (СДНФ).
Теорема (об СКНФ)
Всякая булева функция ( 1, 2, . . . , ) может быть представлена в виде
( 1, 2,..., |
0 |
|
|
|
|
|
|
|
( 1, 2, . . . , ) = |
|
|
1 |
|
2 |
|
|
|
|
1 |
2 |
. . . . |
|||||
) |
( ) |
|
|
|
|
|
||
Такая КНФ функции называется совершенной (СКНФ).
Леонид
Шалагинов
Нормальные
формы
Полнота и замкнутость
Минимизация
ДНФ
Пример СДНФ и СКНФ
Пусть функция ( , , ) задана таблицей истинности
x |
y |
z |
f(x,y,z) |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
Тогда СДНФ: . СКНФ: ( )( )( ).
Леонид
Шалагинов
Нормальные
формы
Полнота и замкнутость
Минимизация
ДНФ
Полнота
Леонид
Шалагинов
Нормальные
формы
Полнота и замкнутость
Минимизация
ДНФ
Система функций B называется полной, если при помощи
суперпозиции функций из B можно получить все булевы функции.
Теорема (О выражении функций полной системы) Пусть
B1 — полная система функций и каждая функция из B1 может быть представлена как суперпозиция функций из B2, тогда B2 — полная система функций.
Примеры полных систем функций
Теорема (О полных системах функций) Следующие системы функций являются полными:
1.{ , , ¬}
2.{ , ¬}
3.{ , ¬}
4.{+, , 1}
5.{|}
6.{↓}
7.{→, 0}
8.{→, ¬}
Леонид
Шалагинов
Нормальные
формы
Полнота и замкнутость
Минимизация
ДНФ
Полиномы Жегалкина
Леонид
Шалагинов
Нормальные
формы
Полнота и замкнутость
Минимизация
ДНФ
Представление функции в виде суперпозиции функций {+, , 1}
называется полиномом Жегалкина.
Теорема (Жегалкина) Любая булева функция единственным образом представима в виде полинома Жегалкина.