35824

Дискретная математика. Тестовые вопросы к экзамену

Тест

Математика и математический анализ

Функции алгебры логики. Булевы функции одной и двух переменных. Функциями алгебры логики или булевыми функциями называются а где б в Множество всех булевых функций от n переменных обозначают а б в г Булева функция существенно зависит от переменной xi если существует такой набор значений...

Русский

2013-09-20

2.41 MB

22 чел.

Министерство образования Республики Беларусь

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

Федеральное агентство по образованию

Государственное учреждение высшего профессионального образования

«БЕЛОРУССКО-РОССИЙСКИЙ УНИВЕРСИТЕТ»

Дискретная математика

Тестовые вопросы к экзамену

для специальности 23 01 02  Автоматизированные системы обработки
информации и управления

Утверждены на заседании кафедры

«Автоматизированные системы управления»,

протокол № 9 от 15 мая 2012 г.

Заведующий кафедрой АСУ

_____________________ С.К. Крутолевич

«___» ____________ 2012

Могилев, 2012

Тестовые вопросы составлены в соответствии с Государственным образовательным стандартом высшего профессионального образования по направлению 654600 и специальности 220202 – «Автоматизированные системы обработки информации и управления», регистрационный номер 224 тех/дс, учебным планом.

Тестовые вопросы составил канд. техн. наук, доц. кафедры
«Автоматизированные системы управления» А.И. Якимов

Тестовые вопросы обсуждены на заседании кафедры «Автоматизированные системы управления»

«15»  мая  2012 г., протокол № 9.

Зав. кафедрой «АСУ»     ________________ С.К. Крутолевич


Критерии определения экзаменационной оценки по дисциплине «Дискретная математика»

Итоговая оценка определяется как сумма текущего и рубежного (итогового) рейтинг-контроля и соответствует баллам:

Минимальная допустимая оценка текущего рейтинг-контроля составляет 36 баллов.

Максимальная оценка текущего рейтинг-контроля составляет 60 баллов.

Минимальная допустимая оценка итогового рейтинг-контроля составляет 15 баллов.

Максимальная оценка итогового рейтинг-контроля составляет 40 баллов.

Экзамен по пятибалльной системе:

Оценка

Отлично

Хорошо

Удовлетворительно

Неудовлетворительно

Баллы

87–100

65–86

51–64

0–50

Итоговый контроль проводится в форме компьютерного тестирования в сетевом классе. Критерием определения экзаменационной оценки является количество правильных ответов на тестовые вопросы, определяемое в процентах.

Баллы определяются по следующей методике.

1) Количество правильных ответов не более 50%:

Балл (<50%) = (%отв – 20%)/2 [Балл], где %отв – правильные ответы в процентах, 20%  эмпирическое количество правильных ответов при случайном выборе.

Пример1. Получено %отв = 46%.

Балл (<50%) = (46% – 20%)/2 = 13 Баллов.

2) Количество правильных ответов более 50%:

Балл (>50%) = (%отв – 50%)/2 +15 [Балл], где %отв – правильные ответы в процентах, 50%  допустимое значение правильных ответов, при котором итоговый рейтинг-контроль полагают успешным.

Пример 2. Получено %отв = 86%.

Балл (>50%) = (86% – 50%)/2 + 15 = 33 Балла.


Основы теории множеств

Основные понятия теории множеств. Способы задания множеств. Операции над множествами. Диаграммы Венна. Свойства теоретико-множественных операций. Представление множеств в ЭВМ.

1. Множество  задано …

  1.  перечислением элементов
  2.  характеристическим предикатом
  3.  порождающей процедурой

2. Множество  задано …

  1.  перечислением элементов
  2.  характеристическим предикатом
  3.  порождающей процедурой

3. Множество  задано …

  1.  перечислением элементов
  2.  характеристическим предикатом
  3.  порождающей процедурой

4. Множество, которое является элементом другого множества, обычно называют …

  1.  подмножеством
  2.  надмножеством
  3.  семейством

5. Операцию над множествами  называют …

  1.  пересечением
  2.  объединением
  3.  разностью

6. Операцию над множествами  называют …

  1.  разностью
  2.  объединением
  3.  пересечением

7. Операцию над множествами  называют …

  1.  симметрической разностью
  2.  разностью
  3.  пересечением

8. Операцию над множествами  называют …

  1.  разностью
  2.  симметрической разностью
  3.  объединением

9. Операцию  называют …

  1.  дополнением
  2.  пересечением
  3.  объединением

10. Свойство операций над множествами  называют …

  1.  ассоциативностью
  2.  коммутативностью
  3.  идемпотентностью

11. Свойство операций над множествами  называют …

  1.  ассоциативностью
  2.  коммутативностью
  3.  дистрибутивностью

12. Свойство операций над множествами  называют …

  1.  ассоциативностью
  2.  коммутативностью
  3.  дистрибутивностью

13. Свойство операций над множествами  называют …

  1.  поглощением
  2.  коммутативностью
  3.  дистрибутивностью

14. Свойство операций над множествами  называют …

  1.  свойством нуля
  2.  поглощением
  3.  свойством единицы

15. Свойство операций над множествами  называют …

  1.  свойством нуля
  2.  дистрибутивностью
  3.  законом де Моргана

16. Свойство операций над множествами  называют …

  1.  инволютивностью
  2.  коммутативностью
  3.  свойством единицы

17. Свойство операций над множествами  называют …

  1.  инволютивностью
  2.  свойством нуля
  3.  дистрибутивностью

18. Свойство операций над множествами  называют …

  1.  инволютивностью
  2.  свойством дополнения
  3.  законом де Моргана

19. Свойство операций над множествами  называют …

  1.  свойством дополнения
  2.  свойством разности
  3.  дистрибутивностью

20. Свойство операций над множествами  называют …

  1.  ассоциативностью
  2.  свойством разности
  3.  свойством дополнения

21. Круги Эйлера

иллюстрируют операцию … над множествами А и В.

  1.  объединение
  2.  пересечение
  3.  разность

22. Круги Эйлера

иллюстрируют операцию … над множествами А и В.

  1.  объединение
  2.  разность
  3.  симметрическая разность

23. Круги Эйлера

иллюстрируют операцию … над множествами А и В.

  1.  симметрическая разность
  2.  пересечение
  3.  разность

24. Круги Эйлера

иллюстрируют операцию … над множествами А и В.

  1.  объединение
  2.  пересечение
  3.  симметрическая разность

25. Результатом операции над множествами  является …

  1.  пустое множество
  2.  универсум
  3.  множество

26. Результатом операции над множествами  является …

  1.  пустое множество
  2.  множество
  3.  множество

27. Мощность множества  равна …

  1.  нулю
  2.  единице
  3.  не имеет смысла

28. Для заданных множеств A={1, 2}, B={2, 3, 4}, C={1, 3, 5} определить: .

1.

2.

3.

29. Для заданных множеств A={1, 2}, B={2, 3, 4}, C={1, 3, 5} определить:  .

1.

2.

3.

30 Диаграмма Венна

иллюстрируют операцию …

1. объединение

2. разность

3. дополнение

31. Заданы два множества:

A = {<x, y> | (x – 3)2 + (y – 3)2 ≤ 9}

B = {<x, y> | yx}.

Найти их пересечение.

1. {<x, y> | (x – 3)2 + (y – 3)2 ≤ 9 или yx}

2. {<x, y> | (x – 3)2 + (y – 3)2 ≤ 9 и yx}

3. {<x, y> | (x – 3)2 + (y – 3)2 ≤ 9 и y > x}

32. Заданы два множества:

A = {<x, y> | (x – 3)2 + (y – 3)2 ≤ 9}

B = {<x, y> | yx}.

Найти разность B\A.

1. {<x, y> | (x – 3)2 + (y – 3)2 ≤ 9 или yx}

2. {<x, y> | (x – 3)2 + (y – 3)2 ≤ 9 и yx}

3. {<x, y> | (x – 3)2 + (y – 3)2 > 9 и yx}

33. Заданы два множества:

A = {<x, y> | (x – 3)2 + (y – 3)2 ≤ 9}

B = {<x, y> | yx}.

Найти разность A\B.

1. A\B = {<x, y> | (x – 3)2 + (y – 3)2 ≤ 9 и y > x}

2. {<x, y> | (x – 3)2 + (y – 3)2 ≤ 9 и yx}

3. {<x, y> | (x – 3)2 + (y – 3)2 > 9 и yx}

34. Заданы два множества:

A = {<x, y> | (x – 3)2 + (y – 3)2 ≤ 9}

B = {<x, y> | yx}.

Найти дополнение A'.

1. {<x, y> | (x – 3)2 + (y – 3)2 > 9}

2. {<x, y> | y > x}

35. Что называется объединением множеств?

1. Элементы, принадлежащие только одному множеству, но не принадлежащие другому.

