Основы логики высказываний

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

Слово логика означает систематический метод рассуждений. Мы познакомимся с одним из разделов этой науки - исчислением высказываний. Исчисление высказываний - совокупность правил, используемых для определения истинности или ложности логических предложений. Логике высказываний можно "научить" вычислительную машину, которая таким образом получает возможность "рассуждать", хотя и на весьма примитивном уровне.

Математик Джордж Буль (1815-1864) описал алгебру, основанную на операторах И, ИЛИ и НЕ и булевых переменных, которые принимают только два значения, например, 0 или 1. Эти значения могут моделироваться наличием или отсутствием тока в электрической цепи, состояниями "Включено" или "Выключено" некоторого переключателя. Далее мы рассмотрим логические предложения, построенные с помощью этих операторов, называемых также логическими связками. Значения таких выражений вычисляются и преобразуются с помощью правил булевой алгебры примерно так же, как числовые выражения преобразуются и упрощаются в обычной арифметике.

Высказывание или предложение - это просто утверждение, которое может быть истинно или ложно. Примерами могут служить следующие ытверждения: "Сидорову 20 лет", "Сидоров - студент". Такие высказывания называются атомарными. Примером составного предложения может служить высказывание "Сидорову 20 лет и он студент", которое содержит два отдельных атомарных предложения (атома), каждое из которых может быть истинно или ложно. Если, например, Сидорову 19 лет, то высказывание "Сидорову 20 лет" ложно. Составные и атомарные предложения называются в логике формулами.

В исчислении высказываний не рассматриваются утверждения, имеющие значения, отличные от "истинно" и "ложно". Используется двузначная логика: ответ, отличный от "Да", есть "Нет". Древние философы назвали этот принцип "законом исключенного третьего". Существуют другие логики, правила которых отличаются от правил исчисления высказываний, например, трехзначная логика со значениями "Да", "Нет", "Не знаю" или так называемая нечеткая логика, где можно оперировать утверждениями типа "С вероятностью 90% величина А больше 3".

В таблице приводятся обозначения, используемые для логических связок в различной литературе. Мы в дальнейшем изложении будем использовать обозначения, принятые в большинстве языков программирования. Истинное значение далее будем обозначать символом T (от True - истина), а ложное - F (от False - ложь).

Связка Название Булева алгебра Логика Программирование

И конъюнкция ^ &&

ИЛИ дизъюнкция + V ||

НЕ отрицание ¬ ¬!

Составные предложения

Для построения составных предложений чаще всего используются связки - И (&&, конъюнкция) и ИЛИ (||, дизъюнкция). Смысл связки И - тот же, что и в разговорной речи: конъюнкция двух предложений истинна тогда и только тогда, когда они оба истинны. Связка ИЛИ "двойственна" связке И: дизъюнкция двух предложений ложна только если они оба ложны.

Дизъюнкция нескольких предложений ложна тогда, когда все они ложны. Рассмотрим, например, утверждение "Плата за подписку снижена для студентов, лиц моложе 21 года и безработных". Согласно ему, приходится платить полную цену, только если все три исключения нарушены. Аналогичное обобщение верно и для связки И. Конъюнкция нескольких предложений истинна, только если все они истинны.

Кроме И и ИЛИ, имеется еще модификатор НЕ (!, отрицание) результат применения которого противоположен его аргументу:!T = F,!F = T. В математической литературе для обозначения отрицания выражения проводят горизонтальную черту над ним.

Значения логических выражений, содержащих связки И, ИЛИ и модификатор НЕ, вычисляются с помощью так называемой таблицы истинности:

A B A && B A || B! A

T T T T F

T F F T F

F T F T T

F F F F T

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

Пример

Вычислить значение логической формулы!X && Y || X && Z

при следующих значениях переменных: X = F, Y = T, Z = T.

Решение

Отметим цифрами порядок выполнения операций:

1 2 4 3

! X && Y || X && Z.

Используя таблицу истинности, вычислим формулу по шагам: 1)!F = T; 2) T && T = T;

3) F && T = F; 4) T || F = T.

Итак, формула при данных значениях аргументов принимает значение T.

Задание

Определите значение логического выражения

!(X>Z) &&!(X=Y), если: 1) X = 3, Y = 5, Z = 2; 2) X = 0, Y = 1, Z = 19;

Законы булевой алгебры

При работе с логическими выражениями часто используют следующие законы. Законы

коммутативности А && В = B && A

A || B = B || A

Законы

ассоциативности A && (B && C) = (A && B) && C

A || (B|| C) = (A || B) || C

Законы

дистрибутивности A && (B || C) = (A && B) || (A && C)

A || (B && C) = (A || B) && (A || C)

Свойства операций

И, ИЛИ A && T = A; A && F = F

A || F = A; A || T = T

Свойства отрицания A &&!A = F; A ||!A = T

Закон коммутативности утверждает, что можно переставлять операнды при использовании конъюнкции или дизъюнкции. Это может показаться очевидным, но имеются операторы вроде арифметического минуса, для которых это неверно: A - B отлично от B - A. Закон ассоциативности позволяет расставлять скобки произвольным образом, если в логическом выражении используется лишь одна из связок && и ||. В таких случаях можно вообще обойтись без скобок, так как закон ассоциативности гарантирует получение одного и того же результата независимо от того, как сгруппированы предложения.

Вместе эти пять законов определяют булеву алгебру. Из них можно получить другие полезные законы, например, такие: Дополнение!(!A) = A

Идемпотентность A && A = A; A || A = A

Поглощение A && (A || B) = A

Приведем очень поучительное доказательство закона поглощения (попробуйте найти его сами прежде, чем ознакомиться с решением).

A && (A || B) =

{ свойство операции ИЛИ }

(A || F) && (A || B) =

{ дистрибутивность }

A || (F && B) =

{ коммутативность }

A || (B && F) =

{ свойство операции И }

A || F =

{ свойство операции ИЛИ }

A

Заметим, что большинство законов существует в двух похожих формах. Принцип двойственности гласит, что любая теорема булевой алгебры остается истинной, если в ее формулировке заменить все связки И на ИЛИ, ИЛИ на И, все T на F и все F на T.

Задания

Упростите выражения:

1)!X ||!(X || Y) ||!(Y &&!(X && Y));

2)!(X || Y ||!(X && Y)) &&!(Y ||X).

Заданы логические функции:

F1 = X && Y || X && Z ||!Y && Z и F2 = (X && Y || Y && Z || X &&!Z) && (X &&!Y ||!Y && Z).

Упростите эти функции и проверьте, являются ли они тождествено равными между собой, т. е. совпадающими для всех возможных значений переменных X, Y и Z.

Дата добавления: 2014-01-20