2014 dxdy logo

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

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки
01/01/18 20:50 UTC: Перешли на HTTPS в тестовом режиме. О проблемах пишите в ЛС cepesh.



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


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

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

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

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

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



Начать новую тему Ответить на тему
 
 Логика высказываний
Сообщение08.12.2014, 22:44 


08/12/14
3
Совсем не понимаю, как доказывать теоремы в системе аксиом L. Со стороны для это выглядит магией, в которой нужно иметь супер интуиции или же решать банальным перебором.
Мне нужно решить конкретно такой пример:
$(\overline{C}\implies \overline{A \wedge B}) \implies (\overline{C} \implies \overline{A}) \vee (\overline{C} \implies \overline {B})$

Система аксиом:

$A1: A \implies ( B \implies  A)\\
A2: (A \implies ( B \implies  C) \implies ((A \implies B) \implies (A \implies C)))\\
A3: (\lnot B \implice \lnot A) \implies ((\lnot B \implies A) \implies B)
$

Можно использовать теоремы(10) MP и теорему о дедукции. Был бы рад комментариям, где бы были описаны причины выбора той или иной формулы

 Профиль  
                  
 
 Posted automatically
Сообщение08.12.2014, 22:53 
Модератор


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

1. Запишите формулы в соответствии с требованиями Правил форума, т.е. в $\TeX$.
Краткие инструкции можно найти здесь: topic8355.html и topic183.html.
Кроме этого, в теме Видео-пособия для начинающих форумчан можно посмотреть видео-ролик "Как записывать формулы".

2. Приведите свои попытки решения и/или укажите затруднения.

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

 Профиль  
                  
 
 Posted automatically
Сообщение14.12.2014, 19:56 
Модератор


20/03/14
7823
 i  Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

 Профиль  
                  
 
 Re: Логика высказываний
Сообщение14.12.2014, 20:29 
Заслуженный участник


08/04/08
8417
IvanEh в сообщении #942706 писал(а):
Можно использовать теоремы(10)
Что за теоремы?

IvanEh в сообщении #942706 писал(а):
Мне нужно решить конкретно такой пример:
$(\overline{C}\implies \overline{A \wedge B}) \implies (\overline{C} \implies \overline{A}) \vee (\overline{C} \implies \overline {B})$
У Вас в формуле присутствуют связки $\vee, \wedge$, в указанных аксиомах они отсутствуют. Чего-то не хватает: определений связок или аксиом.
Еще нехорошо записывать отрицания разными символами.

Ну и
Lia в сообщении #942710 писал(а):
Приведите свои попытки решения или укажите затруднения.

 Профиль  
                  
 
 Re: Логика высказываний
Сообщение15.12.2014, 12:06 


08/12/14
3
Sonic86 в сообщении #946374 писал(а):
IvanEh в сообщении #942706 писал(а):
Можно использовать теоремы(10)
Что за теоремы?

IvanEh в сообщении #942706 писал(а):
Мне нужно решить конкретно такой пример:
$(\overline{C}\implies \overline{A \wedge B}) \implies (\overline{C} \implies \overline{A}) \vee (\overline{C} \implies \overline {B})$
У Вас в формуле присутствуют связки $\vee, \wedge$, в указанных аксиомах они отсутствуют. Чего-то не хватает: определений связок или аксиом.
Еще нехорошо записывать отрицания разными символами.

Ну и
Lia в сообщении #942710 писал(а):
Приведите свои попытки решения или укажите затруднения.


Все операции нужно заменить на импликацию. Я пробовал использовать теоремы и аксиомы, но я не могу уловить сути, когда что нужно использовать

 Профиль  
                  
 
 Re: Логика высказываний
Сообщение15.12.2014, 12:20 
Заслуженный участник


08/04/08
8417
IvanEh в сообщении #946720 писал(а):
Все операции нужно заменить на импликацию.
Тогда я могу в общем посоветовать только применять MP, пока это возможно, а дальше уже пытаться комбинировать посылки и аксиомы.

IvanEh в сообщении #946720 писал(а):
Я пробовал использовать теоремы и аксиомы, но я не могу уловить сути, когда что нужно использовать
К сожалению, тут трудно советовать, для меня это тоже в основном перебор и телепатия. Попробуйте сначала применить MP, потом надо смотреть. Без MP было бы еще сложнее.

 Профиль  
                  
 
 Re: Логика высказываний
Сообщение15.12.2014, 15:57 


07/03/11
662

(Оффтоп)

А зачем вообще нужны такие задания, какая от них польза?

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


08/04/08
8417

(Оффтоп)

vlad_light в сообщении #946835 писал(а):
А зачем вообще нужны такие задания, какая от них польза?
Применение аксиоматического метода в логике. Применение начинается с исчисления высказываний. Затем идет на исчисление предикатов. Про вторую теорему Геделя слыхали? Вот то-то и оно.

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


27/04/09
21649
Уфа
Вывод перестаёт быть магией, если выведены правила введения и удаления связок (например, для конъюнкции это$$\begin{array}{ccc} \dfrac{A,\;B}{A\wedge B} \; (\wedge^+), & \dfrac{A\wedge B}A \; (\wedge^-_1), & \dfrac{A\wedge B}B \; (\wedge^-_2). \end{array}$$В общих чертах стратегия доказательства с ними (и теоремой о дедукции) такая: применять правила удаления к подформулам гипотез (сначала теоремой о дедукции гипотез наделать, если нужно) и применять правила введения для получения подформул желаемого результата, и под конец склеить всё в одну формулу снова теоремой о дедукции.

Маленький и искуственный, но пример к методу: докажем коммутативность конъюнкции $A\wedge B\vdash B\wedge A$:
\begin{array}{rll} 
1. & A\wedge B & \text{(гипотеза)} \\ 
2. & A & \text{(}\wedge^-_1\text{, 1)} \\ 
3. & B & \text{(}\wedge^-_2\text{, 1)} \\ 
4. & B\wedge A & \text{(}\wedge^+\text{, 3, 2)} \\ 
\end{array}

Аксиомы Клини позволяют подобные правила выводить довольно легко. (Вы можете вывести эти аксиомы из своих, если захотите.) Например, $A,B\vdash A\wedge B$, что и рождает правило $\wedge^+$, показывается применением теоремы о дедукции к $\vdash A\to(B\to A\wedge B)$ (это аксиома 3): получим сначала $A\vdash B\to A\wedge B$, а потом и $A,B\vdash A\wedge B$. Выводимости $A\wedge B\vdash A$ и $A\wedge B\vdash B$ показываются однократным применением теоремы о дедукции к аксиомам 6, 7. И так практически с каждым правилом введения/удаления.

-- Пн дек 15, 2014 23:28:00 --

Кстати, можно заметить, что MP — это самое что ни на есть $\to^-$.

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

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



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

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


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

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