Пропозициональное исчисление

Не путать с пропозициональным анализом .

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

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

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

Нотационные варианты связок

соединительный	Символ
И	$A\land B$, $A\cdot B$, $AB$, $A\&B$, $A\&\&B$
эквивалент	$A\equiv B$, $A\Leftrightarrow B$, $A\leftrightharpoons B$
подразумевает	$A\Rightarrow B$, $A\supset B$, $A\rightarrow B$
NAND	$A{\overline {\land }}B$, $A\mid B$, ${\overline {A\cdot B}}$
неэквивалентный	$A\not \equiv B$, $A\not \Leftrightarrow B$, $A\nleftrightarrow B$
НИ	$A{\overline {\lor }}B$, $A\downarrow B$, ${\overline {A+B}}$
НЕТ	$\neg A$, $-A$, ${\overline {A}}$, $\sim A$
ИЛИ	$A\lor B$, $A+B$, $A\mid B$, $A\parallel B$
ИСНО-ИЛИ	$A$ ИСНО-ИЛИ $B$
БЕСПЛАТНО	$A{\underline {\lor }}B$, $A\oplus B$

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

История

Основная статья: История логики

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

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

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

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

Предложения

Основная статья: Предложение

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

Повествовательные предложения

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

• Arc.Ask3.Ru — бесплатная онлайн-энциклопедия, которую может редактировать каждый.
• Лондон – столица Англии .
• Все редакторы Википедии говорят как минимум на трех языках .

Повествовательным предложениям противопоставляются вопросы , такие как «Что такое Arc.Ask3.Ru?», и повелительные утверждения, такие как «Пожалуйста, добавьте цитаты , подтверждающие утверждения в этой статье». Такие недекларативные предложения не имеют истинностного значения . и рассматриваются только в неклассической логике , называемой эротетической и императивной логикой .

Соединение предложений с помощью связок.

См. Также: Атомная формула и Атомное предложение.

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

• Arc.Ask3.Ru — это бесплатная онлайн-энциклопедия, которую может редактировать каждый, и миллионы уже имеют ее . (соединение)
• Неправда, что все редакторы Википедии говорят как минимум на трех языках. (отрицание)
• Либо Лондон — столица Англии, либо Лондон — столица Соединенного Королевства , либо и то, и другое. (дизъюнкция)

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

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

Аргументы

Основная статья: Аргумент

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

Пример аргумента

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

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

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

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

Логическая форма этого аргумента известна как modus ponens . что является классически допустимой формой. Итак, в классической логике аргумент действителен , хотя он может быть или не быть здравым , в зависимости от метеорологических фактов в данном контексте. Этот пример аргумента будет повторно использоваться при объяснении § Формализации .

Валидность и обоснованность

Основные статьи: Валидность (логика) и обоснованность

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

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

Логика, как правило, стремится точно указать действительные аргументы. Это делается путем определения валидного аргумента как аргумента, вывод которого является логическим следствием его посылок. что, если понимать это как семантическое следствие , означает, что не существует случая , в котором посылки истинны, но вывод неверен. – см. § Семантика ниже.

Формализация

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

Пропозициональные переменные

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

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

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

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

Заключение: $Q$

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

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

Обозначение Генцена

Если мы предположим, что истинность modus ponens была принята как аксиома , то тот же аргумент § Примера также можно изобразить следующим образом:

${\frac {P\to Q,P}{Q}}$

Этот метод отображения представляет собой естественной обозначение Генцена для дедукции и секвенциального исчисления . Помещения показаны над линией, называемой линией вывода . разделяются запятой , что указывает на совмещение помещений. Заключение пишется под линией вывода. Линия вывода представляет синтаксическое следствие , иногда называемое дедуктивным следствием , который также обозначается знаком ⊢. Таким образом, вышеизложенное также можно записать в одну строку как $P\to Q,P\vdash Q$.

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

Язык

Язык ( обычно называемый ${\mathcal {L}}$) Исчисление высказываний определяется в терминах:

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

— Правильно составленная формула это любая атомарная формула или любая формула, которая может быть составлена ​​из атомарных формул с помощью операторных символов в соответствии с правилами грамматики. Язык ${\mathcal {L}}$, то определяется либо как идентичное своему набору правильно построенных формул, или как содержащий этот набор (вместе, например, с набором связок и переменных).

Обычно синтаксис ${\mathcal {L}}$ определяется рекурсивно всего несколькими определениями, как показано ниже; некоторые авторы явно включают круглые скобки в качестве знаков препинания при определении синтаксиса своего языка, в то время как другие используют их без комментариев.

Синтаксис

Учитывая набор атомарных пропозициональных переменных $p_{1}$, $p_{2}$, $p_{3}$, ..., и набор пропозициональных связок $c_{1}^{1}$, $c_{2}^{1}$, $c_{3}^{1}$, ..., $c_{1}^{2}$, $c_{2}^{2}$, $c_{3}^{2}$, ..., $c_{1}^{3}$, $c_{2}^{3}$, $c_{3}^{3}$, ..., формула логики высказываний определяется рекурсивно этими определениями:

Определение 1. Атомарные пропозициональные переменные являются формулами.

Определение 2 : Если $c_{n}^{m}$ является пропозициональной связкой и $\langle$А, Б, В, … $\rangle$ представляет собой последовательность m, возможно, но не обязательно атомарных, возможно, но не обязательно различных формул, тогда результат применения $c_{n}^{m}$ чтобы к $\langle$А, Б, В, … $\rangle$ это формула.

Определение 3: Ничто иное не является формулой.

Написание результата применения $c_{n}^{m}$ к $\langle$А, Б, В, … $\rangle$ в функциональной записи, как $c_{n}^{m}$(A, B, C,…), в качестве примеров корректных формул мы имеем следующие:

