В.Н. Нефедов, В.А. Осипова - Курс дискретной математики (1127083), страница 18
Текст из файла (страница 18)
Тогда д, э,,..., «г, — перечень сеободпык переменных формулы (1.!1). Рассмогрнм пранзаольнуга ннтерпрстанвм с множеством М. Пусть <Ь, аь..., а >, где Ьжи, а~жМ(!(!<л) — про- нзасльный набор значыжй снесенных «еременных формулы (1.! 1). Докажем, юо (Чк)л(к) ~А(р))<д ж И. Дсйстввтельва, для формулы А (х) лнбс существуег элемент атыМ такой, что ва наборе <пь аь ..., е„> значеннй сзсбод- ВМХ НЕРЕМЕНЛЫХ К, Хг,,..., М„ А(к))< „о„>=Л, либо для любсга элемента аелМ н» наборе <а, пь,.., а ) ЗпаЧЕлнй СпобОЛВЫХ ЛЕРЕЧЕНПЫХ Х. Хч,..., Х л(х)(<д ... „> -и. В первом случае (Чх)Л(к)( „, > — Л, н тогда (Чх)А(к) ~А(р)(<ь е,,„> - И. Во втором случае (Чх)Л(к)( „, > — — И; А(р)(<э, =И, н тогда (Чх)Л(х).
Л(р)(<, „„> =И. Утвсрхгаенве 1.18, Формула А(у) ~ (Ях)лаях), где лерелеляол р лг ежздот е Формулу А(х). обигеэлочила. В сплу утвержденна 1,18 формула (Чх) "! А(л) — ! (А) 1г Сбжсэнзчпма. Имеем (чх)-)А(х) ~-)л(р) .)(чх)-)А(х) Ч л(р) е' еэ пп(Ях) -1-1А(х) ]/ ]А(У) (Ях)Л(х]Н-ТА(У)=— А(у) ю (Ях)А(х). Слеаовательно, формула А(у) ю (йх)Л(х) общезначима. Как говорьвось выше, адноимеаные квантары можно перестаапятм следовательно, формулы (Ях)(Яд)А(х, д)-(Яу)(Ях)А(х, д), (ух)(уд)А(х, у) (уу)(ух)А(х, у) абшезначимы. Общезначимай является также формула (Як) (уу)Л (х. д) щ щ(уу)(йх)А(х.
д) (доказательство будет прявелено в конце равд 144). Одвакафорыула (ух)(яу)А(хд)ю(яд)(ух)А(х д], не является общсзначимой. Действительно. пусть формула А(х, у) — атомарнаи формула А'И,(т, у). Рассмотрим иитсрпрстааню; областью которой является ыножестпо целых чисел; символу Агпз псегавин в соответствие прсдикат х<у. Тогта формула (ух) (яд)А'п,(к, д] истинне в зтш1 «нтерпрсташш, а формула (Яд)(Ъх]Агп,(х, д) ложна. Утверждение 1.20 Пусть А — ыпсдестеенно.истиннал формула логики еыскозыеаний, Х,,..., Х, — с исая ее переменныт. Падщаеие инесса каждой персменйой ХЧ.
й 1, ' ..., и, формулы логики прсднкагое В» (так, чтобы «ри этом не нардиюлнсь лп. 1 — 4 определения формулы. см. с. 74Л получим общезначниую формулу левики преди«атал. Задача распознавания общезначимости формул загпкн предикатов существенна сложнее, чем формул логики высказыва. ний. Так же, «аи и в логике выспазываний.
оиз называется проблемой разрешимости и тавится слелуюшим образом: указать эффективный способ (алгоритм) распознавании общезначимости формул (т. е. является ли даннаи форнула сбщезначнмой или нет). (Полробно понятие алгоритма будет обсуж-, даться в равд. 1В.) В общем случае вга вроблсма в логике презпкатсз неразрешима. Прнвелем это утверждение без доказательства. Теорема Чертю Ве сдшестеует ангар тма, который длл лнг бой формулы ловки предикотое устанаелиеает, обвгезначима она или нет. Однако в нскстарык чэстиых случаях проблема разрешимости решастс».
Например, если рассматривать формулы логика предякатаж сохсржаатие только одноместные предвкзтные син«опы, та такой алгоритм существует. Лопзка, в которой уаа. трсбляются только одноместные прсдикатм, юагветствует логи-, ке, которая была описана еще Аристотелем. Алгоритм проверки сбщсзначимсстц формул, содержзщик' только сднонсстные предикатные симеоны, основав на следующем утверждении. Не Утеернщение 1.21. Лушь Š— Уюунуэа, ссдержощол роангэ д адяоиесюиэх лреди атных си.иналов. Длл пмо чтобы фор»уха Р была выио.гнилой, неабходи»о и догтпюч о, чтобм оиа была выполни»оа ео егск интерпретациях <М, /> с»наиегтео» М, содгржощич ие более 2" злг»ен ов. Праведен схему доказательства этого утвержденна. Пусть в интерпретациях 11,=<Ми / > п Мэ <Мь / > одночастным прелпкатнмн символам А!'1г формулы поставлены в соответствие прслнкаты Р, и Цэ 1=1, 2, Говорят, что интерпретация М, н Мт юиомарфнй, сели существует сюръскиня угМ Мэтакая,чта лин любого ишМ, и дл» любого /=1, 2, Рг(и) Ща(а)).
Тогда, эак следует нз нндуктищюгоапреиеления, формула, содержащая только одноместные предикатиыс символы, в гамомарфаых нитервретэиних одновременна либо вмпаливма, либо непыпапинма. Покажем, что гели формула Е, содержащая ровна и одиочсстных прехнкатпых символов Агиь.. ° Аа' . выполнима, го опа выполнима и в некоторой пптерпретагши с «овечнмм множеством М, соэержашнм ие более 2" элементов. Пусть М,= = <Мь /~> — пнтерпретаии», в которой «ыполпнма формула Е, а пусть в пгдй щперпретаиин прсдинатным симеонам Аа!г ахи нетствуют предикэты Рг, 1 = 1, К..., и. Для лгабого а ш М, рассмотри» полиножссгэа М,ММь состоящее из таких элементов Ь, что <. Р,(а), Р (а), ..., Р (а) > =< Р [Ь), Р (Ь), ..., Р (Ь)>.
Числа такик подмножеств М пе «ревышает числа наборов нз И и Л длины л, т. е. нс превышает 2". Выберем в «ажлои иэ этик па«множеств ио одночу иредставнтеюо и составим нз них множество М. Тогдэ нвтерпрстаиии М,= у <Мь В> н Иэ=-<М, />, где / — ограниченно фуикиин /г на МшМь гаиоморфны, н, слелаватеиьно, формула Е выпал° има я интерпрстэипм И, с мнажесгпом М, содержащим не более 2" элементов. Отсюда следует утверждсзиге !.21. 1.4А.
Исчисление «редикат в Ках было сказано выше, в лтагике прсхпкато», в отжщие от логик» высказываний, иет эффективною способа для расиознаваеия общезначимости фарп!л. Ппэтаму аксиоматичесипй метал становится существенным при изучении формул, салержаШнх кваитары. Выделение обшезначимых формул так же, кан и в ~гсчггсленин высказываний, ссущесгпляетс» путе» указания некоторой говокупнасти формул, нагорно называются аксиомах'н. н указан»» праввл вывода, позволяющих из общезначимых ФОРмул получать общезначимые. В отличие от общепринятога из.тоження, рассмотрим некотоРрю узкую аисноматнческу!о теорию, которую танжс будем наэыпатЫсчислснзгем преднквтов.
Исчисление прсаикатов — зто аксноматичсская теория, самзоламн которой явлюогся, гю существу, тс же символы, что н в готике прелакатов (см. разл. 1.4.1); !) символы прелмегиык переменных: хь хь - , х,...; 2) символы пРеднкатовг А'пь Аогг,..., АШ„,... (1 = О, 1, "): 3) вогичесиис символы: 4) символы кнанторо»гчф ВП 5) скобки н занятая: (, ). Счрормулггрованное в равд.
!А.! определение формулы оста.ется в силе и для мсчнслсжгя лредикагов (с той лишь разнипей, что мы употребляем только ава логических символа: ! и ю; остальные связки можно ввести, например, тан, как зто сделано в исчислении высказываний, см. с. 04). Аксиолм исчисления предикагок Каковы бы ня были формулы Л и В, сведующие формулы «вляююя аксиомамн '. А!. А ш (Вш Л); А2. (А ш (В ю С)) ю ((А ш В) ю (А ш С) ) ! АЗ. -)Вш.3А) ю ((-1 ВюА) юВ); Аф.
(ух)А(х) юд(хг), где формула А(хг) не содержит :псрсменвой хг; йб. Я(х<)ю(Чхг)Я(хг), гДе фоРмУла А(хг) не содеРжит псуе:менпой х(. Правило выводи исчислении прсдикогое *: 1. Правнла ш. р: Длшл Вшл(х.) 2. Правило связмвання нвантаром общностнг В (т'з)А( ) тдс формула В не содержит переменной х» 3. Правило связывания квавтором «ущесюовання: где формула В не содержит переменкой хс Аы.) эВ (Нх,)А(. ) В 4. Правило переименования связанной переменной. Свнзаннюо переменную формулы А можно заменить (в кванторс и во и"-ег вхождеимяк в обласпг действа» квантора) другой переменной, не являющейся свободной в А.
Понятия нывола, теоремы, вывода из системы гипотез опре.леляются в исчислении предикатов так же, ка» п в любой аксиоматической теории (см. равд. 1.3.1). Теорема 1.20 (ослабленная теорема о дедукции). Если Г, .А' — В и существует вывод в исчислении предикптов, построенный с применением только привили 1, то Г !†АшВ. Эта теорема доказывается аналогично теореме о дедукпии а исчислении высназынаннй. Прн зтои нежипкю нзрумзтыз опрсдьмнзз форнузи. вб Можно показать, что класс всех теорем исчисления иредикатов совпадает с классом общщначнмых формул.
Утверждение 1.22. Аксиомы исчисления лредикатое — оби(езяочгыгеы формулы. Дтя аксиом А! — АЗ это следует нз утверждения !.20, дл» аксиом А4 и Аб — из утверждений 1.18 и 1.19. Утверыденме !.ал. Формула, волучающаясл из общезиачимой фора~увы оо любому иэ правил вывода 1 — 4, явлщтея общезиачи.юб. Ддя правила вывода ! это утверждение следует из свай та нипликаяни. Рассмотрим правило вывода 2. Пусть В щА(к,) — абщсзначимая формула. Докажем, что формуаа В> (Ух.)А(х,) тоже общезначима.
Пусть хар, ха — все свободные переменные этой формулы. Тогда «г, к», °..., ха„— перечеиь свсбоднык переменных формулы В> А(х;) (формула В пс содержит переменной х ). Пусть задана произвольная пнюрпретвщ~я с множеством М и пусть <аь ..., а >, а;щМ, 1<!<л,— произвольный набор значений свободнмх перемеинык формулы Вщ (Ух)А(х~). Возмоищы два случая: !) В) <, „> И; 2) В)<а, а„> — -Л. В первом случае из общезначимости формулы В щ А (х~) следует, что для любого элемента а из множества Л! А (яг) ),„„„> — — И.
Тогда (ух,)А(х;) ) < — И откуда В> (Ух,)А(х,)(<„и > И. Во втором случае в силу свойства импликапии Вщ (Ухг)А(х,)( в, И. Рассмотрим правило выпада 3. Пусть А(х~) щ — общезиачиман формула. Донажеи, что формула (Ях.)А(х,) щ В тоже общезначима. Пусть к ..., х, — все сеободиыс посс. иен|гыс этой формулы.
Тогда хь хьо ..., хз — персчсиь свободных перемеинык формулы А(к,) щВ (фориула В не содержат переменной хД. Пусть задана произвовьная «итериретапия с множеством М в пусть <аь ..., о„>, а~щМ, !<г<л,— произвольный набораначевий свободных переменных формулы (Ях~)А(х,) юВ. Возможны даа случая: !) В(<м в„. = И; 2)В(., =Л, В первом случае в силу свойств имолнкащш (Яхг)А(х,) ю В(, > —— И. Во втором случае «з общезначимости формулы А(к,) >В слелуст, что для любого элемента а пз ииожестве М зт .А(х,)(< „, я >- — Л. Тогда (Бх,)Л(к,)1 <аь .а > =Д.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
