Гильберт, Бернайс - Основания математики. Логические исчисления и формализация арифметики (947375), страница 19
Текст из файла (страница 19)
и могут быть выражены через &, ')/ н 1. 4. Правила устранения и введения импликации н эквивалент- ности: а) Я вЂ” »3 заменимо посредством 1Я )/ 3. б) Я 3 заменимо посредством (Я&В) 1/(?Я & ) 3) [гл. Тн ТЕОРИЯ ИСТИННОСТНЫХ ФУНКЦИИ исчисление Высказыэаннп 81 3. Примеры заменимости.
Приведем несколько примеров применения этих правит. Согласно правилу 4а), Я вЂ” 111 замеппмо посредством 1 2[ '1/ 3. Возьмем в качестве Я переменную А. а в качестве РΠ— выражение  — +- С. Тогда получится, что А -~- ( — ь С) заменимо посредством 1 А [/(Л -с- С). В последнем выражении можно [по правилу 4а) и В2] ') В с.
С заменять посредством 1В 1/С, так что в результате преобразования выражения Л -ь ( — С) мы получим и. вследствие ассоцпатпвностп днзъюнкцнп [правнло ]б)1, ~ А ~/ ~В 1/С. Мы можем здесь выделить 1Л 1/ 1В н вместо него [правило 26)1 подставить 1 (Л дс В).
Тогда мы получим 1(Лси В) 1/ С, э вместо этого можно [правило 4а)] написать (А сйВ) — ~- С. Значит, и это последнее выражение тоже заменимо посредством А -э- (В -ь- С). Далее, так как А А В заменимо посредством В А А [правило 16)1, то отсюда следует, что А — ь (Л -+- С) заменимо посредствам Л вЂ” ~ (А — ~ С). Рассмотрим теперь выражение, получающееся в результате другой расстановки скобок: (Л вЂ” В) -~ С; если здесь исключить [по правилу 4а)] обе импликации, то получится выражение 1 (1 Л 1/ Л) 1/ С. В нем 1 (1 А 1/Л) можно заменить посредством 1 1АА 1В 1правило 26)1 и, далее, посредством Лосс [В [правило 2а)]. так что получится (АА. 1В)ЧС; С) Прннснснис правила подстаноави 82 а лальпсьвисп и всегда бум т оговариваться янно. вместо этого выражения по дистрибутивному закону [правило (в)1 можно написать (А )/ С) д (-1 Л [/ С), н, значит, выражение (Л -+- В) — ~ С заменимо этим выражением.
Тем же самьсм преобразованием мы пз (А -+. В) -ь В получим выражение (А 1/ В) дс ("1В 1/В) в, вследствие коммутатнвности дизъюнкции 1правило 46)1,— (А 1/ В) д, (В 1/ 1В). Здесь, по правилу сокращения За), можно отбросить второй коньюнктивный член, так что в результате преобразования выражения (Л -ь- В) -э- В получится А 1/В. Таким образом, мы установили, что диаъюнкция может быть выражена череа одну только имнликацию.
Рассмотрим отрицание импликации: 1 (А -~- В). Отсюда мы сначала получаем [по правилу 4а)1 -[(-1А 1/ В), а затем [по правилу 26)1 1 [АЙ 1В, и так как 1 [А заменимо посредством А [правило 2а)],то в итоге получается Лсч ~В. Теперь заметим, что А -ь- В заменимо посредством Ч 1 (А -ь В) 1правило 2а)1, а следовательно, н посредством 1(АА 1В) Зто дает пам представление импликации через конъюнкцию и отрицание. Зквивалентность А Л мы с самого начала представили следусощими двумя способами: (Л дс В) )/ ( 1Л А- 1В) (А — ь. В) А (В -+. А). Отсюда на основании коммутативности конъюнкции [правило [6)1 можно заключить о заменимости Л Л посредством Л А. Возьмем отрицание вьсражения (Л -+.
Л) й (Л-с-А). Тогда [по прави- 8 Ч. 1'ипьас1с и. Гсриаас ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИИ АНГЛ, 11! ТЕОРИЯ ИСТИННОСТПЫХ ФУНКЦИЙ лу 2б)) у нас получится 1(А — р- В) р/ 1(В-«-А). Как только что было установлено, здесь можно заменить 1 (А -р В) посредством А др 1 В, а 1 (В-+. Л) посредством Вдс 1А, так что в целом получится (А «х 1В) 1/ (В «ч 1А). Это составное высказывание представляет собой разделительное «или». В самом деле, оно истинно тогда и только тогда, когда один из аргументов А, В принимает значение «истина», а второй— «ложь». Очевидно, что эта истннпостная функция, подобно конъюнкции, дизъюнкции и эквивалентности, симметрична относительно АиВ. Так как ВА 1А заменимо также посредством ~ АА ~ ~ В (вследствие коммутативности конъюнкции [правило 1б)) и по цравилу 2а)), то мы получаем, что разделительное «или» мо»кет быть представлено также и в виде (А й 1В) ~/ ( 1А А. 1 1В), а это вырап1ение в свою очередь на основапии представления (А д«В) )/ ( 1А А.
1 В) для эквивалентности можно заменить посредством А 1В. Тем самым мы установили, что отрицание эквивалентности заменимо посредством разделительного «или», а также посредством А 1В, а потому (на основании симметричности эквивалентности) оно заменимо и посредством 1А В. Таким образом, первое и четвертое из следующих четырех вырая«ений: А В, А 1В, 1А В, 1А 1В представляют собой эквивалентность, а второе и третье — разделительное «или». 4. Двойственность; конъюнктивная и диэъюнктивная нормальиые формы; тождественно истинные выражения; распознающая процедура. Так теория истинностных функций ведет нас к некоему исчислению высказываний.
Чтобы составить себе систематическое представление об этом исчислении, мы рассмотрим ряд общих вопросов, касающихся правил замены. Прежде всего бросается в глаза, что в правилах 1 — 3 коныонкция и дизъюнкция фигурируют совершенно симметричным образом, так что система этих правил не изменится, если др и 1/ всюду поменять местами. Выраженная в этом факте «двойственность» объясняется тем, что конъюнкция и дизъюнкция как истинностные функции находятся в таком отношении друг к другу, что одна из них получается из другой, если в значениях аргументов и функций «истину» и «ложь» всюду поменять местами.
В атом легко убедиться, сравнив таблицы для др и )/. Для алгебры логики, которая отражает аналогию между исчислением высказываний и алгеброй, получающейся ва базе правил замены 1-й группы, ата двойственность влечет за собой тот факт, что для нас оказывается безразличным вопрос о том, какую именно из связок 86 и )/ следует рассматривать как сумму, а какую— как произведение. В самом деле, здесь, в исчислении высказываний, у иас имеются два закона дистрибутивности. Преобладающая в литературе точка зрения на конъюнкцию как на «логическое произведение», а на дизъюнкцию как на «логическую сумму» соответствует точке зрения объемной (экстенсиональной) логики, в то время как с точки зрения содержательной (интенсиональной) логики естественным является как раз обратное сопоставление.
Значение правил замены заключается про>Еде всего в том, что они дают нам в руки способ, позволяющий приводить любое построенное из рассматриваемых истинностных функций выражение к определенным нормальным формам '). Это делается следующим образом. Прежде всего, правила 4-й группы позволяют нам удалить знаки и-р- '). Затем повторным применением правил 2-й группы мы можем добиться того, чтобы знак отрицания стоял только перед отдельными переменными и чтобы более не встречалось повторяющихся отрицаний. Теперь с помощью правил 1б) и 1в) мы моя<ем убрать скобки, «выполнив умножения» в смысле того или другого яз двух имеющихся у нас законов дистрибутивности. В зависимости от того, какой закон дистрибутивности мы применим — первый или второй,— получится квнъюнктивн я или дизъюнктивная нормальная Форма. Конъюнктивная нормальная форма состоит из конъюнктивно связанных друг с другом простых дизъюпкций, а диаыонктивная — из дизъюнктивно связанных простых конъюнкций, причем под и р о с т о й дизъюнкцией или конъюнкцией мы понимаем такую, члены которой суть либо переменные, либо перемен° р ° «рр .С др* ръ р ) Здесь снова предусматри»ается применение правила 32.
6« В5 тногия истинностных егнкций исчнслкник ВыскАЗывании [гл. гп яли днзъюпкция может оказываться состоящей всего лишь из одного члена. Полученная описанным способом нормальная форма будет представлять ту же самую кстинностную функцию, что и исходное выражение. В качестве примера мы рассмотрим приведение к коныонктивной и дизъюнктивной нормальным формам выражения (А -«- 1В) С.
Применение правил 4-й группы даст (( 1А ~/ 1В) Ь С) ~/ ( 1 ( 1А Ч ~ В) А- и.). Выражение 1 (~А 1~ 1В) А ~С стоящее во вторых скобках, согласно правилу 2б) дает (~~Ад,~~В)А,~С и, по 2а), (Ас«В) б: 1С, так что в целом мы получаем (( 1А ~/ 1В) ЬС) ~/ ((Ай В) А )С). Отсюда, применив первый аакон дистрибутивпости и опустив ненужные скобки, мы получаем выражение (1А ~ тВ ~ А)А(~А ~ 1В 1~ В) й(~А 1~ ~В 1~ ~С)8с (С 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}