• $p_{5}$
• $c_{3}^{2}(p_{2},p_{9})$
• $c_{3}^{2}(p_{1},c_{2}^{1}(p_{3}))$
• $c_{1}^{3}(p_{4},p_{6},c_{2}^{2}(p_{1},p_{2}))$
• $c_{4}^{2}(c_{1}^{1}(p_{7}),c_{3}^{1}(p_{8}))$
• $c_{2}^{3}(c_{1}^{2}(p_{3},p_{4}),c_{2}^{1}(p_{5}),c_{3}^{2}(p_{6},p_{7}))$
• $c_{3}^{1}(c_{1}^{3}(p_{2},p_{3},c_{2}^{2}(p_{4},p_{5})))$

То, что было дано выше в качестве определения 2 называет и отвечает за композицию формул, Колин Хаусон принципом композиции . Именно эта рекурсия в определении синтаксиса языка оправдывает использование слова «атомарный» для обозначения пропозициональных переменных, поскольку все формулы в языке ${\mathcal {L}}$ состоят из атомов как основных строительных блоков. Сложные формулы (все формулы, кроме атомов) называются молекулами . или молекулярные предложения . (Это несовершенная аналогия с химией , поскольку химическая молекула иногда может иметь только один атом, как в одноатомных газах .)

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

Грамматика CF в BNF

Альтернативой приведенным выше определениям синтаксиса является написание контекстно-свободной (CF) грамматики для языка. ${\mathcal {L}}$ в форме Бэкуса-Наура (БНФ). Это чаще встречается в информатике, чем в философии . Это можно сделать разными способами, из которых особенно кратким для общего набора из пяти связок является это единственное предложение:

$\phi ::=a_{1},a_{2},\ldots ~|~\neg \phi ~|~\phi ~\&~\psi ~|~\phi \vee \psi ~|~\phi \rightarrow \psi ~|~\phi \leftrightarrow \psi$

Это предложение, в силу его самореферентного характера (поскольку $\phi$ есть в некоторых ответвлениях определения $\phi$), также действует как рекурсивное определение и, следовательно, определяет весь язык. Чтобы расширить его за счет добавления модальных операторов , нужно всего лишь добавить… $|~\Box \phi ~|~\Diamond \phi$ до конца пункта.

Константы и схемы

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

Однако некоторые авторы признают в своей формальной системе только две «пропозициональные константы»: специальный символ $\top$, называемый «истина», который всегда имеет значение True , и специальный символ $\bot$, называемый «ложностью», который всегда имеет значение False . Другие авторы также включают эти символы с тем же значением, но считают их «функторами истинности с нулевым местом». или, что то же самое, « нульарные связки».

Семантика

Основные статьи: Семантика логики и теория моделей

Чтобы служить моделью логики данного естественного языка , формальный язык должен быть семантически интерпретирован. В классической логике все предложения оцениваются ровно в одно из двух истинностных значений : истинное или ложное . Например, « Arc.Ask3.Ru — это бесплатная онлайн-энциклопедия , которую может редактировать каждый» имеет значение True . в то время как «Arc.Ask3.Ru — это бумажная энциклопедия » оценивается как False .

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

Интерпретация (случай) и аргументация

Основная статья: Интерпретация (логика)

Для данного языка ${\mathcal {L}}$, интерпретация , оценка , или случай , – это присвоение семантических значений каждой формуле ${\mathcal {L}}$. Для формального языка классической логики случай определяется как присвоение каждой формуле ${\mathcal {L}}$, одного или другого, но не обоих, значений истинности , а именно истинности ( T или 1) и ложности ( F или 0). Интерпретацию, которая следует правилам классической логики, иногда называют булевой оценкой . Интерпретация формального языка классической логики часто выражается в терминах таблиц истинности . Поскольку каждой формуле присваивается только одно истинностное значение, интерпретацию можно рассматривать как функцию , область определения которой равна ${\mathcal {L}}$, и чей диапазон представляет собой набор его семантических значений ${\mathcal {V}}=\{{\mathsf {T}},{\mathsf {F}}\}$, или ${\mathcal {V}}=\{1,0\}$.

Для $n$ существуют отдельные пропозициональные символы $2^{n}$ различные возможные интерпретации. Для любого конкретного символа $a$, например, есть $2^{1}=2$ возможные интерпретации: либо $a$ присваивается T , или $a$ присвоено Ф. ​И для пары $a$, $b$ есть $2^{2}=4$ возможные интерпретации: либо обоим присвоено T , либо обоим присвоено F , либо $a$ присваивается T и $b$ присваивается F или $a$ присваивается F и $b$ присвоено Т. ​ С ${\mathcal {L}}$ имеет $\aleph _{0}$, то есть счетно много пропозициональных символов, существуют $2^{\aleph _{0}}={\mathfrak {c}}$, и, следовательно, бесчисленное множество различных возможных интерпретаций ${\mathcal {L}}$ в целом.

Где ${\mathcal {I}}$ представляет собой интерпретацию и $\varphi$ и $\psi$ представляют формулы, определение аргумента , данное в § Аргументы , может быть затем сформулировано как пара $\langle \{\varphi _{1},\varphi _{2},\varphi _{3},...,\varphi _{n}\},\psi \rangle$, где $\{\varphi _{1},\varphi _{2},\varphi _{3},...,\varphi _{n}\}$ представляет собой совокупность помещений и $\psi$ это вывод. аргумента Определение достоверности , т.е. его свойства, которое $\{\varphi _{1},\varphi _{2},\varphi _{3},...,\varphi _{n}\}\models \psi$, тогда можно сформулировать как отсутствие контрпримера , где контрпример определяется как случай ${\mathcal {I}}$ в котором предпосылки аргумента $\{\varphi _{1},\varphi _{2},\varphi _{3},...,\varphi _{n}\}$ все верно, кроме заключения $\psi$ это неправда. Как будет видно из § Семантическая истина, достоверность, следствие , это то же самое, что сказать, что заключение является семантическим следствием посылок.

