Помогите доказать одну из секвенций

[gefest_md]

Danila1J в сообщении #1359327 писал(а):

с чего начать

Повторюсь. Начинать с конца. По правилу вывода 7, чтобы доказать секвенцию $\neg(\Phi_1\vee\Phi_2)\vdash(\Phi_1\to\Phi_3)$ (под чертой) надо доказать секвенцию $\neg(\Phi_1\vee\Phi_2),\Phi_1\vdash\Phi_3$. Далее.

1. Что можно получить напрямую из допущений $\neg(\Phi_1\vee\Phi_2),\,\Phi_1$? Получаете: это две секвенции, с этими допущениями слева. Потом к одной из них применяете правило 4. Затем к нужным двум секвенциям применяете правило 10. Наконец правила 12, 9 и 7, в этом порядке.

2. Можно смотреть по списку правил где под чертой стоит одна буква после $\vdash$ в правиле вывода. Потому что $\Phi_3$ одна буква. И пробовать варианты.

[Danila1J]

george66 в сообщении #1359359 писал(а):

Ну, начинать всегда надо с аксиом
$\neg(\Phi_1\vee\Phi_2)\vdash\neg(\Phi_1\vee\Phi_2)$
А предпоследняя секвенция должна быть такая
$\neg(\Phi_1\vee\Phi_2),\Phi_1\vdash\Phi_3$
и к ней применить правило 7.
А посередине надо ужом вертеться, поскольку система правил дурацкая. Попробуйте доказать пред-предпоследнюю секвенцию такую
$\neg(\Phi_1\vee\Phi_2),\Phi_1,\neg\Phi_3\vdash$
что содержательно значит "из перечисленных трёх посылок следует противоречие" и к ней примените правило 9. Противоречие же следует как-то доказать с помощью правила 10 и правил для дизъюнкции.

Так-с,ну я что-то сделал,не могли бы вы посмотреть:
Левый:
$\Phi_1\vdash\Phi_1$
$\overline{\Phi_1\vdash(\Phi_1\vee\Phi_2)(4)}$
$\overline{\Phi_1,\neg(\Phi_1\vee\Phi_2)\vdash(\Phi_1\vee\Phi_2)(12)}$
$\overline{\neg(\Phi_1\vee\Phi_2),\Phi_1\vdash(\Phi_1\vee\Phi_2)(11)}$
$\overline{\neg(\Phi_1\vee\Phi_2),\Phi_1\,\neg\Phi_3\vdash(\Phi_1\vee\Phi_2);(12)}$
Правый:
$\neg(\Phi_1\vee\Phi_2)\vdash\neg(\Phi_1\vee\Phi_2)$
$\overline{\neg(\Phi_1\vee\Phi_2),\Phi_1\vdash\neg(\Phi_1\vee\Phi_2) (12)}$
$\overline{\neg(\Phi_1\vee\Phi_2),\Phi_1,\neg\Phi_3\vdash\neg(\Phi_1\vee\Phi_2) (12)}$
А теперь соединение двух столбцов.
$\overline{\neg(\Phi_1\vee\Phi_2),\Phi_1,\neg\Phi_3\vdash(10)}$
$\overline{\neg(\Phi_1\vee\Phi_2),\Phi_1\vdash\Phi_3(9)}$
$\overline{\neg(\Phi_1\vee\Phi_2)\vdash(\Phi_1\to\Phi_3)(7)}$

Надеюсь я понятно написал, просто я пока не понимаю как аккуратно записать это в виде дерева.

[george66]

Да, всё правильно, поздравляю.

[Danila1J]

Можете проверить?

Левый столбец:
$(\Phi_1\wedge\Phi_2)\vdash(\Phi_1\wedge\Phi_2)(3)$
$\overline{(\Phi_1\wedge\Phi_2)\vdash\Phi_2(12)}$
$\overline{(\Phi_1\wedge\Phi_2),\Phi_1\vdash\Phi_2(7)}$
$\overline{(\Phi_1\wedge\Phi_2)\vdash(\Phi_1\to\Phi_2)(12)}$
$\overline{(\Phi_1\wedge\Phi_2),\Phi_3\vdash(\Phi_1\to\Phi_2)(1);}$

Правый столбец:
$\Phi_3\vdash\Phi_3(12)$
$\overline{(\Phi_1\wedge\Phi_2),\Phi_3\vdash\Phi_3(1)}$

И объединение двух столбцов с помощью первого правила:
$(\Phi_1\wedge\Phi_2),\Phi_3\vdash((\Phi_1\to\Phi_2)\wedge\Phi_3)$

[george66]

Да, всё правильно, только в правом столбце ещё вставьте перестановку (правило 11)

[Danila1J]

У меня очень большие сомнения насчёт правильности написанного ниже.
Левый столбец:
$\neg\Phi_2\vdash\neg\Phi_2 (12)$
$\overline{\neg\Phi_2\,(\Phi_1\to\Phi_2)\vdash\neg\Phi_2 (11)}$
$\overline{(\Phi_1\to\Phi_2),\neg\Phi_2\vdash\neg\Phi_2 (12)}$
$\overline{(\Phi_1\to\Phi_2),\neg\Phi_2,\Phi_3\vdash\neg\Phi_2 (12)}$
$\overline{(\Phi_1\to\Phi_2),\neg\Phi_2,\Phi_3,\neg\Phi_1\vdash\neg\Phi_2 ;(10)}$

