Расчетное задание по "Дискретной математике"

Министерство образования и  науки Российской Федерации

Рязанский государственный радиотехнический университет

Кафедра вычислительной и прикладной математики

 

 

РАСЧЕТНОЕ ЗАДАНИЕ

ПО ДИСЦИПЛИНЕ

«ДИСКРЕТНАЯ МАТЕМАТИКА»

 

ВАРИАНТ 89

 

 

 

 

 

 

 

 

 

 

 

Выполнил

 

Проверил

проф. Цветков И.А.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рязань 2010

Исходные данные

3-местная булева функция  имеет десятичный номер 194.

Решение

1. Переводим десятичный номер 194 3-местной булевой функции в двоичную систему счисления: . Записываем кортеж значений функции, указывая цифры этого двоичного числа справа налево и добавляя справа нулевые элементы, если это требуется, так, чтобы кортеж имел длину . Получаем кортеж значений .

Таблица 3.1
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	0
1	0	0	0
1	0	1	0
1	1	0	1
1	1	1	1

2. Для булевой функции

по кортежу значений

составляем таблицу значений (см. табл. 3.1).

 

 

 

 

 

 

 

3. Для булевой функции

Таблица 3.2
		0	1
0	0	0	1
0	1	0	0
1	1	1	1
1	0	0	0

по таблице значений (табл. 3.1)

составляем карту Карно (см. табл. 3.2).                   

 

 

 

 

 

 

 

Рис. 3.1

 

4. Для булевой функции

по таблице значений (табл. 3.1)

изображаем 3-мерный единичный куб

(см. рис. 3.1).

 

 

 

 

 

 

 

 

 

 

5.Вычисляем 3-местную матрицу  Адамара  . Зная 1-местную матрицу Адамара , получаем 2-местную матрицу Адамара   .

Тогда .Для булевой функции по

 

 

 

кортежу значений записываем вектор-столбец значений           

 

 

 

 

 

Вычисляем спектр Фурье: .

Для проверки выполняем обратное булево преобразование Фурье:.

Полученный вектор-столбец равен исходному, следовательно, спектр Фурье вычислен правильно.

6. По рис. 3.1 определяем, что у булевой функции нет несущественных переменных (т.е. эта функция существенная), так как для нее не выполнено ни одно из шести необходимых и достаточных условий несущественности 3-местной булевой функции.

7. Получим кортеж значений двойственной к булевой функции , проинвертировав в кортеже значений исходной функции все элементы и записав кортеж в обратном порядке. Имеем . По этому кортежу составляем таблицу значений булевой функции (см. табл. 3.3). Записываем элементы этого кортежа справа налево как двоичное число и находим его десятичное значение 188, т.е. булева функция имеет десятичный номер 188.

По табл. 3.3 изобразим 3-мерный единичный куб для булевой функции (см. рис. 3.2).

Таблица 3.3
0	0	0	0
0	0	1	0
0	1	0	1
0	1	1	1
1	0	0	1
1	0	1	1
1	1	0	0
1	1	1	1

 

Рис. 3.2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

8. Для булевой функции запишем СДНФ. По таблице значений (табл. 3.1) определим элементарные конъюнкции для единичных значений функции: , , . Запишем СДНФ как дизъюнкции этих элементарных конъюнкций: (скобки необязательны).Таким образом, имеем равносильность

.

9. Для булевой функции запишем СКНФ. По таблице значений (табл. 3.1) определим элементарные дизъюнкции для нулевых значений функции: , , , , . Запишем СКНФ как конъюнкции этих элементарных дизъюнкций: (скобки обязательны). Таким образом, имеем равносильность .

10. Для булевой функции определим МДНФ по 3-мерному единичному кубу (рис. 3.1). В нем выделяются два ребра (см. рис. 3.3). Т.к. слева на рис. 3.3 выделена точка, то выбираем все элементы этого кортежа, следовательно, этой части соответствует элементарная конъюнкция . Для ребра справа на рис. 3.3 совпадают первые и вторые элементы кортежей аргументов, следовательно, этому ребру соответствует элементарная конъюнкция . Имеем МДНФ , т.е. .

 

Рис. 3.3

 

11. Для булевой функции определим МДНФ по карте Карно (табл. 3.2). Для упрощения не показываем на карте Карно нулевые значения функции (см. табл. 3.4).

Таблица 3.4
		0	1
0	0		1
0	1
1	1	1	1
1	0

На карте выделяются два элемента. Верхнему элементу соответствует элементарная конъюнкция , нижнему — элементарная конъюнкция .

Имеем МДНФ , т.е. .

 

 

 

 

 

12. Составим таблицу значений МДНФ (см. табл. 3.5). Значения МДНФ равны значениям булевой функции (см. табл. 3.1) для всех кортежей аргументов.

Таблица 3.5
0	0	0	0	0	0
0	0	1	1	0	1
0	1	0	0	0	0
0	1	1	0	0	0
1	0	0	0	0	0
1	0	1	0	0	0
1	1	0	0	1	1
1	1	1	0	1	1

 

 

 

 

 

 

 

 

 

 

 

 

 

14. Для булевой функции найдем коэффициенты полинома Жегалкина методом неопределенных коэффициентов.

А. Определяем коэффициент .

Б. Вычисляем коэффициенты

,

,

.

В. Находим коэффициенты

,

, .

Г. Получаем коэффициент 

     

15. Для булевой функции найдем коэффициенты полинома Жегалкина методом преобразования кортежа значений. Имеем табл. 3.6.

Таблица 3.6
0	1	0	0	0	0	1	1
0	1	0	0	0	0	1	0
0	1	0	1	0	0	1	0
0	1	0	1	0	1	1	1

Следовательно, коэффициенты полинома Жегалкина равны: , , , , , , , .

16. Для булевой функции найдем коэффициенты полинома Жегалкина по 3-мерному единичному кубу (рис. 3.1). В нем начало координат не отмечено, поэтому . На оси x нет отмеченных вершин, поэтому . На оси нет отмеченных вершин, поэтому . На оси отмечено нечетное число вершин, поэтому . В плоскости отмечено нечетное число вершин, поэтому . В плоскости отмечено нечетное число вершин, поэтому . В плоскости отмечено нечетное число вершин, поэтому . Во всем единичном кубе отмечено нечетное число вершин, поэтому .

17. Для булевой функции имеем полином Жегалкина . Это полином третьего порядка.

Проверим по полученному полиному Жегалкина, есть ли у булевой функции  несущественные переменные. Все три переменные , , существенные, так как каждая из них есть хотя бы в одной конъюнкции с единичным коэффициентом.

 Составим таблицу значений  этого полинома (см. табл. 3.7). Значения полинома Жегалкина равны значениям булевой функции (см. табл. 3.1) для всех кортежей аргументов, следовательно, полином Жегалкина получен правильно.

 

 

 

Таблица 3.7
x	y	z
0	0	0	0	0	0	0	0
0	0	1	0	0	0	0	1
0	1	0	0	0	0	0	0
0	1	1	1	0	0	0	0
1	0	0	0	0	0	0	0
1	0	1	0	1	0	0	0
1	1	0	0	0	1	0	1
1	1	1	1	1	1	1	1