Пропозициональная соединительная семантика

Основные статьи: Логическая связка и функция истины

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

Семантика через таблицы истинности

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

п	д	п ∧ q	п ∨ q	п → д	п ↔ q	¬p	¬q
Т	Т	Т	Т	Т	Т	Ф	Ф
Т	Ф	Ф	Т	Ф	Ф	Ф	Т
Ф	Т	Ф	Т	Т	Ф	Т	Ф
Ф	Ф	Ф	Ф	Т	Т	Т	Т

Эта таблица охватывает каждую из пяти основных логических связок : конъюнкция (здесь обозначена p ∧ q), дизъюнкция (p ∨ q), импликация (p → q), двуусловие (p ↔ q) и отрицание (¬p или ¬q, в зависимости от обстоятельств). Этого достаточно для определения семантики каждого из этих операторов. Дополнительные таблицы истинности для большего количества различных видов связок см. в статье « Таблица истинности ».

Семантика через выражения присваивания

Некоторые авторы (а именно все авторы, цитируемые в этом подразделе) записывают семантику связок, используя список утверждений вместо таблицы. В этом формате, где ${\mathcal {I}}(\varphi )$ это интерпретация $\varphi$, пять связок определяются как:

• ${\mathcal {I}}(\neg P)={\mathsf {T}}$ тогда и только тогда, когда ${\mathcal {I}}(P)={\mathsf {F}}$
• ${\mathcal {I}}(P\land Q)={\mathsf {T}}$ тогда и только тогда, когда ${\mathcal {I}}(P)={\mathsf {T}}$ и ${\mathcal {I}}(Q)={\mathsf {T}}$
• ${\mathcal {I}}(P\lor Q)={\mathsf {T}}$ тогда и только тогда, когда ${\mathcal {I}}(P)={\mathsf {T}}$ или ${\mathcal {I}}(Q)={\mathsf {T}}$
• ${\mathcal {I}}(P\to Q)={\mathsf {T}}$ тогда и только тогда, когда верно, что если ${\mathcal {I}}(P)={\mathsf {T}}$, затем ${\mathcal {I}}(Q)={\mathsf {T}}$
• ${\mathcal {I}}(P\leftrightarrow Q)={\mathsf {T}}$ тогда и только тогда, когда верно, что ${\mathcal {I}}(P)={\mathsf {T}}$ тогда и только тогда, когда ${\mathcal {I}}(Q)={\mathsf {T}}$

Вместо ${\mathcal {I}}(\varphi )$, интерпретация $\varphi$ может быть записано как $|\varphi |$, или, для таких определений, как приведенные выше, ${\mathcal {I}}(\varphi )={\mathsf {T}}$ можно записать просто как английское предложение " $\varphi$ присвоено значение ${\mathsf {T}}$". Еще другие авторы возможно, предпочту говорить о модели Тарского ${\mathfrak {M}}$ для языка, так что вместо этого они будут использовать обозначение ${\mathfrak {M}}\models \varphi$, что эквивалентно высказыванию ${\mathcal {I}}(\varphi )={\mathsf {T}}$, где ${\mathcal {I}}$ это функция интерпретации для ${\mathfrak {M}}$.

Методы определения связности

Некоторые из этих связок можно определить через другие: например, импликация p → q может быть определена в терминах дизъюнкции и отрицания, как ¬p ∨ q; а дизъюнкция может быть определена в терминах отрицания и конъюнкции как ¬(¬p ∧ ¬q). Фактически это истинно-функционально полная система, в том смысле, что все и только классические пропозициональные тавтологии являются теоремами, могут быть получены с использованием только дизъюнкции и отрицания (как это сделали Рассел , Уайтхед и Гильберт ), или используя только импликацию и отрицание (как это делал Фреге ), или используя только союз и отрицание, или даже используя только одну связку для «не и» ( штрих Шеффера ), как это сделал Жан Никод . Связка совместного отрицания ( логическое ИЛИ ) сама по себе также достаточна для определения всех остальных связок. но никакие другие связки не обладают этим свойством.

Некоторые авторы, а именно Хаусон и Каннингем, отличать эквивалентность от двуусловия. (Что касается эквивалентности, Хаусон называет ее «истинно-функциональной эквивалентностью», а Каннингем называет ее «логической эквивалентностью».) Эквивалентность обозначается ⇔ и является метаязыковым символом, тогда как бикондиционал обозначается ↔ и является логической связкой в объектный язык ${\mathcal {L}}$. В любом случае, эквивалентность или бикондиционал истинны тогда и только тогда, когда связанным с ними формулам присваивается одно и то же семантическое значение при каждой интерпретации. Другие авторы часто не делают этого различия и могут использовать слово «эквивалентность». и/или символ ⇔, для обозначения двуусловной связки их объектного языка.

Семантическая истина, достоверность, следствие

Данный $\varphi$ и $\psi$ как формулы (или предложения) языка ${\mathcal {L}}$, и ${\mathcal {I}}$ как интерпретация (или случай) из ${\mathcal {L}}$, то применяются следующие определения:

