Логика импликаций

[Kosat]

Тождество, которое нужно доказать:

$A \wedge (B \vee C) \equiv (A \wedge B) \vee (A \wedge C)$

Есть три аксиомы:

$ 1. A \Rightarrow (B \rightarrow A) \\* 2. A \rightarrow (B \rightarrow C) \Rightarrow ((A \rightarrow B) \rightarrow (A \rightarrow C)) \\* 3. (\urcorner B \rightarrow \urcorner A) \Rightarrow ((\urcorner B \rightarrow A) \rightarrow B) $

Я перевёл (надеюсь, правильно) тождество в

$\urcorner ( A \rightarrow \urcorner (\urcorner B \rightarrow C)) \equiv ((A \rightarrow \urcorner B) \rightarrow \urcorner (A \rightarrow \urcorner C))$

Сначала хочу доказать импликацию в правую сторону:

$\urcorner ( A \rightarrow \urcorner (\urcorner B \rightarrow C)) \Rightarrow ((A \rightarrow \urcorner B) \rightarrow \urcorner (A \rightarrow \urcorner C))$

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

$ 1. \urcorner ( A \rightarrow \urcorner (\urcorner B \rightarrow C)) – гипотеза \\* 2. (A \rightarrow \urcorner B – гипотеза \\* 3. A – гипотеза \\* 4. \urcorner ( A \rightarrow \urcorner (\urcorner B \rightarrow C)) \Rightarrow (\urcorner ( A \rightarrow \urcorner (\urcorner B \rightarrow C) \rightarrow X) - Аксиома 1 \\* 5. \urcorner ( A \rightarrow \urcorner (\urcorner B \rightarrow C) \rightarrow X – MP, (1), (4) \\* 6. (\urcorner (A \rightarrow \urcorner (\urcorner B \rightarrow C) \rightarrow X) \Rightarrow ((\urcorner (A \rightarrow (\urcorner B \rightarrow C) \rightarrow X) \rightarrow (A \rightarrow (\urcorner B \rightarrow C)) – Аксиома 3, (5) \\* 7. ((\urcorner (A \rightarrow (\urcorner B \rightarrow C) \rightarrow X) \rightarrow (A \rightarrow (\urcorner B \rightarrow C)) – MP, (5), (6) $

Конца не видно. Непонятно, что делать. Кто может помочь? Спасибо.

[Kosat]

Не вставились кириллические буквы. Вот так надо.

Тождество, которое нужно доказать:

$A \wedge (B \vee C) \equiv (A \wedge B) \vee (A \wedge C)$

Есть три аксиомы:

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)$

И одно правило вывода (Modus Ponens):

$(A \wedge (A \rightarrow B)) \Rightarrow B$

Я перевёл (надеюсь, правильно) тождество в

$\neg ( A \rightarrow \neg (\neg B \rightarrow C)) \equiv ((A \rightarrow \neg B) \rightarrow \neg (A \rightarrow \neg C))$

Сначала хочу доказать импликацию в правую сторону:

$\urcorner ( A \rightarrow \neg (\neg B \rightarrow C)) \Rightarrow ((A \rightarrow \neg B) \rightarrow \neg (A \rightarrow \neg C))$

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

1. $ \neg ( A \rightarrow \neg (\neg B \rightarrow C)) $ – гипотеза

2. $ A \rightarrow \neg B $ – гипотеза

3. $ A $ – гипотеза

4. $ \neg ( A \rightarrow \neg (\neg B \rightarrow C)) \Rightarrow (\neg ( A \rightarrow \neg (\neg B \rightarrow C)) \rightarrow X) $ - Аксиома 1

5. $ \neg ( A \rightarrow \neg (\neg B \rightarrow C) \rightarrow X $ – MP, (1), (4)

6. $ (\neg (A \rightarrow \neg (\neg B \rightarrow C) \rightarrow X) \Rightarrow ((\neg (A \rightarrow (\neg B \rightarrow C) \rightarrow \neg X) \rightarrow (A \rightarrow (\neg B \rightarrow C)) $ – Аксиома 3, (5)

7. $ (\neg (A \rightarrow \neg (\neg B \rightarrow C) \rightarrow \neg X) \Rightarrow (A \rightarrow \neg (\neg B \rightarrow C)) $ - MP, (5), (6)

Конца не видно. Непонятно, что делать. Кто может помочь? Спасибо.

[yafkin]

а если просто посчитать значения по таблице истинности для (их не много) всех
значений и сравнить обе половины -так нельзя?

-- 21.04.2014, 20:49 --


А это использовать нельзя?

[Sonic86]

(2 yafkin)

Вы сами не разбираетесь толком, не несите свой хаос другому человеку в мозг, разберитесь с ним сначала сами.

Kosat в сообщении #852677 писал(а):

Не вставились кириллические буквы.

$\text{бла-бла-бла}$.
А также: $\neg X$ вместо $\uncorner X$.

Далее, видите ли, в чем у Вас проблема. У Вас в доказываемом утверждении присутствуют связки $\vee,\wedge,$, а в аксиомах их нет, тем более нет соотношения $\equiv$ между формулами (если только Вы по ошибке не вписали его вместо $\leftrightarrow$). Если Вы работаете в аксиоматической теории, то связки допускаются лишь как сокращения других связок. Т.е. Вам нужно переписать высказывание только через $\neg,\to$ (кстати, связки $\Rightarrow$ обычно нет - откуда Вы ее взяли?). Когда Вы перепишите его, то высказывание станет несколько длинноватым, что наводит на подозрения. Обычно народу показывают 2 аксиоматические системы. 1-я - 3-хаксиомная с MP и правилом подстановки, Вы ее привели, только зачем-то некоторые импликации заменили на $\Rightarrow$. Связки $\vee,\wedge$ в формулировках задач для этой системы аксиом обычно не используют. Есть другая система аксиом, со связками $\wedge,\vee$, в ней 10 аксиом, правила вывода те же. Но соотношение $\equiv$ между формулами там тоже не вводится и соотношения вида $F\equiv G$ там не доказываются. У Вас задание представляет из себя какую-то странную смесь алгебры логики и этих двух аксиоматик.
Часто в таких задачах оговаривают, можно ли использовать теорему дедукции или нет. Можно?

Далее,

Kosat в сообщении #852677 писал(а):

Сначала хочу доказать импликацию в правую сторону:

$\urcorner ( A \rightarrow \urcorner (\urcorner B \rightarrow C)) \Rightarrow ((A \rightarrow \urcorner B) \rightarrow \urcorner (A \rightarrow \urcorner C))$

В аксиоматических теориях так не делают: формулу нельзя "разбивать на части" и доказывать "по частям". Если там нужно вывести формулу $F\leftrightarrow G$ из аксиом, то ее переписывают как $(F\to G)\wedge (G\to F)$, а потом, в силу $X\wedge Y = \neg(X\to\neg Y)$, как $\neg ((F\to G)\to\neg (G\to F))$ и выводят ее целиком из аксиом

Kosat в сообщении #852677 писал(а):

Я перевёл (надеюсь, правильно) тождество в

$\neg ( A \rightarrow \neg (\neg B \rightarrow C)) \equiv ((A \rightarrow \neg B) \rightarrow \neg (A \rightarrow \neg C))$

правильно

[Kosat]

yafkin в сообщении #852682 писал(а):

а если просто посчитать значения по таблице истинности для (их не много) всех
значений и сравнить обе половины -так нельзя?

Нельзя. Надо "решить задачу в теории $L \left\{ \urcorner, \rightarrow \right\}$". Там были даны правила перевода, по которым я вроде и перевёл исходное тождество в эту теорию. Скорее всего правильно.

-- 21.04.2014, 19:47 --

Sonic86 в сообщении #852707 писал(а):

У Вас в доказываемом утверждении присутствуют связки $\vee,\wedge,$, а в аксиомах их нет, тем более нет соотношения $\equiv$ между формулами

Я же переводил. Вроде правильно. Поэтому и не дал правила и ход перевода.

Sonic86 в сообщении #852707 писал(а):

(если только Вы по ошибке не вписали его вместо $\leftrightarrow$).

Не вписал. А что, есть разница?

Sonic86 в сообщении #852707 писал(а):

Если Вы работаете в аксиоматической теории, то связки допускаются лишь как сокращения других связок. Т.е. Вам нужно переписать высказывание только через $\neg,\to$

Вроде переписал.

Sonic86 в сообщении #852707 писал(а):

(кстати, связки $\Rightarrow$ обычно нет - откуда Вы ее взяли?).

Эту связку добавил я – вместо одинарной стрелки. Мне показалось так будет понятнее.

Sonic86 в сообщении #852707 писал(а):

Когда Вы перепишите его, то высказывание станет несколько длинноватым, что наводит на подозрения. Обычно народу показывают 2 аксиоматические системы. 1-я - 3-хаксиомная с MP и правилом подстановки, Вы ее привели, только зачем-то некоторые импликации заменили на $\Rightarrow$. Связки $\vee,\wedge$ в формулировках задач для этой системы аксиом обычно не используют. Есть другая система аксиом, со связками $\wedge,\vee$, в ней 10 аксиом, правила вывода те же. Но соотношение $\equiv$ между формулами там тоже не вводится и соотношения вида $F\equiv G$ там не доказываются. У Вас задание представляет из себя какую-то странную смесь алгебры логики и этих двух аксиоматик.

Я правильно понял, проблема в $\equiv$? Но оно дано в условии…

Sonic86 в сообщении #852707 писал(а):

$\urcorner ( A \rightarrow \urcorner (\urcorner B \rightarrow C)) \Rightarrow ((A \rightarrow \urcorner B) \rightarrow \urcorner (A \rightarrow \urcorner C))$
В аксиоматических теориях так не делают: формулу нельзя "разбивать на части" и доказывать "по частям". Если там нужно вывести формулу $F\leftrightarrow G$ из аксиом, то ее переписывают как $(F\to G)\wedge (G\to F)$, а потом, в силу $X\wedge Y = \neg(X\to\neg Y)$, как $\neg ((F\to G)\to\neg (G\to F))$ и выводят ее целиком из аксиом.

Так, может, так и попытаться (я не вижу разницы между $ \equiv $ и $ \leftrightarrow $)? Хотя указанного вами правила перевода и нет в списке предложенных мне. Есть ли альтернативный подход?

[Sonic86]

Kosat в сообщении #852709 писал(а):

Вроде переписал.

Да-да, переписали правильно.

Kosat в сообщении #852709 писал(а):

я не вижу разницы между $ \equiv $ и $ \leftrightarrow $

$\leftrightarrow$ - это связка. Т.е. если $F,G$ - формулы ИВ (АВ), то $F\leftrightarrow G$ - формула ИВ (АВ). $F\equiv G$ - это не формула ИВ (АВ), это просто математическая формула, это соотношение между формулами. Связка - не соотношение.

(Оффтоп)

Kosat в сообщении #852709 писал(а):

Но оно дано в условии…

Что какбе намекает нам...

Kosat в сообщении #852709 писал(а):

Есть ли альтернативный подход?

Sonic86 в сообщении #852707 писал(а):

Часто в таких задачах оговаривают, можно ли использовать теорему дедукции или нет. Можно?

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

[Kosat]

Sonic86 в сообщении #852717 писал(а):

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

Именно с её помощью и решается образец (а точнее, с помощью её следствия). Я попытался скопировать подход при компоновке гипотез (надо будет ещё её применить в конце) - правильно?

А как можно доказать без её применения? Доказательство самой этой теоремы довольно длинное, так что это было бы трудно.

То есть я правильно понял - надо расписать эквивалентность по вашей формуле?

[Sonic86]

Kosat в сообщении #852719 писал(а):

Именно с её помощью и решается образец (а точнее, с помощью её следствия). Я попытался скопировать подход при компоновке гипотез (надо будет ещё её применить в конце) - правильно?

Ааа, вот что это такое. $\vdash$-и надо ставить. Ну да, примерно так и надо. Теорема дедукции в начале поможет мало - только 1 раз можно применить. А дальше придется думать, дальше общих рецептов нет.

Kosat в сообщении #852719 писал(а):

А как можно доказать без её применения?

Ну я же написал уже.

Kosat в сообщении #852719 писал(а):

То есть я правильно понял - надо расписать эквивалентность по вашей формуле?

Ага. Но у меня смутное подозрение, что автор задачи сам ее не решал.

[Kosat]

Sonic86 в сообщении #852724 писал(а):

$\vdash$-и надо ставить.

Там только перед тождеством его можно поставить, вроде...

Sonic86 в сообщении #852724 писал(а):

Ну я же написал уже.

Я не понял. Хотя это и не особо важно. Путь ясен. Спасибо. Буду пробовать.

-- 21.04.2014, 20:46 --

Sonic86 в сообщении #852709 писал(а):

$\neg ((F\to G)\to\neg (G\to F))$

Изначальный вопрос остаётся - что делать с отрицанием над внешними скобками? Ни одна из аксиом и правило не дают ответа. Как строить гипотезы в этом случае? Помогите.