штрих Шеффера

[Yakov]

Что такое штрих Шеффера от $n$ переменных?
Как показать, что
$\lim_{n \rightarrow \infty} \frac{\Psi(n)} {2^{2^n}} = \frac{1}{4}$, где
$\Psi(n)$ --- число штрихов Шеффера от $n$ переменных?

[Xaositect]

Yakov в сообщении #388234 писал(а):

Что такое штрих Шеффера от $n$ переменных?

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

Цитата:

Как показать, что
$\lim_{n \rightarrow \infty} \frac{\Psi(n)} {2^{2^n}} = \frac{1}{4}$, где
$\Psi(n)$ --- число штрихов Шеффера от $n$ переменных?

Шефферова функция должна не лежать ни в одном из 5 предполных классов. Осталось оценить количество таких функций. Ну там самодвойственных и линейных мало, классы сохранения дают как раз четверть, а немонотонность следует из несохранения констант.

[Yakov]

Просто я думал, что $n$-арный штрих Шеффера --- композиция бинарных, и тогда, очевидно, в пределе получим нуль.

[CYHDYK]

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

[ИСН]

Вот видите, как мало Вы ещё знаете о добрых феях штрихах Шеффера.
(Здесь просто называют этим словом любую функцию, которая... короче, см. тему с начала.)

[CYHDYK]

Ну, я так понял, что имеется ввиду количество всех возможных функций от n переменных скомбинированных попарно? Вот это "попарно" меня смущает, т.к. в знаменателе стоит число вообще всех функций от n переменных. штрих шеффера нельзя представить как f(x1, x2, ...), а можно только в виде f(x1, x2), как тогда оценить число этих функций?

P.S. Задание из ДЗ по теории графов, кстати. Но от этого препода уже были задания не свзаный с темой, так что рад любым советам, не обязательно из графов.

[ИСН]

Имеется в виду то, что написал Xaositect после слова "Видимо". Слова "попарно" там нет, так что нечего смущаться.

[CYHDYK]

хорошо, а как же тогда выглядит эта мифическая шефферова функция?

[ИСН]

Как любая, которая в одиночку образует полную систему. Видите, как их много?

[CYHDYK]

Штрих шеффера - это функция, которая образует полную систему. Но эта функция только от 2-х переменных, а не от n? может я что то не знаю, чего знаете вы?

[ИСН]

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

[Xaositect]

Собственно, мне нравится такая терминология - штрих Шеффера - это вполне конкретная функция $x\mathop{|}y = \overline{xy}$ от 2 переменных, а функции, которые как $|$ в замыкании порождают $P_2$, называются щефферовыми.
Но какой-то преподаватель, судя по формулировке задания в первом посте, называет все шефферовы функции штрихами Шеффера.

[CYHDYK]

математика конкретная и хрупкая наука, и названия тут менять нельзя. В первоначальной задаче написано
$/Psi(n)$ - число штрихов Шеффера от n переменных? Определение функций Шеффера, данное во 2 посте неверно, т.к. функция Шеффера = штрих шеффера, хотя штрих шеффера и образует в одиночку полную систему. Так вот штрих Шеффера - функция 2-х переменных, поэтому вопрос: как определить(оценить) число штрихов Шеффера от n переменных?

П.С. вот ссылка, где в первой строчке написано, что ф. шеффера, то же что и штрих шеффера http://booleanalgebra.narod.ru/basis/S.htm

[Xaositect]

CYHDYK в сообщении #443539 писал(а):

математика конкретная и хрупкая наука, и названия тут менять нельзя.

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

Вот, скажем, из задачника Гаврилова-Сапоженко (http://lib.mexmat.ru/books/8963), гл. II, $\S 6$:

Цитата:

Функция $f(\tilde{x}_n)$ называется шефферовой (или функцией Шеффера), если она образует базис в $P_2$.

Есть и более общее понятие шефферовой функции, где рассматривается не $P_2$, а произвольная функциональная система и произвольное замыкание. Напр. Яблонский, "Введение в дискретную математику", ч.I, гл. 2, $\S 4$, теорема 10:

Цитата:

В заключение рассмотрим еще одно приложение доказанного критерия полноты. Мы дадим характеристическое свойство функции из $P_k$, образующей полную систему (функция Шеффера). Это свойство является незначительным усилением теоремы Мартина [44].

Теорема 10. Функция $f(x_1,\dots, x_n)$ из $P_k$, где $k\geqslant 3$, является функцией Шеффера тогда и только тогда, когда $f(x_1,\dots,x_n)$ порождает все функции одной переменной, принимающие не более $k-1$ значений.

[CYHDYK]

По моему дисскуссия ушла от основной темы, в задаче говорится не о штрихах шеффера от n переменных или функциях шеффера, а о ЧИСЛЕ штрихов шеффера от n переменных(см первый пост). Как это число оценить?

Ух, что то я совсем запутался.