Дискретная математика. Функциональная замкнутость

[Stensen]

Доброго времени суток. Уважаемые, помогите разобраться. Приведен пример:
Класс $B= \left\lbrace x \vee y , x \& y \right\rbrace $ незамкнут, т.к., например, $x_1\vee x_2\vee x_3 \vee x_4 \& x_5 =f \in [B]$ , но $f \notin B $.
Замыканием $$ по определению это множество всех функций из $P_2$ , представимых в виде формулы над $B$, поэтому, вроде, очевидно, что $f \in [B]$ , но почему f \notin B$$ ? Вроде для построения $f$ используются функции, входящие в $B$ ?

[Xaositect]

$B$ состоит ровно из двух функций, и $f$ не является ни одной из них.

[Stensen]

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

$B$ состоит ровно из двух функций, и $f$ не является ни одной из них.

Видимо я не правильно понимаю понятие "формула".
1. $B$ состоит только из двух функций: дизъюнкции и конъюнкции, и $f$ состоит из дизъюнкций и конъюнкций, ничего сверх $B$.
2. Если некая $f \in B$ , например, $f=x_1 \vee x_2$ , то разве композиция $f=x_1\vee (x_2\vee x_3)$ не является функцией из $B$ ?

Если можно, приведите пожалуйста примеры $f \in B$ и $f \notin B$ и поясните почему является и не является.

Спасибо за ответ

[mihaild]

Тут вопрос не про формулы, а про функциональную замкнутость.
То, что $f$ выражается через функции из $B$, не означает, что сама $f$ принадлежит $B$.

Stensen в сообщении #1467038 писал(а):

разве композиция $f=x_1\vee (x_2\vee x_3)$ не является функцией из $B$ ?

Совершенно не обязательно. Существует куча не замкнутых относительно композиции множеств функций.

Stensen в сообщении #1467038 писал(а):

примеры $f \in B$ и $f \notin B$

Ну пример $f \notin B$ вы привели сами. Почему $f \notin B$? Ну потому что в $B$ всего два элемента, и $f$ отличается от них обоих (например тем, что функции из $B$ зависят от двух аргументов, а $f$ от пяти).

[Stensen]

mihaild в сообщении #1467041 писал(а):

Ну пример $f \notin B$ вы привели сами. Почему $f \notin B$? Ну потому что в $B$ всего два элемента, и $f$ отличается от них обоих (например тем, что функции из $B$ зависят от двух аргументов, а $f$ от пяти).

Правильно я понимаю, что:
$x_1 \vee x_2 \vee (x_1\& x_2)=f \in B$ ,
$x_1 \vee x_2 \vee x_3 =f \notin B$ т.к. имеет три переменные?

И попутный вопрос, может ли функция $f$ выражаться через функции из $B$ и не принадлежать $[B]$ ?

[mihaild]

Stensen в сообщении #1467045 писал(а):

$x_1 \vee x_2 \vee (x_1\& x_2)=f \in B$ ,
$x_1 \vee x_2 \vee x_3 =f \notin B$ т.к. имеет три переменные?

Не совсем. Функция $x_1 \vee x_2 \vee (x_1 \wedge x_2)$ действительно принадлежит $B$, но не из-за числа переменных, а просто потому что это та же функция, что и $x_1 \vee x_2$.
Число переменных - это просто один из способов легко заметить, что две функции отличаются.

Stensen в сообщении #1467045 писал(а):

может ли функция $f$ выражаться через функции из $B$ и не принадлежать $[B]$ ?

А как $[B]$ определяется?

[Stensen]

mihaild в сообщении #1467046 писал(а):

А как $ [ B ] $ определяется?

$[ B ]$ это множество всех $f\in P_2$ , представимых в виде формул над $B$.
Просто пока не улавливаю то, что Вы сказали:

mihaild в сообщении #1467041 писал(а):

Тут вопрос не про формулы, а про функциональную замкнутость.
То, что $f$ выражается через функции из $B$, не означает, что сама $f$ принадлежит $B$.

[Aritaborian]

Stensen, если следовать вашим рассуждениям, то вообще выходит, что $B$ должно быть равно $[B]$. Ну а смысл тогда?

[Stensen]

Aritaborian в сообщении #1467056 писал(а):

Stensen, если следовать вашим рассуждениям, то вообще выходит, что $B$ должно быть равно $[B]$. Ну а смысл тогда?

Из определения замыкания "$[ B ]$ это множество всех $f\in P_2$ , представимых в виде формул над $B$", которое я привел из учебника, вроде это и следует. В этом и вопрос.

[Aritaborian]

Это совершенно из него не следует. Xaositect дал ответ сразу же, дальнейшее уже жвачка.

[mihaild]

Stensen в сообщении #1467052 писал(а):

представимых в виде формул над $B$

Что такое "представимость в виде формулы над $B$"?
Вообще, $B$ это множество функций или формул? А $[B]$?

[Stensen]

mihaild в сообщении #1467076 писал(а):

Что такое "представимость в виде формулы над $B$"?
Вообще, $B$ это множество функций или формул? А $[B]$?

$B$ это множество функций, а $ [B] $ это множество всех суперпозиций этих функций. Представимость в виде формулы над $B$, понимаю как получение суперпозиций этих функций (которым, попутно, можно сопоставить функцию). Если не верно подправьте пожалуйста.
С первым вопросом вроде разобрался. Всем спасибо.