2. Элементы, принадлежащие или одному множеству, или второму.

3. Элементы, не принадлежащие ни одному из множеств.

4. Элементы, принадлежащие и одному множеству, и второму.

36. Что называется пересечением множеств?

1. Элементы, принадлежащие только одному множеству, но не принадлежащие другому.

2. Элементы, принадлежащие или одному множеству, или второму.

3. Элементы, не принадлежащие ни одному из множеств.

4. Элементы, принадлежащие и одному множеству, и второму.

37. Что называется разностью множеств?

1. Элементы, принадлежащие только одному множеству, но не принадлежащие другому.

2. Элементы, принадлежащие или одному множеству, или второму.

3. Элементы, не принадлежащие ни одному из множеств.

4. Элементы, принадлежащие и одному множеству, и второму.

38. Are the ordered pairs (2, 3) and (3, 2) equal?

1. This order pairs are different, because two ordered pairs (a, b) and (a’, b’) are equal if and only if a=a’ and b=b’.

2. The set {2, 3} is not an ordered pair since the elements 2 and 3 are not distinguished.

39. Is the set {2, 3} an ordered pair?

1. This order pairs are different, because two ordered pairs (a, b) and (a’, b’) are equal if and only if a=a’ and b=b’.

2. The set {2, 3} is not an ordered pair since the elements 2 and 3 are not distinguished.

40. Какие из приведенных определений множеств A, B, C, D являются корректными?

1. А= {1, 2, 3}

2. С={х | хА}

3. В = {5, 6, 6, 7}

4. D = {A, C}

41. Let A = {1, 2, 3, 4}   and  В = {3, 4, 5, 6}  where  U = {1, 2, 3,  . . .}. Then:

1. AUВ = {1, 2, 3, 4, 5, 6}

2. А∩B = {3, 4}

3. A\B={1, 2}

4. ={5, 6, 7, ...}


Основы теории отношений

1. Прямое произведение множества  самого на себя  = называют …

а) мощностью;

б) булеаном;

в) степенью.

2. Мощность прямого произведения множества и  равна …

а) ;

б) ;

в) .

3. Подмножество R прямого произведения множеств и   называют …

а) надмножеством;

б) отношением;

в) декартовым произведением.

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

а) префиксной;

б) инфиксной;

в) постфиксной.

5. Если есть отношение на , то отношение  является …

а) тождественным отношением;

б) дополнением отношения;

в) обратным отношением.

6. Если  есть отношение на  то отношение  является …

а) универсальным отношением;

б) тождественным отношением;

в) дополнением отношения.

7. Если  есть отношение на :   является …

а) обратным отношением;

б) дополнением отношения;

в) тождественным отношением.

8.  является …

а) обратным отношением;

б) тождественным отношением;

в) универсальным отношением.

9. Пусть  Отношение, определяемое как , является …

а) степенью отношения;

б) композицией отношений;

в) произведением отношений.

10. Если , то  называют …

а) произведением отношения;

б) степенью отношения;

в) ядром отношения.

11. Пусть   является отношением  . Если  , то отношение называют …

а) симметричным;

б) рефлексивным;

в) транзитивным.

12. Пусть  является отношением  . Если , то отношение  называют 

а) антисимметричным;

б) антирефлексивным;

в) транзитивным.

13. Пусть  является отношением . Если  , то такое отношение  называют …

а) полным или линейным;

б) симметричным;

в) рефлексивным.

14. Пусть  является отношением  . Если  , то такое отношение  называют …

а) симметричным;

б) антисимметричным;

в) антирефлексивным.

15. Пусть  является отношением . Если  , то такое отношение   является …

а) рефлексивным;

б) полным или линейным;

в) транзитивным.

16. Пусть  является отношением  . Если   , то такое отношение   называется …

а) симметричным;

б) транзитивным;

в) антирефлексивным.

17. Отношение  называется …

1) унарным

2) бинарным

3) тернарным

4) кватернарным

18. Отношение, заданное матрицей

является …

1. антисимметричным

2. не обладает свойством антисимметричности

3. асимметричным,

4. не обладает свойством асимметричности

4. рефлексивным

5. не обладает свойством рефлексивности

6. антирефлексивным

7. не обладает свойством антирефлексивности

19. Функция . Тогда f1 , представленная на графике,

является …

1. сюръекция, не инъекция;

2. инъекция, не сюръекция;

3. биекция;

4. не сюръекция, не инъекция;

20. Функция . Тогда f2 , представленная на графике,

является …

1. сюръекция, не инъекция;

2. инъекция, не сюръекция;

3. биекция;

4. не сюръекция, не инъекция;

21. Функция . Тогда f3 , представленная на графике,

является …

1. сюръекция, не инъекция;

2. инъекция, не сюръекция;

3. биекция;

4. не сюръекция, не инъекция;

22. Функция . Тогда f4 , представленная на графике,

является …

1. сюръекция, не инъекция;

2. инъекция, не сюръекция;

3. биекция;

4. не сюръекция, не инъекция;

23. Пусть  - отношение на А. Тогда R рефлексивно …

1.  

2.  

3.  

4.  

5.  

6.  

24. Пусть  - отношение на А. Тогда R симметрично …

1.  

2.

3.  

4.  

5.  

6.  

25. Пусть  - отношение на А. Тогда R транзитивно …

1.  

2.

3.  

4.  

5.  

6.  

26. Пусть  - отношение на А. Тогда R антисимметрично …

1.  

2.

3.  

4.  

5.  

6.  

27. Пусть  - отношение на А. Тогда R антирефлексивно …

1.  

2.

3.  

4.  

5.  

6.  

28. Пусть  - отношение на А. Тогда R полно …

1.  

2.  

3.  

4.  

5.  

6.  

29. Пусть отношение R  "быть отцом", определенное на множестве людей М = {a, b, с, d, e, f, g, h}, представлено схемой

.

Тогда отношение R1  "быть дедом" задано множеством упорядоченных пар …

1. {(а, b), (а, с), (b, d), (b, е), (b, f), (с, g), (с, h)}

2. {(a, d), (а, е), (а, f), (а, g), (а, h)}

3. {(b, g), (b, h), (с, d), (с, е), (с, f)}

30. Пусть отношение R  "быть отцом", определенное на множестве людей М = {a, b, с, d, e, f, g, h}, представлено схемой

.

Тогда отношение R2  "быть дядей" задано множеством упорядоченных пар …

1. {(а, b), (а, с), (b, d), (b, е), (b, f), (с, g), (с, h)}

2. {(a, d), (а, е), (а, f), (а, g), (а, h)}

3. {(b, g), (b, h), (с, d), (с, е), (с, f)}

31. Пусть отношение R  "быть отцом", определенное на множестве людей М = {a, b, с, d, e, f, g, h}, представлено схемой

.

Тогда отношение R3  "быть родным братом или сестрой" задано множеством упорядоченных пар …

1. {(b, с), (с, b), (d, е), (е, d), (d, f), (f, d), (e, f), (f, е), (g, h), (h, g)}

2. {(a, d), (а, е), (а, f), (а, g), (а, h)}

3. {(b, g), (b, h), (с, d), (с, е), (с, f)}

32. Пусть отношение R  "быть отцом", определенное на множестве людей М = {a, b, с, d, e, f, g, h}, представлено схемой

.

Тогда отношение R4  "быть племянником  или племянницей" задано множеством упорядоченных пар …

1. {(b, с), (с, b), (d, е), (е, d), (d, f), (f, d), (e, f), (f, е), (g, h), (h, g)}

2. {(g, b), (h, b), (d, c), (e, с), (f, с)}

3. {(b, g), (b, h), (с, d), (с, е), (с, f)}

33. Выберите верное утверждение.

1. Любая эквивалентность определяет несколько разбиений и наоборот.

2. Любая эквивалентность определяет несколько разбиений, обратное утверждение не верно.

3. Любая эквивалентность определяет единственное разбиение и наоборот.

4. Любая эквивалентность определяет единственное разбиение, обратное утверждение не верно.

34. Бинарное отношение R на множестве X называется отношением порядка на X, если оно …

1. рефлексивно, транзитивно и антисимметрично.

2. рефлексивно и симметрично.

3. транзитивно.

4. иррефлексивно, антисимметрично, но не транзитивно.

35. Отношение эквивалентно, если оно …

1. рефлексивно, транзитивно и антисимметрично.

2. является отношением доминирования.

3. рефлексивно, транзитивно и симметрично.

4. рефлексивно.

36. Пусть R1 и R2отношения на N : Rl = {(a, b) | b = a + 2; a, b Î N}, R2 = {(a,b) | b = a2; a, b Î N}. Определить составное отношение R1R2 = {(a, b) | (a, с) R1; (c, b) R2; a ,b, c Î N}.

1. {(a, b) | (a+2)2 = b; a, b ΠN} = {(1, 9), (2, 16), (3, 25), (4, 36), …}.

