2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.



Начать новую тему Ответить на тему
 
 Математическая логика
Сообщение14.12.2008, 02:24 


22/11/08
4
Здравствуйте!

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

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

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

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

 Профиль  
                  
 
 
Сообщение14.12.2008, 02:32 
Модератор


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

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

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

 Профиль  
                  
 
 Еще раз просьба
Сообщение14.12.2008, 13:28 


22/11/08
4
Формулы исправил.

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

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

 Профиль  
                  
 
 
Сообщение14.12.2008, 15:26 
Модератор


16/01/07
1567
Северодвинск
 !  Jnrty:
Коляныч в сообщении #167468 писал(а):
Формулы исправил.


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

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

 Профиль  
                  
 
 ...
Сообщение14.12.2008, 16:16 


22/11/08
4
Ну теперь уж точно все исправил:)

 Профиль  
                  
 
 Re: Математическая логика
Сообщение23.02.2009, 23:50 
Аватара пользователя


01/12/06
697
рм
Коляныч писал(а):
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).$

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 6 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group