2014 dxdy logo

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

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


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


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



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


01/12/06
697
рм
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$ одна буква. И пробовать варианты.

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


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

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

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


31/12/15
922
Да, всё правильно, поздравляю.

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


17/11/18
17
Можете проверить?

Левый столбец:
$(\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)$

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


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

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


17/11/18
17
У меня очень большие сомнения насчёт правильности написанного ниже.
Левый столбец:
$\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)}$

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


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

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


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


$(\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$

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


31/12/15
922
Выведите из посылок противоречие.

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


17/11/18
17
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)}$
С правой частью всё отлично у нас сразу аксиома.А в левой части как я понимаю получается закон де Моргана и как его доказывать?

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


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

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


17/11/18
17
Хорошо сейчас попробую

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

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

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


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

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


31/12/15
922
Всё правильно, только знак отрицания кое-где действительно потеряли, в третьей и четвёртой строке написано $\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$
и в самом верху их прилепите.

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


17/11/18
17
Так:
$.\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}$

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

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



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

Сейчас этот форум просматривают: Google [Bot], Vladimir Pliassov


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

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