2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Логика высказываний с одной схемой аксиом
Сообщение03.12.2016, 15:54 


21/11/15
9
Как доказать, что все тавтологии логики высказываний с Modus Ponens и двумя связками: $\neg$ и $\vee$ могут быть выведены из одной схемы аксиом:
$\neg(\neg (\neg A\vee B)\vee (C\vee (D\vee E)))\vee (\neg (\neg D\vee A)\vee (C\vee (E\vee A)))$?
Подозреваю, что из этой схемы нужно получить три стандартные схемы логики высказываний, из которых доказуемо всё остальное.
Подозреваю, что действовать нужно подстановкой. Например, из данной схемы я могу вывести такую схему:
$\neg(\neg C\vee (\neg A\vee B))\vee(\neg (\neg D\vee A)\vee ((E\vee A)\vee(\neg A\vee B)))$
Но в каком направлении копать, чтобы доказать, скажем, $\neg(A\vee A)\vee A$?

Оригинальную статью с доказательством отыскать не могу:
Meredith Carew A.. Single axioms for the systems (C, N), (C, O) and (A, N) of the two-valued propositional calculus. The journal of computing systems, vol. 1 no. 3 (1953), pp. 155–164.

 Профиль  
                  
 
 Re: Логика высказываний с одной схемой аксиом
Сообщение03.12.2016, 21:55 
Заслуженный участник


27/04/09
28128
Одной только подстановкой в общем случае не обойтись, нужны нетривиальные выводы с использованием MP. Ничего полезного подсказать не могу кроме попыток двигаться в обратную сторону от того, что нужно вывести — если $\dfrac{A,\; B}{C}\,\mathsf{MP}$, то $A\equiv\neg B\vee C$ (или $B\equiv \neg A\vee C$, но ничего нового альтернатива, конечно, не даст, так что можно ограничиваться первой).

Допустим, хотим доказать $\neg A\vee(\neg B\vee A)$. Аксиомой это явно не является, так что должны быть выведены формулы $X_2\equiv\neg X_1\vee(\neg A\vee(\neg B\vee A))$ и $X_1$. Можно попробовать решить, что $X_2$ — это какая-то подстановка в $\neg(\neg D\vee A)\vee(C\vee(E\vee A))$ (правая часть аксиомы). Может получиться, может нет.

Ещё можно попытаться подставлять что-то одинаковое и смотреть, не выводится ли какая-то полезная для будущего вещь.

Вообще, конечно, полезнее всего, если за видом этой аксиомы стоят какие-то соображения, и они известны. Знал бы — поделился, а с наскоку не видно. Раз логика классическая, можно заменить для проверки все $\neg a\vee b$ на $a\to b$ и $a\vee b$ на $\neg a\to b$ и глянуть, не получается ли что-то более внятное.

На Metamath нашлась аксиома этого же автора, но, увы, другая.

-- Вс дек 04, 2016 00:02:16 --

Впрочем, какая-то часть раздела Other axiomatizations of classical propositional calculus вам, возможно, пригодится.

 Профиль  
                  
 
 Re: Логика высказываний с одной схемой аксиом
Сообщение19.05.2017, 16:33 


14/03/11
142
Посмотрите ссылку. Там, правда, базовые связки - отрицание и импликация.
http://us.metamath.org/mpegif/mmtheorems15.html

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 3 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group