• Правда в деле: Предложение $\varphi$ из ${\mathcal {L}}$ верно в соответствии с интерпретацией ${\mathcal {I}}$ если ${\mathcal {I}}$ значение истинности T присваивает $\varphi$. Если $\varphi$ верно ​ под ${\mathcal {I}}$, затем ${\mathcal {I}}$ называется моделью ​ $\varphi$.
• Ложь в случае: $\varphi$ является ложным в соответствии с интерпретацией ${\mathcal {I}}$ тогда и только тогда, когда $\neg \varphi$ верно под ${\mathcal {I}}$. Это определение ложности в случае как «истина отрицания». Ложность в случае также может быть определена с помощью определения «дополнения»: $\varphi$ является ложным в соответствии с интерпретацией ${\mathcal {I}}$ тогда и только тогда, когда $\varphi$ это неправда под ${\mathcal {I}}$. В классической логике эти определения эквивалентны, а в неклассической — нет.
• Семантическое следствие: предложение $\psi$ из ${\mathcal {L}}$ является смысловым следствием ( $\varphi \models \psi$) предложения $\varphi$ если нет толкования, согласно которому $\varphi$ это правда и $\psi$ это неправда.
• Допустимая формула (тавтология): Предложение. $\varphi$ из ${\mathcal {L}}$ верно логически ( $\models \varphi$), или тавтология , если это верно при любой интерпретации, или правда в каждом случае.
• Согласованное предложение: Предложение ${\mathcal {L}}$ является непротиворечивым, если оно истинно хотя бы при одной интерпретации. Оно непоследовательно, если оно непоследовательно. Несогласованную формулу еще называют самопротиворечивой . и сказал, что это внутреннее противоречие , или просто противоречие , хотя это последнее имя иногда резервируется специально для операторов формы $(p\land \neg p)$.

Для толкований (кейсов) ${\mathcal {I}}$ из ${\mathcal {L}}$, иногда даются такие определения:

• Полное дело: Дело ${\mathcal {I}}$ является полным тогда и только тогда, когда либо $\varphi$ верно в- ${\mathcal {I}}$ или $\neg \varphi$ верно в- ${\mathcal {I}}$, для любого $\varphi$ в ${\mathcal {L}}$.
• Последовательный случай: Случай ${\mathcal {I}}$ является непротиворечивым тогда и только тогда, когда не существует $\varphi$ в ${\mathcal {L}}$ такой, что оба $\varphi$ и $\neg \varphi$ верны в- ${\mathcal {I}}$.

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

• Для любой данной интерпретации данная формула либо истинна, либо ложна.
• Ни одна формула не является одновременно истинной и ложной при одной и той же интерпретации.
• $\varphi$ верно под ${\mathcal {I}}$ тогда и только тогда, когда $\neg \varphi$ является ложным под ${\mathcal {I}}$; $\neg \varphi$ верно под ${\mathcal {I}}$ тогда и только тогда, когда $\varphi$ это неправда под ${\mathcal {I}}$.
• Если $\varphi$ и $(\varphi \to \psi )$ оба верны под ${\mathcal {I}}$, затем $\psi$ верно под ${\mathcal {I}}$.
• Если $\models \varphi$ и $\models (\varphi \to \psi )$, затем $\models \psi$.
• $(\varphi \to \psi )$ верно под ${\mathcal {I}}$ тогда и только тогда, когда либо $\varphi$ это неправда под ${\mathcal {I}}$, или $\psi$ верно под ${\mathcal {I}}$.
• $\varphi \models \psi$ тогда и только тогда, когда $(\varphi \to \psi )$ , логически обоснован то есть $\varphi \models \psi$ тогда и только тогда, когда $\models (\varphi \to \psi )$.

Системы доказательств

См. Также: Теория доказательств и Исчисление доказательств.

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

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

Пример таблицы истинности

Графическое представление частично построенной пропозициональной таблицы.

Системы семантических доказательств опираются на концепцию семантических последствий, символизируемую как $\varphi \models \psi$, что указывает на то, что если $\varphi$ верно, тогда $\psi$ также должно быть истинным во всех возможных интерпретациях.

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

Основная статья: Таблица истинности

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

Семантические таблицы

Основная статья: Метод аналитических таблиц

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

Синтаксические системы доказательства

Правила исчисления секвенций высказываний LK в Генцена обозначениях

Системы синтаксического доказательства, напротив, фокусируются на формальном манипулировании символами в соответствии с конкретными правилами. Понятие синтаксического следствия, $\varphi \vdash \psi$, означает, что $\psi$ может быть получено из $\varphi$ используя правила формальной системы.

Аксиоматические системы

Основная статья: Аксиоматическая система (логика)

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

Естественный вычет

Основная статья: Естественный вычет

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

Секвенционное исчисление

Основная статья: Секвенционное исчисление

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

Семантическое доказательство с помощью таблиц истинности

См. также: Таблица истинности

Воспользовавшись семантической концепцией достоверности (истина в каждой интерпретации), можно доказать достоверность формулы с помощью таблицы истинности , которая дает все возможные интерпретации (присвоение значений истинности переменным) формулы. Если и только если все строки таблицы истинности оказываются истинными, формула семантически верна (истинна в любой интерпретации). Далее, если (и только если) $\neg \varphi$ действителен, то $\varphi$ является противоречивым.

Например, эта таблица показывает, что « p → (q ∨ r → (r → ¬p)) » недопустимо:

п	д	р	р ∨ д	р → ¬ п	q ∨ р → ( р → ¬ п )	п → ( q ∨ р → ( р → ¬ п ))
Т	Т	Т	Т	Ф	Ф	Ф
Т	Т	Ф	Т	Т	Т	Т
Т	Ф	Т	Т	Ф	Ф	Ф
Т	Ф	Ф	Ф	Т	Т	Т
Ф	Т	Т	Т	Т	Т	Т
Ф	Т	Ф	Т	Т	Т	Т
Ф	Ф	Т	Т	Т	Т	Т
Ф	Ф	Ф	Ф	Т	Т	Т

Вычисление последнего столбца третьей строки может быть отображено следующим образом:

п	→	(q	∨	р	→	(р	→	¬	п))
Т	→	(Ф	∨	Т	→	(Т	→	¬	Т))
Т	→	(	Т		→	(Т	→	Ф	))
Т	→	(	Т		→		Ф		)
Т	→				Ф
	Ф
