Математическая логика

[Коляныч]

Здравствуйте!

Подскажите, пожалуйста, как можно решить следующие задачи:

0. Докажите, что если предикат $P$ выразим через предикат $x < y$ на множестве $\mathbb Q$, то он выразим через $x < y$ и на множестве $\mathbb Q$ \ {0}.

1. Докажите, что предикат "$x$ и $y$ - родные братья" невыразим через предикаты "$x$ является мужчиной" и "$x$ есть родитель $y$".

2. Являются ли
a) $R$ и $R^2$;
b) $R^2$ и $R^3$;
c) $R^{n-1}$ и $R^n$;
элементарно эквивалентными как частично упорядоченные множества? Порядок в $R^2$ задается так: $(x_1, y_1) \le (x_2, y_2)$, если $x_1 \le x_2$ и $y_1 \le y_2$, таким образом не

любые два элемента сравнимы. В $R^n$ аналогично. В сигнатуру включены символы $\le$,$ =$.)

3. Доказать, что следующие формулы истинны во всякой конечной модели, но не тождественно истинны:
a) $\exists x \forall y \exists z((P(y; z) \to P(x; z)) \to (P(x; x) \to P(y; x)))$;
b) $\forall x_1 \forall x_2 \forall x_3 (P(x_1; x_1) \wedge (P(x1; x3) \to (P(x_1; x_2) \vee P(x2; x3))))$.

Тут есть указание: Удобнее доказывать невыполнимость отрицаний этих формул в конечных моделях и выполнимость в бесконечных.

У меня проблема заключается в том, что прочитав теорию по книге мне трудно решать такие задачи. Просто, примеров простых почти нет, а эти задачи для меня сложны. Помогите, пожалуйста.
Заранее ОГРОМНОЕ спасибо!

[Jnrty]

Jnrty:

Коляныч, Вам даётся некоторое время на исправление записи формул в соответствии с правилами форума, с которыми можно ознакомиться здесь: "Первые шаги в наборе формул" и "Краткий ФАК по тегу [mаth].". Для исправления сообщений служит кнопка .

Если не исправите, отправлю тему в "Карантин" до исправления.

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

[Коляныч]

Формулы исправил.

По поводу попыток решения: дело в том, что я даже не знаю как браться за такие задачи, так как легких примеров нет. Я буду очень благодарен даже за идеи и способы решения, за любые подходы.

Заранее спасибо

[Jnrty]

Jnrty:

Коляныч в сообщении #167468 писал(а):

Формулы исправил.

Исправили, но не до конца. Кванторы "существует" и "для любого" кодируются \exists и \forall: $\exists$ и $\forall$.

Исправьте и подождите, может быть, кто-нибудь подскажет.

[Коляныч]

Ну теперь уж точно все исправил:)

[gefest_md]

Коляныч писал(а):

3. Доказать, что следующие формулы истинны во всякой конечной модели, но не тождественно истинны:
a) $\exists x \forall y \exists z((P(y; z) \to P(x; z)) \to (P(x; x) \to P(y; x)))$;
b) $\forall x_1 \forall x_2 \forall x_3 (P(x_1; x_1) \wedge (P(x1; x3) \to (P(x_1; x_2) \vee P(x2; x3))))$.

Тут есть указание: Удобнее доказывать невыполнимость отрицаний этих формул в конечных моделях и выполнимость в бесконечных.

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

Станет понятнее как решать задачу если овладеть определениями (три). Вот отрывки из учебника Новикова.

Цитата:

Если формула истинна для некоторой области $\mathfrak{M}$ и некоторых предикатов, на ней определённых, мы будем называть её выполнимой

Пример: формула $P(x,y)\,\&\,P(y,z)\to P(x,z)$ выполнима на области $\mathfrak{M}=\mathbb{N}$ потому что она истинна на этой области для предиката "$x$ меньше $y$" ($x<y$): $x<y\,\&\,y<z\to x<z$. (но она не истинна на этой области для всех предикатов на ней определенных, в смысле следущего определения, второго: например конкретный предикат "$y$ следует непосредственно за $x$" имеет смысл на $\mathbb{N}$. Новиков обозначает его так $\sigma(x,y)$. Но формула $\sigma(x,y)\,\&\,\sigma(y,z)\to\sigma(x,z)$ не тождественно истина на $\mathbb{N}$) По этому формула $P(x,y)\,\&\,P(y,z)\to P(x,z)$ просто выполнима.

Цитата:

Если формула истинна для данной области $\mathfrak{M}$ и для всех предикатов определённых на $\mathfrak{M}$, мы будем называть её тождественно истинной для области $\mathfrak{M}$.

Примеры: Пусть $\mathfrak{M}=\{1\}.$ Тогда формула $A(x)\to A(y)$ истинна для $\mathfrak{M}$, для всех предикатов.
Пусть $\mathfrak{M}=\{1,2\}.$ Тогда формула $\forall xA(x)\vee\forall x(\neg A(x)\vee B(x))\vee\forall x(\neg A(x)\vee\neg B(x))$ истинна для $\mathfrak{M}$, для всех предикатов. (Смотреть также Клини "МЛ", параграф 17, упражнение 17.7.)

Цитата:

Если формула истинна для всякой области $\mathfrak{M}$ и для всяких предикатов, будем называть её тождественно истинной или просто истинной.

Примеры формул: $F(x)\vee\neg F(x)$, $\forall xG(x,y)\to G(y,y).$

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