Исчисление - Propositional calculus


Из Википедии, свободной энциклопедии

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

содержание

объяснение

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

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

Предпосылка 1: Если идет дождь, то это облачно.
Предпосылка 2: Это дождь.
Заключение: Это мутное.

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

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

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

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

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

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

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

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

история

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

Пропозициональная логика была в конечном счете очищена с использованием символической логики . Семнадцатый / 18-го века математик Лейбниц был приписывают основателю символической логики его работы с исчислению ratiocinator . Несмотря на то, что его работе была первой в своем роде, это было неизвестно большим логическим сообщество. Следовательно, многие из достижений , достигнутых Лейбниц были воссозданы логиками , как Джордж Буль и Август Де Морган совершенно независимо от Лейбница.

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

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

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

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

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

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

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

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

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

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

Основные понятия

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

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

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

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

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

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

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

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

аргументация

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

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

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

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

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

Generic описание исчисления высказываний

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

  • Альфа - множество является счетно бесконечным множеством элементов , называемых предложени символы или пропозициональным переменной . Синтаксически говоря, это самые основные элементы формального языка , иначе называемые атомарные формулы или оконечных элементов . В приведенных далее примерах, элементы , как правило , буквы р , д , г , и так далее.
В этом разделе, есть множество операторных символов валентность J .
В более привычном пропозициональных исчислений, Ω обычно распределяют следующим образом :
Часто принятая конвенция обрабатывает постоянные логические значения в качестве операторов арности нулевого, таким образом:
Некоторые авторы используют тильды (~) или N, вместо ¬ ; и некоторые используют амперсанд (&), Префиксальный K, или вместо . Обозначение изменяется даже больше для множества логических значений, с символами , такими как {ложно, истинно}, {Р, Т}, или все время рассматривается в различных контекстах вместо {0, 1}.
  • Множество дзета конечное множество правил преобразования , которые называются правила вывода , когда они приобретают логические приложения.
  • Множество йота счетное множество начальных точек , которые называются аксиомами , когда они получают логические интерпретации.

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

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

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

  1. По правилу 1, р представляет собой формулу.
  2. По правилу 2, формула.
  3. По правилу 1, д формула.
  4. По правилу 2, формула.

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

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

  • Альфа множество , счетно бесконечное множество символов, например:
  • Из трех связок конъюнкции, дизъюнкции и импликации ( и ), можно рассматривать как примитивные , а два других могут быть определены в терминах его и отрицания ( ¬ ). В самом деле, все логические связки могут быть определены в терминах единственного достаточного оператора . Biconditional ( ) , конечно , могут быть определены в терминах конъюнкции и импликации, с определяется как .
Принятие отрицания и импликации в качестве двух примитивных операций в исчислении высказываний равносильно имеющее множество омега раздел следующим образом :
  • Правило вывода является модус поненс (т.е. от р и , выводит д ). Затем определяется , и определяется как . Эта система используется в Metamath set.mm формальной базе данных доказательств.

Пример 2. Естественная система вычетов

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

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

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

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

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

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

введение Отрицание
Из и , выводим .
То есть .
устранение Отрицание
Из , выводим .
То есть .
Двойное отрицательное устранение
Из , выводим р .
То есть .
введение Conjunction
Из р и д , выводим .
То есть .
устранение Conjunction
Из , выводим р .
Из , выводит д .
То есть, и .
введение Дизъюнкция
Из р , выводим .
Из д , выводим .
То есть, и .
устранение Дизъюнкция
Из и а , вывод г .
То есть .
Biconditional введение
Из и , выводим .
То есть .
Biconditional элиминация
Из , выводим .
Из , выводим .
То есть, и .
Модусный поненс (условное устранение) 
Из р и , выводит д .
То есть .
Условное доказательство (условное введение) 
Из [принимая р позволяет доказательство д ], выводим .
То есть .

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

