Логика высказываний

10 февраля 2021, автор: Елена Позднякова

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

1. Обучение одного нейрона удобно рассматривать на основе таблиц истинности для базовых логических операций (конъюнкция, дизъюнкция. отрицание).

2. В состав темы "Логика высказываний" входит ужасный XOR (читается, как КСОР)", который приостановил развитие нейросетей в 1969 году.
Причиной стало следующее.
Марвин Минский в своей совместной работе с Сеймуром Папертом "Перцептроны. Введение в вычислительную геометрию" раскритиковал перцептрон (это первая модель нейросети), который, по его словам, не может реализовать простейшую логическую функцию XOR: либо-либо.
На самом деле это не так, но известно об этом стало позже.
А тогда, после публикации названной книги, работы по нейронным сетям были свернуты во многих научных центрах и финансирование существенно урезано. Нейросети почти на 10 лет были забыты и заброшены.

3. И третья причина, почему "Логика высказываний" появилась здесь.
В курсе "На пути к нейросети" рассматривается создание нейросети, которая выполняет производные логические операции (XOR, импликация, эквиваленция), из базовых логических элементов путем их комбинации, без использования метода обратного распространения ошибки.

¬ отрицание

∧ конъюнкция

∨ дизъюнкция

⊕ исключающее или

→ импликация

↔ эквиваленция

Язык логики состоит из высказываний и логических связок.

Высказывание - это повествовательное предложение, относительно которого можно определенно сказать, истинно оно или ложно.
Обозначения:
1 - истина,
0 - ложь.

Синонимом высказывания является суждение.
Приведу некоторые выдержки из авторитетных источников по этому вопросу.

Обратите внимание, что в учебнике логики истинность суждения определена через связь с окружающей действительностью (нам это в дальнейшем еще пригодится!).

А теперь перейдем к логическим операциям.

Логические операции - это действия с высказываниями, как в математике.
Новые высказывания создаются путём соединения более простых. Соединение высказываний производится с помощью логических операторов.

Логические операторы - это специальные символы, которые изменяют или комбинируют логические значения высказываний (истина/ложь).

Базовыми логическими операторами являются:
¬ отрицание
∧ конъюнкция
∨ дизъюнкция.

Все остальные операторы являются производными от базовых и могут быть выражены с помощью них.

Вот некоторые производные логические операторы, которые мы рассмотрим:
⊕ исключающее ИЛИ
→ импликация
↔ эквиваленция.

Раздел математической логики, в котором изучаются логические операции над высказываниями называется алгебра логики.
Чаще всего используется двоичная логика, то есть, предполагается, что высказывания могут быть только истинными или ложными.
Однако, стоит упомянуть, что существуют и логики более высокой размерности, например, троичная логика (в данном материале она не рассматривается).

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

Выполнить логическую операцию - это значит, определить значение истинности выражения.

Этих значений может быть только два: ИСТИНА (1), ЛОЖЬ (0).

Приоритет логических операций:
¬ отрицание
∧ конъюнкция
∨ дизъюнкция
⊕ исключающее или
→ импликация
↔ эквиваленция

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

Смысл: неверно, что ...

Пример:
Маша варит суп.
Неправильное отрицание: Маша не варит суп, Маша варит не суп, не Маша варит суп.
Правильное отрицание: неверно, что Маша варит суп.

Утверждение ¬A истинно тогда и только тогда, когда A ложно.

Конъюнкция ( от лат. conjunctio - "соединение") - логический оператор, отражающий употребление союза "И" в сложных высказываниях.

Конъюнкция - это логическая операция, результат которой равен ИСТИНА тогда и только тогда, когда оба операнда имеют значение ИСТИНА.

Смысл: и то, и это одновременно.

Конъюнкция может применяться к двум и большему числу операндов (бинарная, тернарная, n-арная).

Утверждение A ∧ B истинно, если и A, и B истинны, и ложно в противном случае.

Дизъюнкция ( от лат. disjunctio - "разобщение") - логический оператор, отражающий употребление союза "ИЛИ" в сложных высказываниях.

