Основы логики высказываний
Так как при организации вычислений часто приходится рассматривать те или иные логические условия, то мы начнем изложение с основ математической логики.
Слово логика означает систематический метод рассуждений. Мы познакомимся с одним из разделов этой науки - исчислением высказываний. Исчисление высказываний - совокупность правил, используемых для определения истинности или ложности логических предложений. Логике высказываний можно "научить" вычислительную машину, которая таким образом получает возможность "рассуждать", хотя и на весьма примитивном уровне.
Математик Джордж Буль (1815-1864) описал алгебру, основанную на операторах И, ИЛИ и НЕ и булевых переменных, которые принимают только два значения, например, 0 или 1. Эти значения могут моделироваться наличием или отсутствием тока в электрической цепи, состояниями "Включено" или "Выключено" некоторого переключателя. Далее мы рассмотрим логические предложения, построенные с помощью этих операторов, называемых также логическими связками. Значения таких выражений вычисляются и преобразуются с помощью правил булевой алгебры примерно так же, как числовые выражения преобразуются и упрощаются в обычной арифметике.
Высказывание или предложение - это просто утверждение, которое может быть истинно или ложно. Примерами могут служить следующие утверждения: "Сидорову 20 лет", "Сидоров - студент". Такие высказывания называются атомарными. Примером составного предложения может служить высказывание "Сидорову 20 лет и он студент", которое содержит два отдельных атомарных предложения (атома), каждое из которых может быть истинно или ложно. Если, например, Сидорову 19 лет, то высказывание "Сидорову 20 лет" ложно. Составные и атомарные предложения называются в логике формулами.
В исчислении высказываний не рассматриваются утверждения, имеющие значения, отличные от "истинно" и "ложно". Используется двузначная логика: ответ, отличный от "Да", есть "Нет".
Древние философы назвали этот принцип "законом исключенного третьего". Существуют другие логики, правила которых отличаются от правил исчисления высказываний, например, трехзначная логика со значениями "Да", "Нет", "Не знаю" или так называемая нечеткая логика, где можно оперировать утверждениями типа "С вероятностью 90% величина А больше 3".
В таблице приводятся обозначения, используемые для логических связок в различной литературе. Мы в дальнейшем изложении будем использовать обозначения, принятые в большинстве языков программирования. Истинное значение далее будем обозначать символом T (от True - истина), а ложное - F (от False - ложь).
| И | конъюнкция | - |  | && |
| ИЛИ | дизъюнкция | + |  | || |
| НЕ | отрицание | ¬ | ¬ | ! |
