Алгебра логики

АЛГЕБРА ЛОГИКИ

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

Создателем алгебры логики является живший в Х I Х веке английский математик Джордж Буль, в честь которого эта алгебра названа булевой алгеброй высказываний .

Логическое высказывание тАФ это любое повествовательное п p едлoжение , в oтнoшении кoтopoгo можно oднoзначнo сказать, истинно oнo или лoжнo .

Употребляемые в обычной речи слова и словосочетания "нетАЭ, тАЬитАЭ, тАЬилитАЭ, тАЬесли.. , тотАЭ, тАЬтогда и только тогдатАЭ и другие позволяют из уже заданных высказываний строить новые высказывания. Такие слова и словосочетания называются логическими связками .

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

Существуют три основные логические операции: отрицани я( о перация, выражаемая словом тАЬ не тАЭ ), дизъюнкции(о перация, выражаемая связкой тАЬ или тАЭ) и конъюнкции(о перация, выражаемая связкой тАЬ и тАЭ ).

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

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

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

Существуют и другие логические операции.

Операция, выражаемая связками тАЬ если .., то тАЭ, тАЬ из .. следует тАЭ, тАЬ .. влечет .. тАЭ, называется импликацией (лат. implico тАФ тесно связаны) и обозначается знаком Во . Высказывание А Во В ложно тогда и только тогда, когда А истинно, а В тАФ ложно.

Операция, выражаемая связками тАЬ тогда и только тогда тАЭ, " необходимо и достаточно тАЭ, тАЬ.. равносильно ..тАЭ, называется эквиваленцией или двойной импликацией и обозначается знаком Вл или ~ . Высказывание А Вл В истинно тогда и только тогда, когда значения А и В совпадают.

Импликацию можно выразить через дизъюнкцию и отрицание :

А Во В = v В.

Эквиваленцию можно выразить через отрицание , дизъюнкцию и конъюнкцию :

А Вл В = ( v В) тАв ( v А) . П орядок выполнения логических операций задается круглыми скобками. Но для уменьшения числа скобок договорились считать, что сначала выполняется операция отрицания (тАЬнетАЭ), затем конъюнкция (тАЬитАЭ), после конъюнкции тАФ дизъюнкция (тАЬилитАЭ) и в последнюю очередь тАФ импликация.

Вместе с этим смотрят:

Алгоритм
Алгоритм Кнута - Морриса - Пратта
Алгоритм. Свойства алгоритма
Алгоритмы сортировки