Человеческое мышление



Элементы логики

1. Высказывание и формулы

Одним из основных понятий логики есть Высказывание - повествовательное предложение, о котором можно утверждать, что оно является или истинным, или ошибочным.

Конечно, в языке существуют предложения, о которых нельзя сказать, истинные они или ошибочные. Например, предложение Это предложение является ошибочным. Если допустить, что оно является истинным, то из него выплывает его ошибочность, а если оно является ошибочным, то имеем, что оно истинно. Следовательно, это предложение нельзя рассматривать как высказывание. В действительности оно является вариантом известного Парадокса лгуна: невозможно сказать, является ли истинной или ошибочной фраза лгуна Я лгу.

Однако наличие таких парадоксальных предложений не будет мешать нам дальше, поскольку математические знания формулируются именно высказываниями.

Ошибочность или истинность высказываний может изменяться, например, во времени Сейчас ночь, в пространстве Мы летим над Африкой и тому подобное. Будем смотреть на высказывание как на переменную, которая может иметь одно из двух значений, - ошибочность или истина, обозначенные 0 и 1 соответственно. Эти значения считаются Противоположными друг к другу.

Определение. Переменная с возможными значениями ошибочность или истина называется Пропозицийною.

Будем помечать пропозицийни переменные большими буквами A, B, C, ., возможно, с индексами. Эти буквы также называются Пропозицийними.

Из высказываний можно получать другие высказывания, связывая их сполучниками и, или, если ., то . и другими. Эти сполучники обозначаются специальными знаками и называются Пропозицийними Связками. Будем означать их.

Определение. Высказывание вида Не A записывается A Й называется Отрицанием Высказывание A. Его значение является противоположным значению A.

Определение. Высказывание вида A но B записывается как A B или A B или A B и называется Конъюнкцией высказываний A и B, или их Логическим произведением. Высказывание A и B называются Сомножителями конъюнкции. Она истинна, когда каждый из сомножителей истинный. Если же хотя бы один из них ошибочный, то и она ошибочна. Ее еще записывают в виде .

Определение. Высказывание вида A или B записывается как A B и называется Дизъюнкцией высказываний A и B, или Логической суммой Слагаемых дизъюнкции. Она истинна, когда хотя бы одно из слагаемых истинный возможно, и оба. Если же оба слагаемого ошибочные, то и она ошибочна. Ее еще записывают в виде .

Определение. Высказывание вида Если A, то B записывается как A B и называется Импликацией из Предпосылкой A и Выводом B. Импликация ошибочна, когда предпосылка истинна, а вывод ошибочен. Во всех иных случаях она истинна. Например, высказывание Если 22=4, то Солнце вращается вокруг Земли за этим определением является ошибочным, а высказывание Если 22=5, то Солнце вращается вокруг Земли - истинным. Импликацию часто помечают знаком: A B.

Заметим, что запись A B читается также, как B есть Необходимым условием для A, или как A есть Достаточным условием для B, или как Из A выплывает B, или как A Только тогда, когда B, или как B Тогда, когда A.

Импликация Из не B выплывает не A, что обозначается B A, называется высказыванием, Противоположным до высказывания A B. Импликация Из B выплывает A, что обозначается B A, называется высказыванием, Обратным до высказывания A B.

Определение. Высказывание вида A тогда и только затем, когда B записывается как A" B и называется Эквивалентностью высказываний A и B. Она истинна, когда значение высказываний A и B совпадают. Если же они разные, то эквивалентность ошибочна. Например, высказывание Если 22=5, то Солнце вращается вокруг Земли является истинным. Эквивалентность часто помечают не знаком ", а знаком .

Заметим, что запись A" B читается также как B есть Необходимым и достаточным условием для A, а также как Если A, то B, и если B, то A. Отрицание эквивалентности A" B читается как Или A, или B. Составленный сполучник или ., или . иногда называется Исключительное или. Подчеркнем, что дизъюнкция A B отличается от отрицания эквивалентности A" B.

Определение. Высказывания записывают в виде Формул по таким правилам:

1 пропозицийна буква является формулой;

2 если X и Y - формулы, то X, X Y, X Y, X Y, X" Y также являются формулами;

3 других формул нет.

