uzluga.ru
добавить свой файл
1. Предположим, что высказывание А ® В ложно. Тогда среди следующих высказываний только одно будет ложно. Найдите его:

- В ® А

- А & ØB

- A Ú B

+ ØB ® ØA

- ØA « B


2. Предположим, что высказывание B ® A истинно. Определите, какое из высказываний не может быть ложным:

- A & B

- A « B

- ØA Ú B

- A & ØB

+ A Ú ØB


3. Предположим, что высказывание A ® ØB истинно. Определите, какое из следующих высказываний не может быть истинным:

- A Ú B

+ A & B

- B ® A

- ØA Ú B

- A « B


4. Отметьте формулу, являющуюся тавтологией

- ØP & P

- ØØP ® ØP

+ P ® P

- P ® ØP

- P Ú P


5. Отметьте формулу, не являющуюся тавтологией

- P Ú ØP

- P ® P

- Ø(ØP & P)

- (P & P) ® P

+ P & P


6. Какой из формул равносильна заданная формула: (P ® Q) Ú (Q ® P)

- P « Q

- ØP Ú Q

- (P Ú Q) ® P

- P Ú Q

+ P ® (Q Ú P)


7. В какой из следующих пар содержатся равносильные формулы:

- P « Q и ØP Ú Q

- Ø(P Ú Q) и ØQ & P

+ Q Ú ØP и P ® Q

- Q ® P и ØP & Q

- P ® ØQ и P & Q


8. Решите логическую задачу. Трое друзей, болельщиков автогонок "Формула-1", спорили о результатах предстоящего этапа гонок. «Вот увидишь, Шумахер не придет первым, — сказал Джон. - Первым будет Барикелло.» « Да нет же, победителем будет, как всегда, Шумахер, — воскликнул Ник. — А об Алонзо и говорить нечего, ему не быть первым.» Питер, к которому обратился Ник, возмутился: « Барикелло не видать первого места, а вот Алонзо пилотирует самую мощную машину.» По завершении этапа гонок оказалось, что каждое из двух предположений двоих друзей подтвердилось, а оба предположения третьего из друзей оказались неверны. Кто выиграл этап гонки?

+ Шумахер

- Алонзо

- Барикелло

- Трулли

- Никто из 1-4 ответов


9. Решите логическую задачу. В симфонический оркестр приняли на работу трёх музыкантов: Брауна, Смита и Вессона, умеющих играть на скрипке, флейте, альте, кларнете, гобое и трубе. Известно, что: Смит самый высокий; играющий на скрипке меньше ростом играющего на флейте; играющие на скрипке и флейте и Браун любят пиццу; когда между альтистом и трубачом возникает ссора, Смит мирит их; Браун не умеет играть ни на трубе, ни на гобое. На каких инструментах играет Вессон, если каждый владеет двумя инструментами?

- альт и флейта

- гобой и кларнет

- скрипка и кларнет

+ скрипка и труба

- альт и гобой


10. Решите логическую задачу. Вадим, Сергей и Михаил изучают различные иностранные языки: китайский, японский и арабский. На вопрос, какой язык изучает каждый из них, один ответил: "Вадим изучает китайский, Сергей не изучает китайский, а Михаил не изучает арабский". Впоследствии выяснилось, что в этом ответе только одно утверждение верно, а два других ложны. Какой язык изучает Сергей?

+ китайский

- японский

- арабский


11. Какое из предложений не является высказыванием:

- Солнце есть спутник Земли;

- железо - металл;

- все волки - млекопитающие;

- курица не птица;

+ который час?


12. Какое из предложений является высказыванием:

- который час?

- студент университета;

+ Волга впадает в Каспийское море;

- пейте томатный сок;

- 13 января 2005г


13. Дано высказывание: МИШЕНЬ ПОРАЖЕНА ПЕРВЫМ ВЫСТРЕЛОМ Какое из следующих высказываний является отрицанием данного:

- мишень поражена вторым выстрелом;

- мишень не поражена;

+ мишень не поражена первым выстрелом;

- мишень поражена;

- мишень поражена третьим выстрелом.


14. Какой из методов не является алгоритмом проверки общезначимости в логике высказываний?

- алгоритм Квайна

- правила вывода

- метод обратных рассуждений

- метод дедукции

+ метод резолюций


