Тема 3.3. Операция двоичного сложения. Полином Жегалкина

1. Построить таблицу истинности для формулы

Решение:

Расставим порядок действий и , используя правила выполнения операций штрих Шеффера и стрелка Пирса, заполним таблицу истинности:

x	y	z	1	2	3	4
0	0	0
1	0	0
0	1	0
0	0	1
1	1	0
1	0	1
0	1	1
1	1	1

2. Для формулы составить ДНФ и КНФ.

Решение:

При переходе к основным операциям воспользуемся равносильностями, выражающими Штрих Шеффера и стрелку Пирса через дизъюнкцию и конъюнкцию:

Преобразуем формулу:

….

ДНФ …

КНФ ….

3. Методом неопределенных коэффициентов разложить функции в полином: а)f(x,y)= (0101); б) f(x,y)=(1011); в) f(x,y,z)= (01001110); г) f(x,y,z) = (11000101).

Решение:

Составим полином в общем виде, который для функции двух переменных имеет вид:

,

для функции трех переменных имеет вид:

Сначала составим таблицу истинности, причем соблюдаем соответствие набора его номеру в таблице истинности. Далее против каждой строки составляем уравнение вида

.

Решая уравнение, находим вектор коэффициентов, затем составляем полином:

а)f(x,y)= (0101)

Уравнения:

х	у	f

Вектор коэффициентов:

б) f(x,y)=(1011)

Уравнения:

х	у	f

Вектор коэффициентов:

в) f(x,y,z)= (01001110)

Уравнения:

x	y	z	f

Вектор коэффициентов…

г) f(x,y,z) = (11000101)

Уравнения:

x	y	z	f

Вектор коэффициентов…

4. Путем равносильных преобразований построить полиномы для формул:

а) ху;

б) (х|y)z;

в) (xy)(yz);

г) ((xy)v )|x.

Решение:

Для построения полиномов воспользуемся алгоритмом. Перечислим его пункты:

1) Преобразовать формулу так, что бы остались операции ………………, ……………..

2) Снять отрицания, используя равносильность ….

3) Раскрыть скобки, используя равносильность

а) ху …

б) (х|y)z …

в) (xy)(yz) …

г) ((xy)v )|x …