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

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

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

Объяснение [ править ]

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

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

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

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

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

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

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

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

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

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

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

${\ displaystyle P \ to Q, P \ vdash Q}$

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

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

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

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

История [ править ]

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

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

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

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

Терминология [ править ]

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

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

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

Язык пропозиционального исчисления состоит из

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

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

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

Основные понятия [ править ]

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

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

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

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

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

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

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

Закрытие при операциях [ править ]

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

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

Аргумент [ править ]

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

${\ displaystyle {\ begin {array} {rl} 1. & P \ to Q \\ 2. & P \\\ hline \, следовательно, & Q \ end {array}}}$

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

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

${\displaystyle {\begin{array}{rl}1.&\varphi \to \psi \\2.&\varphi \\\hline \therefore &\psi \end{array}}}$

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

Значение аргумента в формальной логике состоит в том, что можно получить новые истины из установленных истин. В первом примере выше, учитывая две предпосылки, истинность Q еще не известна и не установлена. После того, как аргумент сделан, выводится Q. Таким образом, мы определяем систему дедукции как набор всех предложений, которые могут быть выведены из другого набора предложений. Например, учитывая множество предложений , мы можем определить систему дедукции, Г , которая представляет собой множество всех предложений , которые следуют из A . Повторение всегда предполагается, так что . Кроме того, из первого элемента A , последнего элемента, а также modus ponens, R${\displaystyle A=\{P\lor Q,\neg Q\land R,(P\lor Q)\to R\}}$${\displaystyle P\lor Q,\neg Q\land R,(P\lor Q)\to R\in \Gamma }$это следствие, и так . Однако, поскольку мы не включили достаточно полные аксиомы, ничего другого сделать нельзя. Таким образом, хотя большинство систем дедукции, изучаемых в логике высказываний, способны делать выводы , эта система слишком слаба, чтобы доказать такое утверждение.${\displaystyle R\in \Gamma }$${\displaystyle (P\lor Q)\leftrightarrow (\neg P\to Q)}$

Общее описание исчисления высказываний [ править ]

Исчисление является формальной системой , где:${\displaystyle {\mathcal {L}}={\mathcal {L}}\left(\mathrm {A} ,\ \Omega ,\ \mathrm {Z} ,\ \mathrm {I} \right)}$

Пример 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 \}.}$

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

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

  ${\displaystyle \Omega _{2}=\{\to \}.}$

• Система аксиом, предложенная Яном Лукасевичем и использованная как часть исчисления высказываний системы Гильберта , формулирует исчисление высказываний на этом языке следующим образом. Все аксиомы являются примерами замены :
  • ${\displaystyle (p\to (q\to p))}$
  • ${\displaystyle ((p\to (q\to r))\to ((p\to q)\to (p\to r)))}$
  • ${\displaystyle ((\neg p\to \neg q)\to (q\to p))}$
• Правило вывода - это modus ponens (т. Е. Из p и вывести q ). Тогда определяется как , и определяется как . Эта система используется в Metamath set.mm формальной базе данных доказательств.${\displaystyle (p\to q)}$${\displaystyle a\lor b}$${\displaystyle \neg a\to b}$${\displaystyle a\land b}$${\displaystyle \neg (a\to \neg b)}$

Пример 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}\cup \Omega _{2}}$

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

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

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

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

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

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

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

Из а , сделаем .${\displaystyle (p\to q)}$${\displaystyle (p\to \neg q)}$${\displaystyle \neg p}$

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

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

Из , сделаем вывод .${\displaystyle \neg p}$${\displaystyle (p\to r)}$

То есть .${\displaystyle \{\neg p\}\vdash (p\to r)}$

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

Из , вывести p .${\displaystyle \neg \neg p}$

То есть .${\displaystyle \neg \neg p\vdash p}$

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

Из p и q сделайте вывод .${\displaystyle (p\land q)}$

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

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

Из , вывести p .${\displaystyle (p\land q)}$

Из , вывести q .${\displaystyle (p\land q)}$

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

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

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

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

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

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

Из и и , вывести r .${\displaystyle (p\lor q)}$${\displaystyle (p\to r)}$${\displaystyle (q\to r)}$

То есть .${\displaystyle \{p\lor q,p\to r,q\to r\}\vdash r}$

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

