Полнота и замкнутость

Содержание

1. Полнота и замкнутость
2. ПредисловиеКак известно, все функции алгебры логики можно
3. ОпределениеМножество функций алгебры логики A называется полной
4. Примеры полных систем функций
5. Многочлен ЖегалкинаВ п. 5 теоремы 2 рассмотрена
6. Многочлен Жегалкина
7. Многочлен Жегалкина
8. Замыкание
9. Замкнутый класс
10. Спасибо за внимание!
11. Скачать презентанцию

ПредисловиеКак известно, все функции алгебры логики можно выразить, используя всего три операции: конъюнкцию, дизъюнкцию и отрицание. Однако это не единственный набор операций, с помощью которых также можно выразить любую функцию алгебры

Главная
Разное
Полнота и замкнутость

Слайды и текст этой презентации

Слайд 1Полнота и замкнутость
Е.А. Скородумова
к.ф.-м.н., доцент
доцент кафедры ТВиПМ МТУСИ

Слайд 2Предисловие
Как известно, все функции алгебры логики можно выразить, используя всего

три операции: конъюнкцию, дизъюнкцию и отрицание. Однако это не единственный

набор операций, с помощью которых также можно выразить любую функцию алгебры логики.

Такие системы функций, с помощью которых можно выразить произвольную функцию алгебры логики, называются полными.

ПредисловиеКак известно, все функции алгебры логики можно выразить, используя всего три операции: конъюнкцию, дизъюнкцию и отрицание. Однако

Слайд 3Определение
Множество функций алгебры логики A называется полной системой в P2

(множество всех функций алгебры логики), если любую функцию алгебры логики

можно выразить формулой над A.

ОпределениеМножество функций алгебры логики A называется полной системой в P2 (множество всех функций алгебры логики), если любую

Слайд 4Примеры полных систем функций

Слайд 5Многочлен Жегалкина
В п. 5 теоремы 2 рассмотрена система функций, ранее

не встречавшаяся. Рассмотрим её подробнее.

Определение: Многочленом Жегалкина от переменных x1,x2,…,xn

называется выражение, полученное из 0,1, переменных xi (i =1,2,…,n) путем применения конечного числа операций конъюнкции, сложения по модулю 2 и скобок, определяющих порядок действий.

Замечание: конъюнкция имеет более высокий приоритет, чем сложения по модулю 2.