В.И. Игошин - Задачи и упражнения по математической логике и теории алгоритмов - 2007 (1019105), страница 12
Текст из файла (страница 12)
Р е ш е н и е. л) Составляем конъюнкцию посылок и равносильными преобразованиями приводим ее к СКН-форме: (Х-+ ( Уч У)) н (У-+ У) — = ( Хч Уч У) гЛ;~Хч У) — = (-1Хч Уч У) н н ((Хл -зх)ч Уч чУ) =(~хч Уч У) л (Хч Уч -зУ) к (-1Хч Уч -зУ). Логическими следствиями из данных посылок будут все совершенные дизъюнктивные одночлены, входящие в полученную СКН-форму, а также всевозможные конъюнкции этих одночле- 58 нов по два, по три и т.д.
Выписываем получающиеся формулы, придав им более удобную равносильную форму: ~Хч т ч У= Х-+ (Уч У) (первая посылка); Хч Уч -|У:— У вЂ” » (Хч У); -1Хч )'ч чУ =— (Х л У) -+ ) 1,~Хч Кч У) л (Хч Кч-1У) =— (Х+» У) ч Г; (-1Хч Мч У) л 1~Хч Уч »У) = 1~Хч У) ч (У» -~У) ьт -~Хч Рч ч 0 - =-1Хч К: — Х-+ ); (Х ч Уч -»У) л (-1Хч )'ч -1У) = У-+ т (вторая посылка); (-1Хч Уч У) л (Хч Чч -~У) л ~~Хч Уч -~У) = — (Х-+ (Кч У)) л л (У -+ У) — = (Х ч У) -+ К 2.35.
Найдите формулу Г(Х У), зависящую только от переменных Хи г и являющуюся логическим следствием следующих формул (посылок): а) -1Х-+ У и -1 à — » -~У; б) ~Хч У, ~У л -~ К и )'-» Х; в) Х-+ У, У+» -1Р'и У-+ Р; г) Х л ) л ~У, Х ч»; У++ -1 Ти Х вЂ” » У; д) -1Х У, )'-+ -1У, К вЂ” » (Ул У) и Хч К е) Х-+ У, )"-+ Уи Хч У„' ж) (Х ч У) — » К )' л -1Х и -1 К++ ~У; з) Хч )"ч У, Х++ ) и Ул -1У; и)Х- У,Уч Уи У У; к) -~Г+»-~У, Хч (Ул У) и Х-+ У; л) Х -+ У, ~У -+ г, г -+ К и -1У», К Решение.
л) Составляем таблицу истинности для формул, являющихся посылками: 59 Далее, в правом столбце ставим номера строк, в которых все четыре посылки принимают значение 1. Этому требованию удовлетворяет лишь вторая строка, в которой Х= 0 и У= О. Следовательно, если мы найдем такую формулу Р(Х, У), для которой Г(0, 0) = 1, то такая формула будет логическим следствием четырех данных посылок вне зависимости от того, какие значения принимает эта формула на остальных наборах значений переменных 01, 10 и 11. Это означает, что на остальных трех наборах значений переменных Хи У(01, 10 и 11) искомая формула вольна принимать любые значения.
В итоге мы получаем следующую таблицу значений для формул, служащих решениями данной задачи: Исходя из атой таблицы и используя нормальные формы (или просто узнавая логические связки по их определениям), выписываем сами формулы: Р;(Х У) =— -чХ л -~У; Г2(Х, У) — = Х с-+ У; Р3(Х1 У) = 3 У1 Р4(Х> У) 1 + Х) Р5(Хэ У) )ХА .Ц6(Хз У) = Х + У) Ут(Х У) — = -~Х ~~ -ч У; гз(Х У) — любая тавтология. 2.36.
Найдите следствие из посылок Х-+ ( У ~ Я), К-+ -ч У, (Х л л -ч И~) -+ К И'-+ Х зависящее только от переменных: а)Х,У,К д)Х У,У; и)Х,У,И~; б) Х, К В', е) У У, К; к) У, $К К; 60 в) Х, Х, 1~; ж) У, И', г) Х, 'У', ' 3) Х, И ,' Р е ш е н и е. л) Составьте таблицу значений данных четырех фор- мул от переменных Х 1; У, К И'(в ней будет 32 строки) и выдели- те те строки, в которых все данные формулы принимают значение 1 (это будут строки 1, 3, 5, 7, 9, 13, 22, 23, 24, 26 и 30). В выделенных строках определите наборы значений переменных У, К И~: 000, 010, 100, 110, 101, 111, 001.
На этих наборах каждая из искомых формул должна принимать значение 1. На оставшихся наборах (а это всего один набор — 011) каждая из искомых формул может принимать любое значение. Таким образом, мы получаем лишь одну не тожде- ственно истинную формулу, удовлетворяющую условию задачи: она на всех наборах, кроме 011, принимает значение 1, а Р(0, 1, 1) = О. Тогда ее аналитический вид таков: Р(У, К И') = — У~ ~ У'и ~ И~ 2.37. Найдите все такие не равносильные между собой форму- лы Р(Х, У Я) от трех переменных, что: а) -ч(((У вЂ” + Х) -+ (Х л -ч У)) л У) ~= (е -+ (Х <-> У)) л Р; б) (1'-+ Х) л (У-+ У) ~= ((Х л У) -+ Х) -+ Р; в) (Х++ У) ~ Х ~= Рл ((Х-+ У) ~ 2); г) Х-+ (У-+ 2) ~= Рн ((Хл У) -+ У); д) Х -+ (Ул 2) ~= ((-зХ -+ У) ч Я) ++ Р; е) (-чХ л -з У) -+ У ~= (((У вЂ” э У) ~ Х) л Р) ч ~(-зУ -+ Х); ж) У-+ (-иХ++ У) ь= Р ч ((Х-+ У) л У); з) Хч -зУч ~У~= Рл ((Х-+ У) ч (У-+ У)); и) Х-+ У ь= (Х++ Р) ++ (Уч Я); к) (Хч Уч У) л ~~Хм ~Ум -з2,') ~= (Х-+ (тХч -зу)) л Р; л) Х-+ (У++ -з2) ~= (У-+ (-зХ~ -зу)) л Р Р е ш е н и е.
л) Составим сначала таблицу истинности для фор- мул, стоящих в скобках слева и справа от знака ~ (проверьте са- мостоятельно правильность ее составления): 61 Для того чтобы из формулы со столбцом значений (е) логически следовала формула со столбцом значений (е*), нужно, чтобы в 1-й, 2-й, З-й, 4-й, 6-й и 7-й строках столбца (ее) стояли единицы (потому что в этих строках в столбце (е) стоят единицы). Но в этих строках в столбце (*е) стоят значения искомой формулы Г(Х У, У) на соответствующих наборах значений пропозициональных переменных.
Следовательно, Г(Х У, Я) должна быть такой, чтобы эти значения также равнялись 1. Далее, в 5-й строке столбца (~) стоит О. На основании определения логического следования это означает, что в той же строке столбца (**) может стоять любое значение. Но там стоит Р(1, О, 0). Следовательно, на значение Г(1, О, 0) никаких ограничений не накладывается и оно может быть любым. Наконец 8-я строка удовлетворяет определению логического следования вне всякой зависимости от того, какое значение примет на соответствующем наборе формула Г, т.е.
и на Г(1, 1, 1) также не накладывается никаких ограничений. В итоге получаем для искомой формулы Р(Х У, У) следующую таблицу значений: Расставляя на местах, обозначенных (е), всевозможными способами 0 и 1, мы приходим к четырем (с точностью до равносильности) формулам, аналитические выражения для которых выписываем с помощью СКН-формы: Р,(Х ); У) - =(~Х~ У~ У) л л~,-ьХч -зУч -зУ); Рз(Х 1", У) = -~Хм Уч У= — Х-+~ Уч У); Р~(Х )» Я) - =-чХ ~ ~ Уч ~У; Г4(Х, г, У) — любая тавтология. Наховщеиие посылок для данных следствий.
Рекомендуем решить задачи 2.38 — 2.42. 2.38. Пусть имеется формула 6(Хь ..., Х„) и требуется найти все формулы, логическим следствием каждой из которых будет формула б. Предлагается следующий алгоритм: найти СКН-форму для 6 62 и выявить совершенные дизъюнктивные одночлены от переменных Хь ..., Х„, которые в ней отсутствуют; затем составить конъюнкции формулы 6 с недостающими одночленами, взятыми по одному, по два, по три и т.д. Полученная совокупность формул будет искомой (с точностью до равносильности формул).
Докажите. У к а з а н и е. Воспользуйтесь результатом задачи 2.33. 2.39. Найдите все не равносильные между собой и не тождественно ложные формулы алгебры высказываний, зависящие от переменных Хи У, для которых следующая формула является логическим следствием (за исключением самой данной формулы): а) ~Хч~У; д) (Хч У) -+ (Хл У); и) Х++ -1У; б) Х -+ У; е) -тХ л У; к) -1Х-+ (Х л У); в) Хч~У; ж)(Хч У) — > -1Х; л) Х+~ К г) -з(Хч У); з) -1Х-+ У; Решение. л) Руководствуясь алгоритмом, указанным в предыдущей задаче, приведем сначала данную формулу к СКН- форме: Х++ У= — (Х-+ У) л (У-+ Х) =— (тХ~~ У) л (-чУч Х). Недостающими в этой форме днзъюнктивными одночленами вида Х* ~ У* являются Х~ Уи ~Х~ -1 К Поэтому искомыми посылками для данной формулы являются формулы: (Х++ У) л (Х ч У), (Х++ У) л (-~Х~ -1У), (Х++ У) л (Х~ У) л (-чХ~ -1У).
Преобразуем их равносильным образом к более простым формулам: (Х++ У) л (Х~ У) — = (~Хч У) л (Хч -зУ) л (Хч У) = — (~Х~ У) л лХ=Хл У; (Х<-э У) л (чХч ч У) — = ( ~Х г У) л (Хч чу) л (чХч ч У) ь— з (~Хн ч У) л -1 У = — -1Х л -1 У; (Х+~ У) л (Хч У) л (~Х~ -1 У) = — (~Хч У) л (Хч ~ У) л (Хч У) л л (-зХч -1У) — = (-зХч У) л (-чХч -1У) л Х: — -1Хл Х=— О.
Итак, всякая формула, для которой формула Х++ У является логическим следствием, равносильна либо формуле Х л У, либо формуле -1Хл т У, либо тождественно ложна. Поскольку из тождественно ложной формулы логически следует любая формула, то впредь мы не будем упоминать тождественно ложную формулу в числе возможных посылок для данной формулы (за исключением случая, когда тождественно ложная формула является единственной посылкой для данной формулы). 2.40. Найдите все не равносильные между собой и не тождественно ложные формулы алгебры высказываний (посылки), зависящие от пропозициональных переменных Х У, У, из которых логически следует формула: а) (Х вЂ” + 2) л (У -+ У) л Х; ж) (Х-+ (Ул 2)) л (У++ Я); б) (Х++ У) л -1У; з) -ч(Уч 2) л (Х-+ У); в)ХлУ; и) Х++ У; г) Ул -иУ; к) УлУ; д) -1Хл -1У; л) -1( У г Я).
е) -1Х++ У; 63 Р еще н и е. л) Считая, что данная формула зависит от переменных Х У, 2, найдем ее СКН-форму (проверьте!): ~( Уч 2) ив т (Хч -~ Уч 2) л (Хч Уч т2) л (-Хч т Уч 2) л (-тХч Уч ч ч2) л (Хч ~ Уч -з2) л (~Хч ч Уч -т2). В ней отсутствуют совершенные дизьюнктивные одночлены Хч ч Уч 2и -чХч Уч 2 Поэтому (на основании задачи 2.38) искомыми посылками для данной формулы будут следующие: -4, Уч 2) л (Х ч Уч 2) = -з У л ~2л (Хч Уч 2) = Хл ~ Ул~2; -з( Уч 2) л (-тХч Уч 2) — = т Ул -ч2л (-~Хч Уч 2) = -зХл -т Ул -~2; -з(Уч 2) гЛХч Уч 2) л~~Хч Уч 2) = -~ (Уч 2) л ((Хл ~Х) ч Уч ч 2) = -т(Уч 2) л (Уч 2) = — 0 (тождественно ложная формула).
2.41. Найдите все не равносильные между собой и не тождественно ложные формулы Р, зависящие лишь от указанных пропозициональных переменных (недостающую посылку) так, чтобы выполнялись перечисленные ниже логические следования: а) Х -э 2, У ++ -з У, Г(2, У) ~= -тХ ч -~ У; б) Хч -з2 У-+ (Хл 2), Г(Х, У) ~ -чУч -~2; в) Х -+ 2; -~ Уч -з2, 2'-+ ( Уч У), г(Х У) ~= Х л -~ У; г) У-+ -т2, (Хч 2) -+ (Ул У), Р(Х, У) ~= Х-+ -тУ; д) -зХч ~У, Р(Х, У, 2) ~= 2л Х; е) Х ч -з У, 2-+ (Хл У), Г(Х, 2) ~= -з Ул -т2; ж)Х вЂ” ~ У,Р(Х, У,2) ~=Ха~2; з) У-+ ~Х, (Хч 2) -+ (~Ул -тУ), Р(Х, У) ~= Х-+ Г; и) Хл Ул -з2, Уч -зУ, Р(У, 2) ~ 2л У; к) Ул2, Г(Х, У,2) ~=Х~+~2; л) Хч Уч 2, -тУл У, Р(2, У) ~= Х К Р е ш е н и е.
л) Составим сначала таблицу истинности для формул, являющихся посылками и заключениями: 64 Далее, в правом столбце поставим номера тех строк, в которых обе пось|лки принимают значение 1, а следствие принимает значение О. Этому требованию отвечает лишь 4-я строка, в которой У= 1 и Кш 1. Ясно, что при этих значениях Уи Р'искомая посылка Г(У, Р) должна принять значение О, так как в противном случае формула Хл Кне будет логическим следствием формул Хч У~Г У, -1ул К Г(У, К) (потому что на наборе Х= О, УшО, У= 1, )Г= 1 все посылки примут значение 1, а формула Х л К примет значение 0).
Никаких других ограничений на формулу Г(У, Р) не возникает, т.е. на остальных наборах (00, 01 и 10) она вольна принимать любые значения. В итоге мы получаем следующую таблицу значений для восьми (с точностью до равносильности) формул, удовлетворяющих условию задачи: Исходя из этой таблицы и используя нормальные формы (или просто узнавая логические связки по их определениям), выписываем сами формулы: Г,(У, Р) — любая тождественно ложная формула; У,(У, Р) =- -з(У-+ Р); Гз(У, Р) — = -з(К-+ с) Г4(У Р) = з(У++ ++ Р); Г5(У, Р) = — (У 1Г); Гб(У, Р) - =К; Г(У, Р) = ~У; У~(У, Й') = -зУ Г-ГК 65 3 игошин Формулы Гь Га и Г, можно не включать в ответ (две последние зависят лишь от одной переменной).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