По этим правилам, например, A B, A" B A B являются формулами, A B C - нет. Дальше мы рассмотрим согласования, которые позволяют сокращать запись формул. В частности, эти согласования позволяют рассматривать A B C как формулу. Здесь лишь заметим, что можно не записывать внешние скобки формул, например, писать X Y.

2. Таблицы истинности формул и законы

Формула есть Словом, то есть последовательностью символов - имен пропозицийних переменных, знаков связок и скобок. Это слово имеет определенную структуру, ограниченную правилами построения формул. Подслово этого слова, которое является формулой, называется Подформулой. Например, в формуле A" B A B есть подформулы A, B, A" B, A B, A B.

Формула, которая помечает высказывание, составленное из других, более простых, имеет значение, которое зависит от значений этих составных высказываний. Для его вычисления сначала каждой пропозицийний переменной относится в соответствие одно из значений ошибочность или истина 0 или 1. Дальше за определениями пропозицийних связок вычисляется значение подформул, начиная от самых простых и заканчивая всей формулой. Значение формул с одной двухместной связкой при всех возможных наборах значений переменных приведено в таблице:

A B

A B

A B

A B

A " B

0 0

0

1

0 1

1 0

1 1

Вычислим значение формулы, например, A B B A при всех возможных наборах значений переменных A и B. Вычисление подадим такой таблицей:

B A

A B B A

Таблицы, в которых представлена зависимость значений формул от пропозицийних переменных, называются Таблицами истинности.

Рассмотрим согласования, которые позволяют сокращать запись формул. Пропозицийни связки упорядочиваются за Силой тяготение к формулам подобно знакам арифметических операций. Все понимают, что выражение 1+23 помечает сумму 1 и 23, а не произведение 1+2 и 3, то есть знак умножения притягивается сильнее знака добавления. Связка считается сильнейшей, то есть A B является сокращением от A B, а не от A B. Дальше за спадением силы притяжения двухместные связки идут в таком порядке:, . Следовательно, формулу A B C можно рассматривать, как сокращенная запись формулы A B C, а формулу A B C A - как A B C A.

Все двухместные связки имеют свойство Левостороннего связывания. Это значит, что если справа и влево от подформулы записаны без скобок знаки двухместных связок, сила притяжения которых одинакова, то первой к подформуле применяется левая из них. Например, A B C является сокращенной записью формулы A B C.

Определение. Две формулы называются Эквивалентными, или Равносильными, если принимают одинаковые значения при всех возможных значениях пропозицийних переменных. Ривносильнисть формул обозначается знаком и в логике называется Законом.

Например, нетрудно убедиться, что при произвольных формулах A, B, C следующие ривносильности являются законами справа указаны названия некоторых из них:

1 A B B A, A B B A - законы коммутативности

2 A B C A B C, A B C A B C - законы ассоциативности

3 A B C A B A C, A B C A B A C - законы дистрибутивности конъюнкции относительно дизъюнкции и дизъюнкции относительно конъюнкции

4 A A A, A A A - законы идемпотентности

5 A A B A, A A B A

6 A B A B, A B A B - законы Где Моргана

7 A A - закон двойного отрицания

8 A0 0, A1 A, A0 A, A1 1 - законы поглощения

9 A A 1 - закон исключенного третьего

10 A A 0 - закон противоречия

11 A B B A - закон контрапозициї

Полезно также помнить еще два закона:

12 A B A B

13 A" B A B B A.

На законах основываются так называемые Равносильные Превращение формул, когда формула или ее подформула замещается на равносильную ей. В результате получается формула, равносильная начальной. Такие превращения бывают нужные для упрощения формул. Например, формула A A B имеет равносильные формулы A A B, A A B, A A B, A B, что получаются последовательным применением законов 12, 7, 2, 4.

3. Нормальные формы высказываний

Рассмотрим две разновидности формул, которые имеют определены структурные особенности. Именно структура этих формул предопределяет их использование в таких важных отраслях применения математической логики, как автоматизация доведения утверждений и логическое программирование.

Законы 2 утверждают ассоциативность связок конъюнкции. Отсюда формула вида . A1 A2 A3. An имеет эквивалентную запись A1 A2 A3. An. Формула в такой записи называется Конъюнкцией Формул A1, A2, A3, . An.

Определение. Элементарной Конъюнкцией называется конъюнкция формул, каждая из которых является или пропозицийною переменной, или отрицанием такой. Например, A1 A2 A3.

