Основные свойства булевых операций

Приведем основные свойства булевых операций: дизъюнкции, конъюнкции и сложения по модулю 2. Для этого обозначим эти операции одним символом «».

Ассоциативность: ( ) = ( ). (4.1)

Коммутативность: = . (4.2)

Дистрибутивность конъюнкции относительно дизъюнкции:

Ù( Ú ) = ( Ù ) Ú ( Ù ). (4.3)

Дистрибутивность дизъюнкции относительно конъюнкции:

Ú( Ù ) = ( Ú )Ù( Ú ). (4.4)

Идемпотентность: х Ù х=х, х Ú х=х. (4.5)

Двойное отрицание: = . (4.6)

Свойства констант: Ù 1= ; Ù 0=0; Ú 1=1;

Ú 0 = ; =1; = 0. (4.7)

Правила де Моргана: = Ú ; = Ù . (4.8)

Закон противоречия: Ù =0. (4.9)

Высказывание не может быть истинным и ложным одновременно.

Закон исключенного третьего: Ú =1. (4.10)

Всякое высказывание либо истинно, либо ложно.

Доказательство всех утверждений получается сравнением таблиц истинности левой и правой частей равенств (4.1) - (4.10).

Правило подстановки: если в равносильных формулах вместо всех вхождений некоторой переменной подставить одну формулу, то получатся равносильные формулы.

Согласно правилу подстановки равенства (4.1) - (4.10) остаются справедливыми при подстановке вместо переменных любых логических формул.

Пример 4.1. Возьмём первое соотношение (4.8) и подставим вместо : получим = Ú = Ú Ú .

Правило замены: если в формуле заменить некоторую подформулу на равносильную, то получится равносильная формула.

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

Поглощение: а) Ú у = ; б) ( Ú у) = .

Докажем а): Ú у = Ù 1Ú у = (1Ú у) = Ù1 = . Левая часть эквивалентности б) после раскрытия скобок совпадает с левой частью а).

Склеивание: у Ú = .

Действительно, у Ú = (у Ú ) = Ù1 = .

Обобщенное склеивание: z Ú у Ú у = z Ú у .

Доказательство: z Ú у Ú у = z Ú у Ú у z Ú у = z Ú у с использованием поглощения.

Докажем, что Ú = Ú у (4.11)

Действительно: Ú = у Ú Ú = у Ú Ú у Ú = Ú у.

Пример 4.2. Упростить формулу: . Используем правило исключения импликации . Получаем:

.