Презентации лекций / Презентация лекции 4 ДМ 20
.pdf
План лекции
1.Принцип двойственности
2.Задание функции совершенной дизъюнктивной нормальной формой
3.Задание функции совершенной конъюнктивной нормальной формой
4.Задание функции полиномом Жегалкина
21
Есть алфавит переменных = { , |
,…} |
|
|
|
|
|
|
1 |
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
ПолиномЖегалкинанад |
- |
|
|
Коротко: |
3 |
||||||||||
|
|
|
|
|
|
|
|
|
4 |
||||||
всякаясумма различныхэлементарных |
|
… |
|
|
|||||||||||
конъюнкций,не содержащихотрицаний |
|
|
|
||||||||||||
|
или |
|
|
|
|
|
|||||||||
переменных |
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
… |
|
|||||||
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Наибольшийиз рангов |
|
|
|
|
|
|
Константа0 |
Порядокслагаемыхневажен, |
|||||
конъюнкций- |
|
|
|
|
|
|
|
|
|
посколькуоперация |
|||
|
|
|
|
|
|
–полиномЖегалкина |
|||||||
степеньполинома. |
|
|
|
|
ассоциативна |
||||||||
|
|
|
|
|
|
|
степени 0. |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
Примеры: |
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
– полином Жегалкина степени 4 |
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
э.к.ранга 0 |
э.к.ранга 2 |
э.к.ранга 4 |
|
|
||||||||
|
|
|
|
|
|
|
– полином Жегалкина степени 3 |
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
22
Сколько элементарныхконъюнкцийбез
отрицанийпеременных над алфавитомиз переменных?
Сколько полиномовЖегалкина надалфавитомиз переменных?
1
2
3
4
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
2 |
|
… |
2 |
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
включить не включить |
включить |
не включить |
||||||||
в э.к. |
в э.к. |
в э.к. |
|
в э.к. |
||||||
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
2 |
|
… |
2 |
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
включить не включить |
включить |
не включить |
|
|
||||||||
в П.Ж. |
в П.Ж. |
в П.Ж. |
|
в П.Ж. |
23 |
|||||||
|
|
|
|
|
|
|
|
|
|
|
||
1
2
3
4
1) |
= |
|
|
Попробуемпредставить |
|
|
|
Доказываются |
дизъюнкцию |
|
|||
2) |
|
= |
|
|
||
полиномомЖегалкина |
|
|||||
3) |
|
= |
|
спомощью |
|
|
|
|
|
||||
|
таблиц истинности |
|
|
|||
4) |
1 = ̅ |
|
= ̅ = ̅1 = |
|
||
|
|
|
||||
5) |
0 = |
|
|
|
||
|
|
= ( 1)( 1) 1= |
= |
|||
6) |
= 0 |
|
|
|||
|
|
= 1 1 = |
|
|||
7) |
|
( ) = |
|
|||
= |
|
|||||
|
|
|
|
|
|
|
Если несколько идутподряд,тоскобкиможноопускать
2
4
1
2
3
4
1шаг.Задаемфункциюввиде ДНФ(например,СДНФ)
2шаг.Спомощьюравенства = избавляемсяотдизъюнкций.
3шаг.Спомощьюравенств1-7преобразуемксуммеконъюнкций.
2
5
1шаг.Задаемфункцию ввидеДНФ (например,СДНФ)
2шаг.Спомощью равенства (8) избавляемсяотдизъюнкций.
3шаг.Спомощью (1)-(7)преобразуем ксуммеконъюнкций.
(1)=
(2)=
(3)=
(4) |
1 = ̅ |
(5) |
0 = |
(6) |
= 0 |
(7)( ) =
(8)=
|
|
|
|
1 |
Пример1: |
|
|
|
2 |
|
|
|
3 |
|
|
|
|
( , ) |
|
|
||||
|
4 |
|||
0 |
0 |
|
1 |
|
0 |
1 |
|
0 |
|
1 |
0 |
|
1 |
|
1 |
1 |
|
1 |
|
|
|
|
|
|
= ̅̅ ̅ |
|
= ̅ = ̅ = |
|||
8 |
4 |
|
1 |
|
2 |
= ̅ ̅ = |
1 = |
||||
= |
1 |
|
1 |
||
= |
|||||
= 1 |
( ) |
|
6 |
||
|
= |
||||
= 1
Пример2: = (10001001)
2
6
1
2
Любуюбулевуфункциюможно представитьполиномомЖегалкина, 3
4
причемединственнымобразом.
Представление:
1шаг.Задаемфункцию ввидеДНФ (например,СДНФ)
2шаг.Спомощью равенства (8) избавляемсяот дизъюнкций.
3шаг.Спомощью (1)-(7)преобразуем ксумме конъюнкций.
Переход от формулы
Единственность: кфункции
однозначен по определению
Множество |
Множество |
|
|||
булевых |
полиномов |
|
|||
функций от |
Жегалкина |
|
|||
|
|
от |
|
|
|
переменных |
переменных |
|
|||
|
|
|
|
|
|
|
|
|
|
Если |
|
|
|
|
|
предположить, |
|
|
|
|
|||
|
|
|
|
чтотаквозможно, |
|
|
|
|
|
||
|
|
|
|
тополиномов для |
|
|
|
|
|
функций |
|
|
|
|
|
«нехватит» |
27 |
|
|
|
|
|
|
|
|
|
|
|
|
Функция
ПолиномЖегалкина
Пример:=
= =
П.Ж.
= 0 1 1 1
К. П.Ж.
КаноническийполиномЖегалкина
1
2
3
4
|
|
|
( , ) |
1 |
0 |
0 |
(0,0) |
|
0 |
1 |
(0,1) |
|
1 |
0 |
(1,0) |
|
1 |
1 |
(1,1) |
Общий вид канонического полинома Жегалкина
от 2-хпеременных:
|
, |
= |
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
, |
= ( ,) |
|
|
|
|
|
||
|
|
, |
= ( ,) |
|
|
, , , |
||||
|
|
, |
= ( ,) |
|
|
|||||
|
|
|
|
|
|
|||||
|
|
, |
= ( ,) |
|
|
|
|
|
||
|
|
|
В случае переменных |
|
||||||
|
|
для каждого булевого вектора |
||||||||
|
|
|
длины пишемравенство: |
|
||||||
|
|
, ,…, |
= , ,…, |
|||||||
2