2014 dxdy logo

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

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


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


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

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

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

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



Начать новую тему Ответить на тему На страницу 1, 2, 3  След.
 
 замкнутость ФАЛ
Сообщение20.06.2010, 13:14 
Аватара пользователя


23/01/08
565
Задача 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,...\}$) множество (или класс, я не понимаю, почему это может не быть множеством) не замкнуто?

 Профиль  
                  
 
 Re: замкнутость ФАЛ
Сообщение20.06.2010, 14:26 
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: замкнутость ФАЛ
Сообщение20.06.2010, 15:00 
Аватара пользователя


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

 Профиль  
                  
 
 Re: замкнутость ФАЛ
Сообщение20.06.2010, 15:09 
Заслуженный участник
Аватара пользователя


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

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

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}}$ не принадлежит. Значит, этот класс незамкнут.

 Профиль  
                  
 
 Re: замкнутость ФАЛ
Сообщение20.06.2010, 15:15 


27/01/10
260
Россия
Spook в сообщении #333103 писал(а):
Конъюнкциями нуль не получишь, какой смысл его вносить в $A$?

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

 Профиль  
                  
 
 Re: замкнутость ФАЛ
Сообщение20.06.2010, 16:38 
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: замкнутость ФАЛ
Сообщение20.06.2010, 17:11 
Заслуженный участник
Аватара пользователя


06/10/08
6422
Spook в сообщении #333133 писал(а):
Xaositect, мне кажется, я вот чего не понял: кол-во аргументов. Как я сейчас думаю, оно важно и тогда я разобрался со всеми заданиями. В таком случае, можно ли считать незамкнутым множество $A=\{1,x_1\oplus x_2\}$ только потому, что его замыкание - линейные выражения (включая те, которые зависят не от двух переменных)? Если да, то это всё как-то странно...
Да, это множество незамкнуто. Оно порождает класс всех линейных функций, который уже является замкнутым.
А количество аргументов у формулы может быть произвольным. При совсем строгом изложении обычно говорят, что есть счетное число различных переменных $x_1,\dots,x_n,\dots$. А по определению формулы в функцию можно подставлять любые переменные, не обязательно те, которые указаны в ее описании.

 Профиль  
                  
 
 Re: замкнутость ФАЛ
Сообщение20.06.2010, 17:16 
Аватара пользователя


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

 Профиль  
                  
 
 Re: замкнутость ФАЛ
Сообщение20.06.2010, 17:27 
Заслуженный участник
Аватара пользователя


06/10/08
6422
Spook в сообщении #333143 писал(а):
В таком случае, на чем основана незамкнутость в Вашем втором примере? Было четное число аргументов, потом показали, что можно задать функцию, зависящую от одного аргумента, т.е. нечетного числа. Так?
Да

 Профиль  
                  
 
 Re: замкнутость ФАЛ
Сообщение20.06.2010, 17:36 
Аватара пользователя


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

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

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

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

 Профиль  
                  
 
 Re: замкнутость ФАЛ
Сообщение20.06.2010, 17:44 
Заслуженный участник
Аватара пользователя


06/10/08
6422
Spook в сообщении #333149 писал(а):
То есть были функции, зависящие от двух переменных, а порождаются - от большего числа. Этого достаточно для незамкнутости?
Да.

 Профиль  
                  
 
 Re: замкнутость ФАЛ
Сообщение20.06.2010, 17:46 
Аватара пользователя


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

 Профиль  
                  
 
 Re: замкнутость ФАЛ
Сообщение20.06.2010, 17:52 
Аватара пользователя


14/08/09
1140
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,...\}$;
Смысл включения нуля здесь искать не надо, мы просто захотели рассмотреть такой класс функций.
--
Дальше, рассуждая по аналогии проведите все д-ва сами (можете использовать подсказки из моего первого поста).

 Профиль  
                  
 
 Re: замкнутость ФАЛ
Сообщение20.06.2010, 17:55 
Аватара пользователя


23/01/08
565
почему $x_3\in A$?

 Профиль  
                  
 
 Re: замкнутость ФАЛ
Сообщение20.06.2010, 17:56 


27/01/10
260
Россия
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$. Верно же?

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 41 ]  На страницу 1, 2, 3  След.

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



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

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


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

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