Приведите пример функции, которая сама по себе не образует полный класс, а вместе с f( x, y, z) = x \/ yz образует, и почему так? к ней найти все функции двух переменных (или доказать что их нет).

задан 16 Янв '18 3:58

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

Функция f сохраняет 0 и 1, являясь монотонной, так как выражается через конъюнкцию и дизъюнкцию. При этом она не линейна, и на наборах 011, 100 принимает одинаковые значения, поэтому она не самодвойственна. Чтобы вместе с какой-то функцией g получилась полная система {f,g}, добавляемая функция g должна не принадлежать ни T0, ни T1, а также не быть монотонной. Такое условие на g необходимо и достаточно по критерию Поста. Для функций g(x,y) двух переменных имеем g(0,0)=1, g(1,1)=0, откуда вытекает немонотонность. Но у нас есть ещё условие, что g сама полную систему не образует, то есть она какому-то из предполных классов принадлежит. Это может быть L или S. Линейность означает, что g(x,y)=1+ax+by, где a+b=1. Тогда g есть отрицание одной из переменных, то есть x+1 или y+1. Тем самым, получается два примера.

Самодвойственная функция с такими свойствами задаётся одним из двух векторов: (1010) или (1100). Но это даёт в точности те две функции, которые мы только что рассмотрели.

ссылка

отвечен 16 Янв '18 9:01

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

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

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

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

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

отмечен:

×4,002
×1,109
×92

задан
16 Янв '18 3:58

показан
491 раз

обновлен
16 Янв '18 9:01

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

по почте:

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

по RSS:

Ответы

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

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