Т	Ф	Ф	Т	Т	Ф	Т	Ф	Ф	Т

Далее, используя теорему о том, что $\varphi \models \psi$ тогда и только тогда, когда $(\varphi \to \psi )$ действителен, мы можем использовать таблицу истинности, чтобы доказать, что формула является семантическим следствием набора формул: $\{\varphi _{1},\varphi _{2},\varphi _{3},...,\varphi _{n}\}\models \psi$ тогда и только тогда, когда мы можем создать таблицу истинности, которая окажется верной для формулы $\left(\left(\bigwedge _{i=1}^{n}\varphi _{i}\right)\rightarrow \psi \right)$ (то есть, если $\models \left(\left(\bigwedge _{i=1}^{n}\varphi _{i}\right)\rightarrow \psi \right)$).

Семантическое доказательство с помощью таблиц

Основная статья: Метод аналитических таблиц

Поскольку таблицы истинности имеют 2 ^н строки для n переменных, они могут быть утомительно длинными для больших значений n. Аналитические таблицы являются более эффективным, но, тем не менее, механическим методом. семантический метод доказательства; они пользуются тем фактом, что «мы ничего не узнаем о достоверности вывода, исследуя распределения истинностных значений, которые делают либо посылки ложными, либо вывод истинным: единственные релевантные распределения при рассмотрении дедуктивной валидности — это, очевидно, только те распределения, которые делают посылки истинны, а заключение ложно».

Аналитические таблицы для пропозициональной логики полностью определяются правилами, схематически изложенными ниже. В этих правилах используются «формулы со знаком», где формула со знаком является выражением. $TX$ или $FX$, где $X$ это (беззнаковая) формула языка ${\mathcal {L}}$. (Неофициально, $TX$ читается " $X$ это правда», и $FX$ читается " $X$ неверно».) Их формальное семантическое определение состоит в том, что «при любой интерпретации подписанная формула $TX$ называется истинным, если $X$ истинно и ложно, если $X$ неверно, тогда как знаковая формула $FX$ называется ложным, если $X$ верно, и верно, если $X$ ложно».

${\begin{aligned}&1)\quad {\frac {T\sim X}{FX}}\quad &&{\frac {F\sim X}{TX}}\\{\phantom {spacer}}\\&2)\quad {\frac {T(X\land Y)}{\begin{matrix}TX\\TY\end{matrix}}}\quad &&{\frac {F(X\land Y)}{FX|FY}}\\{\phantom {spacer}}\\&3)\quad {\frac {T(X\lor Y)}{TX|TY}}\quad &&{\frac {F(X\lor Y)}{\begin{matrix}FX\\FY\end{matrix}}}\\{\phantom {spacer}}\\&4)\quad {\frac {T(X\supset Y)}{FX|TY}}\quad &&{\frac {F(X\supset Y)}{\begin{matrix}TX\\FY\end{matrix}}}\end{aligned}}$

В этих обозначениях правило 2 означает, что $T(X\land Y)$ дает оба $TX,TY$, тогда как $F(X\land Y)$ разветвляется на $FX,FY$. Обозначения следует понимать аналогично правилам 3 и 4. Часто в таблицах классической логики обозначение формулы со знаком упрощается так, что $T\varphi$ пишется просто как $\varphi$, и $F\varphi$ как $\neg \varphi$, что объясняет название правила 1 « Правило двойного отрицания ».

Таблицу для набора формул составляют, применяя правила для создания большего количества строк и ветвей дерева до тех пор, пока не будет использована каждая строка, создавая полную таблицу. В некоторых случаях ветка может содержать оба $TX$ и $FX$ для некоторых $X$, то есть противоречие. В этом случае говорят, что ветка закрывается . Если каждая ветвь дерева закрывается, говорят, что закрывается само дерево. В силу правил построения таблиц закрытое дерево является доказательством того, что исходная формула или набор формул, использованных для его построения, сама была противоречивой и, следовательно, ложной. И наоборот, таблица также может доказать, что логическая формула тавтологична : если формула тавтологична, ее отрицание является противоречием, поэтому таблица, построенная на основе ее отрицания, закроется.

Чтобы построить таблицу для аргумента $\langle \{\varphi _{1},\varphi _{2},\varphi _{3},...,\varphi _{n}\},\psi \rangle$, сначала выписывают набор формул посылок, $\{\varphi _{1},\varphi _{2},\varphi _{3},...,\varphi _{n}\}$, с одной формулой в каждой строке, подписанной знаком $T$ (то есть, $T\varphi$ для каждого $T\varphi$ в комплекте); и вместе с этими формулами (порядок неважен) выписывают и вывод: $\psi$, подписал с $F$ (то есть, $F\psi$). Затем создается дерево истинности (аналитическая таблица), используя все эти строки в соответствии с правилами. Замкнутое дерево будет доказательством того, что аргумент верен, поскольку $\varphi \models \psi$ тогда и только тогда, когда $\{\varphi ,\sim \psi \}$ противоречиво (также пишется как $\varphi ,\sim \psi \models$).

Список классически допустимых форм аргументов

Используя методы семантической проверки, такие как таблицы истинности или семантические таблицы, для проверки тавтологий и семантических последствий, можно показать, что в классической логике следующие классические формы аргументов семантически действительны, т. е. эти тавтологии и семантические последствия верны. Мы используем $\varphi$ ⟚ $\psi$ для обозначения эквивалентности $\varphi$ и $\psi$, то есть как сокращение для обоих $\varphi \models \psi$ и $\psi \models \varphi$; Для облегчения чтения символов дано описание каждой формулы. В описании символ ⊧ (называемый «двойной турникет») читается как «следовательно», что является его общепринятым прочтением. хотя многие авторы предпочитают читать это как «влечет за собой», или как «модели».

