В наборе функций φ1,…,φ6 указать (с полным обоснованием!) все минимальные по включению полные подсистемы.
Для одной из этих подсистем (на выбор) выразить все стандартные функции (т.е. 0, 1, x, xy, x∙y, x⊕y,x→y) через функции ээтой подсистемы и нарисовать соответствующие схемы из функциональных элементов.
Решение
Построим таблицы истинности для построенных функций φi.
x y z φ1
φ2
φ3
φ4
φ5
φ6
0 0 0 1 1 0 1 1 0
0 0 1 1 0 1 1 0 1
0 1 0 0 1 1 0 1 0
0 1 1 1 1 0 1 0 0
1 0 0 1 0 1 0 0 1
1 0 1 0 1 0 0 1 1
1 1 0 1 0 0 1 1 1
1 1 1 0 0 1 1 1 0
Выявляем принадлежность функций φi к основным классам булевых функций. Будем постепенно заполнять таблицу Поста.
T0 T1 M S L
φ1
─ ─ ─ ─ ─
φ2
─ ─ ─ ─ ─
φ3
+ + ─ + +
φ4
─ + ─ ─ ─
φ5
─ + ─ ─ ─
φ6
+ ─ ─ ─ ─
Здесь T0 - функции сохраняющие константу 0, т.е. φi0,0,0=0;
T1 - функции сохраняющие константу 1, т.е. φi1,1,1=1;
M - монотонные функции;
S - самодвойственные функции;
L - линейные функции.
Плюс в клеточке i-j означает, что φi принадлежит к классу j, а минус - не принадлежит.
Проверим на самодвойственность функцию φ1:
1101 1010→(01011011)→(10100100)
Первый вектор был записан с конца в начало и, затем, проинвертирован покомпонентно. Так как первый и последний векторы не совпадают, то функция φ1 не самодвойственная.
Найдем полином Жегалкина функции φ1 методом треугольника.
x y z φ1
0 0 0 1 1 1 0 1 1 0 1 0
0 0 1 1 0 1 1 0 1 1 1
0 1 0 0 1 0 1 1 0 0
0 1 1 1 1 1 0 1 0
1 0 0 1 0 1 1 1
1 0 1 0 1 0 0
1 1 0 1 1 0
1 1 1 0 1
Полином Жегалкина функции φ1 имеет вид:
φ1x,y,z=1⊕y⊕yz⊕xz⊕xy⊕xyz.
Т.о
. функция φ1 не линейна.
Находим принадлежность функции φ2 основным классам. Классам T0, T1, M функция не принадлежит.
101 10100→(00101101)→(11010010)
Функция φ2 не самодвойственная.
Строим полином Жегалкина.
x y z φ2
0 0 0 1 1 0 1 1 0 1 0 0
0 0 1 0 1 1 0 1 1 1 0
0 1 0 1 0 1 1 0 0 1
0 1 1 1 1 0 1 0 1
1 0 0 0 1 1 1 1
1 0 1 1 0 0 0
1 1 0 0 0 0
1 1 1 0 0
Имеем:
φ2x,y,z=1⊕z⊕yz⊕x.
Функция не линейная.
Функция φ3 принадлежит классам T0, T1 и не принадлежит классу М.
Проверяем на самодвойственность.
01101001→(10010110)→(01101001).
Функция самодвойственная.
Найдем полином Жегалкина.
x y z φ3
0 0 0 0 0 1 1 0 1 0 0 1
0 0 1 1 1 0 1 1 1 0 1
0 1 0 1 1 1 0 0 1 1
0 1 1 0 0 1 0 1 0
1 0 0 1 1 1 1 1
1 0 1 0 0 0 0
1 1 0 0 0 0
1 1 1 1 0
Имеем полином:
φ3x,y,z=z⊕y⊕x.
Функция линейна.
Рассмотрим функцию φ4=1 1010011;
Функция не сохраняет константу 0, сохраняет константу 1, не монотонна.
Проверяем на самодвойственность.
(11010011)→(11001011)→(00110100).
Не самодвойственная.
Проверяем на линейность
Задать вопрос
на новый заказ в Автор24.
