2014 dxdy logo

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

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


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


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

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

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

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

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



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Установить общезначимость или необщезначимость формулы в т.K
Сообщение15.06.2013, 20:07 


13/01/13
30
Доброго времени суток. Прошу помощи с решением следующей задачи:
Перевести в логическую символику и установить общезначимость или необщезначимость полученной формулы:
"Перья есть только у птиц. Ни один студент не является птицей. Значит, все студенты лишены перьев".

Собственно, в логическую символику перевести просто:
$ (\neg \exists x (\neg P_1^1 (x) \rightarrow P_3^1 (x)) \& \forall x (P_2^1 (x) \rightarrow \neg P_1^1 (x))) \rightarrow \forall x (P_2^1 (x) \rightarrow \neg P_3^1 (x)), где
$P_1^1 (x)$ - быть птицей
$P_2^1 (x)$ - быть студентом
$P_3^1 (x)$ - иметь перья
Формула задана в теории первого порядка (теории K)

Но с доказательством общезначимости или необщезначимости беда - я не нашел в учебниках способа к доказательству общезначимости формул с кванторами.
Буду благодарен, если разъясните, как нужно правильно доказывать (не)общезначимость формул с кванторами.

 Профиль  
                  
 
 Re: Установить общезначимость или необщезначимость формулы в т.K
Сообщение15.06.2013, 20:40 
Заслуженный участник


08/04/08
8556
YgolovnicK в сообщении #737060 писал(а):
"Перья есть только у птиц.
$(\neg \exists x (\neg P_1^1 (x) \rightarrow P_3^1 (x))$
А я бы так написал:
$\forall x(P_3(x)\to P_1(x))$. И эти формулы неравносильны.

YgolovnicK в сообщении #737060 писал(а):
Формула задана в теории первого порядка (теории K)

Но с доказательством общезначимости или необщезначимости беда - я не нашел в учебниках способа к доказательству общезначимости формул с кванторами.
Похоже, что у Вас еще не исчисление предикатов. Значит можно пользоваться функцией истинности $\lambda$. В таком случае можно сначала попытаться составить аналогичную формулу в алгебре высказываний, доказать ее там тоже через $\lambda$, а потом по аналогии доказать общезначимость формулы.

 Профиль  
                  
 
 Re: Установить общезначимость или необщезначимость формулы в т.K
Сообщение15.06.2013, 21:44 


13/01/13
30
Формула в алгебре высказываний:
$(A \rightarrow B) \& (C \rightarrow \neg A) \rightarrow (C \rightarrow \neg B)$, где
$A$ - птица
$B$ - с перьями
$C$ - студент
Хотя первая скобка может быть и такой: $(B \rightarrow A)$
Не уверен.
Если без кванторов, то через таблицы истинности доказать вполне легко.
Позвольте спросить, что такое функция истинности $ \lambda$?
Так же встает вопрос, можно ли просто заменить вышеупомянутую формулу с кванторами этой? Ибо если заменить, то никак не будут описаны слова "ни один" и "все".

 Профиль  
                  
 
 Re: Установить общезначимость или необщезначимость формулы в т.K
Сообщение15.06.2013, 21:59 
Заслуженный участник


08/04/08
8556
YgolovnicK в сообщении #737083 писал(а):
Хотя первая скобка может быть и такой: $(B \rightarrow A)$
Не уверен.
Именно такой.

YgolovnicK в сообщении #737083 писал(а):
Позвольте спросить, что такое функция истинности $ \lambda$?
Если высказывание $A$ истинно, то $\lambda (A)=1$, иначе $\lambda (A)=0$ (хотя м.б. можно и без нее - просто писать доказательство словами). В качестве высказываний можно брать значения предикатов $P(a)$ для явно заданного терма $a$, а также замкнутые формулы типа $\exists x P(x)$.

YgolovnicK в сообщении #737083 писал(а):
Так же встает вопрос, можно ли просто заменить вышеупомянутую формулу с кванторами этой?
В решении нельзя будет. А вот вообще должно быть можно :roll: (но это, видимо, другой вопрос.)

 Профиль  
                  
 
 Re: Установить общезначимость или необщезначимость формулы в т.K
Сообщение15.06.2013, 23:43 


13/01/13
30
Я так ничего и не понял=)
Мне нужно доказать (не)общезначимость формулы в алгебре высказываний? И после что делать?

 Профиль  
                  
 
 Re: Установить общезначимость или необщезначимость формулы в т.K
