Опять дискретка(((, Специальные классы ф.а.л. Опции

[Айра]

Привет!
Не могли бы вы,пожалуйста, объяснить как решать эти задания:

1. Найти мощность множества:
(L\(SU(T₁∩T₀)))U(T₀\(S∩L))\(M∩(LU(S\T₁)))

2. Проверить полноту множества функций:
(S\(LU(M∩(T₀UT₁)))U(S∩(L\(T₀UT₁))U(M∩(L\S))

Заранее спасибо!))

[Atos]

2. Доказательство полноты множества:
1) Множество не содержится в S, так как существует l из L, такое, что l не принадлежит MUS -> (M∩(L\S)) не содержится в S
2) Множество не содержится в LUM, так как существует s из S, такое, что s не принадлежит LUM -> (S\(LU(M∩(T0UT1))) не содержится в LUM
3) Множество не содержится в T0UT1, так как существует l из L, такое, что l не принадлежит SU(T0UT1) -> (S∩(L\(T0UT1)) не содержится в T0UT1

Сообщение отредактировано: Atos - 22.12.2007 19:15

[Айра]

Спасибо! Буду разбираться))
Я понимаю, что для доказательства полноты множества, нужно доказать, что оно целиком не содержиться не в одном из специальных классов, но как-то на практике это сделать не получалось..

Если что, ждите глупых вопросов))

[Айра]

Кто-нибудь знает, какова мощность таких множеств:
1. t1∩M
2. t0∩M
3. t0∩t1∩M
4. t0∩S∩L∩M

Короче все дело в M.. препод говорил, что с ней будут проблемы, вот я их и встретила(((

И еще, проверить полноту:
(S∩(T0\L))U(M\(T0UL))
а, здесь не получится так, что раз и в первой и во второй части множества не функций из L, то множество будет неполным..

[Lapp]

Если что, ждите глупых вопросов))

И ты тоже.

Мне, наверное, вообще не следовало бы вступать в разговор о высших материях, которых я не понимаю, но любопытство - мой главный порок.. Айра, я понимаю, что твоя занятость во время зачетной сессии превышает все разумные границы, но вдруг у тебя найдется время для неучей вроде меня расшифровать таинственную аббревиатуру "ф.а.л." и пояснить, что в данном случае ты обозначила буковками с циферками: t0, t1, M... На всякий случай: я честно выполнил требования Форума и использовал поиск (как по Форуму, так и в Инете) - увы, безрезультатно.. Общепринятых сокращений "ф.а.л.", как оказалось, не существует, а на буковки t, s и m нашлось столько всего, что ни осмыслить, ни привести это тут я просто не в состоянии.. А посему, обращаюсь к тебе за помощью - не вели казнить, вели миловать. Я всего лишь хочу знать, о чем, собственно, речь..

Я понимаю, что рискую своей репутацией, но не могу противостоять желанию узнать истину - которая, по-видимому, известна всем, кроме меня... Спасибо.

PS
Если в лом расшифровывать - ткни в ссылку..

[Atos]

Если в лом расшифровывать - ткни в ссылку..

http://ru.wikipedia.org/wiki/%D0%9A%D1%80%...%81%D1%82%D0%B0

(S∩(T0\L))U(M\(T0UL)) = (SUM)∩(T0\L)) содержится в T0\L содержится в T0 -> неполно

А вот вопрос про мощность чё-то ставит меня в тупик Эти классы функций - они же все имеют бесконечную мощность

[Lapp]

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

Что касается мощности, то, мне кажется, нужно учесть , что разность или пересечение двух бесконечных множеств может быть конечной(-ным) или даже пустой(-ым). Насколько я понимаю, мощность не может превзойти счетную (как счетное объединение конечных множеств) - то есть в ответе либо число (включая ноль), либо алеф-ноль. Надо чуть побольше покрутить в мозгах эти классы, чтоб представить, как они пересекаются..

[Atos]

Что касается мощности, то, мне кажется, нужно учесть , что разность или пересечение двух бесконечных множеств может быть конечной(-ным) или даже пустой(-ым). Насколько я понимаю, мощность не может превзойти счетную (как счетное объединение конечных множеств) - то есть в ответе либо число (включая ноль), либо алеф-ноль. Надо чуть побольше покрутить в мозгах эти классы, чтоб представить, как они пересекаются..

Уже множество t0∩M бесконечно, так как включает в себя функции вида x1, x1Ux2, x1Ux2Ux3...
Может, имеется в виду мощность как функция от числе переменных?

[Айра]

Может, имеется в виду мощность как функция от числе переменных?

хм.. ну похоже, что так.. например T0 имеет мощность 2^{(2^n)-1}..

Я поняла так, что в этом задании надо попытаться разбить множество по формулам на более мелкие части и найти их мощность.. Я пробовала, но у меня либо слишком запутанно получалось, либо в конце оставались множества с М, а для таких у меня мощности нет.. Сегодня препод сказал, что можно разбивать не только по формулам, но и строить диаграммы Венна и по ним уже приводить множество к сумме и\или разности пересечений.. буду пробовать..

по поводу второго: дело в том, что нам надо указывать функции из этого множества (строим табличку и в нее вписываем), которые не входят в T0,T1 и т.д. А я могу, по идее, опять построить диаграмму и по ней смотреть? например, вот в этом кусочке есть функция, лежащая в t1, но не лежащая в t0, тогда я вписываю эту функцию напротив t0 и т.д. и т.п...

to Lapp: сорри я как-то не подумала.. сейчас ты уже разобрался?

Сообщение отредактировано: Айра - 28.12.2007 2:14

[Lapp]

сейчас ты уже разобрался?

Скажем так: начал разбираться, за что большое спасибо тебе и Атосу . Забавная наука.
Но смысл таинственных букв "ф.а.л." по-прежнему за завесой мрака неизвестности..

[Айра]

Функции алгебры логики)))

[Atos]

про мощность класса монотонных функций смотри в Новикове http://www.proklondike.com/contentview.php?content=231
раздел Комбинаторики, если не ошибаюсь, числа Стирлинга

[Айра]

У меня такой учебник, только 2-е издание.. как-то я от него помощи не ощущаю, а вот привеленные там программи порой ввергают в ужас.. бррр..

Кстати, я ж всетаки более менее разобралась с этими задачами, если интересно, то вот примерный план "разборки":

2. Пришлось рисовать диаграмму Венна для 5-ти множеств (какая же каракуля получилась))), а потом из имеющихся кусочков выбирать функции не входящие в спец. классы.. в роли части функции выступили, так сказать, стандартные ф-ции, а одну пришлось придумать..

1. Сначала тоже попробовала через диаграмму - не айс, рисовать очень муторно и не посчитать пересечения с монотонными. Потом дошло, вот, например, тут ("всякая гадость, но без М"...((M\(T1UT0)\L)) получается так:
монотонные\T1 - это уйдут все функции, у которых на наборе (1..1) значение равно 1, значит, т.к. (1..1) сравним со всеми остальными наборами переменных, останутся только ф-ции с результатом 0 на последнем наборе, а значит и с 0-м на первом наборе, что входит в T0.. значит M\(T1UT0) = пустому множеству, дальше тоже пустота.. Тогда общая картинка изначального множества упрощается, заштриховывается на диаграмме и приводится к суммам\разностям пересечений..
Так что сначала надо было поразмыслить над монотонными: они либо полность уходят, либо поддаются перечислению на пальцах))
Как-то так..

..мне в предпоследний день повезло - достались более-менее понятные условия задач, поэтому я их сделалась и "сдалась" ) Ура!