Правый столбец:
Не знаю как доказать $(\Phi_1\to\Phi_2),\neg\Phi_2,\Phi_3,\neg\Phi_1\vdash\Phi_2$

Объединение столбцов:
$\overline{(\Phi_1\to\Phi_2),\neg\Phi_2,\Phi_3,\neg\Phi_1\vdash (9)}$
$\overline{(\Phi_1\to\Phi_2),\neg\Phi_2,\Phi_3\vdash\Phi_1 (7)}$
$\overline{(\Phi_1\to\Phi_2),\neg\Phi_2\vdash(\Phi_3\to\Phi_1)}$

[george66]

Заключительная секвенция вообще неверная, поэтому её нельзя доказать. Если $\Phi_1$ и $\Phi_2$ ложны, а $\Phi_3$ истинна, то обе посылки истинны, а заключение ложно.

[Danila1J]

То есть эта секвенция недоказуема,да?


$(\Phi_1\to\Phi_2),\neg\Phi_2\vdash(\Phi_3\to\Phi_1)$

Всё,вроде понял

-- 12.12.2018, 22:35 --

Хм, а с этой что можно сделать $\Phi_1,\neg(\Phi_1\vee\Phi_2)\vdash\Phi_3$

[george66]

Выведите из посылок противоречие.

[Danila1J]

george66
И снова здравствуйте.
У меня тут небольшая проблемка.
$\neg(\Phi_1\wedge\Phi_2)\vdash\neg(\Phi_1\wedge\Phi_2); \neg(\Phi_1\wedge\Phi_2)\vdash(\neg\Phi_1\vee\neg\Phi_2)$
$\overline{\neg(\Phi_1\wedge\Phi_2)\vdash(\neg(\Phi_1\wedge\Phi_2)\wedge(\neg\Phi_1\vee\neg\Phi_2))(1)}$
С правой частью всё отлично у нас сразу аксиома.А в левой части как я понимаю получается закон де Моргана и как его доказывать?

[george66]

От противного. Предположите $\neg(\neg\Phi_1\vee\neg\Phi_2)$ и выведите противоречие
$\neg(\Phi_1\wedge\Phi_2), \neg(\neg\Phi_1\vee\neg\Phi_2)\vdash$

[Danila1J]

Хорошо сейчас попробую

-- 10.01.2019, 01:03 --

$\neg(\neg\Phi_1\vee\neg\Phi_2)\vdash\Phi_1;\neg(\neg\Phi_1\vee\neg\Phi_2)\vdash\Phi_2$
$\overline{(1)\neg(\neg\Phi_1\vee\neg\Phi_2)\vdash\Phi_1\wedge\Phi_2\hspace{30pt}}\hspace{70pt}\neg(\Phi_1\wedge\Phi_2)\vdash\neg(\Phi_1\wedge\Phi_2)$
$\overline{(11,12)\neg(\Phi_1\wedge\Phi_2),(\neg\Phi_1\vee\neg\Phi_2)\vdash\Phi_1\wedge\Phi_2;\neg(\Phi_1\wedge\Phi_2),(\neg\Phi_1\vee\neg\Phi_2)\vdash\neg(\Phi_1\wedge\Phi_2)(12)}$
$\overline{.\hspace{130pt}\neg(\Phi_1\wedge\Phi_2),(\neg\Phi_1\vee\neg\Phi_2)\vdash\hspace{95pt}(10)}$

-- 10.01.2019, 01:03 --

Сомневаюсь что я сделал правильно,но даже если и так то я не знаю что делать дальше

[gefest_md]

Danila1J
Секвенции из первой строки тоже можно доказать от противного. В строках 3 и 4 потеряли знак отрицания. К четвертой строке примените (9).

[george66]

Всё правильно, только знак отрицания кое-где действительно потеряли, в третьей и четвёртой строке написано $\neg\Phi_1\vee\neg\Phi_2$, а надо $\neg(\neg\Phi_1\vee\neg\Phi_2)$
Теперь докажите секвенции
$\neg(\neg\Phi_1\vee\neg\Phi_2),\neg\Phi_1\vdash$
$\neg(\neg\Phi_1\vee\neg\Phi_2),\neg\Phi_2\vdash$
и в самом верху их прилепите.

[Danila1J]

Так:
$.\hspace{20pt}\neg\Phi_1\vdash\neg\Phi_1$
$(4)\hspace{10pt}\overline{\neg\Phi_1\vdash(\neg\Phi_1\vee\neg\Phi_2)}\hspace{90pt} \neg(\neg\Phi_1\vee\neg\Phi_2)\vdash\neg(\neg\Phi_1\vee\neg\Phi_2)$
$(11,12)\overline{\neg(\neg\Phi_1\vee\neg\Phi_2),\neg\Phi_1\vdash(\neg\Phi_1\vee\neg\Phi_2)};\overline{\neg(\neg\Phi_1\vee\neg\Phi_2),\neg\Phi_1\vdash\neg(\neg\Phi_1\vee\neg\Phi_2)(12)}$
$(10)\hspace{130pt}\overline{\neg(\neg\Phi_1\vee\neg\Phi_2),\neg\Phi_1\vdash}$