Учебное пособие для студентов заочного факультета по дисциплине «Дискретная математика» (90

1.

f T1 ,

f S .

2.

f T0 , f S , f M , f L .

3.

f T0 , f T1 , f S .

4.

f T0 , f T1 , f M .

5.

f T1 , f S , f L .

Решение.

Таблица истинности булевой функции имеет вид:

x

y

z

f (x, y, z)

0

0

0

0

0

0

1

0

0

1

0

1

0

1

1

1

1

0

0

0

1

0

1

1

1

1

0

1

1

1

1

1

f (0,0,0)

0 , следовательно, f ( x, y, z)

T0 .

f (1,1,1)

1 , следовательно, f ( x, y, z)

T1 .

Для проверки самодвойственности разобьем строку значений функции

пополам:

Вторую

половину отбросим, первую отразим

0011

0111 .

симметрично (

и возьмем инверсию от новой второй половины:

0011

1100 ),

f (x, y, z)

S .

0011

0011 . Полученные набор не совпадает с исходным,

Для проверки монотонности разобьем строку значений функции пополам:

0011 предшествует 0111, продолжаем процесс деления пополам.

0011

0111 .

00 предшествует 11, 01 предшествует 11. Продолжаем.

0 0 , 1

1, 0 1 , 1 1.

Следовательно, f (x, y, z)

M .

Построим полином Жегалкина.

f ( x, y, z) x y z

x yz

xy z

xyz

xyz

x 1 y z 1

( x 1) yz x y 1 z

xy(z

1)

xyz

xyz

xy

yz

y xyz

yz

xyz

xz

xyz

xy

xyz

xyz

xz

y.

0

1

0

1

1

0

0

1

0

1

1

0

0

0

0

1

0

1

0

0

1

1

1

1

0

0

1

0 .

1

0

0

0

0

1

0

0

0

0

1

1

0

1

0

0

1

0

0

1

0

1.

( x1 ) 1 ,

( x2 ) 3 ,

( x3 ) 3 ,

(x4 ) 4 ,

( x5 ) 2 ,

( x6 ) 3 ,

(x7 ) 2 .

2.

( x1 ) 3 ,

( x2 ) 3 ,

( x3 ) 3 ,

(x4 ) 4 ,

( x5 ) 2 ,

( x6 ) 3 ,

( x7 ) 1 .

3.

( x1 ) 3 ,

(x2 ) 2 ,

( x3 ) 3 ,

(x4 )

4 ,

( x5 )

2 ,

( x6 )

3 ,

(x7 )

2 .

4.

( x1 )

3 ,

( x2 )

3 ,

( x3 )

3 ,

(x4 )

4 ,

( x5 )

2 ,

( x6 )

3 ,

(x7 )

2 .

5.

( x1 )

3 ,

( x2 )

3 ,

( x3 )

2 ,

(x4 ) 4 ,

( x5 ) 2 ,

( x6 ) 3 ,

(x7 ) 2 ..

Решение.

Матрица

смежности A(G) неориентированного графа G - это матрица

размерности n

n , элементы которой определяются следующим образом:

aij

1,если вершины xi и x j смежны,

0в противном случае.

По матрице смежности построим граф G :

G

x2

x1

x

3

x4

x5

x6

x

7

Степень (валентность) вершины xi неориентированного графа

G -

это

число ребер (xi ) , инцидентных данной вершине. Таким образом,

( x1 )

3 ,

( x2 ) 3 ,

( x3 ) 3 , (x4 ) 4 , ( x5 ) 2 , ( x6 ) 3 , (x7 ) 2 . Правильный ответ под

номером

4.

Задание 19.

Для графа из задания 18 расстояние от вершины x1 до вершины x7 равно...

Решение.

Граф нами уже построен. Расстояние d (x, y) между вершинами x и y в

неориентированном графе G -

это наименьшее число ребер, соединяющих

вершины x и y . Таким образом,

d ( x1, x7 ) 3 . Правильный ответ - 3.

Ответы на вопросы для самопроверки.

1.

Истинное утверждение -1

1, 2,3 .

2.

Истинное утверждение - 1

1,2,3 .

3.

Объединение множеств A и B A

B .

B

x

x

Aили x

4.

Пересечение множеств A и B A

B

x

x

Aи x B .

5.

Разность множеств A и B A \ B

B .

x

x

Aи x

6.

Дополнение множества A A

U \ A .

7.

Симметрическая разность множеств A и B - A B

A \ B

B \ A или

A B

A

B \

A

B .

8.

Свойство коммутативности объединения множеств -

A

B

B

A.

9.

Свойство коммутативности пересечения множеств -

A

B

B

A.

10.Свойство ассоциативности объединения множеств -

A

B

C

A

B

C .

11.Свойство ассоциативности пересечения множеств -

A

B

C

A

B

C .

13.Свойство дистрибутивности объединения множеств относительно

пересечения -

A

B

C

A

B

A

C .

14.Свойство ассоциативности симметрической разности множеств -

A

B C

A B

C .

15.Закон двойного дополнения - A

A .

16.Законы де Моргана для множеств - A

B

A

B и A

B

A

B .

17.– 20. Коммутативность объединения - A

B B A. Ассоциативность

объединения - A

B

C

A

B

C . Коммутативность пересечения -

A

B

B

A. Ассоциативность пересечения -

A

B

C

A

B

C .

Дистрибутивность пересечения относительно объединения -

A

B

C

A

B

A C . Дистрибутивность объединения относительно

пересечения - A

C .Закон де Моргана -

B

C

A

B

A

A

B A

B

и A

B

A

B . Двойное дополнение -

A

A .Ассоциативность

симметрической разности - A B C

A B

C .

21.Прямое произведение множеств A и B

A B a, b

a A, b B .

22.В общем случае выполняется свойство - A B

B

A.

23.Ассоциативность прямого произведения множеств - A

B

C

A

B

C .

24. A

B тогда и только тогда, когда

a

A

a

B .

25. A

B тогда и только тогда, когда A

B, B

A .

26. A

B тогда и только тогда, когда A B, A

B .

27.Множества A и B находятся в общем положении тогда и только тогда, когда

a A, a B ;

b B, b A;

c A, c B .

28.Множества A

1,2,3

и B

3,4 находятся в общем положении.

29.Множества A

1, 2

и B

1, 2,3 таковы, что A

B .

30.Множества A

1, 2

и B

3,4 таковы, что A

B

.

31.Множества A

1,2,3

и B

3

таковы, что B

A.

32.Множество всех подмножеств множества 1,2,3

-

, 1 ,

2 , 3 , 1,2 , 1,3 , 2,3 , 1,2,3 .

33.Множество всех подмножеств множества

3,4,5

-

, 3 , 4 , 5 , 3,4 , 3,5 , 3,4 , 3,4,5 .

34.Множество всех подмножеств множества

4,5

-

, 4

,

5 ,

4,5 .

2n .

35.Если

A

n ,

то

P A

m ,

n , то

mn .

36.Если

A

B

A

B

M M .

42.Свойство рефлексивности бинарного отношения

на множестве M -

x

M x

x .

43.Свойство антирефлексивности бинарного отношения

на множестве M -

x

M x

x .

44.Свойство симметричности бинарного отношения

на множестве M -

x, y

M x y

y x .

45.Свойство антисимметричности бинарного отношения

на множестве M -

x, y M x y, y x x y .

46.Свойство транзитивности бинарного отношения

на множестве M -

x, y, z M x y, y z x z .

47.Свойство рефлексивности бинарного отношения

на множестве M -

x

M x, x

.

48.Свойство симметричности бинарного отношения

на множестве M -

x, y M x, y

y, x

.

49.Свойство транзитивности бинарного отношения

на множестве M -

x, y, z M x, y

, y, z

x, z

.

симметричное.

56.Данная таблица истинности соответствует булевой функции

f

x, y

x

y .

57.Данная таблица истинности соответствует булевой функции

f

x, y

x

y .

58.Данная таблица истинности соответствует булевой функции

f

x, y

x

y .

59.Данная таблица истинности соответствует булевой функции

f

x, y

x

y .

60.Данная таблица истинности соответствует булевой функции

f

x, y

x

y .

61.Данная таблица истинности соответствует булевой функции

f

x, y

x .

62.Булевой функции f x, y x y соответствует таблица истинности…

x

y

f x, y

0

0

0

0

1

1

1

0

1

63.Булевой функции

f

x, y

x

y соответствует таблица истинности…

x

y

f

x, y

0

0

0

0

1

1

1

0

1

1

1

1

64.Булевой функции

f

x, y

x

y соответствует таблица истинности…

x

y

f

x, y

0

0

0

0

1

0

1

0

0

1

1

1

65.Булевой функции

f

x, y

x

y

соответствует таблица истинности…

x

y

f

x, y

0

0

1

0

1

1

1

0

0

1

1

1

66.Булевой функции

f

x, y

x

y

соответствует таблица истинности…

x

y

f

x, y

0

0

1

0

1

0

1

0

0

1

1

1

67.Булевой функции

соответствует таблица истинности…

f

x, y

x

x

y

f

x, y

0

0

1

0

1

1

1

0

0

1

1

0

68.Свойство коммутативности конъюнкции x

y

y

x .

69.Свойство ассоциативности конъюнкции x

( y

z)

(x y) z .

70.Свойство дистрибутивности конъюнкции x ( y z)

(x

y)

(x

z) .

71.Свойство коммутативности дизъюнкции x

y

y

x .

72.Свойство ассоциативности дизъюнкции x

( y

z)

(x

y)

z .

73.Свойство дистрибутивности дизъюнкции x

( y

z)

(x

y)

(x

z) .

74.Законы де Моргана для булевых операций x

y

x

y и x

y

x

y .

75.Закон противоречия - x x

0 . Закон исключения третьего - x

x

1 . Закон

двойного отрицания - x

x .

76. x

x

,

1, .

x,

0.

77. x

x .

78. x

x или x .

79.Совершенная дизъюнктивная нормальная форма булевой функции

f x , x ,..., x

x

1

...x n .

1

2

n

( 1,...,

n ):

1

n

f ( 1,..., n ) 1

80.Совершенная конъюнктивная нормальная форма булевой функции

f x , x ,..., x

( x 1

...

x

n ) .

1

2

n

( 1,...,

n ):

1

n

f ( 1,..., n ) 0

81.Совершенная дизъюнктивная нормальная форма булевой функции не

определена для функции f

x1, x2 ,..., xn

0.

82.Совершенная конъюнктивная нормальная форма булевой функции не

определена для функции f

x1, x2 ,..., xn

1.