О логике

Давайте поговорим о логике: с точки зрения математики, но с привязкой к реальности.

Оглавление рубрики "Мой учебник"

Начнем с высказываний. Высказывание — это некоторое текстовое утверждение, которое может быть истинным или ложным.

Например, "Все кошки серы", "Если сумма цифр числа делится на 3, то и само число делится на 3", "Максимальная выплата в 'игре пиратов' не зависит от численности команды", "Убийца — дворецкий", "Ti amo".

Закон исключенного третьего гарантирует, что "либо-либо", даже если выяснить, что же именно, мы не можем.

А бывает так, что мы не можем, причем принципиально. Об этом в другой раз.

Важно, что логике нет никакого дела до смысла высказываний и их "истинной истинности". Еще важно, что логика устанавливает истинность и ложность высказываний по определенным правилам, опираясь на аксиомы (постулаты, посылки) — высказывания, принимаемые за истину. И логике нет дела, истинны они "на самом деле" или нет. И никакой абсолютной истины нет в логике, все сводится к тем или иным аксиомам (посылкам, постулатам).

Ничего не напоминает? Я про отсутствие абсолютной истины.

Какие же правила позволяют устанавливать истинность одних высказываний на основе других?

Из высказываний можно строить новые с помощью логических операций. Их много, но основные (к которым все сводится) немногочисленны. Это отрицание (НЕ А), которое истинно, если высказывание А ложно, и наоборот. Это конъюнкция А И В, которая объединяет два высказывания и истинна только тогда, когда истинны оба. Дизъюнкция А ИЛИ В, которая тоже объединяет два высказывания и ложна только тогда, когда ложны оба. Исключающее "ИЛИ" (А XOR В), которое ложно, если оба высказывания ложны или оба истинны. И импликация А→В, которая читается "из А следует В" и ложна только тогда, когда А истинно, а В ложно.

Давайте обсудим. С отрицанием и И все понятно. Бытовое ИЛИ может означать как логическое ИЛИ, так и исключающее — различаем по контексту. Так, "Я или эта драная кошка" явно исключающее, а "Там были Маша или Катя?" ИЛИ обычное, так как вполне могли быть и обе.

В программировании обычно используют "короткое замыкание", не вычисляя второй аргумент оператора AND или OR, если по первому результат понятен. Поэтому в Перле пишут $x=shift || 42; если есть ненулевой параметр, shift его вернет, а если нет, то "вычислится" второй аргумент.

Еще одна идиома: do_this() or die; Прелестно же читается! Если функция do_this вернет не нуль, то и ладно, а если нуль (аварийный сигнал), то вычислится функция die, которая прервет программу и выдаст сообщение (которое можно тоже указать).

А в Ассемблере (когда на нем еще писали) вместо присвоения нуля регистру процессора использовали XOR AX, AX. Потому что это намного быстрее.

Есть полезные формулы де Моргана:

НЕ(А И В) = (НЕ А) ИЛИ (НЕ В)
НЕ(А ИЛИ В) = (НЕ А) И (НЕ В)

Проверьте их. В принципе, это очевидно, но иногда бывают ошибки. Например, для ложности высказывания А И Б достаточно опровергнуть одно из них, а не оба.

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

Можно заменить высказывания буквами и строить сколь угодно сложные формулы (они тоже высказывания, или рассуждения). Но все можно выразить через И, ИЛИ и НЕ. И даже только через И и НЕ, применив формулы де Моргана.

Можно заметить, что И похоже на умножение, если истину обозначить 1, а ложь 0. ИЛИ тогда похоже на сложение, только 1+1=1. Отрицание это 1-x, но его обычно обозначают черточкой над буквой. Любую формулу можно свести с конъюктивной нормальной форме (сумма произведений) и к дизъюнктивной нормальной форме (перемножение сумм).

КНФ, если простыми словами, это высказывание вида "или Это, это и это, или То, то и то, или еще_вариант и вот_с_таким_условием, или вот_так_тоже_можно". Например, "Преступник Смит, залез через окно, алиби что играл в карты — покрывают сообщники; либо преступник Джонс, сидел в шкафу, мотив — ревность".

