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

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

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

Объяснение

Логические связки встречаются в естественных языках. Например, в английском языке несколько примеров: «и» (соединение ), "или же" (дизъюнкция ), "нет" (отрицание ) и «если» (но только когда используется для обозначения материальный условный ).

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

Предпосылка 1. Если идет дождь, значит облачно.

Предпосылка 2: идет дождь.

Вывод: облачно.

И посылки, и заключение суть предложения. Помещение считается само собой разумеющимся, и с применением modus ponens (ан правило вывода ), следует вывод.

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

Предпосылка 1: ${displaystyle P o Q}$

Предпосылка 2: ${displaystyle P}$

Вывод: ${displaystyle Q}$

Об этом же можно кратко заявить следующим образом:

${displaystyle P o Q, Pvdash Q}$

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

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

Когда формальная система используется для представления формальной логики, только буквы утверждения (обычно заглавные латинские буквы, такие как ${displaystyle P}$, ${displaystyle Q}$ и ${displaystyle R}$^[1]) представлены напрямую. Предложения естественного языка, возникающие при их интерпретации, выходят за рамки системы, и отношения между формальной системой и ее интерпретацией также находятся вне самой формальной системы.

В классическом истинностно-функциональная логика высказываний, формулы интерпретируются как имеющие ровно одну из двух возможных ценности истины, значение истинности истинный или истинное значение ложный.^[2] В принцип двухвалентности и закон исключенного среднего поддерживаются. Истинно-функциональная логика высказываний, определяемая как таковая, и системы изоморфный к нему считаются логика нулевого порядка. Однако возможны и альтернативные логики высказываний. Подробнее см. Другие логические исчисления ниже.

История

Хотя на логику высказываний (которая взаимозаменяема с исчислением высказываний) намекали более ранние философы, она превратилась в формальную логику (Стоическая логика ) к Хрисипп в 3 веке до нашей эры^[3] и расширен его преемником Стоики. Логика была сосредоточена на предложения. Это продвижение отличалось от традиционного силлогистическая логика, который был сосредоточен на термины. Однако большинство оригинальных произведений было утеряно.^[4] а логика высказываний, разработанная стоиками, перестала быть понятой позже в античности,^{[ВОЗ? ]}. Следовательно, система была по существу заново изобретена Питер Абеляр в 12 веке.^[5]

В конечном итоге логика высказываний была усовершенствована с использованием символическая логика. Математик 17-18 веков Готфрид Лейбниц считается основоположником символической логики за его работу с логический расчет. Хотя его работа была первой в своем роде, она была неизвестна большему сообществу логиков. Следовательно, многие достижения Лейбница были воссозданы такими логиками, как Джордж Буль и Огастес Де Морган - полностью независимый от Лейбница.^[6]

Подобно тому, как логику высказываний можно рассматривать как продвижение по сравнению с более ранней силлогистической логикой, Готтлоб Фреге логика предикатов можно также рассматривать как развитие более ранней логики высказываний. Один автор описывает логику предикатов как сочетание «отличительных черт силлогистической логики и логики высказываний».^[7] Следовательно, логика предикатов открыла новую эру в истории логики; однако успехи в логике высказываний все же были достигнуты после Фреге, включая естественный вычет, деревья правды и таблицы истинности. Естественная дедукция была изобретена Герхард Гентцен и Ян Лукасевич. Деревья правды были изобретены Эверт Виллем Бет.^[8] Однако изобретение таблиц истинности не имеет достоверной атрибуции.

В произведениях Фреге^[9] и Бертран Рассел,^[10] идеи, которые повлияли на изобретение таблиц истинности. Фактическая табличная структура (отформатированная как таблица) обычно приписывается либо Людвиг Витгенштейн или же Эмиль Пост (или оба, независимо).^[9] Помимо Фреге и Рассела, другие, которым приписывают идеи, предшествующие таблицам истинности, включают Филона, Буля, Чарльз Сандерс Пирс,^[11] и Эрнст Шредер. Другие приписывают табличную структуру: Ян Лукасевич, Эрнст Шредер, Альфред Норт Уайтхед, Уильям Стэнли Джевонс, Джон Венн, и Кларенс Ирвинг Льюис.^[10] В конце концов, некоторые пришли к выводу, например, Джон Шоски, что «далеко не ясно, что любому человеку следует присвоить звание« изобретателя »таблиц истинности».^[10]

Терминология

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

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

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

В язык исчисления высказываний состоит из

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

А правильно сформированная формула - это любая атомарная формула или любая формула, которая может быть построена из атомарных формул с помощью символов операторов в соответствии с правилами грамматики.

Математики иногда различают пропозициональные константы, пропозициональные переменные и схемы. Пропозициональные константы представляют собой какое-то конкретное предложение, в то время как пропозициональные переменные охватывают множество всех атомарных предложений. Схемы, однако, охватывают все предложения. Обычно пропозициональные константы представляют как А, B, и C, пропозициональные переменные п, Q, и р,^[1] и схематические буквы часто бывают греческими буквами, чаще всего φ, ψ, и χ.

Базовые концепты

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

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

Любое данное утверждение может быть представлено буквой, называемой «пропозициональной константой», аналогично представлению числа буквой в математике (например, а = 5). Все предложения требуют ровно одного из двух истинностных значений: истинного или ложного. Например, пусть п предположение, что на улице идет дождь. Это будет правда (п), если на улице идет дождь, и false в противном случае (¬п).

• Затем мы определяем истинно-функциональный операторы, начиная с отрицания. ¬п представляет собой отрицание п,^[1] что можно рассматривать как отрицание п. В приведенном выше примере ¬п выражает, что на улице нет дождя, или в более стандартном прочтении: «Это не тот случай, когда на улице идет дождь». Когда п правда, ¬п ложно; и когда п ложно, ¬п правда. Как результат, ¬ ¬п всегда имеет ту же истинностную ценность, что и п.
• Конъюнкция - это функциональная связка истинности, которая формирует предложение из двух более простых предложений, например, п и Q. Соединение п и Q написано п ∧ Q,^[1] и заявляет, что все они верны. Мы читаем п ∧ Q в качестве "п и Q". Для любых двух предложений существует четыре возможных присвоения значений истинности:
  1. п правда и Q правда
  2. п правда и Q ложно
  3. п ложно и Q правда
  4. п ложно и Q ложно

Соединение п и Q верно в случае 1 и ложно в противном случае. Где п это утверждение, что на улице идет дождь и Q это утверждение, что холодный фронт над Канзасом, п ∧ Q правда, когда на улице идет дождь и над Канзасом холодный фронт. Если на улице не идет дождь, то P ∧ Q ложно; и если над Канзасом не будет холодного фронта, тогда п ∧ Q также ложно.

