Функциональная полнота системы. Алгебра Жегалкина

1.

Федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
«Ижевский государственный технический университет
имени М. Т. Калашникова»
Кафедра «АСОИУ»
Курс «Математическая логика и теория алгоритмов»
Тема «Функциональная полнота системы.
Алгебра Жегалкина»
Автор Исенбаева Е.Н., старший преподаватель
Ижевск
2013

2. ФУНКЦИОНАЛЬНАЯ ПОЛНОТА СИСТЕМЫ

Существуют два способа задания
логических функций:
- табличный;
- формульный.
Курс «Математическая логика и теория алгоритмов»
Тема «Функциональная полнота системы. Алгебра Жегалкина»
2

3. ФУНКЦИОНАЛЬНАЯ ПОЛНОТА СИСТЕМЫ

Теорема 1:
Всякая логическая функция может
быть представлена в виде логической
булевой функции, т.е. в виде
суперпозиции
Для всякой функции, кроме 0, таким
представлением может быть её СДНФ.
Курс «Математическая логика и теория алгоритмов»
Тема «Функциональная полнота системы. Алгебра Жегалкина»
3

4. Функциональная полнота системы

Система функций Σ
называется функционально
полной системой, если любая
логическая функция может быть
представлена формулой над Σ
суперпозицией функций из Σ.
Курс «Математическая логика и теория алгоритмов»
Тема «Функциональная полнота системы. Алгебра Жегалкина»
4

5. Функциональная полнота системы

Функционально полной
системой будет любая
система Σ, через
функции которой можно
выразить ˅, ∧, ¬.
Курс «Математическая логика и теория алгоритмов»
Тема «Функциональная полнота системы. Алгебра Жегалкина»
5

6. Пример 1

Дано:
Сведем системы к функционально полной системе
Σ0. Выразим недостающие до Σ0 функции через
остальные две:
Доказано, что Σ1, Σ2 – функционально полные системы.
Курс «Математическая логика и теория алгоритмов»
Тема «Функциональная полнота системы. Алгебра Жегалкина»
6

7. Пример 2

Σ3 = {│} – штрих Шеффера.
Σ4 = {↓} – стрелка Пирса.
Штрих Шеффера: x│y = ¬(xy) = ¬x ˅¬y.
Стрелка Пирса: x↓y ≡ ¬(x˅y).
x
y
x│y x↓y
0
0
1
1
0
1
0
1
1
1
1
0
1
0
0
0
Σ3, Σ4 – функциональнополные системы.
Курс «Математическая логика и теория алгоритмов»
Тема «Функциональная полнота системы. Алгебра Жегалкина»
7

8. Пример 2

Сведём Σ3 к заведомо функционально полной
системе Σ1:
¬x = ¬ (xx) ≡ x│x
x&y = ¬ (x│y) ≡ (x│y)│(x│y).
Сведём Σ4 к заведомо функционально полной
системе Σ2:
¬x = ¬ (x˅x) ≡ x↓x
x˅y = ¬ (x↓y) ≡ (x↓y)↓(x↓y).
Доказали, что Σ3, Σ4 – функционально полные
системы.
Курс «Математическая логика и теория алгоритмов»
Тема «Функциональная полнота системы. Алгебра Жегалкина»
8

9. АЛГЕБРА ЖЕГАЛКИНА

Алгебра Жегалкина – алгебра над множеством логических функций с
двумя бинарными операциями конъюнкция &, сложение по mod 2
Выполняются следующие соотношения:
x⊕y ≡ y⊕x,
x(y⊕z) ≡ xy⊕xz,
x⊕x ≡ 0,
x⊕0 ≡ x,
x(yz) ≡ (xy)z,
xy ≡ yx,
xx ≡ x,
x&1 ≡ x,
x&0 ≡ 0.
Курс «Математическая логика и теория алгоритмов»
Тема «Функциональная полнота системы. Алгебра Жегалкина»
9

10. Функциональная полнота системы

Отрицание и дизъюнкция выражаются
следующим образом:
Курс «Математическая логика и теория алгоритмов»
Тема «Функциональная полнота системы. Алгебра Жегалкина»
10

11. АЛГЕБРА ЖЕГАЛКИНА

От булевой формулы всегда можно перейти к формуле
Жегалкина к полиному Жегалкина, используя
приведённые выше формулы.
Если xy = 0, то x˅y = x ⊕ y. Это, в частности, позволяет
заменять знак ˅ знаком ⊕ , когда исходная формула
СДНФ.
Примеры:
Курс «Математическая логика и теория алгоритмов»
Тема «Функциональная полнота системы. Алгебра Жегалкина»
11

12. Алгебра Жегалкина

Полином Жегалкина – это
формула алгебры Жегалкина,
имеющая вид полинома по mod
2
(суммы
по
mod
2
произведений).
Курс «Математическая логика и теория алгоритмов»
Тема «Функциональная полнота системы. Алгебра Жегалкина»
12

13. ПОЛИНОМ ЖЕГАЛКИНА

Теорема:
Для всякой логической
функции существует полином
Жегалкина, и притом
единственный.
Курс «Математическая логика и теория алгоритмов»
Тема «Функциональная полнота системы. Алгебра Жегалкина»
13

14.

СПАСИБО ЗА ВНИМАНИЕ
© ФГБОУ ВПО ИжГТУ имени М.Т. Калашникова, 2013
© Исенбаева Елена Насимьяновна, 2013