Несколько задач по мат. логике (предикаты и мн-ва)

[UAS]

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

1) На N задан предикат

\[M(x,y,z) \equiv x \cdot y = z\]

. Используя только этот предикат записать формулой логики предикатов:
P(x) \equiv "x есть простое число".

2) Пусть на универсуме U задан предикат

\[Q(x,y) \equiv x \subseteq y\]

. Записать, используя этот предикат, следующее высказывание в виде формулы логики предикатов: "множество x есть пересечение множеств y и z".
В целом, это задание простое, но я понятие не имею, как это правильно записать..

3) Пусть задано разбиение множества

\[X = \{ 1,2,3,4,5,6,7,8\} \]

так:

\[X = \{ 2,7\} \cup \{ 1,3,8\} \cup \{ 4\} \cup \{ 5,6\} \]

.
Построить отношение

\[\rho \]

на Х так, чтобы множества, составляющие разбиение, были классами эквивалентности

\[\rho \]

[Xaositect]

UAS в сообщении #195610 писал(а):

1) На N задан предикат \[M(x,y,z) \equiv x \cdot y = z\]. Используя только этот предикат записать формулой логики предикатов:
P(x) \equiv "x есть простое число".

Для начала выразите через $M$ свойство "$x$ делится на $y$"

UAS в сообщении #195610 писал(а):

2) Пусть на универсуме U задан предикат \[Q(x,y) \equiv x \subseteq y\]. Записать, используя этот предикат, следующее высказывание в виде формулы логики предикатов: "множество x есть пересечение множеств y и z".
В целом, это задание простое, но я понятие не имею, как это правильно записать..

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

[gris]

По поводу третьей задачи. Что если построить функцию, которая равна 0 при 2 и 7, 1 при 1,3,8 и т.д. Многочлен это слишком громоздко, хотя наиболее просто. Что-нибудь с делимостью на 4?
Элементы будут эквивалентны, если функция на них принимает одинаковое значение.

[Xaositect]

gris писал(а):

По поводу третьей задачи. Что если построить функцию, которая равна 0 при 2 и 7, 1 при 1,3,8 и т.д. Многочлен это слишком громоздко, хотя наиболее просто. Что-нибудь с делимостью на 4?
Элементы будут эквивалентны, если функция на них принимает одинаковое значение.

А зачем?
Отношение можно задать таблично.

[VAL]

UAS писал(а):

3) Пусть задано разбиение множества

\[X = \{ 1,2,3,4,5,6,7,8\} \]

так:

\[X = \{ 2,7\} \cup \{ 1,3,8\} \cup \{ 4\} \cup \{ 5,6\} \]

.
Построить отношение

\[\rho \]

на Х так, чтобы множества, составляющие разбиение, были классами эквивалентности

\[\rho \]

Эта задачка самая смешная.
Отношение задается так:
$a\rho b \equiv a$ и $b$ лежат в одном классе указанного разбиения

[TypucT]

VAL писал(а):

UAS писал(а):

3) Пусть задано разбиение множества

\[X = \{ 1,2,3,4,5,6,7,8\} \]

так:

\[X = \{ 2,7\} \cup \{ 1,3,8\} \cup \{ 4\} \cup \{ 5,6\} \]

.
Построить отношение

\[\rho \]

на Х так, чтобы множества, составляющие разбиение, были классами эквивалентности

\[\rho \]

Эта задачка самая смешная.
Отношение задается так:
$a\rho b \equiv a$ и $b$ лежат в одном классе указанного разбиения

Сказано построить, а не определить.
Так что лучше делать, как Xaositect посоветовал - указать все пары, помня о рефлексивности, симметричности и транзитивности.

[VAL]

TypucT писал(а):

VAL писал(а):

UAS писал(а):

3) Пусть задано разбиение множества

\[X = \{ 1,2,3,4,5,6,7,8\} \]

так:

\[X = \{ 2,7\} \cup \{ 1,3,8\} \cup \{ 4\} \cup \{ 5,6\} \]

.
Построить отношение

\[\rho \]

на Х так, чтобы множества, составляющие разбиение, были классами эквивалентности

\[\rho \]

Эта задачка самая смешная.
Отношение задается так:
$a\rho b \equiv a$ и $b$ лежат в одном классе указанного разбиения

