Доказать, что любой базис монотонных функций содержит не менее 3 и не более 4 функций

задан 18 Май 22:46

10|600 символов нужно символов осталось
2

Если в систему монотонных функций не входит 0, то она не порождает M, так как класс M \ {0} замкнут. Значит, в базис должны войти и 0, и 1 по аналогичной причине. Поскольку эти две функции M не порождают, базис состоит минимум из трёх функций.

Легко заметить, что система из 0, 1 и одной конъюнкции нескольких переменных не порождает M; аналогично для дизъюнкции. Значит, в базисе есть функция, являющаяся дизъюнкцией нескольких конъюнкций, а также функция, являющаяся конъюнкцией нескольких дизъюнкций. (Возможно, эти роли выполняет одна и та же функция.) Она может быть записана в такой форме, когда ни одна из элементарных конъюнкций не содержится в другой (для первого случая) ввиду законов поглощения. При этом она не должна стать дизъюнкцией переменных. Поэтому имеется конъюнкция нескольких переменных. Все не входящие в неё переменные обнуляем, подставляя вместо них 0, входящий в базис. Остаётся одна эта конъюнкция, а через неё выражается и xy. Аналогично, из соображений двойственности, выражается x V y, и тогда для порождения всего M хватает подсистемы не более чем из четырёх функций.

ссылка

отвечен 19 Май 2:33

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,036
×493

задан
18 Май 22:46

показан
69 раз

обновлен
19 Май 2:33

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru