Математическая логика. Шапорев С.Д (1019113), страница 24
Текст из файла (страница 24)
)лаяв 3. Пс ика и ща оя 3.6. Предваренная нормальная форма. Общезначимость и выполнимость формул логики предикатов Формула логики преликатов имеет вормальлую фоуыг. если она солержиз только операции коныонкции, Лизъюнкцни и «вацторныс операции, а операци» отрицания отнесена к зясмен ~ арным формулам Использу» равносильности алгебры высказываний и логики предикатав, ка- ждую формулу логики прсдикатав можно привести к нормальной форме. Теореггп 3 !. Для любой формулы существует равносильна» сй вормальнан форма, причем мпежества свобадвых н связанных переменных зтнх формул совпадают.
Среди нормальных форм особое значение имеют предвареиные (или преиексные) нормалыгые формы. Предеоуеллой лоршмьяой )бормои формулы логики прсдикетоя называется такая нормальная фар ча, в которой либо оалнгютыо отсутствук г кллнторныс операции, либо они используются после всех операций алгебры логики. Эта форма имеет внд (ох,)(цхз) .(ох„)Л(хихг,,хв) и <щ, ~лс под символом ох, понимается один из кванторов )Гх или Ьг„ а формула Л кванзоров не содержит. Если все и, )жены Ю, то эта форма называется >У-формулой !или универсальной г))орл~логг). если жс все о, равны Е, то такая форма называется Э- формулой, Если существуя~ !(0 <г < и), таксе. что цоо„...,о, суть и, а о„„...,а„суть зу, то такая форма называется скулсмоесьой вориольиод форлюй (или БЧ-форм>лей). теорема 3.2 Всякая формула «вгики предикатов может быть приведена к раввосвльиай ей предваренной нормвлыюй бюрме.
Обратим аз>~пан>ге только на некоторые особенности доказатещства, имсгошие пращ нческое значение. Гели формула имеет аид Л, то с помощью равносильностей гхч(л) и ИтЛ(х) и ЕтА(х)и зухЛ(х) отрицание вводится пол знак кванторов. Если формула имеет ыгд А, и Л, илн Л, л Лз, тогда послсловательнооть действий может быть такова Снапща переименовываются ' щ|еьс т рыщ) с у аа Г|язт-~звзз — к в '. «а ° и Част 1 Матмагтмсиал логи«в в Аг связанные предметнме переменные так, чтобы в гЧ и А, все связанные переменные били различим.
Получаем г( = (ах,1(а х,)..(а х„)г,(~,х„...,х,) т<л, А, = (о у, )(а у, ) ..(а уг)г, (у„у„...,у, ), р < и. Палее воспользуемся равносильноатями С л ЧхВ(х) и Чх(С л В(х)), Сч 'ьгхВ(х) и зУх(С а В(х)), С л жгВ(х) и ах(Сл В(х)) н Сайхй(х)мйх(СаВ(х)). Псрсггишеьг, например, формулу А, ч ~ сле- дующим образом: А,-А,=(-,)(-,) (-ьЮ,(, „, в)-(.у,Х.у,) ...(а ур)пг(у~ уг ...у„))= (ах,)(а ха)..(ахи)(а у| Ха уг)..(а уа). (а, (хпхг,...,хь)а пг (умуг -'у„)).
т, Р < и. Формула А логики прсдикатои называется вмлолнииой в области М тв данной интерпретации), сали существуют значения переменнмх, входящик в му формулу из области М, при «оторых формула А принимает истинные значения. Формула А называется выполнимой, если существует область, на которой эта формула выполнима. Формула А называетси гполсдесагввггло «ститюй е области М, если она принимает иатинные значения двя вснк значений переменных нз М, втол»- щнх в зту формулу. Формула А называется гттвзггачилгай, если она тождественно истинна на всякой области. Общсзначичую формулу называют логическим законам.
Фармува А общезначима тогда и только тогда, «огда формула А не является выполнимой, и формула А выполнима тогда н только тогда, «агав формула А не «вляегся общезначимой. Очевидно, что если Г и 6 — равносильные в логике предикатов формулы, то Р вч Π— общезначимая формула. Твореии 3.3. Формула ЗУхд(х)-+А(у), где переменная у пс входит в формулу А(х), общезначима. Доказательство.
Пусть хпхг,..,,х„— все свободные переменнмс формулм А(х), тогда у, хп хз.. х„— перечень свободных переменных формулы гУхА(х) — ь А(у). Рассмотрим произвольную интерпретацию с мновгеством М. Пустг, Вмеа 3. Логика о яеюе гб! Ь,а„аы...,а„ЬП М, и, б М, г =1,Я вЂ” пРоизвольный набоР значений свободных переменпьш доказываемой формулы. Пока»кем, что Чхд(х) — » А(у)„, =1.
Для формулы А(х) либо существует ае П М такой, что А(х) = О либодля любого адМ !атом числе и для а=Ь! А(х! = !. В пер- вом случае если А(х) = О, то ВлА(х) = О и тогда (О-»!и1, »Ухд(х) — » А(у) = 1, т. к. для импликании ~ Во второ»» »и, (Π— » О = 1. случае»УхА(х! = 1, А(у) =1, тогда ВхА(х)-» А(у)м1, т, к. 1 †» ! и 1.
Теорема у.б Формула А(у)-+Вхд(х), где переменная у ие входит в формулу А(х), общезначима. Докщкем Эту теорему, опираясь иа предыдущую. Иь»ссм ВхА(х)-» А6) и 1 Тогда 1ГхАГх)-» АЯи»УхАГх)ч А(!») и и ЗхА(х)»» А(у) и "хЛ(х)ч А(у) и АЯч 3~А(х) Л(у)-» Вхд(х) и1.
Следователь»го, форт»ула А(у) — » Зхд(х) общезначима. Теорема 5,5. Пусть А — тмкдествеиио истинная формула алгебры высказываний, х,,х„. „х, — список ее переменных. Подставив вместо шнкдой перемеиноп х, формулу логики преднкатов В, так, чтобы прэ Этом ие иарушалнсь пункты определения формулы логики преднкатов, получим ебщезивчнмую формулу логики преднкатов. Доказательство равносильиостей формул логики прсдикеюв требует либо летального рассмотрения значений формул, либо использования известных равиосильностей. Пример 1. Доказать ЗУхА(х) — ЗхА(т).
Этот пример легко решается. Всспользуемщ первой формулой из списка равносильных формул логики преднкатое БЛ!т)н еВхд(х) Вели от нес взят отрипанис, получим искомый результат ~тУ»(т) и»Утд(х) Вхд(х) гб2 Часа Г. Маг мвгнчынвялмина Пример 2. Пусть А(х) и В(х) два одноместных преликата, опреде- ленных на множестве М и таких, что высказывание Зг(А(х) — «(АГх)ч 'ур(х)-~ А(х))))и 1, доказать, что высказывание Ухд(х) н О .
Упростим исходное высказывание. Зз~ А(х) — !(А Гх) ч ( В (х) — «А(х)ф — = Зх(А(х) е (А(х) ч ЦВк~ч чА~хт ))) н и Зх А(х) — «(А(х)ч(Втх)л А(х)) — = =;г(А(х) — «А(х))и Зх(А хх)ч А(х))и и Зхд(х) и — Ухд(х) н — 1, Тогда чада(х) — и «Ухд(х) и О. Пример 3.
Привести к предваренной нормальной форме следующие формулы логики предикатов: 1. В и рр-еЗхй(х) р-еЗхВВ(х)м рчЗхй(х)и рлЗхй(х)н рлУхй(х)м «Ух(рл Кх)) ййб 72Ж2к ь«ДД ЖТЭЗе мЖй «йк ч(АЯ-«А(х)))мЗх«!1~(А(х ччАА((уу)))ч ~у~чА(х) иЗхУу(А(х)а л А(у)чА(у)лА(х)) Для опрелеления общезначимости формулы логики предикатов иногда бываег достаточно равносильных преобразований. Чаще всего этого недостаточно.
Поэтому связь между общезначимостью и выполнимостью устанавливают теоремами. !йорелл Дб Длн тоге чтобы формула А была общезначима, необходимо и лоствтачно, чтобы ее отрицание была не выполнима. (Певыпслнимость означает, что формула тождественно ложна на всякой области.) Доказиме тьстеа. 1. Деобходиьгость. Пусть формула А общезначима. Тогда А — тождест- венно ложна» формула иа всякой области и, следовательно, не выполнима. Глеев 3. Легляа и едиклгов (бз 2.
Достаточность. Пусть Л не выполнима иа всякой области М 3 огда она там тождественно ложна по опрелелению невыполнимой формулы. Следовательно, А — тождественно истинная формула в любой области М, т е, она общезначима Теорема 3 9.
Длп того чтобы формула А были выполппмой, необходимо н достаточно, чтобы формула Л была необщезначнмой. Доказательство этой теоремы очень просто н аналогично доказательству теоремы 3.6. Поясним смысл последней теоремы. Выполнимость формулы Л означает. что ддя этой форчулы существуют две обласщ М н М, при мм в одной из них, нанрнмер, М, она истинна, а в другой М вЂ” лозкна. Задача распознавания обшсзпачилзости фарьгул логики предикпов существенно сложнее, чем формул алгебры высказываний.
Она также назыгзае~ся проблемой разрешимости, но решается гораздо трулнее. 6(етпд перебора всех варизнтов а общем случае здесь нс применим, т. 55. вариантов чоагст быть бесконечно много. В 1936 г, американский математик А. Черн доказал, пп в общем виде проблема разрешимости ло5ики предикатов нс имеет алгоритмического решения. теорел5а 38 (егеорена Угр о 3 не существует алгоритма, который длв любой формулы логики преднкатов устанавливает, общезначнм» оиа нлн пег. Задача распознавания общсзначнлгости может быть решена в некоторых ча- стных случаях Случай конечных областей Например, если в формулаз логики преднкатов рассматривать толька одном»- стные предикатпые символы, то такой алгоритм сущее гяуст Логика, в которой употрсблязстся только одномссгные прсднкаты. соответствует логике, описанной еще Аристотслеьз. Здесь кващорль5е операции можно заненизь опсрапиями «апъкшкпии и дизъюньнин н тем самым свести формулу логики предикатов к формуле алгебры логики, лля которой проблема рюрешимости мелют бкпь решена.
Алгоритм проверки общезначимости формул, содержащих только одноместные предика гныс символы, ос ною н па еледу5ашей теореме. Теорема 3.9 Пусзь Л вЂ” формула, содержал(ая ровно л одноместных преднкатвых символов. Длн того чтобы формула Л была выполнимой, необкоднмо н достаточно, чтобы она был» выполнима во всех изгтергзретапних (М, Т)смнежеством М,саде(жшщнмне бе.ме 2" элементов. Л 9 ( 9 ((903-(995( — «р . Яьннч Часы !. Мвгемзгн юсавя ложж Пример 4. является ли приведенная формула общезначимоб? Ы(*) я1*!! !ж(*! з(*)).щь!дт,!О ! я!с)г лЗх1;(х))ютУхЦРх ч Рз ххт)гЗтЗу(Р(х)д Р(у))юЗу(чх(Р(х)ч Рз !х~)ч ч Зх(Р (х) л Р (У))) и ЗУ(уз ~РЯ ч Рз Гх) ч Зх(Р (х) л Р (т))) ю ю ЗуЧзЗх((Р,(х) л Рз(у))ч ЦР, х ч Рзгх )!! исходная формула приведена к предварениоб нормальной форме. получено высказывание, т.
к. все переменные связаны кванторамн. Проанализируем его на истинность. Пусть Р(х)мР(х) ю! (для 1гхн М или Зги М). Тогда (Р(х)лрз(у)чРГг)чрз(т))ю((1л1)ч(бчб))и(!ЧО)ю1, Пусть, наоборот, Р(т)ю Р,(т)иб (ддя ухи М нлн Зхи М). Тогда (Олб)ч(!ч1)юбч1ю1 Наконец, Р(х)юО, !з(х)ю! (для дгхн М илн Зха М). тогда (1дО) ч(бч1)мбч1ю1. Итац нско- ма» формула общезначима. Проблема разрешимости для формул, содержащих а предааренной нормальной форме каанторы одного типа Если формула логики предикатов А содержит свободные переменные хнхз,...,х„, то формула В = !Ух,тх ...Чх„А(х„х„...х„) называется заныкжж м обе!лосем формулы А, ~1жрмулз С = Зх~Зхз..ЗхеА(хмхз, х„) называется зжгмкспксж сжг1еплеоеаггнл формулы А .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
