fixfix
2014 dxdy logo

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

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


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


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

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

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

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

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



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


13/01/13
30
Позвольте еще уточнить на счет самой формулы(в контексте высказывания): Первая скобка $\neg \exists x (\neg P_1^1 (x) \rightarrow P_3^1 (x)) \& \forall x (P_2^1 (x))$ гласит о том, что не существует такого $x$, который бы не был птицей, но обладал перьями. Т.е. все те, кто обладают перьями являются птицами, о чем говорит предложенная Вами формулировка первой скобки. Я не понял, в чем разница между ними и какая из них все-таки верна. :-)
А про само доказательство, то у меня возникают некоторые трудности с пониманием самого доказательства. Ведь чтобы доказать, надо рассмотреть и опровергнуть те случаи, которые обращают формулу в 0.
Импликация ложна только в том случае, если посылка истина, а следствие ложно. И тогда нам нужно рассмотреть $\forall x (P_2^1 (x) \rightarrow \neg P_3^1 (x))$ как ложное высказывание и связать его с первой частью высказывания, получив таким образом противоречие. Или я не так как то думаю? Немного не понял, как применить к своей формуле Ваше "колдовство" :-) ибо если общезначимость вашего высказывания я вижу и понимаю, то истинность своего я никак не могу понять, т.е. нет же четкого разграничения, где истина, а где ложь, как в алгебре высказываний, все зависит от интерпретации. А как отвлечься от конкретной интерпретации, я не понимаю.

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


08/04/08
8562
YgolovnicK в сообщении #737252 писал(а):
Позвольте еще уточнить на счет самой формулы(в контексте высказывания): Первая скобка $\neg \exists x (\neg P_1^1 (x) \rightarrow P_3^1 (x)) \& \forall x (P_2^1 (x))$ гласит о том, что не существует такого $x$, который бы не был птицей, но обладал перьями. Т.е. все те, кто обладают перьями являются птицами, о чем говорит предложенная Вами формулировка первой скобки. Я не понял, в чем разница между ними и какая из них все-таки верна. :-)
Исходная формулировка такая:
YgolovnicK в сообщении #737060 писал(а):
"Перья есть только у птиц. Ни один студент не является птицей. Значит, все студенты лишены перьев".

Собственно, в логическую символику перевести просто:
$\neg \exists x (\neg P_1^1 (x) \rightarrow P_3^1 (x))$ где
$P_1^1 (x)$ - быть птицей
$P_3^1 (x)$ - иметь перья
Если отрицание внести, то получим эквивалентную формулу $\forall x(\neg P_1(x)\&\neg P_3(x))$. Убирая квантор, получим конъюнкцию, в то время как ясно, что утверждение имеет вид "для силлогизма", т.е. $\forall x (P(x)\to Q(x))$. Но конъюнкция и импликация неэквивалентны.
(можно разобрать обе формулы, найти, где какая истинна, где какая ложна - в том и будет отличие, но писать лень. Вообще, интуитивно ясно, что исходное рассуждение верно. Потому его формализация должна быть верна, а у Вас получается не так.)

YgolovnicK в сообщении #737252 писал(а):
А про само доказательство, то у меня возникают некоторые трудности с пониманием самого доказательства. Ведь чтобы доказать, надо рассмотреть и опровергнуть те случаи, которые обращают формулу в 0.
Так можно сделать, но необходимости делать именно так нет.

YgolovnicK в сообщении #737252 писал(а):
Импликация ложна только в том случае, если посылка истина, а следствие ложно. И тогда нам нужно рассмотреть $\forall x (P_2^1 (x) \rightarrow \neg P_3^1 (x))$ как ложное высказывание и связать его с первой частью высказывания, получив таким образом противоречие. Или я не так как то думаю?
Мне кажется, что Вы хотите исходную формулу опровергать. Все же лучше ее поправить (ибо расхождение между человеческой логикой и формальной нежелательно) и доказать.

