Математическая логика и теория алгоритмов (курс 1)

Концептуальное отличие нечеткой логики от классической заключается в том, что она оперирует

• только промежуточными между значениями «истина» и «ложь» значениями
• только значениями «ложь»
• только значениями «истина» и «ложь»
• не только значениями «истина» и «ложь», но и промежуточными значениями

Число символов, которое может находиться в ячейке ленты конечного автомата, равно _____ (ответ укажите цифрой)

Установите соответствие логических выражений их равносильным выражениям

• xÙx
• y Ú x
• xÙ0
• 1
• xÚ1
• 0
• xÚy
• X

Установите соответствие логических выражений их равносильным выражениям:

• x Ú (y Ú z)
• y Ù x
• x Ú y
• (x Ù y) Ù z
• x Ù (y Ù z)
• y Ú x
• x Ù y
• (x Ú y) Ú z

Теория алгоритмов является частью

• численных методов
• математического анализа
• математической логики
• теории чисел

Функция, равная единице тогда и только тогда, когда предикат истинен, называется

• примитивно рекурсивной
• частично рекурсивной
• характеристической
• вычислимой

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

• длиной программы
• геделевским номером
• Характеристической
• временным ресурсом

Если f(x,y) = х+у и рекурсия проводится по переменной у, то функция g(x) равна

• x+2
• 2x
• x
• x+1

Переменные, фигурирующие в кванторах всеобщности и существования, называются ___________________ переменными

• свободными
• лингвистическими
• связанными
• несвязанными

Выражение qi,аj Пql является ___________ машины Тьюринга

• элементом алфавита
• конечной конфигурацией
• исходной конфигурацией
• Командой

Понятие полноты формальной системы состоит в том, что для любого утверждения s в рамках данной системы одно из утверждений ¬s и s

• Опровергаемо
• Непротиворечиво
• Доказуемо
• Истинно

Множество аксиом вместе с явным определением доказательства составляют

• машину Тьюринга
• формальную систему
• теорию алгоритмов
• рекурсивное множество

Множество A есть подмножество множества В в том и только в том случае, если каждый элемент множества А является

• является элементом другого множества
• элементом множества B
• не является элементом множества B
• является другим множеством

В логике предикатов термин «некоторые» или «существует хотя бы одно значение» обозначается через

• «
• È
• $
• Ú

В основе описания нечеткой логики лежит теория нечетких

• Множеств
• Высказываний
• Отношений
• Выражений

Всякое повествовательное предложение, о котором имеет смысл говорить, что оно (его содержание) истинно или ложно, называется

• отношением
• выражением
• выводом
• высказыванием

Логику, являющуюся многозначной логикой, позволяющей определить промежуточные значения для таких общепринятых оценок, как да/нет, истинно/ложно, черное/белое, называют

• Модальной
• логикой высказываний
• Математической
• Нечеткой

Даны два числовых множества А={1,2,3,4,5} и B={2,5,9}. Установите соответствие между типом операции над данными множествами и ее результатом:

• AÈB
• {2,5}
• A/B
• {1,3,4}
• AÇB
• {1,2,3,4,5,9}

x,y,z – вещественные числа. Эквивалентна утверждению х £y запись

• «z (x+z=y)
• «x (x+z=y)
• $z (y+z=x)
• $z (x+z=y)

Язык логики предикатов является расширением языка логики

• высказываний
• математической
• нечеткой
• формальной

Даны два высказывания: А = «на улице идет дождь» и В = «над моей головой раскрыт зонтик». Установите соответствие между типом операции над данными высказываниями и результирующим высказыванием:

• Дизъюнкция А и В
• над моей головой раскрыт зонтик тогда и только тогда, когда на улице идет дождь
• Импликация А на В
• на улице идет дождь и над моей головой раскрыт зонтик
• Конъюнкция А и В
• если на улице идет дождь, то над моей головой раскрыт зонтик
• Эквиваленция В и А
• или на улице идет дождь или над моей головой раскрыт зонтик

Логическая функция, принимающая значения в некоторой области истинностных значений, называется

• постоянной
• предикатом
• переменной
• константой

Науки, в которых преобладают дедуктивные рассуждения, принято называть

• естественно–научными
• гуманитарными
• техническими
• точными