15. Решите логическую задачу. На следствии по делу о похищении автомобиля были допрошены четыре гангстера - Андре, Боб, Стив и Том. Андре сказал, что машину похитил Боб. Боб утверждал, что виноват Том. Том заверил следователя, что Боб лжет. Стив настаивал, что автомобиль угнал не он. Следователю удалось установить, что только один из гангстеров сказал правду. Кто похитил автомобиль?

+ Стив

- Андре

- Боб

- Том

- Следователь


16. Логическая операция...истинна всегда, кроме случая, когда оба высказывания ложны

- импликация

- эквивалентность

+ дизъюнкция

- конъюнкция


17. Логическая операция...истинна только в случае, когда оба высказывания истинны

- Импликация

- Эквивалентность

- Дизъюнкция

+ Конъюнкция


18. Логическая операция...истинна всегда, кроме случая, когда А - истинно, а В - ложно

+ Импликация

- Эквивалентность

- Дизъюнкция

- Конъюнкция


19. Логическая операция...истинна, когда оба высказывания ложны или истинны одновременно

- Импликация

+ Эквивалентность

- Дизъюнкция

- Конъюнкция


20. Предложение "Неверно, что Юра занимается теннисом" соответствует логической операции

- Импликация

- Эквивалентность

+ Отрицание

- Конъюнкция


21. Прочитайте утверждение: "x(x Î N Þ $y(y Î N & y > x))

+ Для всякого натурального числа есть большее

- Для некоторых натуральных чисел есть большее

- Для каждого натурального числа есть меньшее

- Для одного натурального числа есть меньшее

- Существуют равные натуральные числа


22. Прочитайте утверждение: $z (z Î R & x < z & z < y)

+ Между х и у есть действительное число

- Есть число, большее х

- Найдется число, большее z

- Есть действительное число, меньшее у

- Существует z


23. Какое из предложений не является предикатом:

- (x + y)2 = x2 + 2xy + y2

- Река х впадает в озеро Байкал

+ Число 9 делится на 3

- Если число х делится на 3, то х делится и на 9

- х2 + х - 6 = 0


24. Какое из следующих высказываний ложно:

+ "x x>7

- $x x>7

- "x $y x < y

- "y $x x < y

- "y $x x > y


25. Дана формула "x (P(x) & Q(x) ® R(x)), где предикаты P(x), Q(x), R(x) определены на множестве натуральных чисел. Найти ее значение, если: P(x) = "Число х делится на 3" Q(x) = "Число х делится на 4" R(x) = "Число х делится на 2"

+ истина

- ложь


26. Дана формула "x (P(x) & Q(x) ® R(x)), где предикаты P(x), Q(x), R(x) определены на множестве натуральных чисел. Най ти ее значение, если: P(x) = "Число х делится на 3" Q(x) = "Число х делится на 4" R(x) = "Число х делится на 5"

- истина

+ ложь


27. Является ли формула $x R(x) ® "x R(x) общезначимой?

- да

+ нет


28. Является ли формула "x R(x) ® $x R(x) общезначимой?

+ да

- нет


29. Для условия x = 0 выясните, является ли оно необходимым и является ли оно достаточным, чтобы выполнялось неравенство x2 - 2x - 8 <= 0.

+ является достаточным, но не является необходимым

- является необходимым, но не является достаточным

- является необходимым и достаточным

- не является необходимым и не является достаточным


30. Для условия -2 <= x <= 10 выясните, является ли оно необходимым и является ли оно достаточным, чтобы выполнялось неравенство x2 - 2x - 8 <= 0.

- является достаточным, но не является необходимым

+ является необходимым, но не является достаточным

- является необходимым и достаточным

- не является необходимым и не является достаточным


31. Какое из утверждений не является категорическим высказыванием?

+ "x(S(x) & P(x))

- "x(S(x) ® P(x))

- "x(S(x) ® ØP(x))

- $x(S(x) & P(x))

- $x(S(x) & ØP(x))


32. Сколько существует правильных модусов непосредственных заключений?

- 8

+ 10

- 16

- 20

- 32


33. Пусть х и у - вещественные числа, а Р(х, у) обозначает "х + у = 0". Даны два высказывания: 1 - "x $y P(x, y) 2 - $x "y P(x, y)

Определите их истинность.

+ 1 - истинно, 2 - ложно

- 1 - ложно, 2 - истинно

- оба истинны

- оба ложны


36. Какому из перечисленных требований не обязан удовлетворять алгоритм?

