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

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

Под высказыванием принято понимать повествовательное предложение, которое является либо истинным, либо ложным, но не тем и другим сразу (см. Высказывание). Высказывания могут быть простыми (неделимыми) или составными. Примеры простых высказываний: «4» — чётное число», «5» — нечётное число», «идёт дождь», «я прогуливаюсь». Примеры составных высказываний: «4» — чётное число и 5 — нечётное число», «если идёт дождь, то я не прогуливаюсь». В этих примерах курсивом выделены слова, связывающие высказывания для образования составных высказываний. Из последнего составного высказывания и высказывания «идёт дождь» можно заключить, что «я не прогуливаюсь»; причём это рассуждение считается правильным. Из того же составного высказывания и высказывания «я прогуливаюсь», можно вывести «не идёт дождь»; и это рассуждение считается правильным.

В естественном языке существует множество способов образования сложных высказываний из простых. Обычно выбирают пять общеизвестных грамматических связок (союзов): «не», «и», «или», «если…, то» и «если…, и только если». Процесс символизации языка логики высказываний состоит в следующем. Элементарные высказывания заменяются пропозициональными переменными p, q, r, … с индексами или без них; указанным выше грамматическим связкам ставятся в соответствие (с близким смыслом) логические связки, которые получают соответственно следующие обозначения и названия: ¬ (отрицание); ∧ или & (конъюнкция); ∨ (дизъюнкция); ⊃ (импликация) и ≡ (эквиваленция); и, наконец, используются скобки для того, чтобы можно было по-разному группировать высказывания и этим определять порядок выполнения операций. Отрицание называется одноместной связкой, а остальные четыре — двухместными связками.

Выражением языка логики высказываний называют любую последовательность указанных символов. Некоторые из этих выражений объявляются правильно построенными. Их называют формулами. Формулы определяются следующими правилами, где буквы A, B … представляют произвольные высказывания: (1) всякая пропозициональная переменная есть формула; (2) если A и B — формулы, то ¬ A, (A ∧ B), (Α ∨ B), (A ⊃ B), (Α ≡ B) тоже формулы; (3) никакие другие соединения символов не являются формулами. Примерами формул являются p, ¬ q, ¬ (p ∨ q). Внешние скобки при записи формул обычно опускают, а связки (по определению) различают по «силе связывания». Например, знак отрицания ¬ связывает сильнее, чем двухместные связки. Таким образом, правила задают эффективный способ распознавания, является ли выражение логики высказываний формулой.

Затем делают два основных допущения, на которых основывается семантика логики высказываний:

(I) Каждое простое высказывание является или только истинным, или только ложным (принцип двузначности). «Истина» и «ложь» называются истинностными значениями высказывания и обозначаются соответственно И и Л, или 1 и 0.

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

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

Приведённые выше таблицы называются истинностными таблицами, а определяемые ими пропозициональные связки — классическими связками. Легко определить, сколько имеется различных классических связок. Число различных строк в таблице длины m равно 2^m и на каждой из них значение функции можно задать двумя способами: И или Л. Поэтому число функций двузначной логики, зависящих от m аргументов, составляет 2 в степени 2^m. Отсюда, например, число одноместных связок равно 4, а число двухместных связок равно 16.

Каждая формула задаёт некоторую истинностную функцию, которая графически может быть представлена истинностной таблицей, содержащей 2^m строк, если в формуле имеется m различных пропозициональных переменных. При этом формула может быть такой, что на каждой строке она принимает только одно значение, равное И, или только одно значение, равное Л. В первом случае она называется тавтологией (тождественно истинным высказыванием), а во втором — противоречием (тождественно ложным высказыванием). В формальной логике (см. Логика формальная) тавтологии играют важную роль. Они служат для записи её законов, так как тавтологии являются всегда истинными высказываниями только в силу своей символической формы, независимо от содержания входящих в них исходных высказываний. Легко установить, что формулы вида Α ⊃ Α, Α ∨ ¬ Α, ¬ (Α ∧ ¬ Α) являются тавтологиями. Законы, выражаемые этими формулами, называются соответственно законом тождества, законом исключённого третьего и законом непротиворечия.

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