Логическая связка дизъюнкция высказываний А и В обозначается как

• В Ç А
• А Ù В
• А Ú В
• А È В

Марковский алгоритм носит также название ___________ алгоритма

• Нормального
• Нелинейного
• Недетерминированного
• Стохастического

Укажите соответствие между понятиями теории множеств и их содержанием:

• множество
• множество, не содержащее элементов
• Мощность множества
• множество А есть подмножество множества В в том и только в том случае, если каждый элемент множества А есть также элемент множества В
• подмножество
• критерий оценки размерности множества
• пустое множество
• объединение произвольного количества определенных отличных друг от друга объектов

x,y,z – вещественные числа. Эквивалентна утверждению х Î[y,z] запись

• $t (x+t=z) Ù (y+t=x)
• $t (y+t=z) Ù (y+t=x)
• «t (x+t=z) Ù (y+t=x)
• $t (x+t=z) Ú (y+t=x)

Усеченная разность чисел 5 и 8 (5÷8) равна _____ (ответ укажите цифрой)

Знаком принадлежности элемента некоторому множеству является символ

• Î
• (
• )
• ()

Символы, которые определяют внутреннее состояние машин Тьюринга, образуют

• внешний алфавит
• Команды
• внутренний алфавит
• Выражения

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

• экспликацией
• заключением
• посылками
• суждением

Конечному автомату соответствует грамматика, порождающая

• машину Тьюринга
• регулярный язык
• словарь машины Тьюринга
• язык программирования

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

• Обращения
• Подстановки
• Рекурсии
• Минимизации

Класс примитивно рекурсивных функций ________________________ вычислимых функций

• дополняет класс
• совпадает с классом
• входит в класс
• содержит в себе класс

Установите соответствие между предикатом и областью истинности предиката:

• x + 5 = 1
• Æ
• x2 – 1 = 0
• +1; –1
• x2
• –4

Свойство формальной аксиоматической теории, когда в ее рамках невозможно доказать две противоречащие друг другу теоремы, называется

• Неполнотой
• Полнотой
• Непротиворечивостью
• Противоречивостью

Формализованный язык для однозначной записи алгоритмов называется __________ языком

• Регулярным
• Алгоритмическим
• Метаязыком
• Автоматным

Если А и В – рекурсивные множества, то рекурсивны также множества 1) AÈB; 2) AÇB

• 1 и 2
• не 1 и не 2
• только 2
• только 1

Пересечение множеств А и В обозначается как

• АÈВ
• А В
• A Ç В
• А + В

Аксиоматический подход относится к такому методу доказательства, при котором осуществляется движение мысли от

• общего к общему
• частного к частному
• частного к общему
• общего к частному

Даны два числовых множества А={3,5,7} и B={2,4,6,8}. Установите соответствие между типом операции над данными множествами и ее результатом

• A/B
• {2,3,4,5,6,7,8}
• AÇB
• {Æ}
• AÈB
• {3,5,7}

Математиками, показавшими возможность существования универсальной вычислительной машины, способной выполнить любую эффективную процедуру, являются

• Тьюринг
• Пост
• Гедель
• Гильберт

В состав конечного автомата входят следующие элементы

• датчик случайных чисел
• угадывающий модуль
• читающая головка
• лента, разбитая на ячейки

Символы, которые машина Тьюринга читает и пишет на ленте, образуют

• Выражения
• внутренний алфавит
• внешний алфавит
• Команды

П.р.ф. S2 (х) = х + 2 вычисляется по формуле

• S(S(x))
• S{х+2)
• S(х+3)
• S2(x)

Логическое выражение Ā, где А – высказывание, обозначает

• конъюнкцию
• импликацию
• отрицание
• дополнение

В любой рекурсивно аксиоматизированной формальной системе множество доказуемых утверждений

• Нерекурсивно
• Неперечислимо
• Разрешимо
• рекурсивно перечислимо

Переход конечного автомата происходит

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

Функция, полученная из вычислимой функции с помощью оператора рекурсии, является

• примитивно рекурсивной
• Интегрируемой
• Дифференцируемой
• Вычислимой

Логику можно определять как науку о(об)

• поисках оптимального решения
• правильных способах рассуждения
• анализах парадоксов
• парадоксах в теории абстрактных множеств