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

Раздел логики

Исчисление высказываний ^[a] является разделом логики . ^[1] Его также называют пропозициональной логикой , ^[2] логикой утверждений , ^[1] исчислением высказываний , ^[3] логикой высказываний , ^[1] или иногда логикой нулевого порядка . ^{[4] [5]} Оно имеет дело с высказываниями ^[1] (которые могут быть истинными или ложными ) ^[6] и отношениями между высказываниями, ^[7] включая построение аргументов на их основе. ^[8] Составные высказывания образуются путем соединения высказываний логическими связками, представляющими функции истинности конъюнкции , дизъюнкции , импликации , биусловия и отрицания . ^{[9] [10] [11] [12] Некоторые} источники включают другие связки, как в таблице ниже.

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

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

Наиболее тщательно исследованной ветвью пропозициональной логики является классическая истинностно-функциональная пропозициональная логика , ^[1] в которой формулы интерпретируются как имеющие только одно из двух возможных значений истинности , истинностное значение истины или истинностное значение лжи . ^[15] Принцип двузначности и закон исключенного третьего поддерживаются. По сравнению с логикой первого порядка истинностно-функциональная пропозициональная логика считается логикой нулевого порядка . ^{[4] [5]}

История

Хотя пропозициональная логика (также называемая пропозициональным исчислением) была предложена более ранними философами, она была развита в формальную логику ( стоическую логику ) Хрисиппом в 3 веке до н. э. ^[16] и расширена его преемниками -стоиками . Логика была сосредоточена на предложениях . Это отличалось от традиционной силлогистической логики , которая фокусировалась на терминах . Однако большинство оригинальных трудов были утеряны ^[17] и в какой-то момент между 3 и 6 веками н. э. стоическая логика канула в Лету, чтобы воскреснуть только в 20 веке, в результате (повторного) открытия пропозициональной логики. ^[18]

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

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

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

Предложения

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

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

Пропозициональная логика имеет дело с утверждениями , которые определяются как повествовательные предложения, имеющие истинностное значение. ^{[25] [1]} Примерами утверждений могут быть:

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

Повествовательные предложения противопоставляются вопросам , таким как «Что такое Википедия?», и императивным утверждениям, таким как «Пожалуйста, добавьте цитаты для подтверждения утверждений в этой статье». ^{[26] [27]} Такие недекларативные предложения не имеют истинностного значения , ^[28] и рассматриваются только в неклассических логиках , называемых эротическими и императивными логиками .

Составление предложений с помощью союзов

В пропозициональной логике утверждение может содержать одно или несколько других утверждений в качестве частей. ^[1] Сложные предложения образуются из более простых предложений и выражают отношения между составными предложениями. ^[29] Это делается путем их объединения с помощью логических связок : ^{[29] [30]} основными типами сложных предложений являются отрицания , союзы , дизъюнкции , импликации и двусторонние условия , ^[29] которые образуются с помощью соответствующих связок для соединения предложений. ^{[31] [32]} В английском языке эти связки выражаются словами «and» ( конъюнкция ), «or» ( дизъюнкция ), «not» ( отрицание ), «if» ( материальное условное предложение ) и «if and only if» ( двусторонние условия ). ^{[1] [9]} Примерами таких сложных предложений могут быть:

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

Если в предложениях отсутствуют какие-либо логические связки, они называются простыми предложениями [ ^1] или атомарными предложениями ; ^[30] если они содержат одну или несколько логических связок, они называются сложными предложениями [ ^29] или молекулярными предложениями ^[30] .

Предложенные связки — это более широкая категория, которая включает логические связки. ^{[2] [30]} Предложенные связки — это любые языковые частицы, которые связывают предложения для создания нового сложного предложения, ^{[2] [30]} или которые склоняют одно предложение для создания нового предложения. ^[2] Логическая связка , или пропозициональная связка , — это разновидность позиционной связки с характерной особенностью: когда исходные предложения, с которыми она работает, являются (или выражают) суждениями , новое предложение, которое получается в результате ее применения, также является (или выражает) суждением . ^[2] Философы расходятся во мнениях о том, что именно является суждением, ^{[6] [2]} , а также о том, какие позиционные связки в естественных языках следует считать логическими связками. ^{[30] [2]} Предложенные связки также называются функторами предложений , ^[33] а логические связки также называются функторами истины . ^[33]

Аргументы

Аргумент определяется как пара вещей, а именно набор предложений, называемых посылками , [ ^c] и предложение, называемое заключением . ^{[34] [30]} [ ^33] Утверждается, что заключение следует из посылок, ^[33] а посылки утверждают, что они подтверждают заключение. ^[30]

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

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

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

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

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

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

Обоснованность и обоснованность

Аргумент действителен тогда и только тогда, когда необходимо , чтобы, если все его предпосылки истинны, его заключение было истинным. ^{[34] [37] [38]} С другой стороны, аргумент действителен тогда и только тогда, когда невозможно, чтобы все его предпосылки были истинными, а заключение ложным. ^{[38] [34]}

Обоснованность противопоставляется обоснованности . [ ^38] Аргумент обоснован тогда и только тогда, когда он обоснован и все его предпосылки истинны. ^{[34] [38]} В противном случае он необоснован . ^[38]

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

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

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

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

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

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

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

Заключение: ${\displaystyle Q}$

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

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

нотация Генцена

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

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

Этот метод отображения является обозначением Генцена для естественной дедукции и последовательного исчисления . ^[39] Посылки показаны над линией, называемой линией вывода , ^[11] разделенной запятой , которая указывает на комбинацию посылок. ^[40] Заключение написано под линией вывода. ^[11] Линия вывода представляет собой синтаксическое следствие , ^[11] иногда называемое дедуктивным следствием , ^[41] которое также обозначается знаком ⊢. ^{[42] [41]} Таким образом, вышесказанное можно также записать в одну строку как . ^[d] ${\displaystyle P\to Q,P\vdash Q}$

