Элементы математической логики

Принципы поиска и обработки информации в ЭВМ основываются на законах математической логики, поскольку компьютеры — это автоматические устройства, принципы работы которых базируются на элементарных законах двоичной логики.

Вычислительные машины всех поколений состояли и состоят из логических элементов и элементов памяти, принимающих два значения (бита) 0 и 1. Вся обработка информации в ЭВМ всех ее логических блоков, логических схем и устройств опиралась и будет опираться на законы и принципы математической логики.

Логика — это древнейшая наука, изучающая правильность суждений, рассуждений и доказательств. Примеры суждений: «снег белый», «2 х 2 = 5», «Земля круглая», «информатика — лженаука», «Интернет — международная сеть».

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

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

Суждения и в математике, и на практике могут быть истинными или ложными. На практике истинность или ложность суждений проверяется их соответствием действительности, а в математике — опровержениями либо доказательством.

Пример истинного суждения — «снег белый». Пример ложного суждения — «генетика — лженаука». Пример суждений, истинность которых до сих пор до конца еще не установлена: «машина может думать», «на Марсе есть жизнь», «информатика — наука».

Работа ЭВМ как автоматических устройств основана исключительно на однозначных правилах выполнения команд, программ и алгоритмах обработки данных. Тем самым работа компьютеров, а также всех вычислительных устройств, систем и сетей допускает верификацию — строгую однозначную проверку правильности их работы.

Все сложные логические элементы и блоки вычислительных машин и устройств конструируются из простейших логических элементов с помощью логических операций «И» (AND), «ИЛИ» (OR) и «НЕ» (NOT). В математической логике для этих операций обычно используются обозначения — & («И»), V («ИЛИ») и — («НЕ»).

Наглядной иллюстрацией этих логических связок служат следующие диаграммы:

Отрицание не А истинно или ложно в зависимости от истинности исходного суждения А. Свойства отрицания не как логической связки можно описать таблицей истинности:

Таблица истинности:

Свойства отрицаний:

НЕ1: Отрицание ложно, если суждение истинно.

НЕ2: Отрицание истинно, если суждение ложно.

Для понимания роли отрицаний в языках запросов важно уметь выражать их в позитивной форме. Приведем примеры отрицания математических неравенств и их эквивалентные позитивные переформулировки:

не (х = 0) ≡ (х ≠ 0);

не (х ≠ 0) ≡ (х = 0);

не (х > 0) ≡ (х ≤ 0);

не (х < 0) ≡ (х ≥ 0);

не (х ≥ 0) ≡ (х < 0);

не (х ≤ 0) ≡ (х > 0).

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

Закон двойного отрицания:

не (не А) = А.

Отрицание отрицания равносильно исходному утверждению.

Логическая связка и в математической логике называется конъюнкцией. Таблица истинности конъюнкции:

Свойства конъюнкции:

И1: Конъюнкция А и В истинна, когда истинны оба суждения.

И2: Конъюнкция А и В ложна, когда ложно хотя бы одно из суждений А или В.

Логическая связка или в математической логике называется дизъюнкцией. Таблица истинности дизъюнкции:

Свойства дизъюнкции:

ИЛИ1: Дизъюнкция А или В истинна, когда истинно любое из суждений А или В.

ИЛИ2: Дизъюнкция А или В ложна, когда ложны оба суждения А и В.

Для понимания принципов поиска информации по запросам в базах данных и сети Интернет необходимо понимать математический смысл сложносоставных запросов с использованием логических операций «И» (AND), «ИЛИ» (OR) и «НЕ» (NOT).

Примеры сложносоставных запросов к базам данных и их эквивалентные позитивные переформулировки:

(признак ≠ 0) & не (х > 0) ≡ (признак (0)) & (х ≤0);

(число > 0) v не (у > 0) ≡ (число > 0) v (у ≤ 0).

Общие принципы отрицания дизъюнкций и конъюнкций в математической логике выражаются двумя закона де Моргана:

Закон отрицания конъюнкции:

не (А и В) = (не А) или (не В)

— отрицание конъюнкции суждений равносильно дизъюнкции отрицаний.

Закон отрицания дизъюнкции: