Установить общезначимость или необщезначимость формулы в т.K

[YgolovnicK]

Позвольте еще уточнить на счет самой формулы(в контексте высказывания): Первая скобка $\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))$ как ложное высказывание и связать его с первой частью высказывания, получив таким образом противоречие. Или я не так как то думаю? Немного не понял, как применить к своей формуле Ваше "колдовство" ибо если общезначимость вашего высказывания я вижу и понимаю, то истинность своего я никак не могу понять, т.е. нет же четкого разграничения, где истина, а где ложь, как в алгебре высказываний, все зависит от интерпретации. А как отвлечься от конкретной интерпретации, я не понимаю.

[Sonic86]

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)$, потом допилить рассуждения до уровня доказательства формулы в АП, а уже потом дописать рассуждение, связанные с общезначимостью.

(Оффтоп)

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

[YgolovnicK]

Доказать то, что формула $(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$.
Так?

[Sonic86]

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

[YgolovnicK]

Продолжая Ваши рассуждения:
Если $ 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$ Верно?

[Sonic86]

YgolovnicK в сообщении #737308 писал(а):

Верно?

Да.

YgolovnicK в сообщении #737308 писал(а):

на любых наборах $x$

А этот кусочек не нужен - о нем уже говорят кванторы.

[YgolovnicK]

Спасибо за помощь