Similar presentations:
Полнота систем булевых функций
1.
Модуль 2Математическая логика
Занятие 2.5. Полнота
систем булевых
функций
2022 г.
2.
Содержание1.
2.
3.
4.
5.
6.
Полная система функций
Теорема о полноте
Замкнутые классы
Примеры классов К0, К1, S, M и L
Критерий Поста- Яблонского
Функциональные базисы
3.
.Полная система функций
Система функций
F = {f1, f2, . . . , fm }
называется полной, если все
остальные логические функции
могут быть представлены с
помощью формул через функции
этой системы F
4.
.Примеры полных систем
1. P2 = {f1, f2, . . . ,fm / m=2^2^N},
содержащая все N-мерные булевы
функции, полна
2. Система функций {+, , -} полна
5.
Теорема о полноте системыбулевых функций
Если даны две системы
логических функций F1 и F2, и
F1 полна, то система F2
полна тогда, и только тогда,
когда каждая функция
системы F1 представима
через функции F2
6.
Полнота штрихаШеффера { }
ДНФ: a b =
a b
a = a + a = a a
a + b = a b = (a a) (b b)
______
_____
a b = a + b = (a b) =
= (a b) (a b)
7.
Полнота импликативнойсистемы
ДНФ:
a b = a + b
a = a + 0= a 0
a + b = a b = (a 0) b
______
_____
a b = a + b = (a b) =
(a (b 0)) 0
8.
Замкнутые классыПять замкнутых классов
функций K0, K1, S, M и L
Замкнутым каждый класс
называется потому, что любая
подстановка из функций данного
класса дает новую функцию,
которая также принадлежит этому
классу
9.
Класс К0Классом K0 (сохраняющих
константу 0) булевых функций fi
(x1, x2, . . ., xn) называется
множество функций, для которых
выполняется условие, что в нуле
функции принимают значение 0,
fi (0, 0, . . . , 0) = 0
10.
Примеры К0К классу K0 принадлежат:
1. константа 0
2. логическое сложение a+b
3. логическое умножение ab
4. жегалкинское сложениеa b
5. функции сохранения первой a и
второй b переменных
11.
Класс К1Классом K1 (сохраняющих
константу 1) булевых функций fi
(x1, x2, . . ., xn) называется
множество функций, для которых
выполняется условие, что в
единице функции принимают
значение 1,
fi (1, 1, . . . , 1) = 1
12.
Примеры К1К классу K1 принадлежат:
1. константа 1
2. логическое сложение a+b
3. логическое умножение ab
4. Эквивалентность a b
5. функции сохранения первой a и
второй b переменных
13.
Класс SКлассом S (самодвойственных) булевых
функций fi (x1, x2, . . ., xn) называется
множество функций, для которых
выполняется условие, что fi* = fi , т. е. на
всех противоположных наборах значение
функции противоположны
________________
fi (x1, x2, . . ., xn) = fi ( x1, x2, . . ., xn)
14.
Примеры SК классу S принадлежат:
1. Отрицание a
2. функции сохранения первой a и
второй b переменных
15.
Класс MКлассом М (монотонных)
булевых функций
fi (x1, x2, . . ., xn) называется
множество функций, для которых
выполняется условие, что на всех
наборах 1 > 2 значение
функции
fi ( 1) > fi ( 2)
16.
Примеры MК классу M принадлежат:
1. константа 0
2. константа 1
3. логическое сложение a+b
4. логическое умножение a·b
5. функции сохранения первой a и
второй b переменных
17.
Класс LКлассом L (линейных) булевых
функций
fi (x1, x2, . . ., xn) называется
множество функций, которые
представимы полиномом
Жегалкина первой степени
fi (x1, x2, . . ., xn) = с0 ci xi
18.
Примеры LК классу L принадлежат:
1. константа 0
2. константа 1
3. отрицание a
4. Эквивалентность a b
5. жегалкинское сложение a b
6. функции сохранения первой a и
второй b переменных
19.
Критерий ПостаЯблонскогоДля того, чтобы система
логических функций F была
полна, необходимо и
достаточно, чтобы она по
совокупности не содержалась ни
в одном из замкнутых классов
K0, K1, S, M и L
20.
Полнота базиса БуляКлассы
K0
K1
S
M
L
{ }
+
+
-
+
+
-
+
-
+
+
-
+
-
{+}
{-}
{ , +, -}
21.
Функциональный базисПолная система логических
функций F называется базисом,
тогда и только тогда, когда она
безизбыточна, т.е. удаление из
системы F хотя бы одной
функции, приведет к тому, что
она перестанет быть полной