Сказано построить, а не определить.

А в чем разница?
Определение-то конструктивное.

Цитата:

Так что лучше делать, как Xaositect посоветовал - указать все пары, помня о рефлексивности, симметричности и транзитивности.

В моем определении, как раз, указаны все пары.

[TypucT]

VAL писал(а):

TypucT писал(а):

VAL писал(а):

UAS писал(а):

3) Пусть задано разбиение множества

\[X = \{ 1,2,3,4,5,6,7,8\} \]

так:

\[X = \{ 2,7\} \cup \{ 1,3,8\} \cup \{ 4\} \cup \{ 5,6\} \]

.
Построить отношение

\[\rho \]

на Х так, чтобы множества, составляющие разбиение, были классами эквивалентности

\[\rho \]

Эта задачка самая смешная.
Отношение задается так:
$a\rho b \equiv a$ и $b$ лежат в одном классе указанного разбиения

Сказано построить, а не определить.

А в чем разница?
Определение-то конмтруктивное.

Цитата:

Так что лучше делать, как Xaositect посоветовал - указать все пары, помня о рефлексивности, симметричности и транзитивности.

В моем определении, как раз, указаны все пары.

Пожалуй, да, разница невелика.

[UAS]

Вообщем посидел немного, придумал следующее для двух задач:

1) Тут руководствовался следующим: число при делении на 1,2,3 дает 1 и по свойству

\[x^2 - 1\]

кратно 24 (если х - простое и > 3).

\[P(x) = \exists x\left[ {M(x,1,1) \vee M(x,1,2) \vee M(x,1,3) \vee \exists y\left[ {M(x \cdot x - 1,y,24)} \right]} \right] \]

Вот что-то такое, такое чувство, что криво, но вроде то, что надо. На большее пока мозгов не хватает..


2) Тут получилось так:

\[\exists x\exists y\exists z\left[ {Q(x,y) \wedge Q(x,z)} \right]\]

Вот. Примерно верно это или нет?

[TypucT]

UAS писал(а):

Вообщем посидел немного, придумал следующее для двух задач:

1) Тут руководствовался следующим: число при делении на 1,2,3 дает 1 и по свойству

\[x^2 - 1\]

кратно 24 (если х - простое и > 3).

\[P(x) = \exists x\left[ {M(x,1,1) \vee M(x,1,2) \vee M(x,1,3) \vee \exists y\left[ {M(x\cdotx - 1,y,24)} \right]} \right] \]

Вот что-то такое, такое чувство, что криво, но вроде то, что надо. На большее пока мозгов не хватает..


2) Тут получилось так:

\[\exists x\exists y\exists z\left[ {Q(x,y) \wedge Q(x,z)} \right]\]

Вот. Примерно верно это или нет?

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

Добавлено спустя 6 минут 23 секунды:

Ваш 1) утверждает словами: существует x такой, что $x=1$ или $x=2$ или $x=3$ или найдется $y$ такой, что $(x-1)y=24$
Ваш 2) утверждает: найдутся такие $x$, $y$, $z$, что $x\subseteq y$ и $x\subseteq z$

[Xaositect]

UAS писал(а):

1) Тут руководствовался следующим: число при делении на 1,2,3 дает 1 и по свойству

\[x^2 - 1\]

кратно 24 (если х - простое и > 3).

Хмм... Вы усложняете. Я такого свойства то не знал никогда
Вас просят дать определение простого числа на формальном языке.
Давайте я попробую это сделать на каком-нибудь другом примере.
Например, выразим свойство "быть иррациональным числом" через предикаты $I(x)$ - "$x$ - целое", $Q(x, y, z)$ - "$z$ есть частное от деления $x$ на $y$".
$x$ - иррациональное - значит, $x$ не рационально, т.е. не может быть отношением двух целых чисел.
Т.е. какие бы целые числа мы не взяли, неверно, что $x$ есть их отношение
Формально: $\forall u\forall v(I(u)\&I(v)\rightarrow \neg Q(u,v,x))$

Цитата:

2) Тут получилось так:

\[\exists x\exists y\exists z\left[ {Q(x,y) \wedge Q(x,z)} \right]\]