• Дизъюнкция похожа на конъюнкцию в том смысле, что она формирует предложение из двух более простых предложений. Мы пишем это п ∨ Q,^[1] и читается "п или же Q". В нем говорится, что либо п или же Q правда. Таким образом, в перечисленных выше случаях дизъюнкция п с Q верно во всех случаях, кроме случая 4. Используя приведенный выше пример, дизъюнкция выражает, что либо на улице идет дождь, либо над Канзасом есть холодный фронт. (Обратите внимание, это использование дизъюнкции должно напоминать использование английского слова «или». Однако оно больше всего похоже на английское включающий «или», которое может быть использовано для выражения истинности по крайней мере одного из двух предложений. Это не похоже на английский эксклюзивный «или», которое выражает истинность ровно одного из двух предложений. Другими словами, исключающее "или" ложно, когда оба п и Q верны (случай 1). Пример эксклюзивного или: у вас может быть рогалик или печенье, но не то и другое вместе. Часто в естественном языке в соответствующем контексте добавление «но не то и другое одновременно» опускается, но подразумевается. Однако в математике «или» всегда включает или; если имеется в виду исключающий или, он будет указан, возможно, с помощью "xor".)
• Условное материальное условие также объединяет два более простых предложения, и мы пишем п → Q,^[1] который читается "если п тогда QПредложение слева от стрелки называется антецедентом, а предложение справа - консеквентом. (Для конъюнкции или дизъюнкции такого обозначения нет, поскольку они являются коммутативными операциями.) Оно выражает, что Q верно всякий раз, когда п правда. Таким образом п → Q верно во всех приведенных выше случаях, кроме случая 2, потому что это единственный случай, когда п правда, но Q не является. Используя пример, если п тогда Q говорит, что если на улице идет дождь, значит, над Канзасом холодный фронт. Материальную обусловленность часто путают с физической причинностью. Однако материальное условие связывает только два предложения посредством их истинностных ценностей, что не является отношением причины и следствия. Это спорное в литературе, представляет ли материал Подразумевается логической причинно-следственная связь.
• Biconditional объединяет два более простых предложения, и мы пишем п ↔ Q,^[1] который читается "п если и только если Q". Он выражает п и Q имеют одинаковую истинностную ценность и в случаях 1 и 4. »п верно тогда и только тогда, когда Q'истинно, в противном случае - ложно.

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

Закрытие под операциями

Логика высказываний закрывается связками, функционирующими по истине. То есть для любого предложения φ, ¬φ тоже предложение. Точно так же для любых предложений φ и ψ, φ ∧ ψ - предложение, а также для дизъюнктивных, условных и биконусных. Это означает, например, что φ ∧ ψ является предложением, поэтому его можно соединить с другим предложением. Чтобы представить это, нам нужно использовать круглые скобки, чтобы указать, какое утверждение с каким связано. Например, п ∧ Q ∧ р не является правильной формулой, потому что мы не знаем, соединяем ли мы п ∧ Q с р или если мы соединяемся п с Q ∧ р. Таким образом, мы должны написать либо (п ∧ Q) ∧ р представлять первых, или п ∧ (Q ∧ р) представлять последнее. Оценивая условия истинности, мы видим, что оба выражения имеют одинаковые условия истинности (будут истинными в одних и тех же случаях), и, более того, любое предложение, сформированное произвольными союзами, будет иметь одинаковые условия истинности, независимо от расположения скобок. Это означает, что союз ассоциативен, однако не следует полагать, что скобки никогда не служат цели. Например, предложение п ∧ (Q ∨ р) не имеет тех же условий истинности (п ∧ Q) ∨ р, поэтому это разные предложения, которые различаются только скобками. В этом можно убедиться с помощью упомянутого выше метода таблицы истинности.

Примечание: для любого произвольного числа пропозициональных констант мы можем сформировать конечное число случаев, в которых перечислены их возможные значения истинности. Простой способ создать это - таблицы истинности, в которых пишут п, Q, ..., Z, для любого списка k пропозициональные константы - то есть любой список пропозициональных констант с k записи. Ниже этого списка пишется 2^k строк и ниже п один заполняет первую половину строк значением true (или T), а вторую половину - false (или F). Ниже Q заполняется четверть строк с помощью T, затем четверть с помощью F, затем четверть с T и последняя четверть с F. Следующий столбец чередуется между истинным и ложным для каждой восьмой строки, затем шестнадцатым, и так далее, пока последняя пропозициональная константа не будет меняться от T до F для каждой строки. Это даст полный список случаев или присвоений истинностных значений, возможных для этих пропозициональных констант.

Аргумент

Затем исчисление высказываний определяет аргумент быть списком предложений. Действительный аргумент - это список предложений, последнее из которых следует из остальных или подразумевается ими. Все остальные аргументы недействительны. Самый простой верный аргумент - modus ponens, одним из примеров которых является следующий список предложений:

${displaystyle {egin {array} {rl} 1. & P o Q 2. & P hline здесь & Qend {array}}}$

Это список из трех предложений, каждая строка - это предложение, а последнее следует из остальных. Первые две строки называются предпосылками, а последняя строка - заключением. Мы говорим, что любое предложение C следует из любого набора предложений ${displaystyle (P_ {1}, ..., P_ {n})}$, если C должно быть истинным всякий раз, когда каждый член набора ${displaystyle (P_ {1}, ..., P_ {n})}$ правда. В приведенном выше аргументе для любого п и Q, в любое время п → Q и п верны, обязательно Q правда. Обратите внимание, когда п верно, мы не можем рассматривать случаи 3 и 4 (из таблицы истинности). Когда п → Q верно, мы не можем рассматривать случай 2. Остается только случай 1, в котором Q тоже верно. Таким образом Q подразумевается помещением.

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

${displaystyle {egin {array} {rl} 1. & varphi o psi 2. & varphi hline herefore & psi end {array}}}$

Другие формы аргументов удобны, но не обязательны. Учитывая полный набор аксиом (один из таких наборов см. Ниже), modus ponens достаточно для доказательства всех других форм аргументов в логике высказываний, поэтому их можно рассматривать как производные. Обратите внимание: это неверно в отношении расширения логики высказываний на другие логики, такие как логика первого порядка. Логика первого порядка требует, по крайней мере, одного дополнительного правила вывода, чтобы получить полнота.

Значение аргумента в формальной логике состоит в том, что можно получить новые истины из установленных истин. В первом примере выше, учитывая две предпосылки, истинность Q еще не известно и не заявлено. После аргументации Q выводится. Таким образом, мы определяем систему дедукции как набор всех предложений, которые могут быть выведены из другого набора предложений. Например, учитывая набор предложений ${displaystyle A = {Plor Q, например, Qland R, (Plor Q) o R}}$, мы можем определить систему дедукции, Γ, который представляет собой набор всех предложений, следующих из А. Повторение всегда предполагается, поэтому ${displaystyle Plor Q, например Qland R, (Plor Q) o Rin Gamma}$. Также из первого элемента А, последний элемент, а также modus ponens, р это следствие, и поэтому ${displaystyle Rin Gamma}$. Однако, поскольку мы не включили достаточно полные аксиомы, ничего другого сделать нельзя. Таким образом, несмотря на то, что большинство систем дедукции, изучаемых в логике высказываний, способны вывести ${displaystyle (Plor Q) leftrightarrow (например, P o Q)}$, это слишком слабо, чтобы доказывать такое предложение.

Общее описание исчисления высказываний

