Основы алгебры логики

Основы работы с такими функциями были заложены английским математиком 19 века Джорджем Булем. В честь него функции, аргументы и значения которых определены на множестве {0,1}, называются булевыми функциями. Другое название этих функций – логические функции. Их изучает соответствующая математическая дисциплина, называемая алгеброй логики (булевой алгеброй, алгеброй высказываний).

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

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

Для обозначения истины (истинного высказывания) используется символ 1, а для обозначения лжи (ложного высказывания) используется символ 0.

Рассмотрим примеры логических высказываний (см. таблицу 1):

Таблица 1. Примеры логических выражений

Предложение	Характеристика с точки зрения алгебры логики
Астана – столица Казахстана	Истинное логическое высказывание
За зимой наступит весна	Истинное логическое высказывание
В городе Иваново проживают только граждане России	Ложное логическое высказывание
После дождя всегда тепло	Ложное логическое высказывание
После вторника будет выходной	Не является логическим высказыванием, т.к. не известно, о каком человеке, каком месяце и дне идет речь (если у человека текущий график работы, возможно, что у него в среду будет выходной, в противном случае среда – рабочий день; если в среду будет праздничный день, например, 8 марта, то этот день также будет выходным)

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

Для обозначения логических высказываний, им назначают имена. Например, если А – высказывание «В четверг был дождь», В – высказывание «В пятницу было солнечно», то составное высказывание «В четверг был дождь, а в пятницу было солнечно», можно записать в виде:

А и В.

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

Каждая логическая связка рассматривается как операция над логическими высказываниями и имеет свое название и обозначение (таблица 2).

Таблица 2. Логические связки

№	Логичес-кая связка	Название	Обозна-чение	Высказывание	Математическая запись
	не	инверсия, логическое отрицание	, , Not	не А	А, , Not A
	и	конъюнкция логическое умножение	Ù, & *, And	A и В	A Ù B, A & B A * B, A And B
	или	дизъюнкция логическое сложение	Ú +, Or	A или В	A Ú B A + B, A Or B
	Если…то	импликация, логическое следование	→, Þ	Если A, то В	A → B A Þ B
	тогда и только тогда	эквивалентность, равносильность, логическое тождество	«, º Û, ~	А тогда и только тогда, когда В	А«В, АºВ АÛВ, А~В

1. Логическое отрицание (инверсия)

В обыденной речи мы часто пользуемся словом "НЕ", или словами "НЕВЕРНО, ЧТО", когда хотим что-то отрицать. Пусть, например, кто-то сказал: "Тоска зеленая." (Обозначим это высказывание А). Если Вы не согласны, Вы скажете:" Тоска НЕ зеленая." Или:" Неверно, что тоска зеленая." (Ваше высказывание обозначим В). Нетрудно заметить, что значения истинности высказываний А и В находятся в определенной связи: если А истинно, то В ложно, и наоборот. Операция, с помощью которой из высказывания А получается высказывание В, называется логическим отрицанием, и само высказывание В называется отрицанием высказывания А и обозначается А.

Таким образом, отрицанием А некоторого высказывания А называется такое высказывание, которое истинно, когда А ложно, и ложно, когда А истинно. Отрицание высказывания А обозначим А.

2. Логическое умножение (конъюнкция) от латинского conjunctio - союз, связь.

Если два высказывания соединены союзом "И", то полученное сложное высказывание обычно считается истинным тогда и только тогда, когда истинны оба составляющие его высказывания. Если хотя бы одно из составляющих высказываний ложно, то и полученное из них с помощью союза "И" сложное высказывание также считается ложным. Например, возьмем два высказывания: "У кота есть хвост" (А), "У зайца есть хвост" (В). Сложное высказывание "У кота есть хвост и у зайца есть хвост" истинно, т.к. истинны оба высказывания А и В. Но если взять другие высказывания: "У кота длинный хвост" (С), "У зайца длинный хвост" (D), то сложное высказывание "У кота длинный хвост и у зайца длинный хвост" будет ложным, т.к. ложно высказывание (D). Таким образом, исходя из обычного смысла союза "И", приходим к определению соответствующей логической операции - конъюнкции.

