Вопрос: алгоритм сортировки данных.Сортировка подсчётом:

Алгоритм сортировки данных – это алгоритм для упорядочивания элементов в списке.

Этот метод подходит для сортировки целых чисел из не очень большого диапазона (сравнимого с размером массива). Идея вот в чем: для каждого элемента найти, сколько элементов, меньших определенного числа, и поместить это число на соответствующие место. Делается это так: за линейный проход по массиву мы для каждого из возможных значений подсчитываем, сколько элементов имеют такое значение. Потом добавляем к каждому из найденных чисел суму всех предыдущих. Получая, таким образом, сколько есть элементов, значения которых не больше данного значения. Далее, опять-таки за линейный проход, формируем из исходного массива новый отсортированный. При этом следим, чтобы два одинаковых элемента не были записаны в одно место.

Вопрос: связанные и свободные переменные:

Вхождение переменной в формулу называется связанным, если оно находится в области действия квантификации по этой переменной или является вхождением в эту квантификацию. Вхождение переменной в формулу называется свободным, если оно не является связанным. Переменная может иметь в формуле одновременно свободные и связанные вхождения. В формуле переменная x имеет только три связанных вхождения, а переменная y имеет одно свободное вхождение (в предикате ), и два связанных(в квантификаторе и в предикате ).

Вопрос: основные понятия и определения дисциплины:

Математическая логика – это наука о правилах формального логического мышления.

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

Алгоритм – совокупность четко определенных правил для решения задач за конечное число шагов.

Вопрос: сложность алгоритмов:

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

Вопрос: основные понятия МЛиТА:

Математическая логика – это наука о правилах формального логического мышления.

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

Алгоритм – совокупность четко определенных правил для решения задач за конечное число шагов.

Вопрос: пропозициональные формулы и логические функции:

Пропозициональными называются формулы состоящие из пропозициональных переменных.

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

Вопрос: общая значимость:

Общезначимость – явление при котором формула истинна в любой интерпретации. Например, формула (p⋁¬p) общезначима.

Вопрос: кванторы:

Кванторы – группа символов, входящая в алфавит языка логики предикатов. Квантор всеобщности соответствует словосочетанию «для всех», т.е. формула вида интерпретируется как высказывание: Для всех объектов области интерпретации выполняется свойство P. Квантор существования соответствует слову «существует». Например, формула вида интерпретируется как высказывание: Существует пара объектов в области интерпретации, которые находятся в отношении Q.

Вопрос: Равносильность. Логическое следствие:

Пусть Е – множество формул. Формулу С – называют логическим следствием из Е, если при всех интерпретациях, при которых одновременно истинны все формулы из Е, формула С, также истинна. Этот факт записывается следующим образом Е|=С.

Равносильность(логическая эквивалентность). Формулы равносильны, если они имеют одинаковые таблицы истин.

Вопрос: логические функции:

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