А пропозициональное исчисление это формальная система ${displaystyle {mathcal {L}} = {mathcal {L}} left (mathrm {A}, Omega, mathrm {Z}, mathrm {I} ight)}$, куда:

Пример 1. Простая система аксиом.

Позволять ${displaystyle {mathcal {L}} _ {1} = {mathcal {L}} (mathrm {A}, Omega, mathrm {Z}, mathrm {I})}$, куда ${displaystyle mathrm {A}}$, ${displaystyle Omega}$, ${displaystyle mathrm {Z}}$, ${displaystyle mathrm {I}}$ определяются следующим образом:

• Альфа-набор ${displaystyle mathrm {A}}$, представляет собой счетное бесконечное множество символов, например:

  ${displaystyle mathrm {A} = {p, q, r, s, t, u, p_ {2}, ldots}.}$

• Из трех связок для соединения, дизъюнкции и импликации (${displaystyle wedge, lor}$, и →), один можно считать примитивным, а два других можно определить в терминах него и отрицания (¬).^[12] Действительно, все логические связки можно определить в терминах единственный достаточный оператор. Двуусловный (↔), конечно, можно определить в терминах соединения и импликации, с ${displaystyle aleftrightarrow b}$ определяется как ${displaystyle (a o b) land (b o a)}$.
  Принятие отрицания и импликации как двух примитивных операций в исчислении высказываний равносильно наличию омега-множества. ${displaystyle Omega = Omega _ {1} чашка Omega _ {2}}$ разделить следующим образом:

  ${displaystyle Omega _ {1} = {lnot},}$

  ${displaystyle Omega _ {2} = {o}.}$

• Система аксиом, предложенная Ян Лукасевич, и используется как часть исчисления высказываний Система гильберта, формулирует исчисление высказываний на этом языке следующим образом. Все аксиомы экземпляры замены из:
  • ${displaystyle (p o (q o p))}$
  • ${displaystyle ((p o (q o r)) o ((p o q) o (p o r)))}$
  • ${displaystyle ((например, p o eg q) o (q o p))}$
• Правило вывода: modus ponens (т.е. из п и ${displaystyle (p o q)}$, сделать вывод q). потом ${displaystyle alor b}$ определяется как ${displaystyle например a o b}$, и ${displaystyle aland b}$ определяется как ${displaystyle eg (a o eg b)}$. Эта система используется в Метамат set.mm формальная база данных доказательств.

Пример 2. Система естественного вычета.

Позволять ${displaystyle {mathcal {L}} _ {2} = {mathcal {L}} (mathrm {A}, Omega, mathrm {Z}, mathrm {I})}$, куда ${displaystyle mathrm {A}}$, ${displaystyle Omega}$, ${displaystyle mathrm {Z}}$, ${displaystyle mathrm {I}}$ определяются следующим образом:

• Альфа-набор ${displaystyle mathrm {A}}$, представляет собой счетное бесконечное множество символов, например:

  ${displaystyle mathrm {A} = {p, q, r, s, t, u, p_ {2}, ldots}.}$

• Набор омега ${displaystyle Omega = Omega _ {1} чашка Omega _ {2}}$ перегородки следующим образом:

  ${displaystyle Omega _ {1} = {lnot},}$

  ${displaystyle Omega _ {2} = {land, lor, o, leftrightarrow}.}$

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

• Набор начальных точек пуст, то есть ${displaystyle mathrm {I} = varnothing}$.
• Набор правил преобразования, ${displaystyle mathrm {Z}}$, описывается следующим образом:

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

При описании правил трансформации мы можем ввести символ метаязыка ${displaystyle vdash}$. По сути, это удобное сокращение для выражения «сделай вывод». Формат ${displaystyle Gamma vdash psi}$, в котором Γ представляет собой (возможно, пустой) набор формул, называемых предпосылками, и ψ это формула, называемая выводом. Правило трансформации ${displaystyle Gamma vdash psi}$ означает, что если каждое предложение в Γ является теоремой (или имеет то же значение истинности, что и аксиомы), то ψ это тоже теорема. Обратите внимание, что учитывая следующее правило Введение в соединение, мы узнаем, когда Γ имеет более одной формулы, мы всегда можем безопасно свести ее в одну формулу с помощью конъюнкции. Короче говоря, с тех пор мы можем представлять Γ как одна формула вместо набора. Еще одно упущение для удобства - когда Γ - пустой набор, и в этом случае Γ может не появиться.

Введение отрицания

Из ${displaystyle (p o q)}$ и ${displaystyle (p o eg q)}$, сделать вывод ${displaystyle например, p}$.

То есть, ${displaystyle {(p o q), (p o eg q)} vdash, например, p}$.

Устранение отрицания

Из ${displaystyle например, p}$, сделать вывод ${displaystyle (p o r)}$.

То есть, ${displaystyle {например, p} vdash (p o r)}$.

Устранение двойного отрицания

Из ${displaystyle например, например, p}$, сделать вывод п.

То есть, ${displaystyle например, например, pvdash p}$.

Введение в соединение

Из п и q, сделать вывод ${displaystyle (pland q)}$.

То есть, ${displaystyle {p, q} vdash (pland q)}$.

Устранение конъюнкции

Из ${displaystyle (pland q)}$, сделать вывод п.

Из ${displaystyle (pland q)}$, сделать вывод q.

То есть, ${displaystyle (pland q) vdash p}$ и ${displaystyle (pland q) vdash q}$.

Введение дизъюнкции

Из п, сделать вывод ${displaystyle (plor q)}$.

Из q, сделать вывод ${displaystyle (plor q)}$.

То есть, ${displaystyle pvdash (plor q)}$ и ${displaystyle qvdash (plor q)}$.

Устранение дизъюнкции

Из ${displaystyle (plor q)}$ и ${displaystyle (p o r)}$ и ${displaystyle (q or r)}$, сделать вывод р.

То есть, ${displaystyle {plor q, p o r, q or r} vdash r}$.

Двузначное введение

Из ${displaystyle (p o q)}$ и ${displaystyle (q o p)}$, сделать вывод ${displaystyle (pleftrightarrow q)}$.

То есть, ${displaystyle {p o q, q o p} vdash (стрелка вправо q)}$.

Двуусловное исключение

Из ${displaystyle (pleftrightarrow q)}$, сделать вывод ${displaystyle (p o q)}$.

Из ${displaystyle (pleftrightarrow q)}$, сделать вывод ${displaystyle (q o p)}$.

То есть, ${displaystyle (pleftrightarrow q) vdash (p o q)}$ и ${displaystyle (pleftrightarrow q) vdash (q o p)}$.

Modus ponens (условное исключение)

Из п и ${displaystyle (p o q)}$, сделать вывод q.

То есть, ${displaystyle {p, p o q} vdash q}$.

Условное доказательство (условное введение)

От [принятия п позволяет доказательство q], сделать вывод ${displaystyle (p o q)}$.

То есть, ${displaystyle (pvdash q) vdash (p o q)}$.

Основные и производные формы аргументов

