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

Логика очень древняя наука. Ещё в античные времена была известна формальная логика, позволяющая делать заключения о правильности какого-либо суждения не по его фактическому содержанию, а только по форме его построения. Например, уже в древности был известен закон исключения третьего. Его содержательная трактовка была такова: «Во время своих странствований Платон был в Египте ИЛИ не был Платон в Египте». В такой форме это или любое другое выражение будут правильны (тогда говорили: истинно). Ничего другого быть не может: Платон либо был, либо не был в Египте - третьего не дано.

Другой закон логики - закон непротиворечивости. Если сказать: «Во время своих странствий Платон был в Египте И не был Платон в Египте», то очевидно, любое высказывание, имеющее такую форму, всегда будет истинным или ложным.

Например: Листва на деревьях опадает осенью. Земля прямоугольная.

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

Пример предложений, не являющихся высказываниями: Не пейте сырую воду! Кто не хочет быть счастливым?

Высказывания могут быть и такими: 2 > 1, Н₂О + SO₃ = H₂SO₄. Здесь используются языки математических символов и химических формул.

Приведённые выше примеры высказываний являются простыми. Но из простых высказываний можно получить сложные, объединив их с помощью логических связок. Логические связки - это слова, которые подразумевают определённые логические связи между высказываниями. Основные логические связки издавна употребляются не только в научном языке, но и в обыденном, - это “и”, “или”, “не”, “если ... то”, “либо ... либо” и другие известные нам из русского языка связки. В рассмотренных нами трёх законах формальной логики использовались связки “и”, “или”, “не”, “если ... то” для связи простых высказываний в сложные.

В 1847 году английский математик Джордж Буль, преподаватель провинциального университета в маленьком городке Корке на юге Англии разработал алгебру логики.

Алгебра логики очень проста, так как каждая переменная может принимать только два значения: истина или ложь.

Логическая константа 1 означает, что какое-то событие истинно, в противоположность этому логический 0 означает, что высказывание не соответствует истине, т. е. ложно. Логическое выражение строится из логических переменных (А, В, Х, …), логических операций и круглых скобок.

В алгебре логики знаки операций обозначают лишь три логические операции ИЛИ, И, НЕ.

1. Логическая операция ИЛИ (V). Логическую функцию принято задавать в виде таблицы. В левой части этой таблицы перечисляются все возможные значения аргументов функции, т. е. входные величины, а в правой указывается соответствующее им значение логической функции. Для элементарных функций получается таблица истинности данной логической операции. Операцию ИЛИ называют также логическим сложением, и потому её можно обозначать знаком «+».

Для операции ИЛИ таблица истинности имеет вид:

Рассмотрим сложное единичное высказывание: «Летом я поеду в деревню или в туристическую поездку». Обозначим через А простое высказывание «Летом я поеду в деревню», а через В - простое высказывание «Летом я поеду в туристическую поездку». Тогда логическое выражение сложного высказывания имеет вид А+В, и оно будет ложным только, если ни одно из простых высказываний не будет истинным.

2. Логическая операция И (&). Таблица истинности для этой функции имеет вид:

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

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

3. Логическая операция НЕ. Эта операция является специфичной для алгебры логики и не имеет аналога в обычной алгебре. Таблица истинности для этой функции имеет вид:

Она обозначается чертой над значением переменной, либо знаком приставки перед значением переменной:

Читается в обоих случаях одинаково «Не А».

В вычислительной технике операцию НЕ называют отрицанием или инверсией, операцию ИЛИ - дизъюнкцией, операцию И - конъюнкцией. Набор логических функций “И”, “ИЛИ”, “НЕ” является функционально полным набором или базисом алгебры логики. С помощью него можно выразить любые другие логические функции, например операции “строгой дизъюнкции”, “импликации” и “эквивалентности” и др. Рассмотрим некоторые из них.

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