Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров (1048837), страница 46
Текст из файла (страница 46)
По- 6 лученную нами выводимость А~ — В-+А вместе с правилом подстановки можно рассматривать как правило 6 Э-~Я 222 «если формула й выводима, то выводима и формула З-« й, где З вЂ” любая формула». Воспользуемся этим правилом в следующем примере. н. А-«В, В-«С) — А-» А-«С. 1, В-«С) — А-«(В-» С) (по новому правилу — ). й З-«6 2. Из А-» (В-»С) и аксиомы П 2 по правилу заключения следует (А — «В)-»- (А«С); следовательно, В- Сь-(А- В)- (А-»-С), 3.
Из (А-»В) и (А-«В)- (А-»С) по правилу заключения следует А — «С; учитывая 2, получаем искомую выводимость. При переходе от 1 к 2 неявно использовалось следующее свойство выводимости; если Г ) — й (à — список формул), а й ) — З, то Г ) — З. Это свойство (гранзитивность отношения выводимости) непосредственно следует из определения выводимости. Основные метатеоремы исчисления высказываний. Для получения выводов в исчислении высказываний оказывается крайне полезной следующая метатеорема. Теорема 6.1 (теорема дедукции). Если Г, й) — В, то Г) — й- В(à — множество формул, й, З вЂ” формулы).
Будем исходить из системы аксиом П и рассматривать их как схемы аксиом (т.е. не пользоваться правилом подстановки). Пусть Г, й) — З. Тогда существует вывод Вь..., З, из Г, й, такой, что В,=З. Докажем по индукции, что для любого й(л Г)- й-»В„ Рассмотрим сначала З,. Зо как первая формула вывода, должна либо быть аксиомой, либо содержаться в Г, либо совпадать с й. Из схемы аксиом П1 следует, что В, — (й - З,) является аксиомой. Если В,— аксиома или содержится в Г, то по правилу заключения й- З> выво.
дима из Г. Если же З, — й, то из примера 6.7,а имеем й- й, т.е.й- З,. В любом случае получаем Г) — й З,. Предполо>ким теперь, что Г) — й- В, для любого с(/г, и рассмотрим Вм Возможны четыре случая: а) З» — аксиома; б) В»енГ; в) З,= й; г) В, выводимо из некоторых предшествующих формул З>н В, по правилу заключения; но тогда З, должно иметь вид Зт- Зы В случаях «а» — «в» доказательство точно такое же, как и для Зт (случаи «а», «б» — с помощью аксиомы П 1! случай «в»вЂ” 223 с помощью примера 6.1, а).
В случае «г» по индуктивному предположению имеем: Г ~- и-+-ит (б. 1) и Г!-и- ззп т. е. Г ~ — и — » Вг-«-и»), (6.2) Подставим в схему аксиом П 2 И~ вместо З и З» вместо ч„Получим: (и — '(зз( — «М)-~((и-~-з~)-~-(и-~аз»)). (6.3) Применив правило заключения к (6.2) и (6.3), получим: Г) — (И вЂ” э-З )-э(И-э-З»), (6.4) а применив то же правило к (6.1) и (6.4), имеем: Г) — И вЂ”:- — Б~. Остается положить й=п. Е) Отметим, что при построении выводов использовались только аксиомы П1 и П2, которые содержатся и в системе аксиом 1. Поэтому приведенное доказательство теоремы дедукции справедливо и для исчисления высказываний, основанного на системе 1. Пример 6.2. а. В качестве первого применения теоремы дедукции покажем, что аксиома НЗ выводима из системы аксиом 1.
1. Подставим в 1 9 1А вместо А. Получим: ( ~А — »В)-+-(( )А-». ~В)«- ') ~А). 2. Двойное применение правила заключения к шагу 1 дает: ~А-»В, 1А-»- ~В)- ) ~А, 3. Так как из аксиомы 110 следует по правилу заключения, что 1 ~Л ) — А, то по транзитивности выводимостн (см. замечание к примеру 6.1, в) получим ~ А-~В; ~Л-+. -» ~В ) А, 4. Переставим гипотезы в полученной выводимости (их порядок неважен, как видно из определения выводимости): ~А-» ~В; )А-»В ) — А. 6. Применив 2 раза к шагу 4 теорему дедукции, получим аксиому П 3: ( ~А-» ~В)-э(( ~А — »В)-~-А). Отметим, что прн доказательстве выводимости системы П из системы 1 были использованы аксиомы системы 1, не содержащие дизъюннции и конъюнкции.
224 б. Очень распространенным методом математических доказательств является метод доказательства от противного: предполагаем, что А верно, и показываем, что, во-первых, из,А выводится В, а во-вторых, что из А выводится !В, что невозможно, и, следовательно, А неверно, т.е. верно ~А. Этот метод формулируется как правило: «если Г, А )-В и Г, А ) — )В, то Г ) — )А». Докажем, что оно в исчислении высказываний выполняется.
Действительно, по теореме дедукции, если Г, А )- В и Г, А ( — )В, то Г )- ) — А-»В и Г) — А-+. ) В. Из этих импликаций и аксиомы 19 двойным применением правила заключения получаем Г )- 1А. Доказанное правило называется также правилом введения отрицания. в. Докажем теперь закон исключенного третьего: ( — А~/ 1А, 1 1(А'/,А), А ) — А'/ ~А (аксиома 16 при В= 1А и правило заключения).
2. ) (А~/ 1А), А ( —;(А'/ )А) (очевидно). 3, Применяя к шагам 1 и 2 только что доказанное пра. вила введения отрицания, получаем: ) (А ~/ 1А) ) — ) А. 4. Аналогично доказывается,(А'/ 1А) )- ) 1А. 5. Применяя к шагам 3 и 4 введение отрицания, получаем: — 1 ~(А~/ ~А). 6. С помощью аксиомы 110 и правила заключения снимаем двойное отрицание в шаге 5 и получаем ~ — А'/ 1А.
Исчисление высказываний и алгебра логики. Формула Р исчисления высказываний содержательно интеопретируется как составное высказывание, истинность которого зависит от истинности входящих в него элементарных высказываний. Эта зависимость в точности соответствует зависимости значения логической функции, представляемой формулой Р, от значений переменных этой функции. Иначе говоря, если задана формула Р(А„...,А») и распределение истинностей входящих в нее элементарных высказываний Аь ..., А„то для выяснения истинности ее нужно вычислить методами, приведенными в гл.
3, как логическую функцию на наборе (ао..., о„), где о.;=1, если А~ истинно, и ш=-"О, если А~ ложно. (В этом смысле можно считать, что набор (оь ..., а ) задает распределение истинностей.) Если Р(оо..., о„) =1, то высказывание Р истинно при дан- ном распределении истинностей Аь..., А„, если Р(оь..., о ) =О, то Р ложно. Возникает вопрос, как связано такое содержательное, «истиппостное» истолкование формул с их выводимостью в исчислении высказываний? Для описания этой связи введем обозначения, аналогичные введенным в 5 3.2 обозначениям вида х'. Пусть для элементарных высказыва иий Аь..., А задано распределение истинностей (ць..., о„).
Обозначим Лч 1 Аь если о, = 1, т. е. если А, истинно; Ас 1Аь если а, = О, т. е. если А; ложно. Теорема 6.2. Пусть формула н (Л,,...,А„) определяет логическую функцию ) от л переменных. Тогда, если 1(оь.., о„)=о, то в исчислении высказываний А;, ..., ао Например, формула ц (Аь Аь Аз) = (А,-+А,)- Аз на наборе (О, 1, О) равна нулю. Тогда теорема утверждает, что ~Ац А„', А, ) — ) ((А,-ьА,)- А,) Доказательство теоремы проводится индукцией по построению формулы (см.
определение формулы). Если ц — буква Аь то утверждение теоремы сводится к А;ь — А, и ) А;! — ~ А;, что тривиально верно. Пусть теорема верна для некоторых формул З и С. Тогда нужно доказать, что она верна для формул а, имеющих вид ) З, З-+-П, Зач, и З'„'6. Перебор всех случаев опускаем; приведем лишь некоторые. Пусть н =--- 1з и при заданном (о;,..., а„) з ложно.
0 а По индуктивному предположению А,..., Л "г- ) З и, следовательно, Л ,..., Л " ~- З, что н требовалось. Пусть ц = З вЂ «- ц и П истинно. Тогда (в силу свойств импликации) н тоже истинно и а' = з. По индуктивному предположению А'О..., А'" ) — С. Но тогда по производному правилу из примера 6.1,б А... А ~ ( — З-~-П, т. е. Л,..., Л„' 1 — ц, что и требовалось. Полный перебор всех случаев для системы аксиом П можно найти в (43). Е Теоремы исчисления высказываний в терминах истинности характеризуется довольно просто. Теорема 6.3.
Всякая теорема исчисления высказываний является тождественно-истинным высказыванием. Тождественная истинность аксиом проверяется либо прямым вычислением на всех наборах, либо приведением их к константе 1 путем тождественных преобразований булевой алгебры, Очевидно, что любая подстановка в тождественно-истинную формулу также даст тождественно-истинную формулу. Остается показать, что правило заключения сохраняет тождественную истинность. Пусть формулы а и а -«З тождественно-истинны, т, е.
м= — 1, ж- а=1. Так как А-+-В— = 1А'»/В, то О~/В— = 1 и Ж= — 1, т. е, формула эЗ, выводимая из я и а —.«эЗ по правилу заключения, также тождественно-истинна. Итак, аксиомы тождественно-истинны, а правила вывода сохраняют тождественную истинность; поэтому любая доказуемая формула тождественно-истинна, ~ '1 Справедлива и обратная теорема. Теорема 6А. Всякая тождественно-истинная формула является теоремой исчисления высказываний. Пусть а (Ан..., А„) — тогкдественно-истинная формула.
Тогда по теореме 6.2 А',~,..., А„'" ) — ц для всех 2" наборов (щ,..., о„). Применив и раз теорему дедукции, получим 2" выводимостей Ь вЂ” А',~-«(А,' -+.(...-+ (А„»-«Ж) ) ...). Подставим в аксиому 18 А вместо В. Получим (А-« — «С)-«(( 'А-+С)-+.((А~/ 1А)«С)). Из этой формулы и правила заключения (учитывая, что А~/ ~А — теорема: см. пример 6.2, в) получаем производное правило: если ) — А — «С и(- ~А С, то ) — С.
Для любого набора (ом..., о„) имеем при о, =1 — А, -(А в -+ (...— (А~"- а)) ...), а при о., = =0~ — ",А,— «(А,'~-«(...— «(А,', -«эл))...). Применяя к этим формулам только что доказанное правило, получаем ) — (А',~-«...-«(А„" — «а) ...), т. е. первая посылка «длинной импликации» удалена. Применяя это удаление еще и — 1 раз, получаем )-Э7. П Таким образом, исчисление высказываний действительно выполняет задачу порождения общелогических законов — тождественно-истинных высказываний. В заключение отметим следующее. Эквивалентные соотношения булевой алгебры соединяют знаком = формулы, которые одновременно равны нулю или единице.
В логике такая равнозначность выражается функцией — (см. 5 3.1); 227 если )г =)г — эквивалентное соотношение, то формула )г -)г является тождественно-истинным высказыванием. В исчислении высказываний формула )г )г является сокращением фоРмУлы (Гг — ~),)гх(1г-+Гг). В силУ теоРемы 6А все такие эквивалентности, например А'~/В-АЬВ, являются теоремами исчисления высказываний. Некоторые общие свойства исчисления высказываний будут рассмотрены в $ 6.3. 62. исчисление пРедикАтОВ и теОРии пеРВОГО ПОРЯДКА Аксиомы и правила вывода. 1. Лл фа в ит исчисления предикатов состоит нз предметных переменных хг, хт..., г г ггредметных констант аг, аг ..., предикатньгх букв Рь Рь ..., Р',...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
