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