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

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

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

Объяснение

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

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

Предпосылка 1. Если идет дождь, значит облачно.
Предпосылка 2: идет дождь.
Вывод: пасмурно.

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

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

Предпосылка 1:
Предпосылка 2:
Заключение:

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

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

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

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

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

История

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • Затем мы определяем функциональные операторы истинности , начиная с отрицания. ¬ Р представляет собой отрицание Р , который можно рассматривать как отрицание P . В приведенном выше примере, ¬ P выражает то , что он не идет дождь снаружи, или путем более стандартного чтения: «Это не тот случай, когда идет дождь снаружи.» Когда P истинно, ¬ P ложно; а когда P ложно, ¬ P истинно. В результате ¬ ¬ Р всегда имеет то же значение истинности как P .
  • Сопряжение истины функциональной соединительно которая формирует предложение из двух простых предложений, например, P и Q . Конъюнкция P и Q записывается как PQ и выражает истинность каждого из них. Мы читаем PQ как « P и Q ». Для любых двух предложений существует четыре возможных присвоения значений истинности:
    1. P верно и Q верно
    2. P истинно, а Q ложно
    3. P ложно, а Q верно
    4. P ложно, а Q ложно
Конъюнкция P и Q истинна в случае 1 и ложна в противном случае. Где P - утверждение о том, что на улице идет дождь, а Q - утверждение о том, что над Канзасом идет холодный фронт, PQ истинно, когда на улице идет дождь, а над Канзасом есть холодный фронт. Если на улице нет дождя, то P ∧ Q ложно; и если над Канзасом нет холодного фронта, то PQ также ложно.
  • Дизъюнкция похожа на конъюнкцию в том смысле, что она формирует предложение из двух более простых предложений. Мы пишем это PQ , и это читается как « P или Q ». Он означает, что либо P, либо Q истинны. Таким образом, в перечисленных выше случаях дизъюнкция P и Q истинна во всех случаях, кроме случая 4. Используя приведенный выше пример, дизъюнкция выражает, что либо на улице идет дождь, либо над Канзасом есть холодный фронт. (Обратите внимание, что такое использование дизъюнкции должно напоминать использование английского слова «or». Однако оно больше всего похоже на английское включающее «или», которое может использоваться для выражения истинности по крайней мере одного из двух предложений. Это не похоже на английское исключающее «или», которое выражает истинность ровно одного из двух утверждений. Другими словами, исключающее «или» ложно, когда и P, и Q истинны (случай 1). Пример исключающего или есть: у вас может быть бублик или выпечка, но не то и другое вместе. Часто в естественном языке с учетом соответствующего контекста добавление «но не оба» опускается, но подразумевается. В математике, однако, «или» всегда включающее или; если подразумевается исключающее или, это будет указано, возможно, с помощью "xor".)
  • Материальное условие также объединяет два более простых предложения, и мы пишем PQ , что читается как «если P, то Q ». Предложение слева от стрелки называется антецедентом, а предложение справа - консеквентом. (Нет такого обозначения для конъюнкции или дизъюнкции, поскольку они являются коммутативными операциями.) Он выражает, что Q истинно, когда P истинно. Таким образом, PQ истинно во всех приведенных выше случаях, кроме случая 2, потому что это единственный случай, когда P истинно, а Q - нет. Используя этот пример, если P, то Q выражает, что если на улице идет дождь, то есть холодный фронт над Канзасом. Материальную обусловленность часто путают с физической причинностью. Однако материальное условие связывает только два предложения посредством их истинностных ценностей, что не является отношением причины и следствия. В литературе ведутся споры о том, представляет ли материальный подтекст логической причинности.
  • Biconditional объединяет два более простых предложения, и мы пишем PQ , что читается как « P тогда и только тогда, когда Q ». Он выражает то, что P и Q имеют одинаковое значение истинности, и в случаях 1 и 4. « P истинно тогда и только тогда, когда Q » истинно, и ложно в противном случае.

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

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

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

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

Аргумент

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

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

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

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