Определение. Дизъюнктивной нормальной формой сокращенно ДНФ называется дизъюнкция элементарных конъюнкций. Например, формула A B B C D. Заметим, что ее структуру лучше видно в записи A B B C D или в записи .

Любая формула может быть преобразована к ДНФ. Мы не будем доводить это утверждение, а лишь опишем нужные равносильные превращения. Применением законов 13 и 12 можно избавиться от связок " и, то есть превратить формулу к равносильной, в которой есть лишь связки, и дальше, если в формуле есть отрицание дизъюнкций или конъюнкций, то они спускаются к пропозицийних переменным применением законов Где Моргана 6. Дальше, если в формуле есть множители-дизъюнкции, то от них можно избавиться применением первого из законов дистрибутивности 3. В результате все множители в конъюнкциях формулы являются элементарными, и она являет собой ДНФ. Применение законов 1, 2, 4, 5, 7-10 может сократить этот процесс.

Пример. Рассмотрим превращение A B" C B. После знаков в скобках указаны номера законов, примененных при дежурном превращении, :

A B" B C 13, 12

A B C B C B A B 6, 7, 2

A B C B B C A B 3

A B B C A B A A B B C B C C A C B

B B C B A B B 1, 4, 9, 8

A B C A C B C B A B 5

A B C A C B

За законами 2 связки дизъюнкции также ассоциативные, откуда формулы . A1 A2 A3 . An и A1 A2 A3. An также является эквивалентными. Последняя из них называется Дизъюнкцией Формул A1, A2, A3, . An.

Определение. Элементарной Дизъюнкцией называется дизъюнкция формул, каждая из которых является или пропозицийною переменной, или отрицанием такой. Например, A1 A2 A3.

Определение. Конъюнктивной нормальной формой сокращенно КНФ называется конъюнкция элементарных дизъюнкций. Например, формула A B B C D, какую можно подать также в виде .

Любая формула превращается к равносильной ей КНФ с использованием тех же законов, только вместо первого из законов дистрибутивности 3 употребляется второй: A B C A B A C.

Пример. Рассмотрим превращение формулы A B" C B после получения формулы A B C B B C A B:

A B C B B C A B 3

A B C A B B B C A B C B 3

A C B C A B B B B A C A

B B C B 9

A C B C A B B A C A C B

4. Тавтология, противоречия и логические выводы

Определение. Формула называется Тотожньо истинной, или Тавтологией, если имеет значение 1 при всех возможных значениях пропозицийних переменных.

Например, A A i ли> A B B A. Нетрудно также убедиться, что заменой знаков на связи " в законах 1-13, приведенных в п. 1.1, получается именно тавтология.

Тавтология характерна тем, что когда все вхождения той же буквы заменить на любое, но одно и то же высказывание, то новое высказывание будет истинным. Например, подставим в тавтологию A B B A вместо буквы A высказывание светит солнце, а вместо буквы B - светят зори. Полученное высказывание Если светит солнце или светят зори, и не светят зори, то светит солнце является истинным. Подчеркнем, что сама по себе структура этого высказывания уже обеспечивает его истинность.

Нетрудно убедиться, что если тавтологией является некоторая формула X и формула X Y, то Y также является тавтологией.

Определение. Формула называется Тотожньо ошибочной, или Противоречием, если имеет значение 0 при всех возможных значениях пропозицийних переменных.

Одним из характерных примеров противоречия есть высказывание A A. Это противоречие используется в доведении утверждений вида A B методом От противоположного. Допускают истинность отрицания A B, то есть истинность A B. Из истинности B выводят A, получая противоречие A A. Она свидетельствует об ошибочности A B, то есть истинность A B.

Заметим, что для доведения истинности A B достаточно из B вывести A, то есть довести истинность противоположного утверждения B A. Ведь по закону контрапозициї 11 A B B A

Очевидно, что отрицание любой тавтологии является противоречием, и наоборот. В отличие от тавтологии, подстановка высказываний в противоречии порождает ошибочные высказывания.

Теперь рассмотрим понятие Логического вывода. В математике, как и в обычной жизни, придется выяснять, выплывает ли некоторое утверждение из одного или нескольких других, то есть есть ли это утверждение их Логическим выводом.

Пример. Допустимо, что покупательная способность денег падает, если растут налоги, и что люди недовольны, когда падает покупательная способность денег. Допустимо также, что налоги растут. Отсюда можно прийти к заключению, что люди недовольны.

