Даны две функции f1(x y) f2(x y z)

А) функция f1x,y=x∼y→x
Составим таблицу истинности.
x
y
y→x
f1x,y
0 0 1 0
0 1 0 1
1 0 1 1
1 1 1 1
Найдем полином Жегалкина.
Px,y=a0+a1x+a2y+a3xy
P0,0=0=a0→a0=0
P0,1=1=a0+a2=0+a2→a2=1
P1,0=1=a0+a1=0+a1→a1=1
P1,1=1=a0+a1+a2+a3=0+1+1+a3→a3=1
P=x+y+xy
Составим СДНФ по наборам, на которых fx,y=1
f1x,y=xy∨xy∨xy
Упростим СДНФ, используя склеивание по «y»
xy∨xy∨xy=xy∨x
Составим СКНФ по наборам, на которых fx,y=0
f1=x∨y
б) функция f2x,y,z=x+y↓xz
Составим таблицу истинности.
x
y
z
x+y
x|z
f2x,y,z
0 0 0 0 1 0
0 0 1 0 1 0
0 1 0 1 1 0
0 1 1 1 1 0
1 0 0 1 1 0
1 0 1 1 0 0
1 1 0 0 1 0
1 1 1 0 0 1
Найдем полином Жегалкина.
Px,y,z=a0+a1x+a2y+a3z+a4xy+a5xz+a6yz+a7xyz
P0,0,0=0=a0→a0=0
P0,0,1=0=a0+a3=0+a3→a3=0
P0,1,0=0=a0+a2=0+a2→a2=0
P0,1,1=0=a0+a2+a3+a6=0+0+0+a6→a6=0
P1,0,0=0=a0+a1=0+a1→a1=0
P1,0,1=0=a0+a1+a3+a5=0+0+0+a5→a5=0
P1,1,0=0=a0+a1+a2+a4=0+0+0+a4→a4=0
P1,1,1=1=a0+a1+a2+a3+a4+a5+a6+a7=0+0+0+0+0+0+0+a7→a7=1
Px,y,z=xyz
Составим СДНФ по наборам, на которых fx,y=1
f1x,y,z=xyz
Составим СКНФ по наборам, на которых fx,y=0
f1=x∨y∨zx∨y∨zx∨y∨zx∨y∨zx∨y∨zx∨y∨zx∨y∨z
Заполним карту Карно
x\yz
00 01 11 10
0 0 0 0 0
1 0 0 1 0
МДНФ: xyz
РКС:
в) таблица Поста имеет вид:
x\yz
T0
T1
L
S
M
f1
+ + - - +
f2
+ + - - +
Для того, чтобы система функций была полна, необходимо и достаточно, чтобы она содержала:
Хотя бы одну функцию, не сохраняющую ноль: T0→f0,0,…,0=0
Хотя бы одну функцию, не сохраняющую единицу: T1→f1,1,…,1=1
Хотя бы одну несамодвойственную функцию: S→fx1,…,xn=fx1,…,xn
Хотя бы одну нелинейную функцию: L→функции, у которых полином Жегалкина
не содержит конъюнкций переменных, т.е