Таким образом, конъюнкцией двух высказываний А и В называется такое высказывание, которое истинно тогда и только тогда, когда истинны оба высказывания А и В.

Конъюнкцию высказываний А и В мы обозначим: A & B. Знак & - амперсент - читается как английское "and".Часто встречается обозначение А Λ В. Иногда, для краткости, пишут просто АВ.

Определение конъюнкции двух высказываний естественным образом распространяется на любое конечное число составляющих: конъюнкция А1 & A2 & A3 &...& AN истинна тогда и только тогда, когда истинны все высказывания А1, A2, A3,...AN (а, следовательно, ложна, когда ложно хотя бы одно из этих высказываний).

3. Логическое сложение (дизъюнкция) от латинского disjunctio - разобщение, различие.

Если два высказывания соединены союзом "ИЛИ", то полученное сложное высказывание обычно считается истинным, когда истинно хотя бы одно из составляющих высказываний. Например, возьмем два высказывания: "Мел черный." (А), "Доска черная." (В). Высказывание "Мел черный или доска черная" будет истинным, т.к. одно из исходных высказываний (В) истинно.

Таким образом, дизъюнкцией двух высказываний называется такое новое высказывание, которое истинно тогда и только тогда, когда истинно хотя бы одно из этих высказываний.

Дизъюнкцию высказываний А и В мы обозначим символом А V В и будем читать: А или В.

Определение дизъюнкции двух высказываний естественным образом распространяется на любое конечное число составляющих: дизъюнкция А1 V А2 V А3 V...V АN истинна тогда и только тогда, когда истинно хотя бы одно из высказываний А1, А2, А3,..., АN (а следовательно, ложна, когда ложны все эти высказывания).

4. Логическое следование (импликация) от латинского implico - тесно связываю.

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

Рассмотрим пример из арифметики. Вам должно быть известно, что утверждение "если каждое слагаемое делится на 3, то и сумма делится на 3" истинно, т.е. из высказывания "каждое слагаемое делится на 3" следует высказывание "сумма делится на 3".

Из истины не может следовать ложь, иначе логика теряет смысл. Высказывание "Если А, то В" с логической точки зрения имеет тот же смысл, что и высказывание "неверно, что А истинно и В ложно". Это означает, что функцию импликации можно выразить через дизъюнкцию и отрицание:

A → B = А Ú B

Обычно, когда мы хотим установить ложность высказывания "Если А, то В", мы стараемся показать, что возможен случай, когда А истинно, а В ложно (доказательство "от противного"). Обозначим импликацию символом => и запись "А => В" будем читать: "Из А следует В".

Таким образом, импликацией А => В называется высказывание, которое ложно тогда и только тогда, когда А истинно и В ложно.

5. Логическое тождество (эквивалентность).

Интуитивно можно догадаться, что высказывания эквивалентны (равносильными), когда их значения истинности одинаковы. Например, эквивалентны высказывания: "железо тяжелое" и "пух легкий", так же как и высказывания: "железо легкое" и "пух тяжелый". Обозначим эквиваленцию символом <=> и запись "А <=> В" будем читать "А эквивалентно В", или "А равносильно В", или "А, если и только если В".

Таким образом, эквиваленцией двух высказываний А и В называется такое высказывание, которое истинно тогда и только тогда, когда оба эти высказывания А и В истинны или оба ложны.

Отметим, что высказывание типа "А, если и только если В" можно заменить высказыванием "Если А, то В и, если В, то А". Следовательно, функцию эквиваленции можно выразить через отрицание, дизъюнкцию и конъюнкцию:

A «B = (А Ú B) Ù (B Ú А)

Приведем примеры записи сложных высказываний с помощью обозначения логических связок:

"Быть иль не быть - вот в чем вопрос." (В. Шекспир) А V A <=> В

"Если хочешь быть красивым, поступи в гусары." (К. Прутков) А => В

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

Таблица 3. Таблица истинности

A	B	A Ú B	A Ù B	A

Таблица 4. Приоритет выполнения логических операций

Приоритет операции	Логическая операция
Первый (высший)	Логическое отрицание
Второй	Конъюнкция (логическое умножение)
Третий	Дизъюнкция (логическое сложение)
Четвертый	Импликация (следование)
Пятый (низший)	Эквивалентность (равносильность)