Реферат: Элементы комбинаторики. Правила умножения и сложения

НЕ ПОЛНОСТЬЮ!!!!

9. Переключательные функции от 2-х и п переменных.

Переключательные функции от 2х переменных – это булевы функции двух переменных.

10. Определение и примеры функционально полных базисов.

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

Очевидно, что если F – функционально полная система, то добавление любого числа перекл функций не изменит статуса вновь полученной системы, т.е. она останется функц полной.

Функционально полная система функции называется функциональным базисом, если она минимальна, т.е. удаление хотя бы одной из функций приводит к тому, что система теряет свойство полноты.

Система из 3х функций: дизъюнкции, конъюнкции и отрицания, явл полной, т.к. через них можно выразить любые функции алгебры логики.

Заметим, что в силу законов де Моргана:

Дизъюнкцию можно представить через конъюнкцию и отрицание. Следовательно, функционально полной является система функций и (конъюнкция и отрицание).

Также конъюнкцию можно представить через дизъюнкцию и отрицание. Следовательно, функционально полной является система функций и (дизъюнкция и отрицание).

Итак, примеры функциональных систем:

Системы F3 и F4 являются базисами, т.к. удаление из них любой функции приводит к системе, не являющейся полной.

11. Специальные разложения переключательных функций.

Любую перекл функцию кроме тожд нуля можно представить в виде СДНФ. А в свою очередь, любую функцию, представленную в виде СДНФ, можно представить с помощью суммы по модулю 2, конъюнкции и константы 1. Т.е. любую перекл функцию можно представить с помощью функций: сумма по модулю 2, конъюнкция и константы 1. Отсюда следует, что система функций явл полной.

Более того эта система является еще и базисом.

Базис называется системой Жегалкина.

Теорема.Каждая перекл функция единственным образом допускает представление в виде полинома Жегалкина.

Пример: . Представим эту функцию в виде полинома Жегалкина.

Решение

Другим, более распространенным способом нахождения полинома Жегалкина явл метод неопределенных коэффициентов, который основан на выше указанной теореме

12. Классы Поста. Теорема о функциональной полноте.