Игошин Математическая логика и теория алгоритмов (1019110), страница 15
Текст из файла (страница 15)
12 (введения дизъюнкции): —, ' Рпб' Рпб Смысл названий этих правил виден из характера их действия. Из тавтологии теоремы 3.1, д получаем правило контрапозиции. à — «6 Правило 6. 13 (контрапозиции): Из тавтологии теоремы 3.1, е вытекает правило цепного заключепия (или правило силлогизма). Р— «6,6-«Н Правило б. 14 (цепного заключения): Из тавтологии теоремы 3.1, м следует правило перестановки посылок. Р-«(6-«Н) Правило 6.15(перестановки посылок): 6-«(Р-«Н) 60 Наконец, из тавтологии теоремы 3.1, и получаем следующие правила: Правила б.16(объединения и разъединения посылок): (Глб) — з Н Г-э (6 — э Н) Г-+(6 — ~ Н) (Г л6) — > Н Правило 6.17(расширенной контрапозиции): (Гл6) — > Н (Гл- Н) — ~- 6 Аналогично формулируются другие правила вывода тавтологий, что рекомендуется проделать самостоятельно.
На правила 6.8 — 6.17 можно смотреть с двух точек зрения. Вопервых, каждое из них представляет собой утверждение следующего типа: формула, записанная в знаменателе, является логическим следствием всех формул, записанных в числителе данного правила. Во-вторых, каждое из этих правил можно рассматривать как правило получения новой тавтологии из уже имеющихся: если все формулы, записанные в числителе, являются тавтологиями, то тавтологией будет и формула, записанная в знаменателе правила (для доказательства этого утверждения примените замечание 6.7). Еще один способ проверки логического следования. Требуется выяснить, является ли формула Н(Х„..., Х) логическим следствием формул Р;(Хн ..., Х„), ..., Г (Хо ..., Х„), т.е.
Гь Вь ..., Г Н. Предположим, что Нне есть логическое следствие формул Р;, Рь ..., Р . Значит, существуют такие конкретные высказывания Аь ..., А„, что высказывание Н(А„..., А„) ложно, в то время как все высказывания Р;(Аь ..., А„), ..., Г„(Ан ..., А„) истинны. Если при этом удается найти распределение нулей и единиц между значениями переменных Х„..., Х„, соответствующее сделанному предположению, то предположение верно. Если же возникает противоречие, то предположение неверно.
Посмотрим на примерах, как это делается. Пример б.18. Выясните, выполняется ли логическое следование Х -э (- У и У), — Х, У вЂ” ~ У ~ Х ~ У. Допустим, что существуют такие конкретные высказывания А, В, С, что)(А-+(-Вч С))=1,Х( А)=1,)(В-+ С) =1, но ) (А ~~ С) = О. Тогда из последнего соотношения получаем 1,(А) = О, )(С) = О, что не противоречит соотношению Х( А) = 1. Далее, соотношение Х(В -+ С) = 1 дает л(В) = 0 (так как ЦС) = О). Наконец, вычислив при данных значениях А, В и Сзначение ЦА — > -~ (- В ч С)), убеждаемся что оно равно 1, а это находится в полном соответствии с допущением.
Следовательно, приходим к выводу: если высказывания А, В, С таковы, что ЦА) = л(В) = л(С) = О, то 61 при подстановке Х= А, 1'= В, У = С формулы-посылки примут значение 1, а формула Хч Упримет значение О. Значит, формула Х г Хне выводима из формул Х-ь (-,Уч Х), Х, У вЂ” > Е Разберите также пример )Чв 1.40, л из Задачника. Нахождение следствий из данных посылок. Мы научились определять, является ли данная формула логическим следствием некоторых других данных формул.
Теперь возникает вопрос„как можно находить все формулы, являющиеся логическим следствием данной совокупности формул. Следующая теорема дает ключ к решению этой задачи. Теорема б.19. Формула Н(Х„..., Х), не являющаяся тавтологией, тогда и только тогда будет логическим следствием формул Р~(Хо ..., Х„), ..., Г (Хн ..., Х„), не все из которых являются тавтологиями, когда все совершенные дизьюнктивные одночлены из разлозкения формулы Н в совершенную коньюнктивную нормальную форму входят в совершенную коньюнктивную нормальную форму формулы У;(Хн ..., Х„) л ...
л Г„(Хо ..., Х„). До каз ател ьств о. Необходимость. Дано: Ун ..., г" ~ Н. Тогда, по теореме 6.4, Р; и ... и Г ~ Н. Найдем для формул У~ г, ... л Г и Них совершенные конъюнктивные нормальные формы. Такая форма для каждой не тождественно истинной формулы существует и единственна с точностью до порядка совершенных дизъюнктивных одночленов в конъюнкции (см.
теорему 5.5). Пусть Р, н ... и л— СКН-форма для формулы Р; л ... н Г, а Н, л ... к Н,— СКН-форма для формулы Н. Тогда: У; л ... н Г„= Р, л ... к .Р», Н =- Н, к ... л Н,. Допустим, что заключение теоремы не выполняется, т.е. среди совершенных дизъюнктивных одночленов Н„..., Н; имеется такой, которого нет среди совершенных дизъюнктивных одночленов Р„..., Р». Не нарушая общности (ввиду несущественности порядка вхождения одночленов Н„..., Н, в СКН-форму Н, л ... г, Н,), можем считать, что таким одночленом является, например, Ни Итак, Н,(Х„..., Х„) Ф Р,(Х„..., Х„), ..., Н,(Хо ..., Х„) Ф Р»(Хо ..., Х„).
Тогда существует единственный (с точки зрения логических значений) набор А„..., А„, на котором совершенный дизъюнктивный одночлен Н,(Х~, ..., Х„) принимает значение 0: ),(Н,(Аь ..., А„)) = О, откуда Х(Н(Ан ..., А„)) = О. Этот набор выбирается следующим образом. Если переменная Х входит в Н, без знака отрицания, то А; таково, что ЦА;) = 0; если Х входит в Н, со знаком отрицания, то А; таково, что ЦА;) = = 1 (1 < 1< и). Каждый из совершенных дизъюнктивных одночленов Р„..., Р» в силу его отличия от совершенного дизъюнктивного одночлена Н, обращается на данном наборе в 1 (почему?): 2(Р,(Ан ..., А„)) = 1, ..., Х(Р»(Ао ..., А„)) =!.
Тогда ЦР,(Ао ..., А„)) л ... л Р»(Ан ..., А„)) = 1, откуда, в силу равносильности Р, ь ... ь Р» ж 62 = Г, и ... и Г, получаем ),(Г,(Аь ..., А„) п ... п Г (А1, ..., А„)) = 1. Следовательно, Х(Г1(Аь ..., А„)) п ... л ЦГ (Аь ..., А„)) = 1, а значит, ).(Г1(Ап ..., А„)) = 1, ..., ).(Г (Аь ..., А„)) = 1. (2) Соотношения (1) и (2) противоречат условию: Г„..., Г Н. Следовательно, в СКН-форме формулы Н нет ни одного соверщенного дизъюнктивного одночлена, который отсутствовал бы в СКН-форме формулы Г, л ...
л Г . Достаточность. Пусть Р, п ... п Р» — СКН-форма формулы Г, п ... п Г . Тогда У; п ... п Г„и Р, п ... л Р». Пусть далее Н- =Рп п ... п Р;„где ! < 1и ..., 1, < lс и !ь ..., 1, попарно различны. Тогда ясно, что если при некоторой подстановке формула Г1 л ...
п Г принимает истинное значение, то и равносильная ей формула Р, п ... п Р» также принимает значение 1. Следовательно, и все члены Рь ..., Р» последней конъюнкции принимают значение 1, включая члены Рц, ..., Рсе Но тогда и конъюнкция Рн и ... и Рн и Н также принимает значение 1. Значит, Гь ..., Г ~ Н. П Эта теорема определяет следующее правило !алгоритм) для нахождения всех (неравносильных) формул, являющихся логическшии следствиями из посылок Г» ..., Г: !) составить конъюнкцию Г1 п ... п Г„й 2) найти СКН-форму формулы Г~ л ...
п Г; 3) выписать все совершенные дизъюнктивные одночлены найденной СКН-формы, а также всевозможные коньюнкции этих одночленов. Полученное множество формул и является искомым (см. Задачник, )Ча 2.34, л). Нахождение посылок для даииого следствия. Задача нахождения всех формул, из которых данная формула логически следует, является обратной по отношению к той, которая была рассмотрена в предыдущем пункте. Ее решение основывается на следующей теореме. Теорема б.20.
Чтобы найти все формулы, логическим следствием каждой из которых будет данная формула 6(Хн ..., Х„), нужно действовать по следующему алгоритму. Найти СКН-форму для формулы 6(Хь ...,Х„); выявить все совершенные дизъюнктивные одночлены, которые в ней отсутствуют; составить всевозможные коньюнкции формулы 6(Хь...,Х„) с недостающими дизъюнктивными одно- членами. Получившаяся совокупность формул (вместе с формулой 6) будет искомой (с точностью до равносильности формул).
Доказательство. Ясно, что из каждой формулы этой совокупности будет логически следовать формула 6, так как 6 и Н ~ 6 (конъюнкция сильнее каждого из сомножителей). Обратно, покажем, что каждая формула Г, из которой логически следует данная Формула 6, имеет указанный вид„т.е. представляет собой коньюнкцию формулы 6 и некоторых совершенных дизъюнктивных одночленов, отсутствующих в СКН-форме для 6. В самом деле, пусть Г ~ 6 и 6 ге Р~ л Р» л ... п Р» — СКН-форма для формулы 6(Хь ..., Х„) и Г ге Ь! п Лз п ...
п Л, — СКН-форма для формулы 63 Г(Х„..., Х„). По определению логического следования, Р 6 означает, что если формула Г(Х„..., Х«) на некотором наборе Аь ..., А«значений пропозициональных переменных приняла значение 1, то и формула 6(Хь ..., Х,) на этом наборе примет значение 1. Другими словами, если формула 6(Хп ..., Х„) на некотором наборе Ап ..., А„значений пропозициональных переменных принимает значение О, то и формула Г(Хп ..., Х„) на этом наборе принимает значение О. Но все наборы значений переменных, на которых 6 принимает значение О, находятся во взаимно-однозначном соответствии с совершенными дизъюнктивными одночленами Рь ЮЪ ..., Ю», образующими СКН-форму для формулы 6, т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