2. {(a, b) | a2+2 = b; a, b ΠN} = {(1, 2), (2, 6), (3, 11), (4, 18), …}.

3. {(a ,b) | a+4 = b; a, b ΠN} = {(1, 5), (2, 6), (3, 7), (4, 8), …}.

37. Пусть R1 и R2отношения на N : Rl = {(a, b) | b = a + 2; a, b ΠN}, R2 = {(a, b) | b = a2; a, b ΠN}. Определить составное отношение R2R1 = {(a, b) | (a, с) R2; (c, b) R1; a, b, c Î N}.

1. {(a, b) | (a+2)2 = b; a, b ΠN} = {(1, 9), (2, 16), (3, 25), (4, 36), …}.

2. {(a, b) | a2+2 = b; a, b ΠN} = {(1, 2), (2, 6), (3, 11), (4, 18), …}.

3. {(a, b) | a+4 = b; a, b ΠN} = {(1, 5), (2, 6), (3, 7), (4, 8), …}.

38. Пусть R1 и R2отношения на N : Rl = {(a, b) | b = a + 2; a, b ΠN}, R2 = {(a, b) | b = a2; a, b ΠN}. Определить составное отношение R12 = R1R1 = {(a, b) | (a, с) R1; (c, b) R1; a, b, c Î N}.

1. {(a, b) | (a+2)2 = b; a, b ΠN} = {(1, 9), (2, 16), (3, 25), (4, 36), …}.

2. {(a, b) | a4 = b; a, b ΠN} = {(1, 1), (2, 16), (3, 81), …}.

3. {(a, b) | a+4 = b; a, b ΠN} = {(1, 5), (2, 6), (3, 7), (4, 8), …}.

39. Пусть R1 и R2отношения на N : Rl = {(a,b) | b = a + 2; a, b ΠN}, R2 = {(a, b) | b = a2; a, b ΠN}. Определить составное отношение R22 = R2R2 = {(a, b) | (a, с) R2; (c, b) R2; a, b, c Î N}.

1. {(a, b) | (a+2)2 = b; a, b ΠN} = {(1, 9), (2, 16), (3, 25), (4, 36), …}.

2. {(a, b) | a2+2 = b; a, b ΠN} = {(1, 2), (2, 6), (3, 11), (4, 18), …}.

3. {(a, b) | a+4 = b; a, b Î N} = {(1, 5), (2, 6), (3, 7), (4, 8), …}.

41. Пусть R1 и R2 – отношения на множестве M студентов университета: R1 – «быть в одной группе», R2 – «иметь одинаковые имена». Определить композицию отношений R1 и R2. (Азимуратов)

1) R1R2 – «быть в разных группах и иметь разные имена»;

2) R1R2 – «быть в одной группе и иметь одинаковые имена»

3) R1R2 – «быть в одной группе и иметь разные имена»

4) R1R2 – «быть в разных группах и иметь одинаковые имена». (Азимуратов)

42. Пусть R – отношение на N: R = {(a, b)| b = a+1; a, b N }. Определить R2. (Азимуратов)

1) R2 = {(a, b)| b = (a+1)2; a, b  N };

2) R2 = {(a,b)| b = (a2+1); a, b  N };

3) R2 = {(a,b)| b = a+2; a, b  N };

4) R2 = {(a,b)| b = 2a+1; a, b  N }.

АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ

Алгебраические системы. Понятие алгебраической системы, алгебры, модели. Группоиды и полугруппы. Понятие группы. Кольца, тела и поля. Гомоморфизм и изоморфизм. Дистрибутивные решетки. Определение решетки, дистрибутивной решетки. ЧУ-множества, диаграмма Хассе. Булева решетка.

  1.  Множество M  вместе с заданными на нем операциями Σ = {φ1, φ2, …, φn} и отношениями  Ω =  называется … .

а) алгеброй

б) алгебраической системой

в) моделью

  1.  Множество M  вместе с заданными на нем операциями φ1, φ2, …, φn называется … .

а) алгеброй

б) алгебраической системой

в) моделью

  1.  , где M  множество вместе с заданными на нем операциями φ1, φ2, …, φn, является обозначением … .

а) алгебры

б) алгебраической системы

в) модели

  1.  В обозначении алгебры , где M  множество вместе с заданными на нем операциями φ1, φ2, …, φn, М называют … .

а) носителем

б) сигнатурой

в) порядком

  1.  В обозначении алгебры , где M  множество вместе с заданными на нем операциями  φ1, φ2, …, φn , Σ = {φ1, φ2, …, φn} называют … .

а) носителем

б) сигнатурой

в) порядком

  1.  В обозначении  алгебраической системы, где M  множество вместе с заданными на нем операциями Σ = {φ1, φ2, …, φn} и отношениями Ω = , Ω =  называют … .

а) носителем

б) сигнатурой

в) порядком

г) множеством отношений

  1.  Множество M  вместе с заданными на нем отношениями  называется … .

а) алгеброй

б) алгебраической системой

в) моделью

  1.  , где M  множество вместе с заданными на нем отношениями , является обозначением …

а) алгебры

б) алгебраической системы

в) модели

  1.  Примерами алгебраических систем могут служить …

а)

б)

в)

г)

  1.  Примерами алгебры могут служить …

а)

б)

в)

г)

  1.  Примерами модели могут служить …

а)

б)

в)

г)

  1.  Алгебраическая система , где Σ состоит из одной бинарной операции называется …

а) группоидом

б) моделью

в) сигнатурой

г) кольцом

  1.  Группоид , где  и есть сложение по модулю 2 представлен таблицей Кэли … .

а)

0

1

0

0

1

1

1

0

б)

0

1

0

0

1

1

1

1

в)

0

1

0

0

0

1

0

1

д)

0

1

0

1

0

1

0

1

  1.  Примерами группоидов  являются … .

а)

б)

в)

г)

  1.  Группоид  называется идемпотентным, если … .

а)

б)

в)

  1.  Группоид  называется коммутативным, если … .

а)

б)

в)

  1.  Группоид  называется полугруппой или моноидом, если … .

а)

б)

в)

  1.  Группоид  называется абелевой полугруппой, если … .

а)

б)

в)

  1.  Отображение множества  в себя называется … .

а) подстановкой

б) композицией

в) перестановкой

  1.  Пусть  – множество всех подстановок множества чисел {1, 2} в себя. Тогда двойка  образует группоид. Обозначим , . Определить таблицу Кэли для группоида, который вмещает все взаимно однозначные подстановки чисел 1, 2 относительно операции композиции  … .

а)

a

b

a

a

b

b

b

a

б)

a

b

a

b

a

b

a

b

в)

a

b

a

a

a

b

b

b

д)

a

b

a

a

b

b

a

b

  1.  Алгебра  называется группой, если удовлетворяет условиям … .

а)

б)

в)

г)

  1.  Алгебра  называется абелевой группой, если удовлетворяет условиям … .

а)

б)

в)

г)

  1.  Таблица Кэли абелевой (коммутативной) группы … .

а) симметрична относительно главной диагонали

б) симметрична относительно побочной диагонали

в) несимметрична относительно главной диагонали

г) несимметрична относительно побочной диагонали

  1.  Число элементов в носителе A конечной группы называют ее … .

а) мощностью

б) порядком

в) длиной

г) рангом

  1.  Подмножество , где  группы , также может образовывать группу. В этом случае G называется  …  группы U.

а) подгруппой

б) подстановкой

в) полугруппой

  1.  Для того, чтобы непустое подмножество G группы U было подгруппой, необходимо и достаточно, чтобы … .

а)

б)

в)

г)

  1.  Алгебра  есть кольцо, если  выполняются условия … .

а)

б)

в)

г)

д)

е)

ж)

з)

  1.  Кольцо  называется абелевым, если … .

а)

б)

  1.  Кольца  , в которых для всех отличных от нуля элементов  существуют обратные, называются … .

а) телами

б) полями

в) группами

  1.  Если мультипликативная группа тела абелева, т. е.  …  , то тело называется полем.

а)

б)

  1.  Объекты, которые имеют одну и ту же форму, одинаковое назначение и, возможно, выполняют одинаковую функцию, называют … .

а) изоморфными

б) гомоморфными

в) аморфными

  1.  Два группоида  и называются … между собой, если существует такая взаимно однозначная функция , что для всех  
    .

а) изоморфными

б) гомоморфными

в) аморфными

г) полиморфными

  1.  Отображение f группоида  на  называется … , если для всех  .

а) гомоморфизмом

б) изоморфизмом

в) полиморфизмом

  1.  От гомоморфизма … взаимно однозначное соответствие.

а) требуется

б) не требуется

  1.  Правильным утверждением является … .

а) Любой изоморфизм является также гомоморфизмом

