Для булевой функции, заданной вектором значений (10100110), определить:
1) существенные и фиктивные переменные;
2) совершенную дизъюнктивную нормальную форму;
3) совершенную конъюнктивную нормальную форму;
4) полином Жегалкина двумя способами;
5) принадлежность классам T0,T1, S, M, L
Дано: функция f(x, y,z)=(10100110)
Найти.
1) существенные и фиктивные переменные;
2) совершенную дизъюнктивную нормальную форму;
3) совершенную конъюнктивную нормальную форму;
4) полином Жегалкина двумя способами;
5) принадлежность классам T0,T1, S, M, L
Решение
Для определения существенных и фиктивных переменных построим таблицу истинности для данной функции:
x y z f (x, y, z)
0 0 0 1
0 0 1 0
0 1 0 1
0 1 1 0
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 0
Из таблицы истинности видно, что переменная x – является существенной переменной, так как выполняется условие:
f (0, y, z) ≠ f (1, y, z).
Исследуем переменную y: f (x, 0, z) ≠ f (x, 1, z), то есть значения функции при y=0 и y=1 также не совпадают, тогда y- существенная переменная.
Исследуем переменную z: f (x, y, 0) ≠ f (x, y, 1), то есть значения функции при z=0 и z=1 также не совпадают, тогда z- существенная переменная. Фиктивных переменных нет.
Используя таблицу истинности, найдем наборы, на которых функция принимает истинные значения:
{0,0,0}, {0,1,0}, {1,0,1}, {1,1,0} Этим наборам поставим в соответствие элементарные конъюнкции по всем переменным. Переменная со значением ноль будет записана со знаком отрицания:
Получим:
{0,0,0} ⟶x y z
{0,1,0} ⟶x y z
{1,0,1} ⟶x y z
{1,1,0}⟶x y z Эти конъюнкции объединим с помощью дизъюнкции:
x y z ⋁x y z ⋁x y z ⋁ x y z -Это Совершенная дизъюнктивная нормальная форма для данной функции.
3) Используя таблицу истинности, найдем наборы, на которых функция принимает ложные значения:
{0,0,1}, {0,1,1}, {1,0,0}, {1,1,1}Этим наборам поставим в соответствие элементарные дизъюнкции
. Переменная, которая принимает значение 1 будет записана с отрицанием:
Получим
{0,0,1} ⟶x⋁ y ⋁z
{0,1,1} ⟶x⋁ y⋁ z
{1,0,0} ⟶x ⋁y ⋁z
{1,1,1}⟶ x ⋁y ⋁z Объединим дизъюнкции с помощью конъюнкции:
(x⋁ y ⋁z) ⋀ (x⋁ y⋁ z)⋀( x ⋁y ⋁z)⋀(x ⋁y ⋁z) -Это совершенная конъюктивная нормальная форма для данной функции.
4)Используя таблицу истинности, построим полином Жегалкина методом треугольника:
1.Строим полную таблицу истинности, в которой строки идут в порядке возрастания двоичных кодов от 000…00 до 111…11
2.Строим вспомогательную треугольную таблицу, в которой первый столбец совпадает со столбцом значений функции в таблице истинности.
Ячейка в каждом последующем столбце получается путём сложения по модулю 2 двух ячеек предыдущего столбца — стоящей в той же строке и строкой ниже.
Столбцы вспомогательной таблицы нумеруются двоичными кодами в том же порядке, что и строки таблицы истинности.
Каждому двоичному коду ставится в соответствие один из членов полинома Жегалкина в зависимости от позиций кода, в которых стоят единицы. Если в верхней строке какого-либо столбца стоит единица, то соответствующий член присутствует в полиноме Жегалкина.
Строим таблицу истинности:
x y z f (x, y, z)
0 0 0 1
0 0 1 0
0 1 0 1
0 1 1 0
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 0
Строим вспомогательную таблицу:
000 001 010 011 100 101 110 111
1 z y yz x xz xy xyz
1 1 0 0 1 0 1 0
0 1 0 1 1 1 1
1 1 1 0 0 0
0 0 1 0 0
0 1 1 0
1 0 1
1 1
0
Выделим единицы, стоящие в верхних столбцах, и получим:
1+x+z+xy – Полином Жегалкина.
Построим полином Жегалкина методом неопределённых коэффициентов:
Для этого
Запишем данную функцию в виде полинома Жегалкина с неопределёнными коэффициентами:
f(x,y,z) = a000 +a100x +a010y + a001z + a110x y + a101x z +a011y z + a111x y z
(0,0,0) = a000 = 1 ⇒ a000 = 1
f(1,0,0) = a000 + a100 = 1 + a100 = 0 ⇒ a100 = 1
f(0,1,0) = a000 + a010 = 1 + a010 = 1 ⇒ a010 = 0
f(0,0,1) = a000 + a001 = 1 + a001 = 0 ⇒ a001 = 1
f(1,1,0) = a000 + a100 + a010 +a110 = 1 + 1 + 0 + a110 = 1 ⇒ a110 = 1
f(1,0,1) = a000 + a100 + a001 + a101 = 1 + 1 + 1 + a101 = 1 ⇒ a101 = 0
f(0,1,1) = a000 + a010 + a001 + a011 = 1 + 0 + 1 + a011 = 0 ⇒ a011 = 0
Далее вычислим полученные значения, поставив в функцию.
f(1,1,1) = a000 + a100 + a010 + a001 + a110 + a101 + a011 + a111 = 1 +1 + 0 +1 +1+ 0 +0 +a111 = 0 ⇒ a111 = 0
Выбираем значения с единицей, тогда получим полином Жегалкина:
a000 = 1, a100 = 1, a001 = 1, a110 = 1 то есть
1+x+z+xy
5) Определим принадлежность функции к классам:
1
Задать вопрос
на новый заказ в Автор24.
