Математическая логика и теория алгоритмов. Часть 1

Формулой алгебры логики называется

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

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

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

Разбейте сложное высказывание «если 45 кратно 3, то и 42 кратно 3» на два простых и запишите его с помощью символов алгебры логики.

• a ~ b

Непротиворечивость – это

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

Логический парадокс — это

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

Функция h в рекурсивной формуле для двухместной функции f(x,y)=x2+y, если рекурсия проводится по y, выглядит следующим образом

• h(x,y,z) = z2 + 2x + 1
• h(x,y,z) = z + 1
• h(x,y,z) = x2 + y + 1
• h(x,y,z) = z + 2x + 1

Импликацией высказываний а и b называется высказывание, которое

• ложно, если а истинно, а b – ложно, и истинно во всех остальных случаях
• истинно, если а и b истинны, и ложно, если хотя бы одно из них ложно
• истинно, если а или b ложно, и ложно, если оба истинны
• истинно, если а и b ложны, и ложно, если хотя бы одно из них истинно

Критерий сложности вычислений – это

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

Приведенные ниже данные противоречивы, когда

Алгоритм называется экспоненциально ограниченным, если его сложность

• возрастает экспоненциально с ростом длины обрабатываемой последовательности
• не зависит от длины обрабатываемой последовательности
• возрастает линейно с ростом длины обрабатываемой последовательности
• возрастает полиномиально с ростом длины обрабатываемой последовательности

Нечетким множеством А называется

• предикат Р(х), который принимает значение 0, если х не принадлежит А
• дополнение А до универсального множества
• отображение, которое ставит в соответствие каждому элементу универсального множества степень его принадлежности к А
• предикат Р(х), который принимает значение 1, если х принадлежит А

Геделевский номер функции равен

• 2
• 7
• 3
• 5

Из перечисленных языков программирования к декларативным относятся

• Бейсик
• Лого
• Лисп
• Паскаль

Пусть x, x’, y, y’ означают, соответственно, «7-простое число», «7-составное число», «8-простое число», «8-составное число». Из нижеприведенных выражений истинно

Конечный автомат может быть задан

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

Функциональная программа состоит из

• совокупности дизъюнктов Хорна
• совокупности операторов присваивания
• совокупности определений функций
• совокупности фраз Хорна

Из следующих эквивалентностей истинны

