Здравствуйте! Сведением к заведомо полным системам в $%P_2$% необходимо показать, что множество $%A$% является полной системой в $%P_2$%.

$$A = \{x \sim y, x \ xor \ y, xy \ xor \ z\}$$

задан 20 Сен '15 6:22

изменен 20 Сен '15 6:24

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

Первые две функции -- это $%f(x,y)=x+y+1$% и $%g(x,y)=x+y$%. Тогда $%f(g(x,y),y)=x+1=\bar{x}$%, то есть отрицание выразимо. Третья функция есть $%h(x,y,z)=xy+z$%. Тогда $%h(x,\bar{y},x)=x\bar{y}+x=x(y+1)+x=xy$%, то есть конъюнкция также выразима. Система из отрицания и конъюнкции полна, откуда всё следует.

ссылка

отвечен 20 Сен '15 6:34

@falcao: Скажите, пожалуйста, а система {1, конъюнкция, xor} является полной?

(20 Сен '15 18:47) Math_2012

@Anna_2012: да, конечно. Это равносильно тому факту, что всякая функция представима полиномом. Доказательство тут очевидное: конъюнкция уже есть, а отрицание -- это x+1.

(20 Сен '15 18:50) falcao

@falcao: Я просто сначала пыталась свести к системе {1, конъюнкция, xor}, хотя xor уже есть, так что это, наверное, неправильно. :(

(20 Сен '15 18:59) Math_2012

@Anna_2012: а так тоже можно! Подставим x=y в первое, получим 1. Подставим x=y=1 во второе, получим 0. Потом z=0 в третье, получим конъюнкцию xy. Получается известная полная система. Этот способ ничем не хуже. То, что вторую функцию мы получаем "готовой", ничему не противоречит.

(20 Сен '15 19:21) falcao
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,087
×139

задан
20 Сен '15 6:22

показан
602 раза

обновлен
20 Сен '15 19:23

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

по почте:

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

по RSS:

Ответы

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

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