Основные равносильности

1.

2. Докажем один из законов поглощения. Рассмотрим формулу А = х˄ (у ˅ х). Если в этой формуле х= 1 то, очевидно, у ˅ х = 1 и тогда х˄(у ˅ х)= 1 как конъюнк­ция двух истинных высказываний. Пусть теперь в фор­муле А х = 0. Но тогда по определению операции конъ­юнкции будет ложной и конъюнкция х& (у v х). Итак, во всех случаях значения формулы А совпадают со зна­чениями х, а поэтому А = х.

3. 2.Равносильности, выражающие одни логические законы через другие:

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

5.

6. Ясно, что равносильности 5 и 6 получаются из равносильностей 3 и 4 соответственно, если от обеих частей последних взять отрицания и воспользоваться законом снятия двойного отрицания. Таким образом, в доказатель­стве нуждаются первые четыре равносильности. Докажем две из них: первую и третью.

7. Так как при одинаковых логических значениях х и у истинными являются формулы , то истинной будет и конъюнкция . Сле­довательно, в этом случае обе части равносильности имеют одинаковые истинные значения.

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

9. Рассмотрим равносильность 3. Если х и у принима­ют одновременно истинные значения, то будет истинной конъюнкция х˄у и ложным отрицание конъюнкции .В то же время будут ложными и , и , а поэто­му будет ложной и дизъюнкция .

10. Пусть теперь хотя бы одна из переменных х или у принимает значение ложь. Тогда будет ложной конъюн­кция х˄у и истинной ее отрицание. В то же время от­рицание хотя бы одной из переменных будет истинным, а поэтому будет истинной и дизъюнкция .

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

12. Аналогично доказываются равносильности 2 и 4.

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

14. Дальнейшее исключение логических операций не­возможно. Так, если мы будем использовать только конъюнкцию, то уже такая формула как отрицание х не может быть выражена с помощью операции конъ­юнкции.

15. З.Равносильности, выражающие основные законы алгебры логики:

16.

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

18. Таким образом, при х = 1 обе части равносильности 6 принимают одинаковые логические значения (истинные).

19. Пусть теперь х = 0. Тогда , и , а поэтому и конъюнкция . Следовательно, здесь обе части равносильности 6 равно­сильны одной и той же формуле , и поэтому прини­мают одинаковые логические значения.

20.

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

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

▪ Представление произвольной функции алгебры логики в виде формулы алгебры логики.

▪ Закон двойственности.

▪ Элементарная дизъюнкция.Дизъюнктивная нормальная форма.

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

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

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

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

Вместе с тем данная формула содержит в виде логичес­ких слагаемых всевозможные конъюнкции указанного вида.

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

Например, если принимает значение 0, а осталь­ные переменные принимают значение 1, то функция F принимает значение F(0,l,l,...1). При этом логическое слагаемое F(0,1,...1)˄ , входящее в нашу формулу, принимает также значение F(0,1,...,1), все остальные логические слагаемые формулы (1) имеют зна­чение 0. Действительно, в них знаки отрицания над переменными распределяются иначе, чем в рассмотрен­ном слагаемом, но тогда при замене переменных теми же значениями в конъюнкцию войдет символ 0 без знака от­рицания, символ 1 под знаком отрицания. В таком слу­чае один из членов конъюнкции имеет значение 0, а по­этому вся конъюнкция имеет значение 0. В связи с этим на основании равносильности х ˅ 0 = х значением нашей фор­мулы является F(0,1,...,1).

Ясно, что вид формулы рассматриваемой нами может быть значительно упрощен, если в ней отбросить те логические слагаемые, в которых первый член конъюнкции имеет значение 0 (и, следовательно, вся конъюнкция имеет значение 0). Если же в логическом слагаемом первый член конъюнк­ции имеет значение 1, то, пользуясь равносильностью 1˄ х = х, этот член конъюнкции можно не выписывать.

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

1) Каждое логическое слагаемое формулы содержит все переменные, входящие в функцию F().

2) Все логические слагаемые формулы различны.

3) Ни одно логическое слагаемое формулы не содержит одновременно переменную и ее отрицание.

4) Ни одно логическое слагаемое формулы не содер­жит одну и ту же переменную дважды.

Перечисленные свойства будем называть свойства­ми совершенства или, коротко, свойствами (С).

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

Если функция F() задана таблицей ис­тинности, то соответствующая ей формула алгебры ло­гики может быть получена просто. Действительно, для каждого набора значений переменных, на котором фун­кция F() принимает значение 1, запишем конъюнкцию элементарных переменных высказываний, взяв за член конъюнкции х_k, если значение x_k на ука­занном наборе значений переменных есть 1 и отрицание x_k, если значение x_k есть 0. Дизъюнкция всех записан­ных конъюнкций и будет искомой формулой.

Пусть, например, функция F(x₁,x₂,x₃) имеет следу­ющую таблицу истинности:

x1	x2	x3	F(x1,x2,x3)

Для наборов значений переменных (1,1,0), (l,0,l), (0,1,0), (ОД0), на которых функция принимает значение 1, запишем конъюнкции , , , а искомая формула, обладающая свойствами (С), имеет вид:

˅ ˅ ˅ .

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

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

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

Например, для формулы имеем: , то есть ДНФ А = (х˄ х)˅(х˄ у),

ДНФ А = х˄ y.

Среди многочисленных ДНФ А существует единствен­ная ДНФ А, для которой выполняются перечисленные выше четыре свойства совершенства (свойства (С)).

Такая ДНФ А называется совершенной дизъюнктив­ной нормальной формой формулы А (СДНФ А).

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

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

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

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

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

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

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

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