Все вопросы к тесту (html) Математическая логика и теория алгоритмов
Алгебра высказываний и алгебра предикатов
Атомарная формула или ее отрицание называется
В логике предикатов термин «некоторые» или «существует хотя бы одно значение» обозначается через
В понятие формулы высказываний входят
Всякое повествовательное предложение, о котором имеет смысл говорить, что оно (его содержание) истинно или ложно, называется
Выражение (комбинация знаков), содержащее знаки «переменных», которое превращается в имя предмета, если вместо «переменных» поставить надлежащим образом выбранные имена предметов, называется ___ формой
Высказывание – это
Даны два числовых множества А={3,5,7} и B={2,4,6,8}. Установите соответствие между типом операции над данными множествами и ее результатом:
Знак, который характеризуется правилами его употребления, – это
Комбинация знаков, содержащая знаки переменных, которая превращается в высказывание при замене переменных именами предметов, называется ___ формой
Логика высказываний и логика предикатов базируются на
Логическая связка дизъюнкция высказываний А и В обозначается как
Логическая связка импликация обозначается как
Логическая связка конъюнкция высказываний А и В обозначается как
Логическая связка эквивалентность обозначается
Логическая функция, принимающая значения в некоторой области истинностных значений, называется
Логическое выражение Ā, где А – высказывание, обозначает
Переменные, фигурирующие в кванторах всеобщности и существования, называются ___ переменными
Под термом имеются ввиду следующие понятия:
Последовательное применение ряда формул теории, такое, что любая формула этого ряда есть либо аксиома этой теории, либо непосредственное следствие из применения предыдущих формул, называется
Система теоретико-множественных операций над высказываниями, которые являются элементами множества, называется ___ высказываний
Термин «для всех» обозначается в логике предикатов символом
Формула в теории, для которой существует механизм вывода в рамках этой теории, называется
Формула, которая истинна при всех интерпретациях, называется
Функция, равная единице тогда и только тогда, когда предикат истинен, называется
Язык логики предикатов является расширением языка логики
Конечные автоматы
Автомат, однократно считывающий входную строку слева направо, называется
В 1–й строке матрицы переходов конечного автомата находятся
В 1–м столбце матрицы переходов конечного автомата находятся
В состав конечного автомата входят следующие элементы
Во внутренних ячейках матрицы переходов записывается
Конечные автоматы могут быть следующих типов:
Переход конечного автомата происходит
Правильность слова, записанного на ленте конечного автомата, определяется по состоянию автомата
Существуют следующие формы записи работы конечного автомата:
Укажите соответствие между понятиями теории конечных автоматов и их содержанием:
Число символов, которое может находиться в ячейке ленты конечного автомата, равно ___ (ответ укажите цифрой)
Логические исчисления
x,y,z – вещественные числа. Эквивалентна утверждению х £y запись
x,y,z – вещественные числа. Эквивалентна утверждению х Î[y,z] запись
В алфавит формального логического языка входят символы
В логике можно выделить следующие основные разделы:
Другое название семантического парадокса – парадокс
Интерес к логике оживился в ___ столетии под влиянием открытия неевклидовых геометрий (ответ укажите римскими цифрами)
Логика Буля основывается на
Логику можно определять как науку о(об)
Наука, изучающая способы обоснования суждений, доказательств, мышления и логического вывода, называется
Науки, в которых преобладают дедуктивные рассуждения, принято называть
Основные типы рассуждений, которые принято выделять в логике называются
Примером логического парадокса может служить парадокс
Примером семантического парадокса могут служить парадаксы
Создателем формальной логики был
Укажите соответствие между названием логической операции и ее обозначением:
Умозаключения – это элементарные рассуждения, в которых из одного или нескольких суждений получается еще одно суждение, называемое
Установите соответствие логических выражений их равносильным выражениям:
Установите соответствие логических выражений их равносильным выражениям:
Установите соответствие между предикатом и областью истинности предиката:
Часть логики, в которой для решения логических задач используется язык математических и логических знаков, – это логика
Неклассические логики
α–уровнем нечеткого подмножества А универсального множества U называется такое подмножество Аα универсального множества U, для которого верно
В модальную логику входят понятия
В основе метода парных сравнений лежит процедура обработки результатов опроса экспертов, представленных в виде
В основе описания нечеткой логики лежит теория нечетких
Если высота нечеткого множества меньше 1, то оно называется
Если высота нечеткого множества равна 1, то оно называется
К термам лингвистической переменной предъявляется лишь требование
Концептуальное отличие нечеткой логики от классической заключается в том, что она оперирует
Логику, являющуюся многозначной логикой, позволяющей определить промежуточные значения для таких общепринятых оценок, как да/нет, истинно/ложно, черное/белое, называют
Наиболее часто на практике используется опрос экспертов
Нечеткая логика – это надмножество логики
Нечеткое отношение – это заданное определенным образом
Одним из самых распространенных методов опросов экспертов является метод парных сравнений, лежащий в основе метода анализа иерархий, предложенного
Способ понимания суждения об объекте, явлении или событии называется
Укажите ограничения, накладываемые на базовые термы лингвистической переменной,
Теория алгоритмов
Временные или пространственные характеристики процесса вычисления называются
Всякое непустое ___ множество является ___ некоторой всюду определенной вычислимой функции
Выражение qi,аj Пql является ___ машины Тьюринга
Вычислительная процедура, приводящая к решению поставленной задачи, называется
Геделевский номер функции e41, равен ___ (ответ укажите цифрами)
Даны два высказывания: А = «на улице идет дождь» и В = «над моей головой раскрыт зонтик». Установите соответствие между типом операции над данными высказываниями и результирующим высказыванием:
Если f(n) = 2n, то функция h(n,m) в рекуррентной формуле равна
Если f(n) = cos(pn), то функция h(n,m) в рекуррентной формуле равна
Если f(n)=n!, то функция h(n,m) в рекуррентной формуле равна
Если f(x,y) = х + у и рекурсия проводится по переменной y, то функция h(х,у,m) равна
Если f(x,y) = х • у и рекурсия проводится по переменной x, то функция h(x,y,m) равна
Если f(x,y) = х+у и рекурсия проводится по переменной у, то функция g(x) равна
Если f(x,y,z) = z•х+у и рекурсия проводится по переменной z, то функция h(х,у,z,m) равна
Если f(x,y,z) == z • х + у и рекурсия проводится по переменной z, то функция g(х,у) равна
Если f(х, y) = х • у и рекурсия проводится по переменной у , то функция g(х) равна
Если f(х, у) = хy и рекурсия проводится по у, то функция g(х) равна ___ (ответ укажите цифрой)
Если f(х, у, z) = х + у2 + z и рекурсия проводится по у , то функция g{х, z) равна
Если f(х, у, z) = х + у2 + z и рекурсия проводится по у , то функция h(х, y, z, m) равна
Если f(х,y) = ху и рекурсия проводится по у, то функция h(х,y,z) равна
Если f(х,у) = х÷у и рекурсия проводится по х, то функция g(у) равна ___ (ответ укажите цифрой)
Если А и В – рекурсивные множества, то рекурсивны также множества 1) AÈB; 2) AÇB
Если А рекурсивно, а В – рекурсивно перечислимо, то множество ___ рекурсивно
Если множество рекурсивно, то оно ___ всюду определенной вычислимой функции
Каждая п.р.ф. (примитивно–рекурсивная функция) имеет число геделевских номеров
Класс примитивно рекурсивных функций ___ вычислимых функций
Количество типов команд машины Тьюринга равно ___ (ответ укажите цифрой)
Команда машины Тьюринга состоит из ___ элементарных действий (ответ укажите цифрой)
Любая неразрешимая алгоритмическая проблема дает пример множества
Марковский алгоритм носит также название ___ алгоритма
Математиками, показавшими возможность существования универсальной вычислительной машины, способной выполнить любую эффективную процедуру, являются
Математиком, предложившим идею использования рекурсии для решения задач, связанных с основаниями математики, является
Множество номеров самоприменимой машины Тьюринга
Множество, если его характеристический предикат является вычислимым, называется
Множество, если оно является множеством значений некоторой вычислимой функции, называется
Не сохраняет примитивную рекурсивность оператор
П.р.ф. S2 (х) = х + 2 вычисляется по формуле
Пусть R обозначает свойство рекурсивности, а Р – рекурсивной перечислимости. Тогда
Свойства, которыми может обладать не рекурсивное множество:
Символы, которые машина Тьюринга читает и пишет на ленте, образуют
Символы, которые определяют внутреннее состояние машин Тьюринга, образуют
Теорема – «Множество тогда и только тогда разрешимо, когда оно само и его дополнение рекурсивно перечислимы», называется теоремой
Теория алгоритмов является частью
Укажите соответствие между понятиями теории алгоритмов и их содержанием:
Укажите соответствие между понятиями, характеризующими машину Тьюринга, и их содержанием:
Укажите соответствие между характеристиками сложности алгоритмов и их содержанием:
Усеченная разность чисел 5 и 8 (5÷8) равна ___ (ответ укажите цифрой)
Установите соответствие между п.р.ф. и ее геделевским номером:
Утверждение, что всякая вычислимая функция является вычислимой по Тьюрингу, называется тезисом ___ (укажите фамилию в родительном падеже)
Формализованный язык для однозначной записи алгоритмов называется ___ языком
Функция 0(х) имеет геделевский номер, равный ___ (ответ укажите цифрой)
Функция S(х) имеет геделевский номер, равный ___ (ответ укажите цифрой)
Функция e11 имеет геделевский номер, равный ___ (ответ укажите цифрой)
Функция e31(x, y, z) + e32(x, y, z) равна
Функция e33 имеет геделевский номер, равный ___ (ответ укажите цифрами)
Функция называется частично рекурсивной, если она либо принадлежит к числу исходных п.р.ф., либо может быть получена из них с помощью операторов
Функция х+у: 1); 2); 3) обладает следующими свойствами:
Функция является примитивно рекурсивной, если она получается из набора исходных п.р.ф. с помощью операторов
Функция, вычислимая по Тьюрингу, является
Функция, вычисляемая некоторой машиной Тьюринга, называется
Функция, определяемая как число шагов в вычислении машиной Тьюринга, называется
Функция, полученная из вычислимой функции с помощью оператора рекурсии, является
Частично вычислимая функция может быть продолжена до
Челночный алгоритм является модификацией ___ алгоритма
Число компонент машины Тьюринга равно ___ (ответ укажите цифрой)
Формальные системы
Аксиоматический подход относится к такому методу доказательства, при котором осуществляется движение мысли от
Базовая единица языка, обладающая определенной для данного языка синтаксической и смысловой законченностью и выражающая утверждение, называется
В любой рекурсивно аксиоматизированной формальной системе множество доказуемых утверждений
В системе арифметики натуральных чисел Пеано единственным неопределимым отношением является
В язык первого порядка входят множества
Выражение «множество А содержится в множестве В» записывается как
Даны два числовых множества А={1,2,3,4,5} и B={2,5,9}. Установите соответствие между типом операции над данными множествами и ее результатом:
Законченная последовательность знаков определенной длины, воспринимаемая как элемент обработки с определенным семантическим содержанием, называется
Знаком принадлежности элемента некоторому множеству является символ
Конечному автомату соответствует грамматика, порождающая
Математический термин, используемый для обозначения какой–либо связи между предметами или понятиями, называется
Множество A есть подмножество множества В в том и только в том случае, если каждый элемент множества А является
Множество аксиом вместе с явным определением доказательства составляют
Множество всевозможных осмысленных утверждений языка является
Множество всех истинных утверждений языка L является
Множество доказуемых утверждений формальной системы арифметики
Множество истинных утверждений
Множество натуральных чисел обладает свойствами
Множество простых чисел обладает свойствами
Объединение множеств А и В обозначается как
Объединение произвольного количества вполне определенных, отличных друг от друга объектов, природа и свойства которых могут быть какими угодно, называется
Осмысленные конечные последовательности символов из алфавита L называются
Пересечение множеств А и В обозначается как
Понятие полноты формальной системы состоит в том, что для любого утверждения s в рамках данной системы одно из утверждений ¬s и s
Разность между множествами А и В обозначается
Свойство формальной аксиоматической теории, когда в ее рамках невозможно доказать две противоречащие друг другу теоремы, называется
Система аксиом Пеано содержит ___ аксиом (ответ дайте цифрой)
Совокупность исходных знаков, принятых за неделимые, и правил построения из них слов и словосочетаний без всякой связи с их возможной семантикой называется ___ языком
Способ видения объектов формальных систем как конкретных объектов при условии, что содержательные объекты сохраняют структуру формальных, называется ___ системы
Способ обозначения определенного понятия, предмета, свойства, используемый для присвоения, хранения, обработки и передачи информации, называется
Существуют следующие классы фраз:
Теорема о том, что не существует формальной системы арифметики, удовлетворяющей условиям полноты и непротиворечивости, носит имя ___ (укажите фамилию)
Укажите соответствие между понятиями логики и их содержанием:
Укажите соответствие между понятиями теории множеств и их содержанием:
Укажите соответствие между понятиями теории формальных грамматик и их содержанием:
Укажите соответствие между понятиями, характеризующими теорию формальных систем и их содержанием:
Установление соответствия между элементарными высказываниями формальной теории и содержательными высказываниями некоторой предметной области называется
Формальная грамматика, позволяющая построить любую правильную цепочку символов, называется ___ грамматикой
Язык, на котором описывается другой язык, называется
Язык, предложения (формулы) которого выражают суждения и отношения исследуемой математической теории, называется