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