2014 dxdy logo

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

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


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


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Доказать в исчислении высказываний
Сообщение22.03.2013, 14:30 


22/03/13
6
Доказать в исчислении высказываний (буквы обозначают произвольные формулы):
$(A\to B) \to((C \lor (A \to C)) \lor B)$
есть 3 аксиомы:
1. $ A  \to (B \to A)$
2.$(A \to (B \to C)) \to ((A \to B) \to (A \to C))$
3.$(\neg B \to \neg A) \to ((\neg B \to A) \to B)$

и 9 сенкквенций:
1. $(A \to B, B \to C) \vdash A \to C $
2. $A \to (B \to C), B \vdash A  \to C $
3. $ \vdash(\neg \neg A \to A)$
4. $\vdash(A \to \neg \neg A)$
5. $\vdash A \to (\neg A \to B)$
6. $ \vdash(\neg B \to \neg A) \to (A \to B)$
7. $\vdash (A \to B) \to (\neg B \to \neg A)$
8.$\vdash (A \to (\neg B \to \neg (A \to B)))$
9.$\vdash (A \to B) \to ((\neg A \to B) \to B)$

с чего хоть начать? какую из этих формул можно применить?
Спасибо.

 Профиль  
                  
 
 Re: Доказать в исчислении высказываний
Сообщение22.03.2013, 14:46 
Заслуженный участник


08/04/08
8556
eholot в сообщении #699830 писал(а):
и 9 сенкквенций:
В смысле приведенными выводимостями можно пользоваться для доказательства 1-й формулы? Или их тоже вывести нужно?
Можно ли пользоваться теоремой дедукции? Правило вывода modus ponens тоже есть?

eholot в сообщении #699830 писал(а):
с чего хоть начать? какую из этих формул можно применить?
Сначала надо хотя бы связку $\vee$ в формуле, которую хотите доказать, переписать через связку $\to$.

 Профиль  
                  
 
 Re: Доказать в исчислении высказываний
Сообщение22.03.2013, 15:05 


22/03/13
6
секвенциями можно пользоваться, выводить их не надо.
теоремой дедукции и модус понес тоже можно.

правильно ли я понимаю:
если $P \lor Q \Leftrightarrow Q \lor P$ и $P \lor Q \Leftrightarrow \neg P \to Q$

значит
$((C \lor (A \to C)) \lor B) \Leftrightarrow (B \lor (C \lor (A \to C))) \Leftrightarrow ( \neg B \to (C \lor (A \to C))) \Leftrightarrow $ ( \neg B \to ( \neg C \to (A \to C)))

 Профиль  
                  
 
 Re: Доказать в исчислении высказываний
Сообщение22.03.2013, 15:11 
Заслуженный участник


08/04/08
8556
eholot в сообщении #699849 писал(а):
теоремой дедукции и модус понес тоже можно.
О, хорошо.

eholot в сообщении #699849 писал(а):
значит
$((C \lor (A \to C)) \lor B) \Leftrightarrow (\neg B \to (\neg C \to (A \to C)))$
Согласно теореме дедукции, исходная формулы выводима тогда и только тогда, когда из гипотез выводима формула, получаемая из исходной формулы многократным применением теоремы дедукции до упора. Вот можно ее выписать и там видно, что она распадается на подзадачу и "остаток".
Это, конечно, не единственный способ (м.б. Вам надо явно вывод построить?)
Ну вообще простых алгоритмов вывода вроде нет. Можете сами попытаться сделать пару выводов, заметить какие-то закономерности, потом попытаться их применить...

 Профиль  
                  
 
 Re: Доказать в исчислении высказываний
Сообщение22.03.2013, 15:17 


22/03/13
6
честно говоря, не очень понял...

 Профиль  
                  
 
 Re: Доказать в исчислении высказываний
Сообщение22.03.2013, 15:24 
Заслуженный участник


