С.Ф. Тюрин, Ю.А. Аляев ДИСКРЕТНАЯ МАТЕМАТИКА ТЕСТ-ДРАЙВ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ И МАТЕМАТИЧЕСКОЙ ЛОГИКЕ
.pdft16. Стандартная форма представления формулы логики предикатов предполагает приведение
(1): к СКНФ
(2): КНФ (3): ДНФ (4): СДНФ
Уровень – сложный
t17. Выражения х уР(х, у) и у хР(х, у)
(1): не равносильны, но х уР(х, у) у хР(х, у) = 1 (2): не равносильны, но у хР(х, у) х уР(х, у) = 1 (3): не равносильны, но у хР(х, у) х уР(х, у) = 0 (4): равносильны
t18. Выражения х уР(х, у) и у хР(х, у) (1): равносильны
(2): не равносильны, но х уР(х, у) у хР(х, у) = 1 (3): не равносильны, но у хР(х, у) х уР(х, у) = 1 (4): не равносильны, но у хР(х, у) х уР(х, у) = 0
t19. Выражения х уР(х, у) и у хР(х, у) (1): равносильны
(2): не равносильны, но у хР(х, у) х уР(х, у) = 1 (3): не равносильны, но х уР(х, у) у хР(х, у) = 0 (4): не равносильны, но х уР(х, у) у хР(х, у) = 1
t20. Выражения у хР(х, у) и х уР(х, у) (1): равносильны
(2): не равносильны, но х уР(х, у) у хР(х, у) = 1 (3): не равносильны, у хР(х, у) х уР(х, у) = 1 (4): не равносильны, но у хР(х, у) х уР(х, у) = 1
171
1.3. Формализация суждений
Уровень – легкий
t1. Клаузальная форма представления формул логики предикатов – это
(1): ДНФ (2): КНФ (3): СКНФ (4): СДНФ
t2. Предложение – это элемент
(1): ДНФ (2): СКНФ (3): СДНФ (4): КНФ
t3. Дизъюнкт – это элемент
(1): ДНФ (2): СКНФ (3): КНФ (4): СДНФ
t4. Для представления произвольной формулы логики предикатов в клаузальной форме необходимо
(1): исключить знаки импликации (2): ввести знаки импликации (3): исключить предикаты (4): ввести знаки
t5. Для уменьшения области действия знаков инверсии до одной предикатной буквы в процессе представления произвольной формулы логики предикатов в клаузальной форме необходимо
(1): ввести общее отрицание всей формулы (2): использовать закон Де Моргана
172
(3): ввести двойное отрицание формулы (4): ввести тройное отрицание формулы
t6. Замена в области действия квантора связанной с ним переменной, другой переменной, не совпадающей с какой-либо другой переменной, входящей в область действия квантора
(1): всегда невозможна (2): всегда возможна
(3): возможна только для квантора (4): возможна только для квантора
t7. Переименование связанных переменных, при котором каждый квантор имеет собственную переменную, отличную от других, называется
(1): элиминацией импликации (2): сколемизацией (3): стандартизацией переменных (4): резолюцией
t8. Исключение кванторов существования называется (1): элиминацией (2): резольвенцией (3): сколемизацией (4): факторизацией
t9. Перенесение всех кванторов в начало формулы называется получением
(1): приведенной формы (2): клаузальной формы (3): сколемизацией (4): предваренной формы
173
t10. После исключения кванторов общности из предваренной формы получают
(1): КНФ (2): СКНФ (3): ДНФ (4): СДНФ
Уровень – средний
t11. Для формулы хG(x) функция Сколема имеет вид
(1): G(а) (2): G(x) (3): G(у)
(4): хG(x)
t12. Формализовать в логике предикатов: «Расстояние от Перми до Лондона»
(1): F(а, b) (2): F(x, y) (3): f(H(а), b) (4): f(а, b)
t13. Формализовать в логике предикатов: «Ромео любит Джульетту»
(1): f(r, j) (2): L(r, x) (3): L(r, j) (4): L(x, j)
t14. Формализовать в логике предикатов: «Все стремятся к счастью»
(1): хН(х) (2): хН(х) (3): Н(х)
(4): Н(а)
174
t15. Формализовать в логике предикатов: «Некоторые студенты занимаются научными исследованиями»
(1): хН(х) (2): Н(х) (3): Н(а) (4): хТ(х)
t16. Формализовать в логике предикатов: «Некоторые задачи решаются каждым студентом»
(1): х уG(x, y) (2): х уG(x, y) (3): х уG(x, y) (4): х уG(x, y)
Уровень – сложный
t17. Введение в формулу х[ уG(x, y)] функции Сколема позволяет получить формулу
(1): хG(x, a) (2): хG(x, g(x)) (3): хG(x, g(y)) (4): хG(x, g(a))
t18. Формализовать в логике предикатов суждение типа А: SaP (1): х[S(x) P(x)]
(2): х[S(x)P(x)]
(3): х[S(x) P(x)], где знак означает инверсию (4): х[S(x) ( P(x))], где знак означает инверсию
t19. Формализовать в логике предикатов суждение типа А: SiP (1): х[S(x) P(x)]
(2): х[S(x) P(x)], где знак означает инверсию
(3): х[S(x)P(x)]
(4): х[S(x) ( P(x))], где знак означает инверсию
175
t20. Формализовать в логике предикатов суждение типа А: SeP (1): х[S(x) ( P(x))], где знак означает инверсию
(2): х[S(x)P(x)]
(3): х[S(x) P(x)], где знак означает инверсию (4): х[S(x) ( P(x))], где знак означает инверсию
t21. Формализовать в логике предикатов суждение типа А: SoP (1): х[S(x) P(x)]
(2): х[S(x)P(x)]
(3): х[S(x) ( P(x))], где знак означает инверсию (4): х[S(x) P(x)], где знак означает инверсию
1.4. Метод резолюций в логике предикатов
Уровень – легкий
t1. В первой модели формализации SaP представляется как (1): х[S(x) ( P(x))], где знак означает инверсию (2): х[S(x) P(x)], где знак означает инверсию
(3): х[S(x) P(x)] (4): х[S(x)P(x)]
t2. В первой модели формализации SiP представляется как (1): х[S(x) ( P(x))], где знак означает инверсию
(2): х[S(x)P(x)]
(3): х[S(x) P(x)], где знак означает инверсию
(4): х[S(x) P(x)]
t3. В первой модели формализации SeP представляется как
(1): х[S(x) P(x)]
(2): х[S(x) P(x)], где знак означает инверсию
(3): х[S(x)P(x)]
(4): х[S(x) ( P(x))], где знак означает инверсию
176
t4. В первой модели формализации SoP представляется как (1): х[S(x) P(x)], где знак означает инверсию
(2): х[S(x) ( P(x))], где знак означает инверсию
(3): х[S(x)P(x)] (4): х[S(x) P(x)]
t5. Подстановка – это прием, в результате которого из некоторых формул получают
(1): их частные случаи (2): их общие случаи (3): приведенную формулу
(4): предваренную формулу
t6. Подстановка {(t3, x1), …, (tj, xi), …, (tn, xk)} означает, что всюду, где производится эта подстановка
(1): терм tj заменяется переменной xi (2): переменная xi заменяется термом tj (3): функция tj заменяется переменной xi (4): константа tj заменяется переменной xi
t7. Формулы, имеющие совместный частный случай, называются (1): резольвируемыми (2): элиминируемыми (3): унифицируемыми (4): квантифицируемыми
t8. Резольвентой двух предложений S(x) P(x), P(a), где знак означает инверсию, является
(1): P(а)
(2): S(а), где знак означает инверсию (3): P(a), где знак означает инверсию
(4): S(а)
177
t9. Резольвентой двух предложений S(x) P(x), P(a) М(а), где знак означает инверсию, является
(1): P(а) М(а)
(2): S(а) М(а), где знак означает инверсию (3): P(a)М(а), где знак означает инверсию
(4): S(а) М(а)
t10. Резольвентой двух предложений P(x), P(a), где знак означает инверсию, является
(1): P(а) (2): 1 (3):
(4): P(a), где знак означает инверсию
Уровень – средний
t11. Во второй модели формализации SaP представляется как (1): х[S(x) ( P(x))], где знак означает инверсию
(2): хS(x) х[S(x) P(x)]
(3): х[S(x) P(x)], где знак означает инверсию
(4): х S(x) х[S(x) P(x)], где знак означает инверсию
t12. Во второй модели формализации SiP представляется как (1): х[S(x) ( P(x))], где знак означает инверсию
(2): хS(x) х[S(x) P(x)] (3): х[S(x)P(x)]
(4): хS(x) х[S(x) P(x)], где знак означает инверсию
t13. Во второй модели формализации SeP представляется как
(1): хS(x) х[S(x) P(x)]
(2): х[S(x) ( P(x))], где знак означает инверсию (3): х[S(x) P(x)], где знак означает инверсию
(4): хS(x) х[S(x) P(x)], где знак означает инверсию
178
t14. Во второй модели формализации SoP представляется как (1): х S(x) х[S(x) P(x)], где знак означает инверсию (2): х[S(x) ( P(x))], где знак означает инверсию
(3): хS(x) х[S(x) P(x)] (4): х[S(x)P(x)]
t15. Для формулы х[S(x) ( P(x))], где знак означает инверсию, дизъюнкт имеет вид
(1): ( S(x))( P(x)), где знак означает инверсию (2): ( S(x))P(x), где знак означает инверсию
(3): S(x)P(x)
(4): ( S(x)) ( P(x)), где знак означает инверсию
t16. Для формулы х[S(x) P(x)] дизъюнкт имеет вид (1): ( S(x)) ( P(x)), где знак означает инверсию (2): ( S(x))P(x), где знак означает инверсию
(3): ( S(x)) P(x), где знак означает инверсию
(4): S(x)P(x)
Уровень – сложный
t17. Для формулы х[S(x)P(x)] дизъюнкты имеют вид (1): ( S(а)), ( P(а)), где знак означает инверсию
(2): S(x), P(а) (3): S(а)P(x) (4): S(а), P(а)
t18. Для формулы х[S(x)( P(x))], где знак означает инверсию, дизъюнкты имеют вид
(1): ( S(а)), ( P(а)), где знак означает инверсию (2): S(а), P(а), где знак означает инверсию
(3): S(а), P(а)
(4): S(а)P(у)
179
t19. Для модуса Barbara (1) дизъюнкты имеют вид
(1): M(x) P(x), S(y) M(y), S(a), P(a), где знак означает инверсию
(2): M(x), P(x), S(y) M(y), S(a), P(a), где знак означает инверсию
(3): M(x), P(x), S(y) M(y), S(x), P(x), где знак означает инверсию
(4): M(a) P(a), S(y) M(y), S(a), P(a), где знак означает инверсию
t20. Для модуса Darapti (3) дизъюнкты имеют вид
(1): M(a) P(a), M(y) S(y), S(z) P(z), где знак озна-
чает инверсию
(2): M(x) P(x), M(y) S(y), S(z) P(z), где знак озна-
чает инверсию
(3): M(x) P(x), M(y) S(y), S(a) P(a), где знак озна-
чает инверсию
(4): M(x) P(x), M(a) S(a), S(z) P(z), где знак озна-
чает инверсию
2.Логические исчисления
2.1.Понятие формальной системы и формальной теории
Уровень – легкий
t1. Теории не бывают (1): содержательными (2): бессодержательными (3): формализованными (4): формальными
t2. Системы операций над объектами, понимаемыми как слова в определенных алфавитах, называются
(1): формальными системами (2): содержательными системами
180