замкнутость ФАЛ

[Spook]

Задача 1.9 из задачника Гаврилова, Сапоженко по дискретной математике. Является ли множество $A$ замкнутым классом?
6) $A=\{x_1\oplus...\oplus x_n,n=1,2,...\}$;
7) $A=\{0,x_1\vee...\vee x_n,n=1,2,...\}$;
8) $A=\{x_1\oplus...\oplus x_{2n-1},n=1,2,...\}$;
9) $A=\{0,x_1\oplus...\oplus x_{2n-1},n=1,2,...\}$.

Интересно, слово "класс" в условии для разнообразия или что-то подчёркивается?

В ответах:
6), 9) - не является;
7), 8) - является.

Именно с этими примерами не могу разобраться.

Класс (множество) называется замкнутым, если он совпадает со своим замыканием.
Замыкание - множество всех булевых функций (из $P_2$), представимых в виде формул через функции множества $A$.

Например, в пункте 6) замыканием будет множество функций, имеющих вид $f(x_1,...,x_n)=c_1x_1\oplus...\oplus c_nx_n$, где $c_i=0,1(i=1,...,n)$; существенные переменные входят с коэффициентом 1, фиктивные - с коэффициентом 0. Почему это ($A=\{x_1\oplus...\oplus x_n,n=1,2,...\}$) множество (или класс, я не понимаю, почему это может не быть множеством) не замкнуто?

[Mathusic]

Если в первом задании отождествить все переменные при чётном $n$, то что получим ? А оно принадлежит самому классу?

7) Докажите что $1 \not \in [A]$
8) Докажите $\{0,1\}\not \in [A]$
9) Докажите $1 \in [A]$

[Spook]

Mathusic, спасибо. Но мне непонятна, например, суть нуля в 7). Конъюнкциями нуль не получишь, какой смысл его вносить в $A$?

[Xaositect]

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

Давайте рассмотрим чуть-чуть другие примеры, а Вы потом по аналогии попытаетесь доказать замкнутость/незамкнутость классов из задачки.

Spook в сообщении #333073 писал(а):

Класс (множество) называется замкнутым, если он совпадает со своим замыканием.
Замыкание - множество всех булевых функций (из $P_2$), представимых в виде формул через функции множества $A$.

Давайте чуть-чуть переформулируем. Класс будет замкнутым, если он совпадает со своим замыканием, т.е. любой элемент замыкания должен принадлежать исходному классу. Элемент замыкания $f\in [A]$- это функция, заданная формулой над $A$. То есть окончательно получаем, что класс $A$ замкнут, если любая формула над $A$ выражает функцию, которая принадлежит $A$.

Рассмотрим пример. Возьмем класс $K_{01} = \{x_1 \& \dots \& x_n| n=1,2,\dots\}$. Любая формула над $K_{01}$ будет иметь вид $k = k_1 \& \dots \& k_n$, где $k_i$ - либо переменные, либо тоже формулы. Если $k_1,\dots k_n$ - это конъюнкции нескольких переменных, то и $k$ будет конъюнкцией переменных. То есть любая формула задает конъюнкцию некоторого числа переменных, а значит $K_{01}$ - замкнутый класс.

Рассмотрим теперь класс $L_{\mathrm{even}} = \{x_1 \oplus \dots x_{2n}| n = 0,1,2,\dots\}$ (в случае $n=0$ считаем суммой константу $0$). Построим над $L_{\mathrm{even}}$ формулу $x_1 \oplus (x_1 \oplus x_1)$. Она задает функцию $x_1$, которая классу $L_{\mathrm{even}}$ не принадлежит. Значит, этот класс незамкнут.

[cyb12]

Spook в сообщении #333103 писал(а):

Конъюнкциями нуль не получишь, какой смысл его вносить в $A$?

Вы имели в виду "дизъюнкциями"?
Внесли его туда, видимо, просто так. Ведь $0\vee x_i = x_i \in A$. То есть нуль ничего не портит, просто добавляет еще одну функцию туда.