08/04/08
8556
eholot в сообщении #699856 писал(а):
честно говоря, не очень понял...
теорема дедукции утверждает следующее: $X\vdash Y \Leftrightarrow \vdash (X\to Y)$. С помощью нее Вы можете доказывать не $\vdash (X\to Y)$, а $X\vdash Y$. Построение 2-го вывода мне кажется легче: увеличивается число посылок слева, укорачивается формула, которую надо вывести, посылки становятся "несимметричными", что помогает выбирать то, что можно пытаться выводить. Я Вам предлагаю из Вашей исходной формулы (запишите ее явно) построить с помощью теоремы дедукции записать выражение вида $X\vdash Y$.

 Профиль  
                  
 
 Re: Доказать в исчислении высказываний
Сообщение22.03.2013, 16:04 


22/03/13
6
Sonic86 в сообщении #699859 писал(а):
eholot в сообщении #699856 писал(а):
честно говоря, не очень понял...
теорема дедукции утверждает следующее: $X\vdash Y \Leftrightarrow \vdash (X\to Y)$. С помощью нее Вы можете доказывать не $\vdash (X\to Y)$, а $X\vdash Y$. Построение 2-го вывода мне кажется легче: увеличивается число посылок слева, укорачивается формула, которую надо вывести, посылки становятся "несимметричными", что помогает выбирать то, что можно пытаться выводить. Я Вам предлагаю из Вашей исходной формулы (запишите ее явно) построить с помощью теоремы дедукции записать выражение вида $X\vdash Y$.

$(A\to B) \to((C \lor (A \to C)) \lor B)$
$(A\to B)\vdash ((C \lor (A \to C)) \lor B)$
$(A\to B) \vdash  (\neg B \to ( \neg C \to (A \to C)))$

 Профиль  
                  
 
 Re: Доказать в исчислении высказываний
Сообщение22.03.2013, 16:47 
Заслуженный участник


08/04/08
8556
eholot в сообщении #699876 писал(а):
$(A\to B) \to((C \lor (A \to C)) \lor B)$
$(A\to B)\vdash ((C \lor (A \to C)) \lor B)$
Ага.

eholot в сообщении #699876 писал(а):
$(A\to B)\vdash ((C \lor (A \to C)) \lor B)$
$(A\to B) \vdash (\neg B \to ( \neg C \to (A \to C)))$
А этот переход откуда? Если Вы воспользовались коммутативностью дизъюнкции, то у Вас вообще-то этой коммутативности нету. Либо ее надо выводить и там применять (было бы очень удобно, кстати)
После преобразования удобно применить теорему дедукции еще раз.

 Профиль  
                  
 
 Re: Доказать в исчислении высказываний
Сообщение22.03.2013, 16:57 


22/03/13
6
Sonic86 в сообщении #699895 писал(а):
А этот переход откуда?


если $P \lor Q \Leftrightarrow Q \lor P$ и $P \lor Q \Leftrightarrow \neg P \to Q$
значит
$((C \lor (A \to C)) \lor B) \Leftrightarrow (B \lor (C \lor (A \to C))) \Leftrightarrow ( \neg B \to (C \lor (A \to C))) \Leftrightarrow $ ( \neg B \to ( \neg C \to (A \to C)))

или это неправильно?

Sonic86 в сообщении #699895 писал(а):
После преобразования удобно применить теорему дедукции еще раз.

то есть правильно я понимаю:
$(A\to B) \vdash (\neg B \to ( \neg C \to (A \to C)))$
$\neg B \vdash (\neg C \to (A \to C))$

 Профиль  
                  
 
 Re: Доказать в исчислении высказываний
Сообщение22.03.2013, 17:19 
Заслуженный участник


08/04/08
8556
eholot в сообщении #699901 писал(а):
$P \lor Q \Leftrightarrow Q \lor P$
Ну я и говорю: Вы пользуетесь коммутативностью дизъюнкции, но у нас она разве есть? У нас же ничего кроме MP, теоремы дедукции, аксиом и 9 секвенций нету. Впрочем, у нас есть секвенции 6 и 7, но тогда надо попытаться применить их предварительно.

