|
Содержание работы или список заданий
|
Задания к контрольной работе
1. Привести формулы к КНФ.
Определить какой является эта формула?
1) F=A (A B) (A B)
2) F= p q r p
3) F=(pq) p q r
4) F=(p q) (s q p)
5) F= p r p r.
6) F= A (A B) B
7) F=p q r
8) F= ((p q) (q r) p) (p r)
9) F= (p q) (s p s)
10) F= (p (¬(p s)) (s p) )
2. С помощью алгоритма редукции проверить общезначимость следующих формул:
1) (A B) (B A)
2) ((A B) ((A B) (¬B A)))
3) (((A B) С) (A B)) ( A C )
4) ((A B) (B C) A) (A C)
5) ((A B) С) (A ( B C))
6) (A B) (A B)) A
7) (A B) (B C) (A C)
8) (A (¬(A B)) (C A)
9) ((A B) C) (A (B C)).
10) (C (A C)) (C (A B)
3. Выяснить, является ли логически правильными следующие рассуждения. В доказательстве использовать метод резолюций
1. Если Иванов или Петров пользовались на контрольной работе шпаргалкой, то Сидоров не пользовался. Если Петров не пользовался шпаргалкой, то пользовались Сидоров и Захаров. Сидоров пользовался шпаргалкой. Следовательно, Сидоров и Захаров пользовались на контрольной работе шпаргалкой.
2. Если Иванов или Петров пользовались на контрольной работе шпаргалкой, то Сидоров не пользовался. Если Петров не пользовался шпаргалкой, то пользовались Сидоров и Захаров. Сидоров пользовался шпаргалкой. Следовательно, Иванов и Петров пользовались на контрольной работе шпаргалкой.
3. Если Иванов или Петров пользовались на контрольной работе шпаргалкой, то Сидоров не пользовался. Если Петров не пользовался шпаргалкой, то пользовались Сидоров и Захаров. Сидоров пользовался шпаргалкой. Следовательно, Иванов и Сидоров пользовались на контрольной работе шпаргалкой.
4. Если Иванов или Петров пользовались на контрольной работе шпаргалкой, то Сидоров не пользовался. Если Петров не пользовался шпаргалкой, то пользовались Сидоров и Захаров. Сидоров пользовался шпаргалкой. Следовательно, только Сидоров пользовался на контрольной работе шпаргалкой.
5. Наша футбольная команда либо выигрывает матч, либо проигрывает, либо сводит его к ничьей. Если матч выигран или проигран, то он не перенесён. Команда матч не выиграла и не свела его к ничьей. Следовательно, матч не перенесён и проигран.
6. Наша футбольная команда либо выигрывает матч, либо проигрывает, либо сводит его к ничьей. Если матч выигран или проигран, то он не перенесён. Команда матч не выиграла и не свела его к ничьей. Следовательно, матч не перенесён и выигран.
7. Если Перт не встречал Ивана, то либо Иван не был на лекциях, либо Пётр лжёт. Если Иван был на лекциях, то Пётр встречал Ивана, и Сергей был в читальном зале после лекций. Если Сергей был в читальном зале после лекций, то либо Иван не был на лекциях, либо Пётр лжёт. Следовательно, Иван не был на лекциях
8. Если Джон не встречал этой ночью Смита, то либо Джон был убийцей, либо Джон лжет. Если Смит не был убийцей, то Джон не встречал Смита этой ночью, и убийство имело место после полуночи. Если же убийство имело место после полуночи, то либо Смит был убийцей, либо Джон лжет. Следовательно, Смит был убийцей.
9. Если 8 – составное число, то 16 – составное число. Если 16– составное число, то существуют простые числа. Если существуют простые числа, то число 16 – составное. Простые числа существуют. Следовательно, число 8 – составное.
10. Кривая является или эллипсом, или параболой, или гиперболой. Если кривая – эллипс или гипербола, то она центральна. Данная кривая не эллипс и не парабола. Следовательно, она центральная и является гиперболой.
4. Найти клаузальную нормальную (КлНФ) форму для формул логики предикатов
1) xP(x) xQ(x,y)
2) xR(x) x Q(x,y)
3) yxQ(x,y) yR(x,y)
4) y(R(y) yQ(x,y)) x R(x,y)
5) xy Q(x,y) xR(x,y)
6) xR(x) yx(Q(x,y) R(x))
7) x(R(x) xQ(x,y))yR(x,y)
8) R(x) Q(x) yP(x,y) x Q(x)
9) R(x) y(R(y) xQ(x))
10) xP(x,y) yxQ(x,y) xR(x))
5. Написать программу на языке Пролог моделирующую коммутационную (релейно-контактную) схему.
6. Определить сложность алгоритма по порядку величины.
Какому классу задач принадлежит такой алгоритм? Ответ обосновать.
1) O(N*log(N)+N3).
2) O(N+ log(N)).
3) O(log(N)+N!).
4) O(log(N)+N!).
5) O(2n+N).
6) O(5+N3).
7) O(2n+N5).
8) O(N*log(N)+N!).
9) O(log(N)+Nn).
10) O(N*10+N10).
|