Синтаксическое следствие противопоставляется семантическому следствию , ^[43] которое обозначается знаком ⊧. ^{[42] [41]} В этом случае заключение следует синтаксически, поскольку предполагается естественное правило вывода modus ponens . Подробнее о правилах вывода см. в разделах о системах доказательств ниже.

Язык

Язык (обычно называемый ) ^{[44] [45] [30]} исчисления высказываний определяется в терминах: ^[2] [ ^10] ${\displaystyle {\mathcal {L}}}$

1. набор примитивных символов, называемых атомарными формулами , атомарными предложениями , ^{[35] [30]} атомами, ^[46] заполнителями , простыми формулами , ^[46] буквами предложений , буквами предложений , ^[35] или переменными , и
2. набор символов операторов, называемых связками , ^{[14] [1] [47]} логическими связками , ^[1] логическими операторами , ^[1] истинностно-функциональными связками, ^[1] истинностно-функторами , ^[33] или пропозициональными связками . ^[2]

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

Обычно синтаксис определяется рекурсивно всего несколькими определениями, как показано далее; некоторые авторы явно включают скобки в качестве знаков препинания при определении синтаксиса своего языка, ^{[30] [48],} в то время как другие используют их без комментариев. ^{[2] [10]} ${\displaystyle {\mathcal {L}}}$

Синтаксис

При наличии набора атомарных пропозициональных переменных , , , ..., и набора пропозициональных связок , , , ... , , , , ... , , , , ..., формула пропозициональной логики определяется рекурсивно следующими определениями: ^{[2] [10] [47] [e]} ${\displaystyle p_{1}}$ ${\displaystyle p_{2}}$ ${\displaystyle p_{3}}$ ${\displaystyle c_{1}^{1}}$ ${\displaystyle c_{2}^{1}}$ ${\displaystyle c_{3}^{1}}$ ${\displaystyle c_{1}^{2}}$ ${\displaystyle c_{2}^{2}}$ ${\displaystyle c_{3}^{2}}$ ${\displaystyle c_{1}^{3}}$ ${\displaystyle c_{2}^{3}}$ ${\displaystyle c_{3}^{3}}$

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

Определение 2 : Если — пропозициональная связка, а A, B, C, … — последовательность из m возможно, но не обязательно атомарных, возможно, но не обязательно различных формул, то результатом применения к A, B, C, … является формула. ${\displaystyle c_{n}^{m}}$ ${\displaystyle \langle }$ ${\displaystyle \rangle }$ ${\displaystyle c_{n}^{m}}$ ${\displaystyle \langle }$ ${\displaystyle \rangle }$

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

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

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

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

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

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

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

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

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

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

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

Однако некоторые авторы признают только две «пропозициональные константы» в своей формальной системе: специальный символ , называемый «истина», который всегда оценивается как True , и специальный символ , называемый «ложь», который всегда оценивается как False . ^{[54] [55] [56]} Другие авторы также включают эти символы с тем же значением, но считают их «функторами истинности с нулевым местом» ^[33] или, что эквивалентно, « нульарными связками». ^[47] ${\displaystyle \top }$ ${\displaystyle \bot }$

Семантика

Чтобы служить моделью логики данного естественного языка , формальный язык должен быть семантически интерпретирован. ^[30] В классической логике все предложения оцениваются как одно из двух значений истинности : Истина или Ложь . ^{[1] [57]} Например, « Википедия — это бесплатная онлайн-энциклопедия , которую может редактировать каждый» оценивается как Истина , ^[58] тогда как «Википедия — это бумажная энциклопедия » оценивается как Ложь . ^[59]

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

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

Для данного языка интерпретация ^[61] оценка [ 48 ^] или случай ^{[30] [g]} — это присвоение семантических значений каждой формуле из . ^[30] Для формального языка классической логики случай определяется как присвоение каждой формуле из одного или другого, но не обоих, значений истинности , а именно истины ( T или 1) и ложности ( F или 0). ^{[62] [63]} Интерпретация, которая следует правилам классической логики, иногда называется булевой оценкой [ ^{48] [64]} Интерпретация формального языка для классической логики часто выражается в терминах таблиц истинности ^{[65] [1]} Поскольку каждой формуле присваивается только одно значение истинности, интерпретацию можно рассматривать как функцию , областью определения которой является , а диапазоном — ее набор семантических значений [ ^2] или ^[30 ] ${\displaystyle {\mathcal {L}}}$ ${\displaystyle {\mathcal {L}}}$ ${\displaystyle {\mathcal {L}}}$ ${\displaystyle {\mathcal {L}}}$ ${\displaystyle {\mathcal {V}}=\{{\mathsf {T}},{\mathsf {F}}\}}$ ${\displaystyle {\mathcal {V}}=\{1,0\}}$

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

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

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

Интерпретация напрямую присваивает семантические значения атомарным формулам . ^{[61] [30]} Молекулярным формулам присваивается функция значения их составляющих атомов в соответствии с используемой связкой; ^{[61] [30]} связки определяются таким образом, что истинностное значение предложения, образованного из атомов со связками, зависит от истинностных значений атомов, к которым они применяются, и только от них. ^{[61] [30]} Это предположение Колин Хаусон называет предположением об истинностной функциональности связок . ^[35]

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

Поскольку логические связки определяются семантически только в терминах значений истинности , которые они принимают, когда пропозициональные переменные , к которым они применяются, принимают одно из двух возможных значений истинности, ^{[1] [30],} семантическое определение связок обычно представляется в виде таблицы истинности для каждой из связок, ^{[1] [30] [66]} , как показано ниже:

Эта таблица охватывает каждую из пяти основных логических связок : ^{[9] [10] [11] [12]} конъюнкция (здесь обозначается как p ∧ q), дизъюнкция (p ∨ q), импликация (p → q), биусловная (p ↔ q) и отрицание (¬p или ¬q, в зависимости от обстоятельств). Этого достаточно для определения семантики каждого из этих операторов. ^{[1] [67] [30]} Для получения дополнительных таблиц истинности для большего количества различных видов связок см. статью « Таблица истинности ».

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

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

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

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

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

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

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

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

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

• Истина в конкретном случае: [ ^30] Предложение истинно при интерпретации , если присваивает значение истинности T . ^[63] [ ^65] Если истинно при , то называется моделью . ^[65] ${\displaystyle \varphi }$ ${\displaystyle {\mathcal {L}}}$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle \varphi }$ ${\displaystyle \varphi }$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle \varphi }$
• Ложность-в-случае: ^[30] ложно при интерпретации тогда и только тогда, когда истинно при . ^{[65] [75] [30]} Это определение ложности-в-случае как «истины отрицания». ^[30] Ложность-в-случае также может быть определена определением «дополнения»: ложно при интерпретации тогда и только тогда, когда не истинно при . ^{[63] [65]} В классической логике эти определения эквивалентны, но в неклассической логике они не эквивалентны. ^[30] ${\displaystyle \varphi }$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle \neg \varphi }$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle \varphi }$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle \varphi }$ ${\displaystyle {\mathcal {I}}}$
• Семантическое следствие: Предложение является семантическим следствием ( ) предложения, если не существует интерпретации, при которой является истинным и не является истинным. ^{[63] [65] [30]} ${\displaystyle \psi }$ ${\displaystyle {\mathcal {L}}}$ ${\displaystyle \varphi \models \psi }$ ${\displaystyle \varphi }$ ${\displaystyle \varphi }$ ${\displaystyle \psi }$
• Действительная формула (тавтология): Предложение является логически действительным ( ) , ^[j] или тавтологией , ^{[76] [77] [48]} если оно истинно при любой интерпретации, ^{[63] [65]} или истинно в каждом случае. ^[30] ${\displaystyle \varphi }$ ${\displaystyle {\mathcal {L}}}$ ${\displaystyle \models \varphi }$
• Согласованное предложение: Предложение согласовано , если оно истинно хотя бы при одной интерпретации. Оно непоследовательно, если оно непоследовательно. ^{[63] [65]} Несогласованная формула также называется самопротиворечивой , ^[1] и считается самопротиворечивой , [ ^1] или просто противоречием , ^{[78] [79] [80]} хотя это последнее название иногда зарезервировано специально для утверждений формы . ^[1] ${\displaystyle {\mathcal {L}}}$ ${\displaystyle (p\land \neg p)}$

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

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

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

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

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

Системы доказательств в пропозициональной логике можно в целом классифицировать на системы семантических доказательств и системы синтаксических доказательств [ ^{83] [84] [85]} в зависимости от вида логического следствия , на котором они основаны: системы семантических доказательств опираются на семантическое следствие ( ), ^[86] тогда как системы синтаксических доказательств опираются на синтаксическое следствие ( ). ^[87] Семантическое следствие имеет дело с истинностными значениями предложений во всех возможных интерпретациях, тогда как синтаксическое следствие касается вывода заключений из предпосылок на основе правил и аксиом в рамках формальной системы. ^[88] В этом разделе дается очень краткий обзор видов систем доказательств со ссылками на соответствующие разделы этой статьи по каждой из них, а также на отдельные статьи Википедии по каждой из них. ${\displaystyle \varphi \models \psi }$ ${\displaystyle \varphi \vdash \psi }$

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

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

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

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

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

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

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

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

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

Правила исчисления последовательностей высказываний LK в нотации Генцена

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

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

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

Натуральный вычет

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

Последовательное исчисление

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

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

Используя семантическую концепцию валидности (истинности в любой интерпретации), можно доказать валидность формулы, используя таблицу истинности , которая дает каждую возможную интерпретацию (присвоение значений истинности переменным) формулы. ^{[90] [46] [33]} Если и только если все строки таблицы истинности оказываются истинными, формула семантически валидна (истинна в любой интерпретации). ^{[90] [46]} Кроме того, если (и только если) валидна, то является непоследовательной. ^{[78] [79] [80]} ${\displaystyle \neg \varphi }$ ${\displaystyle \varphi }$

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

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

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

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

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

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

