Список вопросов базы знаний

Семантика языка - его смысловое содержание:

Часть строки, которую можно свести к нетерминальному символу, - фраза:

В исчислении высказываний общезначимая формула и тавтология - разные понятия

В исчислении высказываний существует четыре вида сентенциональных связок

В классическом исчислении высказываний принимается, что каждый простой формуле сопоставляется один элемент из {T, F}

В математической логике высказывание - любое повествовательное предложение

В сложных формулах без скобок конъюкция выполняется раньше импликации

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

Дизъюнкция двух высказываний истинна тогда и только тогда, когда оба составляющих высказывания истинны

Импликация - сложное предложение, составленное из двух простых, соединенных связкой "тогда и только тогда"

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

Истинностная таблица для сложного высказывания, составленного из N простых содержит N в квадрате строк

Истинностная функция - функция от n-аргументов, причем каждый аргумент может принимать значение Т или F и сама функция должна быть больше нуля

Любая логическая функция может принимать только два значения

Предложение, видоизмененное словом "не", называется отрицанием первоначального предложения

Предложение, образованное соединением двух предложений словом "и", называется конъюкцией этих предложений

Предложение, образованное соединением двух предложений словом "или", - дизъюнкция этих предложений

Число истинностных функций от трех переменных равно 256

Алгебра логики - область традиционной логики, а не математики

Алгебра логики может быть применена в любой области человеческой деятельности

Булевы переменные могут принимать только два значения

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

Другое название операции дизъюнкции - логическое умножение

Другое название операции конъюкции - логическое сложение

Закон ассоциативности в алгебре логики полностью аналогичен закону ассоциативности в обычной алгебре чисел

Законы Де Моргана позволяют менять операцию дизъюнкции на конъюнкцию, и наоборот

Логическая функция от трех аргументов может иметь восемь значений

Логическое отрицание - унарная операция

Любую бинарную логическую операцию можно свести к единственной операции - импликации

Операции булевой алгебры аналогичны обычным операциям алгебры чисел

Операция конъюкции обладает свойством коммуникативности

Принцип работы большинства компьютеров основан на булевой алгебре

Свойство ассоциативности состоит в том, что операнды можно переставлять местами

Существуют всего два основных правила получения новых формул алгебры логики

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

Унарная операция применяется только к одной переменной, константе или формуле

NP-полная задача - такая задача из класса P, к которой можно свести любую другую задачу из класса P

Алгоритмическая сложность - зависимость времени исполнения алгоритма от длины (объема) входных данных

В рамках теории сложности любые алгоритмы, работающие с полиномиальной скоростью, считаются быстрыми

Временем работы алгоритма Tm(x) при фиксированном входном слове x называется длина ленты, которую использует машина Тьюринга (М) при реализации алгоритма

Время при оценке сложности алгоритма измеряется объемом входной информации:

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

Для алгоритма класса O(N) (N - объем входных данных) для каждого данного выполняется только одно действие

Для алгоритмов сложности О(1) количество шагов алгоритма зависит от количества входных данных

Доказано, что классы алгоритмов P и NP совпадают

Задача выполнимости Булевых формул относится к классу NP

Задача нахождения нуля функции методом деления отрезка пополам относится к задачам логарифмической сложности

Задача поиска нужного слова в словаре и задача чистки ковра заданной площади - задачи одного класса сложности

Класс сложности NP - класс сложности алгоритмов, выполняемых детерминированной машиной Тьюринга за полиномиальное время

Регистрация заявок в мастерской бытового обслуживания - пример алгоритма линейного класса сложности