4.2. Булева алгебра
Английский математик Джордж Буль (1815-1864) сформулировал правила для вычисления значений комбинированных логических высказываний и представил их в символьной форме. Основными операциями булевой алгебры являются уже знакомые читателю операции AND, OR и NOT от двоичных переменных, обозначаемых буквами латинского алфавита. Из основных свойств указанных операций, иллюстрируемых табл. 4.1 и 4.2, можно вывести следующие три правила:
Двойное отрицание NOT (NOT P) = Р
Идемпотентность Р AND Р = Р, Р OR Р = Р
Поглощение Р AND (P OR Q) = Р
В табл. 4.3 приведены таблицы истинности, позволяющие проверить правила двойного отрицания и идемпотентности. Построение таблицы для проверки правила поглощения мы предоставляем читателям в качестве упражнения.
Таблица 4.3
Одним из основных принципов булевой алгебры является принцип двойственности, в соответствии с которым для каждого правила этой алгебры существует другое, двойственное ему, получающееся из исходного путем механической замены в нем операций AND на OR, OR на AND, а также констант Т на F и наоборот. Приведенные ниже основные свойства булевой алгебры сгруппированы согласно этому принципу:
Свойство коммутативности Р AND Q = Q AND P, P OR Q = Q OR P Перестановка высказываний, входящих в операции AND и OR, не влияет на результат
Свойство ассоциативности Р AND (Q AND R) = (Р AND Q) AND R
P OR (Q OR R) = (P OR Q) OR R Последовательность выполнения нескольких операций AND или нескольких OR на результат не влияет
Свойство дистрибутивности Р AND (Q OR R) = (Р AND Q)
OR (P AND R)
P OR (Q AND R) = (P OR Q) AND (P OR R) Операция AND дистрибутивна относительно операции OR и наоборот
Свойства операций AND и OR с константами Р AND Т = Р, Р AND F = F Р
OR T = T,P OR F = P
Свойства операции отрицания Р AND NOT P = F, P OR NOT P = Т
|
ПОИСК:
|
При использовании материалов сайта активная ссылка обязательна:
http://informaticslib.ru/ 'Библиотека по информатике'