Многочлен Жегалкина. Таблица истинности. Эквивалентность формул
Построить таблицы
соответствующих функций и выяснить, эквивалентны ли формулы и .
а)
Составим таблицу истинности для функции U:
|
x
|
y
|
z
|
отрицание
x
|
отрицание
у
|
дизъюк
ция
|
конъюнк
ция
|
имплика
ция
|
импликация
|
()
импликация
|
|
0
|
0
|
0
|
1
|
1
|
1
|
0
|
1
|
1
|
1
|
|
0
|
0
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
|
0
|
1
|
0
|
1
|
0
|
1
|
0
|
1
|
1
|
1
|
|
0
|
1
|
1
|
1
|
0
|
1
|
1
|
1
|
1
|
1
|
|
1
|
0
|
0
|
0
|
1
|
1
|
0
|
0
|
1
|
1
|
|
1
|
0
|
1
|
0
|
1
|
1
|
1
|
0
|
1
|
1
|
|
1
|
1
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
1
|
|
1
|
1
|
1
|
0
|
0
|
0
|
0
|
1
|
0
|
1
|
Мы получили формулу U(11111111).
Составим таблицу истинности для функции V:
|
x
|
y
|
z
|
импликация
|
отрицание
у
|
отрицание
x
|
импликация
|
импликация
|
|
0
|
0
|
0
|
1
|
1
|
1
|
1
|
1
|
|
0
|
0
|
1
|
1
|
1
|
1
|
1
|
1
|
|
0
|
1
|
0
|
1
|
0
|
1
|
1
|
1
|
|
0
|
1
|
1
|
1
|
0
|
1
|
1
|
1
|
|
1
|
0
|
0
|
0
|
1
|
0
|
0
|
1
|
|
1
|
0
|
1
|
0
|
1
|
0
|
0
|
1
|
|
1
|
1
|
0
|
1
|
0
|
0
|
1
|
1
|
|
1
|
1
|
1
|
1
|
0
|
0
|
1
|
1
|
Мы получили формулу V(11111111)
Сравнивая таблицы функций U и V,
видим, что U = V.
Значит, формулы U и V эквивалентны.
б)
Составим таблицу истинности для функции U:
|
x
|
y
|
z
|
отрицание
x
|
отрицание
у
|
конъюнкция
|
отрица
ние z
|
конъюнк
ция
|
имплика
ция
|
импликация
|
импликация
|
|
0
|
0
|
0
|
1
|
1
|
1
|
1
|
1
|
0
|
1
|
0
|
|
0
|
0
|
1
|
1
|
1
|
1
|
0
|
0
|
0
|
1
|
0
|
|
0
|
1
|
0
|
1
|
0
|
0
|
1
|
1
|
1
|
0
|
1
|
|
0
|
1
|
1
|
1
|
0
|
0
|
0
|
0
|
1
|
0
|
1
|
|
1
|
0
|
0
|
0
|
1
|
0
|
1
|
0
|
1
|
0
|
1
|
|
1
|
0
|
1
|
0
|
1
|
0
|
0
|
0
|
1
|
0
|
1
|
|
1
|
1
|
0
|
0
|
0
|
0
|
1
|
0
|
1
|
0
|
1
|
|
1
|
1
|
1
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
1
|
|
импликация
|
|
1
|
|
1
|
|
0
|
|
0
|
|
1
|
|
1
|
|
1
|
|
1
|
Мы получили формулу U(11001111).
Составим таблицу истинности для функции V:
|
x
|
y
|
z
|
отрицание z
|
импликация
|
конъюнкция
|
отрицание конъюнкции
|
|
0
|
0
|
0
|
1
|
1
|
0
|
1
|
|
0
|
0
|
1
|
0
|
1
|
0
|
1
|
|
0
|
1
|
0
|
1
|
1
|
0
|
1
|
|
0
|
1
|
1
|
0
|
0
|
0
|
1
|
|
1
|
0
|
0
|
1
|
1
|
1
|
0
|
|
1
|
0
|
1
|
0
|
1
|
1
|
0
|
|
1
|
1
|
0
|
1
|
1
|
1
|
0
|
|
1
|
1
|
1
|
0
|
0
|
0
|
1
|
Мы получили формулу V(11110001)
Сравнивая таблицы функций U и V,
видим, что U ¹ V.
Значит, формулы U и V неэквивалентны.
в)
Составим таблицу истинности для функции U:
|
x
|
y
|
z
|
отрицание
z
|
эквивалентность
|
импликация
|
импликация
|
отрицание
импликации
|
Сумма
по модулю 2
|
дизъюнкция
|
|
0
|
0
|
0
|
1
|
1
|
1
|
1
|
0
|
1
|
1
|
|
0
|
0
|
1
|
0
|
1
|
1
|
1
|
0
|
0
|
0
|
|
0
|
1
|
0
|
1
|
0
|
1
|
1
|
0
|
1
|
1
|
|
0
|
1
|
1
|
0
|
0
|
1
|
1
|
0
|
0
|
0
|
|
1
|
0
|
0
|
1
|
0
|
1
|
1
|
0
|
0
|
0
|
|
1
|
0
|
1
|
0
|
0
|
0
|
1
|
0
|
1
|
1
|
|
1
|
1
|
0
|
1
|
1
|
1
|
1
|
0
|
0
|
0
|
|
1
|
1
|
1
|
0
|
1
|
0
|
0
|
1
|
1
|
1
|
Мы получили формулу
U(10100101).
Составим таблицу истинности для функции V:
|
x
|
y
|
z
|
импликация
|
эквивалентность
|
|
0
|
0
|
0
|
1
|
0
|
|
0
|
0
|
1
|
0
|
1
|
|
0
|
1
|
0
|
1
|
0
|
|
0
|
1
|
1
|
1
|
0
|
|
1
|
0
|
0
|
1
|
1
|
|
1
|
0
|
1
|
0
|
0
|
|
1
|
1
|
0
|
1
|
1
|
|
1
|
1
|
1
|
1
|
1
|
Мы получили формулу V(01001011)
Сравнивая таблицы функций U и V,
видим, что U ¹ V.
Значит, формулы U и V неэквивалентны.
Методом
неопределенных коэффициентов построить полином Жегалкина для следующих функций.
а)
Сначала составим таблицу истинности для функции
|
x
|
y
|
z
|
отрицание
x
|
отрицание
у
|
конъюнкция
|
дизъюнкция
|
|
0
|
0
|
0
|
1
|
1
|
1
|
1
|
|
0
|
0
|
1
|
1
|
1
|
1
|
1
|
|
0
|
1
|
0
|
1
|
0
|
0
|
0
|
|
0
|
1
|
1
|
1
|
0
|
0
|
1
|
|
1
|
0
|
0
|
0
|
1
|
0
|
0
|
|
1
|
0
|
1
|
0
|
1
|
0
|
1
|
|
1
|
1
|
0
|
0
|
0
|
0
|
0
|
|
1
|
1
|
1
|
0
|
0
|
0
|
1
|
Полином
Жегалкина для нее представляется в виде:
Последовательно подставляя значения переменных из
таблицы, получаем:
Следовательно функция представляется полиномом Жегалкина как .
б)
Сначала составим таблицу истинности для функции .
|
x
|
y
|
z
|
конъюнкция
|
импликация
|
|
0
|
0
|
0
|
0
|
1
|
|
0
|
0
|
1
|
0
|
1
|
|
0
|
1
|
0
|
0
|
1
|
|
0
|
1
|
1
|
0
|
1
|
|
1
|
0
|
0
|
0
|
1
|
|
1
|
0
|
1
|
1
|
0
|
|
1
|
1
|
0
|
0
|
1
|
|
1
|
1
|
1
|
1
|
1
|
Полином Жегалкина для нее представляется в виде:
Последовательно подставляя значения переменных из
таблицы, получаем:
Следовательно функция представляется полиномом Жегалкина как .