Основные и производные формы аргументов
название последовательный Описание
Modus поненс Если р , то д ; р ; поэтому д
Modus Толленс Если р , то д ; не д ; поэтому не р
Гипотетический силлогизм Если р , то д ; если д , то г ; Поэтому, если р , то г
дизъюнктивный силлогизм Либо р или д , или обоих; не р ; Таким образом, д
Конструктивная Дилемма Если р , то д ; и если г , то ев ; но р и г ; Поэтому д или с
Разрушительная Дилемма Если р , то д ; и если г , то ев ; но не Q или нет ей ; поэтому не р или нет г
Двунаправленная Дилемма Если р , то д ; и если г , то ев ; но р или нет ей ; Поэтому д или нет г
упрощение р и д являются истинными; Поэтому р верно
конъюнкция р и д справедливы отдельно; поэтому они истинны совместно
прибавление р истинно; Поэтому дизъюнкция ( р или д ) верно
Состав Если р , то д ; и если р , то г ; Поэтому , если р истинно , то д и т справедливы
Теорема де Моргана (1) Отрицание ( р и д ) является эквив. чтобы (не р или нет д )
Теорема де Моргана (2) Отрицание ( р или д ) является эквив. чтобы (не р и не д )
Коммутационные (1) ( Р или д ) является эквив. к ( д или р )
Коммутационные (2) ( Р , и д ) является эквив. к ( д и р )
Коммутационные (3) ( Р является экв. К ц ) является эквив. к ( д является эквив. до р )
Ассоциация (1) р или ( д , или г ) является эквив. к ( р или д ) или г
Ассоциация (2) р и ( д , и г ) является эквив. к ( р и д ) и г
Распределение (1) р и ( д , или г ) является эквив. к ( р и д ) или ( р и г )
Распределение (2) р или ( д , и г ) является эквив. к ( р или д ) и ( р или г )
Двойное Отрицание р эквивалентно отрицанию не р
перестановка Если р , то д является эквив. чтобы если не ц то не р
Материал Причастность Если р , то д является эквив. чтобы не р или д
Материал Эквивалентность (1) ( Р тогда и только тогда д ) является эквив. чтобы (если р истинно , то Q истинно) и (если д истинно , то р истинно)
Материал Эквивалентность (2) ( Р тогда и только тогда д ) является эквив. либо ( р и д являются истинными) или (оба р и д являются ложными)
Материал Эквивалентность (3) ( Р тогда и только тогда д ) является эквив к., Как ( р или нет д истинно) и (не р или д верно)
экспортирование из (если р и д истинны , то г истинно), можно доказать (если ц верно , то г верно, если р истинно)
Импорт Если р , то (если д , то г ) эквивалентно , если р и д , то г
Тавтология (1) р верно , то эквив. к р истинно или р истинно
Тавтология (2) р верно , то эквив. к р истинно и р истинно
Tertium не дано (Закон исключенного среднего) р или не р истинно
Закон непротиворечия р и не р ложно, высказывание является истинным

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

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

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

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

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

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

Корректность и полнота правил

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

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

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

  • Удовлетворяет пропозициональная переменная Р тогда и только тогда , когда ( Р ) = TRUE
  • А удовлетворяет ¬ φ , если и только если не удовлетворяет ф
  • A удовлетворяет условию ( фг | ) тогда и только тогда , когда А удовлетворяет обоим ф и ψ
  • A удовлетворяет условию ( фг | ) тогда и только тогда , когда удовлетворяет , по меньшей мере , один из либо ф или ф
  • A удовлетворяет ( φг | ) , если и только если это не так , что A удовлетворяет φ , но не ф
  • A удовлетворяет условию ( фг | ) тогда и только тогда , когда А удовлетворяет обоим ф и г | или удовлетворяет ни один из них

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

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

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

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

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

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

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

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

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

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

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

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

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

По определению доказуемости, не существует никаких предложений доказуемы иначе , чем будучи членом G , аксиомы, или после по правилу; так что, если все из них семантически подразумевает, вычет исчисление звук.

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

