В.И. Игошин - Задачи и упражнения по математической логике и теории алгоритмов - 2007 (1019105), страница 4
Текст из файла (страница 4)
Дч Я-+ Д; г) Р ч -ъ Д -+ -ъ Я л Д; к) ъРл Д вЂ” » -ъР ч Я; д) ~Рч Ял ДчЯ; л) ъ Р «-» -ъ Д ч Я л Д. е) ъРч Яч Р— » Д; Решение. л) Вот эти формулы (внешние скобки опущены): (-ъР««-ъД)ч(Ял Д); ъ(Р++ -ъ((Д ч Я) л Д)); (ъР+»(-ъДч Я)) л Д; -ъ((Р«+-ъД)ч (Ял Д)); (~Р«»~(Дч Я)) л Д; -ъ((Р«+-ъ(Дч Я)) л Д); -ъ(Р««(-ъДч Я)) л Д; ъ(Р+»(-ъ(Дч Я) л Д)); ~((Р«+~Д) ч Я) л Д; ъ(Р««-ъД)ч(Я л Д); ъ((Р «+ (ъ Д ч Я)) л Д; ~ Р ««((~ Д ч Я) л Д); -ъ(Р«-э ((-ъДч Я) л Д); -ъР«-ь (-ъ(Дч Я) л Д); -ъ(Р«»(ъДч (Ял Д))); ~(Р++ ~(Д ч Я)) л Д. -ъ(Р~ ъ-ъ(Дч(Ял Д))); 1.24.
Выпишите всевозможные подформулы каждой из следую- щих формул (внешние скобки у формул опущены): а) ((Рч Д)ч -ъЯ) л(-ъРч (-ъ Дч Я)); б) (Р -» Д) -+ ((Р-+ -ъ Д) -+ (Рл Д)); в) (Р л ( Д ч -ъ Р)) л ((ч Д -+ Р) ч Д); г) -ъ(Рч Я) л(Р-» Д); д) (Р «-э Д) л -ъ(Я -+ Я); е) (Рч(Дл-ъЯ)) л (Рч Я); ж) ((Рч Д) -+ (Я-+ ~Р)) -+ (-ъЯ-+-ъД); з) (Р-» (Д-+ Я)) -+ ((Р-» -ъЯ) -+ (Р-+-ъД)); и) Рч(Д-+(Я++(Рл Д))); к) (Рл ((Д л Я) ч Х)) ч ъУ, л) ((Р««(Дл-ъЯ))ч(Рл Д)) -»1Рч (~Да Я). Р е ш е н и е. л) Подформула — это такая связная часть данной формулы, которая сама является формулой. Связность означает, что подформулу можно без разрыва «наложить» на данную фор- мулу.
Так, часть (Р«-» (Рл Д)) данной формулы таким свойством не обладает: чтобы «наложить» на данную формулу, ее нужно «разорвать» после знака «++». Поэтому формула (Р««(Рл Д)) не является подформулой данной формулы. Подформулы удобно перечислять последовательно, по числу логических связок, заня- тых в ней. Во-первых, подформулами будут все пропозициональ- ные переменные, входящие в-данную формулу (это подформулы 17 с нулевым числом логических связок): Р, Ц, Я. Далее, подформулы с одной логической связкой: зЯ, Рл Д, -з9 Подформулы с двумя логическими связками: Дл-зЯ, -зДл Я.
Подформулы с тремя логическими связками: Р~~ (Цл ~Я), Рч (~ол Я). Подформул с четырьмя логическими связками в данной формуле нет. Есть одна подформула с пятью связками: (Р~+ (Дл-~Я)) ч ч (Р л Ц). Наконец еще одна подформула совпадает с данной формулой. Таким образом, у данной формулы 12 подформул. 1.25. Составьте таблицы истинности для следующих формул и укажите, какие из формул являются выполнимыми, какие — опровержимыми, какие — тождественно истинными (тавтологиями), какие — тождественно ложными (противоречиями): а) (Р— ь Д) -+ ИР-+ -з О) -+ ~Р); б) ИР-+ О) -э Р) -+ Д; в) (Рл Щ ч ~Р)) л И-ч Д -+ Р) ч Д); г) ИР л -за) -+ Д) -+ (Р-э О); д) Р л ( Д л (-ъ Р ч -з Ц ); е) (ИР-+ Д) -+ Д) -+ Д) -+ Д; ж) ИИР ч -з Д) л (Д ч Я)) ч -зЯ) ч Д; з) (Рл (Дч Я)) -+ ИЯ-+ (Р— > О))++ (Ц-+ (Я-+ Р))); и) (ИР++ Д) ++ (Р ~-ь Я)) ++ Я++ Я)) ++ Р; к) -чИ-зЯ -+ -~(Р-+ -~( Д -+ Я))) — ~ ~(Р— ь -з О)); л) ИРч-зо)-+ О) л(-~Рч Д).
Р е ш е н и е. л) Пользуясь определениями логических связок (операций над высказываниями), составим таблицу истинности данной формулы (логические значения этой формулы записаны в последнем столбце таблицы, где сама формула обозначена Р(Р, Д)): Из построенной таблицы истинности видно, что данная формула выполнима, так как если, например, вместо пропозициональной переменной Р вставить в формулу ложное высказывание, а вместо Д вЂ” истинное, то вся формула превратится в истинное высказывание. Но эта формула является также и опровержимой, поскольку если, например, вместо пропозициональной переменной Р вставить в формулу истинное высказывание, а вместо переменной Ц вЂ” ложное, то вся формула превратится в лож- 18 ное высказывание.
Следовательно, формула не является ни тавтологией, ни тождественно ложной формулой. 1.26. Докажите, что следующие формулы выполнимы, не составляя для них таблиц истинности, а указав какие-нибудь значения входящих в них пропозициональных переменных, при которых эти формулы обращаются в истинные высказывания: а) -ч(Р-~ -зР); б) (Р— ь Д) -+ (Д-+ Р); в) (Д -э1(Р л Я)) л ~((Р ~ Я) -+ Д); г) -з((Р++ -з Д) и Я) л Д; д) (((Р-+ Д) -+ (Я -+ Д)) -+ (Я вЂ” Р)) — (Р-+ Д); е) ((Д-+ -зР) -+ Р) -+ (Р— + (зР-+ Д)); ж) (Р-+ ((Д-+ Я) -+ Я)) -+ ((Р-ъ (Д-+ Я)) -+ (Р— + Я)); з) ((Р-ь Д) л (Д-+ Я)) -+(-тЯ-+-чР); и) ((Р++ Д) л (Д <-+ Я)) -+ (Рч Я); к) ((Р л -ю Д)ч (~Р л Д)) ++ (Р++ Д); л) (Р л Д) -+ ((Я ч Д) -+ (Д л -з Д)). Решение. л) Заключение второй импликации есть, очевидно, тождественно ложная формула. Поэтому если посылка Я ~ Д второй импликации превратится при некоторой подстановке в ложное высказывание, то эта импликация станет истинным высказыванием и, следовательно, вся данная импликация превратится в истинное высказывание независимо от того, в какое высказывание обратится посылка Р л Д всей данной импликации.
Посылка Я ~ Д второй импликации обращается в ложное высказывание, когда вместо переменных Я и Д подставляются ложные высказывания. Итак, данная формула выполнима, поскольку она обращается в истинное высказывание, если вместо Я и Д подставить ложные высказывания, а вместо Р— произвольное высказывание (его истинностное значение в данном случае не повлияет на истинностное значение всего высказывания). 1.27. Докажите, что следующие формулы опровержимы, не составляя для них таблиц истинности, а указав какие-нибудь значения входящих в них пропозициональных переменных, при которых эти формулы обращаются в ложные высказывания: а) ((Х-+ ( Ул Я)) -+ (-ч У-+ -чХ)) — т -ч У; б) ЦХч У) ч 2) -+ ((Х г У) л (Хч 2)); в) ЦХ'4 У) л (( Уч 2) л ~,Хч Х))) -+ ((Хл У) л У); г) (Хл У ) ч (Хл У) ч (Ул У) ч (Ул Р') ~ ((7'л И~) ч ( К л И~) л л(-зХл-ч0); д) ((-чР-+ Р) -+ Р) -+ -з((-з Д -+ -зР) -+ ((-ю Д-+ Р) -+ Д)); е) (((Р-+ Д)-+(Я-+ Д)) — э(Я-+Р))-+(Р— ь Д); ж) ((Д вЂ” э ~Р) -+ Р) -+ (Р— ь (Р-ь -з Д)); з) (Р-+ ((Д -+ Я) -+ Я)) -+ ((Р-ь (Д вЂ” э Я)) -+ (Р— ь -юЯ)); и) ((Р— э Д) л (Я-+ -ч Д) л (Рч Я)) -+ Я; 19 к) ((Р л ~ Д) л (Ц -+ Я) л ~(Яч зВ)) -+ (В л Ц); л) (Х ч У) -+ ((-зХл У) ч(Х л-»У)).
Р е ш е н и е. л) Импликация ложна лишь в одном случае: когда ее посылка истинна, а следствие ложно. Следствием нашей имп- ликации является дизъюнкция, которая ложна тогда и только тог- да, когда оба ее слагаемых ложны. Итак, наша формула обратится в ложное высказывание, если найдугся такие высказывания А и В, что высказывание А ч В истинно, а оба высказывания -зА л В и А л л ~ В ложны. Если высказывания А и В имеют разные истинностные значения, то высказывания »А л В я А л зВ не могут быть ложны оба (почему?) Поэтому А и В либо оба истинны, либо оба ложны. Но если А и В оба ложны, то высказывание А ч В ложно, что нас не устраивает. Следовательно, А и В должны быть оба истинны.
Итак, мы доказали, что данная формула превращается в ложное высказы- вание в одном и только в одном случае, когда вместо переменных Х и Уподставляются истинные высказывания. Тавтология алгебры высказываний. Решить задачи 1.28 — 1. 33. 1.28. Составив таблицы истинности следующих формул, дока- жите, что они являются тавтологиями: а) Рч.зР (закон исключенного третьего); б) ~(Рл-~Р) (закон отрицания противоречия); в) ~~Р+» Р (закон двойного отрицания); г) Р-» Р (закон тождества); д) (Р— » Ц)++(-чД вЂ” »-»Р) (закон контрапозиции); е) ((Р-» 0) л (0-» Я)) -+ (Р-» Я) (правило цепного заключе- ния); ж) (Р+» Д) ++ (-~Рь-»-~Д) (закон противоположности); з) (Рл Д) ++ (Д л Р) (коммугативность конъюнкции); и) (Рч О) ++ (Д ч Р) (коммутативность дизъюнкции); к) ((Рл Д) л Я)++ (Рл (Ол Я)) (ассоциативность конъюнк- ции); л) ((Рч Д) ч Я) ++(Рч (Дч Я)) (ассоциативность дизъюнк- ции); м) (Рл (Цч Я)) +» ((Рл Ц)ч (Рл Я)) (дистрибутивность конь- юнкции относительно дизъюнкции); н) (Рч (Д л Я))++ ((Рч О) л (Рч Я)) (дистрибутивность дизь- юнкции относительно конъюнкции); о) (Рл Р) ++ Р (идемпотентность конъюнкции); и) (Рч Р) ++ Р (идемпотентность дизъюнкции); р) (Р— » Д) +» 1,~Рч О); с) (Р++ Ц)++((Р— » Ц) л(Д-» Р)); т) (Р л(Д ч Р)) +-» Р (первый закон поглощения); у) (Р ч (Д л Р)) ++ Р (второй закон поглощения); ф) ~(Р л О) +» (~Р ч -ч О) (первый закон де Моргана); х) ~(Р ч О) ++ (~Р л -ч0) (второй закон де Моргана); ц) (Р ч Д) ++ (~Р— » Д), 20 Р е ш е н и е.
д) Составим таблицу истинности данной формулы: Таблица показывает, что, какого бы истинностного значения высказывания ни подставлялись в данную формулу вместо пропозициональных переменных Р и Д, формула всегда превращается в истинное высказывание. Значит„формула — тавтология. 1.29. Составив соответствующие таблицы истинности, докажите, что все следующие формулы являются тавтологиями: а) Р— ~(Д-+ Р); б) (Р— ь Д) -+ ((Р— + (О -+ Я)) -+ (Р— э Я)); в) Р— ь(Д-+(Рл Д)); г) Р— ь(Рч Ц); д) (Рл Д)-+ Р; е) (Р-+ ( О л Я)) ++ ((Р-+ О) л (Р-+ Я)); ж) ((Р-ь Д) л (Р— ь -ч Ц)) -+ тР; з) (Р— э Я) -+ ((О-+ Я) -+ ((Рч Д) -+ Я)) (еразбор случаев»); и) (Р -+ Д) -+ ((Р— ь -з Ц) -+ -~ Р); к) ~~Р— ь Р; л) (Р-+ Д) ч (О-+ Р); м) (Р-+ Д) -+ ((Д-+ Р) -+ (Р+ь Ц)); н) ((Р— э Д)-+ Р)-+ Р; о) (Р+ь Ц)-+(Р— ь О); п) (Р-ь Я) -+ ((Рм Д) -+1(Яч Д)); р) (Р- (Ц,- Я)) — ((Р- 0) -+ (Р-+ Я)); с) (Г~ -+ (Рз-+ б))++((Г~ л Гз) -+ 6); т) (Г, -+ (Г~ -+ ...
-+ (Р„-+ 6) ... )) ++ ((Р, л Г~ л ... л Г ) -+ б); у) (Р— э (Д -+ Я)) ++ Щ-+ (Р-+ Я)); ф) (зР— ь Р) -+ Р; х) ((Рл Д)-+ Я)-+(Рл(о-+ Я)); ц) (Р-ь (Д -+ Я)) ++ Щ-+ (Р— ь Я)). 1.30. Докажите, что следующие формулы яалжотся тавтологиями: а) (~Р— ь (Ол-~Д)) -+ Р; б) ((-~Р-+ Д) л (~Р— э -зо)) -+ Р; в) ((Рл ~Д) -+ (Ял-тЯ))-+(Р-э Д); 21 г) (Р», (Р-» О)) -» О; д) ((Р— » О) л -з Д) -+ -чР; е) ((Р-+ О) л(о-+ Р))-+(Р-+ Я)„ ж) ((Р— » Д) л (Я -+ Я) л ~(Ц ч 5)) -+ ~(Р ч Я); з) ((Р-» Д) л (Я -+ Я)) -+ ((Р л Я) -+ ( Д л Я); и) ((Р— » Д)ч Я)+»(Р-+ (Оч Я)); к) Р— » (О-» ((Р «м) -» (Р л Д))). 1.31. Докажите, что если формулы Г и Г-э 6 являются тавтологиями, то и формула 6 является тавтологией, т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
