2014 dxdy logo

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

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


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


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



Начать новую тему Ответить на тему На страницу 1, 2, 3  След.
 
 Помогите доказать одну из секвенций
Сообщение17.11.2018, 18:05 


17/11/18
17
Нужно доказать одну из секвенций, любую из двух, я даже не знаю с чего начать доказательство
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/

 Профиль  
                  
 
 Posted automatically
Сообщение17.11.2018, 18:08 
Супермодератор
Аватара пользователя


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

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

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

 Профиль  
                  
 
 Posted automatically
Сообщение17.11.2018, 21:57 
Супермодератор
Аватара пользователя


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

 Профиль  
                  
 
 Re: Помогите доказать одну из секвенций
Сообщение17.11.2018, 22:59 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Помогите доказать одну из секвенций
Сообщение17.11.2018, 23:17 


17/11/18
17
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$)

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

 Профиль  
                  
 
 Re: Помогите доказать одну из секвенций
Сообщение17.11.2018, 23:29 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Помогите доказать одну из секвенций
Сообщение17.11.2018, 23:59 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Помогите доказать одну из секвенций
Сообщение18.11.2018, 00:17 


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

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

 Профиль  
                  
 
 Re: Помогите доказать одну из секвенций
Сообщение18.11.2018, 00:20 
Заслуженный участник


31/12/15

895
Во-первых, в правиле 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)$

 Профиль  
                  
 
 Re: Помогите доказать одну из секвенций
Сообщение18.11.2018, 19:20 
Заслуженный участник


31/12/15

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

 Профиль  
                  
 
 Re: Помогите доказать одну из секвенций
Сообщение25.11.2018, 21:59 


17/11/18
17
Правая часть :
$(\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}}$

 Профиль  
                  
 
 Re: Помогите доказать одну из секвенций
Сообщение25.11.2018, 22:56 
Заслуженный участник


31/12/15

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

 Профиль  
                  
 
 Re: Помогите доказать одну из секвенций
Сообщение26.11.2018, 00:15 
Заслуженный участник
Аватара пользователя


27/04/09
27506
Их же «линеаризовать» можно. :-)

 Профиль  
                  
 
 Опять попалась секвенция,не знаю с чего начать доказательств
Сообщение06.12.2018, 20:51 


17/11/18
17
george66

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

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

 Профиль  
                  
 
 Re: Помогите доказать одну из секвенций
Сообщение06.12.2018, 22:22 
Заслуженный участник


31/12/15

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

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

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



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

Сейчас этот форум просматривают: dtn888


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

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