Математическая логика

Тут есть теория математической логики. Но сначала покажем интересную вещь!

Построение логических таблиц

Отдельная страница

Правила написания логических формул в символьном формате:

Конъюнкция: A & B; A * B; A ∧ B
Дизъюнкция: A | B; A + B; A v B
Инверсия: !A; -A; ¬A
Импликация: A >> B; A -> B; A => B
Эквиваленция: A = B; A <-> B; A <=> B
NAND (Штрих Шейфера): A ' B
NOR (Стрелка Пирса): A ^^ B;
Разделять выражения можно с помощью ; (Несколько формул в одну таблицу)

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

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

Высказывательная форма (пропозициональная форма) — это предложение с переменными, которое становится истинным или ложным после подстановки значений.

Из высказывательной формы можно получить высказывание двумя способами:

Подставить значения всех переменных
Использовать кванторы ∃ (существует), ∀ (все)

Составление высказываний

Из двух высказываний можно составить новое с помощью связок:

A и B — конъюнкция; A ∧ B
A или B — дизъюнкция; A v B
не A — инверсия; ¬A
если A, то B — импликация; A -> B
Примечание: "ЕСЛИ" (A -> B) = 1, если A = 0; и равно B, если A = 1
A тогда, когда B — эквиваленция; A <-> B
Примечание: эквиваленция = 1, если A = B; иначе 0

P.S. Логические таблицы операций доступны здесь.

Формула логического высказывания

Определения формулы Л.В.:

Любая логическая переменная — формула
0, 1 (Ложь, Истина) — формулы
Если F — формула, то ¬F — формула
Если F₁, F₂ — формулы, то F₁ ∧ F₂; F₁ v F₂; F₁ -> F₂; F₁ <-> F₂ — формулы

Алфавит Л.В.:

X, Y, Z, X_i, Y_i, Z_i — символы для логических переменных
¬, ∧, v, ->, <-> — логические символы (приоритет операций убывает сверху вниз)
0, 1 — логические константы

Тождественно истинные/ложные высказывания

Тавтология — формула, принимающая значение 1 при любых значениях переменных.

Тождественно ложная формула — принимает 0 при любых значениях переменных.

Логическое равносилие

Формулы F₁, F₂ равносильны, если они принимают одинаковые значения при всех наборах значений переменных.

Следствие: таблицы истинности совпадают. Обозначение: F₁ = F₂

Свойства:

Рефлексивность: F = F
Симметричность: F₁ = F₂ ⇒ F₂ = F₁
Транзитивность: F₁ = F₂ и F₂ = F₃ ⇒ F₁ = F₃

Законы логики

Основные законы и равносильности

Тождество:
X = X
Противоречие:
X * ¬X = 0
Исключённый третий:
X + ¬X = 1
Идемпотентность:
X * X = X; X + X = X
Двойное отрицание:
¬¬X = X
Коммутативность:
XY = YX; X + Y = Y + X
Дистрибутивность:
X * (Y + Z) = XY + XZ;
X + YZ = (X + Y) * (X + Z)
Ассоциативность:
X * (Y * Z) = (X * Y) * Z;
X + (Y + Z) = (X + Y) + Z
Законы де Моргана:
¬(X + Y) = ¬X¬Y;
¬(XY) = ¬X + ¬Y
X * 1 = X; X + 0 = X
X * 0 = 0; X + 1 = 1
Поглощение:
X(X + Y) = X; X + XY = X
Склеивание:
(X + Y) * (¬X + Y) = Y;
XY + ¬XY = Y
X + ¬X * Y = X + Y;
¬X + XY = ¬X + Y
Импликация:
X -> Y = ¬X + Y = ¬(X + ¬Y)
Эквиваленция:
X <-> Y = (X -> Y) * (Y -> X) = (¬X + Y) * (¬Y + X) =
= XY + ¬X¬Y
Отрицание эквиваленции:
¬(X <-> Y) = X*¬Y + ¬X*Y

Обратные и противоположные предложения

Теорема — предложение, истинность которого доказывается на основе аксиом или ранее доказанных теорем.

