Конъюнктивная нормальная форма и совершенная конъюнктивная нормальная форма

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

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

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

Например, для формулы А = Ø (х Ú у) º х Ù у имеем:

А = (Ø (х Ú у) ® х Ù у) Ù (х Ù у ® Ø (х Ú у)) =

= (х Ú у Ú х Ù у) Ù (Ø (х Ù у) Ú Ø (х Ú у)) =

= (х Ú х Ú у) Ù (х Ú у Ú у) Ù (Ø х Ú Ø у Ú Ø х) Ù (Ø х Ú Ø у Ú Ø у), то есть

КНФ А = (х Ú х Ú у) Ù (х Ú у Ú у) Ù (Ø х Ú Ø у Ú Ø х) Ù (Ø х Ú Ø у Ú Ø у).

Но так как х Ú х = х, у Ú у = у, Ø х Ú Ø х = Ø х, Ø у Ú Ø у = Ø у, то

КНФ A = (х Ú у) Ù (х Ú у) Ù (Ø х Ú Ø у) Ù (Ø х Ú Ø у).

А так как (х Ú у) Ù (х Ú у) = х Ú у, (Ø х Ú Ø у) Ù (Ø х Ú Ø у) = (Ø х Ú Ø у), то

КНФ A = (х Ú у) Ù (Ø х Ú Ø у).

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

• Все элементарные дизъюнкции, входящие в КНФ А, различны.
• Все элементарные дизъюнкции, входящие в КНФ А, содержат все переменные.
• Каждая элементарная дизъюнкция, входящая в КНФ А, не содержит двух одинаковых переменных.
• Каждая элементарная дизъюнкция, входящая в КНФ А, не содержит переменную и ее отрицание.

Можно доказать, что каждая не тождественно истин­ная формула имеет единственную СКНФ.

Один из способов получения СКНФ состоит в исполь­зовании таблицы истинности для формулы Ø А. Действительно, получив с помощью таблицы истин­ности СДНФ Ø А, мы получим СКНФ А, взяв отрицание Ø (СДНФ Ø А), то есть СКНФ А = Ø (СДНФ Ø А).

Другой способ получения СКНФ, использующий рав­носильные преобразования, состоит в следующем:

1. Путем равносильных преобразований формулы А получают одну из КНФ А.
2. Если в полученной КНФ А входящая в нее эле­ментарная дизъюнкция В не содержит переменную х_i, то, используя закон В Ú (x_i Ù Ø x_i) = В, элементар­ную дизъюнкцию В заменяют на две элементарные дизъ­юнкции В Ú x_i и В Ú Ø x_i, каждая из которых содержит переменную x_i.
3. Если в КНФ А входят две одинаковых элементар­ных дизъюнкции В, то лишнюю можно отбросить, пользуясь законом В Ù В = В.
4. Если некоторая элементарная дизъюнкция, вхо­дящая в КНФ А, содержит переменную x_i дважды, то лишнюю можно отбросить, пользуясь законом x_i Ú x_i = x_i.
5. Если некоторая элементарная дизъюнкция, вхо­дящая в КНФ А, содержит переменную x_i, и ее отрица­ние, то x_i Ú Ø x_i = 1 и, следовательно, вся элементарная дизъюнкция имеет значение 1, а поэтому ее можно от­бросить, как истинный член конъюнкции.

Ясно, что после описанной процедуры будет получе­на СКНФ А. Например, для формулы А = x Ú y Ù (x Ú Ø y) КНФ А = x Ú (y Ù (x Ú Ø y)) = (x Ú y) Ù (x Ú x Ú Ø y). Так как обе элементарные дизъюнкции содержат все переменные (x и y), то первое и второе условие СКНФ выполнены. Элементарная дизъюнкция x Ú x Ú Ø y содержит переменную х дважды, но x Ú x = x, поэтому КНФ А = (x Ú y) Ù (x Ú Ø y); причем, ни одна из элементарных дизъюнкций не содержит переменную и ее отрицание. Значит, все условия СКНФ выполнены, и, следовательно, СКНФ А = (x Ú y) Ù (x Ú Ø y).

12. Приложения алгебры логики

Релейно-контактные схемы (их часто называют переключательными схемами) широко используются в технике автоматического управления.

Под переключательной схемой понимают схематическое изображение некоторого устройства, состоящее из следующих элементов:

1) переключателей, которыми могут быть механические устройства, электромагнитные реле, полупроводники и т.д.;

2) соединяющие их проводники;

3) входы в схему и выходы из нее (клеммы, на которые подается электрическое напряжение). Они называются полюсами.

Простейшая схема содержит один переключатель Р и имеет один вход А и один выход В. Переключателю Р поставим в соответствии высказывание р, гласящее: - “Переключатель Р замкнут ”. Если р истинно, то импульс, поступающий на полюс А, может быть снят на полюсе В без потери напряжения, то есть схема пропускает ток. Если р ложно, то переключатель разомкнут и схема тока не проводит. Таким образом, если принять во внимание не смысл высказывания, а только его значение, то можно считать, что любому высказыванию может быть поставлена в соответсвие переключательная схема с двумя полюсами (двухполюсная схема).

Формулам, включающим основные логические операции, также могут быть поставлены в соответствие переключательные схемы.

Так, конъюнкции двух высказываний ставится в соответствие схема:

а дизъюнкции - схема:

Так как любая формула может быть записана в ДНФ или КНФ, то ясно, что каждой формуле алгебры логики можно поставить в соответствие некоторую РКС, а каждой РКС можно поставить в соответствие некоторую формулу алгебры логики.

13. Расчётный метод минимизации

Применение этого метода состоит в последовательном применении к некоторой формуле законов и правил тождественных преобразований алгебры логики. При этом широко используют следующие приёмы: прибавление одного или нескольких членов, входящих в СДНФ, поскольку X ∨ X ∨ X = X; выделение членов, содержащих множитель ; использование правила склеивания и др. Получающаяся в результате минимизации алгебраическая формула называется тупиковой. Функция может иметь несколько тупиковых форм.

Пример: Минимизировать функцию СДНФ мажоритарного элемента (См. п.2.2) и реализовать его схему на элементах основного базиса.

Склеивая первые три минтерма с четвёртым, получаем ДНФ функции мажоритарного элемента, которая проще СДНФ:

Y = X ₁· X ₂ ∨ X ₁· X ₃ ∨ X ₂· X ₃

Минимизированная функциональная схема мажоритарного элемента приведена на рисунке 7.