графы, формула логики ПП.

[gefest_md]

Помогите, пожалуйста с такой задачей:

Цитата:

2.17. (a) Define a $\nu_G$-sentence $\varphi$ such that $\neg\varphi$ has arbitrarily large finite models and, for any finite graph $G$, if $|G|$ is even, then $G\models\varphi.$

Не будет ли искомая формула решением для множества, а не только для графа? Для чего нужно условие «$\neg\varphi$ has arbitrarily large finite models», и почему $\neg\varphi$, а не $\varphi$?

[Xaositect]

Что такое $\nu_G$-sentence?

gefest_md в сообщении #610049 писал(а):

Для чего нужно условие «$\neg \varphi$ has arbitrarily large finite models»

Для того, чтобы нельзя было взять тривиальное $\varphi$.

[gefest_md]

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

Что такое $\nu_G$-sentence?

Цитата:

We can view any graph as a structure $G$ as follows. The underlying set $U$ of $G$ is the set of vertices. The vocabulary $\nu_G$ of $G$ consists of a single binary relation $R.$ The structure $G$ interprets $R$ as the edge relation. That is, for elements $a$ and $b$ of $U$, $G\models R(a,b)$ if and only if the graph has an edge between vertices $a$ and $b$.

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

Для того, чтобы нельзя было взять тривиальное $\varphi$.

Идея. Можеть взять в качестве $\varphi$ тавтологию? Я подозревал, в контексте, что задача не сложная, пока не потратил полдня на неё. Спасибо.

[Профессор Снэйп]

1) $\varphi_1(x) : \forall y \neg R(x,y)$
2) $\varphi_2x) : \forall y \forall z(R(x,y) \mathop{\&} R(x,z) \rightarrow y = z)$.
3) $\varphi_3(x) : \exists y (R(x,y) \mathop{\&} R(y,x) \mathop{\&} y \neq x \mathop{\&} \varphi_2(x) \mathop{\&} \varphi_2(y))$
4) $\varphi : \neg\exists x (\varphi_1(x) \mathop{\&} \forall y(y = x \vee \varphi_3(y)))$

-- Пт авг 24, 2012 19:42:33 --

gefest_md в сообщении #610123 писал(а):

Идея. Можеть взять в качестве $\varphi$ тавтологию? Я подозревал, в контексте, что задача не сложная, пока не потратил полдня на неё. Спасибо.

Тавтологию, конечно же, нельзя. Ибо её отрицание не будет истинно на сколь угодно больших конечных графах нечётной мощности.

Я Вам решение, собственно, уже написал Оставлю его без пояснений, там всё довольно прозрачно.

[gefest_md]

Профессор Снэйп
У меня не получается доказать, что если $G$ "чётный" граф, то $\varphi$ истина.
Пусть $x$ произвольная изолированная вершина $G$. Тогда по предположению выберем вершину $a$, $a\neq x.$ Надо доказать, что $\neg\varphi_3(a).$ Предположим противное, что $\varphi_3(a).$ Тогда:
$R(a,a_1)\wedge R(a_1,a)\wedge a_1\neq a\wedge\varphi_2(a)\wedge\varphi_2(a_1)$
Но $\varphi_2$ означает, что любые два ребра, выходящие из одной вершины ($a,\,a_1$), совпадают. В результате получаю граф в виде "ступеней" с чётным количеством изолированных вершин, а противоречие так и не следует.

[Профессор Снэйп]

gefest_md в сообщении #610233 писал(а):

Профессор Снэйп
У меня не получается доказать, что если $G$ "чётный" граф, то $\varphi$ истина.

Элемент $x$ назовём парным, если он связан с единственным элементом $y$, который отличен от него, и сам элемент $y$ связан, в свою очередь, с $x$ и только с $x$. Количество парных элементов, очевидно, всегда является чётным. А отрицание $\neg\varphi$ утверждает, что один из элементов графа не связан ни с каким другим, а все остальные элементы парные.

[gefest_md]

Профессор Снэйп в сообщении #610322 писал(а):

А отрицание $\neg\varphi$ утверждает, что один из элементов графа не связан ни с каким другим, а все остальные элементы парные.

Один единственный: $\exists!x$ в формуле $\varphi$.

[Профессор Снэйп]

gefest_md в сообщении #610421 писал(а):

Профессор Снэйп в сообщении #610322 писал(а):

А отрицание $\neg\varphi$ утверждает, что один из элементов графа не связан ни с каким другим, а все остальные элементы парные.

Один единственный: $\exists!x$ в формуле $\varphi$.

Восклицательный знак, кстати, в языке исчисления предикатов изначально отсутствует. Но это не проблема, ибо исчисление с равенством