• 2*2=5 тогда и только тогда, когда 2
• 2*2=5 тогда и только тогда, когда 2>3
• 2*2=4 тогда и только тогда, когда 2
• 2*2=4 тогда и только тогда, когда 2>3
• 1 (истина), только когда все входящие в нее элементарные высказывания истинны
• 1 (истина), только когда все входящие в нее элементарные высказывания ложны
• 0 (ложь) при всех значениях входящих в нее элементарных высказываний
• 1 (истина) при всех значениях входящих в нее элементарных высказываний
• из множества натуральных чисел
• 0 или 1
• из множества действительных чисел
• из отрезка [0, 1]
• состоящее из элементов множества А и множества В
• состоящее из элементов множества В без элементов множества А
• состоящее из элементов множества А без элементов множества В
• состоящее из тех элементов множества А, которые также являются элементами множества В
• область значений переменных, для которых предикат принимает значение “истина”
• область возможных значений всех переменных предиката
• область значений переменных, для которых предикат принимает значение “ложь”
• область, распространяемая на возможные значения связанных переменных
• слова из заданного алфавита, имеющие заданную длину
• любое слово из заданного алфавита, длина которых не менее заданной
• любое слово из заданного алфавита
• язык, допускаемый этим автоматом
• h(x,y,z) = z + 3
• h(x,y,z) = z/3
• h(x,y,z) = 3x+y+1
• h(x,y,z) = 3*z
• sin(x+1)
• sin(x) + x +1
• x+1 + sin(x)
• cos(x) + x + 1
• множество значений переменной х, для которых предикат принимает значение “ложь”
• множество всех значений, которые принимает предикат
• множество значений переменной х
• множество значений переменной х, для которых предикат принимает значение “истина”
• мощность множества А равна мощности множества В
• мощность множества В больше, чем множества А
• мощность множества А больше, чем множества В
• эти мощности нельзя сравнивать
• логику предикатов, использующую кванторы
• многозначную логику, позволяющую определить промежуточные значения для таких оценок как «да | нет», «принадлежит | не принадлежит» и т.д.
• логику, изучающую структуру математических высказываний
• логику, используемую в математических рассуждениях
• h(x,y,z) = z + 2x + 1
• h(x,y,z) = z + 1
• h(x,y,z) = x2 +2x + 1 + y
• h(x,y,z) = z + 2y + 1
• f(n+1) = f(n)*2
• f(n+1) = f(n)/2
• f(n+1) = 2/f(n)
• f(n) = f(n+1)*2
• переменные, на которые распространяется действие квантора всеобщности
• переменные, на которые распространяется действие кванторов всеобщности и существования
• переменные, от которых зависит предикат
• переменные, на которые распространяется действие квантора существования
• k=1 и n>0
• k=1 и n=1
• k=1 или n=0
• k=1 или n=1
• множество всех значений, которые принимает предикат
• множество значений переменной х, для которых предикат принимает значение “ложь”
• множество значений аргумента х
• множество значений переменной х, для которых предикат принимает значение “истина”
• состоящее из элементов множества А и множества В
• состоящее из тех элементов множества А, которые также являются элементами множества В
• состоящее из элементов множества В без элементов множества А
• состоящее из элементов множества А без элементов множества В
• 0 (ложь) при всех значений входящих в нее элементарных высказываний
• 1 (истина) при всех значений входящих в нее элементарных высказываний
• 0 (ложь), только когда все входящие в нее элементарные высказывания ложны
• 0 (ложь), только когда все входящие в нее элементарные высказывания истинны
• 5
• 7
• 13
• 11
• может перемещаться только слева направо
• может перемещаться в обе стороны
• может перемещаться только справа налево
• неподвижно закреплена на ленте
• высказывания
• символы некоторого алфавита
• элементы нечеткого множества
• одноместные предикаты
• f(n+1) = f(n)*2
• f(n) = f(n+1)*2
• f(n+1) = f(n) + 2n + 1
• f(n+1) = n2 + 2n + 1
• я не учусь в школе
• я не люблю математику
• я люблю математику
• я учусь в школе
• μA(x) = 2*x
• μA(x) = 1 – x2
• μA(x) = x
• μA(x) = x + 1
• g(y) = y
• g(x) = x2
• g(x,y) = x2 + y + 1
• g(y) = y + 1
• система логического вывода на множестве высказываний
• рассуждения, имеющие цель доказать непротиворечивость исходной системы аксиом
• рассуждения, состоящие в получении из имеющихся знаний нового знания по некоторым точным правилам
• рассуждения, с помощью которых из знаний об отдельных фактах получаются знания об общих закономерностях.
• g(y) = 3y
• g(y) = 3*3y
• g(y,x) = 3x+y
• g(x) = 3x
• x
• x — 1
• x+1
• 1/x2
• неубывающей
• знакопеременной
• периодической
• не возрастающей
• состоящее из тех элементов множества А, которые также являются элементами множества В
• состоящее из тех элементов множества А, которые не являются элементами множества В
• состоящее из элементов множества А и множества В
• состоящее из элементов множества В без элементов множества А
• существуют значения переменной
• не существует таких значений переменной
• для всех значений переменной
• область истинности предиката есть пустое множество

Разбейте сложное высказывание «45 кратно 3 и 42 кратно 3» на два простых и запишите его с помощью символов алгебры логики.

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

• 1 (истина), только когда все входящие в нее элементарные высказывания истинны
• 1 (истина), только когда все входящие в нее элементарные высказывания ложны
• 0 (ложь) при всех значениях входящих в нее элементарных высказываний
• 1 (истина) при всех значениях входящих в нее элементарных высказываний

Функция принадлежности нечеткого множества А, заданная на универсальном множестве U — μA(U), принимает значения

• из множества натуральных чисел
• 0 или 1
• из множества действительных чисел
• из отрезка [0, 1]

Объединением множеств А и В является множество

• состоящее из элементов множества А и множества В
• состоящее из элементов множества В без элементов множества А
• состоящее из элементов множества А без элементов множества В
• состоящее из тех элементов множества А, которые также являются элементами множества В

Областью действия квантора называется

• область значений переменных, для которых предикат принимает значение “истина”
• область возможных значений всех переменных предиката
• область значений переменных, для которых предикат принимает значение “ложь”
• область, распространяемая на возможные значения связанных переменных

Множество цепочек, допускаемых конечным автоматом, – это

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

Функция h в рекурсивной формуле для двухместной функции f(x,y)=3x+y, если рекурсия проводится по y, выглядит следующим образом

• h(x,y,z) = z + 3
• h(x,y,z) = z/3
• h(x,y,z) = 3x+y+1
• h(x,y,z) = 3*z

Суперпозиция функций f(x)=sin(x) и q(x)=x+1 выглядит следующим образом

• sin(x+1)
• sin(x) + x +1
• x+1 + sin(x)
• cos(x) + x + 1

Областью истинности предиката Р(х) называется

