Закон де Моргана

Закон двойного отрицания

Закон идемпотентности

Свойства операций И, ИЛИ и НЕ.

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

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

устанавливает, что дважды выполненное отрицание эквивалентно пустой операции.

4. Закон коммутативности (переместительный)

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

5. Закон поглощения.

6. Закон свёртки

описывает эффект отрицания переменных, связанных операциями И и ИЛИ.

8. З акон ассоциативности (сочетательный)

переменные можно группировать в любом порядке как для операции И, так и для операции ИЛИ.

9. Закон дистрибутивности ( распределительный)

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

10. Следует отметить свойство симметрии, присущее законам булевой алгебры. Все законы представлены парой соотношений. В каждой паре одно соотношение получается из другого заменой всех операций И на ИЛИ, всех операций ИЛИ на И, всех вхождений логического 0 на логические 1 и всех вхождений логической 1 на логические 0. Это свойство симметрии известно как принцип двойственности.

Многие законы можно обобщить на случай большого числа переменных. Например, закон де Моргана в обобщенной форме можно записать так:

и

а закон дистрибутивности:

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

Рассмотрим специальное преобразование формул, которое называется минимизацией формул алгебры высказываний.

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

Рассмотрим один из способов минимизации. Минимизацию произвольной формулы осуществим следующим образом:

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

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

Например:

(2.3)

(2.4)

(2.5)

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

Примеры минимизации формул, содержащих простые высказывания.

Проиллюстрируем процесс упрощения сложных высказываний на следующих примерах.

Пример 1. Выражение

можно упростить следующим образом:

Пример 2. Выражение

упрощается следующим образом:

Пример 3. Выражение

упрощается следующим образом:

Пример 4. Чтобы выполнить отрицание выражения

будем действовать следующим образом:

Дата добавления: 2014-10-17