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

[Danila1J]

Нужно доказать одну из секвенций, любую из двух, я даже не знаю с чего начать доказательство
1. $\Phi_1,(\Phi_1\to\Phi_2),(\Phi_2\to\Phi_3)\vdash\Phi_3$
2. $\neg(\Phi_1\to\Phi_2),\neg(\Phi_2\to\Phi_1)\vdash\chi$
Для первой секвенции пробовал применить 8 и 7 правило вывода, но что-то дальше я не понял что с этим можно сделать:
$\cdots\hspace{130pt}\overline{\Phi_1,(\Phi_1\to\Phi_2),(\Phi_2\to\Phi_3),\Phi_2\vdash\Phi_3}$
$\overline{\Phi_1,(\Phi_1\to\Phi_2),(\Phi_2\to\Phi_3)\vdash\Phi_2};\overline{\Phi_1,(\Phi_1\to\Phi_2),(\Phi_2\to\Phi_3)\vdash\Phi_2\to\Phi_3}(7)$
$\overline{\Phi_1,(\Phi_1\to\Phi_2),(\Phi_2\to\Phi_3)\vdash\Phi_3\hspace{170pt}}$(8)

Правила вывода:https://studfiles.net/preview/311051/page:2/

[Pphantom]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
по следующим причинам:

- неправильно набраны формулы (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы);
- отсутствуют собственные содержательные попытки решения задач.

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[Pphantom]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

[JohnDou]

Предложу вам послать к черту эти "правила вывода", и решать задачу своей головой.
На практике это выглядит следующим образом:
1. Можно попробовать заменить буквы конкретными утверждениями:
Например, пусть $\Phi_1:=$ "на улице светит солнце",
$\Phi_2:=$ "Фома идёт гулять", $\Phi_3:=$ "Бобик идёт гулять".
Тогда $\Phi_1\to \Phi_2$ будет: "Если на улице солнечно, Фома гуляет". А $\Phi_2\to \Phi_3$: "Фома боится гулять один, и поэтому гуляет с Бобиком". И тогда ответ на вопрос:"На улице ли Бобик, если светит солнце?" Становится очевидным.
2. Если влом придумывать утверждения, в "секвенциях" замените ","(запятые) на "и", и разложите полученную формулу по таблицам истины. В финальной колонке, в 2., у вас будут стоять одни "-"(или "F", итп), это и будет означать Х (т.е. секвенция не может быть истинной ни при каких значениях $\Phi_1, \Phi_2$)

[Danila1J]

JohnDou в сообщении #1354808 писал(а):

Предложу вам послать к черту эти "правила вывода", и решать задачу своей головой.
На практике это выглядит следующим образом:
1. Можно попробовать заменить буквы конкретными утверждениями:
Например, пусть $\Phi_1:=$ "на улице светит солнце",
$\Phi_2:=$ "Фома идёт гулять", $\Phi_3:=$ "Бобик идёт гулять".
Тогда $\Phi_1\to \Phi_2$ будет: "Если на улице солнечно, Фома гуляет". А $\Phi_2\to \Phi_3$: "Фома боится гулять один, и поэтому гуляет с Бобиком". И тогда ответ на вопрос:"На улице ли Бобик, если светит солнце?" Становится очевидным.
2. Если влом придумывать утверждения, в "секвенциях" замените ","(запятые) на "и", и разложите полученную формулу по таблицам истины. В финальной колонке, в 2., у вас будут стоять одни "-"(или "F", итп), это и будет означать Х (т.е. секвенция не может быть истинной ни при каких значениях $\Phi_1, \Phi_2$)

Спасибо,с подобным объяснением стало более понятно как это работает,но всё же надо с помощью правил вывода доказать "секвенцию".
Также спасибо за подсказку что вторую "секвенцию" нельзя доказать

[JohnDou]

Danila1J, так это не подсказка, это условие: надо показать что "секвенция" не может быть правдивой т.е. $\chi$ (я это обозвал как Х).
А "правила" - не что иное как запись вышесказанного через спец. символы. Если вы это сдаёте кому-то, думаю, этот человек не будет против, если вы просто покажете ему таблицы.

[gefest_md]

Danila1J, по ссылке посмотрите, что такое доказательство, не только правило вывода. Для доказательства секвенции 1 нужны аксиома и правила вывода 8, 12. Удобно начинать поиск с конца. Из каких двух секвенций (как-бы то, что над чертой в правиле 8) следует секвенция 1 (под чертой)? Потом эти две секвенции из чего следуют? И т.д. Доказательство обычно имеет вид списка секвенций, секвенция 1 - последняя.

[Danila1J]

gefest_md в сообщении #1354814 писал(а):

Danila1J, по ссылке посмотрите, что такое доказательство, не только правило вывода. Для доказательства секвенции 1 нужны аксиома и правила вывода 8, 12. Удобно начинать поиск с конца. Из каких двух секвенций (как-бы то, что над чертой в правиле 8) следует секвенция 1 (под чертой)? Потом эти две секвенции из чего следуют? И т.д. Доказательство обычно имеет вид списка секвенций, секвенция 1 - последняя.

