правила логического рассуждения -1 (исчисление высказываний)
Речь пойдёт о правилах логического рассуждения, которые применяются в математике. Я собираюсь описать очень небольшой набор правил, которые всем хорошо известны, и которых достаточно для того, чтобы провести любое логическое рассуждение. Всё далее написанное можно также рассматривать как введение в ряд основных разделов курса математической логики. Мне кажется, что схема, которую я здесь буду излагать, намного проще того, что написано в большинстве учебников. Основных правил очень мало, и их легко запомнить. Этот план я также хочу взять за основу курса лекций по математической логике, который буду читать в текущем семестре.
1. О роли тавтологий. Бытует мнение, что тавтологии (понимаемые как "тождественно истинные" утверждения) -- это что-то заведомо тривиальное. Первые приходящие в голову примеры тавтологий -- это что-то вроде "a=a" или "из A следует A". Однако на самом деле существует много примеров совершенно неочевидных тавтологий. Я хочу начать с аргумента, который считаю очень важным, но на котором крайне редко делают акцент.
Пусть мы доказали некоторую теорему T. Доказали при помощи логических рассуждений, опираясь при этом на некоторые аксиомы. Скажем, это могли быть аксиомы элементарной геометрии, а T -- это теорема Пифагора. В любом рассуждении мы используем только конечное число аксиом. Пусть в нашем рассуждении мы опирались на аксиомы A1, ..., An. Что же мы доказали при помощи своего рассуждения? Мы доказали то, что утверждение T логически следует из наших аксиом. Используя логическую символику, мы можем записать следующее утверждение Ф: A1 & A2 & ... & An -> T, означающее, что из некоторых утверждений логически следует T. Сам этот факт доказывается чисто логически, и при этом совершенно неважно, о чём мы говорим. Нигде не подразумевается, что речь идёт именно о точках и прямых, и при желании можно считать, что речь идёт о каких угодно объектах. Поэтому утверждение Ф будет тавтологией -- оно верно всегда, независимо от того, какой смысл мы придадим используемым в записи формулы символам.
Таким образом, любое содержательное математическое утверждение, то есть любое доказательство чего-либо при помощи аксиом, можно интерпретировать как чисто логическое доказательство некоторой тавтологии. Такая переформулировка ничего не даёт в содержательном отношении, потому что доказать тавтологию ничуть не проще, чем провести исходное рассуждение. Но при этом становится ясной такая вещь: тавтологии, взятые в целом, в некотором смысле содержат в себе все содержательные утверждения о математических объектах. Из этого можно сделать несколько поспешный вывод, что математика сводится к чистой логике. Я думаю, в такой формулировке тезис звучит слишком радикально. О том "творческом" элементе, который никуда не исчезает, я бы хотел поговорить в конце. А пока зададимся естественным вопросом: каких логических средств и приёмов достаточно для того, чтобы провести любое логическое рассуждение? То есть каким "арсеналом" надо обладать, чтобы быть в состоянии доказать логически любую тавтологию?
Ответ оказывается неожиданно простым. Достаточный набор средств намного меньше даже того, что всем известно и привычно по материалу школьного курса. Базисный набор средств, обладающих свойством полноты, то есть достаточный для вывода всех тавтологий, может быть предъявлен многими способами при разных подходах. Сразу же отметим, что ни о каких "силлогизмах Аристотеля" не будет и речи. Этот популярный и часто всплывающий набор приёмов не обладает никакой полнотой; он требует специальных усилий для запоминания. То, что я хочу здесь предложить, не только обладает полнотой, но и запоминается (я хотел бы надеяться!) "в первом чтении" :)
2. Логические задачи. Здесь мы сначала рассмотрим часто встречающуюся ситуацию, когда дан некоторый набор считающихся истинными высказываний, из которых требуется вывести некое следствие. Так часто бывает в логических задачах. Типичный ходовой пример: Известно, что все красные варёные раки мертвы. Также известно, что все варёные мёртвые раки красны. Следует ли отсюда, что все красные мёртвые раки варёны? :)
Ответ в этой задаче отрицателен. Задачу можно сформулировать в символической форме, на языке исчисления высказываний. Пусть имеется некий рак. Обозначим через p, q и r соответственно высказывания о том, что этот рак является красным, мёртвым или варёным. Тогда из условий следует истинность высказываний p & r -> q, q & r -> p. Требуется выяснить, следует ли отсюда логически, что p & q -> r? На языке тавтологий это означает в точности следующее: будет ли тавтологией формула (p & q -> r) & (q & r -> p) -> (p & q -> r)?
Если формула, про которую мы хотим выяснить, является ли она тавтологией, содержит n переменных, то легко понять, что имеется в точности 2^n (два в степени n) разных возможных случаев для этих переменных принимать значения "истина" или "ложь". Тавтологичность формулы означала бы, что она истинна во всех 2^n случаях. При небольших значениях n полный перебор вполне возможен; обычно рисуют так называемые "таблицы истинности". В конкретном примере оказывается, что формула тавтологией не будет: она будет ложной при условии, что p, q истинны, а r ложно. В общем случае, если переменных в задаче имеется, скажем, 100, то при полном переборе надо рассмотреть уже 2^{100} вариантов -- это очень много. Одной из актуальных задач современной математики является вопрос о том, имеется ли принципиально более быстрый способ убедиться в тавтологичности формулы, нежели полный перебор всех вариантов.
Хорошо известна популярная головоломка, связываемая с именем Эйнштейна. В Cети есть очень много вариантов её формулировки. Речь там идёт о пяти людях разных национальностей, живущих в домах разного цвета, пьющий один из пяти напитков, курящих определённый сорт сигарет и разводящих какое-то из домашних животных. При этом даётся ряд условий типа "сосед норвежца пьёт пиво", а в итоге спрашивается что-то типа "кто разводит рыбок?" Чисто теоретически можно было бы ввести большое количество обозначений для высказываний типа "в третьем доме живёт англичанин", "обладатель третьего дома курит "Мальборо"". Каждое из этих условий может быть истинно или ложно, поэтому для него можно завести отдельную логическую переменную (вроде p, q или r выше). Переменных при таком подходе будет очень много, и полный перебор заведомо не является удобоваримым подходом. Я здесь использую этот пример как иллюстрацию на тему того, как могут на практике возникнуть тавтологии сложного вида. Особо хочу оговорить, что целью поста не является обсуждение способов решения конкретных логических задач и головоломок, поэтому я в категорической форме заявляю о том, что этих вещей в комментах затрагивать не следует. Анализируя условие задачи, мы можем записать в символической форму всё, что нам известно напрямую. Кроме того, есть ряд неявно подразумеваемых условий вроде того, что тот, кто пьёт кофе, не пьёт пиво. Символически это будет высказывание типа p -> ¬q. Также должно быть учтено то, что один из сортов сигарет кто-то да курит. Это также может быть сделано на языке символов. В итоге мы выписываем ряд условий, которые нам даны, и наш вопрос может заключаться в том, следует ли из этого логически что-то конкретное типа того, что немец разводит рыбок. Соединяя данные нам условия знаком конъюнкции и беря их импликацию с заключением, мы приходим к формуле вида Ф, рассмотренной выше. Относительно неё мы хотим узнать, будет ли она тавтологией. Если да, то мы хотели бы в этом убедиться не путём полного перебора, а путём логического доказательства (в идеале -- короткого). В самом деле, если мы имеем нечто тавтологичное, верное всегда, то есть некий логический закон (пусть и сложно формулирующийся), то должно же быть какое-то подтверждение этому, основанное на базисных правилах логики?
3. Исчисление высказываний. В свете сказанного выше должна представляться естественной следующая схема. Рассматривается некоторый набор символов для обозначения так называемых высказывательных переменных, каждая из которых может принимать два логических значения -- "истина" и "ложь". (Чаще всего этим значениям сопоставляют для простоты символы T и F или просто 1 и 0.) Из переменных, которые здесь будут обозначаться маленькими латинскими буквами (с индексами или без), можно составлять более сложные выражения -- формулы исчисления высказываний -- при помощи логических связок. Последние таковы: отрицание, которое я здесь обозначаю символом ¬, конъюнкция ("логическое и"), дизъюнкция ("логическое или"), импликация ("логическое следование") и эквиваленция ("тогда и только тогда"). Обозначают перечисленные логические связки зачастую по-разному. Хотя я очень не люблю объяснять разного рода "элементарщину", считаю нужным оговорить две вещи. Одна из них касается смысла дизъюнкции: под "p или q" подразумевается "не исключающее или", то есть высказывание "p или q" истинно, если хотя бы одно из высказываний p, q истинно (соответственно, дизъюнкция ложна, если и только если ложны оба высказывания p, q). Второе замечание касается импликации. Когда мы пишем "p -> q" или говорим "p влечёт q" (тот же смысл имеют выражения "если p, то q", "из p следует q", "при условии p выполняется q" и так далее), то ложность этого высказывания предполагает наличие опровергающего примера. То есть в ситуации, когда p истинно, q может оказаться ложным. Здесь p называется посылкой, а q -- заключением импликации. Таким образом, импликация считается ложной только в одном из случаев -- когда посылка истинна, а заключение ложно. Во всех остальных случаях импликация считается истинной, что часто вызывает некоторое недоумение, но к этому нужно привыкнуть. Если мы знаем, что посылка ложна, то этого достаточно для заключения об истинности импликации. То же самое справедливо, если известно, что истинно заключение.
Итак, дадим определение формулы (исчисления высказываний). Всякая высказывательная переменная считается формулой. Если Ф -- некоторая формула, то (¬Ф) -- также формула. Если * есть одна из оставшихся логических связок, перечисленных выше, то (Ф1 * Ф2) считается формулой для любых формул Ф1, Ф2. Каждая формула строится по этим правилам. В итоге может получиться что-нибудь вроде выражения ((p -> (¬q)) & (r V ((¬p) -> (((q & r) -> p))))). Здесь &, V и -> являются символами для конъюнкции, дизъюнкции и имликации соответственно. Лишние скобки при записи формул далее будут часто опускаться.
Чтобы существенно упростить изложение и уменьшить количество используемых правил, мы берём в наше исчисление только две связки -- отрицание и импликацию. Все остальные связки легко выражаются через выбранные две. Например, "p или q" по смыслу означает то же, что ¬p -> q; "p и q" есть отрицание того факта, что "не-p или не-q", то есть ¬(¬p V ¬q). То же самое можно представить и как ¬(p -> ¬q). Эквиваленция "p равносильно q" выразима в виде (p -> q) & (q -> p).
Таким образом, мы берём за основу связки ¬ и ->, и в формулах используем только их. Заметим, что у нас ранее фигурировала конъюнкция в записи формулы Ф из первого раздела. Здесь нет проблемы, так как вместо A & B & C & D -> E мы можем писать имеющую тот же смысл формулу A -> (B -> (C -> (D -> E))) или, упрощая, A -> B -> C -> D -> E, принимая соглашение, что при наличии одних импликаций скобки расставлены по принципу "справа налево".
Обычно при изложении данного материала приводят список общелогических аксиом и правил вывода. В учебниках могут фигурировать либо списки аксиом, трудных для понимания сходу, либо сложные правила вывода, которые также порой плохо запоминаются (особенно при использовании большого числа связок). Мы решили поступить по-иному. Общелогических аксиом у нас не будет вообще (что может несколько удивить на первый взгляд), а вместо правил вывода я приведу простой список из трёх очень просто формулируемых правил доказательства. Все они очень хорошо известны, и удивить может скорее не их наличие, а остутствие других хорошо известных и часто применяемых правил и приёмов. Но наши три правила будут обладать желаемым свойством полноты: их достаточно для построения любого логического рассуждения в рамках исчисления высказываний. В частности, при помощи этих правил можно вывести все тавтологии (тождественно истинные формулы, то есть формулы, истинные на любом наборе значений переменных), а также можно вывести популярные и полезные правила рассуждения, не вошедшие в список. Ниже идёт список правил, который является одним из основных в данном посте. Далее каждое правило будет прокомментировано.
1) Правило modus ponens, или "правило отсечения"
Пусть считаются доказанными формулы A и (A -> B), где A и B -- некоторые формулы. Тогда разрешается считать доказанной формулу B.
2) Правило "условного рассуждения"
Пусть требуется доказать утверждение вида A -> B. Тогда достаточно принять утверждение A (в качестве предположения) и доказать утверждение B.
3) Правило рассуждения "от противного"
Пусть требуется доказать некоторое утверждение B. Тогда достаточно привести к противоречию утверждение ¬B, то есть отрицание утверждения B.
Вот и весь список. Для краткости далее эти три правила будут сокращённо именоваться MP, Cond и Contr соответственно. Первое сокращение общепринято; два других используются для удобства в контексте данного поста.
Первое правило является классическим и почти не нуждается в комментариях. Понятно, что если установлено положение A, и при этом известно, что A влечёт B, то тем самым B также должно быть верно. Хотя я не ставлю цели анализировать часто встречающиеся логические ошибки (вроде путаницы между прямой и обратной теоремой), хотелось бы обратить внимание на один приём, который высмеивал ещё А.Н.Колмогоров. Имеется в виду использование "правила отсечения" в другую сторону. То есть имеется утверждение B, про которое известно, что оно верно, и имеется импликация A -> B, про которую также известно, что она верна. Ясно, что отсюда никак не следует, что верно A. Более того, можно представить себе ситуацию, когда имеется много установленных фактов B1, B2, ..., Bn, и из гипотетического утверждения A следуют все эти факты, то есть имеют место импликации A -> B1, A -> B2, ..., A -> Bn. При этом говорят, что утверждение A объясняет все наличествующие факты, и на основании этого возникает большой соблазн считать его "верным". При этом часто добавляют, что утверждение A якобы подтверждается фактами. (Это к вопросу о "всеобъясняющих" теориях.) На самом деле, конечно, "объяснить" что-либо можно зачастую очень многими способами. (Особенно просто этого достичь, если использовать какое-либо очень сильное допущение.)
Второе правило очень часто применяется. Мы в любой момент имеем право принять условно любое предположение. В математике часто говорят фразы типа "пусть функция f(x) непрерывна" или "пусть ABCD -- параллелограмм". Ясно, что это делать можно, но при этом всё далее доказанное будет доказано условно, в предположении того, что было принято. Но мы в любой момент можем снять предположение A, из которого мы вывели утверждение B, заключив, что тем самым мы "чисто" доказали импликацию A -> B. Очень многие математические утверждения имеют форму "если ... то ...", поэтому данный приём применяется постоянно: мы принимаем посылку импликации и при этом предположении доказываем заключение.
Здесь стоит также отметить, что в излагаемой версии все общелогические аксиомы мы "растворяем" в простых и понятных правилах, и отпадает необходимость доказывать чисто техническую "теорему дедукции". Это сильно упрощает изложение.
Третье правило хорошо известно и тоже очень часто применяется. Зачастую доказать что-либо удаётся путём приведения к противоречию отрицания нужного утверждения. Под противоречием мы понимаем ситуацию, когда для некоторой формулы A оказываются установленными обе формулы A и ¬A. В этом случае при формальной записи мы будем для удобства писать выражение FALSE -- тождественно ложное высказывание, показывающее, что мы пришли к противоречию. Поэтому третье правило можно будет сформулировать ещё и так: если доказано, что ¬B -> FALSE, то тем самым можно считать B доказанным.
Доказательства будут оформляться подобно программам, с нумерацией формул. При принятии предположений мы будем делать абзацный отступ. На примерах будет хорошо видно, как мы применяем правила и как оформляем рассуждения. Формальное определение доказательства или вывода формул -- задача совершенно рутинная, но я не буду приводить здесь это определение, потому что суть и так раскрыта. Вообще говоря, следует определить понятие "из утверждений A1, ..., An логически следует утверждение B". При этом список утверждений может быть пустым (n=0), и при этом B следует "из ничего", то есть является "логическим законом", тавтологией. Равным образом мы можем говорить о том, что тавтологией будет формула вида A1 -> A2 -> ... -> An -> B с "правонормированной" расстановкой скобок.
В комментариях, служащих приложениями к данному посту, я показываю, как обосновать несколько дополнительных правил рассуждения, каждое из которых также можно использовать. Это закон двойного отрицания, согласно которому ¬¬A можно заменять на A и наоборот; закон контрапозиции, согласно которому от импликации ¬B->¬A можно переходить к импликации A -> B (и наоборот). Особняком стоит такое часто применяемое правило как разбор случаев. Состоит оно в следующем. Допустим, требуется доказать некоторое утверждение B. Мы можем рассмотреть два случая: первый -- когда выполняется некоторое условие A; второй -- когда утверждение A не выполняется, то есть имеет место случай ¬A. В каждом из рассматриваемых случаев мы доказываем утверждение B (вообще говоря, совершенно по-своему). Если это удаётся, то утверждение B можно считать доказанным.
При помощи нескольких вспомогательных утверждений (список которых я также привожу в комментах) можно доказать следующий важный факт.
Теорема о полноте исчисления высказываний. Всякую тавтологию, то есть тождественно истинную формулу исчисления высказываний, можно доказать при помощи использования правил 1, 2, 3.
Нелишне добавить, что всякая доказуемая при помощи данных правил формула обязана быть тавтологией (что практически очевидно), то есть теорема верна "в обе стороны".
ПРОДОЛЖЕНИЕ здесь
К ОБСУЖДЕНИЮ
UPD Я написал шесть приложений в виде отдельных комментов, а потом отключил комментарии, не обратив внимания, что приложения перестали при этом быть кому-либо видны.
Сейчас я всё восстановил, но настоятельно прошу не оставлять комментов в этой ветке. Просьба делать это в ОБСУЖДЕНИИ; ссылка дана выше. Любые комменты, оставленные здесь, будут удаляться!
1. О роли тавтологий. Бытует мнение, что тавтологии (понимаемые как "тождественно истинные" утверждения) -- это что-то заведомо тривиальное. Первые приходящие в голову примеры тавтологий -- это что-то вроде "a=a" или "из A следует A". Однако на самом деле существует много примеров совершенно неочевидных тавтологий. Я хочу начать с аргумента, который считаю очень важным, но на котором крайне редко делают акцент.
Пусть мы доказали некоторую теорему T. Доказали при помощи логических рассуждений, опираясь при этом на некоторые аксиомы. Скажем, это могли быть аксиомы элементарной геометрии, а T -- это теорема Пифагора. В любом рассуждении мы используем только конечное число аксиом. Пусть в нашем рассуждении мы опирались на аксиомы A1, ..., An. Что же мы доказали при помощи своего рассуждения? Мы доказали то, что утверждение T логически следует из наших аксиом. Используя логическую символику, мы можем записать следующее утверждение Ф: A1 & A2 & ... & An -> T, означающее, что из некоторых утверждений логически следует T. Сам этот факт доказывается чисто логически, и при этом совершенно неважно, о чём мы говорим. Нигде не подразумевается, что речь идёт именно о точках и прямых, и при желании можно считать, что речь идёт о каких угодно объектах. Поэтому утверждение Ф будет тавтологией -- оно верно всегда, независимо от того, какой смысл мы придадим используемым в записи формулы символам.
Таким образом, любое содержательное математическое утверждение, то есть любое доказательство чего-либо при помощи аксиом, можно интерпретировать как чисто логическое доказательство некоторой тавтологии. Такая переформулировка ничего не даёт в содержательном отношении, потому что доказать тавтологию ничуть не проще, чем провести исходное рассуждение. Но при этом становится ясной такая вещь: тавтологии, взятые в целом, в некотором смысле содержат в себе все содержательные утверждения о математических объектах. Из этого можно сделать несколько поспешный вывод, что математика сводится к чистой логике. Я думаю, в такой формулировке тезис звучит слишком радикально. О том "творческом" элементе, который никуда не исчезает, я бы хотел поговорить в конце. А пока зададимся естественным вопросом: каких логических средств и приёмов достаточно для того, чтобы провести любое логическое рассуждение? То есть каким "арсеналом" надо обладать, чтобы быть в состоянии доказать логически любую тавтологию?
Ответ оказывается неожиданно простым. Достаточный набор средств намного меньше даже того, что всем известно и привычно по материалу школьного курса. Базисный набор средств, обладающих свойством полноты, то есть достаточный для вывода всех тавтологий, может быть предъявлен многими способами при разных подходах. Сразу же отметим, что ни о каких "силлогизмах Аристотеля" не будет и речи. Этот популярный и часто всплывающий набор приёмов не обладает никакой полнотой; он требует специальных усилий для запоминания. То, что я хочу здесь предложить, не только обладает полнотой, но и запоминается (я хотел бы надеяться!) "в первом чтении" :)
2. Логические задачи. Здесь мы сначала рассмотрим часто встречающуюся ситуацию, когда дан некоторый набор считающихся истинными высказываний, из которых требуется вывести некое следствие. Так часто бывает в логических задачах. Типичный ходовой пример: Известно, что все красные варёные раки мертвы. Также известно, что все варёные мёртвые раки красны. Следует ли отсюда, что все красные мёртвые раки варёны? :)
Ответ в этой задаче отрицателен. Задачу можно сформулировать в символической форме, на языке исчисления высказываний. Пусть имеется некий рак. Обозначим через p, q и r соответственно высказывания о том, что этот рак является красным, мёртвым или варёным. Тогда из условий следует истинность высказываний p & r -> q, q & r -> p. Требуется выяснить, следует ли отсюда логически, что p & q -> r? На языке тавтологий это означает в точности следующее: будет ли тавтологией формула (p & q -> r) & (q & r -> p) -> (p & q -> r)?
Если формула, про которую мы хотим выяснить, является ли она тавтологией, содержит n переменных, то легко понять, что имеется в точности 2^n (два в степени n) разных возможных случаев для этих переменных принимать значения "истина" или "ложь". Тавтологичность формулы означала бы, что она истинна во всех 2^n случаях. При небольших значениях n полный перебор вполне возможен; обычно рисуют так называемые "таблицы истинности". В конкретном примере оказывается, что формула тавтологией не будет: она будет ложной при условии, что p, q истинны, а r ложно. В общем случае, если переменных в задаче имеется, скажем, 100, то при полном переборе надо рассмотреть уже 2^{100} вариантов -- это очень много. Одной из актуальных задач современной математики является вопрос о том, имеется ли принципиально более быстрый способ убедиться в тавтологичности формулы, нежели полный перебор всех вариантов.
Хорошо известна популярная головоломка, связываемая с именем Эйнштейна. В Cети есть очень много вариантов её формулировки. Речь там идёт о пяти людях разных национальностей, живущих в домах разного цвета, пьющий один из пяти напитков, курящих определённый сорт сигарет и разводящих какое-то из домашних животных. При этом даётся ряд условий типа "сосед норвежца пьёт пиво", а в итоге спрашивается что-то типа "кто разводит рыбок?" Чисто теоретически можно было бы ввести большое количество обозначений для высказываний типа "в третьем доме живёт англичанин", "обладатель третьего дома курит "Мальборо"". Каждое из этих условий может быть истинно или ложно, поэтому для него можно завести отдельную логическую переменную (вроде p, q или r выше). Переменных при таком подходе будет очень много, и полный перебор заведомо не является удобоваримым подходом. Я здесь использую этот пример как иллюстрацию на тему того, как могут на практике возникнуть тавтологии сложного вида. Особо хочу оговорить, что целью поста не является обсуждение способов решения конкретных логических задач и головоломок, поэтому я в категорической форме заявляю о том, что этих вещей в комментах затрагивать не следует. Анализируя условие задачи, мы можем записать в символической форму всё, что нам известно напрямую. Кроме того, есть ряд неявно подразумеваемых условий вроде того, что тот, кто пьёт кофе, не пьёт пиво. Символически это будет высказывание типа p -> ¬q. Также должно быть учтено то, что один из сортов сигарет кто-то да курит. Это также может быть сделано на языке символов. В итоге мы выписываем ряд условий, которые нам даны, и наш вопрос может заключаться в том, следует ли из этого логически что-то конкретное типа того, что немец разводит рыбок. Соединяя данные нам условия знаком конъюнкции и беря их импликацию с заключением, мы приходим к формуле вида Ф, рассмотренной выше. Относительно неё мы хотим узнать, будет ли она тавтологией. Если да, то мы хотели бы в этом убедиться не путём полного перебора, а путём логического доказательства (в идеале -- короткого). В самом деле, если мы имеем нечто тавтологичное, верное всегда, то есть некий логический закон (пусть и сложно формулирующийся), то должно же быть какое-то подтверждение этому, основанное на базисных правилах логики?
3. Исчисление высказываний. В свете сказанного выше должна представляться естественной следующая схема. Рассматривается некоторый набор символов для обозначения так называемых высказывательных переменных, каждая из которых может принимать два логических значения -- "истина" и "ложь". (Чаще всего этим значениям сопоставляют для простоты символы T и F или просто 1 и 0.) Из переменных, которые здесь будут обозначаться маленькими латинскими буквами (с индексами или без), можно составлять более сложные выражения -- формулы исчисления высказываний -- при помощи логических связок. Последние таковы: отрицание, которое я здесь обозначаю символом ¬, конъюнкция ("логическое и"), дизъюнкция ("логическое или"), импликация ("логическое следование") и эквиваленция ("тогда и только тогда"). Обозначают перечисленные логические связки зачастую по-разному. Хотя я очень не люблю объяснять разного рода "элементарщину", считаю нужным оговорить две вещи. Одна из них касается смысла дизъюнкции: под "p или q" подразумевается "не исключающее или", то есть высказывание "p или q" истинно, если хотя бы одно из высказываний p, q истинно (соответственно, дизъюнкция ложна, если и только если ложны оба высказывания p, q). Второе замечание касается импликации. Когда мы пишем "p -> q" или говорим "p влечёт q" (тот же смысл имеют выражения "если p, то q", "из p следует q", "при условии p выполняется q" и так далее), то ложность этого высказывания предполагает наличие опровергающего примера. То есть в ситуации, когда p истинно, q может оказаться ложным. Здесь p называется посылкой, а q -- заключением импликации. Таким образом, импликация считается ложной только в одном из случаев -- когда посылка истинна, а заключение ложно. Во всех остальных случаях импликация считается истинной, что часто вызывает некоторое недоумение, но к этому нужно привыкнуть. Если мы знаем, что посылка ложна, то этого достаточно для заключения об истинности импликации. То же самое справедливо, если известно, что истинно заключение.
Итак, дадим определение формулы (исчисления высказываний). Всякая высказывательная переменная считается формулой. Если Ф -- некоторая формула, то (¬Ф) -- также формула. Если * есть одна из оставшихся логических связок, перечисленных выше, то (Ф1 * Ф2) считается формулой для любых формул Ф1, Ф2. Каждая формула строится по этим правилам. В итоге может получиться что-нибудь вроде выражения ((p -> (¬q)) & (r V ((¬p) -> (((q & r) -> p))))). Здесь &, V и -> являются символами для конъюнкции, дизъюнкции и имликации соответственно. Лишние скобки при записи формул далее будут часто опускаться.
Чтобы существенно упростить изложение и уменьшить количество используемых правил, мы берём в наше исчисление только две связки -- отрицание и импликацию. Все остальные связки легко выражаются через выбранные две. Например, "p или q" по смыслу означает то же, что ¬p -> q; "p и q" есть отрицание того факта, что "не-p или не-q", то есть ¬(¬p V ¬q). То же самое можно представить и как ¬(p -> ¬q). Эквиваленция "p равносильно q" выразима в виде (p -> q) & (q -> p).
Таким образом, мы берём за основу связки ¬ и ->, и в формулах используем только их. Заметим, что у нас ранее фигурировала конъюнкция в записи формулы Ф из первого раздела. Здесь нет проблемы, так как вместо A & B & C & D -> E мы можем писать имеющую тот же смысл формулу A -> (B -> (C -> (D -> E))) или, упрощая, A -> B -> C -> D -> E, принимая соглашение, что при наличии одних импликаций скобки расставлены по принципу "справа налево".
Обычно при изложении данного материала приводят список общелогических аксиом и правил вывода. В учебниках могут фигурировать либо списки аксиом, трудных для понимания сходу, либо сложные правила вывода, которые также порой плохо запоминаются (особенно при использовании большого числа связок). Мы решили поступить по-иному. Общелогических аксиом у нас не будет вообще (что может несколько удивить на первый взгляд), а вместо правил вывода я приведу простой список из трёх очень просто формулируемых правил доказательства. Все они очень хорошо известны, и удивить может скорее не их наличие, а остутствие других хорошо известных и часто применяемых правил и приёмов. Но наши три правила будут обладать желаемым свойством полноты: их достаточно для построения любого логического рассуждения в рамках исчисления высказываний. В частности, при помощи этих правил можно вывести все тавтологии (тождественно истинные формулы, то есть формулы, истинные на любом наборе значений переменных), а также можно вывести популярные и полезные правила рассуждения, не вошедшие в список. Ниже идёт список правил, который является одним из основных в данном посте. Далее каждое правило будет прокомментировано.
1) Правило modus ponens, или "правило отсечения"
Пусть считаются доказанными формулы A и (A -> B), где A и B -- некоторые формулы. Тогда разрешается считать доказанной формулу B.
2) Правило "условного рассуждения"
Пусть требуется доказать утверждение вида A -> B. Тогда достаточно принять утверждение A (в качестве предположения) и доказать утверждение B.
3) Правило рассуждения "от противного"
Пусть требуется доказать некоторое утверждение B. Тогда достаточно привести к противоречию утверждение ¬B, то есть отрицание утверждения B.
Вот и весь список. Для краткости далее эти три правила будут сокращённо именоваться MP, Cond и Contr соответственно. Первое сокращение общепринято; два других используются для удобства в контексте данного поста.
Первое правило является классическим и почти не нуждается в комментариях. Понятно, что если установлено положение A, и при этом известно, что A влечёт B, то тем самым B также должно быть верно. Хотя я не ставлю цели анализировать часто встречающиеся логические ошибки (вроде путаницы между прямой и обратной теоремой), хотелось бы обратить внимание на один приём, который высмеивал ещё А.Н.Колмогоров. Имеется в виду использование "правила отсечения" в другую сторону. То есть имеется утверждение B, про которое известно, что оно верно, и имеется импликация A -> B, про которую также известно, что она верна. Ясно, что отсюда никак не следует, что верно A. Более того, можно представить себе ситуацию, когда имеется много установленных фактов B1, B2, ..., Bn, и из гипотетического утверждения A следуют все эти факты, то есть имеют место импликации A -> B1, A -> B2, ..., A -> Bn. При этом говорят, что утверждение A объясняет все наличествующие факты, и на основании этого возникает большой соблазн считать его "верным". При этом часто добавляют, что утверждение A якобы подтверждается фактами. (Это к вопросу о "всеобъясняющих" теориях.) На самом деле, конечно, "объяснить" что-либо можно зачастую очень многими способами. (Особенно просто этого достичь, если использовать какое-либо очень сильное допущение.)
Второе правило очень часто применяется. Мы в любой момент имеем право принять условно любое предположение. В математике часто говорят фразы типа "пусть функция f(x) непрерывна" или "пусть ABCD -- параллелограмм". Ясно, что это делать можно, но при этом всё далее доказанное будет доказано условно, в предположении того, что было принято. Но мы в любой момент можем снять предположение A, из которого мы вывели утверждение B, заключив, что тем самым мы "чисто" доказали импликацию A -> B. Очень многие математические утверждения имеют форму "если ... то ...", поэтому данный приём применяется постоянно: мы принимаем посылку импликации и при этом предположении доказываем заключение.
Здесь стоит также отметить, что в излагаемой версии все общелогические аксиомы мы "растворяем" в простых и понятных правилах, и отпадает необходимость доказывать чисто техническую "теорему дедукции". Это сильно упрощает изложение.
Третье правило хорошо известно и тоже очень часто применяется. Зачастую доказать что-либо удаётся путём приведения к противоречию отрицания нужного утверждения. Под противоречием мы понимаем ситуацию, когда для некоторой формулы A оказываются установленными обе формулы A и ¬A. В этом случае при формальной записи мы будем для удобства писать выражение FALSE -- тождественно ложное высказывание, показывающее, что мы пришли к противоречию. Поэтому третье правило можно будет сформулировать ещё и так: если доказано, что ¬B -> FALSE, то тем самым можно считать B доказанным.
Доказательства будут оформляться подобно программам, с нумерацией формул. При принятии предположений мы будем делать абзацный отступ. На примерах будет хорошо видно, как мы применяем правила и как оформляем рассуждения. Формальное определение доказательства или вывода формул -- задача совершенно рутинная, но я не буду приводить здесь это определение, потому что суть и так раскрыта. Вообще говоря, следует определить понятие "из утверждений A1, ..., An логически следует утверждение B". При этом список утверждений может быть пустым (n=0), и при этом B следует "из ничего", то есть является "логическим законом", тавтологией. Равным образом мы можем говорить о том, что тавтологией будет формула вида A1 -> A2 -> ... -> An -> B с "правонормированной" расстановкой скобок.
В комментариях, служащих приложениями к данному посту, я показываю, как обосновать несколько дополнительных правил рассуждения, каждое из которых также можно использовать. Это закон двойного отрицания, согласно которому ¬¬A можно заменять на A и наоборот; закон контрапозиции, согласно которому от импликации ¬B->¬A можно переходить к импликации A -> B (и наоборот). Особняком стоит такое часто применяемое правило как разбор случаев. Состоит оно в следующем. Допустим, требуется доказать некоторое утверждение B. Мы можем рассмотреть два случая: первый -- когда выполняется некоторое условие A; второй -- когда утверждение A не выполняется, то есть имеет место случай ¬A. В каждом из рассматриваемых случаев мы доказываем утверждение B (вообще говоря, совершенно по-своему). Если это удаётся, то утверждение B можно считать доказанным.
При помощи нескольких вспомогательных утверждений (список которых я также привожу в комментах) можно доказать следующий важный факт.
Теорема о полноте исчисления высказываний. Всякую тавтологию, то есть тождественно истинную формулу исчисления высказываний, можно доказать при помощи использования правил 1, 2, 3.
Нелишне добавить, что всякая доказуемая при помощи данных правил формула обязана быть тавтологией (что практически очевидно), то есть теорема верна "в обе стороны".
ПРОДОЛЖЕНИЕ здесь
К ОБСУЖДЕНИЮ
UPD Я написал шесть приложений в виде отдельных комментов, а потом отключил комментарии, не обратив внимания, что приложения перестали при этом быть кому-либо видны.
Сейчас я всё восстановил, но настоятельно прошу не оставлять комментов в этой ветке. Просьба делать это в ОБСУЖДЕНИИ; ссылка дана выше. Любые комменты, оставленные здесь, будут удаляться!