lec08
.pdf
Кафедра Прикладной математики Института информационных технологий РТУ МИРЭА
Дисциплина
«Математическая логика и теория алгоритмов»
2022-2023 уч.г.
Наполнение курса
Объем курса
16 лекционных и 8 практических занятий
Темы лекционных занятий
1.Элементы теории множеств. Булева алгебра
2.Булевы вектора и булевы функции
3.ДНФ, СДНФ, КНФ, СКНФ
4.Минимизация ДНФ
5.Метод Карно и метод Квайна
6.Двойственные функции
7.Функциональная полнота. Полные классы. Алгебра Жегалкина.
8.Замкнутые классы функций: монотонные, самодвойственные, сохраняющие const.
9.Теорема Поста
10.Исчисление высказываний
11.Исчисление предикатов. Основные положения. Кванторы
12.Нормальные формы. Доказательства
13.Конечные автоматы
14.Соединения и синтез автоматов
15.Машина Тьюринга
16.ЧРФ и НАМ
2
Лекция 8.
Важнейшие классы БФ.
8.1.Замкнутые классы функций.
8.2.Монотонные функции.
8.3.Самодвойственные функции.
8.4.Классы функций, сохраняющих константу.
Часть 1.
Замкнутые классы функций.
Пусть Q = {f1,f2,…fn} – совокупность булевых функций, конечная или бесконечная, от любого числа переменных.
Замыканием множества Q называется множество функций, которые могут быть получены из Q с помощью суперпозиций. Обозначение: [Q].
Пример 8.1. Замыкание Булева базиса.
Q = { , &, };
[Q]– все булевы функции.
[Q]– ?
Замечание 8.1. ! замыкание любой полной системы – все БФ.
5
Q называется замкнутым классом, если замыкание [Q] совпадает с Q. Замечание 8.2. ! Замыкание – противоположность ФПС.
Пример 8.2.
а)
Q = { 1 2 … …} – бесконечно,
где i1 i2 ik; Q = [Q].
б) Q – линейная функция, принято обозначать L.
Q = {a0 1 2 … …}, где a0 {0,1}.
Если вместо xi подставлять сумму таких же переменных, то ничего не изменится.
6
Часть 2.
Монотонные функции.
, Вn; = ( 1,α2,…αi,…, n); = ( 1, 2,… i,…, n).
Если i (1≤i≤n): αi i, (αi ≤ i) то α и сравнимы.
В противном случае α и несравнимы. (т.е. i,j: αi > i, αj < j)
Введём условия частичной упорядоченности вершины куба Вn.
, , Вn – очевидно, что если ; , то .
Пример 8.3. Булев куб – В2. Стрелочка совпадает с отношениями порядка.
Наборы (0,0) и (0,1), (0,1) и (1,1) сравнимы, причем (0,0) (0,1) (1,1).
Наборы (0,1) и (1,0), (1,1,0) и (0,1,1)
несравнимы.
!!! Несравнимы также α и разной длины.
8
Булева функция (x1,x2,…xn) называется монотонной (монотонно возрастающей), если упорядоченной пары вершин ( , ): выполняется ( ) ( ).
Пример 8.4. Монотонность в B2. |
|
а) 1(x1,x2) = (0110) |
? |
Является ли 1(x1,x2) – монотонной |
|
Нет. |
|
= (1;1), = (1;0); ; |
|
( ) = 0 1 = ( ) |
|
б) 2(x1,x2) = (0111) |
? |
Является ли 2(x1,x2) – монотонной |
|
в) 3(x1,x2) = (0001) |
? |
Является ли 3(x1,x2) – монотонной |
Да. , : выполняется ( ) ( ).
Итог: x1 x2 – не монотонна; x1 x2, x1 & x2
|
|
|
|
(x ,x ) ? |
|||||
x |
|
x |
|
||||||
|
1 |
|
2 |
1 |
1 |
1 |
2 |
2 |
|
0 |
0 |
||||||||
|
|
0 |
|
|
|||||
0 |
1 |
|
|
1 |
|
|
|||
1 |
0 |
|
|
1 |
|
|
|||
1 |
1 |
|
|
0 |
|
|
|||
x x |
|
(x ,x ) ? |
(x ,x ) ? |
|||||||
1 |
|
2 |
x |
1 |
x |
x |
& x |
|||
|
2 |
1 |
22 |
3 |
1 |
1 |
22 |
|||
0 |
0 |
|
|
0 |
|
|
|
0 |
|
|
0 |
1 |
|
|
1 |
|
|
|
0 |
|
|
1 |
0 |
|
|
1 |
|
|
|
0 |
|
|
1 |
1 |
|
|
1 |
|
|
|
1 |
|
|
– монотонны.
9
Утверждение 8.1. (x1,x2,…xn) является монотонной ее сокращенная ДНФ не содержит отрицаний.
Следствие. Функция монотонна ее Dmin не содержит отрицаний.
Пример 8.5. Монотонность в B3. |
|
|
|
|
|
|
|||
x1 |
x2 |
|
x3 |
1 |
|||||
Функции монотонны? |
|
|
|||||||
|
0 |
|
0 |
0 |
0 |
||||
а) f1 = (0101 1011); (из примера 4.7) |
|
|
|||||||
0 |
|
0 |
|
1 |
1 |
||||
|
|
|
|
|
|
||||
макс интервалы: I1 I2 |
I3 I4 |
0 |
|
1 |
|
0 |
0 |
||
0 |
|
1 |
|
1 |
1 |
||||
|
|
|
|
|
|
||||
|
? |
|
|
|
|
|
|
|
|
DC = 1 3 x2x3 |
x1x2 1 3 |
1 |
0 |
|
0 |
1 |
|||
1 |
|
0 |
|
1 |
0 |
||||
|
|
|
|
|
|
||||
D |
Да. |
, |
D |
1 |
|
1 |
|
0 |
1 |
C |
?1 |
3 |
C |
|
|
|
|
|
|
1 |
|
1 |
|
1 |
1 |
||||
|
|
|
|
|
|
||||
Итог: f1 – не монотонна
10