Значение аргумента в формальной логике состоит в том, что можно получить новые истины из установленных истин. В первом примере, приведенном выше, с учетом двух предпосылок истинность Q еще не известна и не установлена. После того, как аргумент сделан, выводится Q. Таким образом, мы определяем систему дедукции как набор всех предложений, которые могут быть выведены из другого набора предложений. Например, учитывая множество предложений , мы можем определить систему дедукции, Г , которая представляет собой множество всех предложений , которые следуют из A . Повторение всегда предполагается, так что . Кроме того, из первого элемента A , последнего элемента, а также modus ponens, R является следствием, и так далее . Однако, поскольку мы не включили достаточно полные аксиомы, ничего другого сделать нельзя. Таким образом, хотя большинство систем дедукции, изучаемых в логике высказываний, способны делать выводы , эта система слишком слаба, чтобы доказать такое предложение.

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

Исчисление является формальной системой , где:

  • Альфа - множество является счетно бесконечным множеством элементов , называемых предложени символы или пропозициональным переменной . Говоря синтаксически, это самые основные элементы формального языка , иначе называемые атомарными формулами или терминальными элементами . В следующих примерах элементами, как правило, являются буквы p , q , r и т. Д.
  • Омега множество Ω является конечным множеством элементов , называемых символами оператора или логическими связками . Множество Ω является разбивается на непересекающиеся подмножества следующим образом :

    В этом разбиении - множество операторных символов арности j .

    В более знакомых исчислениях высказываний Ω обычно разбивается следующим образом:

    Часто принимаемое соглашение рассматривает постоянные логические значения как операторы с нулевой арностью, таким образом:

    Некоторые авторы используют тильду (~) или N вместо ¬ ; а некоторые используют вместо v , а также амперсанд (&), то префикс К, или вместо . Обозначения еще больше различаются для набора логических значений, при этом символы вроде {false, true}, {F, T} или {0, 1} видны в различных контекстах вместо .
  • Дзета набор представляет собой конечный набор правил преобразования , которые называются правила вывода , когда они приобретают логические приложения.
  • Набор йоты - это счетный набор начальных точек , которые называются аксиомами, когда они получают логические интерпретации.

Язык из , также известный как своей совокупности формул , хорошо образованных формулы , является индуктивно определяются следующими правилами:

  1. База: Любой элемент альфа-набора представляет собой формулу .
  2. Если есть формулы и есть в , то это формула.
  3. Закрыто: ничто другое не является формулой .

Повторное применение этих правил позволяет строить сложные формулы. Например:

  • По правилу 1 p - формула.
  • По правилу 2, это формула.
  • По правилу 1 q - это формула.
  • По правилу 2, это формула.

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

Пусть , где , , , определяются следующим образом :

  • Альфа-набор - это счетно бесконечный набор символов, например:
  • Из трех связок для соединения, дизъюнкции и импликации ( , и ) одну можно принять как примитивную, а две другие можно определить в терминах нее и отрицания ( ¬ ). Все логические связки можно определить с помощью единственного достаточного оператора . Biconditional ( ) может быть, конечно , определены в терминах конъюнкции и импликации, с определяется как .
    Принятие отрицания и импликации в качестве двух примитивных операций исчисления высказываний равносильно разделению омега-множества следующим образом:
  • Система аксиом, предложенная Яном Лукасевичем и используемая в качестве части исчисления высказываний системы Гильберта , формулирует исчисление высказываний на этом языке следующим образом. Все аксиомы являются примерами подстановки :
  • Правило вывода - это modus ponens (т. Е. Из p и вывести q ). Тогда определяется как , и определяется как . Эта система используется в Metamath set.mm формальной базе данных доказательств.

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

Пусть , где , , , определяются следующим образом :

  • Альфа-набор - это счетно бесконечный набор символов, например:
  • Омега устанавливает перегородки следующим образом:

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

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

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

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

