Математическая логика. Шапорев С.Д (1019113), страница 18
Текст из файла (страница 18)
Тогда — ((у -у (хи х))м ! — Л -е (хо х). Правило удаления импликации применительно к этой формуле будет иметь яид — В-е хчх;~-В Наконец, сделаем последнюю подстановку ~-х ох — ((хч х)м~ — Ам А. Итак, исходная формуладоказана. ~ — А — ьв;~ — Аэ В Пример б. Доказать аыеодимгють ~-А В этом прнмере исходное множество формул имеет лид Г = (А-+ В, А — э В). Воспользуемс» амеодимой формулойг, полученной на основе девятой аксиомы ~ — (А — э В) — э (В-+ А). По праеилу простого заключенна имееьг )-А >в~-(А- в)- ~в- А) тогда по правилу силлогизма ~ —  — эА ~- А -+ В; )- В-+ А получается вспомогательная формула .
Пусть ~-А — з А теперь А — любая докззуемая формула. По правилу удаления ~ — А;~ — А -ь А импликацни А Глава 2 И нслсмм высяв н яня г гв Пример 6.Доказать Г= (Л вЂ” «В» — ЛлС вЂ” г ВлС. Г А — ь В. И множестве Г ню формулы С. Введем се дополнительно, положив Г, = (А-е В, Ао Сд Гс Г, . Тогда г г )-А С , В . По правилу ввелсния копънзш пни ппз * ппз ~-л с.,'—,~ г-г ~-з.1-~ в ,-г рв г,)-л:у;)-в — Здесь Г =Г, и Г,Г,шг. Воспользуемся теперь ЦД;~ — ЛоВ Г,С)- А В данном Г)-С-ь Л' теоремой ледукнии случае получим . Итак, формула АнС-» Во С выводима (-"'))"' А — г  — Л л С -ь В л С Пример 7.
Докажем более сложное, чем указано в списке правил исчисления высказываний, правило ввсдени» дизьюнкпии г,+с;г,б)-с Г,А гМ~ — С Г.С)- А По условию Г,+С, Г,В-С. По теореме лелукпии Г~- С вЂ” г Л г,А-с г,у~-с имеем * и . Сдслюм в восьмой аксиоме у)-л- с у)-в- с' следующую замену переменим»: ,г в,г. — ) ((л -ь ) -ь 'бу — г «) — ь (л ч у — ь в))) —= только из Г, введение Г, с формулой АлС было лишь вспомогательным действием. Чв ы а Ма«аман«чеслав логика ттб иГ(А — «С) — «((В-чС)ч(Ачй — «С)) и применим правило сложного заключения ~ — А — + С; ~-  — «С; ~ — (А -+ С) — «(( — «С) — «(А ч  — «С)) ~ — Ачв — «С Длл доказательства требуемой формулы воспользуемс» правилом Г) — С вЂ” «А Г) — А гв-+С удаления импликации . В нашем случае Г,С) — А ГА й(-С Следовательно, правило введеник дизьюнкции доказано. Г(- А; Г)- В Пример 8.
Докажем правило введени» конъюнкции Г)-А В По условию Г1-А, 11 — В. Докажем сначала, что (А,вй'-Ал В. Для этого сделаем подстановки в пятой и первой аксиоме: квм — ) ((х — «х) — «((х -«у) — «(х — «х л у))) ~- (А — «А) -«((А -+ В) — « вл — э(А — «АлВ)), — )(х — «(у-«х))и~- — «(А — «В), Ранее уже покаэьгвалось, что формула А -«А выводима из любой совокупности формул, в том числе и (А,вй' — А — «А. Применим несколько раз правило простого заключенна ~- А -«4 )- (А — «А) -«((А -+ В) -«(А -+ А л В)) ~ — (А -+ В) — «(А — «А л В) ~-В~- — «(А — «В) ~ — А — «В(А-э В) — «(А — «АлВ) ~- А — «В ( — А-«Ал В ~-АлВ улавв 2 Исмюмние вн кюыв иий й.4. Практическое занятие Изб.
Исчисление высказываний: лравила вывода и доказуемость формул 2 4.) . Выписать все падформувы формул. а) А-» Во Ал В; б) А-» (В-»(А» В))» в) ((А — » В)л ( — » С))-+(А~ С) г) (А, — » Ат т А, ) — » А, пг 2.4.2. Пр»»меняя только правило подстановки, доказать, что вьюодины следующие формуль»: а) Ал В-+ Ал Во С; б) (А -+ А) -+ ((А -» В л С) -» (А -» А л В л С)); в) (Ал В-» (С-» ВлС))-» ((Ал В-» С)-»(Ал В-» Вл С)). г) (А т  — » С) — » ГС вЂ” » А л В). 2.4В. Являются ли выводами в исч слепни высказываний слсдуюогис послеловательностн формул а) А — »(А» В); б) А — + (А о В), (А — » (А а В)) -» ( — » (А -» (А и В))), В -» (А -» (А о В)); «) А -»(В-» А),(А -»( †» А)) †» В, В 2.4.4.
Выводами из каких мно»веста формул Г является олслуююая последовательность формул: а) А -»(В -» С) А, В -» С, В, С; б) (А -» В))-ч ( — » А). А — » В,  — » А В, А; в) А -» В, А   — » Во С Во С, (А — » В) — » (А — » В и С). ~юа К. Исчисление еьсказызаний гщ 24,8. Докззать производные правила вывода: ,~, А„,.„А, ~- В а) ~ — А, л А, л...лА„— «В ~- А — «В,)- А — «В 6) )-в ! — А,( — В в) )-А — «В' ~-Ал В г) — —; )-А )-А.
А )-А 24.9. Используя обобщенную теорему дедукции, доказать слелующпе формулы: а) (А — + В) -+ (( — «С) — «(А — «С)); 6) (А — «В) — «((С -+ А) — «(С -+ В)); в) А — «(В-«А) — «В. 2.4 10. Введем следующее исчисление (пачиоле««ие Лукзсевича) множество предметных переменных и констант состоит из бесконечного числа букв и знаков, — «Все буквы есть формулы, если ф — формула то ф также формула, если ф и ф — формулы, то 4« — «р тоже формула.
Система аксиом следующая: а) (А — «В)«(( — «С)-+(А-«С)); 6) (А — «А) — «А; в) А-«(А — «В). Справедливы правило подсгмювкн и правило заключения. Доказать, что в исчислении Лукасевича выводима формула А -«А. Весть!. Ыагемегичеокы яника !20 2.5. Монотонность и эквивалентность формул исчисления высказываний Формула В(А), содержащая переменное высказывание А, называется монотонно возрастающей (убывающей) по А, если из выводнмссти А, -+ А, слелует выводимость В(А,)-+ В(Аз) (В(Аз)-е В(А,)). Говорят, что формула В сильнее формулы В, если ~-  — + В Эти дв» понятия позволяют упрощать доказательства, в которых производится замена части какой-нибудь формулы более слабой или более сильной формулой. Из определения монотонности следует, что если формула В(.'.() монотонно возрастает по А, и ~- В( ( ), то, заменив А, более слабой формулой А,, получим также выводимую формулу.
Действительно, пусть )-:( †А, и ~ — В(у( ). Из определения монотонности )-В(А!)е В(Аз). Тогда по правилу )- В(А )~- В( ( )-ь В(А, ) простогозаключения (- В(А,) Наоборот, если В(А,) убываег по А„ то В(г() осюется выводимой при замене ( более сильной формулой. Теорема 2.2 Все основные лагнчыкне операции монотонны пв всем учвствуяощнм в инх переменным высказываниям! формулы АлВ и АчВ монотонна ввзраетают па А и В, А убывает по А, А-гВ убывает по А н возрастает по В. Докогогвельсжео.
Докажем юлька, чта Ач В монотонно возрастаю по А. Пусть ~ — у( -! ~ . Из аксиомы Ю» (см, формулы (2.).))) подстановкой получим воя ) (У з л ч У) ~-  — ! Аз ч В. подстановка в )и ~ дает у (х — ! «и у) н ! — Аз — ь А, и В, отсюда по правилу силлогизьга ~- е( — + А„) — А, -е ~ и В Наконец, сделаем подстановку в аксиому РВ ь ~ — А, -ь А, и В Глава д Исчисление ем яваы чл тогда )(х-чх)ь((у-ьа) — ь(хоу — ь ))и *я' — = (- (А, -ь А, о В)-ь ((В ь Ат и В) -ь (А, и В -ь А, о В)), Теперь, применяя дважды правило простого заключения, потгучиьг )- А, — ь Ат и В ~ — (Л, -ь Дз и В)-+ ((В -ь Аз и В) -ь (Л, «В ь А и В)) )-( — ь А о В)-т (А, о — ь Л, и В) ( — В -ь А ч В) — ( — ь А, о В) ь (г( и В -ь А,: В) ) —,~ о В ч А, о В Итак, ~ — г( о  — ь А, и В, т.
е, формула А о В монотонно возрастает. Прочие положения теореьгы 2.2, доказываются аналогично Из алгебры высказываний имеем (А-ь В)л(Вч А)и А ьч В Знак г-з нс является символом исчисления высказываний и может употребляты:» лишь для сокращения выражений Этот знак — символ языка, на котором доказываются утверкгдения об исчислении. Иногда этот язык назывмаг мемаязыкач. Две формулы А и В называются океавюегггггггынв, если ) — ! т-з В. Очевидно. что всякис две выводимые формулы исчисления высказываний эквивалентны.
Действительно, Г: А,В, А -ь (В -з А),  — ь А , В -т(А -+ В) ,А -ь В, 1(г, И-л-,~л б.ф ,У (А -+ В) л (В -ь А) Таким образом, если )- А и ~ — В, ~о ~ — А му В. Можно продолжить вгавод, Г) — В-т А мюпользовавшись правилом удаления импликвиии Тогда Г, т» — А ~-В- А ~-А — тВ шзраведлиаы формулы и — —. Слсдаватсльна, если лве 2~-А +В ' формулы эквивалентны,.г, с ~ — Агу В,то т( — В и ~-Л.
Ч ! Магом гичесяея логика Соотношение экаиаалентиости рефлексивно. Л «-э Л, симметрично, т. е. если А « э В,то В « э А;транзит»ело если А « ь В и В «ь С то А « ь С . Теорема ТА Пусть А — формула нсчнслени» высказываний, а  — ее подформула.
Пусть А получается нз А путем замены некоторого вкождеин» В на формулу В'. Тогда если В «-э В', ш А «-э А', т.е. ) — (В «-э В')-ь (А(В) «-~ А(В')). Понятие эквивалентности имеет большое практическое значение, т. к. основные свойства формул исчисления высказываний сохраняются прн переходе к эквивзлентным форь«улам.
Поэтому вмк««о уметь накодить ллз калмой формулы эквивелентиу«а ей формулу, но устроенную но возиожности более просто. 2.б. Связь между формулами алгебры высказываний и исчисления высказываний Как уже >понг«««алесь, алгебру высказываний можно представить в качестве интерпретации исчисления высказываний. Исчисление высюзываний построено как аксиоматическая теория путем форнелизации алгебры высююываний. Покюкем, как множество теорем исчисления совпалаег со множеством тождественно истинных формул аэгебры высказываний. Введем понятие значения формулы исчисления высказываний.
Пусть А— формула исчисления высказываний, а з;,х,...,х„ — ее переменныс, аназ,...,а„— набор значений этих переменных. так как и, б (01) г = 1,л, векюр (аназ,,пь) имеет 2" значений. т Теорема йй Всяка» формуле, доказуемая в исчислении выскнзываний, ивл»етс» тожлествеиио истинной формул»де алгебре высказываний. Докозительстео. Необходимо ршсмотреть и доказать трп случая а) тождественную истинность аксиом исчисления высказываний; б) тождественную истинность формул, полученных применением к тавтологиям правила подстановки; в) тождественную истинносн, формул, полученнык из тавтологий по правилу простого заключения, Глава 2 Иочвслеиие внеюзн»ння газ Тождественная истгшность якове»гас»имения проверяется непосредственно перебором всех значений их персмениых по таблицам истинности.
Проверич по табл. 2.6 1, например, аксиомы, содсргкащис три переменньщ, Пяагвгс» Да. 1 Прочие аксиомы проверяю к» аналогично. Пусть х,х„...,х„,х — перечень всех переменных, вхолящих в формулы А и В, например, А(х„х;,...,т„,х) и В(хйх„...,хг), 1г < и. !'огда значения формул А и В на наборе аоат,,,.,а„,п буду~ равны А(аиа„,..,а„,а) = а, В(аиат,,аг)=Е. рассмотрим значения формул при различных в подстановках: )(х,)=х, х,( =а,, ) (А)=А(х,,х„...,.т„,В), А(х,,хт,...,х„,В!1 = А(анпа,...,а„, В(она„...,аг)) = А(аоот,,а„,В) = а, Если А — тавтологи», то у1(а,,ат,,а„,п)= А(аиат,...,аыр)= — 1, в т.с. сели А(х,,х,...,хя,х)=1,»о ((А)=А(хнхт,,»,„В)= — 1.
Честь ! Метзмзгич сю линке Пусть А и А-ь  — тождественно истинные формулы. Тогда из свойств импликации при любом наборе анас,,..,а„,п ! — !В =1. Отсюда В м!. Следовательно, любая выеолимзе формула тождественна истинна. Теорема 2.5 Глеорема о емеодниосшн). Пусть А — некоторая формула нсчнслеив» высказываний; х„х,...,х„— набор всех переменных, входящих в формулу А; пипз,...,п„— произвольный фиксированный набор значений этих переменных.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
