|
Здравствуйте! Сведением к заведомо полным системам в $%P_2$% необходимо показать, что множество $%A$% является полной системой в $%P_2$%. $$A = \{x \sim y, x \ xor \ y, xy \ xor \ z\}$$ задан 20 Сен '15 6:22 
Math_2012 |
|
Первые две функции -- это $%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 @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
|