Дизъюнкция - это логическая операция, результат которой равен ЛОЖЬ тогда и только тогда, когда оба операнда имеют значение ЛОЖЬ.

Смысл: или то, или это, или оба сразу.

Утверждение A ∨ B истинно, если A или B (или оба) истинны, и ложно, если оба операнда ложны.

Исключающее ИЛИ - логический оператор, который истинен для двух переменных тогда и только тогда, когда один из аргументов истинен, а другой — ложен.

Смысл: или то, или это, но не оба сразу.

Утверждение A ⊕ B истинно, когда истинно либо A, либо B, но не оба.

Операцию XOR можно разложить на базовые логические операции: отрицание, конъюнкция, дизъюнкция:

A ⊕ B = (¬A ∧ B) ∨ (¬B ∧ A)

Читается так:
дизъюнкция двух конъюнкций:
конъюнкции отрицания A и В,
конъюнкции отрицания В и А.

Импликация - бинарная логическая связка, которая записывается формулой:
Посылка → Следствие,
где посылка является достаточным условием для выполнения следствия, а следствие является необходимым условием для истинности посылки.
Импликация соответствует условному оператору "если …, то …"
Импликация не является коммутативной операцией (слагаемые нельзя менять местами).

Смысл: если А, то B.

Еще раз:
A → B (читаем: если А, то B)
где
А достаточное условие для В,
В необходимое условие для истинности А.

A → B ложно, только когда A истинно, а B ложно.

Пример импликации №1.
В этом примере мы учитываем смысл высказываний и смысловую причинно-следственную связь между посылкой и следствием:

Если прошел дождь, то на улице мокро.
А (посылка) = Прошел дождь.
В (следствие) = На улице мокро.

А достаточное условие для В: для того, чтобы на улице стало мокро, достаточно, чтобы прошел дождь. Но не необходимо! Например, вместо дождя могла проехать поливальная машина.

В необходимое условие для истинности А: если прошел дождь, то на улице мокро. Мокро - это необходимое условие, точнее, следствие. Такого не может быть, что прошел дождь, но улица сухая. Если улица сухая, значит, не было никакого дождя и высказывание "Прошел дождь" не может быть истинным.

До рассмотрения таблицы хочу обратить внимание вот на какой момент: в данном случае, в качестве истины или лжи выступает не собственно истина (отражающая окружающую действительность) и не собственно ложь (не отражающая окружающую действительность), а факт выполнения утверждений, указанных в изначальной импликации.
Прошел дождь - условие выполняется - значит, присваиваем значение 1(истина), не прошел дождь - условие не выполняется, значит, присваиваем значение 0 (ложь).

Пока вроде бы все логично?! :)

Уфф! Так хотелось обойтись без парадокса материальной импликации...

И, кажется, у меня получилось!

Временно. Обойти парадокс, конечно же, не удастся.

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

Еще пример (№2, пока опять без парадоксов).

Если этот человек - президент РФ, то он старше 35.
(данное требование к возрасту установлено в Конституции, статья 81).

А (посылка) = Этот человек президент РФ.
В (следствие) = Этот человек старше 35.

А достаточное условие для В: если человек является президентом, то он точно старше 35. Это достаточное условие, но не необходимое. Достаточно знать, что человек - президент, чтобы быть уверенным, что он старше 35.
При этом не все люди старше 35 - президенты.

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

А теперь предлагаю рассмотреть эти же 2 примера наглядно, на множествах, чтобы лучше понять соотношение необходимых и достаточных условий:

Как видите, в обоих случаях множество А является подмножеством множества В.
Именно поэтому А всегда есть В, но В не всегда есть А.

Импликацию можно разложить на базовые логические операции: отрицание, дизъюнкция:

A → B = ¬A ∨ B
Читается так:
дизъюнкция отрицания A и В.

Эквиваленцией двух высказываний А и В называется новое сложное высказывание, которое истинно тогда и только тогда, когда оба исходных высказывания одновременно истинны и одновременно ложны.
Синоним - эквивалентность.

