Презентации лекций / Презентация лекции 4 ДМ 20
.pdf
1
2
3
11
|
|
Задание функциив виде СДНФ |
1 |
|||||
|
|
2 |
||||||
|
|
|
|
|
|
|
|
3 |
|
|
|
|
|
|
|
|
4 |
|
|
Каждуюбулеву функцию , ,…, |
, |
|
|
Обозначения: |
||
|
|
заисключениемтождественноравнойнулю, |
|
|
= |
|||
|
|
можнозадатьформулой: |
|
|
|
|||
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
= |
, ,…, : |
|
|
|
|
|
|||
|
|
|
, ,…, |
|
|
|
|
|
|
|
|
|
|
|
|
|
Формула |
Пример: |
|
|
|
|
|
|
|
называется |
|
|
|
|
|
|
|
совершенной |
|
|
|
|
|
|
|
|
|
|
|
|
( , ) |
|
|
|
|
дизъюнктивной |
|
|
|
|
|
нормальной |
||||
0 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
формойСДНФ |
|||
0 |
1 |
0 |
= ( |
) ( |
) ( |
|
) |
|
1 |
0 |
1 |
|
|
|
|
|
|
1 |
1 |
1 |
|
|
|
|
|
|
|
|
|
= ( ̅ ̅) ( ̅) ( ) |
|
|
|||
|
|
|
Итог: = ̅̅ ̅ |
|
|
12 |
||
|
|
|
|
|
|
|
|
|
|
|
СДНФ |
|
|
|
|
|
|
|
|
|||
|
|
|
|
|||
|
|
|
, ,…, : |
|
|
|
|
|
|
, ,…, |
|
|
|
|
|
|
|
|
|
|
ЧтобызаписатьСДНФ,действуемвсоответствиисформулой:
|
По каждой такой строке |
|
|
|
пишем конъюнкцию, в |
|
|
В таблице истинности |
которую входят все |
Записываем |
|
переменные: |
|||
дизъюнкцию |
|||
функции отмечаем |
либо сами по себе |
||
выписанных |
|||
наборы (строки), в |
(если значение переменной |
||
конъюнкций. |
|||
которых функция |
на наборе равно 1 ), |
||
Это и есть СДНФ |
|||
равна 1 |
либо сотрицанием |
||
функции |
|||
|
(если значение переменной |
||
|
|
||
|
на наборе равно 0) |
|
1
2
3
4
13
План лекции
1.Принцип двойственности
2.Задание функции совершенной дизъюнктивной нормальной формой
3.Задание функции совершенной конъюнктивной нормальной формой
4.Задание функции полиномом Жегалкина
14
|
|
Задание функциив виде СКНФ |
|
1 |
|||||||||
|
|
|
2 |
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
|
|
Каждуюбулеву функцию , ,…, |
, |
|
|
|
4 |
||||||
|
заисключениемтождественноравнойединицы, |
|
Обозначения: |
||||||||||
|
|
|
|
|
|||||||||
|
|
|
можнозадатьформулой: |
|
|
|
|
|
= |
||||
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
= |
|
|
|
|
, ,…, : |
|
|
|
|
||||||
|
|
|
|
|
|
|
|||||||
|
|
|
|
, |
,…, |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Формула |
||
Пример: |
|
|
|
|
|
|
|
|
|
|
называется |
||
|
|
|
|
|
|
|
|
|
|
совершенной |
|||
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
( , ) |
|
|
|
|
|
|
|
конъюнктивной |
|||
|
|
|
|
|
|
|
нормальной |
||||||
0 |
0 |
|
0 |
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
формойСКНФ |
|||||
0 |
1 |
|
1 |
|
= ( |
) ( |
) ( |
|
) |
|
|
||
1 |
0 |
|
0 |
|
|
|
|
|
|
|
|
|
|
1 |
1 |
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
= ( ) ( ̅ ) ( ̅ ̅) |
|
|
|
|||||
|
|
|
|
Итог: = ( |
) ( ̅ ) ( ̅ ̅) |
|
15 |
||||||
|
|
СКНФ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
, |
|
,…, |
|
: |
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
, |
,…, |
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ЧтобызаписатьСКНФ,действуемвсоответствиисформулой:
|
По каждомутакому набору |
|
|
|
пишем дизъюнкцию, в |
|
|
В таблице истинности |
которую входят все |
Записываем |
|
переменные: |
конъюнкцию |
||
функции отмечаем |
|||
либо сами по себе |
выписанных |
||
наборы (строки), в |
|||
(если значение переменной |
дизъюнкций. |
||
которых функция |
|||
на наборе равно 0 ), |
Это и есть СКНФ |
||
равна 0 |
|||
либо сотрицанием |
функции |
||
|
|||
|
(если значение переменной |
|
|
|
на наборе равно 1) |
|
1
2
3
4
16
Принцип |
|
|
|
|
двойственности: |
|
|||
|
|
|
|
|
|
|
|
|
|
Егочастныйслучай: |
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|||||||
|
|
|
|
|
|
|
Какдоказать? |
Записатьформулу, которойопределена двойственнаяфункция, |
||||
|
|||||
|
|
|
|
и упроститьее: |
|
|
|
,…, |
= |
,…, ,…, |
,…, =… |
О
б
о
с
н
о
в
а
н
и
я
17
Каждуюбулеву функцию , ,…,
при любом (1 ≤ ≤ )
можнозадатьформулой:
|
|
|
|
|
|
|
|
|
|
|
( , ,…, ) |
|
|
Какдоказать?
Найти значение,котороепринимает функция,заданная формулой
( , ,…, ) |
|
|
( ,…, , |
,…, ) |
, |
на произвольномнаборе( |
,…, ) значенийпеременных ( ,…, |
)и сравнитьего со |
|||
значениемфункции ( ,…, ) натомженаборе.
О
б
о
с
н
о
в
а
н
и
я
18
|
Каждуюбулеву функцию , |
,…, |
, |
||
|
заисключениемтождественноравнойнулю, |
||||
|
|
можнозадатьформулой: |
|
|
|
|
, ,…, |
|
|
|
|
|
= |
|
|
||
|
|
, ,…, : |
|
|
|
|
|
, ,…, |
|
|
|
|
|
|
|
|
|
Какдоказать?
Записатьформулу разложенияфункции по переменным
( , ,…, ) |
|
( ,…, |
, |
,…, ) |
для = |
и упростить.
О
б
о
с
н
о
в
а
н
и
я
19
Каждуюбулеву функцию , ,…, , заисключениемтождественноравнойединицы,
можнозадатьформулой:
|
, ,…, = |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
, |
|
,…, |
|
: |
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
, |
,…, |
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
Какдоказать?
ЗаписатьввидеСДНФфункцию,двойственнуюк :
= СДНФ
( ) =(СДНФ ) = …[преобразоватьпо принципу двойственности]
О
б
о
с
н
о
в
а
н
и
я
20