Имя	Секвент	Описание
Modus Ponens	${displaystyle ((p o q) land p) vdash q}$	Если п тогда q; п; следовательно q
Modus Tollens	${displaystyle ((p o q) земля, например, q) vdash, например, p}$	Если п тогда q; нет q; поэтому не п
Гипотетический силлогизм	${displaystyle ((p o q) land (q o r)) vdash (p o r)}$	Если п тогда q; если q тогда р; следовательно, если п тогда р
Дизъюнктивный силлогизм	${displaystyle ((plor q) land eg p) vdash q}$	Либо п или же q, или оба; нет п; следовательно, q
Конструктивная дилемма	${displaystyle ((p o q) land (r o s) land (plor r)) vdash (qlor s)}$	Если п тогда q; и если р тогда s; но п или же р; следовательно q или же s
Разрушительная дилемма	${displaystyle ((p o q) land (r o s) land (например, qlor eg s)) vdash (например, plor eg r)}$	Если п тогда q; и если р тогда s; но нет q или нет s; поэтому не п или нет р
Двунаправленная дилемма	${displaystyle ((p o q) земля (r o s) land (plor eg s)) vdash (qlor eg r)}$	Если п тогда q; и если р тогда s; но п или нет s; следовательно q или нет р
Упрощение	${displaystyle (pland q) vdash p}$	п и q верны; следовательно п правда
Соединение	${displaystyle p, qvdash (pland q)}$	п и q верны отдельно; следовательно, они верны вместе
Добавление	${displaystyle pvdash (plor q)}$	п правда; поэтому дизъюнкция (п или же q) правда
Сочинение	${displaystyle ((p o q) земля (p o r)) vdash (p o (qland r))}$	Если п тогда q; и если п тогда р; поэтому если п верно тогда q и р правда
Теорема де Моргана (1)	${displaystyle например (pland q) vdash (например, plor eg q)}$	Отрицание (п и q) эквивалентно. к (не п или нет q)
Теорема де Моргана (2)	${displaystyle например (plor q) vdash (например, pland eg q)}$	Отрицание (п или же q) эквивалентно. к (не п и нет q)
Коммутация (1)	${displaystyle (plor q) vdash (qlor p)}$	(п или же q) эквивалентно. к (q или же п)
Коммутация (2)	${displaystyle (pland q) vdash (qland p)}$	(п и q) эквивалентно. к (q и п)
Коммутация (3)	${displaystyle (pleftrightarrow q) vdash (qleftrightarrow p)}$	(п эквивалентно к q) эквивалентно. к (q эквивалентно к п)
Ассоциация (1)	${displaystyle (plor (qlor r)) vdash ((plor q) lor r)}$	п или же (q или же р) эквивалентно. к (п или же q) или же р
Ассоциация (2)	${displaystyle (pland (qland r)) vdash ((pland q) land r)}$	п и (q и р) эквивалентно. к (п и q) и р
Распределение (1)	${displaystyle (pland (qlor r)) vdash ((pland q) lor (pland r))}$	п и (q или же р) эквивалентно. к (п и q) или же (п и р)
Распределение (2)	${displaystyle (plor (qland r)) vdash ((plor q) land (plor r))}$	п или же (q и р) эквивалентно. к (п или же q) и (п или же р)
Двойное отрицание	${displaystyle pvdash, например, например, p}$ и ${displaystyle например, например, pvdash p}$	п эквивалентно отрицанию not п
Транспозиция	${displaystyle (p o q) vdash (например, q o eg p)}$	Если п тогда q эквивалентно если нет q тогда не п
Материальное значение	${displaystyle (p o q) vdash (например, plor q)}$	Если п тогда q эквивалентно не п или же q
Материальная эквивалентность (1)	${displaystyle (pleftrightarrow q) vdash ((p o q) land (q o p))}$	(п если только q) эквивалентно. к (если п верно тогда q верно) и (если q верно тогда п правда)
Материальная эквивалентность (2)	${displaystyle (pleftrightarrow q) vdash ((pland q) lor (например, pland eg q))}$	(п если только q) эквивалентно. либо (п и q верны) или (оба п и q ложны)
Материальная эквивалентность (3)	${displaystyle (pleftrightarrow q) vdash ((plor eg q) land (например, plor q))}$	(п если только q) эквивалентно., оба (п или нет q верно) и (не п или же q правда)
Экспорт[13]	${displaystyle ((pland q) or r) vdash (p o (q or r))}$	от (если п и q правда тогда р верно) мы можем доказать (если q верно тогда р верно, если п правда)
Импорт	${displaystyle (p o (q o r)) vdash ((pland q) o r)}$	Если п тогда (если q тогда р) эквивалентно if п и q тогда р
Тавтология (1)	${displaystyle pvdash (plor p)}$	п верно эквивалентно. к п правда или п правда
Тавтология (2)	${displaystyle pvdash (pland p)}$	п верно эквивалентно. к п правда и п правда
Tertium non datur (Закон исключенного среднего)	${displaystyle vdash (plor eg p)}$	п или нет п правда
Закон непротиворечия	${displaystyle vdash eg (pland eg p)}$	п и нет п ложно, это истинное утверждение

Доказательства в исчислении высказываний

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

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

Пример доказательства в системе естественного вывода

• Чтобы показать, что А → А.
• Одно возможное доказательство этого (которое, хотя и верно, но содержит больше шагов, чем необходимо) может быть представлено следующим образом:

Пример доказательства

Число	Формула	Причина
1	${displaystyle A}$	предпосылка
2	${displaystyle Alor A}$	Из (1) введением дизъюнкции
3	${displaystyle (Alor A) land A}$	Из (1) и (2) путем введения союзов
4	${displaystyle A}$	Из (3) путем исключения конъюнкции
5	${displaystyle Avdash A}$	Резюме (1) через (4)
6	${displaystyle vdash A o A}$	Из (5) условным доказательством

Интерпретировать ${displaystyle Avdash A}$ как "предполагая А, сделать вывод А". Читать ${displaystyle vdash A o A}$ как "Ничего не предполагая, сделайте вывод, что А подразумевает А"или" Это тавтология, А подразумевает А"или" Это всегда правда, что А подразумевает А".

Пример доказательства в классической системе исчисления высказываний

Докажем теперь ту же теорему ${displaystyle A o A}$ в аксиоматической системе Ян Лукасевич описанный выше, который является примером классические системы исчисления высказываний, или Дедуктивная система Гильберта для исчисления высказываний.

Аксиомы следующие:

(A1) ${displaystyle (p o (q o p))}$

(A2) ${displaystyle ((p o (q o r)) o ((p o q) o (p o r)))}$

(A3) ${displaystyle ((например, p o eg q) o (q o p))}$

И доказательство таково:

1. ${displaystyle A o ((B o A) o A)}$ (пример (A1))
2. ${displaystyle (A o ((B o A) o A)) o ((A o (B o A)) o (A o A))}$ (пример (A2))
3. ${displaystyle (A o (B o A)) o (A o A)}$ (из (1) и (2) по modus ponens )
4. ${displaystyle A o (B o A)}$ (пример (A1))
5. ${displaystyle A o A}$ (из (4) и (3) по modus ponens)

Обоснованность и полнота правил

