Математическая логика. Шапорев С.Д (1019113), страница 25
Текст из файла (страница 25)
Проблема общщначнмости формул логики преднкатов с предвареннои нормальной формой с кванторами одного типа рещается с помощью следую пих теорем. !сорзмл У!О Если замкнута» формула логики предикатов в предвирениоб нормальноуг ферме содержит только кванторы существовании, число которыя равно и, и тожлепгвеиио истинне в дюбоб области, состоящей из одного элементе, та оив общезиачим».
Доказательсюео. Теорема докщывзется методом оз противного. Пусть формула А в предваренной нормальной форме имеет вид З-формулы, т. е. А = За Зх, ЗтВ(де Ем..., Р,',Рз',...й,',Дз,...), гле  — бесквапторная Глэщ 3 Ломи лр дикагое формула, ~у, — логические переменные, Р, — одноместные предикаты, 1х', — двухместные предикаты и т. д. 2 По условию теоремы иа любой области М = Тз), содерясащей один злсмент, Л щ 1, но тогда будет тождественно истинной и формула В(д,,д„..., Р,'(адР, (а)„,0,'(а,адь1~(а,а)...), эза формула является формулой алгебры логики. Предположим, что фориула А не является обшсзначимой.
Это значит, что существует такая область М, и такой набор значений переменных дз,г1„,Р~(х)Р~(х, Р..,Ы', (хох,)ЬЬ(х„х )..., хох,б М,, на котоРом формула Л принимает значение О, т. е. ЧхЭх Бт В(д" до Р(т)Р'(х ) Д~(х х )Д;(т т ) )=О Тогла ЭхЗхз...ЬеВ д~,д„...,Р~'(х,),Рз ху ..,11 х,,х, (Гз х„х, и'Ух,зхх,.РЕх Вд,,д...Р,'(г)Р,' х ...,ф х„х 11з х,х ... — = 1. Следовательно, формула толсдествеино истинна независимо от выбора предметных переменных из области М,. Выберем одно значение х, б М, и поставим его е послсдгною формулу вместо асса предметных переменных. Тогда В гд,д,,...,рз (хе) Р,(хо )"- 1;1~ (хе,хо)1с, (хо*хе) - = 1.
т.е. В(д,,де,...,1з(хе)Р.'(хе),1Г, (т„,хе) Ц,"(хе,хех...)=0, что противоречит тождественной истинности формулы В(дод„..., Р~ (гг) Рг (о),...,й (о,п) Й (о,гззд,.). Таким образом, предпояожсние, что формула А нс является обшезначимой, неверно. Л вЂ” общезначима» формула. Теорема 3.11 Если замипута» формул» логики предлиатов в предваренной нормальной форме содержит только иваитеры обпзноети, число которых равно л, н тождественно истинне иа всяком множестве, содержащем ле более чеч и элементов, то оиа общезнвчим».
1 ба и а |. Маг магиче яа логике Теорема доказываетс» способом, аналогичным способу, примененному для теоремы 3.10. Пример 5. Доказать тождественную ложность формулы ЗхЕу((Р(х)-е Р(у))л(Р(х)-+ 7(у))лГ(х))аЕтЕу((7(х)ч Р(у))л л (Р(х)ч 7(у))л Р(х))а БхБу(ГР(х) ч Г(у)) л (Р(т)л Р(к)ч 7(у)л лР(х)))аВх~у(ГР(к)ч Р(у))л7(у)л Р(к))а ЕхВу((7(х)л7(у)л л Р~х))ч (Г(у)л Р(у)л Р(х)))м БхЕу(0 ч 0)ай Пример б. Привести я оредваренной норлзю)ьной форме следующую формулу логики преликатов: В а%ха кх1ч Е кб(х, у 1= аяксах) ч Е ля(х у) а 3 х(7(х) ч Ях, у)) Требуемая форма получена.
В данном случае формула содержит только один квантор существования, следовательно, ее всеобщность зависит от вида преднкатов Я(к) и м(к, у). Если Ех!б М, что В = — 1, то онз общезначима. 3.7. Практическое занятие 1)йя8. Выполнимость формул логики предикатоа 3.7.1. Па множестве М определены одноместные предикаты Р(х) и С(л). Каким условиям удовлетворе)от области ик истинности, если истинны: а) )Ук(Г(х)ьб(х))лЛхГР(х)лб(х))) ° ИРТДГМД).
) )'г) )*)) 3.72. Выполнимы ли следующие формулы: а) БхР(х)) б) ЗхЧу(б(х,х) лм(х, у)); в) Зх)Уу(б(х, у) — + )Укя(х, у, з)). 3.7.3. Явллюгс» ли тождественно истинными следующие формулы: а) ЗхР(х) — + )УкР(к)) б) )УхР(х) — ) ЗхР(х)) Глава В. Лсгвю пзмдикзгав зеу в) ДхР(х) о Лх0(х) т-з Дх(Р(х)о фх)); г):-:х чуй(х, у)-ь ЧуЗтШ(х. у); д) Р(х) — з Чур(у); с) Зх(Р(х) я (г — з фх))) -з (6~Р(х) — ь йз(х))-э г). 3 7.4.
Доказать тождественную истинность следующих формул: а) йхР~хх)е МкР(х) б) здх(Р(х) ' Яг)) — з ~ЙРГхГя тУх0Я) )'*('(П с63 РР7 =*с* 3.7.5. Доказать, что если С не содержит свсбодньш вхождений х, то: а) ТхР хх)мтдхРГх) б) тдхр(х)я С и зУх(Р(х)л С). 3.7.б. Привести к предваренной нормальной форме слелуюшис формулы логики преянказов, считая Р и бг бескванторными формулами: Ч Отв 5*.3оы ); б) ЗхУуР(х,у)л3хзУуЦ(х,у); в) Еть7у1 (х,у)о йхдуй(х,у), г) Ьхтуур(х, у)-+ ЗхЗУуС(х, у); о итйврулс Я; е) тУх(Р(х) — з Буй(у)).
3.7.7. Привести к скулемовской нормальной форме; а) 'сх3у('З(х, у) -ь БхзУу0(х, у); б) 3х(Р(х) — з (37уфх, у) -з зУс77(х, х))) 3.7.8. Доказать общезначимость следующих формул: а) тУх(Р(х) — г й(х)) ь (МхР(х) — ь зУх0(х)); б) зух(Р(х) — з фх)) — ь (ЗхР(х) — ь ЛхД(х)); в) зУх(д -ь Р(х)) г-з (д -з'4 тР(х)). 1юя Чаагн Мап иакмеская лапяга 3.7.9. Доказать тождестаеннуго ложность форчулы Бхйу((Р(х) — ь Р(у)) л (Р(х) -ь Р(у)) л Р(х)).
3.7.10. Пусть и = (Рн Р„,, Р„), где Ро Р,,..., Є— одноместные предикатные снмаслы. Доказать, что для любой формулы Л сигнатуры о сущест. куст формула В, экаиааленгная Л, построенная с помощью л, ч и из В -аостааляющнх, т. е. бюрмул вида Вх(В, л В, л... л В„), где з < ! и В, (! < ! <н) имеют аид Р(х) нли Р!хч для некоторою Р иэ и. 3.8. Применение языка логики предикатов для записи математических предложений При переводе словесных выражений а логическую символику надо иметь четкое представление сб интерпретации этой символики. Поэтому необходимо четко очертить множеатко М, содержащее асс аыскюыаания, к которым применяются логические методы и приемы.
Затем надо выбрать перечень предикатоа, коюрые будут служить основными независимыми предикатами, участаующими а формулирояках. Каждый из этих предикатои становится высказыванием, когда а«е его переменные будут злеиентами из множества М, н азы аае мого лредмшплай лба остью. Полностью решить логические проблемы, возникающие а "слоаеснык" язы«ах, можно было бы только переведя асс фразы а символику используемого исчисления, а затем польэоааться только формальным аппараюм этого нсчисяениа.
Кяанторы сочетаются друг с другом н логическими сказками многими способами, поэтому переводы аыражений, содержащих кааиторы, обычно неоднозначны. Однако а некоторых областях знания, а частности математике, этот переаод наиболее еатестаенен. Сач язык логики предикатоа очень удобен дяя записи математических предложений. Ои дает возможность выражать логические акязи между понятиями, записывать определения, теоремы, доизательстаа. Выбор перечня необходимых предикатоа, описыаающих заданные свойства или услоаия, также сравнительно прост.
Рассмотрим несколько примерок. Запись математических определений О Олредеяеггие бсгкоиечио матой бгргхгягги. Функции п(х) назыкаетсл бесконечно леллой при х — > а, если !нпп(х)= О. Зто классическое определе- улвю 3 Л пыл пр дина в лба ние. представляющее, по сути дела, определение предела функции, равного нулю. Перепишем это опрелеление на языке е — Б: бэппа(х)=Ос=гнус> ОЗБ(с).
Олуха М,йгР(х,аб), где Р(хе Б) = (О < (х — а~ ~< Б -+ )а(х) < с) — трехместный прсдикпт, определяющий условия предельного перехода. П Опредллевие зжтпренгулга тгугг диигьгнгзнмума в ночке х„, рис. 3 ВР Зхв е М нУХ~ е М ьгхз е М Р(хо хг ха ) где Р(хо хыхз)= ((х, < те) — з (зн(х )> г(хо)))л ((хз >хе)е(г (хз)> г(хе))) Здесь использован трехместный преднкат Р(хе,хыхз). П Определение еыггуктосгии ~вагггугггости) фуиюзии У(х) Грие. З,РР лг Осли во всех точках интервгща (а,1з) вторая производная л' гх) < О, то у'(х) на (и,Ь) выпукла. Это можно выразить совсем просто с помощью следующего выражения' нУха (а,д)(йу (х)л ф г(х)< 0). Испольюван одноместный предикат Р(х). В, Рис. З.В Рвс З.т П Определение нелгиой фуиюгии. Функция З''(х) называетоя чевюод, если область ее определения симметрична относительно начала координат и вля каждого т из области опрелеяения выполняется равенство Л (т) = Л( — л). Тогда зУх е М((-ха М) л (г'(х) = з ( — х))).
170 Часть 1. Ые ем гичесяаялоп» Формулировка математических теорем Теоремы математики допускают форлгулировки в виде условныя предложений. Говоря о строении многих теорем, можно выделить е них три части: ус.юане теоремы — прсдикат РЫ, заданный на множестве К»; эикъсчщше гяеоремы — предикат ! 1(х), заданный на многкестее я; разълсгггггггельггщг часжь, описывающая множество объектов, о которыя идет речь в теореме. Например, строение теоремы может быть таким: "Ещзи любой элемент х из множества М обладает свойством Р(х), то он обладает свойствон ъс(х) " Таким образом, теорема формулируется так: !Ух ц М(Р(х) — 1 й(х)). Вспомним, например, теорему о конечных приращениях (теорему Лагранжа) Если У(х) непрерывна па [а,Ь] н днффереацнруемв на (а,Ь), то най.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
