Основы теории отношений
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}. Определить составное отношениеR1◦R2= {(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}. Определить составное отношениеR2◦R1= {(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=R1◦R1 = {(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=R2◦R2= {(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) R1◦R2– «быть в разных группах и иметь разные имена»;
2) R1◦R2– «быть в одной группе и иметь одинаковые имена»
3) R1◦R2– «быть в одной группе и иметь разные имена»
4) R1◦R2– «быть в разных группах и иметь одинаковые имена».
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)
Высказывательные формы. Функции алгебры логики. Основные понятия и определения. Способы задания булевых функций. Таблица истинности. Существенные и несущественные переменные. Булевы функции одной и двух переменных. Формулы. Реализация функций формулами. Равносильные формулы. Специальные разложения БФ.
Функциями алгебры логики или булевыми функциями называются …
а) 
,
где
б)
в)
Множество всех булевых функций от nпеременных обозначают …
а)
б)
в)
г)
Булева функция
существенно зависит от переменнойxi,
если существует такой набор значений
,
что …
а)
б)
Таблица истинности
|
x1 |
x2 |
f |
|
0 |
0 |
0 |
|
0 |
1 |
1 |
|
1 |
0 |
1 |
|
1 |
1 |
1 |
соответствует функции …
а)
б)
в)
г)
д)
е)
ж)
Таблица истинности
|
x1 |
x2 |
f |
|
0 |
0 |
0 |
|
0 |
1 |
1 |
|
1 |
0 |
1 |
|
1 |
1 |
0 |
соответствует функции …
а)
б)
в)
г)
д)
е)
ж)
Таблица истинности
|
x1 |
x2 |
f |
|
0 |
0 |
1 |
|
0 |
1 |
1 |
|
1 |
0 |
1 |
|
1 |
1 |
0 |
соответствует функции …
а)
б)
в)
г)
д)
е)
ж)
Таблица истинности
|
x1 |
x2 |
f |
|
0 |
0 |
1 |
|
0 |
1 |
1 |
|
1 |
0 |
0 |
|
1 |
1 |
1 |
соответствует функции …
а)
б)
в)
г)
д)
е)
ж)
Таблица истинности
|
x1 |
x2 |
f |
|
0 |
0 |
1 |
|
0 |
1 |
0 |
|
1 |
0 |
0 |
|
1 |
1 |
1 |
соответствует функции …
а)
б)
в)
г)
д)
е)
ж)
Таблица истинности
|
x1 |
x2 |
f |
|
0 |
0 |
0 |
|
0 |
1 |
0 |
|
1 |
0 |
0 |
|
1 |
1 |
1 |
соответствует функции …
а)
б)
в)
г)
д)
е)
ж)
Таблица истинности
|
x1 |
x2 |
f |
|
0 |
0 |
1 |
|
0 |
1 |
0 |
|
1 |
0 |
0 |
|
1 |
1 |
0 |
соответствует функции …
а)
б)
в)
г)
д)
е)
ж)
Функция
называется двойственной к функции
,
если …
а)
б)
в)
Функция
называется самодвойственной, если …
а)
б)
в)
Обозначают в теории булевых функций xσ =x, если σ = 1, иxσ =
,
если σ = 0. Символxσ называют … булевой функцииf.
а) литералом
б) импликантой
в) термом
г) конституентой
Конъюнкцию
,
равную единице, если и только еслиxj = σj
(j= 1, 2, …,n)
называют …
а) литералом
б) импликантой
в) термом
г) конституентой единицы
Всякую конъюнкцию переменных булевой функции f(x1, x2, …, xn), взятых с отрицанием или без отрицания, называют …
а) элементарной
б) дизъюнктивной
в) конъюнктивной
Всякую дизъюнкцию переменных булевой функции f(x1, x2, …, xn), взятых с отрицанием или без отрицания, называют …
а) элементарной
б) дизъюнктивной
в) конъюнктивной
Дизъюнкцию
булевой функцииf(x1, x2, …, xn)
приm =nназывают …
а) дизъюнктом
б) конъюнктом
в) импликантой
Конъюнкцию элементарных дизъюнкций называют …
а) дизъюнктивной нормальной формой или ДНФ
б) конъюнктивной нормальной формой или КНФ
в) бисуммарной нормальной формой или БНФ
Сумму по модулю 2 элементарных конъюнкций называют …
а) дизъюнктивной нормальной формой или ДНФ
б) конъюнктивной нормальной формой или КНФ
в) бисуммарной нормальной формой или БНФ
Дизъюнкцию элементарных конъюнкций называют …
а) дизъюнктивной нормальной формой или ДНФ
б) конъюнктивной нормальной формой или КНФ
в) бисуммарной нормальной формой или БНФ
Представление булевой функции f (x1, x2, …, xn) в виде … называют совершенной дизъюнктивной нормальной формой (СДНФ).
а)
б)
в)
г)
Представление булевой функции f (x1, x2, …, xn) в виде … называют совершенной конъюнктивной нормальной формой (СКНФ).
а)
б)
в)
г)
Представление булевой функции f (x1, x2, …, xn) в виде … называют совершенной бисуммарной нормальной формой (СБНФ).
а)
б)
в)
г)
Дизъюнкцию всех конституент единицы булевой функции f(x1, x2, …, xn) называют …
а) совершенной дизъюнктивной нормальной формой (СДНФ)
б) совершенной бисуммарной нормальной формой (СБНФ)
в) совершенной конъюнктивной нормальной формой (СКНФ)
Сумму по модулю 2 всех конституент единицы булевой функции f(x1, x2, …, xn) называют …
а) совершенной дизъюнктивной нормальной формой (СДНФ)
б) совершенной бисуммарной нормальной формой (СБНФ)
в) совершенной конъюнктивной нормальной формой (СКНФ)
Конъюнкцию всех дизъюнктов булевой функции f(x1, x2, …, xn) называют …
а) совершенной дизъюнктивной нормальной формой (СДНФ)
б) совершенной бисуммарной нормальной формой (СБНФ)
в) совершенной конъюнктивной нормальной формой (СКНФ)
Функция «штрих Шеффера» в аналитической форме записи может иметь вид …
а) f (x1, x2) = {0, 1, 2}
б) f (x1, x2) = (1, 1, 1, 0)
в) f (x1, x2) : 1 2 0
г) f (x1, x2) = {0}
д) f (x1, x2) = (1, 0, 0, 0)
е) f (x1, x2) : -1 2 0 1 -2 0 1 2 0
Функция «стрелка Пирса» в аналитической форме записи может иметь вид …
а) f (x1, x2) = {0, 1, 2}
б) f (x1, x2) = (1, 1, 1, 0)
в) f (x1, x2) : 1 2 0
г) f (x1, x2) = {0}
д) f (x1, x2) = (1, 0, 0, 0)
е) f (x1, x2) : -1 2 0 1 -2 0 1 2 0
В СДНФ функция «стрелка Пирса» имеет вид …
а)
б)
в)
г)
д)
В СКНФ функция «стрелка Пирса» имеет вид …
а)
б)
в)
г)
д)
В СБНФ функция «стрелка Пирса» имеет вид …
а)
б)
в)
г)
д)
В СДНФ функция «штрих Шеффера» имеет вид …
а)
б)
в)
г)
д)
В СКНФ функция «штрих Шеффера» имеет вид …
а)
б)
в)
г)
д)
В СБНФ функция «штрих Шеффера» имеет вид …
а)
б)
в)
г)
д)
Свойство булевых функций, именуемое поглощением конъюнкции, определяется соотношением …
а)
б)
в)
г)
Свойство булевых функций, именуемое поглощением дизъюнкции, определяется соотношением …
а)
б)
в)
г)
Свойство булевых функций, именуемое идемпотентностью дизъюнкции, определяется соотношением …
а)
б)
в)
г)
Свойство булевых функций, именуемое идемпотентностью конъюнкции, определяется соотношением …
а)
б)
в)
г)
Свойство булевых функций, именуемое ассоциативностью конъюнкции, определяется соотношением …
а)
б)
в)
г)
Свойство булевых функций, именуемое ассоциативностью дизъюнкции, определяется соотношением …
а)
б)
в)
г)
Свойство булевых функций, именуемое тавтологией или законом исключения третьего, определяется соотношением …
а)
б)
в)
г)
Свойство булевых функций, именуемое непротиворечивостью, определяется соотношением …
а)
б)
в)
г)
Свойство булевых функций, именуемое законом двойного отрицания, определяется соотношением …
а)
б)
в)
г)
д)
Свойство булевых функций, именуемое коммутативностью конъюнкции, определяется соотношением …
а)
б)
в)
г)
Свойство булевых функций, именуемое коммутативностью дизъюнкции, определяется соотношением …
а)
б)
в)
г)
Свойство булевых функций, именуемое дистрибутивностью конъюнкции относительно дизъюнкции, определяется соотношением …
а)
б)
в)
г)
Свойство булевых функций, именуемое дистрибутивностью дизъюнкции относительно конъюнкции, определяется соотношением …
а)
б)
в)
г)
Конъюнкция – это …
а) НЕ;
б) И;
в) ИЛИ.
Отрицание – это …
а) НЕ;
б) И;
в) ИЛИ.
Указать правильные утверждения:
а) 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 ‑ тождественная функция.