Для A -> B можно составить:

A	B	A -> B Исходное	B -> A Обратное	¬A -> ¬B Противоположное	¬B -> ¬A Обратно-противоположное
0	0	1	1	1	1
0	1	1	0	0	1
1	0	0	1	1	0
1	1	1	1	1	1

Замечание: Исходное = Обратно-противоположное, Обратное = Противоположное

Обратное: истинность исходного не гарантирует истинность обратного
Противоположное: истинность обратного гарантирует истинность противоположного
Обратно-противоположное: метод от противного

Достаточные и необходимые условия:

Достаточное условие: выполнение гарантирует событие, но не обязательно единственная причина

Необходимое условие: без него событие невозможно, но выполнение не гарантирует наступление

Если A -> B, то A — достаточное, B — необходимое условие

Если A <-> B, то A и B — взаимно необходимые и достаточные условия

Логическое следование

Логическое следование — это отношение между высказываниями, при котором истинность одного высказывания гарантирует истинность другого.

Если A и B — высказывания, то записывается как A -> B, что читается «A логически следует из B» или «B является логическим следствием A».

Свойства логического следования

Рефлексивность: любое высказывание логически следует само из себя.
Формально: A -> A

Пример: «Если идёт дождь, то идёт дождь» — всегда истинно.
Транзитивность: если A -> B и B -> C, то A -> C
Пример: «Если идёт дождь, то земля мокрая» (A -> B), «Если земля мокрая, то лужи образуются» (B -> C), тогда «Если идёт дождь, то образуются лужи» (A -> C).
Симметричность (для эквивалентности): если A -> B и B -> A, то A и B логически эквивалентны, обозначается A ↔ B
Пример: «x > 2» эквивалентно «не x ≤ 2».

Применение в рассуждениях

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

Примеры использования:

Вывод теорем методом прямого следования
Использование контрапозиции (обратно-противоположного) для доказательства от противного
Сравнение условий для определения достаточности и необходимости

Аргументы в логике

Аргумент — это рассуждение, состоящее из посылок и вывода, где вывод логически следует из посылок.

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

Примеры аргументов

Название	Пример (по левому краю)
Modus Ponens	\| Если идёт дождь, то земля мокрая \| Идёт дождь ---- \| Земля мокрая
Modus Ponens (пример 2)	\| Если число чётное, то делится на 2 \| Число 8 чётное ---- \| Число 8 делится на 2
Modus Tollens	\| Если идёт дождь, то земля мокрая \| Земля не мокрая ---- \| Дождя нет
Syllogismus Disiunctivus	\| Сегодня идёт дождь или светит солнце \| Сегодня не идёт дождь ---- \| Светит солнце
Hypothetical Syllogism	\| Если идёт дождь, то земля мокрая \| Если земля мокрая, то образуются лужи ---- \| Если идёт дождь, то образуются лужи
Прямой аргумент (равносильное преобразование)	\| Все птицы умеют летать \| Воробей — птица ---- \| Воробей умеет летать

4 способа проверки аргумента

Способ	Описание	Пример
Таблица истинности	Составляем таблицу всех возможных значений посылок и проверяем, что вывод истинный, когда все посылки истинны.	\| P1: Если A, то B \| P2: A ---- \| Вывод: B — аргумент правильный
Контрпример	Ищем случай, где все посылки истинны, а вывод ложен. Если такой есть — аргумент неверен.	\| P1: Если идёт дождь, то земля мокрая \| P2: Идёт дождь ---- \| Вывод: земля сухая — контрпример не существует → аргумент верен
Равносильное преобразование	Логически выводим заключение из посылок, используя равносильные преобразования (например, Modus Ponens, Modus Tollens).	\| P1: Если число чётное, то делится на 2 \| P2: Число 8 чётное ---- \| Вывод: 8 делится на 2
Найти по стандартной схеме

Стандартные схемы аргументов

Верные аргументы