Для этого обозначим высказывание буквами :

A - налоги растут,

B - покупательная способность денег падает,

C - люди недовольны.

Предположение примера выразим формулой:

A B B C A.

Доведем, при истинности такого условия истинным будет высказывание C. Превратим A B B C A к ДНФ:

A B B C A A B B C A A A B B C

A A A B B C A B B C

A B B A B C A B C.

Следовательно, имеем, что истинной является формула A B C. Но она истинна лишь тогда, когда каждый сомножитель истинен. Отсюда высказывание C является истинным.

Таким образом, из истинности формул A B, B C и A выплывает истинность C. В таком случае C называется Логическим выводом этих формул.

Определение. Формула Y называется Логическим выводом формул X1, X2, . Xn, если из истинности X1 X2. Xn выплывает истинность формулы Y. Формулы X1, X2, . Xn называются Предпосылками Y.

Проверить, есть ли одна формула логическим выводом других, можно с помощью сравнения таблиц истинности этой формулы и конъюнкции других. Но можно действовать совсем иным способом на основе двух следующих утверждений.

Теорема 1. Формула Y является логическим выводом формул X1, X2, . Xn тогда и только затем, когда формула X1 X2. Xn Y является тавтологией.

Доведение. 1 Необходимость. Допустимо, что формула Y является логическим выводом формул X1, X2, . Xn. Если при некоторых значениях букв в формулах X1, X2, . Xn хотя бы одна из них ошибочная, то за определением импликации X1 X2. Xn Y истинная. Если же при некоторых значениях букв в формулах X1, X2, . Xn все они истинны, X1 X2. Xn также истинная. Но формула Y является логическим выводом формул X1, X2, . Xn, поэтому она также истинная. Тогда истинная и формула X1 X2. Xn Y. Следовательно, при любых значениях букв X1 X2. Xn Y истинная, то есть является тавтологией.

2 Достаточность. Допустимо, что X1 X2. Xn Y является тавтологией. Тогда если при каких-то значениях букв в формулах X1, X2, . Xn все они истинны, то Y также истинная, то есть есть их логическим выводом.

Теорема 2. Формула Y является логическим выводом формул X1, X2, . Xn тогда и только затем, когда формула X1 X2. Xn Y является противоречием.

Доведение. За теоремой 1, формула Y является логическим выводом формул X1, X2, . Xn тогда и только затем, когда формула X1 X2. Xn Y является тавтологией. Отсюда Y является логическим выводом формул X1, X2, . Xn тогда и только затем, когда отрицание X1 X2. Xn Yявляется противоречием. Но

X1 X2. Xn Y X1 X2. Xn Y

X1 X2. Xn Y X1 X2. Xn Y.

Таким образом, утверждение теоремы истинно.

Рассмотрим пример применения приведенных теорем. Докажем, что формула B является логическим выводом формул A B и A. Превратим формулу A B A B:

A B A B A B A B A A B B A B 00 0.

Следовательно, формула A B A B противоречивая, и за теоремой 2 формула B является логическим выводом формул A B и A.

Тот факт, что формула B является логическим выводом формул A B и A, играет в математике очень важную роль. Он позволяет из уже известных истинных утверждений A B и A получить новое истинное утверждение B. Заметим, что такой способ получения, или Выведение новых утверждений в математической логике является одним из основных. Такое выведение задается специальным Правилом выведения, какое имеет вид и название Modus ponens Правило отделения. Оно позволяет получить вывод B утверждение A B как отдельное высказывание, то есть отделить его вид предпосылки A. В математической логике существуют и другие правила выведения, но здесь мы их не рассматриваем.

Подобьем небольшой неформальный итог. Мы познакомились с двумя принципиально разными способами получение новых высказываний. Первый заключается в том, что мы строим сложные высказывания из более простых с помощью логических связок, а также перестраиваем их, выполняя равносильные превращения на основе законов. Описанные способы построения и превращения высказываний складывают основу Алгебры высказываний.

Второй способ получения новых истинных высказываний заключается в применении упомянутых правил выведения к уже известным истинным высказываниям. При этом формулируется система высказываний-тавтологии, которая складывает основу для выведения других. Они называются Аксиомами, а высказывания, которые выводятся, - Теоремами. Примером аксиомы может служить высказывание AA, которое называется законом исключенного третьего. Такой способ порождения высказываний называется Исчислением высказываний.