Имя	секвентальный	Описание
Режим настройки	$((p\to q)\land p)\models q$	Если р, то q ; п ; поэтому q
Модус Толленс	$((p\to q)\land \neg q)\models \neg p$	Если р, то q ; не д ; поэтому не п
Гипотетический силлогизм	$((p\to q)\land (q\to r))\models (p\to r)$	Если р, то q ; если q, то r ; следовательно, если p, то r
Дизъюнктивный силлогизм	$((p\lor q)\land \neg p)\models q$	Либо p, либо q , либо оба; не п ; следовательно, q
Конструктивная дилемма	$((p\to q)\land (r\to s)\land (p\lor r))\models (q\lor s)$	Если р, то q ; и если г, то s ; но п или р ; поэтому q или s
Разрушительная дилемма	$((p\to q)\land (r\to s)\land (\neg q\lor \neg s))\models (\neg p\lor \neg r)$	Если р, то q ; и если г, то s ; но не q или не s ; поэтому ни п , ни не р
Двунаправленная дилемма	$((p\to q)\land (r\to s)\land (p\lor \neg s))\models (q\lor \neg r)$	Если р, то q ; и если г, то s ; но р или нет s ; поэтому q или нет r
Упрощение	$(p\land q)\models p$	p и q верны; следовательно, p истинно
Соединение	$p,q\models (p\land q)$	p и q верны по отдельности; следовательно, они истинны вместе
Добавление	$p\models (p\lor q)$	р верно; следовательно, дизъюнкция ( p или q ) верна
Состав	$((p\to q)\land (p\to r))\models (p\to (q\land r))$	Если р, то q ; и если р, то р ; следовательно, если p истинно, то q и r истинны
Теорема де Моргана (1)	$\neg (p\land q)$ ⟚ $(\neg p\lor \neg q)$	Отрицание ( p и q ) эквивалентно. to (не p или не q )
Теорема де Моргана (2)	$\neg (p\lor q)$ ⟚ $(\neg p\land \neg q)$	Отрицание ( p или q ) эквивалентно. to (не p и не q )
Коммутация (1)	$(p\lor q)$ ⟚ $(q\lor p)$	( p или q ) эквивалентно. к ( q или p )
Коммутация (2)	$(p\land q)$ ⟚ $(q\land p)$	( p и q ) экв. к ( q и p )
Коммутация (3)	$(p\leftrightarrow q)$ ⟚ $(q\leftrightarrow p)$	( p тогда и только тогда, когда q ) экв. to ( q тогда и только тогда, когда p )
Ассоциация (1)	$(p\lor (q\lor r))$ ⟚ $((p\lor q)\lor r)$	p или ( q или r ) эквивалентно. to ( p или q ) или r
Ассоциация (2)	$(p\land (q\land r))$ ⟚ $((p\land q)\land r)$	p и ( q и r ) эквивалентны. к ( p и q ) и r
Распределение (1)	$(p\land (q\lor r))$ ⟚ $((p\land q)\lor (p\land r))$	p и ( q или r ) эквивалентны. к ( p и q ) или ( p и r )
Распределение (2)	$(p\lor (q\land r))$ ⟚ $((p\lor q)\land (p\lor r))$	p или ( q и r ) эквивалентны. к ( p или q ) и ( p или r )
Двойное отрицание	$p$ ⟚ $\neg \neg p$	p эквивалентно отрицанию not p
Транспонирование	$(p\to q)$ ⟚ $(\neg q\to \neg p)$	Если p , то q эквивалентно. если не q, то не p
Материальное значение	$(p\to q)$ ⟚ $(\neg p\lor q)$	Если p , то q эквивалентно. чтобы не p или q
Эквивалентность материалов (1)	$(p\leftrightarrow q)$ ⟚ $((p\to q)\land (q\to p))$	( p тогда и только тогда, когда q ) экв. (если p истинно, то q истинно) и (если q истинно, то p истинно)
Эквивалентность материалов (2)	$(p\leftrightarrow q)$ ⟚ $((p\land q)\lor (\neg p\land \neg q))$	( p тогда и только тогда, когда q ) экв. либо ( p и q истинны), либо (оба p и q ложны)
Эквивалентность материалов (3)	$(p\leftrightarrow q)$ ⟚ $((p\lor \neg q)\land (\neg p\lor q))$	( p тогда и только тогда , когда q ) эквивалентно., как ( p или не q истинно), так и (не p или q истинно)
Экспорт	$((p\land q)\to r)\models (p\to (q\to r))$	из (если p и q истинны, то r истинно) мы можем доказать (если q истинно, то r истинно, если p истинно)
Импорт	$(p\to (q\to r))$ ⟚ $((p\land q)\to r)$	Если p, то (если q, то r ) эквивалентно тому, что если p и q , то r
Тавтология (1)	$p$ ⟚ $(p\lor p)$	p верно, эквивалентно. для p верно или p верно
Тавтология (2)	$p$ ⟚ $(p\land p)$	p верно, эквивалентно. для p верно и p верно
Третье не дано (Закон исключенного третьего)	$\models (p\lor \neg p)$	р или не р правда
Закон непротиворечия	$\models \neg (p\land \neg p)$	p , а не p — ложь, это истинное утверждение
Взрыв	$(p\land \neg p)\models q$	р и не р ; поэтому q

Синтаксическое доказательство посредством естественной дедукции

Основная статья: Естественный вычет

Естественный вывод , поскольку это метод синтаксического доказательства, определяется путем предоставления правил вывода (также называемых правилами доказательства ). для языка с типичным набором связок $\{-,\&,\lor ,\to ,\leftrightarrow \}$; никакие аксиомы, кроме этих правил, не используются. Правила описаны ниже, а затем приводится подтверждающий пример.

Стили обозначений

