Законы алгебры логики

а. Законы поглощения:

,

.

б. Законы двойственности для сложения и умножения (законы де Моргана):

,

.

Совершенные нормальные формы (СНФ)

Пусть и — некоторые высказывания. Тогда можно образовать сложные высказывания ИЛИ , И , НЕ , введя операции дизъюнкции (ИЛИ), конъюнкции (И) и отрицания (НЕ).

Электронные схемы, реализующие эти операции, называют логическими элементами. На основе логических элементов строятся более сложные узлы и агрегаты, работа которых может быть описана посредством алгебры логики, т. е. с помощью переключательных (булевых) функций.

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

,

где — логические переменные, принимающие значения 0 или 1.

Логические переменные могут быть действительными и фиктивными.

F Переменная действительна, если значение функции, куда она входит, изменяется при изменении значения этой переменной. В противном случае она фиктивна.

Логические функции многих переменных могут задаваться таблично. Рассмотрим пример табличного определение функции трех переменных (табл. 6)

Табл. 6 Пример табличного задания логической функции трех переменных

Из таблицы видно, что переменные и — действительные, а переменная — фиктивная, т. к. справедливо соотношение , при любых комбинациях и . Переменную можно сократить из выражения булевой функции. Следовательно, для функций алгебры логики существует возможность сокращать (расширять) количество переменных устранением (введением) фиктивных.

Булевы функции могут задаваться аналитически, т. е. в виде формул. При этом сложные логические функции можно выражать через более простые логические функции.

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

Базис минимален, если удаление хотя бы одной функции превращает систему ФАЛ в неполную. Примеры базисной системы функций: (И, НЕ); (ИЛИ, НЕ). На практике намного удобней использовать не минимальный базис. И, ИЛИ, НЕ.

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

,

где — конъюнктивный терм; — дизъюнктивный терм.

F Конъюнктивный терм — это логическое произведение переменных и их отрицаний.

F Дизъюнктивный терм — это логическая сумма переменных и их отрицаний.

F Если терм ФАЛ содержит полный набор переменных, связанных операцией конъюнкции, он носит название минтерм (конституента 1).

F Термы ФАЛ, состоящие из полного набора переменных, связанных операциями дизъюнкции, называются макстермами (конституенты 0).

Представление ФАЛ в аналитическом виде возможно в дизъюнктивной нормальной форме и в конъюнктивной нормальной форме.

F Дизъюнктивная нормальная форма (ДНФ) — это сумма конъюнктивных термов (ДНФ не содержит скобок).

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

Всякая сложная логическая функция может быть сведена к различным ДНФ или КНФ. Однозначное соответствие между функцией алгебры логики и ее представлением в дизъюнктивной или конъюнктивной нормальной форме обеспечивается только в одном случае — когда все конъюнкции ДНФ (термы) составлены из полного числа переменных или когда каждая дизъюнкция КНФ содержит максимальное число переменных.

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

Алгоритм получения СДНФ из таблицы истинности, задающей функцию:

1. Выбрать из таблицы набор переменных для которого справедливо соотношение .

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

3. Повторить пункты 1 и 2 для всех других наборов таблицы, где логическая функция равна 1.

4. Построить СДНФ путем логического суммирования полученных минтермов.

Аналогично определяется алгоритм для получения СКНФ:

1. Выбрать из таблицы набор переменных для которого справедливо соотношение .

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

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

4. Построить СКНФ из полученных дизъюнкций переменных и их отрицаний путем логического умножения.

Дата добавления: 2014-01-07