Доказать не-общезначимость формулы

[mruncles]

Добрый день, к сожалению мат логика даётся мне достаточно сложно, нет у кого спросить, даже у преподавателя. Есть задачка:
Доказать что формула первого порядка $\forall (P(x) \supset Q(x)) \supset (\forall P(x) \supset \forall Q(x)) $ - не является логически общезначимой.
я уже неделю провел над этой задачей и смог из себя вынести следующее:

"Для доказательства нам надо найти хотя бы одну интерпретацию, где формула ложна на некоторой последовательности значений свободных вхождений переменной x в P и Q. Тогда предположим, что приведённая формула ложна. Тогда $\forall (P(x) \supset Q(x)) $ – должно быть истинно, а $\forall P(x) \supset \forall Q(x)$ – ложно. Тогда $\forall P(x)$ – истинно, а $\forall Q(x)$ – ложно. Тогда P(x) На этой последовательности всегда истинно, а Q(x) может быть как ложным, так и истинным. Так как на части последовательности Q(x) может быть и истинным, то $P(x) \supset Q(x)$ (в левой части формулы)может обращаться в истину, что приводит к тому, что $\forall (P(x) \supset Q(x))$ – истина, на этой же части последовательности. В итоге $\forall (P(x) \supset Q(x)) \supset (\forall P(x) \supset \forall Q(x)) $ – может может быть ложно. Так как нет противоречия, то формула не является логически общезначимой."

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

Может кто-нибудь поможет!
Спасибо.

[iifat]

Хм. Формальную логику тоже знаю не очень, но как-то мне странно. $Q$ истинно на всех $x$, где истинно $P$; $P$ истинно везде. Из этого вполне, имхо, следует, что и $Q$ тоже. Пока вас не поместили в карантин за неиспользование $\TeX$, проверьте ещё раз задание.

[mruncles]

Исправил формулы, задание проверил. Мне моё доказательство перподаватель завернул, сказав что "..отсутствие противоречия не доказывает логической необщезначимости.." "..построить пример интерпретации, в которой формула не истинна.." - я и так без него понимаю что нужно в голове построить этот пример, но никак не могу этого сделать. Дайте хотя бы намек!
Спасибо.

[Sonic86]

А кванторы по предикатам и формулам - это нормально?
Видимо, имелось ввиду следующее:
$\forall x (P(x) \supset Q(x)) \supset (\forall x P(x) \supset \forall x Q(x)) $

mruncles в сообщении #797638 писал(а):

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

Ну вот у Вас получилось:

