Элементы комбинаторики. Правила умножения и сложения (стр. 2 из 5)

- конъюнкция (логическое умножение)

- дизъюнкция

- импликация

- отрицание импликации

- эквиваленция

- сумма по модулю 2

- стрелка Пирса

│ - штрих Шеффера

Порядок действий в формулах определяется с помощью скобок. Чтобы уменьшить их количество, на множестве функций вводится порядок действий.

Самой старшей считается «отрицание»

Затем – «конъюнкция», «штрих Шеффера», «стрелка Пирса»

Затем – «дизъюнкция»

Затем – «импликация»

На самом низком уровне – эквиваленция и сумма по модулю 2.

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

Итак, стрелка Пирса равна антидизъюнкции, штрих Шеффера равен антиконъюнкции.

Любую булеву функцию можно представить с помощью отрицания, конъюнкции и дизъюнкции.

6. Совершенная конъюнктивная нормальная форма.

Представление булевой функции

в виде конъюнкции несовпадающих элементарных дизъюнкций называется конъюнктивной нормальной формой (КНФ) этой функции.

Пример

Это конъюнкция трех несовпадающих элементарных дизъюнкций.

Чтобы из неполной элементарной дизъюнкции получить полную необходимо неполную элемент дизъюнкцию дополнить 0, а 0 представить в виде конъюнкции недостающей переменной и её отрицания. После этого необходимо применить дистрибутивный закон.

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

Если каждая входящая в КНФ элементарная дизъюнкция является полной относительно набора

, то КНФ называется совершенно конъюнктивной нормальной формой (СКНФ)

Пример:

Любую булеву функцию

, не равную тождественной единице, можно представить в виде СКНФ.

Получить СКНФ можно преобразовывая формулы, а можно по таблице истинности.

7. Совершенная дизъюнктивная нормальная форма.

Представление булевой функции

в виде дизъюнкции несовпадающих элементарных конъюнкций называется дизъюнктивной нормальной формой (ДНФ) этой функции.

Пример

Одна третья конъюнкции является полной элементарной.

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

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

Если каждая входящая в ДНФ элементарная конъюнкция является полной относительно набора

, то ДНФ называется совершенно дизъюнктивной нормальной формой (СДНФ)

Пример:

Получить СДНФ можно преобразовывая формулы, а можно по таблице истинности.

8. Переключательные функции. Способы задания.

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

Основы перекл функций заложил англ матем Дж.Буль в 19 веке.

Пусть предметом изучения явл поведение сложн систем, а не их устройство. В этом случае интересуют лишь входные и выходные сигналы, а не процессы, происходящие внутри устройства.

Отсутствие сигнала как на входе, так и на выходе будет сигнализировать 0, наличие – 1.

Каждому кортежу

, состоящему из 0 и 1, соответствует одно из 2х значений 0 или 1. По сути, имеем булеву функцию . В данном случае её называют переключательной функцией.

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

Рассмотрим этот метод подробнее. Примерами логических схем явл обыкновенные микросхемы, которые в большом кол-ве присутствуют в электробытовых приборах и компьютерах..

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

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

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

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

Система F переключательных функций

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

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

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

приводит к тому, что система теряет свойство полноты.

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

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

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

и (конъюнкция и отрицание).

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

и (дизъюнкция и отрицание).

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

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

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

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

явл полной.

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

Базис

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

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

Пример:

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

Решение