(Это, как правило, гораздо сложнее направление доказательства.)

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

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

  1. G не доказывает . (Успение)
  2. Если G не доказывает А , то мы можем построить (бесконечный) максимальный набор , G * , который является подмножеством G и который также не доказывает .
    1. Разместить заказ (с порядковым типом со) на все предложения на языке (например, короткий первый, и столь же длинные, в расширенном алфавитном порядке), и пронумеровать их ( E 1 , E 2 , ...)
    2. Определение серии G п множеств ( G 0 , G 1 , ...) индуктивно:
      1. Если доказывает А , то
      2. Если это не доказать А , то
    3. Определим G * как объединение всех G п . (То есть, G * есть множество всех предложений, которые в любом G п .)
    4. Можно легко показать, что
      1. G * содержит (является подмножеством) G (по (би));
      2. G * не доказывает(потому что доказательство будет содержать лишь конечное число предложений икогда последний из них вводится в некотором G п , что G п будет доказать А вопреки определению G п ); а также
      3. G * является максимальным набором по: Если какимлибо больше предложений независимо были добавлены в G * , было бы доказать. (Потому что еслиэто было возможночтобы добавить больше предложений, они должны были быть добавленыкогда они были обнаружены во время строительства G п , опятьпо определению)
  3. Если G * максимальное множество относительно А , то это правда, как . Это означает , что она содержит C , только если она не содержит ¬C ; Если она содержит C и содержит «Если С , то В » , то он также содержит B ; и так далее.
  4. Если G * есть истина, как есть G * -каноническая оценка языка: один , что делает каждое предложение в G * верно и все вне G * ложное в тот же время подчиняются законы смысловой композиции в языке.
  5. G * -каноническая оценка будет сделать наш оригинальный набор G все верна, и сделать ложное.
  6. Если есть оценка , на которой G истинны и ложно, то G не (семантический) следует .

QED

Другой план для доказательства полноты

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

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

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

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

  1. назначается Т , или
  2. назначается F .

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

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

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

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

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

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

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

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

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

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

Аксиомы

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

Аксиомы
название Аксиома схемы Описание
ТО-1 Добавить гипотезу х , введение Подразумевается
ТО-2 Распределить гипотезу φ над импликацией
И-1 Исключите конъюнкции
И-2  
И-3 Введем конъюнкции
ИЛИ-1 Представьте дизъюнкции
ИЛИ-2  
ИЛИ-3 Исключите дизъюнкции
НЕ-1 Введем отрицанием
НЕ-2 Исключите отрицание
НЕ-- Исключены средний, классическая логика
IFF-1 Исключите эквивалентность
IFF-2  
IFF-3 Введем эквивалентность
  • Аксиома ТО-2 можно считать , чтобы быть «распределительное свойство импликации по смыслу.»
  • Аксиомы И-1 и И-2 соответствуют «устранению конъюнкции». Соотношение между И-1 и И-2 отражает коммутативности оператора конъюнкции.
  • Аксиома И-3 соответствует «введение конъюнкции.»
  • Аксиомы OR-1 и OR-2 соответствуют "Введение дизъюнкции." Соотношение между OR-1 и OR-2 отражает коммутативности оператора дизъюнкции.
  • Аксиома НЕ-1 соответствует «противному.»
  • Аксиома НЕ-2 говорит , что «все , что может быть выведено из противоречия.»
  • Аксиома НЕ-3 называется « третьего не дано » ( Latin : «а третьего не дано») и отражает смысловую оценку пропозициональных формул: формула может иметь истинностное значение либо истинно , либо ложно. Там нет третьего истинностного значения, по крайней мере , не в классической логике. Интуиционистская логика не принимает аксиому НЕ-3 .

правило Умозаключение

Правило вывода является модус поненс :

,

Правило Meta-умозаключение

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

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

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

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

Обратное DT также справедливо:

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

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

Если
затем
1:
2:
и из (1) и (2) можно вывести
3:
с помощью модуса поненса, КЭД

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

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

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

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

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

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

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

  1. Аксиома ТО-2 с
  2. Аксиома ТО-1 с
  3. Из формулы (1) и (2) модус поненс.
  4. Аксиома ТО-1 с
  5. Из (4) модус поненс (3) и.

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

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

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

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

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

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

,

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

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

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

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

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

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

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

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

Модальная логика также предлагает целый ряд выводов , которые не могут быть захвачены в исчислении. Например, из «ОБЯЗАТЕЛЬНО р » мы можем сделать вывод , что р . Из р мы можем сделать вывод , «Вполне возможно , что р ». Перевод между модальными логиками и алгебраическими логиками проблем классических и интуиционистская логика , но с введением унарного на булевых или гейтинговые алгебрах, отличается от логических операций, интерпретации возможности модальности, и в случае гейтинговой алгебры второго оператора интерпретации необходимости (для булевой алгебры это является излишним , поскольку голь De Morgan двойной возможности). Первый оператор сохраняет 0 и дизъюнкции , а вторая сохраняет 1 и конъюнкции.

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

вычислители

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

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

Higher логические уровни

похожие темы

Рекомендации

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

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

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

внешняя ссылка