Сейчас ещё раз всё проверил и убедился, что у меня всё правильно написано. Странно, что у Вас до сих пор вопросы. Идею я изложил, формулы аккуратно выписал. Если всё ещё что-то непонятно, спрашивайте в конкретных местах.

Насчёт единственности "изолированного $x$". Ну да он само собой будет единственным. Парный элемент не может быть изолированным, изолированный не может быть парным, а я пишу, что существует изолированный элемент, такой, что все отличные от него элементы - парные. Смотрите внимательнее!

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

$$ \forall x(x \neq f(x) \mathop{\&} x = f(f(x))) $$

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

[gefest_md]

(Оффтоп)

Профессор Снэйп в сообщении #610426 писал(а):

Ну и самое простое решение: берём функциональную сигнатуру с одним символом одноместной функции и пишем

$$ \forall x(x \neq f(x) \mathop{\&} x = f(f(x))) $$

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

Эту формулу я использовал в одной задаче про "finite spectrum". Там я написал $f(i)=n-i+1.$ А здесь не понимаю! Т.е. зачем, раз в "vocabulary" только буква $R$, и нету $f.$ Не хочу я эту нагрузку. Поэтому спрятал.

Возвращаюсь к $\varphi.$ В принципе, я согласен, что $\varphi$ искомая. Теперь я спрашиваю как доказать предложение: Если $|G|$ - чётная, то $G\models\varphi$? Правильно ли я это делаю?

Вариант (1). Пусть $|G|$ - чётная. Предположим, что $G\models\neg\varphi.$ Это значит, что существует изолированная вершина такая, что все остальные вершины, отличные от данной, парные. Тогда $|G|$ - нечётная. Противоречие.

Вариант (2). Переписываю $\varphi$ в виде: $\forall x\left(\varphi_1(x)\to\exists y\left(y\neq x\mathop{\&}\neg\varphi_3(y)\right)\right) и доказываю:
Пусть $G$ - "чётный". Пусть $x$ произвольная изолированная вершина. Пусть $y=a\neq x.$ Такая вершина есть, поскольку $G$ - "чётный". Надо доказать $\neg\varphi_3(y).$ Предположим $\varphi_3(y).$ Тогда $y$ - парная. И всё. То есть, ясность, которая в какой-то мере присутствовала в варианте (1), здесь отсутствует.

[Профессор Снэйп]

gefest_md в сообщении #610482 писал(а):

Вариант (2). Переписываю $\varphi$ в виде: $\forall x\left(\varphi_1(x)\to\exists y\left(y\neq x\mathop{\&}\neg\varphi_3(y)\right)\right) и доказываю:
Пусть $G$ - "чётный". Пусть $x$ произвольная изолированная вершина. Пусть $y=a\neq x.$ Такая вершина есть, поскольку $G$ - "чётный". Надо доказать $\neg\varphi_3(y).$ Предположим $\varphi_3(y).$ Тогда $y$ - парная. И всё. То есть, ясность, которая в какой-то мере присувствовала в варианте (1), здесь отсувствует.

Чёт Вы не то доказываете. Вам надо показать, что для каждого нечётного числа найдётся граф с этим числом элементов, на котором будет истинна $\neg\varphi$. Ну так это вроде очевидно: из данного нечётного множества отщепляете один элемент, делаете его изолированным, остальные связываете попарно и всё Ок. А то, что $\neg\varphi$ будет истинной на каждом графе с нечётным числом элементов, никто и не утверждал. Более того, ничего подобного в задаче и не требовалось! Перечитайте условие!

Кстати, построить предложение $\varphi$, истинное на всех графах с чётным числом элементов и ложное на всех графах с нечётным числом не получится. В связи с 0-1 law (см., например, здесь, стр. 235)

[gefest_md]

Запутался совсем. Я про нечётное молчал пока.

Профессор Снэйп в сообщении #610493 писал(а):

А то, что $\neg\varphi$ будет истинной на каждом графе с нечётным числом элементов, никто и не утверждал.

$\varphi$ будет истинной на каждом графе с чётным числом элементов. Это же я как-бы и доказал. "Нечётное" появится если возьму контрапозицию от данной задачи.

[Профессор Снэйп]

gefest_md в сообщении #610505 писал(а):

$\varphi$ будет истинной на каждом графе с чётным числом элементов. Это же я как-бы и доказал. "Нечётное" появится если возьму контрапозицию от данной задачи.

В чём проблема-то, где эти три сосны? Зачем контрапозиция?

Предложение $\varphi$ истинно на всех чётных графах и на некоторых нечётных. Но не на всех. Но на достаточно большом количестве. В частности, для каждого натурального $n$ существуют натуральное $k$ и граф $G$ мощности $| G | = 2k + 1 > n$ такие, что на $G$ выполнено $\neg\varphi$. В точности то, что требовалось в условии задачи!