Многочлен Жегалкина. Таблица истинности. Эквивалентность формул
Построить таблицы соответствующих функций и выяснить, эквивалентны ли формулы
и 
.>
а) 
Составим таблицу истинности для функции 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().
Составим таблицу истинности для функции 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()
Сравнивая таблицы функций 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(1100).
Составим таблицу истинности для функции 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(1)
Сравнивая таблицы функций 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 |
Полином Жегалкина для нее представляется в виде:
Последовательно подставляя значения переменных из таблицы, получаем:
Следовательно функция
представляется полиномом Жегалкина как 
.>
5