Контрольные ОГУ Курсовые ОГУ
20 рублей за вопрос
Письма присылайте на Почтовый ящик
1 Логика высказываний
1 Высказыванием называется:
а) любое повествовательное предложение, которое истинно либо ложно;
б) любое предложение, которое только истинно;
в) любое предложение, которое только ложно;
2 Выберите правильный вариант:
а) A → B ≡ ¬A ∨ B ;
б) A → B ≡ ¬A & B ;
в) A → B ≡ ¬A ∩ B ;
г) A → B ≡ ¬A ∧ B ;
3 Тавтологией (тождественно истинной пропозициональной формой или общезначимой формулой) называется:
а) пропозициональная форма, которая принимает значение И при любой совокупности истинностных значений пропозициональных букв, входящих в нее;
б) логическая операция, с помощью которой из двух данных высказываний А и В образуется новое высказывание, обозначаемое А⇒В, которое ложно тогда и только тогда, когда посылка А истинна, а заключение В ложно;
в) логическая операция, с помощью которой из двух данных высказываний А и В образуется новое высказывание, обозначаемое А∨В, которое ложно тогда и только тогда, когда ложны оба высказывания А и В;
г) логическая операция, с помощью которой из двух данных высказываний А и В образуется новое высказывание, обозначаемое А&В, которое истинно тогда и только тогда, когда А и В оба истинны.
4 Какие из следующих предложений не являются высказываниями?
а) В созвездии Кассиопеи есть жизнь;
б) 2 – четное число;
в) город Париж находится в Азии;
г) 3>5;
5 Выберите правильный вариант и нажмите кнопку «Ответить».
а) ¬(A & B) ≡ A ∨ ¬B ;
б) ¬(A & B) ≡ ¬A ∨ B ;
в) ¬(A & B) ≡ ¬A ∨ ¬B ;
г) ¬(A & B) ≡ A ∨ B .
2 Приложения алгебры высказываний
1 Дизъюнктивной нормальной формой (д.н.ф.) называется:
а) дизъюнкция элементарных произведений;
б) конъюнкция элементарных произведений;
в) импликация элементарных произведений;
г) конъюнкция и импликация произведений;
2 Пропозициональная форма называется конъюнктивной нормальной формой (к.н.ф.), если:
а) представляет собой конъюнкцию элементарных сумм;
б) представляет собой дизъюнкцию элементарных сумм;
в) представляет собой импликацию элементарных сумм;
г) представляет собой сумму элементарных отношений;
3 Выберите правильный вариант.
а) Функцией алгебры высказываний (булевой функцией) называется n-местная операция на множестве {0,1}.
б) Функцией алгебры высказываний (булевой функцией) называется n-местная операция на множестве {0,10}.
в) Функцией алгебры высказываний (булевой функцией) называется n-местная операция на множестве {0,2}.
г) Функцией алгебры высказываний (булевой функцией) называется n-местная операция на множестве {0,1000}.
4 Конъюнкция это:
а) логическая операция, с помощью которой из двух данных высказываний А и В образуется новое высказывание, обозначаемое А&В, которое истинно тогда и только тогда, когда А и В оба истинны;
б) логическая операция, с помощью которой из двух данных высказываний А и В образуется новое высказывание, обозначаемое А∨В, которое ложно тогда и только тогда, когда ложны оба высказывания А и В;
в) логическая операция, с помощью которой из двух данных высказываний А и В образуется новое высказывание, обозначаемое А⇒В, которое ложно тогда и только тогда, когда посылка А истинна, а заключение В ложно;
г) логическая операция, при помощи которой из двух данных высказываний А и В образуется новое высказывание, обозначаемое А≡В, которое истинно тогда и только тогда, когда А и В принимают одинаковые истинностные значения;
5 Дизъюнкция это:
а) логическая операция, с помощью которой из двух данных высказываний А и В образуется новое высказывание, обозначаемое А&В, которое истинно тогда и только тогда, когда А и В оба истинны;
б) логическая операция, с помощью которой из двух данных высказываний А и В образуется новое высказывание, обозначаемое А∨В , которое ложно тогда и только тогда, когда ложны оба высказывания А и В;
в) логическая операция, с помощью которой из двух данных высказываний А и В образуется новое высказывание, обозначаемое А⇒В, которое ложно тогда и только тогда, когда посылка А истинна, а заключение В ложно;
г) логическая операция, при помощи которой из двух данных высказываний А и В образуется новое высказывание, обозначаемое А≡В, которое истинно тогда и только тогда, когда А и В принимают одинаковые истинностные значения.
3 Аксиоматическая система в исчислении высказываний
1 Импликация (следование) это:
а) логическая операция, с помощью которой из двух данных высказываний А и В образуется новое высказывание, обозначаемое А&В, которое истинно тогда и только тогда, когда А и В оба истинны.
б) логическая операция, с помощью которой из двух данных высказываний А и В образуется новое высказывание, обозначаемое А∨В , которое ложно тогда и только тогда, когда ложны оба высказывания А и В.
в) логическая операция, с помощью которой из двух данных высказываний А и В образуется новое высказывание, обозначаемое А⇒В, которое ложно тогда и только тогда, когда посылка А истинна, а заключение В ложно.
г) логическая операция, при помощи которой из двух данных высказываний А и В образуется новое высказывание, обозначаемое А≡В, которое истинно тогда и только тогда, когда А и В принимают одинаковые истинностные значения.
2 Эквивалентность это:
а) логическая операция, с помощью которой из двух данных высказываний А и В образуется новое высказывание, обозначаемое А&В, которое истинно тогда и только тогда, когда А и В оба истинны.
б) логическая операция, с помощью которой из двух данных высказываний А и В образуется новое высказывание, обозначаемое А∨В , которое ложно тогда и только тогда, когда ложны оба высказывания А и В.
в) логическая операция, с помощью которой из двух данных высказываний А и В образуется новое высказывание, обозначаемое А⇒В, которое ложно тогда и только тогда, когда посылка А истинна, а заключение В ложно.
г) логическая операция, при помощи которой из двух данных высказываний А и В образуется новое высказывание, обозначаемое А≡В, которое истинно тогда и только тогда, когда А и В принимают одинаковые истинностные значения.
3 Противоречием (тождественно ложной пропозициональной формой) называется:
а) пропозициональная форма, принимающая значение Л при любой совокупности истинностных значений пропозициональных букв, входящих в нее.
б) логическая операция, с помощью которой из двух данных высказываний А и В образуется новое высказывание, обозначаемое А⇒В, которое ложно тогда и только тогда, когда посылка А истинна, а заключение В ложно
в) логическая операция, с помощью которой из двух данных высказываний А и В образуется новое высказывание, обозначаемое А∨В , которое ложно тогда и только тогда, когда ложны оба высказывания А и В.
г) логическая операция, с помощью которой из двух данных высказываний А и В образуется новое высказывание, обозначаемое А&В, которое истинно тогда и только тогда, когда А и В оба истинны
4 Высказывание, которое можно получить с помощью подстановки в противоречие, называется:
а) логически ложным высказыванием;
б) логически истинным высказыванием;
в) простым истинным высказыванием;
г) логически взаимозаменимым высказыванием;
5 Пропозициональная форма называется выполнимой если:
а) она принимает значения И хотя бы для одной совокупности значений пропозициональных букв, в нее входящих;
б) она принимает значения Л хотя бы для одной совокупности значений пропозициональных букв, в нее входящих;
в) она принимает значения И;
г) она принимает значения Л;
4 Правила вывода заключения в логике высказывания
1 Проблемой дедукции называется:
а) Выяснение будет ли В логическим следствием из А1, А2,…,Аm, m≥1,.
б) Установление результата конъюнкции
в) Установление результата дизъюнкции
г) Установление результата импликации
2 Укажите правило удаления &: ответ б)
3 Укажите правило введения ˅:
4 Укажите правило введения &: Ответ в)
5 Выражение A,B ├ A&B означает правило:
а) удаление;
б) введения &;
в) перевертывания;
г) сведения к нелепости.
5 Метод резолюций в логике высказываний
1 Правило резолюций:
а) если два дизъюнкта содержат контрарную пару, то их логическим следствием является дизъюнкт, полученный объединением исходных дизъюнктов, из которых исключены литералы контрарной пары.
б) если два дизъюнкта содержат контрарную пару, то их логическим следствием является конъюнкт, полученный пересечением исходных дизъюнктов.
в) если два дизъюнкта содержат контрарную пару, то их логическим следствием является дизъюнкт, полученный пересечением исходных дизъюнктов.
г) если два дизъюнкта одинаковы, то они образуют контрарную пару.
2 Методом резолюций называется:
а) последовательное получение бинарных резольвент из данных дизъюнктов и вновь получаемых дизъюнктов;
б) последовательное получение бинарных резольвент из данных конъюнктов и вновь получаемых конъюнктов;
в) получение бинарных резольвент из данных;
г) не последовательное получение бинарных резольвент из данных;
3 Метод резолюций применяется для:
а) Проверки выполнимости формул
б) Установления факта логического следствия
в) Проверки тавтологий
г) Поиска противоречий
4 Проблема разрешимости (алгебры высказываний) состоит в следующем:
а) существует ли правило, позволяющее для каждой пропозициональной формы А конечным числом действий выяснить, является А выполнимой или нет;
б) при каждой совокупности значений всех пропозициональных букв, входящих в А и В, эти формы принимают одинаковые истинностные значения;
в) перевести КНФ в ДНФ;
г) перевести ДНФ в КНФ.
6 Логика предикатов
1 Предикатом называется:
а) повествовательное предложение об элементах некоторого заданного множества M, которое (предложение) становится высказыванием, если все переменные в нем заменить фиксированными элементами из M;
б) повествовательное предложение об элементах;
в) предложение об элементах высказываний;
г) предложение об фиксированных элементах;
2 Символ ∀х называется:
а) квантором всеобщности;
б) квантором существования;
в) числовым индексом;
г) функцией;
3 Символ ∃х называется:
а) квантором всеобщности;
б) квантором существования;
в) числовым индексом;
г) функцией.
4 Буквы начала латинского алфавита (а,b,с,...) и они же с числовыми индексами (а1,а2,...,b1,b2,...,с1,с2,...) называются:
а) предметными постоянными;
б) предметными переменными;
в) функциональными буквами;
г) свободными переменными.
5 Буквы конца латинского алфавита (х,у,z,...) и они же с числовыми индексами (х1,х2,...,у1,у2,...,z1,z2,...) называются:
а) предметными постоянными;
б) предметными переменными;
в) функциональными буквами;
г) свободными переменными.
7 Алгебра предикатов
1 Формула A→B ложна в данной интерпретации когда:
а) A истинно в этой интерпретации, а B ложно
б) Хотя бы одна из них выполнима в этой интерпретации
в) В этой интерпретации истинно A.
г) A и B принимают значение И одновременно
2 Формула A&B выполнима в данной интерпретации когда:
а) хотя бы одна из них выполнима в этой интерпретации
б) в этой интерпретации истинно A.
в) A истинно в этой интерпретации, а B ложно
г) A и B принимают значение И одновременно хотя бы для одной совокупности значений своих свободных переменных
3 Формула логики предикатов A называется выполнимой если:
а) если интерпретации не существует
б) существует интерпретация, в которой выполнимо две операции
в) существует интерпретация, в которой выполнима A
г) существует интерпретация, в которой выполнимы все операции
4 Формулы A и B логики предикатов называют равносильными если:
а) каждая из них логически не влечет другую
б) каждая из них зависит друг от друга
в) каждая из них не зависима
г) каждая из них логически влечет другую
5 Формула A≡B выполнима в данной интерпретации когда:
а) A и B принимают значение И одновременно или значение Л
б) в этой интерпретации истинно A.
в) A истинно в этой интерпретации, а B ложно
г) хотя бы одна из них выполнима в этой интерпретации.
8 Формы логики предикатов
1 Формула вида: Q1Q2...QnВ, где Q1,Q2,...,Qn любая совокупность кванторов, а формула В не содержит кванторов называется:
а) формулой кванторов;
б) формулой в пренексной нормальной форме
в) формулой в предваренной нормальной форме
г) формулой в предваренной нормальной форме или в пренексной нормальной форме
2 Сколемовская стандартная форма имеет вид:
а) ∀x∀y(P(x,y)∨ R(x,f4(x,y),f1(x),f2(f3(f4(x,y))))).
б) (P(x,y)∨ R(x,f4(x,y),f1(x),f2(f3(f4(x,y))))).
в) А
г) ∀x∀y.
3 Константы и функции, используемые для замены переменных квантора существования, называются:
а) сколемовскими функциями;
б) литералом (литерой) в логике предикатов;
в) переменными;
г) дизъюнкцию литералов;
11 Дедуктивные теории
1 Полуэффективным процессом считается:
а) некоторая процедура;
б) некоторый процесс;
в) некоторый алгоритм;
г) заданный алгоритм.
2 Дедукцией называется:
а) когда из множества всех формул языка выделено некоторым дедуктивным способом;
б) форма мышления, когда заключение выводится чисто логическим путем из некоторых данных посылок;
в) форма мышления, посредством которой от одного факта переходят к одной гипотезе;
г) форма мышления, посредством которой от некоторых фактов или истинных высказываний переходят к некоторой гипотезе;
3 Дедуктивная теория считается заданной, если:
а) задан алфавит и правила образования выражений (слов) в этом алфавите.
б) заданы правила образования формул (правильно построенных выражений) языка.
в) из множества всех формул языка выделено некоторым дедуктивным способом (который будет описан ниже) подмножество
г) все варианты верны
4 Дедуктивные теории, в которых множество теорем не покрывает все множество формул называются:
а) противоречивыми;
б) непротиворечивыми;
в) полными;
г) неполными.
5 Дедуктивная теория, в том числе и исчисление высказываний, является разрешимой, если:
а) понятие теоремы не имеет смысла;
б) понятие теоремы не эффективно;
в) понятие теоремы эффективно;
г) теория не разрешима;
12 Неклассические логики
1 Выражение x&y = min(x,y) это:
а) конъюнкция;
б) дизъюнкция;
в) произведение по модулю ;
г) сумма по модулю;
2 Выберите правильный вариант: выражение xVy = max(x,y) это:
а) конъюнкция;
б) произведение;
в) дизъюнкция;
г) сумма;
3 Выберите правильный вариант: выражение x*y = x*y (mod k) это:
а) сумма по модулю;
б) произведение по модулю;
в) конъюнкция;
г) дизъюнкция.
4 Выберите правильный вариант:
Выражение x+y = x+y (mod k) это:
а) произведение по модулю;
б) дизъюнкция;
в) конъюнкция;
г) сумма по модулю.
5 Нечетким высказыванием называется:
а) предложение, относительно которого можно судить о степени его конъюнкции;
б) предложение, относительно которого можно судить о степени его истинности или ложности;
в) предложение, относительно которого можно судить о степени его дизъюнкции;
г) предложение, относительно которого можно судить о степени его импликации.
13 Понятие алгоритма
1 Алфавитом называется:
а) непустое множество символов
б) пустое множество;
в) множество символов;
г) подмножество символов.
2 Символы алфавита называются:
а) значениями;
б) буквами;
в) обозначениями;
г) цифрами.
3 Словом в данном алфавите называется:
а) последовательность значений алфавита;
б) конечная последовательность цифр алфавита;
в) конечная последовательность букв алфавита;
г) последовательность символов алфавита;
4 Пустая конечная последовательность букв алфавита называется:
а) высказыванием;
б) предложением;
в) словом;
г) пустым словом;
5 Алфавит А называется расширением алфавита В, если:
а) B⊂A
б) В не принадлежит А;
в) В является следствием А;
г) В является отношением к А;
14 Нормальные алгоритмы маркова
1 Нормальный алгоритм в алфавите А считается заданным, если:
а) задана конечная таблица (схема) формул подстановок слов алфавита А
б) задана одна таблица подстановок;
в) задано несколько таблиц подстановок алфавита;
г) задана одна формула подстановок алфавита;
2 Формула подстановки называется:
а) заключительной подстановкой;
б) формулой подстановки значений;
в) простой подстановкой
г) конечной формулой подстановок значений;
3 Формула подстановки Р → • Q называется:
а) формулой подстановки значений;
б) простой подстановкой;
в) конечной формулой подстановок значений;
г) заключительной подстановкой/
4 Разветвление нормальных алгоритмов, управляемое нормальным
алгоритмом, является:
а) замыканием алгоритма;
б) алгоритмом;
в) нормальным алгоритмом;
г) неразрешимым алгоритмом.
5 Алгоритм A • полученный из A добавлением формулы подстановки
A→•A в качестве последней подстановки называется:
а) подстановкой алгоритма А;
б) замыканием алгоритма A ;
в) дополнением алгоритма А;
г) нормальным алгоритмом А.
15 Алгоритмическая неразрешимость
1 Под массовой проблемой понимается:
а) бесконечное множество однотипных решений;
б) алгоритмическая разрешимость;
в) однотипные задания;
г) бесконечное множество однотипных задач;
2 Как называется массовая проблема, если существует алгоритм (нормальный алгоритм или алгоритм Тьюринга) позволяющий решить каждую задачу этой массовой проблемы:
а) алгоритмически разрешимой;
б) алгоритмически не разрешимой;
в) однотипной;
г) математически не разрешимой;
3 Императивную (процедурную) вычислительную модель называют:
а) когда не имеется последовательная система команд
б) когда имеется последовательная система команд ;
в) когда имеется последовательная система значений
г) когда имеется система цифр
16 Сложность алгоритмов
1 Сложность исходных данных понимается как:
а) число операций;
б) значения операций;
в) длина (размер) их записи ;
г) сложность операций;
2 Временная сложность вычислений (алгоритма) характеризует:
а) значения операций для решения задачи заданного размера
б) длина операций для решения задачи заданного размера
в) сложность операций для решения задачи заданного размера
г) число операций для решения задачи заданного размера
3 Под временной сложностью задачи понимается:
а) сложность любого алгоритма;
б) временная сложность наилучшего алгоритма, известного для ее решения
в) временная сложность любого алгоритма, неизвестного для ее решения
г) временная сложность лучшего алгоритма, известного для ее решения
4 Считается, что алгоритм – полиномиальный или имеет полиномиальную временную сложность, если:
а) существует полином который завершает все вычисления после выполнения p(n) операций;
б) существует один полином G(x) такой, что только на одном входном слове длины n алгоритм завершает вычисления;
в) существует полином p(x) такой, что на любом входном слове длины n алгоритм завершает вычисления после выполнения не более чем p(n) операций
г) существует полином p(x) такой, что на любом входном слове длины n алгоритм не завершает вычисления после выполнения
5 Задача разрешима за полиномиальное время или полиномиально разрешима, если:
а) существует полиномиальный алгоритм решаемый за короткое время;
б) существует неполиномиальный алгоритм;
в) существует любой алгоритм;
г) существует полиномиальный алгоритм;
17 Временная и емкостная сложности алгоритмов
1 Ёмкостная или ленточная сложность алгоритма характеризует:
а) сам алгоритм вычисления;
б) вычисления память для хранения исходных данных;
в) память для хранения данных;
г) оперативная память для хранения исходных данных;
2 Активной зоной ленты (машины Тьюринга) в данный момент времени t называется:
а) связанная часть ленты, содержащая все ячейки в которых имеются символы алфавита машины;
б) несвязанная часть ленты, содержащая все ячейки;
в) связанная часть ленты, содержащая обозреваемую ячейку и все ячейки
в которых имеются символы из внешнего алфавита машины;
г) связанная часть ленты, содержащая только обозреваемую ;
3 Активной зоной при работе машины Тьюринга на числе n называется:
а) объединение всех не активных зон за время вычисления
б) объединение всех не активных зон;
в) объединение всех зон за время вычисления;
г) объединение всех активных зон за время вычисления
4 Для решения задачи линейного программирования существует:
а) симплекс – метод;
б) метод севера - западного угла;
в) прямой симплекс – метод;
г) метод решения итераций;
5 Если такого полинома не существует, временная сложность считается:
а) полиномиальной;
б) временной;
в) экспоненциальной;
г) не решаемой;