Доказательство у меня снизу вверх идёт

[george66]

Во-первых, в правиле 8 опечатка (вверху слева вместо $\Gamma,A$ должно быть $\Gamma\vdash A$)
Давайте выведем секвенцию $\Phi_1,(\Phi_1\to\Phi_2)\vdash\Phi_2$
(лучше было бы $A,(A\to B)\vdash B$ потому что в правилах буквы латинские, но мы не боимся трудностей)
Начинаем с аксиомы $\Phi_1\vdash\Phi_1$
Содержательно "Из гипотезы $\Phi_1$ можно вывести $\Phi_1$"
Применяем к ней ослабление (правило 12), получаем
$\Phi_1,(\Phi_1\to\Phi_2)\vdash\Phi_1$
Содержательно "Из гипотезы $\Phi_1$ и ещё какой-то гипотезы всё равно можно вывести $\Phi_1$"
Контекст $\Gamma$ в правиле 12 здесь состоит из одной формулы $\Phi_1$
Дальше берём аксиому $(\Phi_1\to\Phi_2)\vdash(\Phi_1\to\Phi_2)$
Применяем правило ослабления (правило 12)
$(\Phi_1\to\Phi_2),\Phi_1\vdash(\Phi_1\to\Phi_2)$
контекст $\Gamma$ в правиле 12 здесь состоит из одной формулы $(\Phi_1\to\Phi_2)$
и затем правило перестановки гипотез (правило 11)
$\Phi_1,(\Phi_1\to\Phi_2)\vdash(\Phi_1\to\Phi_2)$
Контексты $\Gamma,\Gamma_1$ в правиле 11 здесь пустые.
К полученным двум секвенциям
$\Phi_1,(\Phi_1\to\Phi_2)\vdash\Phi_1$
$\Phi_1,(\Phi_1\to\Phi_2)\vdash(\Phi_1\to\Phi_2)$
применяем исправленное от опечатки правило 8 (Modus Ponens) и получаем
$\Phi_1,(\Phi_1\to\Phi_2)\vdash\Phi_2$
Контекст $\Gamma$ здесь $\Phi_1,(\Phi_1\to\Phi_2)$

[george66]

Вторая секвенция тоже верна, но доказать её труднее. Если непонятно, спрашивайте.
Также радикальный совет: скачайте мой учебник и почитайте главу "Исчисление высказываний" (её можно читать независимо от предыдущей части книги)
https://github.com/George66/Textbook

[Danila1J]

Правая часть :
$(\Phi_2\to\Phi_3)\vdash(\Phi_2\to\Phi_3)$ (12)
$\overline{(\Phi_2\to\Phi_3),\Phi_1\vdash(\Phi_2\to\Phi_3)}$ (11)
$\overline{\Phi_1,(\Phi_2\to\Phi_3)\vdash(\Phi_2\to\Phi_3)}$ (12)
$\overline{\Phi_1,(\Phi_2\to\Phi_3),(\Phi_1\to\Phi_2)\vdash(\Phi_2\to\Phi_3)}$ (11)
$\overline{\Phi_1,(\Phi_1\to\Phi_2),(\Phi_2\to\Phi_3)\vdash(\Phi_2\to\Phi_3)}$

Левая часть:
$.\hspace{130pt}\(\Phi_1\to\Phi_2)\vdash\(\Phi_1\to\Phi_2)$ (12)
$\Phi_1\vdash\Phi_1\hspace{90}\overline{(\Phi_1\to\Phi_2),\Phi_1\vdash\(\Phi_1\to\Phi_2)}$ (11)
(8)$\overline{\Phi_1,(\Phi_1\to\Phi_2)\vdash\Phi_1;}\hspace{40}\overline{\Phi_1,(\Phi_1\to\Phi_2)\vdash\(\Phi_1\to\Phi_2)}$ (8)
$\overline{\Phi_1,(\Phi_1\to\Phi_2)\vdash\Phi_2\hspace{150pt}(12)}$
$\overline{\Phi_1,(\Phi_1\to\Phi_2),(\Phi_2\to\Phi_3)\vdash\Phi_2}$

И применяем правило (8) для:
$\overline{\Phi_1,(\Phi_1\to\Phi_2),(\Phi_2\to\Phi_3)\vdash\Phi_2};\overline{\Phi_1,(\Phi_1\to\Phi_2),(\Phi_2\to\Phi_3)\vdash(\Phi_2\to\Phi_3)}$(8)
$\overline{\hspace{60pt}\Phi_1,(\Phi_1\to\Phi_2),(\Phi_2\to\Phi_3)\vdash\Phi_3\hspace{100pt}}$

[george66]

Да, всё правильно, поздравляю! В одном месте (на левом краю) цифру 8 замените на 12. Очень увлекательно эти деревья набирать, сколько я их набрал, пока писал учебник.

[arseniiv]

Их же «линеаризовать» можно.

[Danila1J]

george66

,можете подсказать с чего начать хотя бы ,спасибо.

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

[george66]

Ну, начинать всегда надо с аксиом
$\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 и правил для дизъюнкции.