Похожие презентации:
Функциональная полнота логической системы
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