Даны функции f (таблица 2) и w (таблица 3). а) Вычислить таблицу значений f. б) Найти

Даны функции f (таблица 2) и w (таблица 3). а) Вычислить таблицу значений f. б) Найти минимальные ДНФ функций f и w. в) Выяснить полноту системы {f,w}. Если система не полна, дополнить систему функцией g до полной системы. Указание. Запрещается дополнять систему константами, отрицанием и базовыми функциями двух переменных (⊕, ⋁, ⋀, |, ↓ и т.д.) Не допускается дополнение функцией, образующей с f или w полную подсистему, кроме случаев, когда иное невозможно. г) Из функциональных элементов, реализующих функции полной системы {f,w} или {f,w,g}, построить функциональные элементы, реализующие базовые функции {⋁, ⋀, ⌐, 0, 1}. fx1,x2,x3=x1x2x3⋁x2⋁x3→x1⊕x3. wx1,x2,x3=0,1,0,1,0,1,0,0.

А) Строим таблицу истинности функции f.
fx1,x2,x3=x1x2x3⋁x2⋁x3→x1⊕x3.
x1 x2 x3 A=x1x2x3
B=A⋁x2⋁x3
x1⊕x3
f w
0 0 0 0 1 0 0 0
0 0 1 0 1 1 1 1
0 1 0 0 1 0 0 0
0 1 1 0 0 1 1 1
1 0 0 0 1 1 1 0
1 0 1 1 1 0 0 1
1 1 0 0 1 1 1 0
1 1 1 0 0 0 1 0
б) Находим минимальные ДНФ функций f и w. Строим карты Карно.
x1\x2x3 31496019240500 01 -6731019431011 10
0 0 1 1 0
665480165101 1 0 1 -46990165101
fx1,x2,x3min=x1x4⋁x1x3⋁x2x3.
Находим теперь минимальную ДНФ функции
wx1,x2,x3=(0,1,0,1,0,1,0,0)
x1\x2x3 00 01 11 10
0 314960825531496082550 1 1 0
1 0 1 0 0
wx1,x2,x3min=x1x3⋁x2x3
в) Исследуем принадлежность функций f и w к основным классам булевых функций.
Функция f:
сохраняет константу 0, так как f(0,0,0)=0;
сохраняет константу 1, так как f(1,1,1)=1;
не монотонна, так как, например, f(0,0,1)>f(1,0,1);
не самодвойственная, так как
(0,1,0,1,1,0,1,1)→(1,1,0,1,1,0,1,0)→(0,0,1,0,0,1,0,1),
т.е

. переворот вектора истинности на 1800 и его инвертирования не приводит к получению исходного вектора;
Выясним вопрос о принадлежности функции f к линейным функциям. Для этого найдем полином Жегалкина методом треугольника.
x1 x2 x3
0 0 0 0 1 0 1 1 0 1 1
0 0 1 1 1 1 0 1 1 0
0 1 0 0 0 1 1 0 1
0 1 1 0 1 0 1 1
1 0 0 1 1 1 0
1 0 1 0 0 1
1 1 0 0 1
1 1 1 1
Таким образом, полином Жегалкина имеет вид:
fx1,x2,x3=x1⊕x3⊕x1x2x3.
Т.е