eholot в сообщении #699901 писал(а):
или это неправильно?
Кстати, знака $\Leftrightarrow$ в ИВ тоже нет (т.е. в выводе его не должно быть). В ИВ формула $A\vee B$ - это просто обозначение $\neg A\to B$, причем никаких свойств этого обозначения мы не знаем (хотя они есть). Если мы какие-то его свойства хотим использовать, то их доказать нужно.

eholot в сообщении #699901 писал(а):
то есть правильно я понимаю:
$(A\to B) \vdash (\neg B \to ( \neg C \to (A \to C)))$
$\neg B \vdash (\neg C \to (A \to C))$
Если Вы до 1-й формулы дойдете (пока явно не дошли), то не так: у Вас 1-я гипотеза слева пропала, должно получиться две гипотезы:
$(A\to B) \vdash (\neg B \to ( \neg C \to (A \to C)))$ выводимо тогда и только тогда, когда выводимо $(A\to B), \neg B \vdash \neg C \to (A \to C)$. Опять же, если до исходной точки дойдем, то можем применить теорему дедукции уже 3-й раз.

 Профиль  
                  
 
 Re: Доказать в исчислении высказываний
Сообщение22.03.2013, 17:23 


22/03/13
6
спасибо большое за помощь, сейчас как раз на лекцию по логике иду ) уточню можно ли применять коммутативность дизьюнкции

 Профиль  
                  
 
 Re: Доказать в исчислении высказываний
Сообщение22.03.2013, 17:32 
Заслуженный участник


08/04/08
8556
eholot в сообщении #699917 писал(а):
уточню можно ли применять коммутативность дизьюнкции
там еще нужно учесть следующее: в алгебре высказываний мы не просто знаем, что дизъюнкция коммутативна, мы еще и можем заменять в формуле любую подформулу на эквивалентную (в частности, если где-то внутри длинной формулы у нас появилась дизъюнкция, мы можем внутри переставить ее члены). В исчислении высказываний такого явно нет: преобразовать подформулу в формуле можно лишь преобразовывая всю формулу явно (что, естественно, сложнее), либо надо использовать специальные правила вывода для этого.

 Профиль  
                  
 
 Re: Доказать в исчислении высказываний
Сообщение22.03.2013, 18:34 
Заслуженный участник


27/04/09
28128
Sonic86 в сообщении #699915 писал(а):
В ИВ формула $A\vee B$ - это просто обозначение $\neg A\vee B$
Опечатка, $\neg A\to B$ ведь. :-)

 Профиль  
                  
 
 Re: Доказать в исчислении высказываний
Сообщение22.03.2013, 18:39 
Заслуженный участник


08/04/08
8556
arseniiv в сообщении #699949 писал(а):
Опечатка, $\neg A\to B$ ведь. :-)
Ой, действительно, сейчас исправлю.

 Профиль  
                  
 
 Re: Доказать в исчислении высказываний
Сообщение20.06.2018, 16:10 


02/09/17
1
Здравствуйте! У меня аналогичный пример.
Вот к чему я пришел.
(A\to B)\to ((C\vee (A\to C))\vee B)
Было разрешено делать преобразование конъюнкции и дизъюнкции в импликации и обратно во внутренних импликации.
Таким образом
(A\to B)\to (\neg (C\vee (A\to C))\to B)
1) (A\to B) -гипотеза
2) \neg (C\vee (A\to C)) -гипотиза
3) \neg C\wedge \neg(A\to C) -по де Моргану
4) \neg C -свойство конъюнкции
5) \neg(A\to C) -свойство конъюнкции

Подскажите куда мне двигаться. Я же должен в итоге получить B?

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

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



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

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


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

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