Задачки по дискретной математике

serengeti

помнится, был такой тред несколько лет назад. весьма полезный. правда, создавался он и развивался в
сессию, но так уж вышло, прошу вашей помощи - помогите идеями/решениями задачек по дискре
1. эту задачу не смог решить на основном.
сколько существует замкнутых классов в P_2? а если вопрос про полные или предполные классы? в каком
направлении копать хотя бы?

zzzXAXAXAzzz

классов, замкнутых относительно суперпозиции, по-моему 17... лень за семинарской тетрадкой идти... Классы типа констант, x, x и отрицания, дизъюнкции и т.д.

serengeti

относительно суперпозиции
ты имеешь в виду формулу над множеством функций?

serengeti

вот еще хорошая задачка
2. доказать, что в полной системе из ровно 4х функций обязательно есть "0"

Dallas

классов, замкнутых относительно суперпозиции, по-моему 17... лень за семинарской тетрадкой идти... Классы типа констант, x, x и отрицания, дизъюнкции и т.д.
П*здёж. Их счётно.

serengeti

Их счётно.
и мне так кажется только вот как это показать?

serengeti

а как подсчитать количество симметрических функций в P_2?

Sersk

Кочергин мне как-то задал задачку:
найти все предполные классы в Т_1.
я целые сутки ипался, но решил..
тоже довольно интересная
в дискре многие задачи звучат очень просто, но за их решением нужно лезть в непролазные дебри..

Sersk

> а как подсчитать количество симметрических функций в P_2?
может полиномы Жегалкина в этом пригодятся?

Dallas

то, что как минимум счётно - это легко:
для каждого натурального k рассмотрим множество всех функций f таких, что для любых наборов x1,...,xk таких, что f(x1)=...=f(xk)=1, имеет место x1&...&xk != (0,0,...,0).
По-моему, каждый такой класс замкнут и все они различны.
А вот доказать, что не более, чем счетно - это по-моему только перечислением всех классов (там ах*енная помню диаграмма получается, полный процесс объяснения занимает примерно 10 двухчасовых лекций)

serengeti

всем спасибо за наводки завтра с утра посмотрю, спок ночи!

neemah86

доказать, что в полной системе из ровно 4х функций обязательно есть "0"
Это вроде почти сразу следует из теоремы Поста:
для любого предполного класса T1, T2, L, M, S среди наших ф-ций должна быть ему непринадлежащая
возьмем ту, которая не сохраняет 1
рассмотрим для неё нулевой набор, получим что она или несамодвойственная или не сохраняет 0
если эта функция имеет на каком-то наборе единицу, то она еще и немонотонна, тогда из исходной системы можно выделить полную систему из 3 функций(вроде как противоречие)
следовательно эта функция тождественный 0

neemah86

