Список систем Гильберта - List of Hilbert systems

Эта статья нужны дополнительные цитаты для проверка. Пожалуйста помоги улучшить эту статью к добавление цитат в надежные источники. Материал, не полученный от источника, может быть оспорен и удален Найдите источники: «Список систем Гильберта»  – Новости  · газеты  · книги  · ученый  · JSTOR (Сентябрь 2010 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

Эта статья содержит список образцов Гильбертовский стиль дедуктивные системы за логика высказываний.

Классические системы исчисления высказываний

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

Значение и отрицание

В формулировках здесь используются импликация и отрицание. ${ Displaystyle { к, neg }}$ как функционально полный набор основных связок. Каждая логическая система требует как минимум одного ненулевого правило вывода. Классическое исчисление высказываний обычно использует правило modus ponens:

${ displaystyle A, A to B vdash B.}$

Мы предполагаем, что это правило включено во все системы ниже, если не указано иное.

Frege система аксиом:^[1]

${ Displaystyle А к (В к А)}$

${ Displaystyle (А К (В К С)) К ((А К В) К (А К С))}$

${ Displaystyle (от А к В) к ( отр В к от А)}$

${ Displaystyle neg neg от А до А}$

${ displaystyle A to neg neg A}$

Гильберта система аксиом:^[1]

${ Displaystyle А к (В к А)}$

${ Displaystyle (А К (В К С)) К (В К (А К С))}$

${ Displaystyle (В к С) к ((от А к В) к (от А к С))}$

${ Displaystyle А к ( от А к В)}$

${ Displaystyle (от А до В) к (( от А к В) к В)}$

Лукасевич системы аксиом:^[1]

• Первый:

${ Displaystyle (от А к В) к ((В к С) к (от А к С))}$

${ Displaystyle ( от А к А) к А}$

${ Displaystyle А к ( от А к В)}$

• Второй:

${ Displaystyle ((А к В) к С) к ( отр А к С)}$

${ Displaystyle ((А к В) к С) к (В к С)}$

${ Displaystyle ( от А к С) к ((В к С) к ((А к В) к С))}$

• В третьих:

${ Displaystyle А к (В к А)}$

${ Displaystyle (А К (В К С)) К ((А К В) К (А К С))}$

${ Displaystyle ( от А к от В) к (В к А)}$

• Четвертый:^{[нужна цитата ]}

${ Displaystyle (от А к В) к ((В к С) к (от А к С))}$

${ Displaystyle А К ( Нег А К Б)}$

${ Displaystyle ( от А к В) к ((В к А) к А)}$

Лукасевич и Тарский система аксиом:^[2]

${ Displaystyle [(А к (В к А)) к ([( отр С к (D к отр Е)) к [(С к (D к F)) к ((E to D) to (E to F))]] to G)] to (H to G)}$

Мередит система аксиом:

${ Displaystyle ((((А к В) к ( отр С к отр D)) к С) к Е) к ((Е к А) к (D к А) )}$

Мендельсон система аксиом:^[3]

${ Displaystyle А к (В к А)}$

${ Displaystyle (А К (В К С)) К ((А К В) К (А К С))}$

${ Displaystyle ( от А к от В) к (( от А к В) к А)}$

Рассел система аксиом:^[1]

${ Displaystyle А к (В к А)}$

${ Displaystyle (от А к В) к ((В к С) к (от А к С))}$

${ Displaystyle (А К (В К С)) К (В К (А К С))}$

${ Displaystyle neg neg от А до А}$

${ Displaystyle (А к Нег А) к Нег А}$

${ Displaystyle (А к Нег В) К (В к Нег А)}$

Собочинский системы аксиом:^[1]

• Первый:

${ displaystyle neg A to (A to B)}$

${ Displaystyle А к (В к (С к А))}$

${ Displaystyle ( от А к С) к ((В к С) к ((А к В) к С))}$

• Второй:

${ Displaystyle (от А к В) к ( отр В к (от А к С))}$

${ Displaystyle А к (В к (С к А))}$

${ Displaystyle ( от А к В) к ((А к В) к В)}$

Последствия и ложь

Вместо отрицания классическая логика также может быть сформулирована с использованием функционально полного набора ${ displaystyle { to, bot }}$ связок.

Тарский–Бернейс –Вайсберг система аксиом:

${ Displaystyle (от А к В) к ((В к С) к (от А к С))}$

${ Displaystyle А к (В к А)}$

${ Displaystyle ((от А к В) к А) к А}$

${ displaystyle bot to A}$

Церковь система аксиом:

${ Displaystyle А к (В к А)}$

${ Displaystyle (А К (В К С)) К ((А К В) К (А К С))}$

${ Displaystyle ((А к бот) к бот) к А}$

Системы аксиом Мередит:

• Первый:^[4][5][6]

${ Displaystyle ((((А к В) к (С к бот)) к D) к Е) к ((Е к А) к (С к А))}$

• Второй:^[4]

${ Displaystyle ((А к В) к (( бот к С) к D)) к ((D к А) к (Е к (F к А)))}$

Отрицание и дизъюнкция

Вместо импликации классическая логика также может быть сформулирована с использованием функционально полного набора ${ Displaystyle { neg, lor }}$ связок. В этих формулировках используется следующее правило вывода;

${ displaystyle A, neg A lor B vdash B.}$

Система аксиом Рассела – Бернейса:

${ Displaystyle Нег ( Нег В лор С) лор ( Нег (А лор В) лор (А лор С))}$

${ Displaystyle neg (А лор В) лор (В лор А)}$

${ Displaystyle Нег А лор (В лор А)}$

${ Displaystyle neg (А лор А) лор А}$

Системы аксиом Мередит:^[7]

• Первый:

${ Displaystyle Нег ( Нег ( Нег A лор В) лор (С лор (D лор Е))) лор ( Нег ( Нег D лор А) лор (С лор ( E lor A)))}$

• Второй:

${ Displaystyle Нег ( Нег ( Нег А лор В) лор (С лор (D лор Е))) лор ( Нег ( Нег Е лор D) лор (С лор ( A lor D)))}$

• В третьих:

${ Displaystyle Нег ( Нег ( Нег А лор В) лор (С лор (D лор Е))) лор ( Нег ( Нег С лор А) лор (Е лор ( Д лор А)))}$

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

Инсульт Шеффера

Потому что Инсульт Шеффера (также известный как оператор NAND) функционально полный, его можно использовать для создания полной формулировки исчисления высказываний. Формулировки NAND используют правило вывода, называемое Никод модус поненс:

${ displaystyle A, A mid (B mid C) vdash C.}$

Система аксиом Никода:^[4]

${ displaystyle (A mid (B mid C)) mid [(E mid (E mid E)) mid ((D mid B) mid [(A mid D) mid (A mid D)])]}$

Системы аксиом Лукасевича:^[4]

• Первый:

${ displaystyle (A mid (B mid C)) mid [(D mid (D mid D)) mid ((D mid B) mid [(A mid D) mid (A mid D)])]}$

• Второй:

${ displaystyle (A mid (B mid C)) mid [(A mid (C mid A)) mid ((D mid B) mid [(A mid D) mid (A mid D)])]}$

Система аксиом Вайсберга:^[4]

${ displaystyle (A mid (B mid C)) mid [((D mid C) mid [(A mid D) mid (A mid D)]) mid (A mid ( A mid B))]}$

Аргонн системы аксиом:^[4]

• Первый:

${ displaystyle (A mid (B mid C)) mid [(A mid (B mid C)) mid ((D mid C) mid [(C mid D) mid (A mid D)])]}$

• Второй:

${ displaystyle (A mid (B mid C)) mid [([(B mid D) mid (A mid D)] mid (D mid B)) mid ((C mid B) mid A)]}$^[8]

Компьютерный анализ, проведенный Аргонном, выявил> 60 дополнительных систем с единственными аксиомами, которые можно использовать для формулирования исчисления высказываний NAND.^[6]

Импликационное исчисление высказываний

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

Система аксиом Бернейса – Тарского: ^[9]

${ Displaystyle А к (В к А)}$

${ Displaystyle (от А к В) к ((В к С) к (от А к С))}$

${ Displaystyle ((от А к В) к А) к А}$

Системы аксиом Лукасевича и Тарского:

• Первый:^[9]

${ Displaystyle [(A к (B к A)) к [([((C к D) к E) к F] к [(D к F) к (C к F)]) к G]] к G}$

• Второй:^[9]

${ Displaystyle [(A к B) к ((C к D) к E)] к ([F к ((C к D) к E)] к [(A к F) to (D to E)])}$

• В третьих:

${ Displaystyle ((А к В) к (С к D)) к (Е к ((D к А) к (С к А)))}$

• Четвертый:

${ Displaystyle ((А к В) к (С к D)) к ((D к А) к (Е к (С к А)))}$

Система аксиом Лукасевича:^[10][9]

${ Displaystyle ((А к В) к С) к ((С к А) к (D к А))}$

Интуиционистская и промежуточная логика

Интуиционистская логика подсистема классической логики. Обычно это формулируется с помощью ${ displaystyle { to, land, lor, bot }}$ как набор (функционально законченных) базовых связок. Он не является синтаксически полным, поскольку в нем отсутствует исключенный средний A∨¬A или Закон Пирса ((A → B) → A) → A, которые могут быть добавлены без нарушения логики. Он имеет modus ponens как правило вывода и следующие аксиомы:

${ Displaystyle А к (В к А)}$

${ Displaystyle (А К (В К С)) К ((А К В) К (А К С))}$

${ Displaystyle (А земля В) к А}$

${ Displaystyle (A земля B) к B}$

${ Displaystyle А к (В к (А земля В))}$

${ Displaystyle А К (А лор В)}$

${ Displaystyle В к (А лор В)}$

${ Displaystyle (от А к С) к ((В к С) к ((А лор В) к С))}$

${ displaystyle bot to A}$

В качестве альтернативы интуиционистская логика может быть аксиоматизирована с использованием ${ displaystyle { to, land, lor, neg }}$ как набор основных связок, заменив последнюю аксиому на

${ Displaystyle (А к Нег А) к Нег А}$

${ displaystyle neg A to (A to B)}$

Промежуточная логика находятся между интуиционистской логикой и классической логикой. Вот несколько промежуточных логик:

• Логика Янкова (KC) - это расширение интуиционистской логики, которая может быть аксиоматизирована с помощью интуиционистской системы аксиом плюс аксиомы^[11]

${ displaystyle neg A lor neg neg A.}$

• Логика Гёделя – Даммета (ЛК) может быть аксиоматизирована над интуиционистской логикой, добавив аксиому^[11]

${ Displaystyle (от A до B) lor (от B до A).}$

Положительное импликационное исчисление

Позитивное импликационное исчисление - импликационный фрагмент интуиционистской логики. В приведенных ниже расчетах в качестве правила вывода используется modus ponens.

Система аксиом Лукасевича:

${ Displaystyle А к (В к А)}$

${ Displaystyle (А К (В К С)) К ((А К В) К (А К С))}$

Системы аксиом Мередит:

• Первый:

${ Displaystyle Е к ((А к В) к (((D к А) к (В к С)) к (А к С)))}$

• Второй:

${ Displaystyle А к (В к А)}$

${ Displaystyle (от А к В) к ((А к (В к С)) к (от А к С))}$

• В третьих:

${ Displaystyle ((А к В) к С) к (D к ((В к (С к Е)) к (В к Е)))}$^[12]

Системы аксиом Гильберта:

• Первый:

${ Displaystyle (А К (А К Б)) К (А К Б)}$

${ Displaystyle (В к С) к ((от А к В) к (от А к С))}$

${ Displaystyle (А К (В К С)) К (В К (А К С))}$

${ Displaystyle А к (В к А)}$

• Второй:

${ Displaystyle (А К (А К Б)) К (А К Б)}$

${ Displaystyle (от А к В) к ((В к С) к (от А к С))}$

${ Displaystyle А к (В к А)}$

• В третьих:

${ Displaystyle от А до А}$

${ Displaystyle (от А к В) к ((В к С) к (от А к С))}$

${ Displaystyle (В к С) к ((от А к В) к (от А к С))}$

${ Displaystyle (А К (А К Б)) К (А К Б)}$

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

Положительное исчисление высказываний - это фрагмент интуиционистской логики, использующий только (нефункционально полные) связки ${ Displaystyle { к, земля, лор }}$. Его можно аксиоматизировать с помощью любого из вышеупомянутых исчислений положительного импликационного исчисления вместе с аксиомами

${ Displaystyle (А земля В) к А}$

${ Displaystyle (A земля B) к B}$

${ Displaystyle А к (В к (А земля В))}$

${ Displaystyle А К (А лор В)}$

${ Displaystyle В к (А лор В)}$

${ Displaystyle (А к С) к ((В к С) к ((А лор В) к С))}$

По желанию, мы также можем включить соединительный ${ displaystyle leftrightarrow}$ и аксиомы

${ Displaystyle (A leftrightarrow B) к (от A к B)}$

${ Displaystyle (A leftrightarrow B) к (B к A)}$

${ Displaystyle (от А к В) к ((В к А) к (А leftrightarrow B))}$

Йоханссон с минимальная логика может быть аксиоматизирован любой из систем аксиом для положительного исчисления высказываний и расширен его язык с помощью нулевой связки ${ displaystyle bot}$, без дополнительных схем аксиом. В качестве альтернативы, это также может быть аксиоматизировано на языке ${ displaystyle { to, land, lor, neg }}$ путем расширения положительного исчисления высказываний с помощью аксиомы

${ Displaystyle (А к отр В) к (В к от А)}$

или пара аксиом

${ Displaystyle (от А к В) к ( отр В к от А)}$

${ displaystyle A to neg neg A}$

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

${ Displaystyle (А к отр В) к (В к от А)}$

${ displaystyle neg A to (A to B)}$

или пара аксиом^[13]

${ Displaystyle (А к Нег А) к Нег А}$

${ displaystyle neg A to (A to B)}$

Классическая логика в языке ${ displaystyle { to, land, lor, neg }}$ можно получить из положительного исчисления высказываний, добавив аксиому

${ Displaystyle ( от А к от В) к (В к А)}$

или пара аксиом

${ Displaystyle (А к Нег В) К (В к Нег А)}$

${ Displaystyle neg neg от А до А}$

Исчисление Фитча берет любую из систем аксиом для положительного исчисления высказываний и добавляет аксиомы^[13]

${ displaystyle neg A to (A to B)}$

${ Displaystyle A leftrightarrow neg neg A}$

${ displaystyle neg (A lor B) leftrightarrow ( neg A land neg B)}$

${ Displaystyle neg (A земля B) leftrightarrow ( neg A lor neg B)}$

Обратите внимание, что первая и третья аксиомы также верны в интуиционистской логике.

Эквивалентное исчисление

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

${ Displaystyle А, А эквив Б vdash B}$

Система аксиом Исеки:^[14]

${ Displaystyle ((А эквив С) эквив (В эквив А)) эквив (С эквив В)}$

${ Displaystyle (А эквив (В эквив С)) экв ((А эквив В) эквив С)}$

Система аксиом Исеки – Араи:^[15]

${ Displaystyle А экв А}$

${ Displaystyle (А эквив В) эквив (В эквив А)}$

${ Displaystyle (А эквив В) эквив ((В эквив С) эквив (А эквив С))}$

Системы аксиом Араи;

• Первый:

${ Displaystyle (А эквив (В эквив С)) экв ((А эквив В) эквив С)}$

${ Displaystyle ((A эквив С) эквив (В эквив А)) эквив (С эквив В)}$

• Второй:

${ Displaystyle (А эквив В) эквив (В эквив А)}$

${ Displaystyle ((А эквив С) эквив (В эквив А)) эквив (С эквив В)}$

Системы аксиом Лукасевича:^[16]

• Первый:

${ Displaystyle (А эквив В) эквив ((С эквив В) эквив (А эквив С))}$

• Второй:

${ Displaystyle (А эквив В) эквив ((А эквив С) эквив (С эквив В))}$

• В третьих:

${ Displaystyle (А эквив В) эквив ((С эквив А) эквив (В эквив С))}$

Системы аксиом Мередит:^[16]

• Первый:

${ Displaystyle ((А эквив В) эквив С) эквив (В эквив (С эквив А))}$

• Второй:

${ Displaystyle А эквив ((В эквив (А эквив С)) эквив (С эквив В))}$

• В третьих:

${ Displaystyle (А эквив (В эквив С)) эквив (С эквив (А эквив В))}$

• Четвертый:

${ Displaystyle (А эквив В) эквив (С эквив ((В эквив С) эквив А))}$

• Пятое:

${ Displaystyle (А эквив В) эквив (С эквив ((С эквив В) эквив А))}$

• Шестое:

${ Displaystyle ((А эквив (В эквив С)) эквив С) эквив (В эквив А)}$

• Седьмой:

${ Displaystyle ((А эквив (В эквив С)) эквив В) эквив (С эквив А)}$

Кальман система аксиом:^[16]

${ Displaystyle А эквив ((В эквив (С эквив А)) эквив (С эквив В))}$

Винкер системы аксиом:^[16]

• Первый:

${ Displaystyle А эквив ((В эквив С) экв ((А эквив С) эквив В))}$

• Второй:

${ Displaystyle А эквив ((В эквив С) экв ((С эквив А) эквив В))}$

Система аксиом XCB:^[16]

${ Displaystyle А эквив (((А эквив В) эквив (С эквив В)) эквив С)}$

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

• Параконсистентная логика # Включено список схем аксиом для паранепротиворечивой логики стиля Гильберта

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