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

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

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

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

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

Пример

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

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

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

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

Пример:

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

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

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

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

Пример

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

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

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

Если каждая входящая в ДНФ элементарная конъюнкция является полной относительно набора , то ДНФ называется совершенно дизъюнктивной нормальной формой (СДНФ)

Пример:

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

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

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

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

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

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

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

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