Из а , сделаем .${\displaystyle (p\to q)}$${\displaystyle (q\to p)}$${\displaystyle (p\leftrightarrow q)}$

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

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

Из , сделаем вывод .${\displaystyle (p\leftrightarrow q)}$${\displaystyle (p\to q)}$

Из , сделаем вывод .${\displaystyle (p\leftrightarrow q)}$${\displaystyle (q\to p)}$

То есть и .${\displaystyle (p\leftrightarrow q)\vdash (p\to q)}$${\displaystyle (p\leftrightarrow q)\vdash (q\to p)}$

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

Из p и вывести q .${\displaystyle (p\to q)}$

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

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

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

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

Формы основных и производных аргументов [ править ]

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

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

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

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

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

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

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

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

Интерпретировать как «Предположив A , сделайте вывод A ». Читается как «Ничего не предполагая, сделай вывод, что A подразумевает A », или «Это тавтология, что A подразумевает A », или «Всегда верно, что A подразумевает A ».${\displaystyle A\vdash A}$${\displaystyle \vdash A\to A}$

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

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

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

(A1) ${\displaystyle (p\to (q\to p))}$

(A2) ${\displaystyle ((p\to (q\to r))\to ((p\to q)\to (p\to r)))}$

(A3) ${\displaystyle ((\neg p\to \neg q)\to (q\to p))}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Условные обозначения: пусть G - переменная, изменяющаяся между наборами предложений. Пусть A, B и C разбросаны по предложениям. Вместо « G синтаксически влечет за собой A » мы пишем « G доказывает A ». Вместо « G семантически влечет A » мы пишем « G подразумевает A ».

Мы хотим показать: ( A ) ( G ) (если G доказывает A , то G влечет A ).

Заметим, что « G доказывает A » имеет индуктивное определение, и это дает нам непосредственные ресурсы для демонстрации утверждений вида «Если G доказывает A , то ...». Итак, наше доказательство проводится по индукции.

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

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

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

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

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

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

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

Таким образом, каждая система, которая имеет 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 в качестве правила вывода, и доказывает вышеизложенное. восемь теорем (включая их подстановки). Из восьми теорем последние две являются двумя из трех аксиом; Третья аксиома также может быть доказана, как мы сейчас покажем.${\displaystyle (\neg q\to \neg p)\to (p\to q)}$

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

1. ${\displaystyle q\to (p\to q)}$       (пример 7-й теоремы)
2. ${\displaystyle (q\to (p\to q))\to ((\neg q\to \neg p)\to (q\to (p\to q)))}$       (пример 7-й теоремы)
3. ${\displaystyle (\neg q\to \neg p)\to (q\to (p\to q))}$       (из (1) и (2) по modus ponens)
4. ${\displaystyle (\neg p\to (p\to q))\to ((\neg q\to \neg p)\to (\neg q\to (p\to q)))}$       (пример теоремы о гипотетическом силлогизме)
5. ${\displaystyle (\neg p\to (p\to q))}$       (пример 5-й теоремы)
6. ${\displaystyle (\neg q\to \neg p)\to (\neg q\to (p\to q))}$       (из (5) и (4) по modus ponens)
7. ${\displaystyle (q\to (p\to q))\to ((\neg q\to (p\to q))\to (p\to q))}$       (пример 2-й теоремы)
8. ${\displaystyle ((q\to (p\to q))\to ((\neg q\to (p\to q))\to (p\to q)))\to ((\neg q\to \neg p)\to ((q\to (p\to q))\to ((\neg q\to (p\to q))\to (p\to q))))}$       (пример 7-й теоремы)
9. ${\displaystyle (\neg q\to \neg p)\to ((q\to (p\to q))\to ((\neg q\to (p\to q))\to (p\to q)))}$       (из (7) и (8) по modus ponens)
10. ${\displaystyle ((\neg q\to \neg p)\to ((q\to (p\to q))\to ((\neg q\to (p\to q))\to (p\to q))))\to }$

    ${\displaystyle (((\neg q\to \neg p)\to (q\to (p\to q)))\to ((\neg q\to \neg p)\to ((\neg q\to (p\to q))\to (p\to q))))}$       (пример 8-й теоремы)

