Доказать тождество в теории L

[__ParaPik__]

Здравствуйте. Есть такое тождество, которое нужно доказать в теории L: $\neg(A \& \neg B) \equiv (A\&(B\Rightarrow C))\Rightarrow B$.
Слева направо выводится просто. А вот при выводе справа налево у меня возникли трудности. Преподаватель сказал использовать следующее при выводе $A\Rightarrow (B\Rightarrow C) \equiv A\&B\Rightarrow C$.
Я использую следующие гипотезы:
1. $(A\&(B\Rightarrow C))\Rightarrow B$
2. $A$
Используя формулу, предложенную преподавателем, и правилом monus ponus, получил:
$(B\Rightarrow C)\Rightarrow B$.
Дальше я не знаю, что делать. Подскажите, как дальше выводить.

[Nemiroff]

__ParaPik__ в сообщении #862819 писал(а):

Используя формулу, предложенную преподавателем, и правилом monus ponus, получил:
$(B\Rightarrow C)\Rightarrow B$.

Это сомнительно.

"modus ponus" — мда...

А что такое "теория L"?

[__ParaPik__]

Преподаватель сказал, что у нас Гильбертовская аксиоматизация.
Есть следующие схемы:
1) $A\Rightarrow(B\Rightarrow A)$
2) $(A\Rightarrow(B\Rightarrow C))\Rightarrow((A\Rightarrow B)\Rightarrow(A\Rightarrow C))$
3) $(\neg B\Rightarrow \neg A)\Rightarrow((\neg B\Rightarrow A)\Rightarrow B)$

Еще нам дали 9 секвенций.

[Sonic86]

__ParaPik__ в сообщении #863357 писал(а):

Есть следующие схемы:
1) $A\Rightarrow(B\Rightarrow A)$
2) $(A\Rightarrow(B\Rightarrow C))\Rightarrow((A\Rightarrow B)\Rightarrow(A\Rightarrow C))$
3) $(\neg B\Rightarrow \neg A)\Rightarrow((\neg B\Rightarrow A)\Rightarrow B)$

Еще нам дали 9 секвенций.

Каких?
У Вас $\&$ в аксиомах отсутствует. Т.е. чтобы доказать требуемую формулу $F$, Вам надо в ней все связки переписать через импликацию $\Rightarrow$.

__ParaPik__ в сообщении #862819 писал(а):

Слева направо выводится просто.

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

__ParaPik__ в сообщении #862819 писал(а):

Преподаватель сказал использовать следующее при выводе $A\Rightarrow (B\Rightarrow C) \equiv A\&B\Rightarrow C$.

И откуда Вы это возьмете?

Кстати, через $\equiv$ обозначается отношение эквивалентности формул, а не связка эквиваленция.

[Joker_vD]

(Оффтоп)

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

[__ParaPik__]

Joker_vD, нам сказали сделать. Вот мы и делаем...

Теоремой дедукции пользоваться можно. Нам ввели $A \& B$ в качестве сокращенной записи $\neg (A \Rightarrow \neg B)$. Похожим образом ввели и $A \bigvee B$.

9 секвенций:
1) $A \Rightarrow B, B \Rightarrow C \vdash A \Rightarrow C$
2) $A \Rightarrow (B \Rightarrow C), B \vdash A \Rightarrow C$
3) $\vdash (\neg \neg A \Rightarrow A)$
4) $\vdash (A \Rightarrow \neg \neg A)$
5) $\vdash A \Rightarrow (\neg A \Rightarrow B)$
6) $\vdash (\neg B \Rightarrow \neg A) \Rightarrow (A \Rightarrow B)$
7) $\vdash (A \Rightarrow B) \Rightarrow (\neg B \Rightarrow \neg A)$
8) $\vdash A \Rightarrow (\neg B \Rightarrow \neg (A \Rightarrow B))$
9) $\vdash (A \Rightarrow B) \Rightarrow ((\neg A \Rightarrow B) \Rightarrow B)$

Цитата:

Цитата:

__ParaPik__ в сообщении #862819 писал(а):
Преподаватель сказал использовать следующее при выводе $A\Rightarrow (B\Rightarrow C) \equiv A\&B\Rightarrow C$.

И откуда Вы это возьмете?

Преподаватель сказал, чтобы это тоже доказал.

[Sonic86]

Так у Вас $\equiv$ - точно эквиваленция? Или надо, предполагая одну часть в качестве гипотезы, доказывать другую часть?

__ParaPik__ в сообщении #863422 писал(а):

Преподаватель сказал, чтобы это тоже доказал.

Если предполагать, что вопрос осмысленный, то $\equiv$ - эквиваленция все-таки.
И теорема дедукции доступна для использования или нет?
Ну Вас сначала нужно переписать связки $\vee, \&$ (м.б. и $\equiv$) через $\Rightarrow$, потом, если есть теорема дедукции - заюзать ее, а дальше уже надо явно смотреть.

[__ParaPik__]

Цитата:

Так у Вас $\equiv$ - точно эквиваленция? Или надо, предполагая одну часть в качестве гипотезы, доказывать другую часть?

Надо использовать одну часть в качестве гипотезы и доказать другую.

Цитата:

И теорема дедукции доступна для использования или нет?

Теорема дедукции доступна.

Связки я все переписал. И пришел к $(B\Rightarrow C)\Rightarrow B$.

[Nemiroff]

__ParaPik__ в сообщении #863500 писал(а):

И пришел к $(B\Rightarrow C)\Rightarrow B$.

Nemiroff в сообщении #862826 писал(а):

Это сомнительно.

Потому что не тавтология.

[Sonic86]

__ParaPik__ в сообщении #863500 писал(а):

Надо использовать одну часть в качестве гипотезы и доказать другую.

__ParaPik__ в сообщении #863500 писал(а):

Теорема дедукции доступна.

Прекрасно.

__ParaPik__ в сообщении #863500 писал(а):

Связки я все переписал. И пришел к $(B\Rightarrow C)\Rightarrow B$.

Заблуждаетесь: при переписывании связок $\vee, \&$ через $\Rightarrow$ длина формулы не уменьшается.

[__ParaPik__]

Я выводил так:
1) $(A\&(B\Rightarrow C))\Rightarrow B$ - гипотеза
2) $A$ - гипотеза

$A$ - гипотеза, так как можно вывести, что $\neg(A \& \neg B) \equiv A \Rightarrow B$.
По крайней мере, преподаватель разрешил сделать такую замену.

Далее, используя $A\Rightarrow (B\Rightarrow C) \equiv A\&B\Rightarrow C$, перепишем 1 как
$A \Rightarrow ((B \Rightarrow C) \Rightarrow B)$.

Дальше по правилу modus ponens к шагам 1 и 2 получаем $(B\Rightarrow C)\Rightarrow B$.

[Sonic86]

__ParaPik__ в сообщении #863697 писал(а):

2) $A$ - гипотеза

$A$ - гипотеза, так как можно вывести, что $\neg(A \& \neg B) \equiv A \Rightarrow B$.
По крайней мере, преподаватель разрешил сделать такую замену.

Чего? На каком основании ее можно делать-то?
С чего Вы взяли, что $A$ допустима в качестве гипотезы?
При чем здесь вообще соотношение $\neg(A \& \neg B) \equiv A \Rightarrow B$?

Дальше не читал, ибо там еще хуже.
В любом случае все это не является заменой связок $\vee, \&$ через $\Rightarrow$. Ну можете, конечно, не заменять сразу - Ваши проблемы.