Полнота систем булевых функций

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 хотя бы одной
функции, приведет к тому, что
она перестанет быть полной