Ниже приведены некоторые общие факты о тавтологиях, настолько общие, что они называются правилами логики высказываний:

1. Правило заключения (modus ponens). Если Α и Α ⊃ B тавтологии, то B тавтология.
2. Правило подстановки. Если Α (р) есть тавтология и B — формула, то Α (B) тоже тавтология, где B замещает каждое вхождение переменной p в формуле Α, то есть подстановка в тавтологию приводит к тавтологии. Уже отсюда следует, что имеется бесконечное множество тавтологий.
3. Правило замены. Формулы Α и B называют эквивалентными, если формула Α ≡ B есть тавтология. Очевидно, что если формулы Α и B эквивалентны, то они равны как истинностные функции, то есть принимают одинаковые истинностные значения. Тогда, если Α ≡ B есть тавтология, то C (Α) ≡ C (B) тоже тавтология, где C (Α) — формула, содержащая некоторую формулу Α в качестве своей составной части, и C (B) — формула, полученная из C (Α) заменой этой составляющей Α на формулу B.

Из последнего правила следует, что можно преобразовывать формулы, получая другие, им эквивалентные, на более простые (содержащие меньше пропозициональных связок и переменных). Можно теперь любую формулу привести к какому-либо каноническому виду и этим решать определённого рода задачи. Более того, некоторые эквиваленции выражают основные свойства пропозициональных связок. Например, эквиваленции (Α ∧ B) ≡ (B ∧ Α) и (Α ∨ B) ≡ (Α ∨ B) выражают коммутативный закон конъюнкции и соответственно дизъюнкции. Все эти вопросы (и другие) изучает алгебра логики, основы которой заложены в работах Дж. Буля (1847, 1854) и А. де Моргана (1847).

Отметим некоторые эквиваленции, указывающие на взаимовыразимость одних связок через другие: Α ∧ B ≡ ¬ (¬ Α ∨ ¬ Β), Α ∨ B ≡ ¬ (¬ Α ∧ ¬ B), Α ⊃ B ≡ ¬ Α ∨ B, (Α ≡ B) ≡ (Α ⊃ B) ∧ (B ⊃ Α). Система пропозициональных связок M называется полной, если всякая формула эквивалентна некоторой формуле, в которую входят только связки из системы М, то есть посредством такой системы можно выразить все истинностные функции. Так, системы связок {¬, ∧, ∨), {¬, ∧}, {¬, ∨} и {¬, ⊃} являются полными. Это значит, что мы можем строить логику высказываний на основе любой из указанных систем связок. Оказывается, полной может быть система, состоящая только из одной связки |, которая называется «штрих Шеффера»: высказывание p|q истинно тогда и только тогда, когда неверно, что p и q оба истинны. Достаточность связки | следует из тавтологий: ¬ Α ≡ Α|Α, Α ∨ B ≡ (Α|Α) | (B|B).

