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

[YgolovnicK]

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

Собственно, в логическую символику перевести просто:
$ (\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)

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

[Sonic86]

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

[YgolovnicK]

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

[Sonic86]

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

Хотя первая скобка может быть и такой: $(B \rightarrow A)$
Не уверен.

Именно такой.

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

Позвольте спросить, что такое функция истинности $ \lambda$?

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

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

Так же встает вопрос, можно ли просто заменить вышеупомянутую формулу с кванторами этой?

В решении нельзя будет. А вот вообще должно быть можно (но это, видимо, другой вопрос.)

[YgolovnicK]

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

[Sonic86]

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

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

Да (точнее, я Вам так предлагаю сделать. В принципе, Вы можете своим способом доказать). После доказательства соответствующей формулы в алгебре высказываний можно будет построить более сложное, но аналогичное предыдущему, доказательство в алгебре предикатов. Просто при доказательстве соответствующей формулы в алгебре предикатов Вы сосредоточитесь как бы на самом доказательстве, а в алгебре предикатов - на рассуждениях с общезначимостью.
Только в АВ доказывать формулу надо без таблиц истинности.
Доказать формулу $(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$ истина, $B$ истина, $A$ ложь, то получим конъюнкцию истинную, а последнюю скобку ложную, из чего последует ложная импликация.
А что теперь с этим делать для формулы с кванторами? Нам надо подобрать такую интерпретацию ,чтобы формула оказалась ложна?

[Sonic86]

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

$(B \to A) \& (C \to \neg A) \to (C \to \neg B)$
данная формула необщезначима, т.к. если положить $C$ истина, $B$ истина, $A$ ложь, то получим конъюнкцию истинную, а последнюю скобку ложную, из чего последует ложная импликация.

Неверно, при истинном $B$ и ложном $A$ импликация $B\to A$ ложна. Эта формула истинна (я ее не наугад подобрал)
Кроме того, у высказываний нет общезначимости - не определено для них такое понятие. Высказывания могут быть тавтологиями. Это высказывание - тавтология.

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

А что теперь с этим делать для формулы с кванторами? Нам надо подобрать такую интерпретацию ,чтобы формула оказалась ложна?

Приведенная формула общезначима, ее нужно доказывать.

[YgolovnicK]

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

[geoffrey]

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

[Sonic86]

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

Значит, формула с кванторами тоже истинна. А как это доказать? Подскажите, пожалуйста, не приходилось раньше доказывать.

Ну вот пример: докажем в АВ формулу $A\to (B\to A)$. Ясно, что $A$ либо истинно, либо ложно. Если $A$ ложно, то $A\to (B\to A)$ истинно, т.к. посылка ложна. Если же $A$ истинно, то $B\to A$ тоже истинно, потому вся формула $A\to (B\to A)$ истинна. (т.е. мы просто вносим логику в формулы)
Попробуйте доказать приведенную формулу из АВ аналогично.

[YgolovnicK]

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

[Sonic86]

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

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

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

[YgolovnicK]

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

[Sonic86]

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]$).

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

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

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