Главная / Алгоритмы и дискретные структуры /
Дискретная математика / Тест 10
Номер 3
Ответ:
Дискретная математика - тест 10
Упражнение 1:
Номер 1
Ответ:
Номер 1
Каково число логических функций от 3 переменных?
Ответ:
(1)
8
(2)
9
(3)
28
Номер 2
Ответ:
Каково число логических функций от 4 переменных?
Ответ:
(1)
8
(2)
16
(3)
216
Каково число логических функций от 5 переменных?
Ответ:
(1)
25
(2)
32
(3)
232
Упражнение 2:
Номер 1
Какие из этих функций содержат несущественные переменные?
Ответ:
Номер 1
В таблице приведены три функцииf1,f2,f3от переменныхx,y,z:
x | y | z | f1 | f2 | f3 |
|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 1 |
0 | 0 | 1 | 1 | 1 | 0 |
0 | 1 | 0 | 1 | 0 | 0 |
0 | 1 | 1 | 0 | 1 | 1 |
1 | 0 | 0 | 1 | 1 | 1 |
1 | 0 | 1 | 1 | 0 | 0 |
1 | 1 | 0 | 1 | 1 | 0 |
1 | 1 | 1 | 0 | 0 | 1 |
Ответ:
(1)
f1
(2)
f2
(3)
f3
Номер 2
Какие из этих функций содержат несущественные переменные?
Ответ:
В таблице приведены три функцииf1,f2,f3от переменныхx,y,z:
x | y | z | f1 | f2 | f3 |
|---|---|---|---|---|---|
0 | 0 | 0 | 1 | 1 | 1 |
0 | 0 | 1 | 0 | 0 | 1 |
0 | 1 | 0 | 0 | 1 | 1 |
0 | 1 | 1 | 1 | 0 | 1 |
1 | 0 | 0 | 0 | 1 | 0 |
1 | 0 | 1 | 0 | 0 | 0 |
1 | 1 | 0 | 0 | 1 | 1 |
1 | 1 | 1 | 1 | 0 | 1 |
Ответ:
(1)
f1
(2)
f2
(3)
f3
Номер 3
Какие из этих функций содержат несущественные переменные?
Ответ:
В таблице приведены три функцииf1,f2,f3от переменныхx,y,z:
x | y | z | f1 | f2 | f3 |
|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 1 | 0 |
0 | 0 | 1 | 1 | 1 | 1 |
0 | 1 | 0 | 1 | 0 | 1 |
0 | 1 | 1 | 0 | 1 | 0 |
1 | 0 | 0 | 1 | 1 | 0 |
1 | 0 | 1 | 0 | 1 | 1 |
1 | 1 | 0 | 0 | 0 | 1 |
1 | 1 | 1 | 1 | 1 | 0 |
Ответ:
(1)
f1
(2)
f2
(3)
f3
Упражнение 3:
Номер 1
Ответ:
Номер 1
Какие из функций ассоциативны?
Ответ:
(1)
импликация
(2)
конъюнкция
(3)
штрих Шеффера?
Номер 2
Ответ:
Какие из функций ассоциативны?
Ответ:
(1)
дизъюнкция
(2)
стрелка Пирса
(3)
сложение по модулю
2
Номер 3
Ответ:
Какие из функций ассоциативны?
Ответ:
(1)
эквивалентность
(2)
импликация
(3)
сложение по модулю
2
Упражнение 4:
Номер 1
Ответ:
Номер 1
Какая из формул эквивалентна формуле
(¬x&y)∨(x&z)∨(¬x&z)?
Ответ:
(1)
(x∨¬z)&(y∨z)
(2)
(¬x∨z)&(y∨z)
(3)
(x∨z)&(y∨z)
Номер 2
Ответ:
Какая из формул эквивалентна формуле
(x&¬y)∨(y&z)∨(¬y&z)?
Ответ:
(1)
(x∨¬z)&(y∨z)
(2)
(x∨z)&(¬y∨z)
(3)
(¬x∨z)&(y∨z)
Номер 3
Ответ:
Какая из формул эквивалентна формуле
(x&y)∨(y&z)∨(¬y&z)?
Ответ:
(1)
(x∨¬z)&(y∨z)
(2)
(x∨z)&(y∨z)
(3)
(¬x∨z)&(y∨z)
Упражнение 5:
Номер 1
Какой из полиномов Жегалкина ей соответствует?
Ответ:
Номер 1
Функция f задана таблицей:
x | y | z | f |
|---|---|---|---|
0 | 0 | 0 | 0 |
0 | 0 | 1 | 1 |
0 | 1 | 0 | 1 |
0 | 1 | 1 | 0 |
1 | 0 | 0 | 1 |
1 | 0 | 1 | 1 |
1 | 1 | 0 | 0 |
1 | 1 | 1 | 1 |
Ответ:
(1)
xyz⊕xz⊕x⊕y⊕z
(2)
xyz⊕yz⊕x⊕z
(3)
xy⊕xz⊕y⊕z
(4)
xz⊕x⊕y⊕z
Номер 2
Какой из полиномов Жегалкина ей соответствует?
Ответ:
Функция f задана таблицей:
x | y | z | f |
|---|---|---|---|
0 | 0 | 0 | 0 |
0 | 0 | 1 | 1 |
0 | 1 | 0 | 0 |
0 | 1 | 1 | 0 |
1 | 0 | 0 | 0 |
1 | 0 | 1 | 1 |
1 | 1 | 0 | 1 |
1 | 1 | 1 | 0 |
Ответ:
(1)
xyz⊕xy⊕yz⊕z
(2)
xyz⊕yz⊕x⊕z
(3)
xy⊕yz⊕y⊕z
(4)
xz⊕x⊕y⊕1
Номер 3
Какой из полиномов Жегалкина ей соответствует?
Ответ:
Функция f задана таблицей:
x | y | z | f |
|---|---|---|---|
0 | 0 | 0 | 1 |
0 | 0 | 1 | 1 |
0 | 1 | 0 | 0 |
0 | 1 | 1 | 0 |
1 | 0 | 0 | 0 |
1 | 0 | 1 | 0 |
1 | 1 | 0 | 0 |
1 | 1 | 1 | 1 |
Ответ:
(1)
xyz⊕xy⊕x⊕y⊕1
(2)
xyz⊕x⊕y⊕1
(3)
xy⊕x⊕y⊕z
(4)
xz⊕x⊕y⊕1
Упражнение 6:
Номер 1
Ответ:
Номер 1
Какие из функций являются монотонными?
Ответ:
(1) конъюнкция
(2) импликация
(3) штрих Шеффера
Номер 2
Ответ:
Какие из функций являются монотонными?
Ответ:
(1)
отрицание
(2)
сложение по модулю
2
(3)
дизъюнкция
Номер 3
Ответ:
Какая из функций являются монотонной?
Ответ:
(1)
эквивалентность
(2)
стрелка Пирса
(3)
константа
Упражнение 7:
Номер 1
Ответ:
Номер 1
Какая из функций является линейной?
Ответ:
(1) эквивалентность
(2) стрелка Пирса
(3) конъюнкция
Номер 2
Ответ:
Какие из функций являются линейными?
Ответ:
(1)
сложение по модулю
2
(2)
штрих Шеффера
(3)
дизъюнкция
(4)
константа
Номер 3
Ответ:
Какие из функций являются линейными?
Ответ:
(1)
отрицание
(2)
константа
(3)
импликация
Упражнение 8:
Номер 1
Ответ:
Номер 1
Какие из перечисленных систем функций функционально полны в слабом смысле?
Ответ:
(1)
дизъюнкция и сложение по модулю
2
(2)
импликация
(3)
эквивалентность и сложение по модулю
2
(4)
конъюнкция и дизъюнкция
Номер 2
Ответ:
Какие из перечисленных систем функций функционально полны в слабом смысле?
Ответ:
(1)
дизъюнкция и отрицание
(2)
штрих Шеффера
(3)
эквивалентность и отрицание
(4)
конъюнкция и импликация
Номер 3
Ответ:
Какие из перечисленных систем функций функционально полны в слабом смысле?
Ответ:
(1)
стрелка Пирса
(2)
импликация и отрицание
(3)
сложение по модулю
2 и отрицание
(4)
импликация и дизъюнкция
Упражнение 9:
Номер 1
Какие из этих функций функционально полны в слабом смысле?
Ответ:
Номер 1
В таблице приведены три функцииf1,f2,f3от переменныхx,y,z:
x | y | z | f1 | f2 | f3 |
|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 1 | 0 |
0 | 0 | 1 | 0 | 0 | 0 |
0 | 1 | 0 | 0 | 0 | 0 |
0 | 1 | 1 | 1 | 1 | 0 |
1 | 0 | 0 | 0 | 1 | 1 |
1 | 0 | 1 | 1 | 0 | 0 |
1 | 1 | 0 | 0 | 0 | 1 |
1 | 1 | 1 | 1 | 1 | 1 |
Ответ:
(1)
f1
(2)
f2
(3)
f3
Номер 2
Какие из этих функций функционально полны в слабом смысле?
Ответ:
В таблице приведены три функцииf1,f2,f3от переменныхx,y,z:
x | y | z | f1 | f2 | f3 |
|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 1 | 0 | 1 | 0 |
0 | 1 | 0 | 0 | 1 | 0 |
0 | 1 | 1 | 1 | 0 | 1 |
1 | 0 | 0 | 0 | 1 | 1 |
1 | 0 | 1 | 0 | 0 | 1 |
1 | 1 | 0 | 1 | 0 | 0 |
1 | 1 | 1 | 1 | 1 | 1 |
Ответ:
(1)
f1
(2)
f2
(3)
f3
Номер 3
Какие из этих функций функционально полны в слабом смысле?
Ответ:
В таблице приведены три функцииf1,f2,f3от переменныхx,y,z:
x | y | z | f1 | f2 | f3 |
|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 1 | 0 |
0 | 0 | 1 | 0 | 1 | 0 |
0 | 1 | 0 | 0 | 0 | 0 |
0 | 1 | 1 | 0 | 0 | 0 |
1 | 0 | 0 | 0 | 0 | 1 |
1 | 0 | 1 | 1 | 0 | 1 |
1 | 1 | 0 | 1 | 1 | 0 |
1 | 1 | 1 | 1 | 1 | 1 |
Ответ:
(1)
f1
(2)
f2
(3)
f3
Упражнение 10:
Номер 1
Ответ:
Номер 1
Дано равенство ∀x∀yP(x,y) = ∃x∃yP(x,y).
Какие из утверждений верны?
Ответ:
(1)
Это равенство неверно при любых
Р.
(2)
Это равенство верно при любых
Р.
(3)
Это равенство при некоторых
Р верно, а при некоторых других Р неверно.
Номер 2
Ответ:
Дано равенство ∀x∃yP(x,y) = ∃x∀yP(x,y).
Какие из утверждений верны?
Ответ:
(1)
Это равенство неверно при любых
Р.
(2)
Это равенство верно при любых
Р.
(3)
Это равенство при некоторых
Р верно, а при некоторых других Р неверно.
Номер 3
Ответ:
Дано равенство ∀x∃yP(x,y) = ∃y∀xP(x,y).
Какие из утверждений верны?
Ответ:
(1)
Это равенство неверно при любых
Р.
(2)
Это равенство верно при любых
Р.
(3)
Это равенство при некоторых
Р верно, а при некоторых других Р неверно.
Упражнение 11:
Номер 1
Ответ:
Номер 1
Какая из формул исчисления предикатов выражает
тот факт, что в множестве М, в котором определен
частичный порядок, не существует максимального элемента?
Ответ:
(1)
∀x∃y(x∈M→((y∈M)&(x<y)))
(2)
∀x∃y((x∈M)&(y∈M)&(x<y))
(3)
∀x∃y((x∈M)∨((y∈M)&(x<y)))
Номер 2
Ответ:
Какая из формул исчисления предикатов выражает
тот факт, что в множестве М, в котором определен
частичный порядок, не существует минимального элемента?
Ответ:
(1)
∀x∃y(x∈M→((y∈M)&(y<x)))
(2)
∀x∃y((x∈M)&(y∈M)&(y<x))
(3)
∀x∃y((x∈M)∨((y∈M)&(y<x)))
Номер 3
Ответ:
Какая из формул исчисления предикатов выражает
тот факт, что в множестве М, в котором определен
частичный порядок, существует максимальный элемент?
Ответ:
(1)
∃x∀y(((x∈M)&(y∈M)&(x<y))→(x=y))
(2)
∀x∃y(((x∈M)&(y∈M)&(x<y))→(x=y))
(3)
∃x∃y(((x∈M)&(y∈M)&(x<y))→(x=y))
Упражнение 12:
Номер 1
Ответ:
Номер 1
Отметьте неверную формулу:
Ответ:
(1)
∀x∀yP(x,y) = ∀y∀xP(x,y)
(2)
∀x∃yP(x,y) = ∃y∀xP(x,y)
(3)
∀x(P(x)&Q(x)) = ∀xP(x)&∀xQ(x).
Номер 2
Ответ:
Отметьте неверную формулу:
Ответ:
(1)
∀x(P(x)&Q(x)) = ∀xP(x)&∀xQ(x)
(2)
∃x(P(x)&Q(x)) = ∃xP(x)&∃xQ(x)
(3)
∃x∃yP(x,y) = ∃y∃xP(x,y).
Номер 3
Ответ:
Отметьте неверную формулу:
Ответ:
(1)
∀x∀yP(x,y) = ∀y∀xP(x,y)
(2)
∀x(P(x)∨Q(x)) = ∀xP(x)∨∀xQ(x)
(3)
∃x(P(x)∨Q(x)) = ∃xP(x)∨∃xQ(x).