Даны функции f и w. fx1,x2,x3=x1∨x2∨x3∨x3⇒x1~x2↓x3wx1,x2,x3=1,0,0,1,0,1,1,0 а) Вычислить таблицу значений функции f. б) Найти минимальные

Даны функции f и w. fx1,x2,x3=x1∨x2∨x3∨x3⇒x1~x2↓x3wx1,x2,x3=1,0,0,1,0,1,1,0 а) Вычислить таблицу значений функции f. б) Найти минимальные ДНФ функции f и w. в) Выяснить полноту системы f,w. Если система неполна, дополнить систему функцией g до полной системы. г) Из функциональных элементов, реализующих функции полной системы f,w или f,w, g, построить функциональные элементы, реализующие базовые функции ∨,∧,,0, 1.

А) Вычислить таблицу значений функции f.
x1
x2
x3
x1
x2
x3
x3⇒x1
x2↓x3
x2↓x3
x1∨x2∨x3∨x3⇒x1
f
0 0 0 1 1 1 1 1 0 1 0
0 0 1 1 1 0 1 1 0 1 0
0 1 0 1 0 1 1 1 0 1 0
0 1 1 1 0 0 1 0 1 1 1
1 0 0 0 1 1 0 1 0 1 0
1 0 1 0 1 0 1 1 0 1 0
1 1 0 0 0 1 0 1 0 1 0
1 1 1 0 0 0 1 0 1 1 1
б) Найти минимальные ДНФ функции f и w.
fСДНФ=x1x2x3∨x1x2x3
fМДНФ=x2x3
wx1,x2,x3=1,0,0,1,0,1,1,0
wСДНФ=x1 x2 x3∨x1x2x3∨x1x2x3∨x1x2x3
wМДНФ=x1 x2 x3∨x1x2x3∨x1x2x3∨x1x2x3
в) Выяснить полноту системы f,w. Если система неполна, дополнить систему функцией g до полной системы.
x1
x2
x3
f
w
0 0 0 0 1
0 0 1 0 0
0 1 0 0 0
0 1 1 1 1
1 0 0 0 0
1 0 1 0 1
1 1 0 0 1
1 1 1 1 0
Воспользуемся критерием Поста. Проверим каждую из этих функций на принадлежность к замкнутым классам P0, P1 , L, S, M.
1) P0 - класс функий, сохраняющих нуль (т.е если F(0,0,...,0)=0, то F принадлежит этому классу)

. Проверяем
f0,0,0=0 – принадлежит классу P0
w0,0,0=1 – не принадлежит классу P0
2) P1 - класс функций, сохраняющих единицу (т.е если F(1,1,...,1)=1, тоF принадлежит этому классу).
f1,1,1=1 – принадлежит классу P1
w1,1,1=0 – не принадлежит классу P1
3) L-класс функций, представимых линейным многочленом Жегалкина.
f=x2x3 – нелинейная
w=x1+1x2+1x3+1+x1+1x2x3+x1x2+1x3∨x1x2x3+1==x1x2x3+x1x2+x1x3+x2x3+x1+x2+x3+1+x1x2x3+x2x3+x1x2x3+x1x3++x1x2x3+x1x2=x1+x2+x3+1
w=x1⨁x2⨁x3⨁1 – Получился линейный многочлен, значит, функция принадлежит классу L
4) S - класс самодвойственных функций. То есть функций, для которых выполняется:
f(x1,x2,...,xn)=¬f(¬x1,¬x2,...,¬xn)
Самодвойственность проще всего определять по таблице значений функции