Смысл: тогда и только тогда.

A ↔ B (читаем: А тогда и только тогда, когда В)
где
А необходимое и достаточное условие для В,
В необходимое и достаточное условие для А.

A ↔ B истинно, только если оба значения A и B ложны, либо оба истинны.

Пример эквиваленции.
Две прямые параллельны тогда и только тогда, когда они не пересекаются.

А: Две прямые параллельны.
В: Две прямые не пересекаются.

А необходимое и достаточное условие для В, а В необходимое и достаточное условие для А.

Множества А и В равны. Графически это можно представить так:

Эквиваленцию можно разложить на базовые логические операции: отрицание, конъюнкция, дизъюнкция:

A ↔ B = (¬A ∧ ¬B) ∨ (A ∧ B)

Читается так:
дизъюнкция двух конъюнкций:
конъюнкции отрицания A и отрицания В,
конъюнкции А и В.

А попробуйте сами заполнить!

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

Итак, возможно, что до сих пор вы никакого парадокса не заметили - и это потому, что когда я приводила примеры импликации, я умышленно ввела оговорку, что:

мы учитываем смысл высказываний и смысловую причинно-следственную связь между посылкой и следствием.

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

Теперь еще раз посмотрите на таблицу истинности импликации и особое внимание обратите на последние две строчки:

Как же так?
В предпоследней строчке мы видим, что если из ЛЖИ следует ИСТИНА, то результатом будет: ИСТИНА!
В последней строчке мы видим, что если из ЛЖИ следует ЛОЖЬ, то результатом будет: опять ИСТИНА.

А давайте подставим в эту конструкцию не связанные по смыслу выражения:
Если луна сделана из зеленого сыра, то 2х2=4.
Если луна сделана из зеленого сыра, то жирафы умеют летать.

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

Итак, парадокс материальной импликации:
ИЗ ЛЖИ МОЖЕТ СЛЕДОВАТЬ ВСЁ, ЧТО УГОДНО: РЕЗУЛЬТАТ БУДЕТ ИСТИННЫМ.

Как это объяснить?

Дело в том, что истинность следования А → В (если А, то В), подтверждается отношениями между множествами А и В.
Множество А всегда является подмножеством множества В.
На математических символах это выглядит так: A ⊂ В.
Графически так:

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

Ну в самом деле: какая луна из зеленого сыра? Какие летающие жирафы?
Ложь, вранье, болтовня. Есть даже соответствующая фраза в разговорном языке: "Да это все пустое!" - И действительно, пустое. Множество не состоящее ни из одного элемента. Ноль. Пустота.

Пустое множество обозначается вот таким знаком: ∅ и обладает следующими свойствами:

• пустое множество является подмножеством любого множества ∅ ⊂ ∀а
• пустое множество является подмножеством самого себя ∅ ⊂ ∅

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

И никакого парадокса здесь, как видите, нет: обычная математика и операции над множествами.

И не бойтесь того, что из лжи следует истина. Эта операция абсолютно безопасна.
Если вы будете строить автоматическое доказательство какой-либо теоремы с использованием логических операторов (в том числе примените и импликацию, как оператор следования, - а куда ж без него в доказательствах!), то ложь на входе - это просто 0. В пустое множество невозможно передать никакое значение, потому что оно не содержит ни одного элемента. Там всегда будет пусто. Луна из зеленого сыра не появится, а жирафы не научатся летать.
А если вдруг они возьмут и научатся, то множество становится НЕ ПУСТЫМ, значит, оно приобретает значение ИСТИНА и таблица истинности импликации работает уже по-другому.

Парадокс эквиваленции.
В завершение темы хочу сказать, что в таблице истинности эквиваленции можно разглядеть такой же парадокс (0,0,1):
Ложь тогда и только тогда, когда ложь. Ведь это выражение имеет значение ИСТИНА!
"Луна сделана из зеленого сыра тогда и только тогда, когда жирафы умеют летать". Истина.

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