${\displaystyle {\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 означает, что дает оба , тогда как разветвляется на . Обозначение следует понимать аналогично для правил 3 и 4. ^[48] Часто в таблицах для классической логики обозначение знаковой формулы упрощается, так что записывается просто как , и как , что объясняет название правила 1 « Правило двойного отрицания ». ^{[35] [66]} ${\displaystyle T(X\land Y)}$ ${\displaystyle TX,TY}$ ${\displaystyle F(X\land Y)}$ ${\displaystyle FX,FY}$ ${\displaystyle T\varphi }$ ${\displaystyle \varphi }$ ${\displaystyle F\varphi }$ ${\displaystyle \neg \varphi }$

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

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

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

Используя методы семантической проверки, такие как таблицы истинности или семантические таблицы, для проверки тавтологий и семантических следствий, можно показать, что в классической логике следующие классические формы аргументов являются семантически допустимыми, т. е. эти тавтологии и семантические следствия имеют место. ^[33] Мы используем ⟚ для обозначения эквивалентности и , то есть как сокращение для и ; ^[33] в качестве помощи при чтении символов дается описание каждой формулы. Описание читает символ ⊧ (называемый «двойным турникетом») как «следовательно», что является его обычным прочтением, ^{[33] [100]} хотя многие авторы предпочитают читать его как «влечет», ^{[33] [101]} или как «модели». ^[102] ${\displaystyle \varphi }$ ${\displaystyle \psi }$ ${\displaystyle \varphi }$ ${\displaystyle \psi }$ ${\displaystyle \varphi \models \psi }$ ${\displaystyle \psi \models \varphi }$

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

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

Стили нотации

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

Доказательство , тогда изложенное в соответствии со стилем обозначений Саппса–Леммона , ^[39] представляет собой последовательность строк, содержащих предложения, [ ^34] где каждое предложение является либо предположением, либо результатом применения правила доказательства к более ранним предложениям в последовательности. ^[34] Каждая строка доказательства состоит из предложения доказательства вместе с его аннотацией , его набором предположений и текущим номером строки . ^[34] Набор предположений перечисляет предположения, от которых зависит данное предложение доказательства, на которые ссылаются номера строк. ^[34] Аннотация указывает, какое правило доказательства было применено и к каким более ранним строкам, чтобы получить текущее предложение. ^[34] См. пример доказательства естественной дедукции §.

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

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

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

Приведенное ниже доказательство ^[34] выводится только из MPP и RAA и использует их , что показывает, что MTT не является примитивным правилом, поскольку его можно вывести из этих двух других правил. ${\displaystyle -P}$ ${\displaystyle P\to Q}$ ${\displaystyle -Q}$

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

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

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

ФрегеBegriffsschrift

Хотя аксиоматическое доказательство использовалось со времен знаменитого древнегреческого учебника «Элементы геометрии» Евклида , в пропозициональной логике оно восходит к Begriffsschrift Готлоба Фреге 1879 года . ^{[33] [108]} Система Фреге использовала в качестве связок только импликацию и отрицание , ^[2] и имела шесть аксиом, ^[108] а именно: ^{[109] [110]}

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

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

Лукасевич P2

Ян Лукасевич показал, что в системе Фреге «третья аксиома излишняя, поскольку ее можно вывести из двух предыдущих аксиом, и что последние три аксиомы можно заменить одним предложением ». ^{[110] Что, взятое из} польской записи Лукасевича в современную запись, означает . Таким образом, Лукасевичу приписывают ^[108] эту систему из трех аксиом: ${\displaystyle CCNpNqCpq}$ ${\displaystyle (\neg p\rightarrow \neg q)\rightarrow (p\rightarrow q)}$

• ${\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 в качестве правила вывода. ^[108] Точно такую ​​же систему (с явным правилом подстановки) дал Алонзо Чёрч , ^[111] который назвал её системой P2 _[ ^{111] [112]} и помог популяризировать её. ^[112]

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

Можно избежать использования правила подстановки, представив аксиомы в схематической форме, используя их для создания бесконечного набора аксиом. Следовательно, используя греческие буквы для представления схем (металогических переменных, которые могут обозначать любые правильно сформированные формулы ), аксиомы задаются как: ^{[33] [112]}

• ${\displaystyle \varphi \to (\psi \to \varphi )}$
• ${\displaystyle (\varphi \to (\psi \to \chi ))\to ((\varphi \to \psi )\to (\varphi \to \chi ))}$
• ${\displaystyle (\neg \varphi \to \neg \psi )\to (\psi \to \varphi )}$

Схематическая версия P ₂ приписывается Джону фон Нейману [ ^108] и используется в базе данных формальных доказательств Metamath "set.mm". ^[112] Она также приписывается Гильберту ^[113] и названа в этом контексте ^[113] ${\displaystyle {\mathcal {H}}}$

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

В качестве примера ниже приведено доказательство в P _2. Сначала аксиомам даны имена: ${\displaystyle A\to A}$

(А1) ${\displaystyle (p\to (q\to p))}$

(А2) ${\displaystyle ((p\to (q\to r))\to ((p\to q)\to (p\to r)))}$

(А3) ${\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)

Решатели

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

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

• Философский портал

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

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

Похожие темы

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

Примечания

1. Многие источники пишут это с определенным артиклем, как исчисление высказываний, в то время как другие просто называют это исчислением высказываний без артикля.
2. «Или оба» ясно показывает ^[30] , что это логическая дизъюнкция , а не исключающее или , которое более распространено в английском языке.
3. Набор предпосылок может быть пустым набором ; ^{[33] [34]} аргумент из пустого набора предпосылок действителен тогда и только тогда, когда заключение является тавтологией . [ ^{33] [34]}
4. Турникет, для синтаксического следования, имеет более низкий приоритет, чем запятая, которая представляет комбинацию посылок, которая, в свою очередь, имеет более низкий приоритет, чем стрелка, используемая для материальной импликации; поэтому для интерпретации этой формулы скобки не нужны. ^[40]
5. Здесь дан очень общий и абстрактный синтаксис, следующий обозначениям в SEP, ^[2], но включающий третье определение, которое очень часто дается явно другими источниками, такими как Gillon, ^[10] Bostock, ^[33] Allen & Hand, ^[34] и многими другими. Как отмечено в другом месте статьи, языки по-разному составляют свой набор атомарных пропозициональных переменных из заглавных или строчных букв (часто фокусируясь на P/p, Q/q и R/r), с подстрочными цифрами или без них; и в свой набор связок они могут включать либо полный набор из пяти типичных связок, , либо любые из его функционально полных подмножеств. (И, конечно, они также могут использовать любые варианты обозначений этих связок.) ${\displaystyle \{\neg ,\land ,\lor ,\to ,\leftrightarrow \}}$
6. Обратите внимание, что фраза «принцип композиции» относилась к другим вещам в других контекстах, и даже в контексте логики, поскольку Бертран Рассел использовал ее для обозначения принципа, согласно которому «предложение, подразумевающее каждое из двух предложений, подразумевает их оба». ^[49]
7. Название «интерпретация» используется некоторыми авторами, а название «случай» — другими авторами. Эта статья будет безразличной и будет использовать любое из них, поскольку она редактируется совместно и нет единого мнения о том, какую терминологию следует принять.
8. Истинно-функционально полный набор связок ^[2] также называется просто функционально полным , или адекватным для истинно-функциональной логики , ^[35] или выразительно адекватным , ^[72] или просто адекватным . ^{[35] [72]}
9. Некоторые из этих определений используют слово «интерпретация» и говорят о том, что предложения/формулы истинны или ложны «под» ним, а некоторые будут использовать слово «случай» и говорить о том, что предложения/формулы истинны или ложны «в» нем. Опубликованные надежные источники ( WP:RS ) использовали оба вида терминологических соглашений, хотя обычно данный автор будет использовать только одно из них. Поскольку эта статья редактировалась совместно и нет единого мнения о том, какое соглашение использовать, эти вариации в терминологии были оставлены.
10. Традиционно , без ничего слева от турникета, используется для обозначения тавтологии. Это можно интерпретировать как то, что является семантическим следствием пустого множества формул, т. е. , но с пустыми скобками, опущенными для простоты; ^[33] что равносильно утверждению, что это тавтология, т. е. что нет интерпретации, при которой она ложна. ^[33] ${\displaystyle \models \varphi }$ ${\displaystyle \varphi }$ ${\displaystyle \{\}\models \varphi }$
11. Для упрощения формулировки правила слово «отрицание» здесь используется следующим образом: отрицание формулы , которая не является отрицанием , есть , тогда как отрицание , , имеет два отрицания , а именно, и . ^[34] ${\displaystyle \varphi }$ ${\displaystyle -\varphi }$ ${\displaystyle -\varphi }$ ${\displaystyle \varphi }$ ${\displaystyle --\varphi }$

Ссылки

1. "Пропозициональная логика | Интернет-энциклопедия философии" . Получено 22 марта 2024 г.
2. Franks, Curtis (2023), "Propositional Logic", в Zalta, Edward N.; Nodelman, Uri (ред.), The Stanford Encyclopedia of Philosophy (ред. осень 2023 г.), Metaphysics Research Lab, Stanford University , получено 22 марта 2024 г.
3. Weisstein, Eric W. "Propositional Calculus". mathworld.wolfram.com . Получено 22 марта 2024 г. .
4. Белоглавек, Радим; Даубен, Джозеф Уоррен; Клир, Джордж Дж. (2017). Нечеткая логика и математика: историческая перспектива . Нью-Йорк, Нью-Йорк, Соединенные Штаты Америки: Oxford University Press. стр. 463. ISBN 978-0-19-020001-5.
5. Manzano, María (2005). Расширения логики первого порядка . Кембриджские трактаты по теоретической информатике (цифровая печать первой версии в мягкой обложке, ред.). Кембридж: Cambridge University Press. стр. 180. ISBN 978-0-521-35435-6.
6. McGrath, Matthew; Frank, Devin (2023), "Propositions", в Zalta, Edward N.; Nodelman, Uri (ред.), The Stanford Encyclopedia of Philosophy (зимнее издание 2023 г.), Metaphysics Research Lab, Stanford University , получено 22 марта 2024 г.
7. "Предикатная логика". www3.cs.stonybrook.edu . Получено 22 марта 2024 г. .
8. "Философия 404: Лекция пятая". www.webpages.uidaho.edu . Получено 22 марта 2024 г. .
9. "3.1 Propositional Logic". www.teach.cs.toronto.edu . Получено 22 марта 2024 г. .
10. Дэвис, Стивен; Гиллон, Брендан С., ред. (2004). Семантика: хрестоматия . Нью-Йорк: Oxford University Press. ISBN 978-0-19-513697-5.
11. Платон, Ян фон (2013). Элементы логического рассуждения (1-е изд.). Кембридж: Cambridge University Press. С. 9, 32, 121. ISBN 978-1-107-03659-8.
12. "Propositional Logic". www.cs.miami.edu . Получено 22 марта 2024 г. .
13. Платон, Ян фон (2013). Элементы логического рассуждения (1-е изд.). Кембридж: Cambridge University Press. стр. 9. ISBN 978-1-107-03659-8.
14. Weisstein, Eric W. "Connective". mathworld.wolfram.com . Получено 22 марта 2024 г. .
15. "Пропозициональная логика | Brilliant Math & Science Wiki". brilliant.org . Получено 20 августа 2020 г. .
16. Бобзиен, Сюзанна (1 января 2016 г.). «Древняя логика». В Zalta, Edward N. (ред.). Стэнфордская энциклопедия философии. Исследовательская лаборатория метафизики, Стэнфордский университет – через Стэнфордскую энциклопедию философии.
17. "Пропозициональная логика | Интернет-энциклопедия философии" . Получено 20 августа 2020 г.
18. Бобзиен, Сюзанна (2020), «Древняя логика», в Zalta, Edward N. (ред.), The Stanford Encyclopedia of Philosophy (лето 2020 г.), Metaphysics Research Lab, Stanford University , получено 22 марта 2024 г.
19. Peckhaus, Volker (1 января 2014 г.). «Влияние Лейбница на логику 19-го века». В Zalta, Edward N. (ред.). The Stanford Encyclopedia of Philosophy. Metaphysics Research Lab, Stanford University – через Stanford Encyclopedia of Philosophy.
20. Херли, Патрик (2007). Краткое введение в логику, 10-е издание . Wadsworth Publishing. стр. 392.
21. Бет, Эверт В.; «Семантическое следствие и формальная выводимость», серия: Mededlingen van de Koninklijke Nederlandse Akademie van Wetenschappen, Afdeling Letterkunde, Nieuwe Reeks, vol. 18, нет. 13, Северо-Голландский Уитг. Mij., Амстердам, 1955, стр. 309–42. Перепечатано в Jaakko Intikka (ed.) The Philosophy of Mathematics , Oxford University Press, 1969.
22. Истина во Фреге
23. "Рассел: Журнал исследований Бертрана Рассела".
24. Анеллис, Ирвинг Х. (2012). «Истинно-функциональный анализ Пирса и происхождение таблицы истинности». История и философия логики . 33 : 87–97. doi :10.1080/01445340.2011.621702. S2CID  170654885.
25. "Part2Mod1: ЛОГИКА: Утверждения, Отрицания, Квантификаторы, Таблицы истинности". www.math.fsu.edu . Получено 22 марта 2024 г. .
26. "Lecture Notes on Logical Organization and Critical Thinking". www2.hawaii.edu . Получено 22 марта 2024 г. .
27. "Логические связки". sites.millersville.edu . Получено 22 марта 2024 г. .
28. "Lecture1". www.cs.columbia.edu . Получено 22 марта 2024 г. .
29. "Введение в логику - Глава 2". intrologic.stanford.edu . Получено 22 марта 2024 г. .
30. Beall, Джеффри К. (2010). Логика: основы (1. изд.). Лондон: Рутледж. стр. 6, 8, 14–16, 19–20, 44–48, 50–53, 56. ISBN. 978-0-203-85155-5.
31. "Watson". watson.latech.edu . Получено 22 марта 2024 г. .
32. "Введение в теоретическую информатику, Глава 1". www.cs.odu.edu . Получено 22 марта 2024 г. .
33. Bostock, David (1997). Промежуточная логика . Oxford : New York: Clarendon Press ; Oxford University Press. стр. 4–5, 8–13, 18–19, 22, 27, 29, 191, 194. ISBN 978-0-19-875141-0.
34. Аллен, Колин ; Хэнд, Майкл (2022). Букварь по логике (3-е изд.). Кембридж, Массачусетс: MIT Press. ISBN 978-0-262-54364-4.
35. Хаусон, Колин (1997). Логика с деревьями: введение в символическую логику . Лондон; Нью-Йорк: Routledge. стр. ix, x, 5–6, 15–16, 20, 24–29, 38, 42–43, 47. ISBN 978-0-415-13342-5.
36. Стойнич, Уна (2017). «Modus Ponens человека: модальность, связность и логика». Философия и феноменологические исследования . 95 (1): 167–214. doi :10.1111/phpr.12307. ISSN  0031-8205. JSTOR  48578954.
37. Дутил Новаес, Катарина (2022), «Аргумент и аргументация», в Zalta, Edward N.; Nodelman, Uri (ред.), The Stanford Encyclopedia of Philosophy (ред. осень 2022 г.), Metaphysics Research Lab, Stanford University , получено 5 апреля 2024 г.
38. "Validity and Soundness | Internet Encyclopedia of Philosophy" . Получено 5 апреля 2024 г. .
39. Пеллетье, Фрэнсис Джеффри; Хейзен, Аллен (2024), «Естественные системы дедукции в логике», в Zalta, Edward N.; Nodelman, Uri (ред.), The Stanford Encyclopedia of Philosophy (весеннее издание 2024 г.), Metaphysics Research Lab, Stanford University , получено 22 марта 2024 г.
40. Restall, Greg (2018), «Substructural Logics», в Zalta, Edward N. (ред.), The Stanford Encyclopedia of Philosophy (весна 2018 г.), Metaphysics Research Lab, Stanford University , получено 22 марта 2024 г.
41. "Компактность | Интернет-энциклопедия философии" . Получено 22 марта 2024 г.
42. "Темы лекций для студентов, изучающих дискретную математику". math.colorado.edu . Получено 22 марта 2024 г. .
43. Paseau, Alexander; Pregel, Fabian (2023), «Дедуктивизм в философии математики», в Zalta, Edward N.; Nodelman, Uri (ред.), The Stanford Encyclopedia of Philosophy (ред. осень 2023 г.), Metaphysics Research Lab, Stanford University , получено 22 марта 2024 г.
44. "Компактность | Интернет-энциклопедия философии" . Получено 22 марта 2024 г. .
45. Demey, Lorenz; Kooi, Barteld; Sack, Joshua (2023), «Логика и вероятность», в Zalta, Edward N.; Nodelman, Uri (ред.), The Stanford Encyclopedia of Philosophy (ред. осень 2023 г.), Metaphysics Research Lab, Stanford University , получено 22 марта 2024 г.
46. Клини, Стивен Коул (2002). Математическая логика (ред. Дувра). Минеола, Нью-Йорк: Dover Publications. ISBN 978-0-486-42533-7.
47. Humberstone, Lloyd (2011). Связующие. Кембридж, Массачусетс: MIT Press. С. 118, 702. ISBN 978-0-262-01654-4. OCLC  694679197.
48. Smullyan, Raymond M. (1995). Логика первого порядка . Нью-Йорк: Dover. С. 5, 10–11, 14. ISBN 978-0-486-68370-6.
49. Рассел, Бертран (2010). Принципы математики . Классика Routledge. Лондон: Routledge. С. 17. ISBN 978-0-415-48741-2.
50. Hodges, Wilfrid (1977). Логика . Harmondsworth; Нью-Йорк: Penguin. стр. 80–85. ISBN 978-0-14-021985-2.
51. Ханссон, Свен Ове; Хендрикс, Винсент Ф. (2018). Введение в формальную философию . Springer бакалаврские тексты по философии. Cham: Springer. стр. 38. ISBN 978-3-030-08454-7.
52. Айяла-Ринкон, Маурисио; де Моура, Флавио LC (2017). Прикладная логика для специалистов по информатике. Темы бакалавриата по информатике. Springer. стр. 2. doi :10.1007/978-3-319-51653-0. ISBN 978-3-319-51651-6.
53. Ланде, Нельсон П. (2013). Классическая логика и ее кроличьи норы: первый курс . Индианаполис, Индиана: Hackett Publishing Co., Inc. стр. 20. ISBN 978-1-60384-948-7.
54. Голдрей, Дерек (2005). Исчисление высказываний и предикатов: модель аргумента . Лондон: Springer. С. 69. ISBN 978-1-85233-921-0.
55. "Propositional Logic". www.cs.rochester.edu . Получено 22 марта 2024 г. .
56. "Исчисление высказываний". www.cs.cornell.edu . Получено 22 марта 2024 г. .
57. Шрамко, Ярослав; Вансинг, Генрих (2021), «Ценности истины», в Zalta, Edward N. (ред.), The Stanford Encyclopedia of Philosophy (зима 2021 г. ред.), Metaphysics Research Lab, Stanford University , получено 23 марта 2024 г.
58. Меткалф, Дэвид; Пауэлл, Джон (2011). «Следует ли врачам отвергать Википедию?». Журнал Королевского медицинского общества . 104 (12): 488–489. doi :10.1258/jrsm.2011.110227. ISSN  0141-0768. PMC 3241521. PMID 22179287  . 
59. Айерс, Фиби; Мэтьюз, Чарльз; Йейтс, Бен (2008). Как работает Википедия: и как вы можете стать ее частью. Сан-Франциско: No Starch Press. стр. 22. ISBN 978-1-59327-176-3. OCLC  185698411.
60. Шапиро, Стюарт; Коури Киссель, Тереза ​​(2024), «Классическая логика», в Zalta, Edward N.; Nodelman, Uri (ред.), The Stanford Encyclopedia of Philosophy (весеннее издание 2024 г.), Metaphysics Research Lab, Stanford University , получено 25 марта 2024 г.
61. Landman, Fred (1991). "Структуры для семантики". Исследования по лингвистике и философии . 45 : 127. doi :10.1007/978-94-011-3212-1. ISBN 978-0-7923-1240-6. ISSN  0924-4662.
62. Nascimento, Marco Antonio Chaer (2015). Frontiers in quantum methods and applications in chemical and physics: favorite materials of QSCP-XVIII (Paraty, Brazil, December, 2013) . Прогресс в теоретической химии и физике. Международный семинар по квантовым системам в химии и физике. Cham: Springer. стр. 255. ISBN 978-3-319-14397-2.
63. Chowdhary, KR (2020). «Основы искусственного интеллекта». SpringerLink : 31–34. doi :10.1007/978-81-322-3972-7. ISBN 978-81-322-3970-3.
64. Рестолл, Грег; Стэндефер, Шон (3 января 2023 г.). Логические методы. MIT Press. стр. 76. ISBN 978-0-262-54484-9.
65. Хантер, Джеффри (1971). Металогика: Введение в метатеорию стандартной логики первого порядка . Издательство Калифорнийского университета. ISBN 0-520-02356-0.
66. Рестолл, Грег (2010). Логика: введение . Основы философии. Лондон: Routledge. С. 5, 36–41, 55–60, 69. ISBN 978-0-415-40068-8.
67. Aloni, Maria (2023), «Disjunction», в Zalta, Edward N.; Nodelman, Uri (ред.), The Stanford Encyclopedia of Philosophy (весеннее издание 2023 г.), Metaphysics Research Lab, Stanford University , дата обращения 23 марта 2024 г.
68. Makridis, Odysseus (2022). Символическая логика . Философия Palgrave сегодня. Cham, Швейцария: Palgrave Macmillan. стр. 119. ISBN 978-3-030-67395-6.
69. Берджесс, Джон П. (2009). Философская логика. Принстонские основы современной философии. Принстон: Princeton University Press. стр. 5. ISBN 978-0-691-13789-6. OCLC  276141382.
70. Beall, JC; Restall, Greg (2006). Логический плюрализм. Clarendon Press. стр. 38. ISBN 978-0-19-928840-3.
71. Левин, Оскар. Логика высказываний.
72. Смит, Питер (2003), Введение в формальную логику , Cambridge University Press , ISBN 978-0-521-00804-4. (Определяет «выразительно адекватный», сокращенно до «адекватный набор связок» в заголовке раздела.)
73. Каннингем, Дэниел В. (2016). Теория множеств: первый курс . Кембриджские математические учебники. Нью-Йорк, Нью-Йорк: Cambridge University Press. ISBN 978-1-107-12032-7.
74. Дженесерет, Майкл; Као, Эрик Дж. (2017). Введение в логику. Лекции по синтезу в информатике. Cham: Springer International Publishing. стр. 18. doi : 10.1007/978-3-031-01801-5. ISBN 978-3-031-00673-9.
75. Роджерс, Роберт Л. (1971). Математическая логика и формализованные теории. Elsevier. стр. 38–39. doi :10.1016/c2013-0-11894-6. ISBN 978-0-7204-2098-2.
76. "6. Семантика пропозициональной логики — документация Logic and Proof 3.18.4". leanprover.github.io . Получено 28 марта 2024 г. .
77. «Представление знаний и рассуждение: основы логики». www.emse.fr . Получено 28 марта 2024 г. .
78. "1.4: Тавтологии и противоречия". Mathematics LibreTexts . 9 сентября 2021 г. Получено 29 марта 2024 г.
79. Сильвестр, Джереми. EF Тавтологии и противоречия.
80. DeLancey, Craig; Woodrow, Jenna (2017). Elementary Formal Logic (1-е изд.). Pressbooks.
81. Дикс, Дж.; Фишер, Майкл; Новак, Питер, ред. (2010). Вычислительная логика в многоагентных системах: 10-й международный семинар, CLIMA X, Гамбург, Германия, 9-10 сентября 2009 г.: пересмотренные избранные и приглашенные доклады. Конспект лекций по информатике. Берлин; Нью-Йорк: Springer. стр. 49. ISBN 978-3-642-16866-6. OCLC  681481210.
82. Prakken, Henry; Bistarelli, Stefano; Santini, Francesco; Taticchi, Carlo, ред. (2020). Вычислительные модели аргументации: труды comma 2020. Frontiers in artificial intelligence and applications. Washington: IOS Press. стр. 252. ISBN 978-1-64368-106-1.
83. Аводей, Стив; Арнольд, Грег Фрост-, ред. (2024). Рудольф Карнап: исследования по семантике: собрание сочинений Рудольфа Карнапа, том 7. Нью-Йорк: Oxford University Press. стр. xxvii. ISBN 978-0-19-289487-8.
84. Harel, Guershon; Stylianides, Andreas J., ред. (2018). Advances in Mathematics Education Research on Proof and Proving: An International Perspective . ICME-13 Monographs (1-е изд. 2018 г.). Cham: Springer International Publishing : Выходные данные: Springer. стр. 181. ISBN 978-3-319-70996-3.
85. DeLancey, Craig (2017). «Краткое введение в логику: §4. Доказательства». Milne Publishing . Получено 23 марта 2024 г.
86. Фергюсон, Томас Маколей; Прист, Грэм (23 июня 2016 г.), «семантическое следствие», Словарь логики , Oxford University Press, doi : 10.1093/acref/9780191816802.001.0001, ISBN 978-0-19-181680-2, получено 23 марта 2024 г.
87. Фергюсон, Томас Маколей; Прист, Грэм (23 июня 2016 г.), «синтаксическое следствие», Словарь логики , Oxford University Press, doi : 10.1093/acref/9780191816802.001.0001, ISBN 978-0-19-181680-2, получено 23 марта 2024 г.
88. Кук, Рой Т. (2009). Словарь философской логики . Эдинбург: Издательство Эдинбургского университета. С. 82, 176. ISBN 978-0-7486-2559-8.
89. "Таблица истинности | Булевы значения, операторы, правила | Britannica". www.britannica.com . 14 марта 2024 г. . Получено 23 марта 2024 г. .
90. "MathematicalLogic". www.cs.yale.edu . Получено 23 марта 2024 г. .
91. "Analytic Tableaux". www3.cs.stonybrook.edu . Получено 23 марта 2024 г. .
92. "Формальная логика - Семантические таблицы, доказательства, правила | Britannica". www.britannica.com . Получено 23 марта 2024 г. .
93. "Аксиоматический метод | Логика, доказательства и основания | Britannica". www.britannica.com . Получено 23 марта 2024 г. .
94. "Propositional Logic". mally.stanford.edu . Получено 23 марта 2024 г. .
95. "Естественная дедукция | Интернет-энциклопедия философии" . Получено 23 марта 2024 г.
96. Weisstein, Eric W. "Sequent Calculus". mathworld.wolfram.com . Получено 23 марта 2024 г. .
97. "Интерактивный учебник по последовательному исчислению". logitext.mit.edu . Получено 23 марта 2024 г. .
98. Лукас, Питер; Гааг, Линда ван дер (1991). Принципы экспертных систем (PDF) . Международная серия по информатике. Уокингем, Англия; Рединг, Массачусетс: Addison-Wesley. стр. 26. ISBN 978-0-201-41640-4.
99. Бахмайр, Лео (2009). "CSE541 Логика в информатике" (PDF) . Университет Стоуни-Брук .
100. Лоусон, Марк В. (2019). Первый курс логики . Бока-Ратон: CRC Press, Taylor & Francis Group. стр. пример 1.58. ISBN 978-0-8153-8664-3.
101. Дин, Невилл (2003). Логика и язык . Бейзингсток: Palgrave Macmillan. стр. 66. ISBN 978-0-333-91977-4.
102. Чизвелл, Ян; Ходжес, Уилфрид (2007). Математическая логика . Оксфордские тексты по логике. Оксфорд: Oxford university press. стр. 3. ISBN 978-0-19-857100-1.
103. Ходжес, Уилфрид (2001). Логика (2-е изд.). Лондон: Penguin Books. стр. 130–131. ISBN 978-0-14-100314-6.
104. Toida, Shunichi (2 августа 2009 г.). «Доказательство импликаций». Материал веб-курса по дискретным структурам/дискретной математике CS381 . Кафедра компьютерных наук, Университет Олд Доминион . Получено 10 марта 2010 г.
105. Леммон, Эдвард Джон (1998). Начало логики . Бока-Ратон, Флорида: Chapman & Hall/CRC. стр. везде, особенно 39-40. ISBN 978-0-412-38090-7.
106. "Естественные системы вывода в логике > Заметки (Стэнфордская энциклопедия философии)". plato.stanford.edu . Получено 19 апреля 2024 г. .
107. Артур, Ричард TW (2017). Введение в логику: использование естественной дедукции, реальных аргументов, немного истории и немного юмора (2-е изд.). Питерборо, Онтарио: Broadview Press. ISBN 978-1-55481-332-2. OCLC  962129086.
108. Smullyan, Raymond M. (23 июля 2014 г.). Руководство для начинающих по математической логике. Courier Corporation. стр. 102–103. ISBN 978-0-486-49237-7.
109. Мендельсон, Ричард Л. (10 января 2005 г.). Философия Готлоба Фреге. Издательство Кембриджского университета. п. 185. ИСБН 978-1-139-44403-3.
110. Лукасевич, Январь (1970). Ян Лукасевич: Избранные произведения. Северная Голландия. п. 136.
111. Church, Alonzo (1996). Введение в математическую логику. Princeton University Press. стр. 119. ISBN 978-0-691-02906-1.
112. "Proof Explorer - Домашняя страница - Metamath". us.metamath.org . Получено 2 июля 2024 г. .
113. Walicki, Michał (2017). Введение в математическую логику (Расширенное издание). Нью-Джерси: World Scientific. стр. 126. ISBN 978-981-4719-95-7.
114. WVO Quine, Математическая логика (1980), стр. 81. Издательство Гарвардского университета, 0-674-55451-5

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

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

Похожие работы

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

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

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