Контрольная работа по "Дискретная математика"

Задание №1.

Определить, являются ли формулы f и g эквивалентными.

Построим таблицы значений функций алгебры логики f и g

Порядок выполнения действий 1 3 2 7 4 6 5

x y z x ↓ z ~ y x ~ x z | z → y

0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0

0 0 1 0 0 1 1 0 0 0 1 0 1 1 1 1 0 0

0 1 0 0 1 0 1 1 1 0 1 0 0 0 1 0 1 1

0 1 1 0 0 1 0 1 1 0 1 0 1 1 0 1 1 1

1 0 0 1 0 0 0 0 1 1 1 1 1 0 0 0 1 0

1 0 1 1 0 1 0 0 1 1 0 1 0 1 1 1 0 0

1 1 0 1 0 0 1 1 0 1 0 1 1 0 0 0 1 1

1 1 1 1 0 1 1 1 0 1 0 1 0 1 0 1 1 1

Порядок выполнения действий 1 3 2 7 4 6 5

x y z z ~ x ~ y | z ~ y ↓ z ~ z ~ x

0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0

0 0 1 0 0 1 0 0 1 0 0 0 0 1 1 1 0 0

0 1 0 0 1 0 1 1 1 0 0 0 1 0 0 0 0 1

0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 1

1 0 0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 0

1 0 1 1 1 1 1 0 1 1 1 1 0 1 1 1 0 0

1 1 0 1 0 0 1 1 0 1 1 1 0 0 1 0 0 1

1 1 1 1 1 1 0 1 0 1 1 1 0 1 0 1 1 1

Отсюда следует, что и следовательно, они не эквивалентны.

Задание №2.

Для булевой функции, заданной вектором значений (1101 0110), определить:

1. Существенные и фиктивные переменные;

2. Совершенную дизъюнктивную нормальную форму;

3. Совершенную конъюнктивную нормальную форму;

4. Полином Жегалкина двумя способами;

5. Принадлежность классам T0, T1, S, M, L.

Построим таблицу функции алгебры логики:

x y z f

0 0 0 1

0 0 1 1

0 1 0 0

0 1 1 1

1 0 0 0

1 0 1 1

1 1 0 1

1 1 1 0

1. Для того, чтобы xi была существенной необходимо, чтобы существовала пара наборов u и v соседних по i-ой переменной, для которых выполняется f(u) ≠ f(v). Если это неравенство не выполняется для всех пар наборов u и v, то такая переменная является фиктивной.

Проверим является ли переменная x существенной?

f(000) ≠ f(100) ⇒ x – существенная

Проверим является ли переменная y существенной?

f(000) ≠ f(010) ⇒ y – существенная

Проверим является ли переменная z существенной?

f(010) ≠ f(011) ⇒ z – существенная

2. СДНФ:

3. СКНФ:

4. Полином Жегалкина

1 способ:

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

1. Выпишем S элементарных конъюнкций (S = количество «1» в таблице значений)

2. Над переменными равными «0» ставим отрицание.

3.

4. Упрощаем полученное выражение ( )

2 способ:

5. Принадлежность классам T0, T1, S, M, L.

, то есть если на любых парах противоположных наборов ее значения противоположны.

Полином Жегалкина данной функции принимает вид:

Задание №3.

Данную формулу преобразовать в СДНФ двумя способами: 1) по таблице истинности, 2) преобразованием.

а) б)

А1.

Построим