Схема	Пример
X -> Y и X следует Y (Modus Ponens)	\| Если идёт дождь, то земля мокрая \| Идёт дождь ---- \| Земля мокрая
X -> Y и ¬Y следует ¬X (Modus Tollens)	\| Если идёт дождь, то земля мокрая \| Земля не мокрая ---- \| Дождя нет

Неверные аргументы

Схема	Пример
X -> Y и Y следует X (Обратное)	\| Если идёт дождь, то земля мокрая \| Земля мокрая ---- \| Дождь идёт — неверно
X -> Y и ¬X следует ¬Y (Противоположное)	\| Если идёт дождь, то земля мокрая \| Дождя нет ---- \| Земля не мокрая — неверно

Нормальные формы логических функций

Нормальная форма логической функции — это стандартизированное представление булевой функции в виде структурированной формулы с использованием конъюнкций (И), дизъюнкций (ИЛИ) и отрицаний (НЕ) переменных.

Виды нормальных форм

Обычная ДНФ (Дизъюнктивная нормальная форма) — формула в виде дизъюнкции конъюнкций, но не обязательно совершенная. Каждая конъюнкция может не включать все переменные.

F = XY + Z
F = ¬XY + X¬Z
F = X¬Y + ¬XZ

Обычная КНФ (Конъюнктивная нормальная форма) — формула в виде конъюнкции дизъюнкций, не обязательно совершенная. Каждая дизъюнкция может не включать все переменные.

F = (X + Y) & (¬X + Z)
F = (¬X + Y + Z) & (X + ¬Y)
F = (X + ¬Y) & (¬X + ¬Z)

СДНФ (Совершенная ДНФ) — каждая конъюнкция включает все переменные; формула истинна точно в тех строках таблицы, где функция = 1.
СКНФ (Совершенная КНФ) — каждая дизъюнкция включает все переменные; формула ложна точно в тех строках таблицы, где функция = 0.

СДНФ и СКНФ из таблицы истинности

X	Y	Z	F(X,Y,Z)
0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	0
1	1	1	1

СДНФ:

Строка 2: X=0, Y=0, Z=1 → ¬X¬YZ
Строка 3: X=0, Y=1, Z=0 → ¬XY¬Z
Строка 5: X=1, Y=0, Z=0 → X¬Y¬Z
Строка 8: X=1, Y=1, Z=1 → XYZ

СДНФ = (¬X¬YZ) + ¬XY¬Z + X¬Y¬Z + XYZ

СКНФ:

Строка 1: X=0, Y=0, Z=0 → (X ∨ Y ∨ Z)
Строка 4: X=0, Y=1, Z=1 → (X ∨ ¬Y ∨ ¬Z)
Строка 6: X=1, Y=0, Z=1 → (¬X ∨ Y ∨ ¬Z)
Строка 7: X=1, Y=1, Z=0 → (¬X ∨ ¬Y ∨ Z)

СКНФ = (X ∨ Y ∨ Z) & (X ∨ ¬Y ∨ ¬Z) & (¬X ∨ Y ∨ ¬Z) & (¬X ∨ ¬Y ∨ Z)

Алгоритм получения СДНФ из обычной формулы

Избавиться от импликаций и эквиваленций (X -> Y = ¬X + Y; X <-> Y = XY + ¬X¬Y)
Убрать одинаковые члены дизъюнкции
Если конъюнкция не содержит всех переменных, умножаем на (X ∨ ¬X) = 1 для недостающих переменных
Раскрыть скобки, объединить одинаковые члены → получаем СДНФ

Алгоритм получения СКНФ из обычной формулы

Избавляемся от импликаций и эквиваленций
Убираем одинаковые члены конъюнкции
Если дизъюнкция не содержит всех переменных, добавляем (X ∨ ¬X) для недостающих
Раскрываем скобки → получаем СКНФ

Алгоритм получения всех логических следствий из данных посылок (через СКНФ)

Исходные данные

Дано множество посылок: Γ = {A₁, A₂, …, Aₙ}

Требуется получить все высказывания B, такие что Γ ⊨ B.

Идея метода

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

Для этого используется совершенная конъюнктивная нормальная форма (СКНФ).

Алгоритм