Разные авторы в некоторой степени различаются относительно того, какие правила вывода они предлагают, что будет отмечено. Однако более поразительным для внешнего вида доказательства являются различия в стилях обозначений. Обозначение § Генцена , которое было рассмотрено ранее для краткого рассуждения, на самом деле может быть сложено для получения больших древовидных доказательств естественного вывода. — не путать с «деревьями истинности», другим названием аналитических таблиц . Существует также стиль Станислава Ясковского , где формулы в доказательстве записываются внутри различных вложенных блоков. и существует упрощение стиля Ясковского благодаря Фредрику Фитчу ( обозначение Fitch ), где рамки упрощены до простых горизонтальных линий под введением предположений и вертикальных линий слева от строк, которые находятся под предположением. Наконец, есть единственный стиль обозначений, который фактически будет использоваться в этой статье, и принадлежит Патрику Суппесу . но был очень популяризирован Э. Дж. Леммоном и Бенсоном Мейтсом . Этот метод имеет то преимущество, что графически он наименее трудоемкий в создании и отображении, что сделало его естественным выбором для редактора , написавшего эту часть статьи, который не понимал сложных команд LaTeX , которые потребуются для создания доказательства другими методами.

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

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

Правила естественного вывода, созданные, в конечном счете, Генценом , приведены ниже. Существует десять примитивных правил доказательства, которые представляют собой правило предположения , плюс четыре пары правил введения и исключения для бинарных связок, а также правило reductio ad adbsurdum . Дизъюнктивный силлогизм можно использовать как более простую альтернативу правильному ∨-исключению, а MTT и DN — это обычно заданные правила, хотя они не примитивны.

Список правил вывода

Имя правила	Альтернативные названия	Аннотация	Успенский набор	Заявление
Правило предположений	Предположение	А	Текущий номер строки.	На любой стадии аргументации вводите предложение как предположение аргумента.
Знакомство с союзом	Знакомство с амперсандом, союз (CONJ)	м, н и я	Объединение наборов допущений в строках m и n .	От $\varphi$ и $\psi$ в строках m и n сделайте вывод $\varphi ~\&~\psi$.
Устранение союза	Упрощение (S), устранение амперсанда	мне	То же, что и в строке m .	От $\varphi ~\&~\psi$ в строке m сделайте вывод $\varphi$ и $\psi$.
Введение в дизъюнкцию	Дополнение (ДОБАВИТЬ)	м ∨I	То же, что и в строке m .	От $\varphi$ в строке m сделайте вывод $\varphi \lor \psi$, что бы ни $\psi$ может быть.
Устранение дизъюнкции	Устранение клина, дилемма (DL)	j,k,l,m,n ∨E	Линии j,k,l,m,n .	От $\varphi \lor \psi$ в строке j и предположение о $\varphi$ в строке k и вывод $\chi$ от $\varphi$ в строке l и предположение о $\psi$ в строке m и вывод $\chi$ от $\psi$ в строке n сделайте вывод $\chi$.
Дизъюнктивный силлогизм	Устранение клина (∨E), метод удаления и размещения (MTP)	м,н ДС	Объединение наборов допущений в строках m и n .	От $\varphi \lor \psi$ на линии м и $-\varphi$ в строке n сделайте вывод $\psi$; от $\varphi \lor \psi$ на линии м и $-\psi$ в строке n сделайте вывод $\varphi$.
Устранение стрелы	настройка режима (МПП), настройка режима (МП), условное исключение	м, н →Е	Объединение наборов допущений в строках m и n .	От $\varphi \to \psi$ в строке m и $\varphi$ в строке n сделайте вывод $\psi$.
Знакомство со стрелкой	Условное доказательство (CP), условное введение	п, →I (м)	Все в предположении, заданном в строке n , за исключением m , строки, где предполагался антецедент.	От $\psi$ в строке n , что следует из предположения о $\varphi$ в строке m сделайте вывод $\varphi \to \psi$.
Доведение до абсурда	Косвенное доказательство (IP), введение отрицания (−I), устранение отрицания (-E)	м,   н   РАА   (к)	Объединение наборов предположений в строках m и n , исключая k (опровергнутое предположение).	Из приговора и его отрицания в строках m и n сделайте вывод об отрицании любого предположения, появляющегося в доказательстве (в строке k ).
Знакомство с двойной стрелкой	Двуусловное определение ( Df ↔), двуусловное введение	м, н ↔ я	Объединение наборов допущений в строках m и n .	От $\varphi \to \psi$ и $\psi \to \varphi$ в строках m и n сделайте вывод $\varphi \leftrightarrow \psi$.
Устранение двойной стрелки	Двуусловное определение ( Df ↔), двуусловное исключение	м ↔ Е	То же, что и в строке m .	От $\varphi \leftrightarrow \psi$ в строке m сделайте вывод либо $\varphi \to \psi$ или $\psi \to \varphi$.
Двойное отрицание	Устранение двойного отрицания	м Ду	То же, что и в строке m .	От $--\varphi$ в строке m сделайте вывод $\varphi$.
Способ снятия удаления	Отличный режим (МТ)	м, н МТТ	Объединение наборов допущений в строках m и n .	От $\varphi \to \psi$ в строке m и $-\psi$ в строке n сделайте вывод $-\varphi$.

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

Доказательство ниже выводит $-P$ от $P\to Q$ и $-Q$ используя только MPP и RAA , что показывает, что MTT не является примитивным правилом, поскольку его можно вывести из этих двух других правил.

Вывод MTT из MPP и RAA

Успенский набор	Номер строки	Доказательное предложение	Аннотация
1	1	$P\to Q$	А
2	2	$-Q$	А
3	3	$P$	А
1 , 3	4	$Q$	1 , 3 →E
1 , 2	5	$-P$	2 , 4 РАА

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

Основная статья: Аксиоматическая система (логика)

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

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

Фреге Концептуальное письмо