11. ${\displaystyle ((\neg q\to \neg p)\to (q\to (p\to q)))\to ((\neg q\to \neg p)\to ((\neg q\to (p\to q))\to (p\to q)))}$       (из (9) и (10) по modus ponens)
12. ${\displaystyle (\neg q\to \neg p)\to ((\neg q\to (p\to q))\to (p\to q))}$       (из (3) и (11) по modus ponens)
13. ${\displaystyle ((\neg q\to \neg p)\to ((\neg q\to (p\to q))\to (p\to q)))\to (((\neg q\to \neg p)\to (\neg q\to (p\to q)))\to ((\neg q\to \neg p)\to (p\to q)))}$       (пример 8-й теоремы)
14. ${\displaystyle ((\neg q\to \neg p)\to (\neg q\to (p\to q)))\to ((\neg q\to \neg p)\to (p\to q))}$       (из (12) и (13) по modus ponens)
15. ${\displaystyle (\neg q\to \neg p)\to (p\to q)}$       (из (6) и (14) по modus ponens)

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

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

(DN1) - двойное отрицание (одно направление)${\displaystyle \neg \neg p\to p}$

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

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

(HS2) - еще одна форма гипотетического силлогизма${\displaystyle (p\to q)\to ((q\to r)\to (p\to r))}$

(TR1) - Транспонирование${\displaystyle (p\to q)\to (\neg q\to \neg p)}$

(TR2) - еще одна форма транспозиции.${\displaystyle (\neg p\to q)\to (\neg q\to p)}$

(L1) ${\displaystyle p\to ((p\to q)\to q)}$

(L3) ${\displaystyle (\neg p\to p)\to p}$

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

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

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

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

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

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

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

1. ${\displaystyle a}$присваивается T , или
2. ${\displaystyle a}$назначается F .

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

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

Так как есть , то есть счетное множество пропозициональных символов, есть , и , следовательно , несчетное множество различных возможных интерпретаций . ^[14]${\displaystyle {\mathcal {P}}}$${\displaystyle \aleph _{0}}$${\displaystyle 2^{\aleph _{0}}={\mathfrak {c}}}$${\displaystyle {\mathcal {P}}}$

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

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

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

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

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

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

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

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

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

Аксиомы [ править ]

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

Аксиомы

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

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

Правило вывода [ править ]

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

${\displaystyle \phi ,\ \phi \to \chi \vdash \chi }$.

Правило мета-вывода [ править ]

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

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

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

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

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

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

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

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

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

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

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

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

на самом деле справедливость обращения DT почти тривиальна по сравнению с DT:

Если

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

тогда

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

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

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

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

с помощью modus ponens, QED

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

${\displaystyle \vdash \phi \wedge \chi \to \phi }$

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

${\displaystyle \phi \wedge \chi \vdash \phi }$

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

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

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

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

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

1. ${\displaystyle (A\to ((B\to A)\to A))\to ((A\to (B\to A))\to (A\to A))}$

   Аксиома THEN-2 с${\displaystyle \phi =A,\chi =B\to A,\psi =A}$

2. ${\displaystyle A\to ((B\to A)\to A)}$

   Аксиома THEN-1 с${\displaystyle \phi =A,\chi =B\to A}$

3. ${\displaystyle (A\to (B\to A))\to (A\to A)}$

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

4. ${\displaystyle A\to (B\to A)}$

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

5. ${\displaystyle A\to A}$

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

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

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

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

Как в булевой алгебре, так и в алгебре Гейтинга неравенство может использоваться вместо равенства. Равенство выражается парой неравенств и . И наоборот, неравенство можно выразить как равенство или как . Значение неравенства для систем типа Гильберта состоит в том, что оно соответствует символу вывода или следования последнего . Следствие${\displaystyle x\leq y}$${\displaystyle x=y}$${\displaystyle x\leq y}$${\displaystyle y\leq x}$${\displaystyle x\leq y}$${\displaystyle x\land y=x}$${\displaystyle x\lor 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 x\leq y}$

${\displaystyle x\ \vdash \ y}$.

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

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

Графические исчисления [ править ]

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

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

Другие логические исчисления [ править ]

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

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

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

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

Решатели [ править ]

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

См. Также [ править ]

Высшие логические уровни [ править ]

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

Связанные темы [ править ]

Ссылки [ править ]