Важнейшие свойства этого набора правил заключаются в том, что они звук и полный. Неформально это означает, что правила верны и никаких других правил не требуется. Эти утверждения могут быть сделаны более формальными следующим образом. Обратите внимание, что доказательства правильности и полноты логики высказываний сами по себе не являются доказательствами логики высказываний; это теоремы в ZFC используется как метатеория доказать свойства логики высказываний.

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

Мы определяем, когда такое назначение истинности А удовлетворяет определенный правильно сформированная формула со следующими правилами:

• А удовлетворяет пропозициональной переменной п если и только если А(п) = правда
• А удовлетворяет ¬φ если и только если А не удовлетворяет φ
• А удовлетворяет (φ ∧ ψ) если и только если А удовлетворяет оба φ и ψ
• А удовлетворяет (φ ∨ ψ) если и только если А удовлетворяет хотя бы одному из φ или же ψ
• А удовлетворяет (φ → ψ) тогда и только тогда, когда это не так, А удовлетворяет φ но нет ψ
• А удовлетворяет (φ ↔ ψ) если и только если А удовлетворяет оба φ и ψ или не удовлетворяет ни одного из них

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

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

Прочность: Если набор правильных формул S синтаксически влечет правильную формулу φ тогда S семантически влечет за собой φ.

Полнота: Если набор правильных формул S семантически влечет правильную формулу φ тогда S синтаксически влечет за собой φ.

Для приведенного выше набора правил это действительно так.

Эскиз доказательства прочности

(Для большинства логические системы, это сравнительно "простое" направление доказательства)

Условные обозначения: Пусть грамм быть переменной, охватывающей наборы предложений. Позволять А, Б и C диапазон предложений. За "грамм синтаксически влечет А" мы пишем "грамм доказывает А". За "грамм семантически влечет А" мы пишем "грамм подразумевает А".

Мы хотим показать: (А)(грамм) (если грамм доказывает А, тогда грамм подразумевает А).

Отметим, что "грамм доказывает А"имеет индуктивное определение, и это дает нам непосредственные ресурсы для демонстрации утверждений формы" Если грамм доказывает А, то ... ". Итак, наше доказательство проводится по индукции.

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

Базовые шаги демонстрируют, что простейшие доказуемые предложения из грамм также подразумеваются грамм, для любого грамм. (Доказательство простое, поскольку семантический факт, что набор подразумевает любой из его членов, также тривиален.) Индуктивный шаг будет систематически охватывать все дальнейшие предложения, которые могут быть доказаны, - рассматривая каждый случай, в котором мы могли бы прийти к логическому заключению. используя правило вывода - и показывает, что если новое предложение доказуемо, оно также подразумевается логически. (Например, у нас может быть правило, говорящее нам, что от "А"мы можем получить"А или же B". В III.a мы предполагаем, что если А доказуемо подразумевается. Мы также знаем, что если А тогда доказуемо "А или же B"доказуемо. Тогда мы должны это показать"А или же B"тоже подразумевается. Мы делаем это, обращаясь к семантическому определению и сделанному предположению. А можно доказать из грамм, мы предполагаем. Так что это также подразумевается грамм. Таким образом, любая семантическая оценка, делающая все грамм правда делает А истинный. Но любая оценка А правда делает "А или же B"истина, в соответствии с определенной семантикой для" или ". Таким образом, любая оценка, которая делает все грамм правда делает "А или же B"правда. Итак"А или же B"подразумевается.) Как правило, индуктивный шаг будет состоять из длинных, но простых индивидуальный анализ всех правил вывода, показывая, что каждое «сохраняет» семантическую импликацию.

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

Эскиз доказательства полноты

(Обычно это гораздо более сложное направление доказательства.)

Мы принимаем те же обозначения, что и выше.

Мы хотим показать: если грамм подразумевает А, тогда грамм доказывает А. Мы продолжаем противопоставление: Вместо этого мы показываем, что если грамм делает нет доказывать А тогда грамм делает нет подразумевать А. Если мы покажем, что существует модель куда А не держится, несмотря на грамм если правда, то очевидно грамм не подразумевает А. Идея состоит в том, чтобы построить такую ​​модель, исходя из самого нашего предположения, что грамм не доказывает А.

Таким образом, каждая система, которая имеет modus ponens в качестве правила вывода и доказывает следующие теоремы (включая их подстановки), является полной:

• р → (¬p → д)
• (p → q) → ((¬p → q) → q)
• р → (д → (р → д))
• p → (¬q → ¬ (p → q))
• ¬p → (p → q)
• р → р
• р → (д → р)
• (p → (q → r)) → ((p → q) → (p → r))

Первые пять используются для выполнения пяти условий на этапе III выше, а последние три - для доказательства теоремы дедукции.

Пример

В качестве примера можно показать, что, как и любая другая тавтология, три аксиомы классической системы исчисления высказываний, описанной ранее, могут быть доказаны в любой системе, которая удовлетворяет вышеизложенному, а именно, которая имеет modus ponens в качестве правила вывода, и доказывает вышесказанное. восемь теорем (включая их подстановки). В самом деле, из восьми теорем последние две являются двумя из трех аксиом; третья аксиома, ${стиль отображения (например, q o eg p) o (p o q)}$, также может быть доказано, как мы сейчас покажем.

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

1. ${displaystyle q o (p o q)}$ (пример 7-й теоремы)
2. ${displaystyle (q o (p o q)) o ((например, q o eg p) o (q o (p o q)))}$ (пример 7-й теоремы)
3. ${стиль отображения (например, q o eg p) o (q o (p o q))}$ (из (1) и (2) по modus ponens)
4. ${displaystyle (например, p o (p o q)) o ((например, q o eg p) o (например, q o (p o q)))}$ (пример теоремы о гипотетическом силлогизме)
5. ${displaystyle (например, p o (p o q))}$ (пример 5-й теоремы)
6. ${стиль отображения (например, q o eg p) o (например, q o (p o q))}$ (из (5) и (4) по modus ponens)
7. ${displaystyle (q o (p o q)) o ((например, q o (p o q)) o (p o q))}$ (пример 2-й теоремы)
8. ${displaystyle ((q o (p oq)) o ((например, q o (p oq)) o (p oq))) o ((например, q o eg p) o ((q o (p oq)) o ( (например, q o (p oq)) o (p oq))))}$ (пример 7-й теоремы)
9. ${displaystyle (например, q o eg p) o ((q o (p o q)) o ((например, q o (p o q)) o (p o q)))}$ (из (7) и (8) по modus ponens)
10. ${displaystyle ((например, q o eg p) o ((q o (p o q)) o ((например, q o (p o q)) o (p o q)))) o}$

    ${displaystyle (((например, q o eg p) o (q o (p o q))) o ((например, q o eg p) o ((например, q o (p o q)) o (p o q))))}$ (пример 8-й теоремы)