[Spook]

Xaositect, мне кажется, я вот чего не понял: кол-во аргументов. Как я сейчас думаю, оно важно и тогда я разобрался со всеми заданиями. В таком случае, можно ли считать незамкнутым множество $A=\{1,x_1\oplus x_2\}$ только потому, что его замыкание - линейные выражения (включая те, которые зависят не от двух переменных)? Если да, то это всё как-то странно...

cyb12, да, дизъюнкциями) Тут что с нулем, что без него - рассуждения, как в первом примере Xaositect.

[Xaositect]

Spook в сообщении #333133 писал(а):

Xaositect, мне кажется, я вот чего не понял: кол-во аргументов. Как я сейчас думаю, оно важно и тогда я разобрался со всеми заданиями. В таком случае, можно ли считать незамкнутым множество $A=\{1,x_1\oplus x_2\}$ только потому, что его замыкание - линейные выражения (включая те, которые зависят не от двух переменных)? Если да, то это всё как-то странно...

Да, это множество незамкнуто. Оно порождает класс всех линейных функций, который уже является замкнутым.
А количество аргументов у формулы может быть произвольным. При совсем строгом изложении обычно говорят, что есть счетное число различных переменных $x_1,\dots,x_n,\dots$. А по определению формулы в функцию можно подставлять любые переменные, не обязательно те, которые указаны в ее описании.

[Spook]

В таком случае, на чем основана незамкнутость в Вашем втором примере? Было четное число аргументов, потом показали, что можно задать функцию, зависящую от одного аргумента, т.е. нечетного числа. Так?

[Xaositect]

Spook в сообщении #333143 писал(а):

В таком случае, на чем основана незамкнутость в Вашем втором примере? Было четное число аргументов, потом показали, что можно задать функцию, зависящую от одного аргумента, т.е. нечетного числа. Так?

Да

[Spook]

Тогда все же интересно:

Spook писал(а):

можно ли считать незамкнутым множество $A=\{1,x_1\oplus x_2\}$ только потому, что его замыкание - линейные выражения (включая те, которые зависят не от двух переменных)?

То есть присутствуют функции, зависящие и от $n$ переменных.

-- Вс июн 20, 2010 17:38:37 --

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

[Xaositect]

Spook в сообщении #333149 писал(а):

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

Да.

[Spook]

В последнем пункте единица не принадлежит замыканию?

[Mathusic]

Spook в сообщении #333103 писал(а):

Mathusic, спасибо. Но мне непонятна, например, суть нуля в 7). Конъюнкциями нуль не получишь, какой смысл его вносить в $A$?

Хорошо. Попробую разобрать первые два примера.
6) $A=\{x_1\oplus...\oplus x_n,n=1,2,...\}$
Рассмотрим, например, $n=2$, тогда $x_1\oplus x_2 \in A$, а так как и $x_3\in A$, то $0=x_3\oplus x_3 \in [A]$. Но $0 \not \in A$, значит класс не замкнут.

7)$A=\{0,x_1\vee...\vee x_n,n=1,2,...\}$;
Смысл включения нуля здесь искать не надо, мы просто захотели рассмотреть такой класс функций.
--
Дальше, рассуждая по аналогии проведите все д-ва сами (можете использовать подсказки из моего первого поста).

[Spook]

почему $x_3\in A$?

[cyb12]

Mathusic в сообщении #333157 писал(а):

$A=\{x_1\oplus...\oplus x_n,n=1,2,...\}$
Рассмотрим, например, $n=2$, тогда $x_1\oplus x_2 \in A$, а так как и $x_3\in A$, ...

Как $x_3 \in A$? $A=\{x_1,x_1\oplus x_2, x_1\oplus x_2 \oplus x_3,...\}$?

Что-то я у Вас не понимаю про множество $A=\{1,x_1\oplus x_2\}$. Это множество из двух функций. Оно не замкнутое, хотя бы потому, что $x_1\oplus 1 \in [A]$, $x_1\oplus 1 \notin A$. Верно же?