YgolovnicK в сообщении #737252 писал(а):
Немного не понял, как применить к своей формуле Ваше "колдовство" :-) ибо если общезначимость вашего высказывания я вижу и понимаю, то истинность своего я никак не могу понять, т.е. нет же четкого разграничения, где истина, а где ложь, как в алгебре высказываний, все зависит от интерпретации. А как отвлечься от конкретной интерпретации, я не понимаю.
Я там выше неправильно термин употребил, спутал истинность с общезначимостью. Истинность формулы алгебры предикатов действительно задается вместе с ее интерпретацией. Но общезначимость (тавтологичность) формулы - это истинность формулы во всех моделях - уже от интерпретации не зависит. И для доказательства общезначимости формула в АП в самом простом случае применяется сведЕние к истинности формулы в АВ для любой модели, например, как в примере с $\forall x(P(x)\to P(x))$.
(хотел примеры написать, но лень)

Сами "заклинания" об общезначимости Вы сначала можете просто переписать по аналогии - это момент содержательный, но никаких преобразований с его помощью Вы как бы не делаете - "заклинания" всегда будут те же. Именно поэтому я Вам все же предлагаю сначала в АВ доказать формулу $(B \to A) \& (C \to \neg A) \to (C \to \neg B)$, потом допилить рассуждения до уровня доказательства формулы в АП, а уже потом дописать рассуждение, связанные с общезначимостью.

(Оффтоп)

ужас, зачем я так многабукав написал... Как бы все просто, ну буковок почему-то всегда много.

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


13/01/13
30
Доказать то, что формула $(B \to A) \& (C \to \neg A) \to (C \to \neg B)$ является тавтологией не составит труда: импликация ложна лишь при истинной посылке и ложном следствии, соответственно берем $(C \to \neg B)$, выражение является ложью, когда $C$ истина и $B$ истина, при таком раскладе $A$ может принимать значения истина и ложь, и в обоих случаях конъюнкция будет ложна, т.к. одна из скобок будет ложна. Получили противоречие, соответственно формула $(B \to A) \& (C \to \neg A) \to (C \to \neg B)$ является тавтологией. Значит высказывание $ (\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)) истинно на любых наборах $x$.
Так?

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


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

YgolovnicK в сообщении #737283 писал(а):
Значит высказывание $ (\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)) истинно на любых наборах $x$.
Не значит. (это доказательство не опирается на предыдущее, оно ему просто аналогично (хотя может его и можно опереть, но для этого, видимо, нужна какая-то теорема, а я такой не знаю)). Просто сделайте аналогично. Тоже от противного:
Пусть $(\forall x(P_3(x)\to P_1(x)) \& \forall x (P_2 (x) \to \neg P_1 (x))) \to \forall x (P_2 (x) \to \neg P_3 (x))$ ложно.
Тогда $\forall x(P_3(x)\to P_1(x)), \forall x (P_2 (x) \to \neg P_1 (x))$ истинны, а $\forall x (P_2 (x) \to \neg P_3 (x))$ ложно.
$\forall x (P_2 (x) \to \neg P_3 (x))$ ложно, значит существует $t: P_2 (t) \to \neg P_3 (t)$ ложно.
Дальше сами.

-- Вс июн 16, 2013 11:37:03 --

upd: и я опять Вас немного путаю: здесь надо писать не "истинно"/"ложно", а "общезначимо"/"необщезначимо", а перед всем этим - такой кусок текста про общезначимость с переходом к предикатом произвольной модели. Считайте, что текст выше - упрощенная схема доказательства.

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


13/01/13
30
Продолжая Ваши рассуждения:
Если $ P_2 (t) \to \neg P_3 (t)$ ложно, то $ P_2(t) , P_3 (t)$ истины, а при таком раскладе $P_1$ может принимать истину или ложь, однако при любых его значениях одна из формул $\forall x(P_3(x)\to P_1(x)), \forall x (P_2 (x) \to \neg P_1 (x))$ окажется невыполнимой (на всех значениях будет принимать значение ложь), пришли к противоречию. Значит формула $ \forall x(P_3(x)\to P_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))$ истина на любых наборах $x$ Верно?

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


08/04/08
8562
YgolovnicK в сообщении #737308 писал(а):
Верно?
Да.
YgolovnicK в сообщении #737308 писал(а):
на любых наборах $x$
А этот кусочек не нужен - о нем уже говорят кванторы.

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


13/01/13
30
Спасибо за помощь :D

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

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



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

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


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

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