Дискретная математика (998286), страница 20
Текст из файла (страница 20)
Объединим зти выводы и достроим следующий вывод: (А -+ (Е. -~ Е»)) -+ ЯА -+ Е*) -+ (А -~ Е»)) Аг'(Е'/В,Е»/С1 и+ 1. (А — » Е;) -~ (А --+ Е») МР;У, и и+2. А -» Е» МР;т, и+ 1 Таким образом, Г Рс А -+ Ем для любого )г, в частности, для й = и. Но Е„= В, го есть Г )-с А -+ В. Обратно. Имеем вывод Г )-с А -+ В, состоящий из п формул. Достроим его следующим образом.
и. А-+В и + 1. А гипотеза и+2. В МР; и+1, и ТТЗ 4.3. Исчисление высказываний Таким образом, имеем Г,А Рс В, ЗАМЕЧАНИЕ Схема аксиом Аэ теории С не использовалась в доказательстве, поэтому теорема дедукции имеет место для более широкого класса теорий, чем Х, СЛЕДСТВИЕ 1 Дели А 1-с В, то ~-с А -+ В и обратно, Доказательство Г:=я СЛЕДСТВИЕ 2 А-ь В,В-+ С~-с А -ь С. Докдзатвль ство гипотеза гипотеза по теореме, дедукции. ЗАМЕЧАНИЕ Это производное правило назывется правилом транзитиенссти, СЛЕДСТВИЕ 3 А -ь ( — > С), В Рс А — ь С.
Докдздткпьот во гипотеза гипотеза МР,'2,1 гипотеза МР; 4, 3 1 — 5 по теореме дедукции. ЗАМЕЧАНИЕ Это производное правило наэывется лраеилсм сечения. 1. А-+ В 2. В-+С 3. А 4. В 5. С 6. А -+ В, В -+ С, А ~-с С 7 А-+В В-+С14А-+С 1. А -+ (В -+ С) 2. А 3. В-+С 4. В 5. С 6. А -~ ( — ь С), В, А 1-с С 7 А -+ (В -+ С), В ) с А -+ С гипотеза МР;3,1 МР;4,2 1-5 Глава 4. Логические исчисления 114 4.3.7. Некоторые теоремы теории х. Множество теорем теории х, бесконечно.
Здесь приведены некоторые теоремы, которые используются в дальнейших построениях. ЗАМЕЧАНИЕ Каждая доказанная теорема (то есть формула теории, для которой построен выньд) может использоваться в дальнейших выводах иа правах аксиомы. ТЕОРЕМА В теории х.
выводимы следующие теоремы. )кй Утверждение 1. ( А — + А) -+((-А-+ -А) -+А) 2. - А -+ - А 3. (-А-+ А) -+ А 4. А -+ (-А -+ А) 5. А-+А Обоснование Аз; ( А/В1 а; ( А/А) МР; 2, 1 Аы ( - А/В) Сл. 2; ( -А/В,А/А, А/С) а) 1с А-~А б) 1-с А-+ А в) (-с А-+(А-+В) г) )-с (- В -+ - А) -+ (А -+ В) д) г в (А -+ В) -+ (- В -+ -'А) е) Ра А-+ (-В-+-(А-+ В)) ж) Рс (А -ь В) -к((- А -+ В) -+ В) Доказательство Доказательство теоремы а: Рс А -+ А.
Доказательство теоремы б: Рс А -+ А. )че Утверждение 1. ( - А-+ А)-+ — к (( — А-+А) -+ А) 2. А-+ А 3. ( - А-+А)-+ А 4, А-+( - А — +А) 5. А-+ А Обоснование Аз, '(А/В, А/А) первая теорема 4.3.5; (- А/А) Сл. 3; 1 А -+ А/А, А -+. А/В,А/С) Аы( . А/А, ° А/В) Сл.2; ( . А/А,. А-+ А/В;А/С) 4.3. Исчисление выскввываний Доказательство теоремы в: 1-с - А — к (А -+ В). Доказательство теоремы г: «-с — В -+,4) -+ (А -+ В), Доказательство теоремы д: 1-с (А -+ В) -+ (- В -~ А) 1, 3. 6.
7. 8. 9. 10. 11. 12. 3. 4. 5. 6. 8. 9. 10. 1. 2. 3. 4. 5. 6. 7. 8. 9. Утверждение -А А А-+( В-+А) А-+( В-к А) — В -+ А В-+ А (-В+ А)-+(( В~А)-+В) (- В -+ А) -+ В В - А, А 'с-с В -Ас-с А — к В 1с ' А-+ (А-+ В) Утверждение -В-+ — А А ( В -е А) -~ Я- В -к А) -к В) А -+ ( В -в А) (- В -+ А) -+ В А-+ В В - В -+ А, А 1-с В - — к -А ~с А-+ В ~-с ( В -+ - А) -+ (А -+ В) Утверждение А -+ В А-+ А А — кВ В-+ В - - А -к -~-~В А-+ В)-+(-В-+ А) -В-к А А — +В1 с -' — +.
А (4 — В)- ( В- А) Обоснование гипотеза гипотеза Аг,(. В/В~ А~,( А/А,-В/В1 МР; 2, 3 МР; 1,4 Аз МР;6,7 МР;5,8 1 — 9 теорема дедукции теорема дедукции Обоснование гипотеза гипотеза Аз Аг,( В/В1 МР; 1,3 Сл.,2; (-В -+ А/В,В/С': МР; 2, 6 1-7 теорема дедукции теорема дедукции Обоснование гнпотеза Сл. 2; (А/В, А/А,А/С~ б; (В/Ат Сл. 2; ( А/А, В/С) г; ( А/В,- В/А) МР; 5,6 1 — 7 теорема дедукции 116 Глава 4.
Логические исчисления Доказательство теоремы его-с А -е ( В -+ (А -+ В)) М Утверждение Обоснование 1. А гипотеза 2. А-+В гипотеза 3. В МР; 1, 2 4. А,А-+ Вис В 1 — 3 5. А~ с (А-+В) — +В теорема дедукции 6. Рс А-+((А-+ В) -+В) теорема дедукции 7 1-с ((А — ~ В) + В) -+ д; (А-+ В/А) -+ (- В -+ -(А -+ В)) 8. Рс А-+( В-+ (А — к В)) Сл.
2; (((А-+В) -+В)/В, (  — + - (А -+ В))/С) Доказательство теоремы ж: Рс (А -+ В) -+ ((- А -+ В) -+ В). ле Утверждение Обоснование 1. А-+В гипотеза 2. -А — +В гипотеза 3. (" -е В) -+ (-В-+ А) д 4. В + А МР; 1, 3 5. ( А-'+В)-+( В-» А) д; ( А/А) 6. В~ А МР; 2, 5 7.
( В -+ А) -+ (( В -+ А) -+ Аз'( А/А) В) 8. (-В-+ А) -+В МР;6,7 9. В МР;4,8 10. А-+В, А-+Врг, В 1 — 9 11. А-+Врс( А-+В)-+В теорема дедукции 12. 1-с (А -+ В) — к (( А -+ В) -+ В) теорема дедукции 4.3.8. Множество теорем теории С Пусть формула А содержит переменные ам..., а„, и пусть задана некоторая интерпретация 7 формулы А, то есть приписаны истинностные значения переменным ам...,а„. Обозначим ио,=И, А, 7(А)=И к 1-ао еслиа,=Л ' А, еслиХ(А)=Л в данной интерпретации ЛЕММА А'г, А'„1-с А'. )4оклзлткльство Индукция по структуре формулы А, 117 $.3.
Исчисление высказываний 1. Переменная. Пусть А=и. Тогда арг,аи амс а. 2. Отрицание. Пусть А = - В. в Пусть 1(В) = И. Тогда 1(А) = Л и А' = ~А = В. По индукционному предположению А'„...,А'„1-с В. Но Рг.  — г В по теореме 4.3,7, б, следовательно, А'ы..., А'„1-с В = А'.
м Пусть 1(В) = Л. Тогда 1(А) = И и А' = А = .В. По индукционному предположению А'ы...,А'„1-с В = А'. 3. Импликация. Пусть А = (В -+ С). По индукционному предположению А'ы °, А'л Р с В' и А'ы А'л Рг, С'. м Пусть 1(В) = Л. Тогда, независимо от значения 1(С), имеем: 1(А) = И и В' = В, А' = А. Но А'ы..., А'„1-с В, Рс - В ч (В + С) по теореме 4.3.7, в, следовательно, А'ы " ., А' Рс В + С = А' м Пусть 1(В) = И и 1(С) = И.Тогда1(А) =И и С'=С,А'=А=В-+С. Имеем: А'ы..., А'„1-с С, 1-с С -+ (В -+ С) (аксиома Аг с подстановкой (С1А)), следовательно, А'„..., А'„1-с  — > С = А'. м Пусть1(В) = Ии1(С) =Л.ТогдаА'= А= (В-+С),В'= ВиС'=-С. Имеем: А'И...,А'„~- В, А'И...,А'„)- С, 1-с В + ( С -+ (В ч С)) по теореме 4.3.7, е. Следовательно, А'ы..., А'„1-с — (В -+ С) = А'.
П ТЕОРЕМА Теоремами теории 1 являются общезначимые формулы и только они: 1-с А с=в А — тавтология. ДОКАЗАТЕЛЬСТВО Пусть А — тавтология. Тогда А'И...,А'„~- А в любой интерпретации. Таким образом, имеется 2" различных выводимостей А'И...,А'„~- А. Среди них есть две, которые различаются в А'„: А'И...,А'„ы о 1- А и А'и...,А'„ы а„1- А. По теореме дедукции А'м...,А'„, 1-с а„-+ А и А'ы ...,А'„ г Р и„ -+ А, но 1-с (а„ -+ А) -+ (( а -+ А) -+ А) по теореме 4.3.7(й), следовательно, А'ы..., А'„г Р А.
Повторив этот процесс егце н — 1 раз, имеем Рс А. = Аксиомы Ам Аз, Аз суть тавтологии. МР сохраняет тавтологичность, следовательно, теоремы теории к, суть тавтологии. П СЛЕДСТВИЕ Теория г", формально непротиворечива. ДОКАЗАтвльстВ О Все теоремы к. суть тавтологии. Отрицание тавтологии не есть тавтология. Следовательно, в г" нет теоремы и ее отрицания. П 118 Глава 4. Логические исчисления 4.3.9. Другие аксиоматизации исчисления высказываний 1.
Гильберт и Аккерман, 1938. Связки: (А -+ В: = - А ч В). Аксиомы: АчА-+ А, А-+ АнВ, А ~/ В -+ В н А, (В -+ С) -+ (А н В -+ А ч' С). Мос1нв ропепв. Правило: 2. Россер, 1953. Связки: Аксиомы: й,, (А -+ В;= (Ай В)), А -+ АйА, АйВ-+ А, (А — + В) -+ (-(ВЙС) — + (СйА)) Моды ропепв. Правило: 3. Клини, 1952. Связки: Аксиомы: -,й,~г,-+. А -+ (В -+ А), (А -+ (В -+ С)) -+ ((А -+ В) -+,(А -+ С)), Ай — к А, АйВ-~ В, А -+ (В -к (Ай В)), А -+(АНВ), В -+ (АнВ), (А -+ С) -'+ ((В -+ С) — + ((А ч В) -+ С)), (А-+ В) -+ ((А-+. В) -+ -А), А -+ А.
Модна ропепв. Правило: 4. Никол, 1917. Связка: Аксиома: (А)В:= А~/ В). (А ( (В ( С)) ( ((Ю ! (В ( В)) ( ( ((Е ! В) ( ((А ( Е) ! (А ! Е)))), А,А((В(С) С Правило: 4.4. Исчисление предикатов Описание формальной теории исчисления предикатов в этом разделе носит конспективный характер, в частности, многие технически сложные доказательства Теория к, не является единственной возможной аксиоматизацией исчисления высказываний. Ее основное достоинство — лаконичность при сохранении апре- деленной наглядности.
Действительно, в теории С всего две связки, три схемы аксиом и одно правило. Известны и многие другие аксиоматизации исчисления высказываний, предложенные различными авторами. 119 4.4. Исчисление првдиквтов 4.4.1. Определения (Чистое) исчисление предикатов (первого порядка) — это формальная теория Х, в которой определены следующие компоненты. 1.
Алфавит: связки основные дополнительные Й Ы служебные символы кванта ры ( ) Ы всеобщности существования а,Ь,...,аыЬИ... х,у,...,хыуы... Р,тд,... Лу,". константы переменные предикаты функторы предметные предметные С каждым предикатом и функтором связано некоторое натуральное число, которое называется арностью, или местностью, 2. Формулы имеют следующий синтаксис: (формула) (атом) ! (формула)~ ((формула) -+ (формула)) ~ Ы (переменная) (формула) ~ Л (переменная) (формула) (предикат) ((список термов) ) (терм) ! (терм), (список термов) (константа) ! (переменная)/ (функтор) ((список термов) ) (атом) (список терман) (терм) При этом должны быть выполнены следующие контекстные условия: в терме г'(сы °,т„) функтор ~ должен быть и-местным.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