Подчеркнем еще раз, что в этом разделе нашей целью является лишь знакомство с основными понятиями и языком обозначений логики, потому мы не касаемся ее существенных вопросов. Они раскрываются во многих источниках см. список рекомендованной литературы.

5. Неформальное знакомство с кванторами

В математике, как и в повседневной жизни, возникают утверждения со специфической структурой. Эта структура делает возможными рассуждения, которые нельзя воссоздать выведением высказываний. Классическим примером таких рассуждений является:

Каждый человек смертен.

Сократ - человек.

Отсюда выплывает, что Сократ смертен.

Очевидно, что высказывание Сократ смертный не является логическим выводом предпосылок Каждый человек смертен и Сократ - человек. Однако корректность приведенных рассуждений ни у кого не вызывает сомнения. Очевидно, что она предопределена каким-то особенным содержанием слова каждая.

Введем дополнительные обозначения. Пусть X помечает некоторую переменную, значения которой могут иметь некоторое свойство P. Такие переменные называются Предметными. Высказывание X имеет свойство P обозначим P X. Например, высказывание Целое число X является парным обозначим E X. Значение такого высказывания зависит от значения этой переменной. При X=1 высказывание E X ошибочное, при X=2 - истинное. Вместо буквы X можно записать ее значение, например, E2.

Предложение Каждое значение X имеет свойство P, или Все значения X имеют свойство P, или Все X имеют свойство P, или При всех X исполняется свойство P обозначим записью X P X. В этой записи часть X называется Квантором всеобщности. Слово квантор происходит от слова квантификация, которая означает количественное выражение. Продолжая пример о парных числах, заметим, что утверждение X E X является ошибочным.

Предложение Существует значение X, что имеет свойство P, или Некоторые значения X имеют свойство P, или При некотором значении X исполняется свойство P, или Некоторые X имеют свойство P обозначим записью $ X P X. В этой записи часть $ X называется Квантором существования. Очевидно, что в примере о парных числах утверждения $ X E X является истинным.

Очевидно, что

X P X $ X P X,

Причем утверждение X P X и $ X P X неравносильные.

Рассмотрим некоторые из возможных применений пропозицийних связок к выражениям с кванторами. Отрицание X P X читается как неистинно, что все значения X имеют свойство P, то есть как существует значение X, что не имеет свойства P. Такое предложение можно обозначить как $ X P X. Таким образом,

X P X $ X P X.

Аналогично

$ X P X X P X.

Высказывание X P X X Q X читается как все значения X имеют свойство P и все значения X имеют свойство Q, то есть все значения X имеют свойство P и свойство Q. Таким образом,

X P X X Q X X P X Q X.

Высказывание X P X X Q X читается как все значения X имеют свойство P или все значения X имеют свойство Q. Из этого предложения выплывает, что все значения X имеют свойство P или свойство Q, но эти два предложения не равносильные. Таким образом, X P X Q X является логическим выводом высказывания X P X X Q X, то есть

X P X X Q X X P X Q X,

Но они неравносильны.

Пример. Если P X помечает предложение X - парное число, а Q X - X - нечетное число, то высказывание X P X Q X является истинным, а X P X X Q X - ошибочным.

В конце, рассмотрим предложение с двумя и больше кванторами. Они появляются, когда идет речь о свойствах пар, троек и тому подобное переменных. Например, предложение При любом натуральном значении X существует значение Y, такое, что X является делителем Y можно записать как

X $ Y D X, Y,

Где D X, Y помечает предложение X является делителем Y.

Предложение вида При любом значении X исполняется, что при любом значении Y истинно A X, Y можно обозначить так:

X Y A X, Y.

Будем опускать скобки, записывая, например, X $ Y D X, Y или X Y A X, Y. Последнее выражение можно прочитать также, как При любом значении X и при любом значении Y истинно A X, Y.

Аналогично предложение вида При любом значении X и при любом значении Y и при любом значении Z истинно A X, Y, Z можно обозначить выражением

X Y Z A X, Y, Z.

И так далее. Рассмотрим, например, утверждение большой теоремы Ферма:

Уравнение zn=xn+yn, где n - целое число, больше 2, не имеет решений в целых положительных числах.

Одной из возможных записей этого утверждения есть такой:

X Y Z N N2 Zn Xn+ Yn.