А ДНФ — это высказывание "Либо это, либо то, но при этом обязательно либо А, либо Б, либо Ц, и непременно либо ты, либо он, либо она". Например, "на завтрак яичница или каша или йогурт, на обед щи или борщ или солянка, на ужин спагетти алла карбонара или тальятелли кон ле коцце".

Есть такая любопытная задача, не решенная. Выполнимость. Пусть дана дизъюнктивная нормальная форма; истинна ли она хоть при каком-то наборе переменных? Если переменных много и скобок много, то решение неэффективно: только скобки раскрыть, а это "каждый с каждым" и по сути полный перебор. А вот есть ли эффективное решение — пока неизвестно. Подробнее в другой раз.

Я как-то писал популярно про парадокс парламента. Если в парламенте нет единогласного по всем вопросам большинства, то он может принять противоречивые утверждения, и значит — любое наперед заданное утверждение. Речь идет о том, что парламент голосованием устанавливает истинность утверждений, которые ставит спикер. Утверждения, которые окажутся истиной, можно пересчитать: А1, А2 и т.д. За каждое голосует большинство. Но за "А1 и А2" голосует не больше, чем за А1, а за "А1 и А2 и А3" не больше, чем за "А1 и А2". Либо на каком-то шаге одно и то же большинство голосует за все утверждения, либо утверждения, скажем, А1 и А2 по-отдельности принимаются, а "А1 и А2" отвергается. А это уже противоречие. Ставьте на голосование "НЕ(А1 и А2) ИЛИ С", его примут, до С обсуждение даже не дойдет. Потом суд постановит, что раз приняты А1 и А2, то "А1 и А2" ложно, а тогда выполнять надлежит С. А уж как это "заболтать" убедительно — политики знают, их учить не надо.

Теперь обсудим импликацию: следование. Эта операция напрямую связана с логическим выводом: из А следует В.

Примером является высказывание "Если сумма цифр числа делится на 3, то и само число делится на 3", в котором А — это "сумма цифр числа делится на 3", а В — это "число делится на 3". В данном случае можно обратить высказывание, так как из В следует А. Иногда нельзя, например, если сумма цифр делится на 9, то само число делится на 3, а вот наоборот не обязательно.

Если А истинно, а В ложно, то импликация ложна: это трактуется как невозможность вывести из истинного утверждения ложное. Из истинного выводится истина, для этого все и затевалось, а вот что из лжи можно вывести истину — многих удивляет.

Но ведь можно. Вот очевидные примеры.

• Все нечетные числа простые (ЛОЖЬ). Семь нечетно (ИСТИНА). Следовательно, семь простое (ИСТИНА).
• Если ряд сходится, он сходится абсолютно (ЛОЖЬ). Ряд из обратных квадратов сходится (ИСТИНА). Значит, он сходится абсолютно (ИСТИНА).
• Все птицы летают (ЛОЖЬ). Голубь — птица (ИСТИНА). Голубь летает.
• У любого непрерывного преобразования шара есть единственная неподвижная точка (ЛОЖЬ, не обязательно единственная). Точки а и b неподвижны (ИСТИНА). Следовательно, они совпадают (может быть, и истина).
• Пример из Ш. Холмса: если на руках есть следы пороха, человек стрелял из пистолета. Если их нет, он все равно мог стрелять из пистолета.

Рассуждение про голубя даже убедительно. Если забыть про киви, пингвинов и страусов. Но ведь можно так: большинство птиц летает, а голубь — птица. Значит, голубь летает ИЛИ голубь относится к немногочисленному списку нелетающих птиц. Можно даже XOR, поскольку варианты взаимоисключающие. Далее проверяем, что голубь в список нелетучих не вошел, и доказали, что голубь летает. Вот такие вот рассуждения и составляют предмет практической логики.

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

Удобно представлять себе высказывания как множества, и истинность — это попадание в множество. Тогда картинки наглядно иллюстрируют все понятия. Обсудим подробнее импликацию: это одно множество в другом. Если вы попали в маленькое, вы попали в большое тоже. Это и есть следование.

Теперь очевидно правило: если из C следует D, то из (НЕ D) следует (НЕ C). В самом деле, если C лежит в D, то точки, не попавшие в D, в C попасть не могут тем более.

Оно используется при доказательстве от противного. Надо вывести В из А? Предположи, что В неверно и опровергни А.