Наряду с понятием тавтологии фундаментальным для логики высказываний является понятие логического следования, поскольку одной из главных задач логики является устанавливать, что из чего следует, и тем самым указывать, какие высказывания являются теоремами при заданных условиях. Всякую теорему можно записать в виде импликации и таким образом выделить её условие и заключение. Говорят, B логически следует из Α или является логическим следствием из Α, и пишут Α | = B, если в таблицах истинности для Α и B формула B имеет значение И во всех тех строках, где Α имеет значение И. Отсюда вытекает, что Α | = B тогда и только тогда, когда Α ⊃ B есть тавтология. Если формула Α тавтология, то иногда пишут | = Α. Приведённое определение логического следования без труда расширяется на некоторую систему формул (систему посылок) Α₁, … Α_n, которая обозначается посредством Г, и тогда пишут Г | = B. Примером логического следования (вывода) из посылок является уже упомянутое правило modus ponens. Выводимость B из высказываний Α и Α ⊃ B следует из того, что формула (Α ∧ (Α ⊃ B) ⊃ B является тавтологией. Следует также отметить, что в силу таблиц истинности для связки импликации получаем, что тождественно истинная формула логически следует из любой системы формул. Α из того, что имеется разрешающая процедура для тавтологий, получаем, что проблема выводимости произвольной формулы B из заданной системы посылок также разрешима.

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

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

1. p ⊃ (q ⊃ p)
2. (p ⊃ (q ⊃ r)) ⊃ (p ⊃ q) ⊃ (p ⊃ r))
3. p ⊃ (p ∨ q)
4. q ⊃ (p ∨ q)
5. (p ⊃ r) ⊃ (q ⊃ r) ⊃ (p ∨ q) ⊃ r)
6. (p ∧ q) ⊃ p
7. (p ∧ q) ⊃ q
8. (p ⊃ q) ⊃ (p ⊃ r) ⊃ (p ⊃ (q ∧ r),
9. (p ⊃ ¬ q) ⊃ (q ⊃ ¬ p)
10. p ⊃ (¬ p ⊃ q)
11. p ∨ ¬ p

Таким образом, в отличие от табличного определение логических связок ¬, ∧, ∨, ⊃ задаётся аксиоматически. Затем с помощью уже известных правил, но чисто формально осуществляется вывод — переход от высказывания или системы высказываний к высказыванию: из Α и Α ⊃ B следует B (правило заключения); из Α (p) следует Α (B) (подстановка). Так, заданную логику высказываний обозначим посредством C₂ и назовём классической.

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

Логическое исчисление, заданное посредством некоторого множества аксиом и некоторого множества правил вывода, называется исчислением гилбертовского типа. Выводом в нём называется всякая последовательность Α₁, … Α_n формул такая, что для любого i формула Α_i, есть либо аксиома, либо непосредственное следствие каких-либо предыдущих формул по одному из правил вывода. Формула Α называется теоремой, если существует вывод, в котором последней формулой является Α; такой вывод называется выводом формулы Α. Запись |– Α служит сокращением утверждения «Α есть теорема». Если формула Α выводима из некоторого множества Г исходных формул, то тогда запись принимает вид Г |– Α.

Исходя из синтаксического представления логики высказываний, последняя зачастую отождествляется с множеством теорем или, что более принято, с отношением выводимости. Итак, при семантическом подходе формулы понимаются содержательно (как функции на множестве из двух элементов И, Л), а при синтаксическом подходе формула — это определённый набор символов и различаются только теоремы и нетеоремы. Однако, несмотря на такое различие, оба подхода к построению логики высказываний по существу совпадают и, как говорят, являются адекватными. Это значит, что совпадают понятия логического следования и понятия вывода. Рассмотрим следующую примечательную теорему, которая иногда называется теоремой адекватности: для всех Α, |– Α тогда и только тогда, когда |= Α.

Доказательство в одну сторону, а именно: для всех Α, если |– Α, то |= Α носит название теоремы о корректности. Это минимальное условие, которое мы требуем от логического исчисления и которое состоит в том, что представленная нами семантика корректна для выбранной аксиоматизации. Для доказательства теоремы нужно проверить, во-первых, что все аксиомы (1)–(11) являются тавтологиями, что легко устанавливается непосредственной проверкой с помощью истинностных таблиц, и, во-вторых, что правила вывода выбраны таким образом, что они сохраняют тавтологичность. Поэтому все формулы последовательности, образующей доказательство какой-либо теоремы исчисления C₂, в том числе и сама доказуемая теорема, являются тавтологиями. Из этой теоремы следует наиболее важное свойство нашего исчисления высказываний C₂: в C₂ формулы Α и ¬ Α одновременно недоказуемы, то есть исчисление высказываний C₂ непротиворечиво. Ели бы это было не так, то (с использованием аксиомы (10) и двойным применением modus ponens) в C₂ была бы доказуема любая формула B. В силу этого противоречивая логика высказываний никакой ценности не представляет. В ней истина и ложь неразличимы и поэтому любая теорема одновременно истинна и ложна.

Имеет место и обратное утверждение о том, каждая тавтология доказуема, то есть для всех Α, если |= Α, то |– Α. Доказательство этой теоремы не столь тривиально и носит название теоремы о полноте исчисления высказываний относительно предложенной семантики. По существу здесь утверждается, что логических средств, то есть аксиом и правил вывода, исчисления высказываний C₂ вполне достаточно для доказательства всех тавтологий. Таким образом, поставленная цель достигнута: используя минимальные средства, можно обозреть всё множество тавтологий.

Имеется много различных аксиоматизаций C₂, в том числе состоящих из одной аксиомы и содержащих только одну связку (штрих Шеффера). Понятно, что чем меньше аксиом, тем сложнее доказательства. И вообще, в гилбертовских исчислениях доказательство теорем и сам поиск вывода весьма громоздок. Поэтому используются другие формулировки исчисления, более или менее приближённые к естественным рассуждениям, такие, как исчисление секвенций, исчисление натурального вывода и другие. Но соотношение между семантикой и синтаксисом здесь не столь прозрачно.

Первая аксиоматизация классической логики C₂ была предпринята Г. Фреге (1879). Однако в терминах современного символического языка аксиоматизация C₂ появилась в «Princіріа Mathematica» А. Уайтхеда и Б. Рассела (1910–1913). В обеих работах вопрос о полноте просто не возникал. Их целью было показать, что вся логика, а в действительности вся математика может быть развита внутри их системы. Первая публикация доказательства полноты принадлежит Э. Посту (1921), который исходил из системы Уайтхеда и Рассела. Ещё ранее это было сделано П. Бернайсом. В обоих случаях использовались двузначные истинностные таблицы (приведённые выше) для доказательства теоремы адекватности. В этом случае говорят ещё, что эти таблицы являются характеристическими для C₂.

Теперь можно перейти к характеризации того, что называется классической логикой высказываний:

1. C₂ основана на принципе двузначности (бивалентности). В последнее время большое развитие получили так называемые «бивалентные семантики», не только для C₂.
2. Двузначные истинностные таблицы являются характеристическими. В этом смысле классическая логика высказываний является минимальной.
3. Классическая логика высказываний является максимальной в том смысле, что она не имеет расширений: всякое добавление к ней в качестве аксиомы какой-либо формулы, не выводимой в ней, делает её противоречивой.
4. Классическая логика высказываний имеет наиболее простую семантику, которую можно только изобрести. Всё это говорит о классической логике высказываний как уникальном явлении среди всего множества логик.

Если в приведеной аксиоматизации C₂ отбросить последнюю аксиому (закон исключённого третьего), то получим аксиоматизацию пропозициональной интуиционистской логики. Оказывается, она имеет континуум расширений (В. Л. Янков, 1968) и никакие конечнозначные истинностные таблицы не являются для неё характеристическими (К. Гёдель, 1932). Есть логики, которые имеют только одно расширение, то есть саму C₂.

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

Следует отметить широкое применение алгебраических методов для решения различных задач логики высказываний. Это становится возможным прежде всего с истолкованием логики высказываний как некоторой структуры (в смысле алгебраической «теории структур»). Так, дистрибутивная структура с дополнениями (булевы алгебры) соответствует классической логике высказываний, а импликативная структура, где импликация является некоторым аналогом деления, если конъюнкция трактуется как умножение (псевдобулевы алгебры или алгебры Гейтинга), соответствует интуиционистской логике высказываний. Кроме того, в основе приложений булевой алгебры к логике лежит интерпретация элементов булевой алгебры как высказываний.

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