б) Любой гомоморфизм является также изоморфизмом

  1.   При гомоморфизме  и  сохраняются свойства … алгебраической операции.

а) коммутативности

б) ассоциативности

в) дистрибутивности

г) идемпотентности


ОСНОВЫ АЛГЕБРЫ ЛОГИКИ (часть 1)

Высказывательные формы. Функции алгебры логики. Основные понятия и определения. Способы задания булевых функций. Таблица истинности. Существенные и несущественные переменные. Булевы функции одной и двух переменных. Формулы. Реализация функций формулами. Равносильные формулы. Специальные разложения БФ.

  1.  Функциями алгебры логики или булевыми функциями называются …

а) , где

б)

в)

  1.  Множество всех булевых функций от n переменных обозначают …

а)

б)

в)

г)

  1.  Булева функция  существенно зависит от переменной xi, если существует такой набор значений , что …

а)

б)

  1.  Таблица истинности

x1

x2

f

0

0

0

0

1

1

1

0

1

1

1

1

соответствует функции …

а)

б)

в)

г)

д)

е)

ж)

  1.  Таблица истинности

x1

x2

f

0

0

0

0

1

1

1

0

1

1

1

0

соответствует функции …

а)

б)

в)

г)

д)

е)

ж)

  1.  Таблица истинности

x1

x2

f

0

0

1

0

1

1

1

0

1

1

1

0

соответствует функции …

а)

б)

в)

г)

д)

е)

ж)

  1.  Таблица истинности

x1

x2

f

0

0

1

0

1

1

1

0

0

1

1

1

соответствует функции …

а)

б)

в)

г)

д)

е)

ж)

  1.  Таблица истинности

x1

x2

f

0

0

1

0

1

0

1

0

0

1

1

1

соответствует функции …

а)

б)

в)

г)

д)

е)

ж)

  1.  Таблица истинности

x1

x2

f

0

0

0

0

1

0

1

0

0

1

1

1

соответствует функции …

а)

б)

в)

г)

д)

е)

ж)

  1.  Таблица истинности

x1

x2

f

0

0

1

0

1

0

1

0

0

1

1

0

соответствует функции …

а)

б)

в)

г)

д)

е)

ж)

  1.  Функция  называется двойственной к функции , если …

а)

б)

в)

  1.  Функция  называется самодвойственной, если …

а)

б)

в)

  1.  Обозначают в теории булевых функций xσ x, если σ = 1, и xσ = , если σ = 0. Символ xσ  называют … булевой функции f.

а) литералом

б) импликантой

в) термом

г) конституентой

  1.  Конъюнкцию , равную единице, если и только если xj = σj (j = 1, 2, …, n) называют …

а) литералом

б) импликантой

в) термом

г) конституентой единицы

  1.  Всякую конъюнкцию переменных булевой функции f(x1, x2, …, xn), взятых с отрицанием или без отрицания, называют …

а) элементарной

б) дизъюнктивной

в) конъюнктивной

  1.  Всякую дизъюнкцию переменных булевой функции f(x1, x2, …, xn), взятых с отрицанием или без отрицания, называют …

а) элементарной

б) дизъюнктивной

в) конъюнктивной

  1.  Дизъюнкцию  булевой функции f(x1, x2, …, xn) при m n называют …

а) дизъюнктом

б) конъюнктом

в) импликантой

  1.  Конъюнкцию элементарных дизъюнкций называют …

а) дизъюнктивной нормальной формой или ДНФ

б) конъюнктивной нормальной формой или КНФ

в) бисуммарной нормальной формой или БНФ

  1.  Сумму по модулю 2 элементарных конъюнкций называют …

а) дизъюнктивной нормальной формой или ДНФ

б) конъюнктивной нормальной формой или КНФ

в) бисуммарной нормальной формой или БНФ

  1.  Дизъюнкцию элементарных конъюнкций называют

а) дизъюнктивной нормальной формой или ДНФ

б) конъюнктивной нормальной формой или КНФ

в) бисуммарной нормальной формой или БНФ

  1.  Представление булевой функции f (x1, x2, …, xn) в виде … называют совершенной дизъюнктивной нормальной формой (СДНФ).

а)

б)

в)

г)

  1.  Представление булевой функции f (x1, x2, …, xn) в виде … называют совершенной конъюнктивной нормальной формой (СКНФ).

а)

б)

в)

г)

  1.  Представление булевой функции f (x1, x2, …, xn) в виде … называют совершенной бисуммарной нормальной формой (СБНФ).

а)

б)

в)

г)

  1.  Дизъюнкцию всех конституент единицы булевой функции f(x1, x2, …, xn) называют …

а) совершенной дизъюнктивной нормальной формой (СДНФ)

б) совершенной бисуммарной нормальной формой (СБНФ)

в) совершенной конъюнктивной нормальной формой (СКНФ)

  1.  Сумму по модулю 2 всех конституент единицы булевой функции f(x1, x2, …, xn) называют …

а) совершенной дизъюнктивной нормальной формой (СДНФ)

б) совершенной бисуммарной нормальной формой (СБНФ)

в) совершенной конъюнктивной нормальной формой (СКНФ)

  1.  Конъюнкцию всех дизъюнктов булевой функции f(x1, x2, …, xn) называют …

а) совершенной дизъюнктивной нормальной формой (СДНФ)

б) совершенной бисуммарной нормальной формой (СБНФ)

в) совершенной конъюнктивной нормальной формой (СКНФ)

  1.  Функция «штрих Шеффера» в аналитической форме записи может иметь вид …

а) (x1, x2) = {0, 1, 2}

б) (x1, x2) = (1, 1, 1, 0)

в) (x1, x2) : 1 2 0

г) (x1, x2) = {0}

д) (x1, x2) = (1, 0, 0, 0)

е) (x1, x2) : -1 2 0 1 -2 0 1 2 0

  1.  Функция «стрелка Пирса» в аналитической форме записи может иметь вид …

а) (x1, x2) = {0, 1, 2}

б) (x1, x2) = (1, 1, 1, 0)

в) (x1, x2) : 1 2 0

г) (x1, x2) = {0}

д) (x1, x2) = (1, 0, 0, 0)

е) (x1, x2) : -1 2 0 1 -2 0 1 2 0

  1.  В СДНФ функция «стрелка Пирса» имеет вид …

а)

б)

в)

г)

д)

  1.  В СКНФ функция «стрелка Пирса» имеет вид …

а)

б)

в)

г)

д)

  1.  В СБНФ функция «стрелка Пирса» имеет вид …

а)

б)

в)

г)

д)

  1.  В СДНФ функция «штрих Шеффера» имеет вид …

а)

б)

в)

г)

д)

  1.  В СКНФ функция «штрих Шеффера» имеет вид …

а)

б)

в)

г)

д)

  1.  В СБНФ функция «штрих Шеффера» имеет вид …

а)

б)

в)

г)

д)

  1.  Свойство булевых функций, именуемое поглощением конъюнкции, определяется соотношением …

а)

б)

в)

г)

  1.  Свойство булевых функций, именуемое поглощением дизъюнкции, определяется соотношением …

а)

б)

в)

г)

  1.  Свойство булевых функций, именуемое идемпотентностью дизъюнкции, определяется соотношением …

а)

б)

в)

г)

  1.  Свойство булевых функций, именуемое идемпотентностью конъюнкции, определяется соотношением …

а)

б)

в)

г)

  1.  Свойство булевых функций, именуемое ассоциативностью конъюнкции, определяется соотношением …

а)

б)

в)

г)

  1.  Свойство булевых функций, именуемое ассоциативностью дизъюнкции, определяется соотношением …

а)

б)

в)

г)

  1.  Свойство булевых функций, именуемое тавтологией или законом исключения третьего, определяется соотношением …

а)

б)

в)

г)

  1.  Свойство булевых функций, именуемое непротиворечивостью, определяется соотношением …

а)

б)

в)

г)

  1.  Свойство булевых функций, именуемое законом двойного отрицания, определяется соотношением …

а)

б)

в)

г)

д)

  1.  Свойство булевых функций, именуемое коммутативностью конъюнкции, определяется соотношением …

а)

б)

в)

г)

  1.  Свойство булевых функций, именуемое коммутативностью дизъюнкции, определяется соотношением …

а)

б)

в)

г)

  1.  Свойство булевых функций, именуемое дистрибутивностью конъюнкции относительно дизъюнкции, определяется соотношением …

а)

б)

в)

г)

  1.  Свойство булевых функций, именуемое дистрибутивностью дизъюнкции относительно конъюнкции, определяется соотношением …

а)

б)

в)

г)

  1.  Конъюнкция – это …

а) НЕ;

б) И;

в) ИЛИ.

  1.  Отрицание – это …

а) НЕ;

б) И;

в) ИЛИ.

  1.  Указать правильные утверждения:

а) f (x1, x2) = (х1х2)    дизъюнкция x1 и х2;

