В.Н. Нефедов, В.А. Осипова - Курс дискретной математики (1127083), страница 14
Текст из файла (страница 14)
Утверждение !.0.1- АщА для любой формулы Я. 11астранм вывод формулы А ~лг (!) (А з ((А зЛ) щА)) щ ((Аю (Лщд)) з (ЛщА)) (пслстановка в схему аксиом Л2 формулы Ащд вместо В и формулы А вместо С)! (2) Ащ ((А~А) «А) (подстановка в схему аксиом Л( (юрмулы Л щ А вместо В)! (3) (Я щ (А ~ А) ) ~ (А ~ Л] (из (!) и (2) оо ж. р.); (4) А ~ (А ю А) (подстановка в скему аксиом Л( формулы А вместо В); (3) Л щА (из (3) и (4) па ю. р.). Утверждение 1.!О. Если Г 1- А и  — побоя формула, то Г(- Вщй Пусть Аз,..., А„— вывод формулы А иэ Г, где А совпадает с Я. Тогда последовательность Аь. °, Л, А щ (В ~А), Вюл — вывод формулы ВщА па Г.
В математических рассуждениях часто нанос-то утвержденна В доказывают в прслпаложении всрносчи неногорого ару гого утверждения А, после чепз ваилючают, что верно упюрждсние чесли А, то В . В нсчиспеняи высказываний этот прием обосновывается следующей теоремой. '-жщ сэ Теорема 1.11 (о дедукции). Пусть à — миожесгео формул, ' А и 3 — формулы и Г, А 1 — В. Тогда Г 1 — А ю В. Пусть Вь..., В„ (1.3) есть вывод формулы В яз Г н А. Доказательство проведем нн. дукш~ей по л — длине вывола (1.3).
Прн л 1 формула В совпадает с Вь Согласно определению вывода возможны трн случая: 1) В, — аксиома; 2) В, — формула из множества Г; 3) В~ совпадает с А. В первых двух случаях нмеем Г ]- Вь Тогда согласно ут. всржденню 1.10 Г]- А шВь т. е, Г ! — А юВ. В третьем случае формула А~В имеет внд Аюд. Согласно утверждению 1.9 ]- А юА, откуда Г 1 в Л ю А. Допустим теперь, что есл» длина вывода формулы В нз Г, А меныве л, то утверждение теоремы верно. Докажем его лля случая, когда пляпа вывода (1.3) равна л.Прн этом возможно, что: !) „— эконома; 2) „— формула нз Г; 3) В„совпадает с А; 4) В„получена по ш.
р. нз Вг н Вь где ! < л, ] < л. В первых трех случаях доказательство проводится так же, как прк л 1. В четвертом случае либо формула В!имеет внд В,юВ, либо формула В; имеет взд Втю В . Ограничимся рассмотреннем случая, когда Вг нмеет внд В~ю В . Отбрасывая последние л †! формулы нэ (1.3]. получаем вывод В; нз Г н А, а отбрасывая последние л †) формулы нэ (1.3), — вывод Вт, нэ Г н А; длины этих выводов меньше л. По кядуктявному пРедположению 1) Г 1-А ~В4 '2] Г]-Л (ВЪВ.]. По схеме аксиом 32 имеем 3) Г! — [Аз (ВююВ„)) ю ((Аюйг) ш(А юВ )). рнменяя свойство Ч] к (2) в (3], получаем (4) Г 1- (Л юВг) ю (А~В ].
Применяя свойство Ч! к (1] н (4), получаем Г] — АюВ . Теорема доказана. Следггеие ! (пролило силлогизме)г АюВ, ВюС]-А юС. Построим вывод; (1) Аюй — гипотеза; (2) В ю С вЂ” гипотеза; (3) А — гнпотеза; еа (4)  — црямеяясм правила гн. р. к (1) н (3); (3) С вЂ” прнменяец правило ш. р. к (2) н (4). Тогда А~В. ВшС, А 1-С. По теореме о делукцнц А:»В, В С) А С.' Следствие 2: Аш (ВшС), Вг-АшС. В результате лнухратного цркмснення нраацза ш р.
лолу. часн А, А:» (ВюС), В! — С. Отсюда цо теореме о дедукццц ,1ю(ВшС), Б)-г!шС Для любык форм)л А н Н в нсчнслсцкн эысказываг!нй верны слелуюцгне утвержденна (нрнведсч нх без доказатсзьшв), Утверждение !.1!. ! — ! )А'юЛ. утоержденне 1.12. 1 — Л ш А! -! Л. Утвержленне !13. (--!Л ш (А ш В). Утверждение 1.14. ' (7Вш -)А) ш (А.» В). Утверждение 1ЛЗ.
) — (ЛшН) ш (-)В:»-(А). УтвеРждение 116. 1 — А ~ ( -)В ш -1,'Л:» В) ) . Утвернщенне 137. 1-(ЛшН) ш П-1 ЛшВ) шй). Следстомк Если Г, А)-В н Г, ПА!-В, то Г! — В. По теореме а дедукш!н Г' — А»Н к Г )- -)АшВ Отсюда з силу угвержлення 1.17 Г 1- В. 1.3.3. Полнота я оеяротнэоречквость ьсчксшння высказываний. Неэаанснмость еясаом Пы формализовалц логику выскатыванцй н построялн нсчнсзеацс высьазынаннй «ах эксцоматнчсгкую тсорню По эжен. тго множество теоРем нсчнстсння высказыегннй соева аст с яковы твоы тождественно-нствннык ф рчут логння вы«казывшшй.
Покажем сначала следующее уз верйзснне. Теорема 1.12. Всякая выводцллз (из лцгтод сцстглм гицотгз) бюрлрза ксчислгки оыскозыо яш! гождестлгяцо-иггишш. Уеносреагтвснвой проверкой убедяцся в том. что аксиомы цсчнсленцн высказываний — тожлсствсеко-нстшшые формулы.
В галу свойств нмцаянациц форм)аа, нолучаюцгаяся нз толзсстпсяно-нстнцных форчул цо нравнлу т р., томдесгвсняа-кс. ткана. Следовательно, любая выводимая формула тагклсствецно.встннна. Покажем теперь обратное теореме 1.!2 утзсржл цне тоц, что .цобая тождественно-нстянная форм)ла аыеолгма а исчясзенян аыскззываннй, т. с. является теоремой. Скмволы Кй н А' имеют здесь тот же счысл. ч о и о разя. 13П г К„еслн з = 1;, / А, если а 1; -!Х, если е О; ! -!Л. если е О. Вместо снмвола И уяотрсбляем сямвол 1, выес о снмшша П вЂ” снмшш О.
Пусть Хь.... Х вЂ” все церемонные бюрмулы А н хакане яе"вторая оценка списка переменных (еь.... а >, состоящая' э аз нз нулей н елнннц. Через А(в,..., е ) будем обозначать звачеппе формулы А на этой оценке. Пример !.24. Пусть формула А имеет впл (Х ю Хз)ю з -Тх» где Х, н Хз — переменные. Тогда Лч, — зто -)Х„ Х',— зто Хг. фоРн!ла А' — это А, фоРмУла Лз — зто -1 ((«~~хе)ю -1 «,). Рассмотрим все четыре возможные оценки, саотаетстнуюшпе различным распределениям нстпннасгвых значепнй переменных: <О, 0>, <О, 1>, <1, 0>, <1, ! >.
В нашем случае А(0, 0) !. А(0, 1) = 1, А(1, О) 1, А(1, 1) = О. Лемма 1.7. Пуси А — произвольная фарпрла, Х» ..., Х— все ягпепеппме, цтадяп(пе в А (длл рдобспю мы обоз ачилп пк так, как если бы окп была перэыпп лереаеппыпи). и пусть также задала проиюолзная оценка списка перепеппмх <.с,..., е >. Тепдо Л О,..., Л „)-А; где е — зпачгнис формулы А па Оценке <в,.... е >. Прнмер !.25.
Пусть Л вЂ” формула, рассмотренаая в примее!.24. тогда нз леммы 1.7 следуют вмнолнмастн Х» 1«з1- (Х> Х) -)Х, Х,Х ! — -1 ((«1ю«г) ю !Л)). Докажем лемму 1.7. Пол длиной формулы А будем понимать чнсло вхожденпй логических символов в А Доказательство проведен нпдукпней по й — длине формулы А.
Прн й 0 формула А представляет собой переменную Х» н утвержденнс леммы сводят я к Х, (-Х» Пусть для формул, длина которых меньше й, утверждение леммы спрзвеллпео. Докажем ега лла формул данны Д Воз. мцкны два случея. Случай !. Формула А имеет впд -1 В. Длина формулы В равна й — 1, множества переменных формул В совпадает с мно. жсством переменных формулы А. Пусть В(в., е ) ец Тсз да з= )а'. Если с' О, то з = 1. По ннлуктнвному предположению 'Л Ц,..., Л "„1-ВЦ Но Вз — это П В плн в данном глучае ЛЦ Следовательяа, Х'ь..., Х „! — Ац Еслн е' 1, та в=О.
По индуктивному предпаложенвю Согласно утверждению!.!2 и правилу ю. р. Л"ь..., Л", У. П-1 В. Но -! !  — это н есть А". Следовательно, Х'ь.,., Л"„)-А. Случал 2. Формуле А имеет внд Вю С. Длина формул вв ц С меньше Д. Пусть значение формулы В на оценке <зь ° а„> равно е'.
значение формулы С на оценке <ю,..., е > равно е". Тогда с е' ш ек Если е'=О, то е 1. По индуктивному предположению Хиь..., Л ", 1-В", т, е. Л „..., Л.„)--)В. Согласна упверждению !АЗ '; П В ш (В ш С). Применяя иравило ю, р., получаем Х" »..., Х'" „1 — В ш С.
Следовательно, Пусть теперь е' 1, е О. Тогда е=б и А' — зто 1(Вш ш С). По индуктивному предположению Х', , Лч „! — В, ХЦЬ ..., Л "„1- -!С. Согласно утвсржвеиию 1.1О г-Вш()Сш ~(ВшС)). В рсаультзтс двукратного применения правила лт. р. получаем Х ь..., Лы„ 1- †,(В ш С). Если е' 1, е" = 1, то е 1 и А' — зто В ш С. По инду»- тивиому прглположсиию Хн» ., К' „)- С. По схеме аксиом А! имеем ы Сш (ВшС). Приз~сияя пра- вило т. р„получаем Х*ь „Л"„1- Вшс. Теорема 1.13. Если формула А исчисленил высклзмеонпб яехаеггя тпндестеенкс-штикиоб, то она еьиюдинл. Пусть А — тождественно-истинная формула, а Хь ..., К— есе ее переменные. Тогда в силу леммы !.7 нв любек оцснне <и...., е >, состояшея из нулея н единиц, получаем Хь .Л", А, Псзтому в случае, когда е 1, имеем а в случае, когда е О, имеем Приманю следствие уптерждения 1.1У, получаем Точно так же, рассматривая случаи, когда е , принимает значения 1 и О, получаем н т.
д. Наианеп, приходим к 1- А. Из теорем 1.12 н 1.13 непосредственно вытекает следующее утверждение. Теорема 1Л4. Формула А исчисления гмгкпзыаоиил омао- дина тогда и только тогда, когда оиа гождестагино-петиных Свойство аксиоматнческой тсорнн, заключающееся в том, что если формула Л выражает логический закон (как, напри-, мер, тождественно-истинная формула), то она выводима в этой теории, называется полнотой аксиоматнческой теории (нлн пол- нотой в широком смысле).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