11. ${displaystyle ((например, q o eg p) o (q o (p o q))) o ((например, q o eg p) o ((например, q o (p o q)) o (p o q)))}$ (из (9) и (10) по modus ponens)
12. ${стиль отображения (например, q o eg p) o ((например, q o (p o q)) o (p o q))}$ (из (3) и (11) по modus ponens)
13. ${displaystyle ((например, q o eg p) o ((например, q o (p oq)) o (p oq))) o (((например, q o eg p) o (например, q o (p oq))) o ((например, q o eg p) o (p oq)))}$ (пример 8-й теоремы)
14. ${displaystyle ((например, q o eg p) o (например, q o (p o q))) o ((например, q o eg p) o (p o q))}$ (из (12) и (13) по modus ponens)
15. ${стиль отображения (например, q o eg p) o (p o q)}$ (из (6) и (14) по modus ponens)

Проверка полноты классической системы исчисления высказываний

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

(DN1) ${displaystyle, например, например, p o p}$ - Двойное отрицание (Одно направление)

(DN2) ${displaystyle p o eg например p}$ - Двойное отрицание (другое направление)

(HS1) ${displaystyle (q o r) o ((p o q) o (p o r))}$ - одна форма Гипотетический силлогизм

(HS2) ${displaystyle (p o q) o ((q o r) o (p o r))}$ - другая форма гипотетического силлогизма

(TR1) ${displaystyle (p o q) o (например, q o eg p)}$ - Транспозиция

(TR2) ${стиль отображения (например, p o q) o (например, q o p)}$ - другая форма перестановки.

(L1) ${displaystyle p o ((p o q) o q)}$

(L3) ${displaystyle (например, p o p) o p}$

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

• p → (¬p → q) - доказательство:
  1. ${displaystyle p o (например, q o p)}$ (пример (A1))
  2. ${стиль отображения (например, q o p) o (например, p o eg eg q)}$ (экземпляр (TR1))
  3. ${displaystyle p o (например, p o eg eg q)}$ (из (1) и (2) с использованием гипотетической метатеоремы силлогизма)
  4. ${стиль отображения, например, например, q o q}$ (экземпляр (DN1))
  5. ${стиль отображения (например, q o q) o ((например, p o, например, q) o (например, p o q))}$ (экземпляр (HS1))
  6. ${стиль отображения (например, p o например, q) o (например, p o q)}$ (из (4) и (5) с использованием modus ponens)
  7. ${displaystyle p o (например, p o q)}$ (из (3) и (6) с использованием гипотетической метатеоремы силлогизма)
• (p → q) → ((¬p → q) → q) - доказательство:
  1. ${displaystyle (p o q) o ((например, q o p) o (например, q o q))}$ (экземпляр (HS1))
  2. ${стиль отображения (например, q o q) o q}$ (экземпляр (L3))
  3. ${displaystyle ((например, q o q) o q) o (((например, q o p) o (например, q o q)) o ((например, q o p) o q))}$ (экземпляр (HS1))
  4. ${displaystyle ((например, q o p) o (например, q o q)) o ((например, q o p) o q)}$ (из (2) и (3) по modus ponens)
  5. ${displaystyle (p o q) o ((например, q o p) o q)}$ (из (1) и (4) с использованием гипотетической метатеоремы силлогизма)
  6. ${стиль отображения (например, p o q) o (например, q o p)}$ (экземпляр (TR2))
  7. ${displaystyle ((например, p o q) o (например, q o p)) o (((например, q o p) o q) o ((например, p o q) o q))}$ (экземпляр (HS2))
  8. ${displaystyle ((например, q o p) o q) o ((например, p o q) o q)}$ (из (6) и (7) с использованием modus ponens)
  9. ${displaystyle (p o q) o ((например, p o q) o q)}$ (из (5) и (8) с использованием гипотетической метатеоремы силлогизма)
• p → (q → (p → q)) - доказательство:
  1. ${displaystyle q o (p o q)}$ (пример (A1))
  2. ${displaystyle (q o (p o q)) o (p o (q o (p o q)))}$ (пример (A1))
  3. ${displaystyle p o (q o (p o q))}$ (из (1) и (2) с использованием modus ponens)
• p → (¬q → ¬ (p → q)) - доказательство:
  1. ${displaystyle p o ((p o q) o q)}$ (экземпляр (L1))
  2. ${displaystyle ((p o q) o q) o (например, q o eg (p o q))}$ (экземпляр (TR1))
  3. ${displaystyle p o (например, q o eg (p o q))}$ (из (1) и (2) с использованием гипотетической метатеоремы силлогизма)
• ¬p → (p → q) - доказательство:
  1. ${displaystyle например, p o (например, q o eg p)}$ (пример (A1))
  2. ${стиль отображения (например, q o eg p) o (p o q)}$ (пример (A3))
  3. ${displaystyle, например, p o (p o q)}$ (из (1) и (2) с использованием гипотетической метатеоремы силлогизма)
• p → p - доказательство приведено в пример доказательства выше
• p → (q → p) - аксиома (A1)
• (p → (q → r)) → ((p → q) → (p → r)) - аксиома (A2)

Еще один план доказательства полноты

Если формула тавтология, то есть таблица истинности для него, который показывает, что каждая оценка дает значение, истинное для формулы. Рассмотрим такую ​​оценку. Путем математической индукции по длине подформул покажите, что истинность или ложность подформулы следует из истинности или ложности (в зависимости от оценки) каждой пропозициональной переменной в подформуле. Затем объедините строки таблицы истинности по две за раз, используя "(п верно подразумевает S) следует ((п ложно подразумевает S) подразумевает S) ". Продолжайте повторять это до тех пор, пока не будут устранены все зависимости от пропозициональных переменных. В результате мы доказали данную тавтологию. Поскольку каждая тавтология доказуема, логика завершена.

Интерпретация исчисления высказываний с функцией истинности

An интерпретация истинностно-функционального исчисления высказываний ${displaystyle {mathcal {P}}}$ является назначение для каждого пропозициональный символ из ${displaystyle {mathcal {P}}}$ одного или другого (но не обоих) ценности истины правда (Т) и фальшь (F) и присвоение соединительные символы из ${displaystyle {mathcal {P}}}$ их обычных истинностно-функциональных значений. Интерпретация исчисления высказываний с функцией истинности также может быть выражена в терминах таблицы истинности.^[14]

За ${displaystyle n}$ различные пропозициональные символы есть ${displaystyle 2 ^ {n}}$ различные возможные интерпретации. Для любого конкретного символа ${displaystyle a}$, например, есть ${displaystyle 2 ^ {1} = 2}$ возможные интерпретации:

1. ${displaystyle a}$ назначается Т, или же
2. ${displaystyle a}$ назначается F.

Для пары ${displaystyle a}$, ${displaystyle b}$ Существуют ${displaystyle 2 ^ {2} = 4}$ возможные интерпретации:

1. оба назначены Т,
2. оба назначены F,
3. ${displaystyle a}$ назначается Т и ${displaystyle b}$ назначается F, или же
4. ${displaystyle a}$ назначается F и ${displaystyle b}$ назначается Т.^[14]

С ${displaystyle {mathcal {P}}}$ имеет ${displaystyle aleph _ {0}}$, то есть, бесчисленно много пропозициональных символов, есть ${displaystyle 2 ^ {алеф _ {0}} = {mathfrak {c}}}$, и поэтому бесчисленное множество различные возможные интерпретации ${displaystyle {mathcal {P}}}$.^[14]

