Найти функцию f такую, что { 0, 1, f } - базис класса всех булевых функций

задан 7 Апр 16:29

из штриха Шеффера или стрелки Пирса, вроде как, выводятся все остальные булевы функции

(7 Апр 17:01) haosfortum

@haosfortum: это будет полная система, но не базис. Под базисом чаще всего понимают такую полную систему, из которой нельзя удалить ни одну из функций.

(7 Апр 17:21) falcao
10|600 символов нужно символов осталось
0

Чтобы система оказалась полной, необходимо и достаточно, чтобы f была нелинейной и немонотонной. Если она не принадлежит T0, то функцию 1 можно убрать, не нарушая свойство полноты. Аналогично, если f не принадлежит T1, то можно убрать 0. Таким образом, f должна быть и в T0, и в T1, чтобы получился базис.

Среди функций двух переменных, все такие функции монотонны. Для функций трёх переменных годится пример f(x,y,z)=x+xy+xyz. Она сохраняет 0 и 1, и нелинейна. На наборе 110 функция равна 0, а на 100 она равна 1, поэтому f не монотонна.

ссылка

отвечен 7 Апр 17:36

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

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

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

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

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

отмечен:

×1,699

задан
7 Апр 16:29

показан
34 раза

обновлен
7 Апр 17:36

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

по почте:

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

по RSS:

Ответы

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

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