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
22918
Кронштадт
 i  Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
по следующим причинам:

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

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

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


09/05/12
22918
Кронштадт
 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
28093
Их же «линеаризовать» можно. :-)

 Профиль  
                  
 
 Опять попалась секвенция,не знаю с чего начать доказательств
Сообщение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  След.

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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