Интерпретация предложения истинностно-функциональной логики высказываний

Если φ и ψ находятся формулы из ${displaystyle {mathcal {P}}}$ и ${displaystyle {mathcal {I}}}$ интерпретация ${displaystyle {mathcal {P}}}$ тогда применяются следующие определения:

• Предложение логики высказываний верно в интерпретации ${displaystyle {mathcal {I}}}$ если ${displaystyle {mathcal {I}}}$ присваивает значение истины Т к этому предложению. Если предложение истинный при интерпретации, то эта интерпретация называется модель этого предложения.
• φ является ложный при интерпретации ${displaystyle {mathcal {I}}}$ если φ не верно под ${displaystyle {mathcal {I}}}$.^[14]
• Предложение логики высказываний логически действительный если это правда при любой интерпретации.

  ${displaystyle models}$ φ Значит это φ логически верно.

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

Некоторые следствия этих определений:

• Для любой данной интерпретации данная формула либо истинна, либо ложна.^[14]
• Никакая формула не является одновременно истинной и ложной при одной и той же интерпретации.^[14]
• φ ложно для данной интерпретации, если и только если ${displaystyle eg phi}$ верно для этой интерпретации; и φ верно при интерпретации, если и только если ${displaystyle eg phi}$ ложно при такой интерпретации.^[14]
• Если φ и ${displaystyle (phi o psi)}$ оба верны при данной интерпретации, то ψ верно при такой интерпретации.^[14]
• Если ${displaystyle models _ {mathrm {P}} phi}$ и ${displaystyle models _ {mathrm {P}} (phi o psi)}$, тогда ${displaystyle models _ {mathrm {P}} psi}$.^[14]
• ${displaystyle eg phi}$ верно под ${displaystyle {mathcal {I}}}$ если только φ не верно под ${displaystyle {mathcal {I}}}$.
• ${displaystyle (phi o psi)}$ верно под ${displaystyle {mathcal {I}}}$ если и только тогда φ не верно под ${displaystyle {mathcal {I}}}$ или же ψ верно под ${displaystyle {mathcal {I}}}$.^[14]
• Предложение ψ логики высказываний является семантическим следствием предложения φ если только ${displaystyle (phi o psi)}$ является логически действительный, то есть, ${displaystyle phi models _ {mathrm {P}} psi}$ если только ${displaystyle models _ {mathrm {P}} (phi o psi)}$.^[14]

Альтернативное исчисление

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

Аксиомы

Позволять φ, χ, и ψ обозначают правильные формулы. (Сами по себе правильно сформированные формулы не будут содержать никаких греческих букв, а будут содержать только заглавные латинские буквы, операторы связки и круглые скобки.) Тогда аксиомы следующие:

Аксиомы

Имя	Схема аксиомы	Описание
ТО-1	${displaystyle phi o (chi o phi)}$	Добавить гипотезу χ, введение импликации
ТО-2	${displaystyle (phi o (chi o psi)) o ((phi o chi) o (phi o psi))}$	Распространить гипотезу ${displaystyle phi}$ над подтекстом
И-1	${displaystyle phi land chi o phi}$	Исключить союз
И-2	${displaystyle phi land chi o chi}$
И-3	${displaystyle phi o (chi o (phi land chi))}$	Ввести союз
ИЛИ-1	${displaystyle phi o phi lor chi}$	Ввести дизъюнкцию
ИЛИ-2	${displaystyle chi o phi lor chi}$
ИЛИ-3	${displaystyle (phi o psi) o ((chi o psi) o (phi lor chi o psi))}$	Устранение дизъюнкции
НЕ-1	${displaystyle (phi o chi) o ((phi o eg chi) o eg phi)}$	Ввести отрицание
НЕ-2	${displaystyle phi o (например, phi o chi)}$	Устранить отрицание
НЕ-3	${displaystyle phi lor eg phi}$	Исключенная средняя, ​​классическая логика
МКФ-1	${displaystyle (phi leftrightarrow chi) o (phi o chi)}$	Устранение эквивалентности
МКФ-2	${displaystyle (phi leftrightarrow chi) o (chi o phi)}$
МКФ-3	${displaystyle (phi o chi) o ((chi o phi) o (phi leftrightarrow chi))}$	Ввести эквивалентность

• Аксиома ТО-2 может рассматриваться как «распределительное свойство импликации по отношению к импликации».
• Аксиомы И-1 и И-2 соответствуют «устранению союзов». Связь между И-1 и И-2 отражает коммутативность оператора конъюнкции.
• Аксиома И-3 соответствует «введению соединения».
• Аксиомы ИЛИ-1 и ИЛИ-2 соответствуют «введению дизъюнкции». Связь между ИЛИ-1 и ИЛИ-2 отражает коммутативность оператора дизъюнкции.
• Аксиома НЕ-1 соответствует «reductio ad absurdum».
• Аксиома НЕ-2 говорит, что «из противоречия можно вывести что угодно».
• Аксиома НЕ-3 называется "tertium non datur " (латинский: «третье не дано») и отражает семантическую оценку пропозициональных формул: формула может иметь истинное или ложное значение. Третьего истинностного значения не существует, по крайней мере, в классической логике. Логики-интуиционисты не принимаю аксиому НЕ-3.

Правило вывода

Правило вывода: modus ponens:

${displaystyle phi, phi o chi vdash chi}$.

Правило мета-вывода

Пусть демонстрация представлена ​​последовательностью с гипотезами слева от турникет и вывод справа от турникета. Тогда теорема дедукции можно сформулировать следующим образом:

Если последовательность

${displaystyle phi _ {1}, phi _ {2}, ..., phi _ {n}, chi vdash psi}$

была продемонстрирована, то также можно продемонстрировать последовательность

${displaystyle phi _ {1}, phi _ {2}, ..., phi _ {n} vdash chi o psi}$.

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

С другой стороны, DT настолько полезен для упрощения процесса синтаксического доказательства, что его можно рассматривать и использовать как еще одно правило вывода, сопровождающее modus ponens. В этом смысле DT соответствует естественному условное доказательство правило вывода, которое является частью первой версии исчисления высказываний, представленной в этой статье.

Обратное DT также верно:

Если последовательность

${displaystyle phi _ {1}, phi _ {2}, ..., phi _ {n} vdash chi o psi}$

была продемонстрирована, то также можно продемонстрировать последовательность

${displaystyle phi _ {1}, phi _ {2}, ..., phi _ {n}, chi vdash psi}$

на самом деле, выполнение обратного DT почти тривиально по сравнению с DT:

Если

${displaystyle phi _ {1}, ..., phi _ {n} vdash chi o psi}$

тогда

1: ${displaystyle phi _ {1}, ..., phi _ {n}, chi vdash chi o psi}$

2: ${displaystyle phi _ {1}, ..., phi _ {n}, chi vdash chi}$

и из (1) и (2) можно вывести

3: ${displaystyle phi _ {1}, ..., phi _ {n}, chi vdash psi}$

с помощью modus ponens, Q.E.D.

Обратное DT имеет сильные последствия: его можно использовать для преобразования аксиомы в правило вывода. Например, аксиома И-1,