- алгоритм должен содержать конечное количество элементарно выполнимых предписаний, т.е. удовлетворять требованию конечности записи

- алгоритм должен выполнять конечное количество шагов при решении задачи, т.е. удовлетворять требованию конечности действий

- алгоритм должен быть единым для всех допустимых исходных данных, т.е. удовлетворять требованию универсальности

- алгоритм должен приводить к правильному по отношению к поставленной задаче решению, т.е. удовлетворять требованию правильности

+ алгоритм должен содержать обращение к себе самому, т.е. удовлетворять требованию рекурсивности


37. Линейным называется алгоритм с трудоемкостью ...

- O(log n)

- O(n2)

- O(n log n)

- O(n3)

+ O(n)


38. Экспоненциальным называется алгоритм с трудоемкостью ...

- O(log n)

- O(n2)

- O(n log n)

+ O(3n)

- O(n)


39. Алгоритмическая проблема - это ...

- проблема определения верхней оценки сложности алгоритма

+ проблема построения алгоритма с заданными свойствами

- проблема создания программы по существующему алгоритму

- проблема разрешимости множества

- проблема определения нижней оценки сложности алгоритма


40. Алгоритм для размещения данных требует памяти. Память считается ...

- непрерывной;

+ дискретной;

- неоднородной;

- оперативной;

- универсальной.


41. Класс задач, недетерминированно разрешимых за полиномиальное время, называется:

- KNF.

- NPC;

- P;

+ NP;

- NPH;


42. Какое из перечисленных множеств принадлежит классу Р:

+ произвольный контекстно-свободный язык;

- множество всех выполнимых формул логики высказываний;

- множество всех пар изоморфных графов;

- множество всех систем линейных неравенств с целыми коэффициентами, разрешимых в целых числах.


43. Какое из перечисленных множеств принадлежит классу NР:

+ множество всех выполнимых формул логики высказываний;

- произвольный контекстно-свободный язык;

- множество пар изоморфных графов со степенями вершин, не превосходящими d (для всякого d);

- множество всех систем линейных неравенств с целыми коэффициентами, разрешимых в действительных числах.


44. Утверждение "Класс задач, решаемых в любой формальной алгоритмической модели, совпадает с классом задач, которые могут быть решены интуитивно алгоритмическими методами"

известно, как ...

- теорема Черча

- теорема Геделя

- теорема Поста

+ тезис Черча

- теорема Тьюринга


45. Что из перечисленного не является вычислительной моделью?

- машина Тьюринга

- машина Поста

- конечные детерминированные автоматы

- рекурсивные функции

+ калькулятор


46. Программа для машины Тьюринга с алфавитом A = {a0, a1, ..., am}: 0q1 ® Rq2 0q2 ® 0q0 aiq1 ® Rq2 aiq2 ® Rq2 реализует операцию ...

+ сдвига вправо

- сдвига влево

- копирования

- транспозиции

- стирания


47. Что не является компонентом машины Тьюринга:

- лента;

- считывающая/записывающая головка;

- система команд;

- множество состояний;

+ процессор.


48. Дана схема подстановок алгоритма Маркова: a0 ® 0a a1 ® 1b b0 ® 1a b1 ® 0b a ® Ù b ® Ù ® a Результатом ее применения к слову 001101110101 будет слово:

- 010110011010

+ 001011001111

- 110011101100

- 100111000101

- 001101001101


49. Дана схема подстановок алгоритма Маркова: a0 ® 0a a1 ® 1b b0 ® 1a b1 ® 0b a ® Ù b ® Ù ® a Результатом ее применения к слову 101100110010 будет слово:

+ 111010101011

- 110011011010

- 111000101010

- 010100101001

- 000101101111


50. В модели машины Тьюринга внешняя память представлена в виде ..., разделенной на секции одинакового размера - ячейки памяти.

- конечной ленты

- бесконечной вправо ленты

+ бесконечной в обе стороны ленты

- бесконечной влево ленты


51. Конечное число символов, с помощью которых кодируется информация, подаваемая в машину, и информация, которая вырабатывается в процессе её работы, называется ...

+ внешним алфавитом

- внутренним алфавитом

- совокупностью

- алфавитом


52. В ячейке ленты может храниться

- только одна буква внутреннего алфавита

- произвольное количество букв внешнего алфавита

+ только одна буква внешнего алфавита

- произвольное количество букв внутреннего алфавита


53. Управляющая головка - это устройство, которое в каждый момент времени "умеет" обозревать

- две ячейки ленты, идущие подряд

- произвольное количество ячеек ленты

- две произвольные ячейки

+ одну ячейку ленты


54. Какой элементарной операции нет в модели машины Тьюринга?

+ Н (Назад)

- П (Вправо)

- Л (Влево)

- Н (На месте)


55. Унарная запись натурального числа n - это набор, состоящий из

- (n-1)-ого символа "|"

+ (n+1)-ого символа "|"

- n-ого символа "|"

- (n+1)-ого символа "1"


56. Что не является элементом машины Тьюринга?

- бесконечная в обе стороны лента

- считывающая/записывающая головка

+ матрица

- ячейка


66. Основой языков логического программирования служит:

- метод математической индукции;

- метод Квайна;

- метод дедукции;

+ метод резолюций;

- нормальный алгоритм Маркова.


67. Алгоритмические логики создаются с целью ...

+ описания семантики языков программирования;

- построения доказательств;

- верификации программ;

- интерпретации категорий;

- описания способов вывода высказываний.


68. В нечеткой логике пропозициональная переменная интерпретируется:

+ степенью опредленности;

- k-значной функцией;

- степенью достоверности;

- символом будущего;

- истинностным значением.


69. Модальное высказывание - это:

- тождественно ложное высказывание;

- квазивысказывание;

- тождественно истинное высказывание;

+ высказывание, характеризующее степень достоверности суждения;

- общее высказывание.


70. Какая из перечисленных логик не является предикатной:

- многосортная логика первого порядка;

+ модальная логика;

- слабая логика второго порядка;

- бесконечная логика;

- логика с новыми кванторами.


71. Некоторое предложение о первоначальных терминах теории называется:

+ аксиома;

- теорема;

- лемма;

- правило;

- метод.


76. Логическая операция, соответствующая союзу "И" - это

- импликация

- эквивалентность

- дизъюнкция

+ конъюнкция


77. Логическая операция, соответствующая союзу "или" - это

- импликация

- эквивалентность

+ дизъюнкция

- конъюнкция


78. Логическая операция, соответствующая союзу "если ..., то ..." - это

+ импликация

- эквивалентность

- дизъюнкция

- конъюнкция


79. Логическая операция, соответствующая союзу "тогда и только тогда, когда" - это

- импликация

+ эквивалентность

- дизъюнкция

- конъюнкция


80. Суждение - это...

- Форма мышления, в которой отражаются признаки предмета

- Совокупность правил, которым подчиняется процесс мышления

+ Мысль, в которой что-то утверждается или отрицается

- Прием мышления, когда из исходного знания получается новое знание


81. Понятие - это...

+ Форма мышления, в которой отражаются признаки предмета

- Совокупность правил, которым подчиняется процесс мышления

- Мысль, в которой что-то утверждается или отрицается

- Прием мышления, когда из исходного знания получается новое знание


82. Умозаключение - это...

- Форма мышления, в которой отражаются признаки предмета

- Совокупность правил, которым подчиняется процесс мышления

- Мысль, в которой что-то утверждается или отрицается

+ Прием мышления, когда из исходного знания получается новое знание


83. Логика - это...

- Форма мышления, в которой отражаются признаки предмета

+ Совокупность правил, которым подчиняется процесс мышления

- Мысль, в которой что-то утверждается или отрицается

- Прием мышления, когда из исходного знания получается новое знание


84. Наука о законах и формах правильного мышления - это

- Женская логика

+ Формальная логика

- Шахматная логика

- Математическая логика


85. Наука о логических связях и отношениях, лежащих в основе дедуктивного вывода - это

- Женская логика

- Формальная логика

- Шахматная логика

+ Математическая логика


86. Рассуждение, в котором из заданных двух суждений выводится третье - это

- Высказывание

+ Силлогизм

- Понятие

- Логика


87. Повествовательное предложение, относительно которого можно сказать истинно оно или ложно - это

+ Высказывание

- Силлогизм

- Понятие

- Логика


88. Форма мышления, в которой отражаются признаки предмета - это

- Высказывание

- Силлогизм

+ Понятие

- Логика


89. Совокупность правил, которым подчиняется процесс мышления

- Высказывание

- Силлогизм

- Понятие

+ Логика


90. Какой закон не является законом математической логики?

- Закон исключённого третьего

- Закон двойного отрицания

+ Закон Ома

- Закон непротиворечия