Основы дискретной математики В.А. Осипова (552659), страница 9
Текст из файла (страница 9)
Поэтому к Вг применимо индуктивное предположение; 4) А1 имеет вид -(В1 ',г С1). Тогда А1 = . Вгй. Сг и в ~В1, С1 логических символов меньше, чем и. Поэтому существуют такие формулы Вг, Сг, что - В1 = Вг, С1 = Сг и в Вг, Сг отрицание встречается только перед переменными. Ясно, что А1 = ВгйС2 и ВгйС2 является формулой с «тесными» отрицаниями; 5) А1 имеет вид — (ВгйС1). Тогда А1 = — В1 Ч вЂ” С1, и далее поступаем, как в предыдущем случае. При практическом преобразовании встречающиеся в формуле отрицания просто передвигают к переменным, используя законы де Моргана и уничтожая пары стоящих рядом отрицаний, если таковые встречаются.
Пример 2.5. Преобразуем к формуле с «тесными» отрицаниями: -(-(Х,й-Х,) Ч (Х,й-Х1)) = (Хгй Хг)й-(Хгй. Х1) = = — -1(Хгй-1Хг)й(-1Хг г/-~-~Х1) = = ( 1Х1 Ъ ' 'Х2)й( 'Х2 в Х1) = = (- Х1 гг Хг)й(. Хг у Х1). 3-й этап Полученную формулу Аг можно считать построенной из переменных и их отрицаний с помощью многочленных 50 Глава 2.
ЭЛЕМЕНТЫ МАТЕМАТИЧЕОКОИ ЛОГИКИ 2.1. Логика высказываний 51 конъюнкций и дизъюнкций. Применив теперь обобщенную дистрибутивность Й относительно ~/ последовательно преобразуем формулу (аналогично приведению алгебраического выражения, составленного из переменных, с помощью сложений и умножений к виду многочлена). Заметим, что при этом Ч будет аналогична сложению, а Й вЂ” умножению. Полученная в результате преобразований формула В будет удовлетворять требованиям доказываемой теоремы. Пример 2.6.
Применим преобразования 3-го этапа к формуле с «тесными» отрицаниями, полученной в примере 2.5: (- Х1 ~/ Хг)й(- Хг ~/ Хг) эз аэ (-Х1Й- Хг) Ч ( Х1ЙХ1) ~/ (Хгй- Хг)'/(ХгйХг). В результате мы получили формулу, находящуюся в ДНФ. Говорят, что формула А находится в конъюнктъвной нормальной 4орме (КНФ), если формула А" определена (т. е. в А нет символов и Э) и находится в ДНФ. КНФ можно дать и другое равносильное определение.
Формулу называют элементарной дизъюнкцией, если она является дизъюнкцией (возможно, одночленной) переменных и отрицаний переменных. Формула находится в КНФ, если она является конъюнкцией (возможно, одночленной) элементарных днзъюнкций. Теорема 2.3 (о приведении к КНФ). Для любой 4ормулы А можно найти такую 4ормулу В, что А находится в КНФ и А ае В. Формула В называется конъюнктивной нормалъной 4ормой 4ормулы А.
Первое доказательство. Пусть А эз А1 и А1 не содержит символов, ~. Пусть В1 — дизъюнктивная нормальная форма для формулы А~. Тогда В1 находится в КНФ и, кроме того, по принципу двойственности В~ = — (А~)* = А1 = А. Значит, В~ удовлетворяет требованиям теоремы. Второе доказательство, Применив первые два этапа из доказательства теоремы 2.2 о ДНФ, получим формулу Аг, равносильную А, не содержащую символов °, ~ и содержащую отрицания только перед переменными. Преобразуем теперь Аг как алгебраическое выражение, считая на этот раз Й аналогом сложения, а Ч вЂ” аналогом умножения и применяя дистрибутивность Ч относительно й. Приведение формулы Аг к виду многочлена дает на этот раз КНФ. Пример 2.7.
Приведем к КНФ формулу (ХгйХг) '" ( ХгйХз) =— = ИХгйХг)й( Х1йХз)) ~/ (-(ХгйХг)й-( ХгйХз)) = = (ХгйХгй. ХгйХз) ~/(( Хг Н. Хг)й(- Хг '/ Хз)) = — : (Х1ЙХгй- Х1ЙХз) Ч ((- Х1 г/ - Хг)й(Хг '/. Хз)) эз = (Х, /--Х, ~/ -Х,) й(Х, / Х1 / -Хз)й й(Хг Ч- Хгг/. Хг)й(Хг ~~ Хг ~/. Хз)й Й(- Хг '/- Х1 '/. Хг)й(- Х1 '/ Х/'/. Хз)й й(Хз''. Хг и Хг)й(Хз ~/Хг ~/- Хз). Заметим, что первое преобразование основано на равносильности 16. Нетрудно видеть, что ДНФ не является однозначно определенной.
Рассмотрим, например, формулу Хг'/(ХгйХз). Она уже находится в ДНФ. В то же время преобразование Хг ~/ (ХгйХз) =— — = (Х1 '/ Хг)й(Хг '/ Хз) аэ (Х1ЙХг) '/ (ХгйХ3) / (ХгйХ1) / (ХгйХз) дает для этой формулы другую ДНФ. Конечно, все ДНФ данной формулы равносильны. Выделим среди ДНФ формулы так называемую совершенную дизъюнктивную нормальную форму. Пусть формула А зависит от списка переменных < Х... Х;„... ..., Х;, ). Говорят, что А находится в совершенной дизъюнктивной нормальйой 4орме (СДНФ) относительно этого списка, если выполняются следующие условия: 1) А находится в ДНФ; 2) каждый днзъюнктиввый член А является й-член ной конъюнкцией, причем на «ьм месте (1 < 1 < /«) этой конъюнкции обязательно стоит либо переменная Х;„либо ее отрицание — Х;, ", 3) все дизъюнктивные члены А попарно различны. Пример 2.8.
Пусть < Хы Хг, Лз ) — список переменных. Тогда формулы Хгй. Хгй Хз, (ХгйХгйХз) г/(. ХгйХгйХз)~/ ~/(ХгйХгй- Хз) находятся в СДНФ относительно этого списка переменных. 52 Глава 2. ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ 24, Логика высказывании Теорема 2.4. Пусть формула А зависит от списка переменных < Х;,, Х;„..., Х; > и А не тождествепно-лоокная формула.
Тогда существует такая формула В, что А ив з В и В находится в СДНФ относительно списка переменных < Хй, Хио ..., Х;„>. Согласно теореме о приведении к ДНФ существует формула А1 такая, что А = — А1 и А| находится в ДНФ. При этом можно считать, что А1 зависит от списка переменных < Х;„ Х;„..., Х;, > (в процессе приведения формулы к ДНФ новые переменные не появляются).
Будем исходить из этой формулы и просматривать ее дизъюнктивные члены, т. е. элементарные конъюнкции: 1. Пусть в элементарную конъюнкцию одновременно входят какая-нибудь переменная Х;, и ее отрицание. Если это единственная элементарная конъюнкция формулы, то она на всех оценках принимает значение Л, а следовательно, и вся формула, что невозможно, так как предполагается, что формула не тождественно-ложная. Значит, имеются другие элементарные конъюнкции, и формула (после некоторых перестановок) будет иметь вид (Х;,й-Х;,йс) ~ Р, где С вЂ” остальные члены нашей элементарной конъюнкции; Р— остальные дизъюнктивные члены всей формулы.
Но (Х;, й- Х;,йС) и'Р ив з Р, поскольку первый дизъюнктивный член левой части при всех оценках принимает значение Л. Следовательно, наша формула равносильна Р, а рассматриваемую элементарную конъюнкцию можно отбросить. Поскольку А не тождественно-ложная, то после всех таких шагов всегда останутся какие-то неотброшенные элементарные конъюнкции, 2.
Пусть в некоторой элементарной конъюнкции переменная Х;, (или . Х;,) встречается несколько рвз. Тогда в силу идемпотентности (равносильности 2) можно оставить только одно вхождение Х;, (или . Х;,). 3. После проведенной обработки каждая элементарная коньюнкция С будет содержать какую-нибудь переменную не более одного раза (включая ее вхождение под знаком отрицания), при этом возможны только следующие варианты: а) конъюнкция С содержит в качестве своего конъюнктивного члена один раз Х;, и не содержит ни разу Х;„ б) конъюнкция С содержит один раз Х;, и не содержит ни Разу Ху~ в) конъюнкция С не содержит ни Х,„ни . Х;,; В последнем случае мы заменяем С на (СйХ;,) М (Сй- Х;,) по основной равносильности 14 (первой формуле расщепления).
Эту операцию следует проводить до тех пор, пока для каждой элементарной конъюнкции и каждой переменной Хн не будут выполнены условия «а» или «б». 4. Переупорядочим в каждой элементарной конъюнкции ее конъюнктивные члены таким образом, чтобы на 1-м месте в ней стояла Х, или . Х, 5. Если в преобразованной формуле несколько раз повторяется одна и та же элементарная конъюнкция, то, пользуясь основной равносильностью 5 (идемпотентпостью), выбрасываем все ее вхождения, кроме одного. Пример 2.9. Формула (Х1й Х1йХз) ч'(Х1й ХзйХ1)ЧХ2 зависит от списка пеРеменных < Хм Хз, Хз >.
ПРиведем ее к СДНФ относительно этого списка. Первую элементарную конъюнкцию можно отбросить, во второй оставить только одно вхождение Х;, а затем провести преобразования по пп. 3, 4, 5; (Х,й-,Х,) ~ Хэ = (Х1й- ХзйХ.) ~ (Х1й- Хзй "Хз)М Н (ХзйХ1)Ч (Хзй- Хг) =— (Х~й- ХзйХ2)Ч Ч (Х1й- Хзй Хз)Ч (ХзйХ1йХз) ~ (ХзйХ1й- Хз)М Ч(Х,й-Х1йХз) М(Хзй- Х|й Хз) = = (Х,йХ,й. Хз) ~ (Х, й-Хзй- Хз) " (Хг йХзйХз)"' Ч (-.Х,йХ,йХз) М (-Х1йХзй-Хз). Как уже отмечалось, СДНФ обладает некоторой однозначностью, а именно справедлива следующая теорема. Теорема 2.5 (о единственности СДНФ). Если В1 и Вв — совершенные дизъюнктивные нормальные формы формулы А относительно списка переменных < Х;„Х„, ..., Х,, >, то Вз и Вз могут отличаться только порядком своих дизъюнктивных членов.
Докажем эту теорему несколько позднее (см. замечание 2.2 п. 2.2.1). Следует отметить, что если расширить список переменных < Х;,, Х;„..., Х,, >, от которого зависит формула А, новыми 54 Глава 2. ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ 2.1. Логика высказываний переменными (реально в А не входящими), то относительно нового списка А будем иметь другую СДНФ. Например, СДНФ формулы Х1 относительно списка переменных < Х1 > совпадает с самой формулой, а относительно списка переменных < Х1, Хз > является формулой (Х1въхз) М (Х1ъс. Х2).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
