Дискретная математика:
логика, группы, графы, фракталыАкимов О.Е.
1.4. Введение в логику высказываний
Аксиома порядка и ее применение
Мы уже сказали, что доказательство в логике высказываний строится на отношении порядка, которое является более общим случаем отношения эквивалентности. В самом деле, закон симметричности эквивалентности:
если А = В, то В = А,
всегда можно представить в антисимметричной форме:
если А = В, то В = А,
но не наоборот, т.е. из условия антисимметричности отношения порядка:
если А ⇒ В , то В ⇒ А,
вовсе не вытекает условие симметричности:
если А ⇒ В, то В ⇒ А.
А это нужно понимать так, что логика высказываний является расширением логики Буля, так как отношение эквивалентности можно представить двумя отношениями порядка — прямым и обратным, о чём говорилось в предыдущем подразделе. Поэтому все истинные тождества логики Буля автоматически становятся справедливыми клаузами логики высказываний. Например, закон склеивания:
(А ∨ В) ∨ (А ∨ В) = А,
можно представить следующими справедливыми клаузами:
(А ∨ В), (А ∨ В) ⇒ А, А ⇒ (А ∨ В) ∨ (А ∨ В),
1 ⇒ ((А ∨ В) ∨ (А ∨ В)) ~ А, А ∨ В ⇒ (А ∨ В) → А.
Таким образом, независимая система аксиом логики Буля, которая состоит из четырех законов — коммутативности, ассоциативности, дистрибутивности, нуля и единицы — автоматически становится системой аксиом и логики высказываний. Для выражения же отношения порядка, в принципе, требуется лишь какое-то одно элементарное высказывание, к которому можно было бы сводить все остальные более сложные высказывания. Сейчас мы его введем.
Очевидное предложение: «Истину может изречь всякий». На формальном языке логики высказываний эту сентенцию можно представить следующей клаузой:
А ⇒ В → А.
Она означает: «если А истинно, то источником этой истинности может быть что угодно, например, В». Если произвести эквивалентное преобразование этой клаузы
А, В ⇒ А, (1.4)
то семантика ее тоже изменится, и станет примерно такой: «если ранее было установлено, что А истинно, то истинность В не может проявиться так, что А станет ложным» или «истинность одного высказывания (В) не может повлиять на истинность другого высказывания (А)». Путем эквивалентных преобразований клаузу (1.4) всегда можно преобразовать к другим формам:
А ⇒ А ∨ В, А ⇒ А; В, 1 ⇒ (А ∨ В) → А , ...
Однако в качестве основной аксиомы логики высказываний, выражающей отношение порядка, мы возьмем клаузу (1.4).
Теперь на первом нашем примере, который был приведен выше, выясним, как производится доказательство справедливости логической клаузы. Исходная клауза имела вид:
А, А → В ⇒ В. (1.5)
Преобразуем ее к несколько иному виду:
А ∨ (А ∨ В) ⇒ В.
После раскрытия скобок и упрощения сразу же приходим к аксиоме порядка (1.4). Доказанная элементарная клауза (1.5) известна со времен Аристотеля и играет исключительно важную роль в логике высказываний. Она имеет даже специальное латинское название — modus ponens — правило отделения. Если в процессе доказательства справедливости какой-либо сложной клаузы удалось свести ее к клаузе (1.5), будем считать, что доказательство состоялось.
Закон антисимметричности по существу определяет правила действия по переносу объектных высказываний относительно символа метаимпликации « ⇒ ». Что же касается двух других законов отношения порядка, то они, в принципе, сводятся к аксиоме порядка. Так, закон рефлексивности путем использования закона о единице может быть записан как:
А, 1 ⇒ А,
что является частным случаем аксиомы порядка.
Закон транзитивности
А → В, В → С ⇒ А → С,
также можно свести к аксиоме порядка. Доказательство проведем в три этапа:
1) перенесем А влево за знак метаимпликации —
А, А → В, В → С ⇒ С;
2) воспользуемся правилом отделения, которое нами уже доказано, для первых двух посылок —
В, В → С ⇒ С;
не будет ошибкой записать это выражение и так:
В, В, В → С ⇒ С;
3) затем еще раз воспользуемся этим же правилом, что приведет к аксиоме порядка
В, С ⇒ С.
Таким образом, закон транзитивности доказан.
Убедимся в истинности тавтологии:
1 ⇒ (А → (В → С)) → ((А → В) → (А → C)).
Доказательство:
1) произведем эквивалентные преобразования —
А → (В → С), А → В, А ⇒ С;
2) дважды воспользуемся правилом отделения, получим
В → С, В ⇒ С;
3) перед нами modus ponens в чистом виде, который уже был сведен к аксиоме порядка.
Докажем справедливость клаузы, которая построена на основе тождественного закона склеивания:
1 ⇒ (А → В) → ((А → В) → А).
После эквивалентных преобразований:
(А ∨ В) ∨ (А ∨ В) ⇒ А,
выражение сводится к закону рефлексивности, т.е. к частному случаю аксиомы порядка, рассмотренному выше.
Исторически первой системой аксиом классической логики была система, предложенная Г. Фреге (1848 – 1925):
1. 1 ⇒ А → (В → А),
2. 1 ⇒ (А → (В → С)) → ((А → В) → (А → С)),
3. 1 ⇒ (А → (В → С)) → (В → (А → С),
4. 1 ⇒ (А → В) → (В → А),
5. 1 ⇒ А → А , 1 ⇒ А → А.Первая аксиома Фреге является нашей аксиомой порядка. Вторая «аксиома» нами доказана выше. Остальные «аксиомы» представляют собой тождества логики Буля, записанные в форме клауз.
Позднее Я. Лукасевич (1878 – 1956) уменьшил число аксиом в системе Фреге с пяти до трех —
1. 1 ⇒ А → (В → А),
2. 1 ⇒ (А → (В → С)) → ((А → В) → (А → С)),
3. 1 ⇒ (А → В) → (В → А).Вместо третьей «аксиомы» в современной логике часто используют «аксиому» вида:
1 ⇒ (А → В) → ((А → В) → А),
вытекающую из тождественного закона склеивания. Однако системы Фреге и Лукасевича, а также все другие системы аксиом являются избыточными. Для доказательства клауз достаточно одной-единственной аксиомы порядка. Разумеется, без аксиом булевой логики обойтись невозможно, хотя они не были включены в системы Фреге и Лукасевича в явном виде. Таким образом, есть смысл говорить о пяти основополагающих законах логики высказываний: отношения порядка, коммутативности, ассоциативности, дистрибутивности, нуля и единицы.
В заключение этого подраздела вспомним о логическом круге, который возникал у нас в связи с древним объяснением опоры Земли. Тогда мы пришли к логическому соотношению вида:
(X ∨ Y ∨ Z) → (X ∨ Y ∨ Z).
Если перейти на метаязык, то получим клаузу:
X ; Y ; Z ⇒ X, Y, Z.
Двоеточия стоят слева от метаимпликации, а запятые — справа, следовательно, данное выражение противоречит аксиоме порядка. Это говорит об ошибке в объяснении древних. Сказав, что Земля держится на трех китах, киты — на водах океана, а океан — на Земле, древние нарушили естественный порядок вещей — причину обусловили следствием, поэтому математический аппарат логики высказываний сразу же дал сбой. В приведенной клаузе уже нельзя будет переносить посылки через символ метаимпликации, так как выражение
(X ∨ Y ∨ Z) → (X ∨ Y ∨ Z).
не эквивалентно выражению
(X ∨ Y) → (Z ∨ X ∨ Y ∨ Z), или
(X ∨ Y) → (0 ∨ X ∨ Y), (X ∨ Y) → 0
Отсюда вывод: метадизъюнкция « ; » не может разделять две различные посылки, а метаконъюнкция « , » — два различных заключения; это приводит к невозможности использовать аппарат логики высказываний.
|
|
