4. Некрасова М.Г. Дискретная математика часть 1
.pdf
Задание 6. Разбить высказывание на элементарные и записать в виде кванторной формулы логики предикатов, используя наименьшее возможное число предикатов наименьшей местности. Привести формулу к предваренной нормальной форме.
Для любого натурального числа найдется число больше данного, которое тоже является натуральным.
Решение.
1) Введем обозначения:
Р(х): «число х – натуральное», х R, где R – множество действительных чисел; Q(x, у): «x < y», где (х, у) R R.
Исходное выражение можно записать в виде следующей формулы:
х P x y P y Q x, y .
2) Сначала приведем формулу к приведенной нормальной форме, т.е. избавимся от знака импликации, используя равносильности логики высказываний и логики предикатов:
х P x y P y Q x, y х P x y P y Q x, y .
Для приведения к предваренной нормальной форме необходимо вынести все кванторы в начало формулы (используя равносильности логики предикатов):
х P x y P y Q x, y х у P x P y Q x, y .
Задание 7. Построить интерпретацию формулы логики предикатов:
хP x, y zQ z yR y S .
Решение.
Данная формула является открытой (первое вхождение переменной у не связано квантором), и формула содержит нульместный предикат (S). Значит, интерпретация будет состоять из четырех шагов:
1)Зададим множество, на котором будем рассматривать все предикаты: М = R, где R – множество действительных чисел.
2)Каждой предикатной букве ставим в соответствие предикат:
P(x, y): «x < y»; Q(z): «z – четное число»; R(y): «делителем у является единица».
3)Нульместному предикату припишем значение И.
4)Свободному вхождению переменной у припишем значение 0.
является лож-При данной интерпретации высказывание
ным (читается: «любое действительное число х меньше у = 0»),zQ z – истинное высказывание (читается: «существует действительное
131
число z, которое не является четным»), yR y – истинное высказывание
(читается: «любое действительное число у делится на единицу без остатка»), S – истинное высказывание. В результате получили высказывание,
которое можно записать: 0 (1 1 1) 1.
Значит, данная интерпретация обращает формулу логики предикатов в истинное высказывание.
4. КЛЮЧИ К ПРОВЕРОЧНЫМ ТЕСТАМ
4.1.Ключ к проверочному тесту по теме «Теория множеств»
Вопрос 1. |
|
Ответ: 1 – а, 2 – б, 3 – в |
Коэффициент сложности 12 |
|
|
|
|
|
|
|
|
Вопрос 2. |
|
Ответ: 1 – а, 2 – б, 3 – в |
Коэффициент сложности 12 |
|
|
|
|
|
|
|
|
Вопрос 3. |
|
Ответ: 1 – а, 2 – б, 3 – в |
Коэффициент сложности 12 |
|
|
|
|
|
|
|
|
Вопрос 4. |
|
Ответ: 1 – а, 2 – б, 3 – в |
Коэффициент сложности 12 |
|
|
|
|
|
|
|
|
Вопрос 5. |
|
Ответ: 16 |
Коэффициент сложности 6 |
|
|
|
|
|
|
|
|
Вопрос 6. |
|
Ответ: 4 |
Коэффициент сложности 6 |
|
|
|
|
|
|
|
|
Вопрос 7. |
|
Ответ: 8 |
Коэффициент сложности 6 |
|
|
|
|
|
|
|
|
Вопрос 8. |
|
Ответ: 2 |
Коэффициент сложности 6 |
|
|
|
|
|
|
|
|
Вопрос 9. |
|
Ответ: 16 |
Коэффициент сложности 6 |
|
|
|
|
|
|
|
|
Вопрос 10. |
|
Ответ: 32 |
Коэффициент сложности 6 |
|
|
|
|
|
|
|
|
Вопрос 11. |
|
Ответ: 2 |
Коэффициент сложности 6 |
|
|
|
|
|
|
|
|
Вопрос 12. |
|
Ответ: 8 |
Коэффициент сложности 6 |
|
|
|
|
|
|
|
|
|
132 |
|
Вопрос 13. |
|
Ответ: 4 |
Коэффициент сложности 6 |
|
|
|
|
|
|
|
|
Вопрос 14. |
|
Ответ: 1 |
Коэффициент сложности 6 |
|
|
|
|
|
|
|
|
Вопрос 15. |
|
Ответ: M = {1, 2, 4, 5, 6} |
Коэффициент сложности 6 |
|
|
|
|
|
|
|
|
Вопрос 16. |
|
Ответ: M = {0, 3, 7, 8} |
Коэффициент сложности 6 |
|
|
|
|
|
|
|
|
Вопрос 17. |
|
Ответ: M = {0, 3, 7, 8, 9, 10} |
Коэффициент сложности 6 |
|
|
|
|
|
|
|
|
Вопрос 18. |
|
Ответ: M = {3, 4, 7, 8} |
Коэффициент сложности 6 |
|
|
|
|
|
|
|
|
Вопрос 19. |
|
Ответ: M = {1, 2, 4, 5, 6} |
Коэффициент сложности 6 |
|
|
|
|
|
|
|
|
Вопрос 20. |
|
Ответ: M = {1, 2, 5, 6} |
Коэффициент сложности 6 |
|
|
|
|
|
|
|
|
Вопрос 21. |
|
Ответ: M = {9, 10} |
Коэффициент сложности 6 |
|
|
|
|
|
|
|
|
Вопрос 22. |
|
Ответ: |
Коэффициент сложности 6 |
|
M = {1, 2, 3, 4, 5, 6, 7, 8} |
|
|
|
Вопрос 23. |
|
Ответ: |
Коэффициент сложности 6 |
|
M = {0, 3, 4, 5, 6, 7, 8, 9, 10} |
|
|
|
Вопрос 24. |
|
Ответ: M = {3, 4, 7, 8} |
Коэффициент сложности 6 |
|
|
|
|
|
|
|
|
Вопрос 25. |
|
Ответ: 1 – а, 2 – б, 3 – в |
Коэффициент сложности 8 |
|
|
|
|
|
|
|
|
Вопрос 26. |
|
Ответ: 1 – а, 2 – б, 3 – в |
Коэффициент сложности 8 |
|
|
|
|
|
|
|
|
Вопрос 27. |
|
Ответ: 1 – а, 2 – б, 3 – в |
Коэффициент сложности 8 |
|
|
|
|
|
|
|
|
Вопрос 28. |
|
Ответ: 1 – а, 2 – б, 3 – в |
Коэффициент сложности 8 |
|
|
|
|
|
|
|
|
Вопрос 29. |
|
Ответ: 1 – а, 2 – б, 3 – в |
Коэффициент сложности 8 |
|
|
|
|
|
|
|
|
|
133 |
|
Вопрос 30. |
|
Ответ: 1 – а, 2 – б, 3 – в |
||||
Коэффициент сложности 8 |
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Вопрос 31. |
|
Ответ: 1 – а, 2 – б, 3 – в |
||||
Коэффициент сложности 8 |
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Вопрос 32. |
|
Ответ: 1 – а, 2 – б, 3 – в |
||||
Коэффициент сложности 8 |
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Вопрос 33. |
|
Ответ: б) пустое |
||||
Коэффициент сложности 1 |
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Вопрос 34. |
|
Ответ: г) |
|
|
|
0 |
|
|
|
||||
Коэффициент сложности 1 |
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Вопрос 35. |
|
Ответ: в) равномощными |
||||
Коэффициент сложности 1 |
|
|||||
|
|
|
|
|
|
|
|
|
|
||||
Вопрос 36. |
|
Ответ: а) подмножеством |
||||
Коэффициент сложности 1 |
|
множества В |
||||
|
|
|
||||
Вопрос 37. |
|
Ответ: а) множество всех |
||||
Коэффициент сложности 1 |
|
возможных подмножеств |
||||
|
|
исходного множества |
||||
Вопрос 38. |
|
Ответ: в) перечисление |
||||
Коэффициент сложности 1 |
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Вопрос 39. |
|
Ответ: 3 |
||||
Коэффициент сложности 2 |
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Вопрос 40. |
|
Ответ: 5 |
||||
Коэффициент сложности 2 |
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Вопрос 41. |
|
Ответ: 3 |
||||
Коэффициент сложности 2 |
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Вопрос 42. |
|
Ответ: 1 |
||||
Коэффициент сложности 2 |
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Вопрос 43. |
|
Ответ: 6 |
||||
Коэффициент сложности 2 |
|
|||||
|
|
|
|
|
|
|
|
|
|
||||
Вопрос 44. |
|
Ответ: а) объединением |
||||
Коэффициент сложности 5 |
|
множеств А и В |
||||
|
|
|
||||
Вопрос 45. |
|
Ответ: а) объединением |
||||
Коэффициент сложности 5 |
|
множеств А и В |
||||
|
|
|
||||
Вопрос 46. |
|
Ответ: б) пересечением |
||||
Коэффициент сложности 5 |
|
множеств А и В |
||||
|
|
|
|
|
|
|
|
134 |
|
|
|
|
|
Вопрос 47. |
Ответ: в) разностью |
|
Коэффициент сложности 5 |
множеств А и В |
|
|
|
|
Вопрос 48. |
Ответ: г) симметрической |
|
Коэффициент сложности 5 |
разностью множеств А и В |
|
|
|
|
Вопрос 49. |
Ответ: 1 – а, 2 – б, 3 – в |
|
Коэффициент сложности 4 |
||
|
||
|
|
|
Вопрос 50. |
Ответ: 1 – а, 2 – б, 3 – в |
|
Коэффициент сложности 4 |
||
|
||
|
|
|
Вопрос 51. |
Ответ: 1 – а, 2 – б, 3 – в |
|
Коэффициент сложности 4 |
||
|
||
|
|
|
Вопрос 52. |
Ответ: 1 – а, 2 – б, 3 – в |
|
Коэффициент сложности 4 |
||
|
||
|
|
|
Вопрос 53. |
Ответ: 1 – а, 2 – б, 3 – в |
|
Коэффициент сложности 4 |
||
|
||
|
|
|
Вопрос 54. |
Ответ: 1, 2, 3, 4, 5 |
|
Коэффициент сложности 10 |
||
|
||
|
|
|
Вопрос 55. |
Ответ: 3, 4, 5, 6, 7 |
|
Коэффициент сложности 10 |
||
|
||
|
|
|
Вопрос 56. |
Ответ: а){1, 2, 3, 4, 5}; |
|
Коэффициент сложности 9 |
в) {a, b, c, d, e}; |
|
|
г) {3, 4, 5, 6, 7} |
|
Вопрос 57. |
Ответ: а); б); в) |
|
Коэффициент сложности 3 |
||
|
||
|
|
|
Вопрос 58. |
Ответ: а); б); в); г); д); е) |
|
Коэффициент сложности 7 |
||
|
||
|
|
|
Вопрос 59. |
Ответ: а); б); в) |
|
Коэффициент сложности 11 |
||
|
||
|
|
135
4.2.Ключ к проверочному тесту по теме «Бинарные отношения и алгебраические операции»
Вопрос 1. |
|
Ответ: в) транзитивность |
Коэффициент сложности 5 |
|
|
|
|
|
|
|
|
Вопрос 2. |
|
Ответ: а) рефлексивность; |
Коэффициент сложности 5 |
|
б) симметричность; |
|
|
в) транзитивность; |
|
|
г) отношение эквивалентности |
Вопрос 3. |
|
Ответ: б) симметричность |
Коэффициент сложности 5 |
|
|
|
|
|
|
|
|
Вопрос 4. |
|
Ответ: а) рефлексивность; |
Коэффициент сложности 5 |
|
в) транзитивность |
|
|
|
Вопрос 5. |
|
Ответ: в) транзитивность |
Коэффициент сложности 5 |
|
|
|
|
|
|
|
|
Вопрос 6. |
|
Ответ: а) рефлексивность; |
Коэффициент сложности 5 |
|
в) транзитивность |
|
|
|
Вопрос 7. |
|
Ответ: а) рефлексивность; |
Коэффициент сложности 5 |
|
б) симметричность; |
|
|
в) транзитивность; |
|
|
г) отношение эквивалентности |
Вопрос 8. |
|
Ответ: а) рефлексивность; |
Коэффициент сложности 5 |
|
б) симметричность; |
|
|
в) транзитивность; |
|
|
г) отношение эквивалентности |
Вопрос 9. |
|
Ответ: а) рефлексивность; |
Коэффициент сложности 5 |
|
б) симметричность; |
|
|
в) транзитивность; |
|
|
г) отношение эквивалентности |
Вопрос 10. |
|
Ответ: б) симметричность |
Коэффициент сложности 5 |
|
|
|
|
|
|
|
|
Вопрос 11. |
|
Ответ: 1 – а, 2 – б, 3 – в |
Коэффициент сложности 12 |
|
|
|
|
|
|
|
|
Вопрос 12. |
|
Ответ: 1 – а, 2 – б, 3 – в |
Коэффициент сложности 12 |
|
|
|
|
|
|
|
|
Вопрос 13. |
|
Ответ: 1 – а, 2 – б, 3 – в |
Коэффициент сложности 12 |
|
|
|
|
|
|
|
|
|
136 |
|
Вопрос 14. |
|
Ответ: 1 – а, 2 – б, 3 – в |
Коэффициент сложности 12 |
|
|
|
|
|
|
|
|
Вопрос 15. |
|
Ответ: 1 – а, 2 – б, 3 – в |
Коэффициент сложности 12 |
|
|
|
|
|
|
|
|
Вопрос 16. |
|
Ответ: в) биекция |
Коэффициент сложности 9 |
|
|
|
|
|
|
|
|
Вопрос 17. |
|
Ответ: б) отношением |
Коэффициент сложности 1 |
|
эквивалентности |
|
|
|
Вопрос 18. |
|
Ответ: в) рефлексивное |
Коэффициент сложности 1 |
|
|
|
|
|
|
|
|
Вопрос 19. |
|
Ответ: а) {<5,1>, <5,0>, <6,1>, |
Коэффициент сложности 5 |
|
<6,0>, <7,1>, <7,0>}; |
|
|
|
Вопрос 20. |
|
Ответ: а) отношением |
Коэффициент сложности 1 |
|
частичного порядка |
|
|
|
Вопрос 21. |
|
Ответ: г) не зависит |
Коэффициент сложности 1 |
|
от расстановки скобок |
|
|
|
Вопрос 22. |
|
Ответ: б) симметричное |
Коэффициент сложности 1 |
|
|
|
|
|
|
|
|
Вопрос 23. |
|
Ответ: г) транзитивное |
Коэффициент сложности 1 |
|
|
|
|
|
|
|
|
Вопрос 24. |
|
Ответ: г) инъективна |
Коэффициент сложности 1 |
|
и сюръективна |
|
|
|
Вопрос 25. |
|
Ответ: в) (4,5), (4,6), (5,5), (5,6) |
Коэффициент сложности 5 |
|
|
|
|
|
|
|
|
Вопрос 26. |
|
Ответ: инъекция |
Коэффициент сложности 6 |
|
|
|
|
|
|
|
|
Вопрос 27. |
|
Ответ: сюръекция |
Коэффициент сложности 6 |
|
|
|
|
|
|
|
|
Вопрос 28. |
|
Ответ: б) сюръекция |
Коэффициент сложности 9 |
|
|
|
|
|
|
|
|
Вопрос 29. |
|
Ответ: г) не является |
Коэффициент сложности 9 |
|
ни инъекцией, ни сюръекцией |
|
|
|
Вопрос 30. |
|
Ответ: функция |
Коэффициент сложности 2 |
|
|
|
|
|
|
|
|
|
137 |
|
Вопрос 31. |
Ответ: 1 – а, 2 – б, 3 – в |
|
Коэффициент сложности 8 |
||
|
||
|
|
|
Вопрос 32. |
Ответ: 1 – а, 2 – б, 3 – в |
|
Коэффициент сложности 8 |
||
|
||
|
|
|
Вопрос 33. |
Ответ: 1 – а, 2 – б, 3 – в |
|
Коэффициент сложности 8 |
||
|
||
|
|
|
Вопрос 34. |
Ответ: 1 – а, 2 – б, 3 – в |
|
Коэффициент сложности 8 |
||
|
||
|
|
4.3.Ключ к проверочному тесту по теме «Логика высказываний»
Вопрос 1. |
Ответ: 1 – а, 2 – б, 3 – в |
|
Коэффициент сложности 8 |
||
|
||
|
|
|
Вопрос 2. |
Ответ: 1 – а, 2 – б, 3 – в |
|
Коэффициент сложности 8 |
||
|
||
|
|
|
Вопрос 3. |
Ответ: 1 – а, 2 – б, 3 – в |
|
Коэффициент сложности 8 |
||
|
||
|
|
|
Вопрос 4. |
Ответ: 1 – а, 2 – б, 3 – в |
|
Коэффициент сложности 8 |
||
|
||
|
|
|
Вопрос 5. |
Ответ: 1 – а, 2 – б, 3 – в |
|
Коэффициент сложности 8 |
||
|
||
|
|
|
Вопрос 6. |
Ответ: 1 – а, 2 – б, 3 – в |
|
Коэффициент сложности 8 |
||
|
||
|
|
|
Вопрос 7. |
Ответ: 1 – а, 2 – б, 3 – в |
|
Коэффициент сложности 8 |
||
|
||
|
|
|
Вопрос 8. |
Ответ: 1 – а, 2 – б, 3 – в |
|
Коэффициент сложности 8 |
||
|
||
|
|
|
Вопрос 9. |
Ответ: 1 – а, 2 – б, 3 – в |
|
Коэффициент сложности 8 |
||
|
||
|
|
|
Вопрос 10. |
Ответ: 1 – а, 2 – б, 3 – в |
|
Коэффициент сложности 8 |
||
|
||
|
|
|
Вопрос 11. |
Ответ: 1 – а, 2 – б, 3 – в |
|
Коэффициент сложности 8 |
||
|
||
|
|
138
Вопрос 12. |
|
Ответ: 1 |
Коэффициент сложности 6 |
|
|
|
|
|
|
|
|
Вопрос 13. |
|
Ответ: 1 |
Коэффициент сложности 6 |
|
|
|
|
|
|
|
|
Вопрос 14. |
|
Ответ: 1 |
Коэффициент сложности 6 |
|
|
|
|
|
|
|
|
Вопрос 15. |
|
Ответ: 0 |
Коэффициент сложности 6 |
|
|
|
|
|
|
|
|
Вопрос 16. |
|
Ответ: 0 |
Коэффициент сложности 6 |
|
|
|
|
|
|
|
|
Вопрос 17. |
|
Ответ: 1 |
Коэффициент сложности 6 |
|
|
|
|
|
|
|
|
Вопрос 18. |
|
Ответ: 1 |
Коэффициент сложности 6 |
|
|
|
|
|
|
|
|
Вопрос 19. |
|
Ответ: 0 |
Коэффициент сложности 6 |
|
|
|
|
|
|
|
|
Вопрос 20. |
|
Ответ: 0 |
Коэффициент сложности 6 |
|
|
|
|
|
|
|
|
Вопрос 21. |
|
Ответ: 1 |
Коэффициент сложности 6 |
|
|
|
|
|
|
|
|
Вопрос 22. |
|
Ответ: г) 0 |
Коэффициент сложности 1 |
|
|
|
|
|
|
|
|
Вопрос 23. |
|
Ответ: а) да |
Коэффициент сложности 1 |
|
|
|
|
|
|
|
|
Вопрос 24. |
|
Ответ: а) 0 |
Коэффициент сложности 1 |
|
|
|
|
|
|
|
|
Вопрос 25. |
|
Ответ: а) логическая опера- |
Коэффициент сложности 1 |
|
ция, которая истинна только |
|
|
тогда, когда исходное |
|
|
высказывание ложно |
Вопрос 26. |
|
Ответ: а) да |
Коэффициент сложности 5 |
|
|
|
|
|
|
|
|
Вопрос 27. |
|
Ответ: а) легенда |
Коэффициент сложности 1 |
|
|
|
|
|
|
|
|
Вопрос 28 |
|
Ответ: в) a b |
Коэффициент сложности 5 |
|
|
|
|
|
|
|
|
|
139 |
|
Вопрос 29. |
Ответ: 0 |
|
Коэффициент сложности 2 |
||
|
||
|
|
|
Вопрос 30. |
Ответ: да |
|
Коэффициент сложности 1 |
||
|
||
|
|
|
Вопрос 31. |
Ответ: 0 |
|
Коэффициент сложности 1 |
||
|
||
|
|
|
Вопрос 32. |
Ответ: 1 – а, 2 – б, 3 – в |
|
Коэффициент сложности 12 |
||
|
||
|
|
|
Вопрос 33. |
Ответ: 1 – а, 2 – б, 3 – в |
|
Коэффициент сложности 12 |
||
|
||
|
|
|
Вопрос 34. |
Ответ: 1 – а, 2 – б, 3 – в |
|
Коэффициент сложности 12 |
||
|
||
|
|
4.4.Ключ к проверочному тесту по теме «Булевы функции»
Вопрос 1. |
Ответ: 1101 |
|
Коэффициент сложности 2 |
||
|
||
|
|
|
Вопрос 2. |
Ответ: 0001 |
|
Коэффициент сложности 2 |
||
|
||
|
|
|
Вопрос 3. |
Ответ: 0110 |
|
Коэффициент сложности 2 |
||
|
||
|
|
|
Вопрос 4. |
Ответ: 1001 |
|
Коэффициент сложности 2 |
||
|
||
|
|
|
Вопрос 5. |
Ответ: 1110 |
|
Коэффициент сложности 6 |
||
|
||
|
|
|
Вопрос 6. |
Ответ: 0111 |
|
Коэффициент сложности 6 |
||
|
||
|
|
|
Вопрос 7. |
Ответ: 0110 |
|
Коэффициент сложности 6 |
||
|
||
|
|
|
Вопрос 8. |
Ответ: 1001 |
|
Коэффициент сложности 6 |
||
|
||
|
|
|
Вопрос 9. |
Ответ: 1011 |
|
Коэффициент сложности 6 |
||
|
||
|
|
140