Построить конъюнкцию посылок
Записать формулу: F = A₁ ∧ A₂ ∧ … ∧ Aₙ
Построить таблицу истинности для F
Рассмотреть все возможные наборы значений переменных.
Выделить ложные наборы
Отметить все строки таблицы, в которых F = 0.
Построить СКНФ формулы F
Для каждого ложного набора построить дизъюнкцию литералов:
переменная берётся без отрицания, если в наборе она равна 0,
и с отрицанием, если равна 1.

СКНФ — конъюнкция всех полученных дизъюнкций.
Получить все логические следствия
Каждая дизъюнкция, входящая в СКНФ, является логическим следствием Γ.

Любая формула, логически следующая из каждой дизъюнкции СКНФ, также является логическим следствием Γ.

Критерий следования

Высказывание B является логическим следствием Γ тогда и только тогда, когда формула F → B является тавтологией.

Пример

Исходная формула:

F = x ∧ (x ↔ y)

СКНФ формулы:

F = (x + y)(x + ¬y)(¬x + y)

Логические следствия:

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

Все логические следствия (7):

x + y
x + ¬y
¬x + y
(x + y)(x + ¬y)
(x + y)(¬x + y)
(x + ¬y)(¬x + y)
(x + y)(x + ¬y)(¬x + y)

Общее число следствий равно 2³ − 1 = 7, где 3 — количество дизъюнкций в СКНФ.

Получение логических следствий, содержащих заданные переменные

Постановка задачи

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

Идея метода

Следствия, содержащие только заданные переменные, получаются путём исключения остальных переменных из СКНФ конъюнкции посылок.

Алгоритм

Построить конъюнкцию посылок
F = A₁ ∧ A₂ ∧ … ∧ Aₙ
Построить СКНФ формулы F
СКНФ представляет все минимальные логические следствия.
Выбрать заданное множество переменных
Зафиксировать множество V, которое должно входить в следствия.
Исключить лишние переменные
В каждой дизъюнкции СКНФ удалить литералы, содержащие переменные, не принадлежащие множеству V.
Удалить тривиальные дизъюнкции
Если дизъюнкция стала тавтологией — удалить её.
Если дизъюнкция стала пустой — следствий с такими переменными не существует.
Получить все следствия
Все непустые конъюнкции полученных дизъюнкций являются логическими следствиями, содержащими только переменные из V.

Критерий корректности

Высказывание B, содержащее только переменные из V, является логическим следствием Γ тогда и только тогда, когда формула F → B является тавтологией.

Пример

Посылки:

¬x → y;
¬z → ¬y

Конъюнкция посылок:

F = (¬x → y) ∧ (¬z → ¬y)

Таблица истинности посылок

x	y	z	(¬x) → y	(¬z) → (¬y)
0	0	0	0	1
0	0	1	0	1
0	1	0	1	0
0	1	1	1	1
1	0	0	1	1
1	0	1	1	1
1	1	0	1	0
1	1	1	1	1

СКНФ конъюнкции:

F = (x + y + z)(x + y + ¬z)(x + ¬y + z)(¬x + ¬y + z)

Следствия, содержащие заданные переменные:

Для любого заданного множества переменных выбираются дизъюнкции СКНФ с последующим удалением литералов по алгоритму.

NAND, NOR

Есть специальные элементы: NAND или штрих Шейфера; NOR или стрелка Пирса

NAND - инверсия И (Not AND); NOR - инверсия ИЛИ (Not OR)

Эти две операции способны заменить все остальные:

NOR:

!A = A^^A
A + B = (A ^^ B) ^^ (A ^^ B)
A * B = (A ^^ A) ^^ (B ^^ B)
A -> B = ((A ^^ A) ^^ B) ^^ ((A ^^ A) ^^ B)
A <-> B = (A ^^ (B ^^ B)) ^^ (B ^^ (A ^^ A))

NAND:

!A = A'A
A + B = (A ' A) ' (B ' B)
A * B = (A ' B) ' (A ' B)
A -> B = A ' (B ' B)
A <-> B = (A ' B) ' ((A ' A) ' (B ' B))