б) f (x1, x2) = (х1х2)    конъюнкция x1 и х2;

в) f (x1, x2) = (х1&х2)    конъюнкция x1 и х2;

г) f (x1, x2) = (х1 х2)    сложение x1 и х2  по mod 2;

д) f (x1, x2) = (х1 + х2)    импликация  x1 и х2;

е) f (x)=x    тождественная функция.


ОСНОВЫ АЛГЕБРЫ ЛОГИКИ (часть 2)

Полиномы Жегалкина. Cуществование и единственность представления булевой функции полиномом Жегалкина (теорема Жегалкина). Теоремы о полноте системы функций алгебры логики. Пять классов булевых функций: линейные функции; функции, сохраняющие нуль; функции, сохраняющие единицу; монотонные функции; самодвойственные функции. Функционально полные системы логических функций. Примеры функционально полных базисов.

  1.  Выполните подстановку операции так, чтобы равенство 1 … 1 = 0 оказалось верным.

а) логическое И

б) отрицание

в) сложение по модулю 2

г) логическое ИЛИ

  1.  Равенство (х1х3)  (х2х3) = 1  выполняется при значениях …

а) х1=1, х2=0, х3=1

б) х1=0, х2=0, х3=1

в) х1=1, х2=1, х3=1

г) х1=0, х2=0, х3=1

  1.  Является ли формула  тавтологией?

а) да

б) нет

  1.  Является ли формула  тавтологией?

а) да

б) нет

  1.  Указать, какие из формул A и B являются эквивалентными?

а) ; 

б) ; 

в) ;

г) ;

  1.  Указать, какие из формул A и B являются эквивалентными?

а) ; 

б) ; 

в) ;

  1.  Указать, какие из формул A и B являются эквивалентными?

а) ; 

б) ; 

в) ;

  1.  Указать, какие из формул A и B являются эквивалентными?

а) ; 

б) ; 

в) ;

  1.  Определением класса булевых функций, сохраняющих 0, является …

а)

б)

в)

г)

д)

  1.  Определением класса булевых функций, сохраняющих 1, является …

а)

б)

в)

г)

д)

  1.  Определением класса булевых самодвойственных функций является …

а)

б)

в)

г)

д)

  1.  Определением класса булевых монотонных функций является …

а)

б)

в)

г)

д)

  1.  Определением класса булевых линейных функций является …

а)

б)

в)

г)

д)

  1.  Для проверки полноты системы булевых функций строится …

a) диаграмма Вейча

b) машина Тьюринга

с) карта Карно

d) таблица Поста

  1.  Если булева функция f представима в виде полинома Жегалкина первой степени, то она принадлежит классу…

a) линейных функций

б) функций, сохраняющих 0

в) самодвойственных функций

г) монотонных функций

д) функций, сохраняющих 1

  1.  Для булевой функции  в общем виде полином Жегалкина имеет вид:

В соответствии с методом неопределенных коэффициентов получены следующие значения ai:

Тогда функция имеет вид …

а)

б)

в)

  1.  Булева функция  …

а) не монотонная

б) не линейная

в) не самодвойственная

г) не сохраняющая 0

д) не сохраняющая 1

  1.  Булева функция  …

а) не монотонная

б) не линейная

в) не самодвойственная

г) не сохраняющая 0

д) не сохраняющая 1

  1.  Булева функция  …

а) не монотонная

б) не линейная

в) не самодвойственная

г) не сохраняющая 0

д) не сохраняющая 1

  1.  Булева функция  …

а) не монотонная

б) не линейная

в) не самодвойственная

г) не сохраняющая 0

д) не сохраняющая 1

  1.  Булева функция  …

а) не монотонная

б) не линейная

в) не самодвойственная

г) не сохраняющая 0

д) не сохраняющая 1

  1.  Булева функция  …

а) не монотонная

б) не линейная

в) не самодвойственная

г) не сохраняющая 0

д) не сохраняющая 1

  1.  Булева функция  …

а) не монотонная

б) не линейная

в) не самодвойственная

г) не сохраняющая 0

д) не сохраняющая 1

  1.  Сколько конъюнкторов имеет схема, соответствующая функции ?

a) 3

б) 2

в) 5

г) 4

  1.  Если на вход функциональной схемы

подать и то на выходе получится …

a)

b)

c) ¬()


ОСНОВЫ АЛГЕБРЫ ЛОГИКИ (часть 3)

Минимизация булевых функций. Основные понятия и определения. Геометрический метод. Метод Квайна. Метод Квайна  Мак-Класки. Метод Блейка – Порецкого. Метод диаграмм Вейча. Метод карт Карно. Метод неопределенных коэффициентов. Минимизация конъюнктивных нормальных форм. Метод Петрика. Минимизация частично определенных булевых функций. Минимизация систем булевых функций.

  1.  Задачу упрощения булевых функций обычно формулируют в классе …

а) ДНФ

б) КНФ

в) БНФ

  1.  Имеется ДНФ булевой функции f(x1, x2, …, xn):

f(x1, x2, …, xn) = K1K2Ks,

где Ki (i = 1, 2, …, s) – элементарная конъюнкция. Число s элементарных конъюнкций называют …

а) длиной ДНФ

б) рангом ДНФ

в) термом ДНФ

  1.  ДНФ булевой функции f(x1, x2, …, xn) называют … , если она содержит наименьшее число s элементарных конъюнкций по сравнению с другими ДНФ этой же функции.

а) кратчайшей

б) сокращенной

в) тупиковой

г) минимальной

  1.  В элементарной конъюнкции

K x1σ1x2σ2 ··· xσr 

число r переменных в конъюнкции K  называют ее …

а) длиной

б) рангом

в) термом

  1.  ДНФ, представленную в виде

f(x1, x2, …, xn) = K1K2Ks,

можно охарактеризовать также числом

R = r1+r2+…+rs,

которое называют …

а) суммарной длиной

б) суммарным рангом

в) суммарным термом

  1.  ДНФ булевой функции f(x1, x2, …, xn) называют … , если ей соответствует наименьший суммарный ранг R по сравнению с другими ДНФ этой же функции.

а) кратчайшей

б) сокращенной

в) тупиковой

г) минимальной

  1.  Соотношения

,

называют …

а) законами неполного склеивания

б) законами полного склеивания

в) законами поглощения

г) законами де Моргана

  1.  Соотношения

,

называют …

а) законами неполного склеивания

б) законами полного склеивания

в) законами поглощения

г) законами де Моргана

  1.  Соотношения

,

,

,

называют …

а) законами неполного склеивания

б) законами полного склеивания

в) законами поглощения

г) законами де Моргана

  1.  Законы неполного склеивания, используемые при минимизации элементарных конъюнкций или элементарных дизъюнкций,  заданы соотношениями …

а)

б)

в)

г)

  1.  Законы полного склеивания, используемые при минимизации элементарных конъюнкций или элементарных дизъюнкций,  заданы соотношениями …

а)

б)

в)

г)

  1.  Законы поглощения, используемые при минимизации элементарных конъюнкций или элементарных дизъюнкций,  заданы соотношениями …

а) ,

б) ,

в) ,

г)

д)

е)

  1.  Булева функция g(x1, x2, …, xn) называется импликантой функции f(x1, x2, …, xn), если …

а) функция g(x1, x2, …, xn) = 0 на тех же наборах, на которых f(x1, x2, …, xn) = 0

б) для любого набора, на котором g(x1, x2, …, xn) = 1, справедливо f(x1, x2, …, xn) = 1

в) функция g(x1, x2, …, xn) содержит наименьшее число элементарных конъюнкций, чем функция f(x1, x2, …, xn)

  1.  Если функция f(x1, x2, …, xn) и функции gi(x1, x2, …, xn) заданы таблицей истинности:

x3x2x1

f  

g1

g2

g3

g4

g5

g6

g7

000

0

0

0

0

0

0

0

0

001

0

0

0

0

0

1

0

0

010

0

0

0

0

0

0

0

0

011

1

0

0

0

1

1

1

1

100

0

0

0

0

0

0

0

0

101

0

0

0

0

0

0

0

0

110

1

0

1

1

0

0

1

1

111

1

1

0

1

0

0

0

1

то импликантами функции f(x1, x2, …, xn) являются …

а) g1(x1, x2, …, xn)

б) g2(x1, x2, …, xn)

в) g3(x1, x2, …, xn)

г) g4(x1, x2, …, xn)

д) g5(x1, x2, …, xn)

е) g6(x1, x2, …, xn)

ж) g7(x1, x2, …, xn)

  1.  Имеется элементарная конъюнкция

K x1σ1x2σ2 ··· xσr .

Конъюнкцию, полученную из K удалением некоторых переменных, называют …

а) собственной частью

б) термом

в) импликантой

г) простой импликантой

  1.  Собственными частями конъюнкции

