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