2014 dxdy logo

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

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


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


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

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

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

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

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



Начать новую тему Ответить на тему
 
 Математическая логика
Сообщение11.11.2009, 01:52 


21/03/09
406
Здравствуйте.
Нужна ваша помощь, никак невыходит нигде узнать. Немогу разобраться с некоторыми задачами в математической логике.
Точнее уже неделю ищу где можно ясно и чётко узнать как решать.
Просмотрел кучу книг по Мат. логике, по крайне мере почти все тут http://eqworld.ipmnet.ru/ru/library/mat ... /logic.htm, пробовал найти чтото похожее, но почти полностью безуспешно.

Например если взять легкий пример, как показать что формулу $\[p \to p\]$ можно доказать через торжественные формулы Гильберта?
Тоесть есть следующий набор формул $$\[\begin{array}{l}
 1)\,({x_1} \to ({x_2} \to {x_1})); \\ 
 2)\,((({x_1} \to {x_2}) \to {x_1}) \to {x_1}); \\ 
 3)\,({x_1} \to {x_2}) \to (({x_2} \to {x_3}) \to ({x_1} \to {x_3})); \\ 
 4)\,({x_1} \wedge {x_2}) \to {x_1}; \\ 
 5)\,({x_1} \wedge {x_2}) \to {x_2}; \\ 
 6)\,({x_1} \to {x_2}) \to (({x_1} \to {x_3}) \to ({x_1} \to ({x_2} \wedge {x_3}))); \\ 
 7)\,{x_1} \to ({x_1} \vee {x_2}); \\ 
 8)\,{x_2} \to ({x_1} \vee {x_2}); \\ 
 9)\,({x_1} \to {x_3}) \to (({x_2} \to {x_3}) \to (({x_1} \wedge {x_2}) \to {x_3})); \\ 
 10)\,({x_1} \sim {x_2}) \to ({x_1} \to {x_2}); \\ 
 11)\,({x_1} \sim {x_2}) \to ({x_2} \to {x_1}); \\ 
 12)\,({x_1} \to {x_2}) \to (({x_2} \to {x_1}) \to ({x_1} \sim {x_2})); \\ 
 13)\,({x_1} \to {x_2}) \to (\neg {x_2} \to \neg {x_1}); \\ 
 14)\,{x_1} \to \neg \neg {x_1}; \\ 
 15)\,\neg \neg {x_1} \to {x_1}; \\ 
 \end{array}\]

$$
и правило Modus Ponens.

-- Ср ноя 11, 2009 02:53:15 --

Цитата:
В том списке, который Вы дали, есть "Математическая логика" Клини. У него это пример 4 в параграфе 9.


А есть-ли какойто материал где кратко написано, прочитав который я смогу понять как доказывать. (я просто уже замучился читать)
Или лучше, можете ктонибудь объяснить поэтапно что нужно делать.
У меня есть вот такой список формул примерных заданий
$$\[\begin{array}{l}
 a)\,| - (p\& q) \to (q\& p) \\ 
 b)| - (p \vee q) \to (q \vee p) \\ 
 c)| - ((r\& p) \vee (\neg r\& p)) \to p \\ 
 d)p \to ((q \to p)\& (r \vee p)) \\ 
 e)\neg \neg \neg \neg p \to p \\ 
 f)(p\& q) \to (p \vee q) \\ 
 \end{array}\]$$

P.S.
Модератор, пожалуйста стерите из карантина старую тему. Все условия я надеюсь выполнил.
Насчет того что это торжественные формулы, я не уверен.

 Профиль  
                  
 
 Re: Математическая логика
Сообщение11.11.2009, 02:06 


02/07/08
322
Это есть в книге Н.К. Верещагин, А.Шень. Лекции по математической логике и теории алгоритмов. Часть 2. Языки и исчисления. Есть в свободном доступе на http://www.mccme.ru/free-books/

-- Ср ноя 11, 2009 03:08:52 --

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

 Профиль  
                  
 
 Re: Математическая логика
Сообщение11.11.2009, 02:11 
Заблокирован по собственному желанию
Аватара пользователя


18/05/09
3612
nbyte в сообщении #260711 писал(а):
Модератор, пожалуйста стерите из карантина старую тему...
Насчет того что это торжественные формулы, я не уверен.
Сама стерётся.
Торжественность --- Ваше слово. Подозреваю, что в оригинале тождественость. Но пусть знатоки вопроса поправят.

 Профиль  
                  
 
 Re: Математическая логика