Хотя аксиоматическое доказательство использовалось со времен знаменитого древнегреческого учебника « , Евклида Элементы геометрии» в логике высказываний оно восходит к Готтлоба Фреге года 1879 «Begriffsschrift» . Система Фреге использовала в качестве связок только импликацию и отрицание . и у него было шесть аксиом, какие это были:

• Предложение 1: $a\supset (b\supset a)$
• Предложение 2: $(c\supset (b\supset a))\supset ((c\supset b)\supset (c\supset a))$
• Предложение 8: $(d\supset (b\supset a))\supset (b\supset (d\supset a))$
• Предложение 28: $(b\supset a)\supset (\neg a\supset \neg b)$
• Предложение 31: $\neg \neg a\supset a$
• Предложение 41: $a\supset \neg \neg a$

Они использовались Фреге вместе с modus ponens и правилом замены (которое использовалось, но никогда не было точно сформулировано), чтобы дать полную и последовательную аксиоматизацию классической истинностно-функциональной логики высказываний.

Лукасевича _{П 2}

Ян Лукасевич показал, что в системе Фреге «третья аксиома является лишней, поскольку ее можно вывести из двух предыдущих аксиом, и что последние три аксиомы можно заменить одним предложением $CCNpNqCpq$". Лукасевича Что, переведя из польской записи в современную систему обозначений, означает: $(\neg p\rightarrow \neg q)\rightarrow (p\rightarrow q)$. Следовательно, Лукасевичу приписывают с этой системой трех аксиом:

• $p\to (q\to p)$
• $(p\to (q\to r))\to ((p\to q)\to (p\to r))$
• $(\neg p\to \neg q)\to (q\to p)$

Как и система Фреге, эта система использует правило замены и использует modus ponens в качестве правила вывода. Точно такую ​​же систему предложил (с явным правилом замены) Алонсо Чёрч , который назвал ее системой P _2, и способствовал его популяризации.

Схематическая форма Р ₂

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

• $\varphi \to (\psi \to \varphi )$
• $(\varphi \to (\psi \to \chi ))\to ((\varphi \to \psi )\to (\varphi \to \chi ))$
• $(\neg \varphi \to \neg \psi )\to (\psi \to \varphi )$

Схематическая версия P ₂ приписывается Джону фон Нейману , и используется в базе данных формальных доказательств Metamath «set.mm». Его также приписывают Гильберту . и назван ${\mathcal {H}}$ в этом контексте.

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

В качестве примера доказательство $A\to A$ в P ₂ приведен ниже. Во-первых, аксиомам даны имена:

(А1) $(p\to (q\to p))$

(А2) $((p\to (q\to r))\to ((p\to q)\to (p\to r)))$

(А3) $((\neg p\to \neg q)\to (q\to p))$

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

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

Решатели

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

См. также

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

• Логика первого порядка
• Пропозициональная логика второго порядка
• Логика второго порядка
• Логика высшего порядка

Связанные темы

• Булева алгебра (логика)
• Булева алгебра (структура)
• Темы булевой алгебры
• Логический домен
• Булева функция
• Логическая функция
• Категорическая логика
• Комбинационная логика
• Комбинаторная логика
• Концептуальный график
• Дизъюнктивный силлогизм
• Существенный граф
• Эквациональная логика
• Экзистенциальный граф
• Исчисление высказываний Фреге
• Импликативное исчисление высказываний
• Интуиционистское исчисление высказываний
• Жан Буридан
• Законы формы
• Список логических символов
• Логический график
• Логическое НО
• Логическое значение
• Математическая логика
• Операция (математика)
• Павел Венецианский
• Закон Пирса
• Петр Испанский (автор)
• Пропозициональная формула
• Симметричная разница
• Тавтология (правило вывода)
• Функция истины
• Таблица истинности
• Уолтер Берли
• Уильям Шервудский

Дальнейшее чтение

• Браун, Фрэнк Маркхэм (2003), Булево рассуждение: логика булевых уравнений , 1-е издание, Kluwer Academic Publishers, Норвелл, Массачусетс. 2-е издание, Dover Publications, Минеола, Нью-Йорк.
• Чанг, CC и Кейслер, HJ (1973), Теория моделей , Северная Голландия, Амстердам, Нидерланды.
• Кохави, Цви (1978), Теория коммутации и конечных автоматов , 1-е издание, McGraw-Hill, 1970. 2-е издание, McGraw-Hill, 1978.
• Корфхаге, Роберт Р. (1974), Дискретные вычислительные структуры , Academic Press, Нью-Йорк, Нью-Йорк.
• Ламбек Дж. и Скотт П.Дж. (1986), Введение в категориальную логику высшего порядка , издательство Кембриджского университета, Кембридж, Великобритания.
• Мендельсон, Эллиот (1964), Введение в математическую логику , Компания Д. Ван Ностранда.

Связанные работы

• Хофштадтер, Дуглас (1979). Гёдель, Эшер, Бах: Вечная золотая коса . Основные книги . ISBN  978-0-465-02656-2 .

Внешние ссылки

• Клемент, Кевин К. (2006), «Пропозициональная логика», в книге Джеймса Физера и Брэдли Даудена (ред.), Интернет-энциклопедия философии , Eprint .
• Формальное исчисление предикатов содержит систематическое формальное развитие с аксиоматическим доказательством.
• forall x: введение в формальную логику П.Д. Магнуса охватывает формальную семантику и теорию доказательств для логики предложений.
• Глава 2 / Пропозициональная логика из «Логики в действии»
• Доказательство секвенциального исчисления высказываний в рамках проекта «Наюки». ( примечание : импликацию можно ввести в форме !X|Y, а секвенция может представлять собой одну формулу с префиксом > и без запятых)
• Пропозициональная логика — порождающая грамматика
• Пропозициональный калькулятор, который помогает понимать простые выражения.