Функциональная полнота логической системы

1.

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

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

Лемма 1 (о немонотонных функциях).
Если функция f(x1,x2,..,xn) немонотонная, то
подстановкой
констант
из
нее
можно
получить отрицание.
Точнее, существует такая подстановка n-1
константы, что функция оставшейся одной
переменной является отрицанием.
Курс «Математическая логика и теория алгоритмов»
Тема «Функциональная полнота логической системы»
2

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

Лемма 2 (о нелинейных функциях).
Если функция f(x1,x2,..,xn) нелинейная, то с
помощью
подстановки
констант
и
использования отрицаний из нее можно
получить дизъюнкцию и конъюнкцию.
Точнее, существует представление дизъюнкции
и конъюнкции в виде суперпозиции констант,
отрицаний и функции f.
Курс «Математическая логика и теория алгоритмов»
Тема «Функциональная полнота логической системы»
3

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

При
схемной
реализации
константы 0 и 1 специальных
элементов не требуют. Поэтому
имеет смысл ввести ослабленное
понятие
функциональной
полноты.
Курс «Математическая логика и теория алгоритмов»
Тема «Функциональная полнота логической системы»
4

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

Курс «Математическая логика и теория алгоритмов»
Тема «Функциональная полнота логической системы»
5

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

Теорема
Для того, чтобы система функций ∑ была
функционально полной в слабом смысле,
необходимо и достаточно, чтобы она
содержала:
-хотя бы одну немонотонную функцию;
-хотя бы одну нелинейную функцию.
Курс «Математическая логика и теория алгоритмов»
Тема «Функциональная полнота логической системы»
6

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

Доказательство
Необходимость
Классы монотонных и линейных функций
замкнуты и содержат 0 и 1. Поэтому, если ∑ не
содержит
немонотонных
и
нелинейных
функций, то их нельзя получить с помощью
суперпозиции функций из ∑ и констант.
Курс «Математическая логика и теория алгоритмов»
Тема «Функциональная полнота логической системы»
7

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

Курс «Математическая логика и теория алгоритмов»
Тема «Функциональная полнота логической системы»
8

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

Пример
а) Система ∑6 = {&,⊕} функционально полна в слабом
смысле,
так
как
∧
нелинейна,
а
∑
по mod 2 немонотонна.
Константа 0 получается из соотношения х⊕х=0,
однако константу 1 с помощью ∧ получить нельзя,
поэтому ∑6 не является функционально полной
системой в обычном (сильном смысле).
Курс «Математическая логика и теория алгоритмов»
Тема «Функциональная полнота логической системы»
9

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

Курс «Математическая логика и теория алгоритмов»
Тема «Функциональная полнота логической системы»
10

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

в) Проверить на слабую функциональную
полноту систему ∑7, состоящую из одной
функции f1, заданной таблично.
Курс «Математическая логика и теория алгоритмов»
Тема «Функциональная полнота логической системы»
11

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

f1∉M, т.к. нарушается условие монотонности:
(0,0,0)<(0,1,0)
f1(0,0,0)>f1(0,1,0)
Курс «Математическая логика и теория алгоритмов»
Тема «Функциональная полнота логической системы»
12

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

f1∉L, т.к. множества
элементов
содержат ∧ переменных х1,х2⇒
∑7 – функционально полная в
слабом смысле.
Курс «Математическая логика и теория алгоритмов»
Тема «Функциональная полнота логической системы»
13

14. ТЕОРЕМА ПОСТА О ФУНКЦИОНАЛЬНОЙ ПОЛНОТЕ

Для того, чтобы система ∑ была
функционально полной (в сильном смысле)
необходимо и достаточно, чтобы она
содержала:
1) Нелинейную функцию
2) Немонотонную функцию
3) Несамодвойственную функцию
4) Функцию, не сохраняющую 0
5) Функцию, не сохраняющую 1
Курс «Математическая логика и теория алгоритмов»
Тема «Функциональная полнота логической системы»
14

15. ТЕОРЕМА ПОСТА О ФУНКЦИОНАЛЬНОЙ ПОЛНОТЕ

Условные обозначения для лемм:
Курс «Математическая логика и теория алгоритмов»
Тема «Функциональная полнота логической системы»
15

16. ПОСТРОЕНИЕ СХЕМЫ

Пусть f0 p0 ; f1 p1; fL L; fS S; fM M.
Используя леммы, из них можно будет
построить ¬ и &, то есть [μ] {¬ , &}, что и
будет означать полноту μ.
Курс «Математическая логика и теория алгоритмов»
Тема «Функциональная полнота логической системы»
16

17. ПОСТРОЕНИЕ СХЕМЫ

Курс «Математическая логика и теория алгоритмов»
Тема «Функциональная полнота логической системы»
17

18.

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