являются конъюнкции …

а) ,

б) ,

в) ,

г)

д)

е)

  1.  Элементарная конъюнкция

K x1σ1x2σ2 ··· xσr

называется … булевой функции f(x1, x2, …, xn), если K является импликантой функции f(x1, x2, …, xn) и никакая собственная часть K не является импликантой f(x1x2, …, xn).

а) конституентой

б) простой импликантой

в) простым термом

  1.  Дизъюнкция всех простых импликант функции f(x1, x2, …, xn) называется … этой функции.

а) сокращенной ДНФ

б) кратчайшей ДНФ

в) совершенной ДНФ

г) тупиковой ДНФ

  1.  Дизъюнкция совокупности простых импликант функции f(x1, x2, …, xn) такая, что удаление из нее любой импликанты приводит к отсутствию покрытия дизъюнкций оставшихся импликант всех единиц функции, называют … функции f(x1, x2, …, xn).

а) сокращенной ДНФ

б) кратчайшей ДНФ

в) совершенной ДНФ

г) тупиковой ДНФ

  1.  Любая минимальная ДНФ булевой функции f(x1, x2, …, xn) является …

а) сокращенной ДНФ

б) кратчайшей ДНФ

в) совершенной ДНФ

г) тупиковой ДНФ

  1.  Общая схема минимизации булевых функций включает следующие этапы:

а) построение сокращенной ДНФ

б) нахождение тупиковой ДНФ

в) построение совершенной ДНФ

г) нахождение минимальной ДНФ

д) построение совершенной КНФ

  1.  Все методы построения сокращенной ДНФ основаны на выполнении правил …

а) склеивания

б) поглощения

в) дизъюнкции

г) конъюнкции

д) отрицания

  1.  В геометрическом методе минимизации для булевой функции f(x1, x2, x3) конституенте единицы соответствует …

а) вершина единичного куба

б) ребро единичного куба

в) грань единичного куба

  1.  В методе Квайна – Мак-Класки минимизации булевой функции f(x1, x2, x3, x4) = (0, 6, 7, 8, 12, 13, 14, 15) разбиение на группы имеет вид …

а)

0000

1-я группа

1000

2-я группа

0110

1100

3-я группа

0111

1101

1110

4-я группа

1111

5-я группа

б)

0000

1-я группа

0001

2-я группа

0101

1100

3-я группа

0111

1101

1011

4-я группа

1111

5-я группа

в)

0000

1-я группа

0010

1000

2-я группа

0110

1100

3-я группа

0111

1101

1011

4-я группа

  1.  В методе Квайна – Мак-Класки минимизации булевой функции f(x1, x2, x3, x4) = (0, 6, 7, 8, 12, 13, 14, 15) в результате склеивания соседних конституент получают таблицу …

а)

0000*

х000

1-я группа

1000*

1х00

2-я группа

0110*

1100*

011х

х110

11х0

110х

3-я группа

0111*

1101*

1110*

х111

11х1

111х

4-я группа

1111*

б)

0000*

000х

1-я группа

0001*

0х01

2-я группа

0101*

1100*

х101

110х

3-я группа

0111*

1101*

1011*

х111

11х1

1х11

4-я группа

1111*

в)

0000*

00х0

х000

1-я группа

0010*

1000*

0х10

1х00

2-я группа

0110*

1100*

011х

110х

3-я группа

0111*

1101*

1011

  1.  В методе Квайна – Мак-Класки минимизации булевой функции f(x1, x2, x3, x4) = (0, 6, 7, 8, 12, 13, 14, 15) в результате склеивания соседних конституент получают таблицу …

х000

1х00

011х*

х110*

11х0*

110х*

х11х

11хх

1-я группа

х111*

11х1*

111х*

которой соответствует сокращенная ДНФ …

а)

б)

в)

  1.  В методе минимизации Квайна и Квайна – Мак-Класки для получения минимальной ДНФ строится импликантная матрица. Для булевой функции f(x1, x2, x3, x4) = (0, 6, 7, 8, 12, 13, 14, 15) после этапа построения сокращенной ДНФ импликантная матрица имеет вид:

Простые

импликанты

Конституенты единицы

0000

1000

0110

1100

0111

1101

1110

1111

х

х

х

х

х

х

х

х

х

х

х

В этом случае минимальная ДНФ …

а)

б)

в)

  1.  Метод Блейка-Порецкого позволяет строить сокращенную ДНФ булевой функции f(x1, x2, …, xn), если она задана …

а) произвольной ДНФ

б) совершенной ДНФ

в) совершенной КНФ

г) совершенной БНФ

  1.  Задана импликантная матрица булевой функции f(x1, x2, x3, x4) по методу Петрика.

yi

Простые

импликанты

Конституенты единицы

0001

0011

0101

0111

1110

1111

y1

х

х

х

х

y2

х

х

y3

х

х

Определенная по этому методу минимальная ДНФ …

а)

б)

в)

  1.  Для нахождения по методу Петрика минимальной ДНФ булевой функции f(x1, x2, x3, x4), представленной импликантной матрицей, каждой простой импликанте поставлена в соответствие булева переменная yi. Конъюнкции элементарных дизъюнкций, построенные по правилам метода Петрика, имеют вид

 

и определяют …

а) 5 тупиковых ДНФ

б) 7 тупиковых ДНФ

в) 4 тупиковых ДНФ

  1.  Если сокращенная ДНФ булевой функции f(x1, x2, …, xn) не содержит отрицаний переменных, то …

а) она является единственной минимальной формой этой функции

б) импликантную матрицу не строят

в) минимальную ДНФ определяют методом Петрика

  1.  Сокращенная ДНФ монотонной булевой функции f(x1, x2, …, xn) …

а) не содержит отрицаний переменных

б) является единственной минимальной формой этой функции

в) не требует построения импликантной матрицы

г) требует применения метода Петрика для определения минимальной ДНФ

  1.  Диаграмма Вейча для функции двух переменных имеет вид …

а)

0

1

y

0

1

x

б)

0

1

y

0

1

x

в)

0

1

y

0

1

x

  1.  Сокращенная ДНФ булевой функции, представленной на карте Карно

00

01

11

10

x3x4

00

1

1

1

01

1

1

11

1

1

10

1

1

1

x1x2

имеет вид …

а)

б)

в)

  1.  Алгоритм поиска минимальной ДНФ частично определенной булевой функции f(x1, x2, …, xn) включает следующие действия …

а) найти сокращенную ДНФ функции доопределением единицами f(x1, x2, …, xn) на всех неопределенных наборах

б) найти сокращенную ДНФ функции доопределением нулями f(x1, x2, …, xn) на всех неопределенных наборах

в) выбрать минимальную ДНФ по импликантной матрице с полностью определенными единичными наборами

в) выбрать минимальную ДНФ по импликантной матрице с учетом полностью определенных и доопределенных единичных наборов

  1.  Сокращенная ДНФ частично определенной булевой функции, представленной на карте Карно

0

1

x2

0

-

1

1

1

0

x1

имеет вид …

а)

б)

в)


Основы теории графов

  1.  Задан граф G(V,E):

Несмежными рёбрами являются…

а) е1,е2; е2,е3; е3,е4; е4,е1;

б) е1,е5; е2,е5; е3,е5; е4,е5;

в) е1,е3; е2,е4.

  1.  Задан граф G(V,E):

Смежными рёбрами являются…

а) е1, е2; е2,е3; е3,е4; е4,е1;

б) е1,е5; е2,е5; е3,е5; е4,е5;

в) е1,е3; е2,е4.

  1.  Количество рёбер инцидентных вершине v называют степенью d(v) или  валентностью, где p – число вершин…

а) d(v) ≥ 0;

б) d(v) ≤ р-1;

в) d(v) ≤ р(р-1)

  1.  Если степень вершины равна нулю, d(v)=0, то вершину называют…

а) концевой;

б) начальной;

в) изолированной.

  1.  Если степень вершины равна 1, то вершину называют…

а) концевой;

б) начальной;

в) изолированной.

  1.  Задан граф G(V,E):

В графе G(V,E) маршрут (v1-v3-v1,v4) – это…

а) маршрут, но не цепь;

б) цепь, но не простая;

в) простая цепь.

  1.  Задан граф G(V,E):

В графе G(V,E) маршрут (v1-v3-v5-v2-v3-v4) – это…

а) маршрут, но не цепь;

б) цепь, но не простая;

в) простая цепь.

  1.  Задан граф G(V,E):

В графе G(V,E) маршрут (v1-v4-v3-v2-v5) – это…

а) маршрут, но не цепь;

б) цепь, но не простая;

в) простая цепь.

  1.  Задан граф G(V,E):

В графе G(V,E) маршрут (v1-v3-v5-v2-v3-v4-v1) – это…

а) простая цепь;

б) цикл, но не простой цикл;

