25. Логическая функция двух переменных. Правила построения совершенной дизъюнктивной нормальной формы.

koralexand.ru > 25. Логическая функция двух переменных. Правила построения совершенной дизъюнктивной нормальной формы.

1. Свойства элементарных функций алгебры логики

Элементарные функции типа отрицания, дизъюнкции, Шеффера, Пирса, импликации и т. д. находятся в определенной связи друг с другом. Рассмотрим эти связи и свойства исходных функций.

Конъюнкция , дизъюнкция , отрицание (функции И, ИЛИ, НЕ) . Справедливы следующие аксиомы. Пусть x — некоторая логическая пе- ременная. Тогда

1. что означает возможность исключения из логического выражения всех членов, имеющих двойное отрицание, заменив их исходной величиной;
2. x+x=x; xx=x— правила подобных преобразований позволяют сокращать, длину логичecкиx выражений;
3. x+0=x;
4. x+1=1;
5. x0=0;
6. x·1=x;
7. ;
8. ;

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

1) свойство ассоциативности (сочетательный закон):

2) свойство коммутативности (переместительный закон):

3) свойство дистрибутивности (распределительный закон):

для дизъюнкции относительно конъюнкции

Свойство дистрибутивности фактически определяет правила раскрытия скобок или взятия в скобки логических выражений.

Замечание: справедливость указанных свойств доказывается с помощью вышеизложенных аксиом.

Например, докажем что

Аналогично можно доказать и другие законы.

Законы де Моргана:

Следствия, вытекающие из законов де Моргана:

с помощью которых можно выражать конъюнкцию через дизъюнкцию и отрицание или дизъюнкцию через конъюнкцию и отрицание.

Законы де Моргана и следствия из них справедливы для любого количества переменных:

Для логических функций устанавливаются соотношения, известные как законы поглощения:

Закон склеивания применяется в том случае, когда две конъюнкции соединенные знаком дизъюнкции содержат одинаковое количество одних и тех же переменных, причем одна из них входит в одну из конъюнкций с отрицанием, а в другую – без отрицания. Тогда по этой переменной производится «склеивание». В результате вместо двух конъюнкций остается одна, в которой на одну переменную меньше.

В таблице 5 показана справедливость законов поглощения.

Функция сложения по модулю 2— функция, выражаемая следующим образом:

Функция сложения по модулю 2 обладает следующими свойствами:

1) коммутативности (переместительный закон):

2) ассоциативности (сочетательный закон):

3) дистрибутивности (распределительный закон):

Для этой функции справедливы аксиомы:

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

Функция импликации (→) — функция, выражается следующим образом:

Для функции импликации справедливы следующие аксиомы:

Из аксиом следует, что импликация обладает только свойством коммута-тивности (переместительный закон) в измененном виде: .

Свойство ассоциативности для этой функции несправедливо (таблица 6).

Функции И, ИЛИ, НЕ через импликацию выражаются следующим образом:

Функция Шеффера (/) — функция, которая может быть выражена соотно-шением .

Для нее характерны аксиомы:

что подтверждается таблицей 7.

Эти аксиомы позволяют сформулировать следующие правила преобразования:

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

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

Эти выводы подтверждаются также тем, что свойства ассоциативности и дистрибутивности для функции Шеффера несправедливы от трех переменных, а следовательно, несправедливо и для «n» переменных.

. Функция Пирса (Вебба) () — функция, которая описывается выражением

Для функций Пирса (Вебба) справедливы аксиомы:

что подтверждается таблицей 8.

Элементарные булевы функции И, ИЛИ, НЕ выражаются через функцию Пирса (Вебба) следующим образом:

Для функции Пирса (Вебба) справедливо свойство коммутативности только для двух переменных: =. Функция Пирса (Вебба), так же как и функция Шеффера, является двуместной функцией. Следовательно, невозможны записи вида: ; для установления приоритетов обязательно должны использоваться скобки, которые определяют последовательность осуществления операций:

Замечание: равносильность функций Пирса и функции НЕ—ИЛИ (), не ведет к наличию одинаковых свойств у этих функций.

4 Аналитическое представление функций алгебры логики

Существует много способов задания логических функций. Ранее был рассмотрен табличный способ, при котором каждому набору значений переменных в таблице истинности указывается значение самой логической функции. Этот способ нагляден и может быть применен для записи функций от любого количества переменных. Однако при анализе свойств функций алгебры логики (ФАЛ) такая запись не является компактной. Проще выглядит аналитическая запись в виде формул.

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

Пусть имеется функция :

Функцию называют термом.

Дизъюнктивный терм — терм, связывающий все переменные, представленные в прямой или инверсной форме, знаком дизъюнкции.

Конъюнктивный терм — терм, связывающий переменные, представленные в прямой или инверсной форме, знаком конъюнкции. Обозначается конъюнктивный терм следующим образом:

Ранг терма r определяется количеством переменных, входящих в данный терм. Например, для конъюнктивного терма , и для дизъюнктивного терма .

Любая таблично заданная функция алгебры логики может быть представлена аналитически в виде

где i — номера наборов, на которых функция равна 1; — знак дизъюнкции, объединяющий все термы , равные единице.

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

Нормальная дизъюнктивная форма (НДФ) — объединение термов, включающее конъюнктивные термы переменного ранга.

Количество всех термов, входящих в состав (2.11), равно количеству единичных строк таблицы.

Пример. Записать в аналитическом виде функцию, заданную таблицей 9