Математическая логика. Шапорев С.Д (1019113), страница 39
Текст из файла (страница 39)
Проблема эквивалентности слов в любом аесоцнатнв. иом исчислении влпгрнтмнчеекн неразрешима. Эта проблема репюна лишь в некоторых ассоциативных исчислениях спе- циального вида. Глава Д те рил вло римме ллв 6.8. Практик!еское занятие Мя 12. Словарные функции. Построение программ дпя машин Тьюринга 5.8.1. Пусть словврнвя функцил Е(а) в алфавите А = (А,В,С) опредсленв следулощим обрвзолл. г(л)= Вс, Е((3А)= Н,(33, ГЯ)= последней букве слова 33, е((3В)= н,(л ГЯ)= 5,'О!)=Ос, е(33С)= н,(К гЯ)= 1,'(В,г(!3))=33. ПвГлти значение Е(СВА) и определить все прсдстввляющис функции.
л 5,82, 0 ялфввиш А = ьА,В,С,Р,Е)зядвив слоеярнвя функция Е(а,В,Т). г(л,(3,у) = н(!3,у) = у, Г(аА, и у)= Н,(п, Г(о,ВНЯ;!)= а!!у, г(.в,б,у)=нз(а,г(а,р,у)Р,Т)=л, Г(аС33 у)= Н,(а,г(а (3 у)33у)= 5,(а)=аЕ, Е (а Р, (3П) = Н, (а, Г (а, 33, у) (3, у ) = у!За, Е (аЕ К у) = Нз (а, Е(а (3 у ф, у ) = В СР. Переделить значение Е(СР,А,Е) н найти соответствующее знвчеиие пренстввляющей функции. 5.8.3. Построить машину Тьюринга для вычисления функции — (1,к=О, ябпз = Исходллсесостояллие д,01!1О или д,00000 (О,л и О.
5.8 4. Какую функцию вычисляет ьлвшинв Гьюрингв со следующей системой «омвнд, длΠ— л дтОЯ, дл! л да1, дзΠ— з дв1 '! ! л длду 5.8.5. Решить звдвчу5.8.3. в алфавите Л =Ттз,~ ), если нвчвльиое снова а,) () о,. 5.8.6. Построип, машину Тыорингя для прввильного вычисления функции .т! у. Часы Ь Маюманмзсааа логнвз 5.80, Построить машину Тьюринга, правильно вычислнюшую функцию 1„"'(х,,хз,.,х„), где 1<гл <л.
5.8.8. Пусть функции з (х) и 8(х) правильна вычислимы. Поквзать, что функция Ь(х) = з (8(х)) правильно вычислииа. 5,8.9. Посзроить машины Тьюринга для правильного вычисления функций: а) х — у; б) [ — '~. 5.8.10. Показать, что если функция 8(х,у) правильно вычислимц то и функция у (х) = р, (8(х, у) = О) правильно вычислима. Глава 6 Алгебра высказываний 6.1. Ответы и решения задач практического занятия МВ 1 15 ! Все предложения, кроме предложения 6, яш~яюгся в~лсказываииями. Высказывание 2 считаюс» истинным в геометрии Евклида и лолшым а геометрии Лоба ~вескою Всказыванне 3 ложно Высказывания 1, 4 и 7 истинны. В шкушее время неизкестно, истинно гьзи ложно высказывание 5 1.5.2.
Ц р —.( число 174 не делится нв 3 ) лозкпо, род=( число 174 делится на 3 или идет дождь ) истинно: род=( число 174 делится на 3 и ндпг дожль ) ложно; !з — ь г! = ( если 174 делиш» на 3, то нлсгдозкаь ) ложно, р — з с!=( если 174 не делигся па 3, зо наст лозкль ) иш инно; р ь» д = ( ! 74 де штся на 3 зог да и только тогда, когда не идет !голые ) истинно 2! д = ( неверно, что если число простое, то оно почетное ). если число равно двум, высказывание истинно, во всеь остальных сяу ~аяз оно ложно; д — З р = ( неверию что если истинно, что если число просим, та она нечстгюе, тогда конъюнкция кочмугативна и есяи числа органе, то оно нечетное н конъюикдия нскоммутативпа ) ложно (р л д) — з р — истинное высказывание! (д ь' р) з д — = д — смотрите первый случай.
1.5 3 Высказыванияии леля|отса второе и третье угверждени». причем вю- рое лоагио, а третье иьгишю 1.54 Противоре швыданпыс2 и3 Ч ь Л. Огеегм, линяя, юяаняя 1,5,5. Не формулами являются логледовательности 1 н ф 156. 11 Ам А,А„А„А, -ь АЧА, — + Ам А ч Ат,(Аа -ь А )и (ф — +Ат); 2) г(, А„Ам А„А„т( — ь А„А, е+ Аз ' З).д,А„А„В С,Вч С,А, л(ВчС) А ч А, л(Вч С). 1,5В. Тождественно истиннммн являются формулы 2 н 3. 1 5 8. х-ь у = 1, х -ь (х-ь у) и х — ь! = 1 всегда; х — ь у — ь у и ! -е у и О е у = 1 всегда; !1, г=1, (х -ь г) — ь г — = 1 — ь я = (О, я=О.
1.5 9. Таблицы истинности всех требуемых формул представлены в табл. 6!-6да Тебяяяа бд Таллина б.1 Тлава и Ллгабрв вы аввы иии Т Тивини б.З Таллина б.а таа иа б.б Тиб вице б.б Чае В Огввгм вшвцвц, к валка Твмыцв 6.6 Т коан ги 7 Товгцца 6;7 Той ицв й В 1.5.10. Упростим формулы путем равносильных преобразований. Тогда будет очевиден набор переменных, при которых формула молгет принимать логическое значение 1. 1) Р -г Р— Р о Р и Р л Р и Р, Р = 1. 2) ф-в(РлЯ))лирк Я) — вЯ-=$ (Рлд))л~Рмд ~Я = м~о(Рг Я))л((РЧ Я)лД)м и ЯчР)л ЯЧЯ))л((РлД)о(ЯлД))м раааа б доге а ямская«еа«кн — = 'бдч Р0ч Я0чРЯ)л(Р0ч Я0)—= = — Р~~ ч Р>2 ч Р>дй 'г Р!>К ч Дй 'г РДЯ ч ДЯ ч Рай =- н РОК ч Дй г Рй з Яй(Р ч 1) ч Р>й и с!й ч Рй' и гй(Р ч Я).
Я=О, Р= К=1 3! (Р— > Я) — > ф — > Р) = Р ч 1,! ч (Дч Р) и (Р г фч Д ч Р = и ЯР ч 1) ч Р = — Р г Д. Р=1, Д=1. 1 5 ! 1. ~!Рч Р л Д) — > Я и (О л Д) — > Я и Π— > Я и 1 г Я и 1. Таким образом, данное высказывание является тождественно истииныи и не зависи~ оттого. истинны или яожны высказывания Рй п й 1.5.12. То>клее>ленная истииност« форыул показывается либо непосредственна по таблнпал> истинности, либо пузом разносы>ьных преобразований Для фориуя ! и 8 приведены таблипы истинности !табл. б 9 и 6. ! О!.
!) Таажц» 6.9 21 (Р— >Д) — > ((Р— >Я) — > Р)и Р >Д«~УчЯ«Р)м(Р>,Д)ч ч (Р л Д) ч Р и РДч РД ч Р и Р ~~ Д)ч Р я Рч Р и! 3) (Р— > Я) — > ((Д вЂ” > Я) — > ((Р ч >2) --> й !) =- Р г Я >г ~й > ч Ъ и (~ г Я) и (Р л й) ч ((Д л й)ч (! Р л Ц) ч К)) и Р Я г Дй ч чРДч Ки Рйл(5>чй)чгдй(рч Р)ч РЯ(йч К)г Р о о (й и Я) л 'дй ч >г) .=. РДйч Р0 Р. ч Р~й ч РОЯ и Р~й Глава б Аегеб вмакаяиааииа бба 1.5.13. !) ((Р— з (й п Я))ч (Д-з Р))-+Д вЂ” Р ЬгЯ4Д Р)ч йи и Р и ЦЛ ч Дч Р ч Д и Р и (гбач Я) ч Дч Рч )3 и мРОч РЯч ДчРч Дибич РЦЯпД(1ч РЯ)=-Д Тогда, например, если Р и Я вЂ” любые, а СО = 1, то неводная формула ложна. г)((Р 37) Я) ((Р С)),(Р Я)) 1,, Л, ч(Рч ШчРЯчОЯ)и Р4яч(рчдя)=ряяч рчдя Тогда Р= 0=0, Я=!.
3) Длв формулы 3 таблица истинности такова !табл. б.11). 7'яблияе б.11 Р)зтабл.б.)!видно,что Р=1, ьг= О. 1.5.14. (Р 0=1 !) Пуать, например, Оч Я= О, тогла Я=О и Л= 0 и ( (1 0=1 (Р=О т. е. ~, чго невозможно. 2) Предположим, что Р— з Я=О. Тогда, очевидно, Р=) и Я=!, т.е Я=О. Следовательно. РчД=!чД=Очй)=1 и Лч ги' = 0 ч Д = 1, т е Д = 1 и ь) = ! одновременно, "по невозможно.
Таким образом, всегда Р— з Ли О,т.е. Р ' Л = 1. Част б. Омеги женил, юаан я 3) Пусть Во И'= О. Отсюда по таблице истинности В= О, И'= О, )Р-е0=1, Но Р— «В=! и «А — «И'"=1, т.е, ~ ' Тогда Д=О н '1«А -«О =! . Р=О, Ра !А = Он 1. Получено противоречие,т, е, Вч И«=1. !.5.!5. Таблицы истинносщ (табл. 6.12) лдя двухместных операций имен«г сяедующий вид. Таблина б. 72 Все эти таблицы различаются только последним столбцом, элементы которого заменены значком *. Вместо " мажет стоять 1 или О, причем возмоягны любые комбинации. Различных комбинаций будет 2' = 16 1зтэ раъчещсния с повторениями из двух элементов по четыре). 1.5.16. А аВн АлВ, Ал Вм Ач В.
1.5.17. Составив«таблицу истинности для операции ех начиная с тех строк, для которых Ю истинна. Каждой такой строке псстави» в соответствие каньюнкцию тех простых высказынщий, котОрые в этой строке истинны, и отрицание остальных. Затем найдем дизъюикцию этих конъюнкций. Кажлая из псщрзенных конъюнкций будет истинна только при тех значениях истинности простых вьюказмваний, кОторые стоят в соответствующей ей строке. Ясно, что логическаа операция 9 определястая множеством наборов, на которых полученное сложное высказывание истинно и толька на них, на ссыльных ано ложно. Например, для зканвялснцнн: 5 «.'-э Аз — 1д — «Аз)л(А« — «гд). Таблила б,!3 Тлела б. Алке аискааиаанча гтт Из табл. 6.13 видно, что (А, л А, ) ч (А, л А, ) и (А, ч ( ( л А, )) л (Аз ч ГА1 л А, )) и — = ((тй ч Л, )л (А> ч Л.з )) л ((Аз ч А )л (Аз ч Аз)) — = (А ч Аз)л л(Л, чЛ~)п(Л~ — ада)л(Аз чА~)п А~ Я!Аз.
1.5.18. !) А -з В и Ач В и Ал В и Ал В; 2) Ал (АчС)л(ВчС)пАл(ВчС)л(АчС)и и ((Л ч В) л (Л ч С)) л (Л ч С) и ((А л В ) л (А ч С)) ч ч ((А л С) л (Л ч С)) и (А л (Л л В)ч С л (Л л В)) ч ч (А л (А и С1ч С л (А л С)) и (Л В ч АВС) ч (А ч А С) и и АВ(1 чС)ч АС= — АВч АСи (АлВ)ч (АлС). 3) (ЛлА)и ЛАм Л; 4) (Ач (Вл А))= — А или по табл. б 14. Тайна! ° 6. !а 5) Логические значения левой и правой частей формулы 5 приведены в табл. 6.15. Таблица 6.!5 Часа б. Огяепа аминя, ннч Таблице б./5 (окенче вф 777 6) (А д В)ч ((А ч В) а ГА ч В)) н ((А л В)ч (А ч В)) л ((А п В) ч ч (Ач В))и (((Ачй)ч А) ((АчВ)ч В))л(((АчВ)чА)л л ~ййч В)ч В))е((Ач В) л (Ач В))л(1 л1)и Ач В.
7) Логические значения левой и правой частей формулы 7 приведены в табл. 6.16. Таблица Мб 1.5.19. Пусть дана искодная формула А, Если оиа содержит импликапию, то эту логическую связку можно убрать, используя эквивалентность .ц — т В, и тц ч В,, где тц и В, — подформулы формулы А. Отри~ганне всегда можно отнести к простым выскюываниям по формулам .ц дВ, ° тц чВ, и тц чВ, и.ц лтц и исполюуя следуюшую зк«иватеитиосты если С вЂ” = П, то 5(С) — 5(В).
главе В. ллгебра икн зм иив 273 6.2. Ответы и решения практического занятия МВ2 1.! 1 1. пусть формуле ( соответствует функция Г(гз), формуле А, соогЬютина, веютвУег бУлева фУнкциЯ Г(Аз). Если А, = ( ' го г(4) = ~ ' ( ложь, (О Тогда ((А)= /1А), «(А о Аз) = 1(А )о,р(Аг), г'(А„оА,)=г'(А,)от(А,),г'(А,— А,)=г(А,)- У(А,). Видно, что значению истина всегда соответстауьг значение 1, значению ложь соответствует О. 1.11 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