в) простой цикл.

  1.  Задан граф G(V,E):

В графе G(V,E) маршрут (v1-v3-v4) – это…

а) простая цепь;

б) цикл, но не простой;

в) простой цикл.

  1.  Длина кратчайшей цепи между вершинами u, v (<u,v>) называется…

а) диаметр;

б) ярус;

в) расстояние.

  1.  В графе G(V,E)  наибольшая длина из кратчайших путей называется…

а) диаметр;

б) ярус;

в) расстояние.

  1.  Множество вершин, находящихся на одинаковом расстоянии от вершины называется…

а) диаметр;

б) ярус;

в) расстояние.

  1.  Полным  графом с р вершинами, обозначенным Кр и имеющим максимально возможное число рёбер является…

а) q(Кр)=p-1/2;

б) q(Кр)=p(p-1);

в) q(Кр)=p(p-1)/2.

  1.  Если в орграфе полустепень захода вершины d+(v)=0, то вершина v

а) источник;

б) сток;

в) сеть.

  1.  Если в орграфе полустепень исхода вершины d(v)=0, то вершина v

а) источник; б) сток; в) сеть.

  1.  Заданы диаграммы графов:

Изоморфными графами являются …

а) G1, G2, G3;      b) G1,G2;      c) G2, G3;      d) G1, G3.

  1.  Количество рёбер d(), инцидентных вершине , называется …

a) степенью;      b) маршрутом;        c) инвариантом.

  1.  По теореме Эйлера сумма степеней вершин графа равна:

a) ∑d() = 2q;     b) ∑d() = p(p-1);    c) ∑d() = p(p-1) / 2;

  1.  Задан граф G(V1,E1).

Дополнением G1(V1,E1) является граф …

1    

  1.  Заданы графы G1(V1,E1), G2(V2,E2):

Объединением графов является граф G (V,E): G1(V1,E1) U G2(V2,E2) …

    

4. нет правильного ответа

  1.  Дан граф G1(V1,E1) и граф G2(V2,E2):

Соединением графов G1 и G2 является граф G(V,E) = G1(V1,E1) + G2(V2,E2) …

3.

  1.  Дан граф G1(V1,E1):

Удаление вершины 2 приводит к графу G(V,E) …

2.  

  1.  Дан граф G1(V1,E1):

Удаление ребра (2,4) приводит к графу G(V,E) …

1.

  1.  Дан граф G(V,E):

Добавление ребра е в граф G1(V1,E1) даёт граф G2(V2,E2), где V2:=V1&E2=E1U {e}…

4. нет правильного ответа.

  1.  Дан граф G(V,E):

Стягивание подграфа А графа G1(V1,E1) даёт граф G2(V2,E2), где V2:=(V1/А)U{} &

E2 := E1 /{e = (, ω)| є A V ω є A} U { e = (, )| є Г (А) / A} …

3.

  1.  Дан граф G(V,E):

Размножение вершины V графа G1(V1,E1) даёт граф G2(V2,E2), где

V2 := V1 U{'} & E2 := E1 U {(, ')} U { e = (, ')|  є F+ ()}

4. нет правильного ответа

  1.  Дан граф G(V,E):

Матрицей смежности вершин является …

    

4) нет правильного ответа.

  1.  Дан граф G(V,E):

Матрицей смежности рёбер является …

   

4) нет правильного ответа

  1.  Дан граф G(V,E):

Матрицей инцидентности является …

   

4) нет правильного ответа.

  1.  Если в графе G(V, E)удаление вершины Vi увеличивает число компонент связности, эту вершину называют …

а)  изолированная вершина;

б)  точка сочленения;

в)  заходящая вершина;

г)  исходящая вершина.

  1.  Пусть p - число вершин, q - число ребер, k - число компонент связности графов. Тогда  справедливы  следующие  отношения:

а) q

б)  pk 

в) q

г) p (p-k)

  1.  Если G состоит из одной компоненты связности K(G)= 1, то граф называется:

а) точкой сочленения;

б) мостом;

в) блоком;

г) связным графом.

  1.  Ребро, удаление которого увеличивает число компонент связности, называют:

а) мостом;

б) насыщенное ребро;

в) ненасыщенное ребро;

г) нагруженное ребро.

  1.  Связный граф, не имеющий точек сочленения, называют:

а) тривиальный;  

б) блок;

в) Эйлеров граф;

г) Гамильтонов  граф.

  1.  Наименьшее число вершин, удаление которых  приводит к несвязному или тривиальному графу, называется:

а) реберной связностью;

б) вершинной связностью;

в) точка сочленения;

г) изолированная точка.

  1.  Максимальное количество ресурса, которое  может пропустить в единицу времени по заданному ребру называется:

а) пропускной способностью;

б) потоком по этому ребру;

в) потоком по сети;

  1.  Количество ресурса, проходящее через ребро в единицу времени называется:

а) потоком по этому ребру;

б) насыщенным;

в) ненасыщенным;

г) потоком по сети.

  1.  Если  граф G несвязный, тогда он имеет следующую характеристику вершинной связности:

а) λ(G) = 1

б) λ(G) = 0

в) λ(G) = -1

г) λ(G) = 2

  1.  Если на сети задан поток x ={xij}<cij, то ребро между вершиной i-й и j-й называется …

а) поток по сети;

б) насыщенным;

в) ненасыщенным;

г) поток по этому ребру.

  1.  Если на сети задан поток x ={xij} и если поток xij  по нему совпадает с пропускной способностью, то ребро называется …

а) насыщенным;

б) потоком по сети;

в) ненасыщенным;

г) разрезом на сети.

  1.  Если задан орграф G (V, E),  в котором дуги помечены числами, то  эти числа называются …

а) длинами;

б) весами;

в) пропускной способностью.

  1.  Алгоритм Флойда находит:

а) кратчайший путь между двумя данными вершинами орграфа, если длины дуг отрицательны;

б) кратчайшие пути между всеми парами вершин в орграфе;

в) кратчайший путь между двумя данными вершинами в орграфе, если длины дуг неотрицательны.

  1.  Алгоритм Дейкстры находит:

а) кратчайшие пути между всеми парами вершин в орграфе;

б) кратчайший путь между двумя данными вершинами орграфа, если длины дуг неотрицательны;

в) кратчайший путь между двумя данными вершинами орграфа, если длины дуг отрицательны.

  1.  Совокупность ребер (i,j), начальные вершины которых  принадлежит подмножеству А, а конечные подмножеству В транспортной сети, и обозначается  R (A/B) называется …

а) пропускной способностью разреза;

б) разрезом сети;

в) потоком по сети.

  1.  Ориентированное дерево, в котором полустепень исхода любой его вершины не больше 2 называют:

1) полным

2) бинарным

3) выровненным

4) сбалансированным

  1.  Ордерево называется … , если все узлы, степень которых меньше 2, располагаются на одном или двух последних уровнях.

1) выровненным

2) сбалансированным

3) одноуровненным

4) полным

  1.  Каким обязательно должно быть Выровненное дерево?

1) связным

2) симметричным

3) несимметричным

4) многосвязным

  1.  Как называют бесконтурный ориентированный граф, у которого полустепень захода любой вершины не больше 1 и существует ровно одна вершина, называемая корнем ориентированного дерева, полустепень захода которой равна 0?

1) неориентированное дерево

2) ориентированное дерево

3) сбалансированное дерево

  1.  Какое бинарное дерево называют сбалансированным?

1) если все листья находятся на одном уровне

2) если полустепень исхода любой его вершины не больше 2

3) если для любого узла высота левого и правого поддеревьев отличается не более чем на единицу.

  1.  Сбалансированным по высоте деревом называется также:

1) выровненным

2) подровненным

3) АВЛ-деревом

  1.  Для сбалансированного по высоте бинарного дерева:

1) h < 2 log2 p.

2) h <  log2 p

3) h < 2 lg p

  1.  Какие основные структуры данных используются для представления ассоциативной памяти?

1) неупорядоченный массив

2) упорядоченный массив

3) сбалансированные деревья

4) таблица расстановки

  1.  Какое дерево оказывается во многих случаях наилучшим вариантом представления дерева сортировки?

1) сбалансированное дерево.

2) выровненное

3) полное

  1.  Как еще называется  таблица расстановки в ассоциативной памяти?

1) хэш-таблица

2) ассоциативная таблица

3) таблица данных

  1.  По какой формуле рассчитывается сумма степеней вершин графа?

А)

 

Б)

  1.  По какой формуле рассчитывается сумма полу степеней вершин орграфа?

А)

Б)

  1.  Какой цикл называется гамильтоновым циклом?

1) содержащий все вершины графа (по одному разу);

2) содержащий все вершины графа (по нескольку раз);

3) содержащий все ребра графа (по одному разу);

4) содержащий все ребра графа (по нескольку раз);

  1.  Какой цикл называется эйлеровым циклом

