Исчисление высказываний

Система исчисления высказываний^[3]:

• ориентирована на форму и выводимость: можно ли получить данную формулу из аксиом по правилам;
• не опирается напрямую на понятие истинности: вывод строится чисто формально;
• отвечает на вопрос: «Можно ли доказать эту формулу в данной системе?»;

Основным инструментом является последовательность формальных преобразований (доказательство).

Пример: вывод формулы A→A из аксиом с помощью правила modus ponens.

• Высказывание — повествовательное предложение, о котором можно однозначно сказать, истинно оно или ложно (в классической логике — только «1» / «истина» или «0» / «ложь»). Вопросительные, побудительные и неопределённые фразы высказываниями не являются.
• Пропозициональные переменные — обозначают целые высказывания; обычно — буквы латинского алфавита (возможно, с индексами). Пример: A, B, C, p1​, q и т. п.
• Логические операции (связки):
  • Отрицание: ¬A («не A»).
  • Конъюнкция: A∧B («A и B»).
  • Дизъюнкция: A∨B («A или B»).
  • Импликация: A→B («если A, то B»).
  • Эквиваленция: A↔B («A тогда и только тогда, когда B»).
• Пропозициональная формула — конечная последовательность символов алфавита, построенная по правилам синтаксиса.

Примеры: A, ¬A, A∧B, (A→B)∨C.

Перечисление исходных символов и правил образования формул составляет синтаксис языка. Индуктивное определение множества формул^[4]:

1. Любая пропозициональная переменная — формула.
2. Если A — формула, то ¬A — тоже формула.
3. Если A и B — формулы, то конъюнкция, дизъюнкция, импликация, эквиваленция — тоже формулы.
4. Иных формул в языке исчисления высказываний нет.

Скобки задают порядок операций; по соглашению необязательные скобки могут опускаться.

Типичная гильбертовская система аксиом (фрагмент):

• A1​:A→(B→A);
• A2​:(A→(B→C))→((A→B)→(A→C));
• A3​:A∧B→A;
• A4​:A∧B→B;
• A5​:A→(B→(A∧B));
• A9​:¬A→(A→B);
• A10​:(A→B)→((A→¬B)→¬A);
• A11​:A∨¬A (закон исключённого третьего).

Единственное правило вывода — modus ponens: BA(A→B)​.

Операция приписывания определённых значений выражениям языка называется интерпретацией. Существование интерпретации определяет семантику языка.

• Интерпретация — подстановка конкретных высказываний вместо пропозициональных переменных.
• Истинностное значение формулы определяется индуктивно с помощью таблиц истинности для связок.
• Тождественно истинная формула (тавтология) — формула, принимающая значение «истина» при любых значениях переменных.

Основные этапы работы с исчислением высказываний^[4]:

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

• Теорема адекватности (корректности)^[3]: всё, что выводимо в исчислении, является тавтологией в логике высказываний. С помощью modus ponens из истинных посылок можно получить только истинные заключения.

• Теорема полноты: всякая тавтология логики высказываний выводима в исчислении.

Эти теоремы связывают синтаксис (исчисление) и семантику (логику).

• Законы де Моргана — применяются в дискретной математике, электротехнике, физике и информатике для оптимизации цифровых схем путём замены одних логических элементов на другие. Законы де Моргана устанавливают связь между парами логических операций при помощи отрицания:
  • отрицание конъюнкции есть дизъюнкция отрицаний;
  • отрицание дизъюнкции есть конъюнкция отрицаний.
• Закон контрапозиции — строится на простом умозаключении: когда из истинности утверждения следует, что другое утверждение истинно, то при ложности этого другого утверждения первое не может быть истинным (так как в таком случае второе тоже должно быть истинным). Различают полный закон контрапозиции, прямой и обратный законы контрапозиции. На основе закона контрапозиции как общезначимого импликативного утверждения строится правило вывода, которое называется modus tollens.
• Законы поглощения:
  • дизъюнкция некой формулы А и конъюнкции этой формулы с другой формулой эквивалентна формуле А;
  • конъюнкция некой формулы А и дизъюнкции этой формулы с другой формулой эквивалентна формуле А.
• Законы дистрибутивности — дистрибутивность конъюнкции относительно дизъюнкции и дистрибутивность дизъюнкции относительно конъюнкции. Также эти законы называются распределительными.

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

Хотя понятия «логика высказываний» и «исчисление высказываний» тесно связаны и часто упоминаются совместно, между ними есть принципиальное методологическое различие^[1]. Исчисление высказываний — это формальный аппарат для записи, преобразования и доказательства логических утверждений. Оно связывает синтаксис (правила записи и вывода) с семантикой (истинность и интерпретация) через теоремы корректности и полноты.

• Логика высказываний отвечает на вопрос «Это истинно?» (через таблицы истинности). Понятие логики высказываний связано со смыслом и истинностью высказываний и их комбинаций^[4].
• Исчисление высказываний отвечает на вопрос «Это доказуемо?» (через цепочку формальных выводов). Понятие исчисления высказываний связано с формальным доказательством: как из аксиом по правилам получать новые формулы^[2].

Логика высказываний — семантическая теория, изучающая:

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

Ключевые черты логики высказываний:

• Ориентирована на значение и истинность высказываний.
• Использует таблицы истинности для анализа формул.
• Отвечает на вопрос: «При каких условиях данное высказывание истинно?»
• Основной инструмент — интерпретация формул в терминах «0» (ложь) и «1» (истина).
• Пример: анализ, будет ли формула A→(B∨¬B) тавтологией (всегда истинной).

Интерпретация'^[3]:

Исчисление высказываний интерпретируется в логике высказываний: переменным придаются значения «0»/«1», а логическим связкам — их табличные значения. Тогда:

• Аксиомы исчисления оказываются тавтологиями логики.
• Правила вывода сохраняют истинность (если посылки истинны, то и заключение истинно).

Существует установленная взаимосвязь между формулами, выводимыми в исчислении высказываний, и тавтологиями в логике высказываний. Чтобы доказать, что формула является выводимой в исчислении высказываний, достаточно показать, что она является тавтологией в логике высказываний, а для этого достаточно построить таблицу истинности и убедиться в её истинности на всех значениях пропозициональных переменных, входящих в неё. Аналогично обратное утверждение: чтобы доказать, что формула является тавтологией, достаточно показать, что она выводима в исчислении высказываний^[1].