3. а как подсчитать количество симметрических функций в P_2?
от n переменных?
тогда очедно что 2^(n+1 т.к. это функции от веса набора

CokpaT

А вот доказать, что не более, чем счетно - это по-моему только перечислением всех классов (там ах*енная помню диаграмма получается, полный процесс объяснения занимает примерно 10 двухчасовых лекций)
ну десять лекций - это как-то черезчур
А "не менее, чем счетное" следует, в частности, из того, что функции d_m (дизъюнкции попарных конъюнкций переменных x_1,...,x_m) друг через друга не выражаются, т.е. образуют разные замкнутые классы для каждого m.

CokpaT

1. эту задачу не смог решить на основном.
сколько существует замкнутых классов в P_2? а если вопрос про полные или предполные классы? в каком направлении копать хотя бы?
что-то я не поняла, в чем состоит "вопрос про полные или предполные классы". Сколько полных классов что ли?

Dallas

ну десять лекций - это как-то черезчур
а какое есть простое доказательство?
А "не менее, чем счетное" следует, в частности, из того, что функции d_m (дизъюнкции попарных конъюнкций переменных x_1,...,x_m) друг через друга не выражаются, т.е. образуют разные замкнутые классы для каждого m.
Так можно, только бОльшие дизъюнкции всё-таки выражаются через меньшие, получается цепочка вложенных друг в друга классов.
Классы похожие на мои получаются (только из монотонных функций).

CokpaT

Ну да, вложенные...
для каждого натурального k рассмотрим множество всех функций f таких, что для любых наборов x1,...,xk таких, что f(x1)=...=f(xk)=1, имеет место x1&...&xk != (0,0,...,0).
По-моему, каждый такой класс замкнут и все они различны.

а твой пример я, честно говоря, не поняла. Что за функции? От k переменных или нет? x_1,...x_k - это наборы? Или это компоненты наборов? И что тогда за условия?
простого доказательства нет, есть теорема Поста. Но 10 лекций на нее как-то много

Dallas

а твой пример я, честно говоря, не поняла. Что за функции? От k переменных или нет? x_1,...x_k - это наборы? Или это компоненты наборов? И что тогда за условия?
x1,...,xk - наборы, & - конъюнкция наборов (почленная). Функции от любого числа переменных.
простого доказательства нет, есть теорема Поста. Но 10 лекций на нее как-то много
Насколько я помню, эта теорема доказывается полным перечислением классов и доказательством, что других нет. А классы там очень разнообразные. Короче, работа огромная.

CokpaT

сходу мне кажется, что твой пример - это вариации на тему семейств O^m и I^m.
кстати, вроде бы счетных семейств не вложенных классов в P_2 не бывает.

serengeti

вот еще одна задачка из экзаменационного билета:
4. пусть f(x g(x) из P_2(n)? f \ne g и degf(x degg(x) не больше k. показать, что
\sum_{x \in {0,1}^n} (f(x) \oplus g(x \ge 2^{n-k}
дошел до того, что в скобках в сумме в принципе стоит одна функция. т.е. мне кажется, что суммой
только запутать хотят. а во-вторых, надо раскрутить индукцию. с базой порядок, но вот переход мне
как-то не дался пока может, кто подскажет направление, плиз?

serengeti

и то, что досталось мне 8го, на что Угольников сказал "это же даже не университетская, это школьная математика":
5. (задача 12) посчитать количество булевых функций в P_2(3 существенно зависящих от всех своих
переменных я сделал это по форуме включений/исключений. решение мое лектор принял, но несколько
повозмущался, что сложным приемом решил задачу. как можно проще? решив своим, другое решение уже
трудно найти

CokpaT

4. пусть f(x g(x) из P_2(n)? f \ne g и degf(x degg(x) не больше k. показать, что
\sum_{x \in {0,1}^n} (f(x) \oplus g(x \ge 2^{n-k}
напиши словами лучше, что там за сумма, и, кстати, что понимается под степенью.

serengeti

как я понял, это степень полинома Жегалкина, т.е. максимльный ранг элементарной конъюнкции
сумма по всем элементам x из B^n суммы по модулю 2 f(x) и g(x) больше или равна 2 в степени n-k

Dallas

сходу мне кажется, что твой пример - это вариации на тему семейств O^m и I^m.
это не вариации, это они и есть (одно из семейств, не помню какое)
кстати, вроде бы счетных семейств не вложенных классов в P_2 не бывает.
попарно невложенных реально не бывает

neemah86

4. пусть f(x g(x) из P_2(n)? f \ne g и degf(x degg(x) не больше k. показать, что
 \sum_{x \in {0,1}^n} (f(x) \oplus g(x \ge 2^{n-k}
Если я правильно понял условие, то все почти очевидно.
h(x)=f(x)+g(x известно что h(x)!=0 и degh(x)=<k, надо доказать, что wt(h(x>=2^(n-k)
 Известно, что wt(f(x>= 2^(n- degf(x отсюда все и следует.
На всякий случай напишу, как это доказывается:
Выбираем самый длинный моном в полиноме функции(их может быть несколько -надо выбрать один). Вместо переменных, не входящих в этот моном подставляем всевозможные наборы из 0 и 1(всего 2^(n- degf(x ). Получем 2^(n- degf(x различных функций от degf(x) переменных. Все они ненулевые, т.к. в каждой есть как минимум наш исходный моном, следовательно, каждая хоть на одном наборе равна 1. Получаем, что есть как минимум 2^(n- degf(x наборов, на которых исходная функция f(x) равна 1.

serengeti

спасибо большое заодно про понятие веса вспомнил )
кстати, мне давали еще такую задачку про вес на первом экзамене. сейчас вижу, что много облегченный
вариант, чтобы проверить вообще общую сообразительность:
дана функция f(x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,x12) =
= x1 + x2x3 + x2x4x5 + x4x6 + x7x8x9 + x8x10 + x7x9 + x8x9x10x11x12
найти ее вес?
я долго тупил, потом увидел, что x1 входит только в одну конъюнкцию, после чего стало понятно, что вес
функции 2^{2^n-1}. действительно, на наборах, отличающихся в первой компоненте функция принимает
различные значения, т.е. наборов, на которых функция будет принимать 1 и на которых 0, поровну

anteijant

А задачку на экзамене обязательно надо решить? хоть 3ку могут без задачи поставить?

kolyan

что, совсем ни одной задачи хочешь не решить?

anteijant

да не, просто боюсь что вдруг не решу, а тут какбы слухи ходят что до 20го надо обязательно закрыться, ато выгонят..

kolyan

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

anteijant

спасибо за инфу, просто я ещё ниразу не сдавала дискру, вот и боюсь..

gosha_vis

до 1-го марта кажется, если не был на комиссии в январе.

anteijant

а если быда на комиссии в январе и дали строгач за 4 долга, но к отчислению не представляли?
я знаю, что дали сдавать до 20 тем кого представили. а что с остальными?

serengeti

други, выручайте, плиз. по материалам семинаров Чашкина с дмвн:
почему любые два столбца проверочной матрицы кода с кодовым расстоянием 3 (исправляет 1 ошибку)
должны быть линейно независимы?
толи поздно уже, толи я не достоин тройки по дискре
апд: отбой это в лекциях было
Оставить комментарий
Имя или ник:
Комментарий: