Главная / Алгоритмы и дискретные структуры /
Алгоритмы и теория вычислений / Тест 12
Алгоритмы и теория вычислений - тест 12
Упражнение 1:
Номер 1
Традиционный набор операций в исчислении высказываний включает
Ответ:
 (1) дизъюнкцию 
 (2) конъюнкцию 
 (3) импликацию 
Номер 2
Синонимом названия операции конъюнкции является
Ответ:
 (1) логическое "или" 
 (2) логическое "и" 
 (3) логическое "если" 
Номер 3
Синонимом названия операции импликации является
Ответ:
 (1) логическое "и" 
 (2) логическое "если" 
 (3) логическое "не" 
Упражнение 2:
Номер 1
Стандартное правило вывода состоит из
Ответ:
 (1) посылки 
 (2) заключения 
 (3) алфавита 
Номер 2
Стандартное правило вывода обычно называют
Ответ:
 (1) modus ponens 
 (2) modens ponus 
 (3) ponus modens 
Номер 3
Принцип рассуждения от следствия к причине называется
Ответ:
 (1) дедукция 
 (2) абдукция 
 (3) редукция 
Упражнение 3:
Номер 1
Метатеорема - это
Ответ:
 (1) утверждение о свойствах некоторой теории 
 (2) утверждение о свойствах исчисления предикатов  
 (3) утверждение о свойствах конечных автоматов 
Номер 2
Проверка истинности утверждения на первом шаге при n=1 в методе математической индукции называется
Ответ:
 (1) базисом индукции 
 (2) индукционным шагом 
 (3) леммой индукции 
Номер 3
Индукционный шаг в методе математической индукции - это
Ответ:
 (1) доказательство того, что утверждение верно для n=1 
 (2) доказательство того, что утверждение верно для n=k 
 (3) доказательство того, то утверждение верно для n=k+1 при доказанной истинности для n=k 
Упражнение 4:
Номер 1
В исчисления предикатов существуют кванторы
Ответ:
 (1) общности 
 (2) существования 
 (3) незначимости 
Номер 2
Если переменная х
не связана в формуле F
, то она называется
Ответ:
 (1) чистой 
 (2) свободной 
 (3) несвязанной 
Номер 3
Терм - это
Ответ:
 (1) символ переменной 
 (2) n-арная функция нескольких переменных, где каждая переменная - это терм 
 (3) одно из правил вывода исчисления предикатов 
Упражнение 5:
Номер 1
Исчисления предикатов
Ответ:
 (1) включает в себя ИВ 
 (2) включено в ИВ 
 (3) не связано с ИВ 
Номер 2
Формулы в исчислении предикатов образуются с помощью
Ответ:
 (1) переменных 
 (2) кванторов 
 (3) знаков логических операций 
Номер 3
Аксиомы исчисления предикатов формируются из
Ответ:
 (1) аксиом ИВ 
 (2) аксиом для кванторов общности и существования 
 (3) аксиом для логических операций 
Упражнение 6:
Номер 1
Правила вывода исчисления предикатов формируются из
Ответ:
 (1) modus ponens 
 (2) правило введения квантора общности 
 (3) правило введения квантора существования 
Номер 2
Утверждение об объектах исчисления предикатов, подлежащее доказательству, называется
Ответ:
 (1) теоремой 
 (2) леммой 
 (3) аксиомой 
Номер 3
Утверждение о некоторой теореме исчисления предикатов, подлежащее доказательству, называется
Ответ:
 (1) метатеоремой 
 (2) теоремой 
 (3) метааксиомой 
Упражнение 7:
Номер 1
Предметная область, соответствующая формальной системе, называется
Ответ:
 (1) моделью формальной системы 
 (2) интерпретацией формальной системы 
 (3) областью значений формальной системы 
Номер 2
Предметная область называется моделью, если
Ответ:
 (1) хотя бы одна теорема формальной системы является в этой области истинной 
 (2) любая теорема формальной системы является в этой области истинной 
 (3) ни одна из теорем формальной системы не является в этой области истинной 
Номер 3
Формула называется общезначимой, если она
Ответ:
 (1) истинна в любой предметной области 
 (2) истинна в некоторой предметной области 
 (3) она имеет интерпретацию 
Упражнение 8:
Номер 1
Теорема Гёделя о полноте исчисления предикатов утверждает, что
Ответ:
 (1) исчисление предикатов является неполным 
 (2) исчисление предикатов является полным 
 (3) исчисление предикатов разрешимо 
Номер 2
Исчисление предикатов называется разрешимым, если
Ответ:
 (1) не существует такого алгоритма, который для любой формулы покажет, выводима она, или нет 
 (2) существует такой алгоритм, который для любой формулы покажет, выводима она, или нет 
 (3) оно полно 
Номер 3
Теорема Чёрча утверждает, что
Ответ:
 (1) исчисление предикатов разрешимо 
 (2) исчисление предикатов неразрешимо 
 (3) исчисление предикатов полно 
Упражнение 9:
Номер 1
Литера в методе резолюций - это
Ответ:
 (1) буква 
 (2) отрицание буквы 
 (3) цифра 
Номер 2
Пустой дизъюнкт в методе резолюций обозначается
Ответ:
 (1) квадратом 
 (2) треугольником 
 (3) кругом 
Номер 3
Аббревиатура КНФ в контексте логических исчислений - это
Ответ:
 (1) конъюнктивной нормальная форма 
 (2) конечная нормальная форма 
 (3) конечная неполная форма 
Упражнение 10:
Номер 1
Аббревиатура ДНФ в контексте логических исчислений - это
Ответ:
 (1) дизъюнктивная нормальная форма 
 (2) декомпозиция нормальной формы 
 (3) декомпозиционная неполная форма 
Номер 2
Контрарная пара в методе резолюций - это
Ответ:
 (1) операции конъюнкции и дизъюнкции 
 (2) операции отрицания и импликации 
 (3) литера и ее отрицание 
Номер 3
Идея метода резолюций состоит в
Ответ:
 (1) доказательстве тождественной ложности некоторой формулы 
 (2) доказательстве тождественной истинности некоторой формулы 
 (3) тождественных преобразованиях некоторой формулы с целью получения в итоге пустого дизъюнкта 
Упражнение 11:
Номер 1
Метод резолюций по своему смыслу более всего близок методу
Ответ:
 (1) математической индукции 
 (2) доказательства от противного 
 (3) математической аппроксимации 
Номер 2
Обязательным требованием метода резолюций является приведение исходной формулы к
Ответ:
 (1) контрарной паре 
 (2) дизъюнктивная нормальная форма 
 (3) конъюнктивной нормальная форма 
Номер 3
Метод аналитических таблиц в отличие от метода резолюций
Ответ:
 (1) не требует приведения формулы к конъюнктивной нормальной форме 
 (2) требует приведение формулы к конъюнктивной нормальной форме 
 (3) требует приведения формулы к дизъюнктивной нормальной форме 
Упражнение 12:
Номер 1
К формулам конъюнктивного типа относятся
Ответ:
 (1) отрицание дизъюнкции 
 (2) отрицание имликации 
 (3) двойное отрицание 
Номер 2
К формулам дизъюнктивного типа относятся
Ответ:
 (1) отрицание конъюнкции 
 (2) дизъюнкция 
 (3) импликация 
Номер 3
К формулам конъюнктивного типа не относится
Ответ:
 (1) дизъюнкция 
 (2) отрицание дизъюнкции 
 (3) отрицание импликации 
 (4) импликация