Введение отрицания
Из а , сделаем .
То есть .
Устранение отрицания
Из , сделаем .
То есть .
Устранение двойного отрицания
Из , вывести p .
То есть .
Введение в соединение
Из p и q сделайте вывод .
То есть .
Устранение конъюнкции
Из , вывести p .
Из , вывести q .
То есть и .
Введение дизъюнкции
Из p сделать вывод .
Из q сделать вывод .
То есть и .
Устранение дизъюнкции
Из и и , вывести r .
То есть .
Двузначное введение
Из а , сделаем .
То есть .
Двуусловное исключение
Из , сделаем .
Из , сделаем .
То есть и .
Modus ponens (условное исключение)
Из p и вывести q .
То есть .
Условное доказательство (условное введение)
Из [принятие p дает доказательство q ], сделайте вывод .
То есть .

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

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

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

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

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

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

  • Для того, чтобы показать , что AA .
  • Одно из возможных доказательств этого (которое, хотя и действительно, содержит больше шагов, чем необходимо) может быть представлено следующим образом:
Пример доказательства
Число Формула Причина
1 посылка
2 Из ( 1 ) путем введения дизъюнкции
3 Из ( 1 ) и ( 2 ) введением конъюнкции
4 Из ( 3 ) путем исключения конъюнкции
5 Резюме от ( 1 ) до ( 4 )
6 Из ( 5 ) по условному доказательству

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

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

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

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

(A1)
(A2)
(A3)

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

  1.       (пример (A1))
  2.       (пример (A2))
  3.       (из (1) и (2) по modus ponens )
  4.       (пример (A1))
  5.       (из (4) и (3) по modus ponens)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  1. Основа. Показать: Если является членом G , то G означает A .
  2. Основа. Показать: Если аксиома, то G означает A .
  3. Индуктивный шаг (индукция по n , длина доказательства):
    1. Пусть для любого G и А , что если G доказывает А в п или меньше шагов, то G означает .
    2. Для каждого возможного применения правила вывода на шаге п + 1 , что приводит к новой теореме B , показывает , что G означает B .

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

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

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

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

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

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

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

  1. G не доказывает А . (Предположение)
  2. Если G не доказывает А , то мы можем построить (бесконечный) максимальный набор , G * , который является подмножеством G и который также не доказывает А .
    1. Поместите порядок (с типом порядка ω) во все предложения на языке (например, самые короткие сначала и одинаковые длинные в расширенном алфавитном порядке) и пронумеруйте их ( E 1 , E 2 , ...)
    2. Определим индуктивно серию G n множеств ( G 0 , G 1 , ...) :
      1. Если доказывает A , то
      2. Если это не доказать А , то
    3. Определим G как объединение всех G n . (То есть G - это множество всех предложений, содержащихся в любом G n .)
    4. Легко показать, что
      1. G содержит (является надмножеством) G (по (bi));
      2. G не доказывает A (поскольку доказательство будет содержать только конечное число предложений и когда последнее из них вводится в некоторый G n , G n доказывает A вопреки определению G n ); а также
      3. G * является максимальным набором относительно A : Если какиелибо больше предложений независимо были добавлены в G * , было бы доказать A . (Потому что, если бы можно было добавить еще предложения, они должны были быть добавлены, когда они встречались во время построения G n , опять же по определению)
  3. Если G - максимальное множество относительно A , то оно истинно . Это означает, что он содержит C тогда и только тогда, когда он не содержит ¬C ; Если он содержит C и содержит «Если C, то B », то он также содержит B ; и так далее. Чтобы показать это, нужно показать, что аксиоматическая система достаточно сильна для следующего:
    • Для любых формул C и D , если он докажет , как C и ¬C , то это доказывает , D . Отсюда следует, что максимальный набор относительно А не может доказать , как C и ¬C , так как в противном случае было бы доказать A .
    • Для любых формул C и D , если оно доказывает , как CD и ¬CD , то это доказывает , D . Это используется вместе с теоремой вывода , чтобы показать, что для любой формулы либо она, либо ее отрицание принадлежат G : пусть B - формула, не принадлежащая G ; то G * с добавлением B доказывает . Таким образом , из теоремы дедукции следует , что G * доказывает BA . Но предположим, что ¬B также не было в G , тогда по той же логике G также доказывает ¬BA ; но тогда G доказывает A , ложность которого мы уже показали.
    • Для любых формул C и D , если оно доказывает , C и D , то это доказывает , CD .
    • Для любых формул C и D , если это доказывает C и ¬D , то доказывает ¬ ( CD ).
    • Для любых формул C и D , если оно окажется ¬C , то это доказывает , CD .
    Если дополнительные логические операции (такие как конъюнкция и / или дизъюнкция) также являются частью словаря, то к аксиоматической системе предъявляются дополнительные требования (например, если она доказывает C и D , она также доказывает их конъюнкцию).
  4. Если G подобен истине, существует G -каноническая оценка языка: такая, которая делает каждое предложение в G истинным, а все вне G ложным, при этом подчиняясь законам семантической композиции в языке. Обратите внимание, что требование истинности необходимо для гарантии того, что законы семантической композиции в языке будут удовлетворены этим назначением истинности.
  5. G * -каноническая оценка будет сделать наш оригинальный набор G все верна, и сделать A ЛЖИ.
  6. Если есть оценка , на которой G истинны и ложно, то G не (семантический) следует A .

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

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

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

