Дискретная математика (стр. 10 )

f(1, 0)  f(0, 0),

остальные наборы входных переменных несравнимы.

5.  f(x1, x2) = x1x2 не является линейной, так как ее невозможно представить в виде линейного полинома Жегалкина.

Пример 2. Определить свойства логической функции, заданной таблицей

x1	0	0	0	0	1	1	1	1
x2	0	0	1	1	0	0	1	1
x3	0	1	0	1	0	1	0	1
f	0	1	0	1	0	1	0	1

f(0, 0, 0) = f(1, 0, 0)

f(0, 0, 1) = f(1, 0, 1)

f(0, 1, 0) = f(1, 1, 0)

f(0, 1, 1) = f(1, 1, 1) Þ f не зависит существенно от x1

f(0, 0, 0) = f(0, 1, 0)

f(0, 0, 1) = f(0, 1, 1)

f(1, 0, 0) = f(1, 1, 0)

f(1, 0, 1) = f(1, 1, 1) Þ f не зависит существенно от x2

f(0, 0, 0) ¹ f(0, 0, 1) Þ f существенно зависит от x3

f(0, 0, 0) = 0 Þ f сохраняет ноль

f(1, 1, 1) = 1 Þ f сохраняет единицу

f(0, 0, 0) ¹ f(1, 1, 1)

f(0, 0, 1) ¹ f(1, 1, 0)

f(0, 1, 0) ¹ f(1, 0, 1)

f(0, 1, 1) ¹ f(1, 0, 0) Þ f самодвойственна

f(1, 1, 1) > f(0, 0, 0)

f(1, 1, 0) = f(1, 0, 0)

f(1, 1, 0) = f(0, 1, 0)

f(1, 0, 1) > f(1, 0, 0)

f(1, 0, 1) = f(0, 0, 1)

f(0, 1, 1) > f(0, 1, 0)

f(0, 1, 1) = f(0, 0, 1) Þ f монотонна

Из таблицы значений функции f понятно, что f = x3. Эта запись одновременно является и полиномом Жегалкина для функции f. Данный полином – линейный (так как в нем нет слагаемых, являющихся конъюнкциями нескольких переменных), следовательно, и функция f является линейной.

Пример 3. Определить свойства логической функции, заданной таблицей

x	0	0	0	0	1	1	1	1
y	0	0	1	1	0	0	1	1
z	0	1	0	1	0	1	0	1
f	1	1	0	1	0	1	0	1

f(0, 0, 0) ¹ f(1, 0, 0) Þ f существенно зависит от x

f(0, 0, 0) ¹ f(0, 1, 0) Þ f существенно зависит от y

f(0, 1, 0) ¹ f(0, 1, 1) Þ f существенно зависит от z

f(0, 0, 0) = 1 Þ f не сохраняет ноль

f(1, 1, 1) = 1 Þ f сохраняет единицу

f(0, 0, 0) = f(1, 1, 1) Þ f не является самодвойственной

f(0, 1, 0) < f(0, 0, 0) Þ f не является монотонной

Получить полином Жегалкина можно из ДСНФ функции. Чтобы упростить данный процесс, попробуем сначала минимизировать нашу функцию, например, с помощью карты Карно.

f(x, y, z) = z +`x`y = z Å`x`y Å`x`y z = z Å (x Å 1)(y Å 1) Å (x Å 1)(y Å 1)z =

= z Å xy Å x Å y Å 1 Å xyz Å xz Å yz Å z = xyz Å xy Å xz Å yz Å x Å y Å 1

Замечание:

Были использованы следующие преобразования:

a + b = a Å b Å ab

`a = a Å 1

a Å a = 0

a Å 0 = a

Полученный полином Жегалкина не является линейным, следовательно, исходная функция f – не линейная.

Контрольные вопросы

1. Если f(x1, x2, ..., xi–1, 0, xi+1, ..., xn) = f(x1, x2, ..., xi–1, 1, xi+1, ..., xn) на одном из наборов данных, можно ли сказать, что функция f не зависит существенно от xi?

2. Можно ли сказать, что функция является самодвойственной, если она принимает противоположные значения на какой-нибудь одной паре противоположных наборов?

3. Является ли истинным следующее неравенство: (1, 0, 1) ³ (0, 1, 0)?

4. Является ли следующий полином Жегалкина линейным: f(x1, x2) = x1 Å x1x2 ?

Часть 2

Варианты заданий

Задание 1. Операции над множествами

Вариант 1

Даны множества: Определить множества:

A = {1, 2, 3, 4, 5, 6, 7, 8}; D1 = A D B;

B = {3, 4, 5, 6, 9, 10, 11, 12}; D2 = C \ (A È B);

C = {5, 6, 7, 8, 9, 10, 13, 14}. D = D2 ´ D1.

Вариант 2

Даны множества: Определить множества:

A = {1, 2, 3, 4, 5, 6, 7, 8}; D1 = A Ç B Ç С;

B = {3, 4, 5, 6, 9, 10, 11, 12}; D2 = (A È B) \ C;

C = {5, 6, 7, 8, 9, 10, 13, 14}. D = D1 ´ D2.

Вариант 3

Даны множества: Определить множества:

A = {1, 2, 3, 4, 5, 6, 7, 8}; D1 = С \ B;

B = {3, 4, 5, 6, 9, 10, 11, 12}; D2 = A Ç B;

C = {5, 6, 7, 8, 9, 10, 13, 14}. D = D2 ´ D1.

Вариант 4

Даны множества: Определить множества:

A = {1, 2, 3, 4, 5, 6, 7, 8}; D1 = A \ B;

B = {3, 4, 5, 6, 9, 10, 11, 12}; D2 = B Ç С;

C = {5, 6, 7, 8, 9, 10, 13, 14}. D = D1 ´ D2.

Вариант 5

Даны множества: Определить множества:

A = {1, 2, 3, 4, 5, 6, 7, 8}; D1 = B \ С;

B = {3, 4, 5, 6, 9, 10, 11, 12}; D2 = A Ç С;

C = {5, 6, 7, 8, 9, 10, 13, 14}. D = D2 ´ D1.

Вариант 6

Даны множества: Определить множества:

A = {1, 2, 3, 4, 5, 6, 7, 8}; D1 = A \ С;

B = {3, 4, 5, 6, 9, 10, 11, 12}; D2 = (A È B È С) \ (A È B);

C = {5, 6, 7, 8, 9, 10, 13, 14}. D = D1 ´ D1.

Вариант 7

Даны множества: Определить множества:

A = {1, 2, 3, 4, 5, 6, 7, 8}; D1 = B \ A;

B = {3, 4, 5, 6, 9, 10, 11, 12}; D2 = (A Ç C) \ B;

C = {5, 6, 7, 8, 9, 10, 13, 14}. D = D2 ´ D1.

Вариант 8

Даны множества: Определить множества:

A = {1, 2, 3, 4, 5, 6, 7, 8}; D1 = C \ A;

B = {3, 4, 5, 6, 9, 10, 11, 12}; D2 = (A Ç B) \ C;

C = {5, 6, 7, 8, 9, 10, 13, 14}. D = D1 ´ D1.

Вариант 9

Даны множества: Определить множества:

A = {1, 2, 3, 4, 5, 6, 7, 8}; D1 = A D C;