Кванторы стоят неверно
$Q(x,y) \wedge Q(x,z)$ значит, что $x$ есть общее подмножество $y$ и $z$ - эта часть в результате будет, но нужно что-то еще.
Если, например, $y=\{1,2,3\}$, $z=\{1,3,5\}$, то формула $Q(x,y) \wedge Q(x,z)$ будет верна для $x=\{1,3\}$, $x=\{3\}$, $x=\{1\}$, $x=\emptyset$

[UAS]

TypucTА, понял..

1)

\[P(x) = M(x,1,1) \vee M(x,1,2) \vee M(x,1,3) \vee \exists y\left[ {M(x \cdot x - 1,y,24)} \right]\]

Т.е. тем самым передаем x в выражение, если оно равно 1,2,3, то простое. Иначе если существует такое

\[y \in mathbb{N}\]

и y получается целым при делении на 24, то число четное.

2)

\[F(x,y,z) = Q(x,y) \wedge Q(x,z)\]

Xaositect, так тут-то все надо через один предикат сделать. Если б можно было дополнительные заводить, то задача была бы проще, я думаю)

[Xaositect]

Как-то не верится, что если $x^2\equiv 1(\mathrm{mod} 24)$, то $x$-простое. Это неверно, $x=25$ - контрпример.
Веразите через $M$ отношение "$x$ делится на $y$", а дальше не ищите никаких свойств, воспользуйтесь определением простого числа.

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

Добавлено спустя 1 минуту 2 секунды:

UAS в сообщении #196169 писал(а):

Xaositect, так тут-то все надо через один предикат сделать. Если б можно было дополнительные заводить, то задача была бы проще, я думаю)

Разницы особой нет, я просто сходу не придумал хороший пример с одним предикатом.

Добавлено спустя 3 минуты 28 секунд:

Xaositect в сообщении #196172 писал(а):

Разницы особой нет, я просто сходу не придумал хороший пример с одним предикатом.

Придумал
$L(x, y)$ - $x\leq y$
тогда отношение "$z$ есть минимум из $x$ и $y$" запишется так:
$L(z,x)\& L(z,y)\& \forall v(L(v,x)\& L(v,y)\rightarrow L(v,z))$
Строго говоря, это определение не минимума, а точной нижней грани, но для чисел это одно и то же.

[TypucT]

И $1$ тоже простым числом не считается. (В дополнение к тому, что сказал Xaositect)

Добавлено спустя 5 минут 30 секунд:

UAS писал(а):

Иначе если существует такое

\[y \in mathbb{N}\]

и y получается целым при делении на 24, то число четное.

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

[UAS]

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

1)

\[P(x) = \neg \left[ {\,\forall y\exists r[\,M(r,x,y) \wedge \neg M(1,r,1) \wedge \neg M(1,r,x) \wedge \exists zM(z,r,x)\,]\,} \right]\]

Эту запись я понимаю так: P(x) - функция, определяющая простое число p или нет на множестве натуральных чисел.
Само выражение: для любого y существует такое r, что: r является частным от "y делить на x", r

\[\ne\]

1, r

\[\ne\]

x, и существует такое z, которое является частным от "x делить на r" (т.е. проверка на взаимную простоту r и x). Тем самым получим выражение для числа, кот. не является простым, теперь остается лишь инвертировать это выражение и получим нужную нам функцию проверки числа на простоту. Вот. Вроде то, что мне надо.
Пробовал на комбинациях чисел (r,x,y): (2,4,8); (3,7,21); (4,5,20); (4,6,24); (1,2,2); (3,3,9) и везде получил необходимый верный мне результат. Проверьте, правильно ли составил выражение, плз.

2) Учитывая последний пост Xaositect, сделал следующее (по аналогии):

\[Q(x,y) \wedge Q(x,z) \wedge \forall r\left[ {Q(r,y) \wedge Q(r,z) \to Q(r,x)} \right]\]

. Т.е. тем самым произвели то самое объединение всех возможных множеств в одно множество.

3) Я так понимаю, что это надо решать на подобии того, как описано в этой теме? Т.е. придумать какие-либо условия (например, простое или делиться на 3 и т.д.) и в зависимости от них строить таблицу истинности для получения необходимых разбиений?