Пример

В качестве примера можно показать, что, как и любая другая тавтология, три аксиомы классической системы исчисления высказываний, описанной ранее, могут быть доказаны в любой системе, которая удовлетворяет вышеизложенному, а именно, которая имеет modus ponens в качестве правила вывода, и доказывает вышеизложенное. восемь теорем (включая их подстановки). Из восьми теорем последние две являются двумя из трех аксиом; Третья аксиома также может быть доказана, как мы сейчас покажем.

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

  1.       (пример 7-й теоремы)
  2.       (пример 7-й теоремы)
  3.       (из (1) и (2) по modus ponens)
  4.       (пример гипотетической теоремы силлогизма)
  5.       (пример 5-й теоремы)
  6.       (из (5) и (4) по modus ponens)
  7.       (пример 2-й теоремы)
  8.       (пример 7-й теоремы)
  9.       (из (7) и (8) по modus ponens)
  10.       (пример 8-й теоремы)
  11.       (из (9) и (10) по modus ponens)
  12.       (из (3) и (11) по modus ponens)
  13.       (пример 8-й теоремы)
  14.       (из (12) и (13) по modus ponens)
  15.       (из (6) и (14) по modus ponens)

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

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

(DN1) - двойное отрицание (одно направление)
(DN2) - Двойное отрицание (другое направление)
(HS1) - одна из форм гипотетического силлогизма
(HS2) - еще одна форма гипотетического силлогизма
(TR1) - Транспонирование
(TR2) - еще одна форма транспозиции.
(L1)
(L3)

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

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

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

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

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

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

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

  1. присваивается T , или
  2. назначается F .

Для пары , есть возможные интерпретации:

  1. обоим присваивается Т ,
  2. обоим назначены F ,
  3. присваивается T и присваивается F , или
  4. назначается F и назначается T .

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

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

Если φ и ψ являются формулами из и является интерпретацией , то применяются следующие определения:

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

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

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

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

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

Аксиомы

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

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

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

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

.

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

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

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

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

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

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

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

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

Если
тогда
1:
2:
и из (1) и (2) можно вывести
3:
с помощью modus ponens, QED

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

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

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

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

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

Докажите: (Рефлексивность импликации).

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

  1. Аксиома THEN-2 с
  2. Аксиома THEN-1 с
  3. Из (1) и (2) по modus ponens.
  4. Аксиома THEN-1 с
  5. Из (3) и (4) по modus ponens.

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

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

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

Как в булевой алгебре, так и в алгебре Гейтинга неравенство может использоваться вместо равенства. Равенство выражается парой неравенств и . И наоборот, неравенство можно выразить как равенство или как . Значение неравенства для систем в стиле Гильберта состоит в том, что оно соответствует последнему символу вывода или вывода . Следствие

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

Наоборот, алгебраическое неравенство переводится как следствие

.

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

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

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

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

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

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

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

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

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

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

Решатели

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

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

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

похожие темы

использованная литература

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

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

Сопутствующие работы

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