$$\left\{ \begin{array}{lll} \lambda (\forall x (P(x) \supset Q(x))) =1 \\ \lambda (\forall x (P(x))) =1 \\ \lambda (\forall x (Q(x))) =0 \end{array} $$

Ну попробуйте подобрать самую простую интерпретацию, в которой выполнялись бы 2-я и 3-я формулы.

mruncles в сообщении #797638 писал(а):

Q(x) может быть как ложным, так и истинным. Так как на части последовательности Q(x) может быть и истинным, то $P(x) \supset Q(x)$ (в левой части формулы)может обращаться в истину, что приводит к тому, что $\forall (P(x) \supset Q(x))$ – истина, на этой же части последовательности. В итоге $\forall (P(x) \supset Q(x)) \supset (\forall P(x) \supset \forall Q(x)) $ – может может быть ложно.

Вы не рассмотрели 2-й вариант значений $Q(x)$. Рассмотрите его.

[mruncles]

да, вы правы я тут потерял иксы.


Ну мне в голову приходит только:
$x \Rightarrow \mathbb{Z}
$P \Rightarrow x+x=2x$
$Q \Rightarrow x/x=1$
Вот выполняются вторая и треться формула на нуле, но первая то не выполняется.

Цитата:

Вы не рассмотрели 2-й вариант значений

На втором варианте там правая часть формулы будет истина, что делает всю формулу истина! Мне же надо найти интерпретацию где она ложна! например подобрать какие то числа и 2 операции над ними, которые приведут к ложности вышеописанную формулу.

[Sonic86]

mruncles в сообщении #797772 писал(а):

$P \Rightarrow x+x=2x$
$Q \Rightarrow x/x=1$

$P(x), Q(x)$ совершенно нет необходимости задавать какими-то конкретными арифметическими формулами, кроме того, для задания формул по определению надо использовать знак $\Leftrightarrow$. (писать $P$ вместо $P(x)$ некорректно).

mruncles в сообщении #797772 писал(а):

$x \Rightarrow \mathbb{Z}

Это нечто бессмысленное.
Еще подсказка: достаточно одноэлементного множества для интерпретации.

mruncles в сообщении #797772 писал(а):

На втором варианте там правая часть формулы будет истина, что делает всю формулу истина!

2-й вариант, это когда $Q(x)$ ложно для некоторых $x$, а Вы рассматриваете что-то другое.

[mruncles]

Я правильно понимаю, я должен подобрать такую интерпретацию, чтобы выполнилось одновременно $ Q(x) =1 $ и $\forall x Q(x) = 0$?
Потому что $ P(x) $ и $\forall x P(x)$ у нас должны быть истиной, чтобы вся формула стала ложной.
Просто, если так то такое вообще возможно?

[Sonic86]

mruncles в сообщении #797804 писал(а):

Я правильно понимаю, я должен подобрать такую интерпретацию, чтобы выполнилось одновременно $ Q(x) =1 $ и $\forall x Q(x) = 0$?
Потому что $ P(x) $ и $\forall x P(x)$ у нас должны быть истиной, чтобы вся формула стала ложной.
Просто, если так то такое вообще возможно?

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

[mruncles]

Так как раз преподаватель требует от меня доказать, что она НЕобщезначима, и как я уже писал(мой второй пост в ветке), требует от меня именно пример интерпретации.

[AGu]

mruncles в сообщении #797818 писал(а):

Так как раз преподаватель требует от меня доказать, что она НЕобщезначима.

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

[nikvic]

AGu в сообщении #797821 писал(а):

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

У меня тоже ощущение, что ф-ла "верна". Посылка импликации - принадлежность первого множества второму. Посылка заключения - совпадение первого множества и универсума.

[mruncles]

Цитата:

В задаче ваши рассуждения правильны, но отсутствие противоречия не доказывает логической необщезначимости. Вы показываете, что она возможна, но нужно реализовать эту возможность. Поэтому надо построить пример интерпретации, в которой формула не истинна. Переменная x является связанной в формуле, поэтому надо говорить о последовательностях значений свободных вхождений других переменных формулы (если они есть).

Полный ответ от преподавателя. Формулу перепроверил уже 100 раз. И как видно почему то преподу она кажется необщезначимой.

PS:Ещё в догонку, если ли книги по мат логике где русским языком объясняют такие понятия как терм, квантор, связанность переменной в формуле, свободные вхождения. Потому что у меня складывается ощущения, что я, читая его лекции, вообще ничего уже не понимаю. К сожалению, образование дистанционное.

Игошина и Мандельсона не предлагать, ибо там ничего не понятно.

[Sonic86]

mruncles в сообщении #797838 писал(а):

Игошина и Мандельсона не предлагать, ибо там ничего не понятно.

Ну я не знаю тогда, в Игошине все подробно разжевано для студентов. Ну попробуйте Новикова тогда.

mruncles в сообщении #797818 писал(а):

Так как раз преподаватель требует от меня доказать, что она НЕобщезначима, и как я уже писал

Поспорьте с ним на 100 баксов, что он не сможет предъявить такую интерпретацию
Серьезно: формула общезначима, доказательство фактически выписано.

mruncles в сообщении #797838 писал(а):

И как видно почему то преподу она кажется необщезначимой.

Вы преподу доверяете или доказательствам?