Например, индукция. Пусть есть объекты с номерами от 1 и далее, и некоторое свойство верно для первого. И известно, что если оно верно для какого-то, то верно и для следующего. Тогда оно верно для всех.

Предположим, что это не так, и оно неверно для какого-то объекта номер N. Ну, оно верно для 1 и, следовательно, для 2. Раз оно верно для 2, то и для 3. И так далее, мы придем на каком-то шаге к N, и опровергнем предположение. Раз истинные посылки привели нас к противоречию, то они ложны, ведь из истины не может следовать ложь. Мы из (НЕ В) вывели (НЕ А). Значит, из А следует В.

Собственно, рассуждения и сводятся с оперированию высказываниями с помощью описанных операций. Есть высказывания, истинность которых уже установлена, либо когда-то раньше (отпечатки пальцев разных людей различны), либо выведена только что. Высказывания могут быть составными, через И, ИЛИ, XOR и с применением отрицания, а также могут использовать импликацию (если... то...). Ну и рассуждаем. Наша цель — получить цепочку высказываний, связанных импликацией, и чтобы первое было истиной. Тогда истинны все.

Последнее про импликацию. Она самодостаточна, то есть с ее помощью можно выразить все логические операции. Достаточно выразить НЕ и либо И, либо ИЛИ, потому что к ним сводится все остальное. Отрицание получается как x→0 (если х истина, то импликация ложна, а если ложь, то импликация истинна). ИЛИ получается так: (x→0)→y. А вот И: ((x→0)→y)→0.

Ясно, что x→1 это 1, и 1→x это x.

Кстати, на множествах ясны и кванторы: "для всех" и "хотя бы для одного". Часто рассуждения так и ведутся: "все птицы летают", или "существуют нелетающие птицы". Первое означает, что все множество лежит в другом, второе означает непустоту множества или пересечения двух множеств.

Вот пример определения (непрерывности в точке) с использованием кванторов: "Для любого положительного числа эпсилон существует хотя бы одно положительное число дельта, такое, что если x-a по модулю меньше дельта, то f(x)-f(a) по модулю меньше эпсилон." Курсивом выделены кванторы и импликация.

Единственное, что логик может сказать по поводу посылок (аксиом, постулатов) — это выявить их противоречивость. Проверить непротиворечивость, как правило, не удается без привлечения дополнительных предположений.

Вот пример: в геометрии Эвклида есть пятый постулат (о параллельных). Он гласит, что "...ровно одну". У Лобачевского "...хотя бы две". А вот если попробовать "...ни одной", то есть чтобы любые две прямые пересекались, то получится противоречие с другими аксиомами. Из других аксиом можно вывести, что через точку вне данной прямой всегда можно провести прямую, не пересекающую данную. А вот только одну или можно несколько — доказать нельзя, как выяснилось.

Если вы этого не знаете, но решите потягаться с Лобачевским, то поначалу вы докажете много интересных теорем. В общем-то, почти что угодно сможете доказать! Но потом либо сами заметите, что доказали два противоположных утверждения, либо вас кто-то приведет в чувство.

Чисто логическое доказательство удается (за пределами научных работ) увидеть редко. Причина в том, что сложные рассуждения вроде соритов редки. Если посылки даны, выводы перечислить обычно несложно. Вся проблема в этих посылках.

Ошибки чаще встречаются. Классика: "В стране нет свободы слова, о чем ежедневно вещают сотни оппозиционных ресурсов". "Статьи против теории относительности запрещены, хотя опровержения ее опубликованы". "Теория относительности неверна, потому что Эйнштейн украл ее у ***". "Вы строите свое рассуждение на постулате ***, а он неверен; следовательно, всё ваше рассуждение неверно". "Есть более простое объяснение, поэтому ваше бредово". Ну и так далее.

Особенно забавно наблюдать, как разнообразные отрицатели старательно отфильтровывают в Сети то, что играет им на руку. Демоны Максвелла прямо какие-то! Честно говоря, я бы ввел статью за надругательство над Логикой в уголовный кодекс.