• множество значений переменной х, для которых предикат принимает значение “ложь”
• множество всех значений, которые принимает предикат
• множество значений переменной х
• множество значений переменной х, для которых предикат принимает значение “истина”

Пусть множество А имеет мощность континуум, а В есть счетное множество. Тогда можно утверждать, что

• мощность множества А равна мощности множества В
• мощность множества В больше, чем множества А
• мощность множества А больше, чем множества В
• эти мощности нельзя сравнивать

Нечеткую логику можно определить как

• логику предикатов, использующую кванторы
• многозначную логику, позволяющую определить промежуточные значения для таких оценок как «да | нет», «принадлежит | не принадлежит» и т.д.
• логику, изучающую структуру математических высказываний
• логику, используемую в математических рассуждениях

Функция h в рекурсивной формуле для двухместной функции f(x,y)=x2+y, если рекурсия проводится по х, выглядит следующим образом

• h(x,y,z) = z + 2x + 1
• h(x,y,z) = z + 1
• h(x,y,z) = x2 +2x + 1 + y
• h(x,y,z) = z + 2y + 1

Рекуррентная формула для функции f(n) = 2n выглядит следующим образом

• f(n+1) = f(n)*2
• f(n+1) = f(n)/2
• f(n+1) = 2/f(n)
• f(n) = f(n+1)*2

Разбейте сложное высказывание «45 кратно 3 тогда и только тогда, когда 42 кратно 3» на два простых и запишите его с помощью символов алгебры логики.

Связанные переменные – это

• переменные, на которые распространяется действие квантора всеобщности
• переменные, на которые распространяется действие кванторов всеобщности и существования
• переменные, от которых зависит предикат
• переменные, на которые распространяется действие квантора существования

Дизъюнкт называется правилом, если

• k=1 и n>0
• k=1 и n=1
• k=1 или n=0
• k=1 или n=1

Областью определения предиката Р(х) называется

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

Пересечением множеств А и В является множество

• состоящее из элементов множества А и множества В
• состоящее из тех элементов множества А, которые также являются элементами множества В
• состоящее из элементов множества В без элементов множества А
• состоящее из элементов множества А без элементов множества В

Из приведенных ниже формул не является тавтологией

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

• 0 (ложь) при всех значений входящих в нее элементарных высказываний
• 1 (истина) при всех значений входящих в нее элементарных высказываний
• 0 (ложь), только когда все входящие в нее элементарные высказывания ложны
• 0 (ложь), только когда все входящие в нее элементарные высказывания истинны

Геделевский номер функции равен

• 5
• 7
• 13
• 11

Читающая головка конечного автомата

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

Значения лингвистической переменной – это

• высказывания
• символы некоторого алфавита
• элементы нечеткого множества
• одноместные предикаты

Рекуррентная формула для функции f(n) = n2 выглядит следующим образом

• f(n+1) = f(n)*2
• f(n) = f(n+1)*2
• f(n+1) = f(n) + 2n + 1
• f(n+1) = n2 + 2n + 1

Пусть а – высказывание «Я учусь в школе», b – высказывание «Я люблю математику». Словесная формулировка высказывания следующая

• я не учусь в школе
• я не люблю математику
• я люблю математику
• я учусь в школе

Пусть аргумент х меняется от 0 до 1, тогда функция μA(x) может являться функцией принадлежности некоторого нечеткого множества A

• μA(x) = 2*x
• μA(x) = 1 – x2
• μA(x) = x
• μA(x) = x + 1

Функция g в рекурсивной формуле для двухместной функции f(x,y)=x2+y, если рекурсия проводится по x, выглядит следующим образом

• g(y) = y
• g(x) = x2
• g(x,y) = x2 + y + 1
• g(y) = y + 1

Дедуктивные рассуждения – это

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

Функция g в рекурсивной формуле для двухместной функции f(x,y)=3x+y, если рекурсия проводится по х, выглядит следующим образом

• g(y) = 3y
• g(y) = 3*3y
• g(y,x) = 3x+y
• g(x) = 3x

Суперпозиция функций f(x)=1/x и q(x)=x2 выглядит следующим образом

• x
• x — 1
• x+1
• 1/x2

Функция принадлежности для нечеткого множества «высокий рост» является функцией

• неубывающей
• знакопеременной
• периодической
• не возрастающей

Разностью множеств А и В является множество

• состоящее из тех элементов множества А, которые также являются элементами множества В
• состоящее из тех элементов множества А, которые не являются элементами множества В
• состоящее из элементов множества А и множества В
• состоящее из элементов множества В без элементов множества А

Квантор всеобщности, за которым следует переменная, означает

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