Сообщение11.11.2009, 02:13 
Заслуженный участник
Аватара пользователя


06/10/08
6422
nbyte в сообщении #260711 писал(а):
А есть-ли какойто материал где кратко написано, прочитав который я смогу понять как доказывать.

Доказываете $p\to p$, потом доказываете теорему о дедукции, а потом используете ее :)

 Профиль  
                  
 
 Re: Математическая логика
Сообщение11.11.2009, 02:25 


21/03/09
406
А можете ктонибудь доказать вот эту формулу
$a)\,| - (p\& q) \to (q\& p) \\ $
Тогда у меня будет хоть одно правильное решение и будет на что опереться.
Например через таблицу которую я привел тут или через таблицу которая есть к книге
Цитата:
Н.К. Верещагин, А.Шень. Лекции по математической логике и теории алгоритмов. Часть 2. Языки и исчисления. 47 стр.


P.S.
Ещё хотелбы спросить, как правильно написать знак вывода тоесть $| -$ ?

 Профиль  
                  
 
 Re: Математическая логика
Сообщение11.11.2009, 02:38 
Заслуженный участник
Аватара пользователя


06/10/08
6422
Код:
$\vdash$

$\vdash$

-- Ср ноя 11, 2009 02:43:12 --

Ну, это как раз просто, ИМХО проще, чем $p\to p$.

1.$p\& q \to p$ (A4)
2.$p\& q \to q$ (A5)
3.$(p\& q \to q)\to ((p\& q\to p)\to (p\&q \to q\& p))$ (A3)
4.$(p\& q\to p)\to (p\&q \to q\& p)$ из 3 и 2 по MP
5.$p\&q \to q\& p$ из 4 и 1 по MP

 Профиль  
                  
 
 Re: Математическая логика
Сообщение11.11.2009, 09:55 


21/03/09
406
Бррр... сел сегодня на свежую голову, вродубы дело пошло :)

 Профиль  
                  
 
 Re: Математическая логика
Сообщение11.11.2009, 11:02 


21/03/09
406
Помогите пожалуйста дошел до (c) примера и застрял
Тоесть на этом более сложном $$\[c)| - ((r\& p) \vee (\neg r\& p)) \to p\]
$$
Как его решить используя таблицу
$$\[\begin{array}{l}
 1.1\,A \to (B \to A) \\ 
 1.2\,(A \to (B \to C)) \to ((A \to B) \to (A \to C)) \\ 
  \\ 
 2.1\,(A\& B) \to A \\ 
 2.2\,(A\& B) \to B \\ 
 2.3\,(A \to B) \to ((A \to C) \to (A \to (B\& C))) \\ 
  \\ 
 3.1\,A \to (A \vee B) \\ 
 3.2\,B \to (A \vee B) \\ 
 3.3\,(A \to C) \to ((B \to C) \to ((A \vee B) \to C)) \\ 
  \\ 
 4.1\,(A \to B) \to (\neg B \to \neg A) \\ 
 4.2\,A \to \neg \neg A \\ 
 4.3\,\neg \neg A \to A \\ 
 \end{array}\]
$$
?? :shock:

 Профиль  
                  
 
 Re: Математическая логика
Сообщение11.11.2009, 13:11 


02/07/08
322
2.2, 3.3, MP в какой-то последовательности.

 Профиль  
                  
 
 Re: Математическая логика
Сообщение11.11.2009, 16:53 


21/03/09
406
Неособо я вижу как тут можно это всё применить :roll:
Можете показать, ато мне неясно. Хоть один буду иметь сложный пример как пример, а другие по аналогии буду пробовать решать.

 Профиль  
                  
 
 Re: Математическая логика
Сообщение11.11.2009, 17:05 


02/07/08
322
$A = r\& p, B = \neg r\& p, C = p$. Выведите $A\to C, B\to C$ из 2.2, а затем дважды MP в 3.3 в указанных обозначениях.
Замечание: если сказано, что нужно использовать MP в заданной формуле, то это можно сделать единственным образом: нужно представить формулу как $X\to Y$, заметить, что $X$ уже выведен, и сделать вывод про $Y$.

 Профиль  
                  
 
 Re: Математическая логика
Сообщение12.11.2009, 11:32 


21/03/09
406
Спасибо Cave. Теперь более менее разобрался.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 12 ] 

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



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

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


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

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