${displaystyle vdash phi wedge chi o phi}$

можно преобразовать с помощью обращения теоремы дедукции в правило вывода

${displaystyle phi wedge chi vdash phi}$

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

Пример доказательства

Ниже приводится пример (синтаксической) демонстрации, включающей только аксиомы. ТО-1 и ТО-2:

Доказывать: ${displaystyle A o A}$ (Рефлексивность импликации).

Доказательство:

1. ${displaystyle (A o ((B o A) o A)) o ((A o (B o A)) o (A o A))}$

   Аксиома ТО-2 с ${displaystyle phi = A, chi = B o A, psi = A}$

2. ${displaystyle A o ((B o A) o A)}$

   Аксиома ТО-1 с ${displaystyle phi = A, chi = B o A}$

3. ${displaystyle (A o (B o A)) o (A o A)}$

   Из (1) и (2) по modus ponens.

4. ${displaystyle A o (B o A)}$

   Аксиома ТО-1 с ${displaystyle phi = A, chi = B}$

5. ${displaystyle A o A}$

   Из (3) и (4) по modus ponens.

Эквивалентность эквациональной логике

Предыдущее альтернативное исчисление является примером Система дедукции в стиле Гильберта. В случае систем высказываний аксиомы - это термины, построенные с помощью логических связок, и единственное правило вывода - это modus ponens. Логика уравнений, которая обычно неформально используется в школьной алгебре, представляет собой исчисление, отличное от систем Гильберта. Его теоремы являются уравнениями, а его правила вывода выражают свойства равенства, а именно то, что это конгруэнтность членов, допускающая замену.

Классическое исчисление высказываний, описанное выше, эквивалентно Булева алгебра, пока интуиционистское исчисление высказываний эквивалентно Алгебра Гейтинга. Эквивалентность показывается переносом в каждом направлении теорем соответствующих систем. Теоремы ${displaystyle phi}$ классического или интуиционистского исчисления высказываний переводятся как уравнения ${displaystyle phi = 1}$ булевой или гейтинговой алгебры соответственно. Обратно теоремы ${displaystyle x = y}$ булевой алгебры или гейтинга переводятся как теоремы ${displaystyle (x o y) land (y o x)}$ классического или интуиционистского исчисления соответственно, для которых ${displaystyle xequiv y}$ стандартное сокращение. В случае булевой алгебры ${displaystyle x = y}$ можно также перевести как ${displaystyle (xland y) lor (например, xland, например, y)}$, но этот перевод интуиционистски неверен.

Как в булевой алгебре, так и в алгебре Гейтинга неравенство ${displaystyle xleq y}$ может использоваться вместо равенства. Равенство ${displaystyle x = y}$ выражается в виде пары неравенств ${displaystyle xleq y}$ и ${displaystyle yleq x}$. Наоборот, неравенство ${displaystyle xleq y}$ выражается как равенство ${displaystyle xland y = x}$, или как ${displaystyle xlor y = y}$. Значение неравенства для систем типа Гильберта состоит в том, что оно соответствует выводу последнего или логическое следствие символ ${displaystyle vdash}$. Следствие

${displaystyle phi _ {1}, phi _ {2}, dots, phi _ {n} vdash psi}$

переводится в версии алгебраической системы с неравенством как

${displaystyle phi _ {1} land phi _ {2} land dots land phi _ {n} leq psi}$

Наоборот, алгебраическое неравенство ${displaystyle xleq y}$ переводится как следствие

${displaystyle x vdash y}$.

Разница между импликацией ${displaystyle x o y}$ и неравенство или логическое следствие ${displaystyle xleq y}$ или же ${displaystyle x vdash y}$ состоит в том, что первое является внутренним по отношению к логике, а второе - внешним. Внутренний смысл между двумя терминами - это еще один термин того же типа. Вступление как внешнее следствие между двумя терминами выражает метаистину вне языка логики и считается частью метаязык. Даже когда изучаемая логика является интуиционистской, следствие обычно понимается классически как двузначное: либо левая сторона влечет за собой, либо меньше или равна правой стороне, либо нет.

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

Графические исчисления

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

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

Другие логические исчисления

Исчисление высказываний - это простейший вид логического исчисления, который сейчас используется.Его можно расширить несколькими способами. (Аристотелевское «силлогистическое» исчисление, который в значительной степени вытесняется современной логикой, находится в немного способы более простые - но в других отношениях более сложные - чем исчисление высказываний.) Самый быстрый способ разработать более сложное логическое исчисление - это ввести правила, которые чувствительны к более мелким деталям используемых предложений.

Логика первого порядка (он же логика предикатов первого порядка) возникает, когда "атомарные предложения" логики высказываний разбиваются на термины, переменные, предикаты, и кванторы, все соблюдают правила логики высказываний с некоторыми новыми введенными. (Например, из «Все собаки - млекопитающие» мы можем вывести «Если Ровер - собака, то Ровер - млекопитающее».) С помощью инструментов логики первого порядка можно сформулировать ряд теорий, либо с помощью явных аксиом. или по правилам вывода, которые сами по себе можно рассматривать как логические исчисления. Арифметика самый известный из них; другие включают теория множеств и мереология. Логика второго порядка и другие логика высшего порядка являются формальными расширениями логики первого порядка. Таким образом, логику высказываний имеет смысл называть "логика нулевого порядка", сравнивая это с этой логикой.

Модальная логика также предлагает множество выводов, которые нельзя уловить в исчислении высказываний. Например, из «Обязательно п"мы можем сделать вывод, что п. Из п мы можем сделать вывод "Возможно, что п". Перевод между модальной логикой и алгебраической логикой касается классической и интуиционистской логики, но с введением унарного оператора в булевых или гейтинговых алгебрах, отличного от булевых операций, интерпретации модальности возможностей, а в случае алгебры Гейтинга - второго оператора интерпретация необходимости (для булевой алгебры это избыточно, поскольку необходимость является двойственной по Де Моргану возможности). Первый оператор сохраняет 0 и дизъюнкцию, а второй сохраняет 1 и конъюнкцию.

Многозначная логика те, которые позволяют предложениям иметь значения, отличные от истинный и ложный. (Например, ни один и обе стандартные «дополнительные значения»; «континуальная логика» позволяет каждому предложению иметь любую из бесконечного числа «степеней истины» между истинный и ложный.) Эта логика часто требует вычислительных устройств, совершенно отличных от исчисления высказываний. Когда значения образуют булеву алгебру (которая может иметь более двух или даже бесконечно много значений), многозначная логика сводится к классической логике; Поэтому многозначные логики представляют независимый интерес только тогда, когда значения образуют алгебру, не являющуюся булевой.

Решатели

Поиск решений формул логики высказываний - это НП-полный проблема. Однако существуют практические методы (например, Алгоритм DPLL, 1962; Алгоритм Chaff, 2001), которые очень быстрые для многих полезных случаев. Недавняя работа расширила SAT решатель алгоритмы работы с предложениями, содержащими арифметические выражения; эти Решатели SMT.

Смотрите также

Высшие логические уровни

• Логика первого порядка
• Логика высказываний второго порядка
• Логика второго порядка
• Логика высшего порядка