В обычной жизни логика — это борьба за посылки (надо либо убедить оппонента, что верны те, что тебе нужны, либо опровергнуть как-то те, что тебе не нужны, либо просто проверить) и ограничение/расширение класса объектов так, чтобы утверждение про "все из" или "хотя бы один из" были верны. Если удастся собрать всех подозреваемых в особняке, то "хотя бы один из них преступник" станет верным и можно двигаться дальше. Если удастся выделить из них часть, для которых "каждый из них невиновен", то вообще отлично. Если останется один, то задача решена.

Если удалось опровергнуть посылку "я всю ночь играл в шахматы с Васей", то можно поставить под сомнение вывод "он не провел ночь с Олей", и это прекрасно (с точки зрения логики).

Именно по этой причине — логически доказать что бы то ни было раз и навсегда можно только в исключительных случаях — и существуют суды. Если бы можно было выдать формальное доказательство, проверить его и выбрать соответствующее наказание в кодексе — суды были бы не нужны. Но в том-то и дело, что надо убедить, в том числе и с помощью логики: исключить все варианты, кроме одного, или даже не исключить, а свести вероятность (в смысле уверенности) к пренебрежимо малой величине. А убедительность рассуждения — вещь вне логики. Вася подтвердил, что в шахматы играли — убедительно это или нет?

И именно по этой причине — логически доказать что бы то ни было раз и навсегда не получится — ученый никогда не побежит проповедовать свою новую теорию на всех перекрестках! Равно как и сыщик, быстренько сляпавший на первый взгляд непротиворечивую версию, не закричит о раскрытом деле: надо проверить все альтернативы, исключить все варианты, подсобрать доказательств. Детективы полны такими примерами.

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

Вот пример ошибочного вывода. Как доказать, что в любом табуне все кони одного цвета? Ну, по индукции. Табун характеризуется числом коней. Если конь всего один, то "все" кони одного цвета. Если для табуна в N коней факт имеет место, то он имеет место и для табуна в N+1 коня. Потому что можно одного коня изъять, остальные одного цвета. Потом коня вернем, изымем другого. Все тоже одного цвета, причем того же самого, остальные-то кони остались в табуне. По индукции, в любом табуне все кони одного цвета.

С точки зрения логики, кстати, почти все правильно. Но ошибка есть: изъятие коней из табуна, в котором два коня, не работает. Два коня могут быть разного цвета, и все в порядке. Так что индукцию надо строить на числе два, а не один, так как переход от 1 к 2 неверен. Если любые два коня одного цвета, то все кони одного цвета, и с этим не поспоришь. Эта импликация верна. А вот верна ли посылка (про любые два) или нет — логику без разницы.

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

Напоследок пару слов о парадоксах. Причина их часто (но не всегда) в самоприменимости, и еще иногда в тщательно скрытой противоречивости посылок.

"Это утверждение ложно" — такое утверждение не может быть не истинным, ни ложным. Оно само себе противоречит.

Но можно же спрятать самоприменимость. Утверждение А: "Утверждение В ложно". Утверждение В: "Утверждение А истинно".

Или вот парадокс заключенного. По приказу, Узника надо казнить в течение недели, но чтобы было неожиданно. В последний день казнить нельзя, не будет неожиданно. Но тогда и предпоследний день не годится. И день перед ним. Вообще казнить нельзя! Узник успокоился, но в четверг неожиданно пришли — и казнили.

Здесь самоприменимость скрыта очень хорошо! Правила противоречивы, и казнить нельзя, но раз нельзя, то стало можно. Как-то так.

Ведь если правила противоречивы, то как быть? Не казнишь — самого казнят за нарушение приказа. Казнишь с нарушением правил — опять рискуешь. Узник полагал, что казнить не будут (с чего он это взял?), ну а тогда правила не нарушены, он же не ожидал сюрприза. А мог рассуждать, что казнят, только пренебрегут правилом. Придут в воскресенье и скажут "да, ты нас ждал, но извини, лучше отвечать за это, чем за срыв казни". И парадокса нет.

Или вот пример, который приводит Салливан. Его брат сказал ему первого апреля: "Сегодня я тебя разыграю". Тот весь день стерегся, но ничего не произошло. Брат сказал: "так вот я тебя и разыграл!"

На этой позитивной ноте и закончим на сегодня. Чтите логику и не мучайте ее. Она хорошая.

Путеводитель по каналу. И подписывайтесь, если еще не.