1) цикл содержащий все рёбра графа по несколько раз;

2) цикл содержащий все рёбра графа;

3) цикл содержащий ребро графа;

4) цикл, содержащий все рёбра графа по одному разу;

  1.  Название «гамильтонов цикл» произошло от задачи…

1) «Овальное путешествие»

2) « Путешествие вокруг земли»

3) «Кругосветное путешествие»

4) «Круговое путешествие»


Конечные автоматы

  1.  Конечный автомат Мура определяется кортежем …

а)

б)

в)

г)

  1.  Конечный автомат Мили определяется кортежем …

а)

б)

в)

г)

  1.  Конечный автомат может быть задан …

а) автоматной таблицей

б) графом переходов

в) матрицей переходов

г) таблицей истинности

  1.  Число вершин в графе переходов автомата Мили определяется …

а) мощностью входного алфавита X

б) мощностью выходного алфавита Y

в) мощностью множества состояний S

г) функцией выходов λ

д) функцией переходов δ

  1.  Число вершин в графе переходов автомата Мура определяется …

а) мощностью входного алфавита X

б) мощностью выходного алфавита Y

в) мощностью множества состояний S

г) функцией выходов λ

д) функцией переходов δ

  1.  Характеристические функции λ и δ в графе переходов автомата Мили обозначают …

а)

б)

в)

г)

  1.  Характеристические функции λ и δ в графе переходов автомата Мура обозначают …

а)

б)

в)

г)

  1.  Абстрактный конечный автомат представляют …

а) черным ящиком

б) одним входом

в) одним выходом

г) комбинационной схемой

д) памятью

е) несколькими входами

ж) несколькими выходами

  1.  Структурный  конечный автомат представляют …

а) черным ящиком

б) одним входом

в) одним выходом

г) комбинационной схемой

д) памятью

е) несколькими входами

ж) несколькими выходами

  1.  Эквивалентные состояния конечного автомата обладают свойствами …

а) рефлексивности

б) симметричности

в) транзитивности

г) полноты

д) антисимметричности

е) антирефлексивности

  1.  Автоматной таблице конечного автомата Мили

δ

1

2

3

λ

1

2

3

x1

2

1

3

x1

1

2

2

x2

1

3

2

x2

1

1

2

соответствует граф переходов …

а)

б)

в)

  1.  Автоматной таблице конечного автомата Мили

δ

1

2

3

λ

1

2

3

x1

2

1

2

x1

2

2

2

x2

1

3

3

x2

1

1

1

соответствует граф переходов …

а)

б)

в)


Дискретная математика

(вопросы к экзамену)

  1.  Основные понятия теории множеств. Способы задания множеств.
  2.   Операции над множествами. Диаграммы Венна.
  3.   Свойства теоретико-множественных операций. Представление множеств в ЭВМ.
  4.  Отношения: упорядоченные пары, прямое произведение множеств. Многоместные отношения.
  5.   Композиция отношений. Степень отношений. Ядро отношения.
  6.  Свойства отношений. Представление отношений в ЭВМ.
  7.  Специальные классы отношений. Отношение эквивалентности и разбиения.
  8.  Отношения порядка. Минимальные элементы. Теорема о существовании минимального элемента. Алгоритм топологической сортировки. 
  9.  Замыкание отношений. Операции над отношениями. Транзитивное замыкание, рефлексивное замыкание. Алгоритм Уоршалла вычисления транзитивного замыкания.
  10.  Функции и отображения. Инъекция, сюръекция, биекция. Представление функций в ЭВМ.
  11.  Операции. Свойства бинарных операций: ассоциативность, коммутативность, дистрибутивность слева и справа. Способы задания операций. Таблица Кэли.
  12.  Гомоморфизмы. Алгебраическая система. Проверка условия гомоморфизма.
  13.  Изоморфизмы. Изоморфные алгебры. Изоморфизм модели. Примеры изоморфных алгебр.
  14.  Нечеткие множества. Основные понятия и определения. Основные характеристики.
  15.  Теоретико-множественные операции над нечеткими множествами. Графическое представление операций.
  16.  Алгебраические операции над нечеткими множествами
  17.  История теории графов. Основное определение графов. Смежность. Изоморфизм графов.
  18.   Элементы графов. Подграфы. Валентность. Теорема Эйлера.
  19.  Маршруты в графах. Цепи. Циклы. Расстояние между вершинами. Связность.
  20.  Виды графов: тривиальные и полные графы, двудольные графы, орграфы и сети. Операции над графами.
  21.  Представление графов в ЭВМ. Матрица смежности, матрица инцидентности. Списки смежности вершин.
  22.  Компоненты связности и объединение графов. Оценка числа ребер через число вершин и число компонентов связности. Вершинная и реберная связность. Мосты и блоки.
  23.  Потоки в сетях. Пример сети с потоками. Определение потока. Разрезы.
  24.  Теорема Форда и Фалкерсона. Алгоритм нахождения максимального потока.
  25.  Кратчайшие пути. Алгоритм Флойда. Алгоритм Дейкстры. Методы систематизации обхода вершин: поиск в ширину, поиск в глубину.
  26.  Свободные деревья. Основные свойства деревьев.
  27.  Ориентированные, упорядоченные и бинарные деревья.
  28.  Представление в ЭВМ свободных, ориентированных и упорядоченных деревьев.
  29.  Применение деревьев в программировании. Ассоциативная память. Выровненные деревья. Сбалансированные деревья.
  30.  Минимальный каркас. Схемы алгоритмов построения минимального каркаса: алгоритм Краскала, ближайшего соседа.
  31.  Циклы и коциклы. Эйлеровы циклы. Гамильтоновы циклы. Теорема Дирака.
  32.  Раскраска графов. Хроматическое число. Планарные графы. Укладка графов. Алгоритм раскрашивания.
  33.  Переключательные функции. Основные понятия и определения. Способы задания переключательных функций. Таблица истинности.
  34.  Переключательные функции одного и двух аргументов. Условие равенства логических функций.
  35.  Неполностью определенные (частные) ПФ.
  36.  Принцип двойственности. Двойственные, самодвойственные ПФ. Нормальные формы. Разложение булевых функций по переменным.
  37.  Совершенные нормальные формы. СДНФ. Теорема о единственности СДНФ. СКНФ. Теорема о единственности СКНФ.
  38.  Алгоритм построения ДНФ. Алгоритм построения КНФ
  39.  Понятие о минимизации ПФ. Геометрическая интерпретация минимизации.
  40.  Минимизация ПФ и неполностью определенных ПФ. Метод неопределенных коэффициентов.
  41.  Алгебра Жегалкина. Свойства булевых функций.
  42.  Пять классов переключательных функций. Функционально замкнутые классы булевых функций.
  43.  Функциональная полнота систем булевых функций. Теорема Поста. Примеры функционально полных базисов.
  44.  Теорема о функциональной полноте. Основная функционально полная система логических функций.
  45.  Законы алгебры логики в ОФПС и их следствия.
  46.  Задачи анализа и синтеза логических схем.
  47.  Теория автоматов. Основные понятия теории конечных автоматов.
  48.  Способы задания абстрактных автоматов: таблица переходов, граф переходов, матрица переходов.
  49.  Автоматы Мили и Мура. Частичный автомат.
  50.  Синтез автоматов. Абстрактный уровень проектирования автомата.


 

А также другие работы, которые могут Вас заинтересовать

62703. Музыкальное путешествие в весенний лес 21.64 KB
  Ребята Послушайте загадку: Зажурчали ручейки в овражке Прилетают с юга пташки Греет солнышко с утра В гости к нам пришла Дети: Весна Ждёт нас в гости друг зелёный Ждут берёзки липы клёны Травы птицы и цветы Небывалой красоты Сосны ели до небес Ждёт...
62704. Урок музыки - основная форма организации начального процесса в музыкальном воспитании 17.53 KB
  Цель урока музыки воспитание гармонически развитой личности. В основе построения любого школьного урока лежат: Закономерности педагогического процесса А психолого-педагогические...
62706. Русские народные инструменты 17.47 KB
  Какую информацию получили из этой песни о наших предках славянах Срежу я с берёзы три пруточка Сделаю из них я три годочка Как вы думаете каким был первый музыкальный инструмент Какие знаете русские народные инструменты...
62708. WE AND MASS-MEDIA 24.27 KB
  We know about politics, crimes, cultural and sporting events. We can hardly imagine our life without Mass-Media. Mass-media has changed our lives in many ways. It has brought many positive things but also many negative things.
62711. There’s a good film on at 4.30 55.53 KB
  Почитайте вместе, потренируйте, обращаясь к детям “Hi, Fox!” (тот, у кого лиса – должен отреагировать) и, убедившись, что реплики достаточно усвоены, вызывайте к доске рассказывать диалог, попросив изменять время на своё.