Составить базис всех монотонных булевых функций

задан 26 Янв '16 20:24

{0,1,xVy,xy}

Это всё "перепевы" на тему того, что всякая монотонная функция представима в виде ДНФ без отрицаний. Базисность доказывается просто: если выбросить 0, то мы его уже не выразим. То же для 1. Ясно также, что если выбросить дизъюнкцию, то выразимыми окажутся только константы и конъюнкции нескольких переменных. Для конъюнкции -- аналогично.

Вообще, этот вопрос когда-то на форуме уже был. При желании, можно было бы даже ссылку поискать.

(26 Янв '16 21:10) falcao
10|600 символов нужно символов осталось
1

$%\{0,1,x\lor y,xy\}$%

Это всё "перепевы" на тему того, что всякая монотонная функция представима в виде ДНФ без отрицаний. Базисность доказывается просто: если выбросить 0, то мы его уже не выразим. То же для 1. Ясно также, что если выбросить дизъюнкцию, то выразимыми окажутся только константы и конъюнкции нескольких переменных. Для конъюнкции -- аналогично.

Вообще, этот вопрос когда-то на форуме уже был. При желании, можно было бы даже ссылку поискать.

P.S. Здесь была задача о нахождении базисов каждого из пяти предполных классов. Эта ссылка может в дальнейшем пригодиться.

ссылка

отвечен 26 Янв '16 21:15

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

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

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

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

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

отмечен:

×179

задан
26 Янв '16 20:24

показан
1215 раз

обновлен
26 Янв '16 21:15

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

по почте:

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

по RSS:

Ответы

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

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