Формализация выражения (логика предикатов)

[RealnoDeb]

Всем привет!

Необходимо формализовать на языке логики предикатов высказывание:

Цитата:

Каждый итальянский город старше хотя бы одного немецкого города.

Использую следующие нелогические символы:

P(x) — «x является итальянским»;
Q(x) — «x является немецким»;
R(x) — «x является городом»;
S(x,y) — «x старше y».

Моя первоначальная формула:

\forall x\exists y\bigl((R(x)\land P(x)\land R(y)\land Q(y))\supset S(x,y)\bigr).

Насколько я понимаю, она неправильна, а исходному высказыванию соответствует формула:

\forall x\bigl((R(x)\land P(x))\supset\exists y(R(y)\land Q(y)\land S(x,y))\bigr).

Я понимаю следующее возражение против первой формулы: для каждого x можно выбрать такой y, который не является немецким городом. Тогда антецедент импликации будет ложным, а сама импликация - истинной независимо от значения S(x,y).

Однако мне непонятно, почему это делает первую формулу неправильной, тогда как во второй формуле при выборе в качестве x объекта, который не является итальянским городом, антецедент также будет ложным, а импликация - истинной.

В чем состоит принципиальная разница между этими двумя случаями?

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

\forall x(A(x)\supset\ldots),

а ограничение при кванторе существования - посредством конъюнкции:

\exists y(B(y)\land\ldots)?

но в моем учебнике вообще про это ничего нет и такое объяснение я не понимаю.

Был бы благодарен за помощь!

[epros]

RealnoDeb в сообщении #1729842 писал(а):

но в моем учебнике вообще про это ничего нет и такое объяснение я не понимаю

А что тут можно понять? Это, вроде, просто соглашение о смысле слов.

[mihaild]

RealnoDeb в сообщении #1729842 писал(а):

Однако мне непонятно, почему это делает первую формулу неправильной, тогда как во второй формуле при выборе в качестве x объекта, который не является итальянским городом, антецедент также будет ложным, а импликация - истинной.

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

[epros]

mihaild в сообщении #1729856 писал(а):

Потому что для первой формулы есть модель, в которой она выполнена, а исходное утверждение - нет

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

[RealnoDeb]

mihaild в сообщении #1729856 писал(а):

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

Вот этого объяснения я и не понимаю, потому что из него как будто бы следует, что для второй формулы такой модели нет.

Но опять же: берем во второй формуле вместо $x$ - неитальянский город, но остальные параметры интерпретируем корректно, и так же получаем истину, хотя, опять же, одно из условий исходного высказывания ($x$ должен быть итальянским гороом) не соблюдено. Из этого, по моим представлениям, следует, что наличие модели, в которой формула принимает значение "истина", несмотря на несоответствие исходному высказыванию, не говорит о том, что формула некорректна.

[mihaild]

RealnoDeb в сообщении #1729869 писал(а):

Но опять же: берем во второй формуле вместо $x$ - неитальянский город, но остальные параметры интерпретируем корректно, и так же получаем истину, хотя, опять же, одно из условий исходного высказывания ($x$ должен быть итальянским гороом) не соблюдено.

Не соблюдена посылка исходного высказывания. Всё высказывание целиком верно.

[warlock66613]

RealnoDeb, модель -- это не конкретные значения для $x$ или других переменных. Модель -- это воображаемый мир с указанием какие в нём есть города, итальянские, немецкие и другие, какой у каждого города возраст, есть ли в мире ещё что-то кроме городов. Для каждой модели можно определить истинно ли высказывание. Например, возьмём модель -- мир, где нет городов вообще. В таком мире исходное высказывание истинно. А вот в мире, где есть только один итальянский город, а немецких нет вообще, исходное высказывание неверно. Вам надо придумать такой мир, что исходное высказывание истинно, а ваша формула -- нет. Это докажет что формализация неверна.

[epros]

RealnoDeb, просто поймите, что на человеческий язык Ваша первая формула переводится так: Каждый итальянский город старше чего-нибудь или существует что-то, не являющееся немецким городом.

[RealnoDeb]

Окей… Видимо, у меня есть какой-то фундаментальный пробел, который мне не помогает понять Ваши объяснения.

Попробую объяснить свое непонимание следующим образом. Сразу оговорюсь, что мой уровень знаний математики где-то на уровне семиклассника (не ирония), но мне удобно представлять формулу в виде функции.

Итак, берем мою формулу:

\forall x\exists y\bigl((R(x)\land P(x)\land R(y)\land Q(y))\supset S(x,y)\bigr).

Область определения функции: всевозможные объекты (универсум).

Цитата:

1) При помощи предикаторов $R$, $P$, $Q$ я говорю функции: пройдись по всем объектам универсума и верни только те, которые соответствуют условиям, заданным предикаторами, то есть: для $x$ – верни только итальянские города, а для $y$ – только немецкие города.

Результат: сформирован антецедент, в котором есть только итальянские города и только немецкие.

2) Далее начинаем формировать консеквент: при помощи двухместного предикатора $S$:
2.1) так как $S$ предикатор двухместный, функция берет все возможные значения $x$ и $y$ из антецендента, и составляет все возможные значения пар $(x, y)$, то есть, по сути, производим декартово произведение всех итальянских и немецких городов.

Результат: все возможные комбинации, где $x$ – итальянский город, $y$ – немецкий город.

2.2) так как предикатор $S$ выражает некоторое отношение, функция оставляет только те пары, которые удовлетворяют условию: $x$ старше $y$.

4) И наконец: при помощи кванторов я говорю функции: проверь, чтобы в оставшихся парах множество $x$ = множеству всех итальянских городов, а во множестве $y$ был бы хотя бы один элемент.

То есть ($x$ = множество итальянских городов) $\land$ (множество $y$ - не пустое).

Результат: либо истина, либо ложь.

На каком моменте логика ломается?

[warlock66613]

RealnoDeb, обратите внимание, что ваша формула не требует чтобы $y$ был немецким городом.

[RealnoDeb]

warlock66613 в сообщении #1729889 писал(а):

RealnoDeb, обратите внимание, что ваша формула не требует чтобы $y$ был немецким городом.

Почему не требует? Я через предикаторные константы $Q$ и $R$ определил, что рассматриваются только $y$, которые являются немецкими городами.

Я понимаю, что моя формула, в конечном итоге, примет значение "истина", даже если вместо $y$ подставить ненемецкий город, но я не понимаю, почему именно мою формулу это делает некорректной, а правильную формулу не делает, хотя, если у нее вместо $x$ подставить неитальянский, то она тоже примет значение "истина".

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

[epros]

RealnoDeb в сообщении #1729881 писал(а):

На каком моменте логика ломается?

На первом. Пройтись нужно не только по итальянским и немецким городам, а по всем парам объектов предметной области. И Вы должны сразу увидеть, что среди этих пар обязательно существует такая, в которой $y$ не является немецким городом, а значит антецедент импликации ложен, а значит импликация истинна.

[mihaild]

RealnoDeb в сообщении #1729881 писал(а):

На каком моменте логика ломается?

В тот момент, когда вы отфильтровали пары, на которых антецедент неверен.
И еще раз, когда в разговоре о консеквенте откуда-то возникла география.

Правильный способ чтения этой формулы в этом стиле такой:
1. Антецедент верен на понятно каких парах $(x, y)$.
2. Консеквент верен тоже понятно на каких парах $(x, y)$.
3. Вся импликация верна на парах, на которых либо верен консеквент, либо неверен антецедент (либо и то, и другое). В частности, она верна на всех парах $(x, y)$, где $x$ - не итальянский город.
4. Осталось проверить, что для каждого $x$ найдётся такой $y$, что либо антецедент на них неверен (например, если $y$ не немецкий город), либо консеквент верен.

[epros]

RealnoDeb в сообщении #1729892 писал(а):

итог один: для обоих формул можно найти интерпретации их переменных, которые не соответсвуют исходному высказыванию

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

[warlock66613]

RealnoDeb в сообщении #1729892 писал(а):

хотя, если у нее вместо $x$ подставить не итальянский, то она тоже примет значение "истина"

Дело совсем не в том, какое значение она примет. Исходное высказывание ничего не говорит о неитальянских городах. И формула (правильная) тоже ничего не говорит: хотя $x$ и пробегает не только итальянские города, для неитальянских городов формула не утверждает ничего (проверьте, например, переведите формулу обратно на русский). А вот ваша формула уже кое-что утверждает, но это не главная её проблема.