Тема 8. Конъюнктивная нормальная форма(КНФ)

▪ Элементарная конъюнкция.

▪ Конъюнктивная нормальная форма.

▪ Минимальная КНФ. Два правила поглощения.

▪ Совершенная конъюнктивная нормальная форма(СКНФ).

▪ Два способа получения КДНФ.

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

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

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

Например, для формулы имеем:

, то есть

КНФ A .

Но так как х ˅ х = х, у ˅ у = у, , то КНФ А = .

А так как , ,

то КНФ A= .

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

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

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

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

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

Каждая не тождественно истин­ная формула имеет единственную СКНФ.

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

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

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

Путем равносильных преобразований формулы А получают одну из КНФ А.

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

3. Если в КНФ А входят две одинаковых элементар­ных дизъюнкции В, то лишнюю можно отбросить, пользуясь равносильностью В˄ В = В.

4. Если некоторая элементарная дизъюнкция, входящая в КНФ А, содержит переменную x_i дважды, то лишнюю можно отбросить, пользуясь равносильностью x_i ˅ x_i = x_i.

5. Если некоторая элементарная дизъюнкция, вхо­дящая в КНФ А, содержит переменную x_i и ее отрицание, то = 1 и, следовательно, вся элементарная дизъюнкция имеет значение 1, а поэтому ее можно от­бросить, как единичный член конъюнкции.

Ясно, что после описанной процедуры будет получе­на СКНФ А.

Конъюнктивная нормальная форма(КНФ)

В результате изучения курса математической логики учащиеся должны:

- знать определение «элементарной конъюнкции», «конъюнктивной нормальной формы», «минимальной КНФ», «совершенной конъюнктивной нормальной формы(СКНФ)», два правила поглощения, два способа получения СКНФ;

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

Тема 9.Приложение алгебры логики в технике (релейно-контактные схемы)

▪ Понятие релейно-контактной схемы (РКС).

▪ Определение переключательной схемы.

▪Функция проводимости. Нахождение функции проводимости для некоторых переключательных схем.

▪ Равносильные схемы.

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

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

Еще в 1910 году физик П. С. Эренфест указал на воз­можность применения аппарата алгебры логики при исследовании релейно-контактных схем (РКС). Однако его идеи стали реализовываться значительно позже, когда создание общей теории конструирования РКС стало ост­ро необходимым.

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

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

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

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

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

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

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

Сопротивления, конденсаторы и т.д. на схемах не изображаются.

Переключательной схемой принимается в расчет только два состояния каждого переключателя, которые называют «замкнутым» и «разомкнутым».

Рассмотрим простейшую схему, содержащую один переключатель p и имеющую один вход А и один выход В. Переключателю p поставим в соответствие высказы­вание р, гласящее: «Переключатель p замкнут». Если р истинно, то импульс, поступающий на полюс А, может быть снят на полюсе В без потери напряжения. Будем в этом случае говорить, что схема проводит ток. Если р ложно, то переключатель разомкнут, и схема тока не проводит или на полюсе В снимается минимальное напря­жение при подаче на полюс А максимального напряже­ния.

Если принять во внимание не смысл высказывания, а только его значение, то можно считать, что любому высказыванию может быть поставлена в соответствие переключательная схема 1.

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

Конъюнкция двух высказываний p и q будет представ­лена двухполюсной схемой с последовательным соедине­нием двух переключателей Р и Q (схема 2).

Эта схема пропускает ток тогда и только тогда, когда истинны и p, и q одновременно, то есть истинна конъюн­кция p˄q.

Дизъюнкция двух высказываний p к q изобразится двухполюсной схемой с параллельным соединением двух переключателей p и q (схема 3).

Эта схема пропускает ток в случае, если истинно высказывание p или истинно высказывание q, то есть истинна дизъюнкция p ˅ q.

Если высказывание есть отрицание высказывания р, то тождественно истинная формула ˅ р изображает­ся схемой, которая проводит ток всегда (схема 4), а тож­дественно ложная формула ˄р изобразится схемой, которая всегда разомкнута (схема 5)

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

Как было показано, всякая формула алгебры логики путем равносильных преобразований может быть пред­ставлена в виде формулы, содержащей только две опера­ции: конъюнкцию и отрицание или дизъюнкцию и от­рицание. Из этого следует, что всякая формула алгебры логики может быть изображена П-схемой и, обратно, для любой П-схемы может быть записана формула, ко­торая изображается этой схемой.