2014 dxdy logo

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

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




 
 Про конечность базиса замкнутого класса из P_2
Сообщение01.04.2011, 17:31 
Доказать, что если у замкнутого класса $K \subseteq P_2$ существует конечный базис, то всякий базис этого класса конечен.

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

Предположим, что у $K$ есть как конечный, так и бесконечный базис. Тогда с помощью бесконечного базиса можно получить конечный базис (т.е. бесконечный базис является базисом для конечного базиса). А так как в бесконечном базисе существует функция, существенно зависящая от бесконечно большого числа переменных, то в силу того, что замыкание бесконечного базиса есть конечный базис (по предположению, что бесконечный базис есть базис для конечного базиса), эта функция от бесконечного числа аргументов должна быть в конечном базисе, что противоречит определению конечного базиса. Следовательно, утверждение верно.

Верны ли рассуждения? Верно ли доказательство? Если есть ошибки, то в чем?
Заранее благодарен.

 
 
 
 
Сообщение01.04.2011, 18:22 
Аватара пользователя
_nobody в сообщении #430004 писал(а):
Базис класса булевых функций называется бесконечным, если в нем существует функция, существенно зависящая от бесконечно большого числа переменных.
Откуда Вы взяли это определение? таких функций во всем $P_2$ нет.

 
 
 
 
Сообщение01.04.2011, 18:34 
Xaositect,
Отсюда (см. по фразе "Базис называется бесконечным"), дословно:
Базис называется бесконечным, если содержит функции, существенно зависящие от сколь угодно большого числа переменных (плюс там еще определение в полуматематическом формате).
Других определений не нашел сего понятия.
Что же тогда такое конечный и неконечный базисы?
Задача из Гаврилов Г.П. Сапоженко А.А. Задачи и упражнения по дискретной математике. 2005 год (стр. 64, №1.20).

 
 
 
 
Сообщение01.04.2011, 18:46 
Аватара пользователя
_nobody в сообщении #430004 писал(а):
Базис класса булевых функций называется бесконечным, если в нем существует функция, существенно зависящая от бесконечно большого числа переменных.

_nobody в сообщении #430032 писал(а):
Базис называется бесконечным, если содержит функции, существенно зависящие от сколь угодно большого числа переменных (плюс там еще определение в полуматематическом формате).

Сравните и поймите разницу.
Вообще, все значительно проще - базис бесконечен, если он содержит бесконечное количество элементов.

В данном случае также существенно, что базис - это неизбыточная система функций, порождающая некоторый класс, т.е. из нее нельзя выкинуть никакую из функций (см. определение базиса в Гаврилове-Сапоженко, начало главы II).
Предположите, что существует бесконечный базис и конечный базис и выделите из бесконечного базиса функции, которые можно убрать без вреда для замыкания.

 
 
 
 
Сообщение01.04.2011, 19:00 
Цитата:
Сравните и поймите разницу.

Не вижу никакой смысловой разницы.
Про определение самого базиса в курсе, в данном же определении говорится, что базис бесконечный — это базис... и т.д.

Или бесконечен тот базис, в котором ВСЕ функции существенно зависят от бесконечно большого числа аргументов? По-моему, нет.

Цитата:
выделите из бесконечного базиса функции, которые можно убрать без вреда для замыкания.

Каким образом? Не понимаю, как можно выбрать функцию из базиса, если они там могут быть любыми (за исключением того, что дополнительно есть функции, существенно зависящие от сколь угодно большого числа аргументов).

Цитата:
Вообще, все значительно проще - базис бесконечен, если он содержит бесконечное количество элементов.

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

Так, с учетом этого. Тогда разве при отбрасывании конечного числа функций из бесконечного базиса он не останется бесконечным? Как связать конечный и бесконечный базисы?

P.S. Так понимаю, первоначальное рассуждение совершенно неверно.

 
 
 
 
Сообщение01.04.2011, 22:01 
Функций, зависящих от бесконечно большого числа аргументов, не бывает. То есть бывают, конечно, но не рассматриваются в этой науке. В этой науке, тем не менее, встречаются функции, зависящие от сколь угодно большого конечного числа переменных.

-- Пт апр 01, 2011 22:07:24 --

(Оффтоп)

Xaositect в сообщении #430041 писал(а):
Вообще, все значительно проще - базис бесконечен, если он содержит бесконечное количество элементов.
Это, конечно, правильно, но тут возникают дурацкие тонкости с местным определением понятия "функция". Ну типа что $\{\bar x_1,\bar x_2,\bar x_3,\ldots\}$ - это некое бесконечное множество функций, которое бесконечным называть совсем не хочется. Так что приведенное в том учебнике определение педагогически достаточно меткое. Впрочем, Вы лучше меня это всё понимаете.

 
 
 [ Сообщений: 6 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group