Сообщение16.06.2013, 07:36 
Заслуженный участник


08/04/08
8556
YgolovnicK в сообщении #737139 писал(а):
Я так ничего и не понял=)
Мне нужно доказать (не)общезначимость формулы в алгебре высказываний? И после что делать?
Да (точнее, я Вам так предлагаю сделать. В принципе, Вы можете своим способом доказать). После доказательства соответствующей формулы в алгебре высказываний можно будет построить более сложное, но аналогичное предыдущему, доказательство в алгебре предикатов. Просто при доказательстве соответствующей формулы в алгебре предикатов Вы сосредоточитесь как бы на самом доказательстве, а в алгебре предикатов - на рассуждениях с общезначимостью.
Только в АВ доказывать формулу надо без таблиц истинности.
Доказать формулу $(B \to A) \& (C \to \neg A) \to (C \to \neg B)$ получилось?

 Профиль  
                  
 
 Re: Установить общезначимость или необщезначимость формулы в т.K
Сообщение16.06.2013, 09:25 


13/01/13
30
$(B \to A) \& (C \to \neg A) \to (C \to \neg B)$
данная формула необщезначима, т.к. если положить $C$ истина, $B$ истина, $A$ ложь, то получим конъюнкцию истинную, а последнюю скобку ложную, из чего последует ложная импликация.
А что теперь с этим делать для формулы с кванторами? Нам надо подобрать такую интерпретацию ,чтобы формула оказалась ложна?

 Профиль  
                  
 
 Re: Установить общезначимость или необщезначимость формулы в т.K
Сообщение16.06.2013, 09:51 
Заслуженный участник


08/04/08
8556
YgolovnicK в сообщении #737187 писал(а):
$(B \to A) \& (C \to \neg A) \to (C \to \neg B)$
данная формула необщезначима, т.к. если положить $C$ истина, $B$ истина, $A$ ложь, то получим конъюнкцию истинную, а последнюю скобку ложную, из чего последует ложная импликация.
Неверно, при истинном $B$ и ложном $A$ импликация $B\to A$ ложна. Эта формула истинна (я ее не наугад подобрал)
Кроме того, у высказываний нет общезначимости - не определено для них такое понятие. Высказывания могут быть тавтологиями. Это высказывание - тавтология.

YgolovnicK в сообщении #737187 писал(а):
А что теперь с этим делать для формулы с кванторами? Нам надо подобрать такую интерпретацию ,чтобы формула оказалась ложна?
Приведенная формула общезначима, ее нужно доказывать.

 Профиль  
                  
 
 Re: Установить общезначимость или необщезначимость формулы в т.K
Сообщение16.06.2013, 10:04 


13/01/13
30
Да, тавтология, верно. Ошибся, когда составлял истинностную таблицу для поиска ложных значений.
Значит, формула с кванторами тоже истинна. А как это доказать? Подскажите, пожалуйста, не приходилось раньше доказывать.

 Профиль  
                  
 
 Re: Установить общезначимость или необщезначимость формулы в т.K
Сообщение16.06.2013, 10:10 


09/10/11
29
YgolovnicK
метод аналитических таблиц, метод модельных множеств.

 Профиль  
                  
 
 Re: Установить общезначимость или необщезначимость формулы в т.K
Сообщение16.06.2013, 10:21 
Заслуженный участник


08/04/08
8556
YgolovnicK в сообщении #737200 писал(а):
Значит, формула с кванторами тоже истинна. А как это доказать? Подскажите, пожалуйста, не приходилось раньше доказывать.
Ну вот пример: докажем в АВ формулу $A\to (B\to A)$. Ясно, что $A$ либо истинно, либо ложно. Если $A$ ложно, то $A\to (B\to A)$ истинно, т.к. посылка ложна. Если же $A$ истинно, то $B\to A$ тоже истинно, потому вся формула $A\to (B\to A)$ истинна. (т.е. мы просто вносим логику в формулы)
Попробуйте доказать приведенную формулу из АВ аналогично.

 Профиль  
                  
 
 Re: Установить общезначимость или необщезначимость формулы в т.K
Сообщение16.06.2013, 10:53 


13/01/13
30
Sonic86
Формулы в теории высказываний я могу доказать, что она является (не)тавтологией. Проблема у меня возникает с формулами, содержащими кванторы. Как доказать, что формула в теории первого порядка общезначима? Если не общезначима, то необходимо лишь подобрать интерпретацию, при которой формула будет ложна. А вот если она общезначима, то я не знаю, как надо доказать, таблицу истинности не построить.
geoffrey
попробую поискать описания данных методов на просторах сети. О результате напишу позже.

 Профиль  
                  
 
 Re: Установить общезначимость или необщезначимость формулы в т.K
Сообщение16.06.2013, 11:07 
Заслуженный участник


08/04/08
8556
YgolovnicK в сообщении #737213 писал(а):
Проблема у меня возникает с формулами, содержащими кванторы. Как доказать, что формула в теории первого порядка общезначима? ... А вот если она общезначима, то я не знаю, как надо доказать, таблицу истинности не построить.
Ну примерно так же, как я выше показал: я же не использовал таблиц истинности.
Можете доказать, что в АП формула $\forall x(P(x)\to P(x))$ общезначима? А можете доказать, что $\neg \exists x (P(x)) \to \forall x(\neg P(x))$ общезначима? Какой смысл у высказывания $\forall x P(x)$?

 Профиль  
                  
 
 Re: Установить общезначимость или необщезначимость формулы в т.K
Сообщение16.06.2013, 11:28 


13/01/13
30
Вот с этим то и возникает проблема. Что нужно сказать, чтобы показать, что формула $\forall x(P(x)\to P(x))$ общезначима? Я помню, есть правило, которое позволяет нам утверждать истинность данной импликации, но просто словами я не знаю, как показать, что эта формула общезначима. Смысл высказывания $\forall x(P(x))$ - для любого х из множества допустимых значений (или из рассматриваемого множества) предикат P(x) принимает значение истина. Как доказать вторую формулу из Вами написанных не имею представления, т.е. я понимаю, что она истинная, понимаю смысл, что если не существует $x$, для которого бы предикат $P(x)$ принимал значение истина, то для всех $x$ он будет принимать значение ложь. Но именно показать, что это так, я не могу.

 Профиль  
                  
 
 Re: Установить общезначимость или необщезначимость формулы в т.K
Сообщение16.06.2013, 11:52 
Заслуженный участник


08/04/08
8556
YgolovnicK в сообщении #737231 писал(а):
т.е. я понимаю, что она истинная, понимаю смысл, что если не существует $x$, для которого бы предикат $P(x)$ принимал значение истина, то для всех $x$ он будет принимать значение ложь.
Вот примерно это и нужно в качестве доказательства написать, возможно, лишь чуть более формально + нужно добавить "заклинания", связанные с общезначимостью.
На примере формулы $\forall x(P(x)\to P(x))$ это выглядит примерно так:

Пусть $\forall x(A(x)\to A(x))$ истинна (здесь $A$ - некоторый конкретный предикат). Это равносильно тому, что для любого $x$ высказывание $P(x)\to P(x)$ истинно. Но высказывание $A(x)\to A(x)$ действительно всегда истинно (если посылка ложна, то импликация истинна, а если посылка истинна, то вывод истинен, значит и импликация тоже истинна). Значит формула $\forall x(A(x)\to A(x))$ истинна.
Т.е. я ничего не сделал, я просто квантор $\forall x$ превратил в текст на русском и дальше рассуждал согласно его смысла, но в итоге проблема свелась к алгебре высказываний.

Здесь пропущены "заклинания", связанные с общезначимостью. Для их добавления нужно только воспользоваться определением общезначимости:

Докажем, что формула $\forall x(P(x)\to P(x))$ общезначима.
Формула $\forall x(P(x)\to P(x))$ общезначима тогда и только тогда, когда в любой модели $M$ для любой интерпретации $x$ как предметной переменной, а $P$ - как некоторого предиката, соответствующая формула будет $\forall y(A(y)\to A(y))$ будет истинна на $M$ (здесь $y$ - интерпретация $x$, $A$ - интерпретация $P$. Например, $M$ - натуральные числа $y$ - натуральное число, $A(y)=[y\text{ делится на }2]$).

И все, дальше идут рассуждения, подобные написанным выше. Чисто синтаксически здесь переход к модели выглядит как замена буковок, т.е. затруднений здесь нет, одни только буковки. (а вот если бы требовалось опровержение, вот тогда надо было бы конкретную модель подбирать, конкретное значение переменной и конкретный предикат)

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

(если что - это все есть в книге Игошина по матлогике, которая есть в интернетах)

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

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



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

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


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

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