Математическая логика и теория алгоритмов

131

Глоссарий

Аксиома – основное положение рассматриваемой теории, принимаемое без доказательств.

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

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

Алгоритм – это общий, единообразный, точно установленный способ решения любой задачи из данной массовой проблемы.

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

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

Дизъюнктивная нормальная форма (ДНФ) – форма записи алгебры вы-

сказываний, представленная в виде дизъюнкции элементарных конъюнкций. Дизъюнкция двух высказываний А и В – высказывание А B , ложное в

том и только в том случае, когда оба высказывания А и В ложны.

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

Квантор – это общее название для логических операций, ограничивающих область истинности какого-либо предиката.

Конъюнктивная нормальная форма (КНФ) – форма записи алгебры вы-

сказываний, представленная в виде конъюнкции элементарных дизъюнкций. Конъюнкция двух высказываний А и В – высказывание А B , истинное

тогда и только тогда, когда истинны оба высказывания А и В.

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

Логическая переменная – это переменная, обозначающая любое высказывание, которая может принимать логические значения «истина» или «ложь».

Математическая логика – естественнонаучная дисциплина, изучающая математические доказательства и вопросы оснований математики.

132

Область истинности предиката P(x) , заданного на множестве M – совокупность всех x из M, при которых данный предикат обращается в истинное высказывание.

Отрицание (инверсия) высказывания А – высказывание А , истинное тогда и только тогда, когда А ложно.

Предметная область (область определения) предиката – это множество M, на котором определен предикат.

Предметная переменная – это элементы множества M, на котором определен предикат.

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

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

Совершенная ДНФ (СДНФ) – ДНФ, в которой нет одинаковых элементарных конъюнкций и все конъюнкции состоят из одного и того же набора переменных, в который каждая переменная входит только один раз (возможно с отрицанием).

Совершенная КНФ (СКНФ) – КНФ, в которой нет одинаковых элементарных дизъюнкций и все дизъюнкции состоят из одного и того же набора переменных, в который каждая переменная входит только один раз (возможно с отрицанием).

Тождественно истинные формулы (тавтологии) – формулы, принима-

ющие значение «истина» на всех наборах логических переменных.

Тождественно ложные формулы (противоречия) – формулы, принима-

ющие значение «ложь» на всех наборах логических переменных.

Эквиваленция двух высказываний А и В – высказывание А B , истинное тогда и только тогда, когда истинностные значения А и В одинаковы.

Элементарное высказывание – высказывание, представляющее собой одно утверждение.

Элементарная дизъюнкция (ЭД) – дизъюнкция k логических переменных или их отрицаний k 1 .

Элементарная конъюнкция (ЭК) – конъюнкция k логических переменных или их отрицаний k 1 .