Алгебры и алгебраические структуры. булева алгебра
ТЕМАТИЧЕСКАЯ СТРУКТУРА ТЕСТОВЫХ МАТЕРИАЛОВ
МОДУЛЬ 1 (115 вопросов)
ОБЩИЕ ВОПРОСЫ ТЕОРИИ СИСТЕМ (25 вопросов)
ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ (35 вопросов)
АЛГЕБРЫ И АЛГЕБРАИЧЕСКИЕ СТРУКТУРЫ. БУЛЕВА АЛГЕБРА (30 вопросов)
ЛОГИЧЕСКИЕ ИСЧИСЛЕНИЯ (25 вопросов)
МОДУЛЬ 2 (85 вопросов)
ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ (40 вопросов)
СЕТИ ПЕТРИ (15 вопросов)
IDEF-ТЕХНОЛОГИИ (15 вопросов)
МОДЕЛИ ИС НА ОСНОВЕ ТЕХНОЛОГИЙ "КЛИЕНТ-СЕРВЕР" (15 вопросов)
МОДУЛЬ 1
ОБЩИЕ ВОПРОСЫ ТЕОРИИ СИСТЕМ
1. Система – это
þ упорядоченная совокупность взаимосвязанных и взаимодействующих элементов, образующих единое функциональное целое, предназначенное для решения определенных задач (достижения определенной цели).
þ совокупность сущностей (объектов) и связей между ними, организованных некоторым образом в единое целое и противопоставляемое внешней среде.
þ совокупность (множество) отдельных объектов, выполняющих преобразование энергии, материалов или информации с целью замены или облегчения физического и умственного труда человека.
o множество объектов, объединенных общей целью и сходными функциями.
2. Дайте определение понятию система
þ система – это комбинация взаимодействующих элементов, организованная для достижения одной или нескольких поставленных целей.
o система – это совокупность взаимосвязанных и взаимодействующих элементов.
o система ‑ это иерархическая структура множества взаимосвязанных элементов.
3. Совокупность (множество) отдельных объектов, выполняющих преобразование энергии, материалов или информации с целью замены или облегчения физического и умственного труда человека, называется
þ системой.
o информационной системой.
o сложной системой.
o сложной информационной системой.
4. Система – это
þ совокупность взаимосвязанных объектов, которые называются элементами системы.
o совокупность отдельных множеств, элементы которых, в свою очередь, являются множествами.
o совокупность отдельных множеств, элементы которых представляют собой взаимосвязанные объекты.
o набор отдельных элементов и их функций.
5. Архитектура системы – это
þ организационная структура системы или ее компонента.
þ распределение компонентов системы по уровням иерархии.
o структурная модель, включающая в себя технические средства и средства связи
6. Что такое модель системы?
þ математическое или физическое представление взаимосвязей системы.
þ представление одного или нескольких аспектовсистемы
o представление или идеализация выбранных аспектов структуры, поведения, функционирования или иных характеристик процесса, концепции или системы реального мира.
7. Что такое информационная система (ИС)?
þ автоматизированная и/или автоматическая система с набором технических, программных и информационных средств, предназначенная для представления пользователям информационных услуг.
o система, ориентированная на сбор и хранение текстовой и/или фактографической информации.
o целостное, упорядоченное множество взаимосвязанных и целенаправленно взаимодействующих информационных элементов.
8. Информационная система – это
þ организационно-упорядоченная взаимосвязанная совокупность средств, и методов информационных технологий, а также используемых для хранения, обработки и выдачи информации в интересах достижения поставленной цели.
þ средой, составляющими элементами которой являются компьютеры, компьютерные сети, программные продукты, БД, люди, различного рода технические и программные средства связи и т.д.
o совокупность ЭВМ, информации и, алгоритмов ёё переработки, организованных в программную систему.
9. К основным задачам информационных систем можно отнести:
þ поиск, обработку и хранение информации.
þ анализ и прогнозирование потоков информации.
o непрерывное воспроизводство информации.
10. Комплекс, в состав которого входит вычислительное и коммуникационное оборудование, программное обеспечение, лингвистические средства и информационные ресурсы, системный персонал, называется
þ информационной системой.
o информационно-справочной системой.
o информационно-организационной системой.
o информационно-ориентированной системой.
11. К основной группе показателей качества ИС относятся
þ множество временных показателей.
þ показателей связности.
þ множество эксплуатационных показателей.
o точностных показателей.
12. К информационным ресурсам относятся
þ данные для систем баз данных.
þ документы для систем текстового поиска.
þ НТМL-страницы или ХМL-документы для поисковых систем.
o объекты для объектно-ориентированных систем.
13. Данные для систем баз данных, документы для систем текстового поиска, НТМL-страницы или ХМL-документы для поисковых систем объединяются общим понятием
þ информационный ресурс.
o базовый ресурс.
o системный ресурс.
14. Что такое информационный процесс?
þ информационным называют процесс, возникающий в результате установления связи между двумя объектами материального мира: источником информации и ее приемником.
o множество взаимосвязанных действий, преобразующих входные элементы в выходные результаты.
o это процесс подготовки и сопровождения целенаправленного воздействия на объекты реального мира.
15. Любой процесс, в котором присутствует хотя бы один из элементов: приём, передача информации, ее хранение, обработка, выдача пользователю называется
þ информационным процессом.
o базовым процессом информационной системы.
o элементарным процессом информационной системы.
o основным процессом информационной системы.
16. Под информацией понимается
þ сведения об окружающем мире, протекающих в нем процессах.
þ совокупность сообщений, сведений, сигналов о множестве состояний объектов и процессов реального мира.
o отражение ближайшей среды с сигналами системы управления.
17. Для характеристики информации пользуется
þ количественная мера Шеннона.
o качественная мера Колмогорова.
o уровень информационного сигнала.
o частота информационного сигнала.
18. Двоичной единицей количества информации является
þ бит.
o байт.
o килобайт.
o машинное слово.
19. Что такое канал передачи данных?
þ средства обмена данными, включающие аппаратуру окончания канала данных и линию передачи данных.
o средства, которые используются в информационных сетях для распределения сигналов в нужном направлении.
o совокупность технических средств, обеспечивающих независимую передачу сообщений от передатчика к приемнику по физическим линиям связи.
20. Какое из представленных определений является определением информационной сети?
þ информационная сеть - коммуникационная сеть, в которой продуктом генерирования, переработки, хранения и использования является информация.
o сеть, в состав которой входит вычислительные средства и устройства передачи и приема данных, передаваемых по сети.
o система, состоящая из объектов, осуществляющих функции генерации, преобразования, хранения и линий связи.
21. Под графическим представлением ИС понимается
þ описание системы средствами теории графов в виде совокупности двух классов объектов: вершин и соединяющих их линий – рёбер или дуг.
þ описание процессов системы средствами теории графов в виде совокупности двух классов объектов: вершин и соединяющих их линий – рёбер или дуг.
o описание процессов системы в форме графиков, гистограмм, диаграмм.
22. Системы, которые поддерживают информационную модель предметной области и позволяют решать на её основе некоторые классы задач управленческого, исследовательского, конструкторского или иного характера, называются
þ информационными системами вместе с приложениями.
þ системами обработки данных.
o системами информационного управления.
o информационными системами.
23. К процессам, обеспечивающим работу ИС любого назначения, можно отнести:
þ ввод информации из внешних или внутренних источников.
þ обработку входной информации и представление ее в удобном виде.
þ вывод информации для представления потребителям или передачи в другую систему.
o передачу информации по каналам связи.
o складирование информации в специальных хранилищах.
24. Хранилище данных
þ очень большая предметно-ориентированная корпоративная БД, специально разработанная и предназначенная для подготовки отчётов, анализа бизнес-процессов с целью поддержки принятия решений в организации.
o БД содержащая информацию, относящуюся к управленческим аспектам деятельности организации.
o БД содержащая информацию, относящуюся к технологическим аспектам деятельности организации.
o совокупность всех БД предприятия.
25. Источниками данных для ИС могут быть:
þ традиционные системы регистрации операций (БД).
þ отдельные документы.
þ наборы данных.
o метаданные обо всех событиях.
o внутренние и внешние генераторы данных.
ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ
26. Пустое множество ‑
þ множество, не содержащее ни одного элемента; обозначается Æ или {0}.
þ возникает из потребности, чтобы результат всякой операции над множествами был также множеством
o тождественно равно понятию "нуль"....
o множество, содержащее бесконечное число нулевых элементов.
27. Пустое множество ‑
þ множество, не содержащее ни одного элемента;
þ множество, содержащее только один нулевой элемент, обозначается {0}.
o множество, содержащее только один и более нулевых элементов, обозначается {0 …}.
o множество, содержащее только нулевые элементы.
28. Несчетное множество -
þ понятие теории множеств; бесконечное множество, мощность которого больше, чем мощность счетного множества; например, множество всех действительных чисел ‑ несчетное множество.
o понятие теории множеств; множество, содержащее бесконечное число ненулевых элементов.
o понятие теории множеств; множество, содержащее число элементов в диапазоне [-¥; +¥]
o понятие теории множеств; множество, содержащее число элементов в диапазоне [0; +¥]
o понятие теории множеств; множество, содержащее число элементов в диапазоне [-¥; 0]
29. Дано множество M = {a,b,{c,d},e}. Какие из утверждений верны?
þ {a, e}ÎM
o {c, d}ÎM
o cÎM
o {d}ÎM
30. Мощность множества M = {a,b,{c,d},e} равна
þ М=|4|
o М=|5|
o М=|0|
o М=|1|
31. Формула мощности булеана В(А)
þ |B(A)| = 2|A|
o |B(A)| = |A||
o |B(A)| = 2|A|-1
o |B(A)| = |A|2
32. Счетное множество ‑
þ бесконечное множество, элементы которого возможно занумеровать натуральными числами.
o конечное множество, элементы которого возможно занумеровать натуральными числами.
o конечное множество, элементы которого являются подмножеством натуральных чисел.
33. Примеры счётных множеств
þ множество всех рациональных чисел.
þ множество всех алгебраических чисел.
þ множество всех двоичных чисел.
o множество всех действительных чисел.
34. Мощность множества
þ это обобщение понятия количества (числа элементов множества).
þ характеризует то общее, что присуще всем множествам, количественно эквивалентным данному.
þ имеет смысл для всех множеств, включая бесконечные.
o имеет смысл только для конечных множеств.
35. Наименее бесконечную мощность из представленных ниже множеств имеют
þ счётные множества
o множество натуральных чисел
o множество всех действительных чисел
o несчётные множества
36. Наименее бесконечную мощность из представленных ниже множеств имеет
þ пустое множество
o счётное множества
o множество всех действительных чисел
o несчётные множества
37. Объединение множеств (сумма множеств)
þ множество, состоящее из всех тех элементов, каждый из которых принадлежит хотя бы одному из данных множеств.
o число, равное сумме элементов обоих множеств.
o число, равное сумме неповторяющихся элементов обоих множеств.
o множество, состоящее из элементов обоих множеств.
38. Множество –
þ простейшее математическое понятие, оно не определяется, а лишь поясняется при помощи примеров: множество книг на полке, множество точек на прямой (точечное множество) и т. д.
o любая совокупность явлений, предметов и объектов реального мира.
o любая совокупность чисел: натуральных, действительных, комплексных, включая единственный ноль.
39. Выберите определение подмножеств
þ множество A является подмножеством множества B, если любой элемент, принадлежащий A также принадлежит B.
o множество A является подмножеством множества B, если число элементов А меньше числа элементов В.
o множество A является подмножеством множества B, если число элементов А меньше либо равно числу элементов В.
40. Выберите определение и свойства подмножеств
þ множество всех четных чисел является подмножеством множества всех целых чисел.
þ то пустое множество является подмножеством любого множества.
þ подмножества конечных множеств конечны.
þ множество натуральных чисел (счётное) имеет бесконечное число подмножеств.
þ конечное множество имеет конечное число подмножеств.
o то пустое множество не является подмножеством никакого множества.
o подмножество бесконечных множеств всегда бесконечны.
o множество натуральных чисел (счётное) имеет конечное число подмножеств.
41. Даны множества 
þ 
o 
o 
o 
42. Взаимно однозначное соответствие ‑
þ такое соответствие между элементами двух множеств, при котором каждому элементу первого множества соответствует один определенный элемент второго множества, а каждому элементу второго множества - один определенный элемент первого множества
o такое соответствие между элементами двух множеств, при котором каждый элемент первого множества равен значению некоторой функции f, тогда как соответствующий элемент второго множества соответственно равен значению функции g. Причём функции f и g взаимнообратны.
43. Заданы множества A={2,4,3,1} и B={4,2,1,3}, тогда для них неверным утверждением будет…
o множество A включает в себя множество B.
o множества A и B равны .
þ множества A и B не имеют общих элементов.
o множество A есть подмножество множества B .
44. Заданы множества M={2, 3, 4, 5} и N={4, 3}, тогда для них верным утверждением будет…
o множества M и N равны.
o множества M и N не имеют общих элементов.
þ множества M включает в себя множество N.
o множество M есть подмножество множества N.
45. Заданы множества A={1,2,3} и B={1,2,3,4,5}, тогда для них верным утверждением будет…
þ множество A есть подмножество множества B.
o множества A и B равны.
o множества A и B не имеют общих элементов.
o множество A включает в себя множество B.
46. Заданы множества A={2,3,4,5} и D={5,2,3}, тогда для них верным утверждением будет…
þ множество D есть подмножество множества A.
þ множество A включает в себя множество D.
o множества D и A состоят из одинаковых элементов.
o множества A и D равны.
47. Заданы множества A={1,2,3} и M={2,3}, тогда для них верным утверждением будет…
o множества M включает в себя множество A
þ множество M есть подмножество множества A
o множества A и M равны
o множество A есть подмножество множества M
48. Выбрать верный порядок убывания старшинства операций алгебры Кантора
þ 
o 
o 
o 
49. Выбрать формулу, соответствующую дистрибутивному закону
þ 
o 
o 
o 
50. Указать формулу, соответствующую закону Порецкого
þ
o
o
o
51. Могут ли повторяться элементы множества?
þ нет
o да
o при определённых условиях - да
52. Является ли множество несобственным подмножеством самого себя?
þ да
o нет
o да, при определённых условиях
53. Множества равны, если они содержат:
þ одинаковые элементы.
o одинаковое количество элементов.
54. Являются ли понятия мощности множества и его кардинального числа идентичными?
þ да
o нет
o да при определённых условиях
55. Булеан множества А={{1, 2}, 3} определяется как
þ 
o 
o 
o 
56. Какое из утверждений верно для всех множеств А,В,С:
þ 
o 
o 
57. Какой закон определяется формулой 
?
þ элиминации.
o Порецкого
o Де Моргана
o инволюции
58. Чему равно выражение 
?
þ А
þ 
o 
o В
59. два подхода к теории множеств
þ наивная теория множеств Кантора.
þ аксиоматическая теория множеств.
o алгебраическая теория множеств.
o математическая теория множеств.
o графо-аналитическая теория множеств.
60. Диаграммы Эйлера ‑ Венна
þ содержат результаты операций над геометрическими фигурами как множествами точек
o представляют собой визуальное представление множеств
o определяют порядок сравнения множеств
АЛГЕБРЫ И АЛГЕБРАИЧЕСКИЕ СТРУКТУРЫ. БУЛЕВА АЛГЕБРА.
61. Решетка –
þ частично упорядоченное множество, в котором каждое двухэлементное подмножество имеет точную верхнюю (sup) и точную нижнюю (inf) грани.
þ алгебраическая система 
, любые два элемента которой имеют единственные точные верхнюю и нижнюю грани, определяемые следующим образом: 
.
o упорядоченное множество, в котором двухэлементные подмножества не равны между собой.
o множество, в котором есть минимальный (inf – infinum) и максимальный элементы (sup – supremum).
62. Решёткой является
þ универсальная алгебра с двумя бинарными операциями 
, удовлетворяющими свойствам: идемпотентности, коммутативности, ассоциативности, поглощения.
o универсальная алгебра с двумя бинарными операциями , удовлетворяющими свойствам: дистрибутивности, коммутативности, ассоциативности, отрицания.
63. Решёткой является
þ любое линейно упорядоченное множество.
þ множество всех подмножеств данного множества (булеан), упорядоченное по включению.
o счётное множество.
o несчётное множество.
o бесконечное множество.
o конечное множество.
64. Решетка называется дедекиндовой (модулярной) тогда и только тогда, когда для любых ее трех элементов выполнено условие:
þ 
o 
o 
65. Решетка называется дистрибутивной, если для любых её трех элементов ( 
) выполнены тождества:
þ 
, 
o 
66. Булеву алгебру можно рассматривать
þ как дистрибутивную решетку с дополнениями.
o как декиндову решётку.
o как дистрибутивную решётку.
o как подрешётку классической алгебры.
67. Какой из законов не обязательно присутствует в определении решетки:
þ дистрибутивный.
o коммутативный.
o элиминации.
o ассоциативный.
68. Какой закон в дополнение к обязательным определяет решетку как булеву алгебру:
þ дистрибутивный.
o коммутативный.
o элиминации.
o ассоциативный.
69. Решетка определяется на:
þ частично упорядоченном множестве.
o произвольном множестве.
o линейно упорядоченном множестве.
o неупорядоченном множестве.
70. Какое из условий определяет дедекиндову решетку:
þ 
o 
o 
o 
o 
o 
o 
71. Какое из условий определяет дистрибутивную решетку в дополнение к свойству модулярности:
þ
o 
o 
o 
o 
o 
72. Абстрактная алгебра
þ раздел математики, изучающий алгебраические системы (также иногда называемые алгебраическими структурами), такие как группы, кольца, поля, частично упорядоченные множества, решётки, а также отображения между такими структурами.
o это непустая система подмножеств, замкнутая относительно дополнения и объединения.
o совокупность вещественных чисел с определёнными для них операциями сложения и умножения являются алгеброй.
73. Раздел математики, изучающий алгебраические системы, такие как группы, кольца, поля, частично упорядоченные множества, решётки, а также отображения между такими структурами, называется
þ абстрактной алгеброй.
o теоретической алгеброй.
o высшей алгеброй.
o алгеброй множеств.
74. Булево выражение называется выполнимым,
þ если существует хотя бы одна комбинация значений переменных, подстановка которых обращает его в единицу.
o если его можно привести к КНФ.
o если его можно привести к ДНФ.
o если оно допускает построение эквивалентного отрицаня
75. Сколько двоичных наборов содержит таблица истинности функции f(a,b,c)?
þ 8
o 2
o 3
o 7
76. Чему равно логическое выражение 
?
þ 
o 
o 0
o 1
77. Предельное дизъюнктивное разложение функции по теореме Шеннона есть
þ СДНФ
þ СКНФ
o ДНФ
o КНФ
78. На каком входном наборе дизъюнкция двух переменных равна единице?
þ 0 1
þ 1 0
þ 1 1
o 0 0
79. Функция f(x1,x2,...,xn) называется булевой, если каждый ее аргумент и сама функция суть булевы переменные
þ если каждый ее аргумент и сама функция суть булевы переменные.
o если каждый ее аргумент является булевой переменной.
o если каждый ее аргумент принимает значения {1, 0}.
80. На каком входном наборе конъюнкция двух переменных равна нулю?
þ 0 1
þ 1 0
þ 0 0
o 1 1
81. Конъюнкция некоторого числа переменных равна единице, когда
þ все переменные равны единице.
o все переменные равны нулю.
o хотя бы одна переменная равна единице.
o хотя бы одна переменная равна нулю.
82. Дизъюнкция некоторого числа переменных равна единице, когда
þ все переменные равны единице;
þ хотя бы одна переменная равна единице;
o хотя бы одна переменная равна нулю.
83. Бyлевыми фyнкциями (истинностными фyнкциями) называются
þ функции, определенные на множестве состоящем из двух элементов {0, 1} и принимающие значения тоже на этом множестве.
o функции, определенные на множестве состоящем из двух элементов {0, 1}.
o принимающие значения на множестве из двух элементов {0, 1}.
84. Областью определения булевой функции является
þ множество, состоящее из нуля и единицы.
þ множество всех булевых констант.
o множество натуральных чисел.
o множество действительных чисел.
o множество комплексных чисел.
85. Каждая функция из множества всех булевых функций является сyпеpпозицией следующих функций:
þ отрицание, конъюнкция, дизъюнкция.
o отрицание, конъюнкция.
o отрицание, дизъюнкция.
o конъюнкция, дизъюнкция.
86. Булевы функции называются равными,
þ если на одинаковых наборах они принимают одинаковые значения.
þ если на каждом наборе значений аргументов x1, x2, ..., xn функции f1(x1,x2,...,xn) и f2(x1,x2,...,xn) принимают одно и то же значение.
þ если совпадают их таблицы истинности.
o если число входящих в них переменных равны.
o если число входящих в них переменных и значения этих переменных равны.
87. Разложение булевой функции f(x1,x2,...,xn) по переменной xi производится
þ по формуле Шеннона: 
.
o по формуле Шеннона f(x1,x2,...,xn)= x1f(1,x2,...,xn)+ х1(0,x2,...,xn) +…+ xnf(1,x2,...,xn)+ хn(0,x2,...,xn).
o по формуле Шеннона f(x1,x2,...,xn)= x1f(1,x2,...,xn)+…+ xnf(1,x2,...,xn).
o по формуле Шеннона f(x1,x2,...,xn)= x1f(1,x2,...,xn)Ú…Ú xnf(1,x2,...,xn).
o по формуле Шеннона f(x1,x2,...,xn)= x1Ùf(1,x2,...,xn)Ú…Ú xnÙf(1,x2,...,xn).
88. К элементарным функциям относятся
þ не зависящие от аргументов: константа 0 и константа 1;
þ одного аргумента: тождественная функция f(x) = x и функция отрицания f(x) = 
, которая называется инверсией или функцией НЕ.
þ функции двух аргументов: конъюнкция, дизъюнкция, импликация
89. ДHФ, задающая бyлевy функцию f называется минимальной ДHФ функции f, если она
þ содержит наименьшее число букв по сравнению со всеми другими ДHФ, задающими данную функцию.
o содержит только положительные литеры, т.е. буквы без отрицания.
o содержит минимальное число отрицательных литер, т.е.букв с отрицанием.
90. Таблицей истинности называется таблица, которая содержит
þ все наборы значений аргументов, упорядоченные по возрастанию значений чисел, и соответствующие им значения булевой функции.
o такие наборы значений аргументов, при которых соответствующие им значения булевой функции являются истинными
ЛОГИЧЕСКИЕ ИСЧИСЛЕНИЯ
91. Какие из перечисленных выражений являются формулами?
þ 
þ 
þ 
þ 
o 
o 
92. Элементами логических рассуждений являются утверждения, которые либо
þ истинны
þ ложны
þ не то и другое вместе
o то и другое вместе
93. К логическим связкам (операторам) в логике высказываний относятся
þ Ø (отрицание)
þ Ù (конъюнкция)
þ Ú (дизъюнкция)
þ ® (следствие)
o ¯ (существование)
o (отсутствие)
o « (тождество)
94. К логическим связкам (операторам) в логике предикатов относятся
þ Ø (отрицание)
þ Ù (конъюнкция)
þ Ú (дизъюнкция)
þ ® (следствие)
þ « (тождество)
o ¯ (существование)
o (отсутствие)
95. Правильно построенные составные высказывания
þ называют пропозициональными формулами
þ содержат операторы Ø Ù Ú ®
o имеют только истинные значения
o имеют ложные значения
96. Таблица истинности для операции импликации
þ 0 0 1
0 1 1
1 0 0
1 1 1
o 0 0 0
0 1 0
1 0 1
1 1 0
o 0 0 1
0 1 0
1 0 0
1 1 1
97. Интерпретация (интерпретация формулы)
þ конкретный набор истинностных значений, приписанных переменным, входящим в пропозициональную формулу.
o набор значений типа true, приписанных переменным, входящим в пропозициональную формулу.
o набор значений типа false, приписанных переменным, входящим в пропозициональную формулу.
98. Формула логики высказываний, истинная при некоторых значениях входящих в неё переменных, называется
þ выполнимой
o частично-выполнимой
o невыполнимой
99. Формула логики высказываний, истинная при всех значениях входящих в неё переменных, называется
þ общезначимой.
þ тавталогией.
o выполнимой.
o невыполнимой.
100. Формула логики высказываний, истинная при всех значениях входящих в неё переменных, называется
þ невыполнимой.
þ противоречием.
o отрицанием.
o false-формулой.
o zero-формулой.
101. Предикатом Р(x1,..., xn) называется
þ функция P: Mn→ {0,1} , т. е. функция, принимающая значение "0" или "1", аргументы которой пробегают значения из произвольного множества М.
o функция P: Mn→ {0,1, 2, …} , т.е. функция, принимающая целочисленные значения, аргументы которой пробегают значения из произвольного множества М.
o функция P: Mn→ {0,1} , т. е. функция, принимающая значение "1", если её аргументы реальные (принадлежат множеству М) или "1", если её аргументы мнимые ( не принадлежат множеству М).
102. В логике предикатов используются кванторы
þ квантор всеобщности (все, всякий, каждый)
þ квантор существования (существует, имеется, некоторый)
o квантор модальности (может быть, иногда случается, может иметь место)
o временные кванторы (часто, редко, иногда, постоянно)
103. Запись "xP(x) эквивалентна утверждению
þ для всех x из области его определения имеет место Р(x).
þ предикат Р(х) принимает значение "истина" для каждого экземпляра из области определения х.
o для некоторых x из области его определения имеет место Р(x).
o в области определения х найдутся такие экземпляры, для которых предикат Р(х) принимает значение "истина".
104. Запись $xP(x) эквивалентна утверждению
þ найдется, по крайней мере, один x в области определения х, такой, что истинен Р (х)".
þ для некоторых x из области его определения имеет место Р(x).
o для любого x из области его определения имеет место Р(x).
o предикат Р(х) принимает значение "истина" при любом значении аргумента х.
105. Переменные, находящиеся в сфере действия кванторов, называются
þ связанными
þ квантифицированными
o свободными
o применёнными
106. Формула ЛП называется, выполнимой в области D
þ если в этой области для формулы существует такая подстановка всех констант, что формула становится истинным высказыванием.
o если в этой области определены предикаты, принимающие истинные значения.
o если в этой области определены переменные, связанные квантором всеобщности, а предикаты с этими переменными принимают истинные значения
o если в этой области определены переменные, связанные квантором существования, а предикаты с этими переменными могут принимать как истинные, так и ложные значения.
107. Формула ЛП называется тождественно истинной в области D
þ если формула становится истинным высказыванием при любых подстановках констант из области D.
o если формула становится истинным высказыванием при любых подстановках переменных из области D, связанных квантором всеобщности.
o если формула становится истинным высказыванием при любых подстановках переменных из области D, связанных квантором существования.
108. описательные возможности логики предикатов значительно выше возможностей логики высказываний за счёт
þ использования кванторов всеобщности и существования
þ использования предикатов
o введения силлогизмов
o использования формул
o введения логических операций следствия и тождества
109. Предваренная нормальная форма в логике предикатов включает в себя
þ префикс, образованный кванторами " и $ и матрицу, под которой понимается формула, не содержащая квантификаций.
o предикаты, переменные которых связаны только кванторами всеобщности.
o предикаты, переменные которых связаны только кванторами существования.
o предикаты, переменные которых не связаны никакими логическими связками.
110. Приведение формул логики предикатов к сколемовской форме (сколемизация) призвано
þ обеспечить дальнейшее упрощение логических представлений и облегчить введение процедур машинной обработки в ЛП.
þ исключить $-квантификации для возможности проведения доказательства методом резолюции.
o исключить вхождения всех кванторов для минимизации последующего процесса доказательства.
o ввести сколемовские константы и функции вместо любой квантифицированной переменной для минимизации последующего процесса доказательства.
111. Резольвента – это
þ дизъюнкт, полученный в результате соединения двух дизъюнктов, в один из которых входит некоторая литера без отрицания, а в другой – с отрицанием.
o дизъюнкт, полученный в результате удаления из него некоторой литеры с отрицанием и без отрицания.
o дизъюнкт, полученный в результате сколемизации, т.е. удаления всех $-квантифицированных переменных.
112. Главная идея метода резолюций состоит
þ в доказательстве совместной невыполнимости множества аксиом Ai и отрицания целевого утверждения F, т.е. невыполнимости формулы 
þ в доказательстве "от противного": для доказательства выводимости формулы из набора аксиом к набору добавляется отрицание исследуемой формулы, и осуществляется попытка вывести противоречие.
o в доказательстве выводимости формулы из набора аксиом путём применения правил вывода (законов логики высказывания или логики предикатов) к ДНФ-формам этих аксиом.
o в доказательстве выводимости формулы из набора аксиом путём применения правил вывода (законов логики высказывания или логики предикатов) к КНФ-формам этих аксиом.
113. Метод резолюций
þ выдает ответ «Да», если F является логическим следствием из множества аксиом {А1, А2, …Аn}.
þ выдает ответ «Нет» если не верно, что F является логическим следствием из множества аксиом {А1, А2, …Аn}.
þ не выдает никакого ответа (то есть зацикливается), если неверно, что F является логическим следствием из множества аксиом {А1, А2, …Аn}.
o выдает ответ «Да», если F является логическим следствием из множества {А1& А2& …&Аn ØF}.
o выдает ответ «Нет» если не верно, что F является логическим следствием из множества {А1& А2& …&Аn ØF}.
o не выдает никакого ответа (то есть зацикливается), если неверно, что F является логическим следствием из множества аксиом {А1& А2& …&Аn ØF}.
114. Метод резолюций
þ выдаёт один из ответов "да" или "нет".
þ может привести к комбинаторному взрыву.
o может выдать несколько ответов "да" и только один ответ "нет".
o может выдать только один ответ "да" и несколько ответов "нет".
o либо выдаёт ответ "да" , либо приводит к комбинаторному взрыву.
115. В основе автоматического доказательства теорем логики предикатов и логики высказываний лежит
þ метод резолюции.
o метод сколемизации.
o автоматическое применение логических законов (правил вывода).
o поэтапное исключения кванторов и метод выбора наименьшего унификатора.
МОДУЛЬ 2
ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ
116. Назовите алгоритм нахождения кратчайшего пути от узла-источника ко всем другим узлам
þ алгоритм Дейкстры.
þ алгоритм Беллмана-Форда.
o алгоритм Флойда-Уоршела.
117. Теория графов ‑
þ раздел математики, основная особенность которого заключается в геометрическом подходе к изучению объектов.
o раздел математики, в котором изучаются общие свойства графических систем.
o раздел математики, в котором изучаются свойства и характеристики геометрических объектов.
o раздел математики, в котором изучаются свойства и характеристики структурных объектов.
118. Ребра графа называются смежными, если они
þ инцидентны одной и той же вершине.
o параллельны.
o являются кратными.
119. Граф задаётся
þ множеством вершин (точек) и множеством ребер (связей), соединяющих некоторые пары вершин.
þ матрицей смежности.
o матрицей дуг.
o списками вершин.
120. Если две вершины соединены одной дугой, они называются
þ смежными.
o коинцидентными.
o инцидентными
121. Какие из графов я.вляются подграфами данного графа G 
þ 
o 
o 
o 
122. Если любые две вершины графа можно соединить простой цепью, то граф называется:
þ связным
o деревом
o несвязным
o остовом
123. Для графа, представленного на рисунке, 
матрица смежности имеет вид
þ 
o 
o 
124. Для графа, представленного на рисунке, матрица инциденций имеет вид
þ 
o 
o 
125. Равны ли графы? 
(проверить по матрице смежности)
þ да
o нет
126. Даны графы 
| þ |  |
| o |  |
| o |  |
127. Даны графы
| þ |  |
| o |  |
| o |  |
128. Даны графы
| þ |  |
| o |  |
| o |  |
129. Квадрат G2 графа G 
þ 
o 
o 
130. Квадрат G2 графа G 
þ 
o 
o 
131. Эйлеров цикл графа 
þ (1, 2, 3, 4, 5, 6, 7, 8, 9)
o (1, 2, , 6, 7, 8, 9)
o (1, 2, 3, 4, 6, 5, 7, 8, 9)
o (1, 9, 8, 7, 6, 5, 4, 2,3)
132. Граф является эйлеровым тогда и только тогда,
þ когда он связен и степень каждой вершины чётна.
o когда он связен, а степень каждой вершины не важна
o когда он связен и степень каждой вершины нечётна
133. Граф 
является
þ неэйлеровым
þ несвязным
o эйлеровым
o связным
134. Граф 
является
þ эйлеровым
þ связным
o неэйлеровым
o несвязным
135. Сколько вершин содержит гамильтонов цикл графа с 5 вершинами?
þ 5
o 4
o 6
136. Граф содержит 7 дуг. Его эйлеров цикл будет состоять из
þ 7 дуг
o 6 дуг
o 8 дуг
137. Эйлеров цикл
þ содержит каждое ребро только один раз.
o содержит каждую вершину только один раз.
o проходит через все вершины и ребра графа только один раз.
138. Гамильтонов цикл
þ содержит каждую вершину только один раз.
o содержит каждое ребро только один раз.
o проходит через все вершины и ребра графа только один раз.
139. В эйлеровом графе все вершины
þ четной степени.
o нечетной степени.
140. В эйлеровом графе допускаются
þ 2 вершины нечетной степени.
o 3 вершины нечетной степени.
o 1 вершина нечетной степени.
141. Какой алгоритм определяет гамильтоновы циклы графа:
þ Гильберта-Мура
o Флери
o Робертса-Флореса
o Дейкстры
142. Какой из циклов графа с множеством вершин {a,b,c,d,e,f} является гамильтоновым?
þ abecdfa
o abeca
o fbecdf
o abcdfca
143. Двоичным деревом называется
þ ориентированное дерево, полустепень числа исходящих дуг из исхода каждой вершины которого не превышает 2.
o неориентированное дерево, полустепень числа исходящих дуг из исхода каждой вершины которого не превышает 2.
o ориентированное дерево, полустепень числа исходящих дуг из исхода каждой вершины которого не превышает 22.
o неориентированное дерево, полустепень числа исходящих дуг из исхода каждой вершины которого не превышает 22
144. На рисунке 
представлено
þ дерево
þ двоичное дерево
o сеть
o двоичная сеть
145. Длина ориентированного пути в графе G – это
þ сумма длин рёбер, входящих в путь.
o сумма длин рёбер графа.
o сумма длин рёбер графа минус сумма длин рёбер, входящих в путь.
146. Кратчайшим путем из вершины s в вершину t называется
þ ориентированный s-t – путь, имеющий минимальную длину.
o ориентированный s-t – путь, не имеющий промежуточных вершин .
147. Расстоянием от вершины s до вершины t d(s, t) называется
þ длина кратчайшего ориентированного s-t пути.
o эвклидово расстояние между s и t, вычисленное в эвклидовом пространстве.
o хэммингово расстояние между s и t, вычисленное в эвклидовом пространстве.
148. Алгоритм Дейкстры
þ определяет кратчайшие пути из данной вершины ко всем другим вершинам связного (в общем случае ориентированного) ориентированного графа, состоящего из n вершин.
o построение остова наименьшей длины.
o построение кратчайшего пути из одной вершины в другую.
149. Алгоритм Краскала осуществялет:
þ построение кратчайшего остова.
o построение оптимального дерева бинарного поиска.
o построение дерева кратчайших путей.
150. В графе из n вершин остов содержит:
þ n-1 ребро
o n ребер
o 2n ребер
o n+1 ребро
151. Дерево есть:
þ связный граф без циклов.
o остовный подграф графа.
o граф без циклов.
o связный граф.
152. Простая цепь это:
þ маршрут, где нет повторяющихся вершин и ребер.
o маршрут, где нет повторяющихся ребер.
o маршрут, где нет повторяющихся вершин.
o маршрут минимальной стоимости.
153. Расстояние между вершинами есть
þ длина кратчайшего пути.
o сумма длин ребер, входящих в путь.
154. Глубина элемента а2 в дереве 
равна
þ 1
o 0
o 2
o 3
155. Степень вершины а2 в графе равна
þ 3
o 0
o 1
o 2
СЕТИ ПЕТРИ
156. Сетью Петри называется
þ четвёрка C=(P,T,I,O), где P – конечное множество позиций; T – конечное множество переходов; I : T®P¥ входная функция, отображающая переходы в комплекты входных позиций; O: T®P¥ выходная функция, отображающая переходы в комплекты выходных позиций.
o четвёрка C=(P,T,D,M), где P – конечное множество позиций; T – конечное множество переходов; D – конечное множество дуг; М – конечное множество маркеров.
o четвёрка C=(P,T,D,M), где P – конечное множество позиций; T – конечное множество переходов; D – конечное множество дуг; М – бесконечное множество маркеров.
157. Сетью Петри называется
þ совокупность переходов и позиций, связанных направленными дугами, по которым могут перемещаться маркеры.
o совокупность переходов и позиций, связанных отношениями использования и помеченных маркерами.
o совокупность переходов, позиций, дуг и маркеров, отображающих замкнутую цепь.
158. Сетью Петри моделируют
þ динамические свойства систем.
o статические свойства систем.
o структурные свойства систем.
o устойчивость систем.
159. Сеть Петри представляет собой мультиграф, содержащий следующие графические элементы
þ позиции
þ переходы
þ дуги
o входы
o выходы
160. Формализм cети Петри основан на понятии
þ комплекта
o множества
o бинарных отношений
161. Комплект – это
þ набор элементов, причём всякий элемент может входить в комплект более одного раза.
o набор элементов, причём всякий элемент может входить в комплект не более одного раза.
o разновидность понятия множества с ограниченными свойствами.
o обобщение множества с дополнительной функцией числа экземпляров в комплекте.
162. Маркировка сети Петри – это
þ функция, отображающая множество позиций P в множество неотрицательных целых чисел N.
o функция, отображающая множество позиций P в множество переходов T.
o функция, отображающая множество переходов T во множество переходов Р.
| p1 |
| p2 |
| p3 |
| p4 |
| p5 |
| t1 |
| t2 |
| t3 |
| t4 |
163. Маркировка сети Петри
þ m(p1) = m(p3) = 1 m(p2) = m(p3) = m(p4) = 0
o m(p1) = m(p3) = 0 m(p2) = m(p3) = m(p4) = 1
o m(t2 - p3) = m(t1 - p1) = 1 m(t3 - p5) = 0
164. Маркировка сети Петри представляет собой
þ вектор m = (m1, m2, …, mn), где n – число позиций сети, каждый элемент вектора есть m(pi) = 1
þ комплект m, в который входят позиции сети piÎP и #(pi, m)=m(pi), m(pi) ¹0
o множество mпар {p, t} или {t, p}, отображающих движение маркеров от переходов к позициям и наоборот.
165. Маркировка сети Петри может меняться в результате
þ запуска переходов.
o открытия переходов и открытия позиций.
o открытия переходов и закрытия позиций.
o освобождения одних позиций и закрытия других позиций.
| p1 |
| p2 |
| p3 |
| p4 |
| p5 |
| t1 |
| t2 |
| t3 |
| t4 |
166. Множество входных и выходных позиций для сети Петри
þ I(t1) = {p1, p1, p1} O(t1) = {p3, p4, p4}
o I(t1) = {p1} O(t1) = {p3, p4}
o I(t1) = {p3, p4, p4} O(t1) = {p1, p1, p1}
o I(t1) = {p3, p4} O(t1) = {p1}
167. Переход в маркированной сети Петри с маркировкой m называется разрешенным, если
þ I(tj) Í m, т. е. в каждой входной позиции tj находится не меньше фишек, чем из этой позиции выходит дуг в tj.
o O(tj) Í m, т. е. в каждой выходной позиции tj находится не меньше фишек, чем в эту позицию входит дуг.
o число входов перехода tj не меньше числа его выходов.
o число входных позиций перехода tj не меньше числа выходных позиций этого же перехода.
168. Переход в сети Петри является
þ разрешённым
o неразрешённым
o избыточным
o избыточным по выходам
169. Переход в сети Петри является
þ неразрешённым
o разрешённым
o избыточным по входам
o избыточным по выходам