Многочлен Жегалкина. Таблица истинности. Эквивалентность формул

Вид работы:

Методичка
Предмет:

Математика
Язык:

Русский
,
Формат файла:
MS Word
Опубликовано:

2010-06-22

Скачать методичку Читать текст online Посмотреть все методички

Вы можете узнать стоимость помощи в написании студенческой работы.

Многочлен Жегалкина. Таблица истинности. Эквивалентность формул

Построить таблицы соответствующих функций и выяснить, эквивалентны ли формулы и .

а)

Составим таблицу истинности для функции 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	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

Полином Жегалкина для нее представляется в виде:

Последовательно подставляя значения переменных из таблицы, получаем:

Следовательно функция представляется полиномом Жегалкина как .

Многочлен Жегалкина. Таблица истинности. Эквивалентность формул

Многочлен Жегалкина. Таблица истинности. Эквивалентность формул

Похожие работы на - Многочлен Жегалкина. Таблица истинности. Эквивалентность формул