Эквиваленция (двойная импликация)

Операция эквиваленции соответствует построению "тогда и только тогда" и обозначается символом "ó" или "≡". Эквиваленция определяется как сложное высказывание вида . Построим таблицу соответствия (табл.3.5) при помощи таблиц для импликаций и .

 

Таблица 3.5
х 1	х 2

 

Исходя из таблицы соответствия, эквиваленцию (х ₁ó x ₂) можно также определить как высказывание, которое истинно тогда и только тогда, когда высказывания x ₁ и х ₂ либо оба истинны, либо оба ложны.

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

Вопросы и задания

3.14. Составьте сложное высказывание с использованием операции эквиваленции из следующих простых высказываний: "Сумма квадратов двух сторон треугольника равна квадрату третьей стороны", "Треугольник прямоугольный". Проверьте результат по таблице соответствия.

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

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

 

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

Возникает вопрос: как доказать, что выражение действительно является тождеством? Есть два пути:

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

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

 

Всего существует 16 операций с двумя логическими (булевыми) переменными (табл.3.6).

Очевидно, что одни операции могут быть выражены через другие. Например, дизъюнкция может быть выражена через конъюнкцию и отрицание:

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

 

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

 

Таблица 3.6
x 1					Варианты обозначения	Названия	Чтение
x 2
y 0						Константа 0 (тождественный нуль, всегда ложно)	Любое 0
y 1						Конъюнкция (логическое "и", произведение, пересечение, совпадение)	x 1 и x 2 (и x 1 и x 2)
y 2						Отрицание импликации (совпадение с запретом, антисовпадение, запрет)	x 1, но не x 2
y 3						Повторение (утверждение, доминация) первого аргумента	Как x 1
y 4						Отрицание обратной импликации (обратное антисовпадение)	Не x 1, но x 2
y 5						Повторение (утверждение, доминация) второго аргумента	Как x 2
y 6						Сумма по модулю 2 (неравнознач-ность, антиэквивалентность, исключающее "или")	x 1 не как x 2 (или x 1 или x 2)
y 7						Дизъюнкция (разделение, логическая сумма, сборка, логическое "или")	x 1 или x 2 (x 1 или хотя бы x 2)
y 8						Стрелка Пирса (функция Вебба, отрицание дизъюнкции, логическое "не–или")	Ни x 1, ни x 2
y 9						Эквиваленция (равнозначность, эквивалентность, взаимозависимость)	x 1 как x 2 (x 1, если и только если x 2)
y 10						Отрицание (инверсия) второго аргумента (дополнение к первой переменной)	Не x 2
y 11						Обратная импликация (обратное разделение с запретом, обратная селекция)	Если x 2, то x 1 (x 1 или не x 2)
y 12						Отрицание (инверсия) первого аргумента (дополнение ко второй переменной)	Не x 1
y 13						Импликация (разделение с запретом, следование, селекция)	Если x 1, то x 2 (не x 2 или x 1)
y 14						Штрих Шеффера (отрицание конъюнкции, несовместность, логическое "не–и")	Не x 2 или не x 1
y 15						Константа 1 (тождественная единица, всегда истинно)	Любое 1

Вопросы и задания

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

а) ;

б) ;

в) ;

г) .

 

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

Математический аппарат булевой алгебры нашел широкое применение при проектировании технических устройств различной природы – электрических, механических, пневматических, электромагнитных, электронных, гидравлических и многих других.

В качестве примера рассмотрим электрическую схему, состоящую из источника напряжения (батареи), лампочки и одного или двух ключей (х ₁ и х ₂). Ключи управляются кнопками с двумя состояниями: 1 (кнопка нажата) и 0 (кнопка отпущена). Если в исходном состоянии ключ разомкнут, то при нажатии кнопки он замыкается (такой ключ – нормально разомкнутый). Ключ может быть сконструирован и так, что в исходном состоянии он замкнут (нормально замкнутый ключ), тогда нажатие кнопки означает его размыкание, т.е. приводит к противоположному результату. Поэтому нормально замкнутые ключи обозначим через и .

При соответствующих состояниях кнопок лампочка принимает одно из двух состояний: горит (1) и не горит (0). Состояния кнопок отождествляются со значениями булевых переменных х ₁ и х ₂, а состояние лампочки – со значениями функции f (x ₁, х ₂) этих переменных.

 

 

Операции отрицания соответствует переключательная схема с одним нормально замкнутым ключом (рис.4.1). Если кнопка нажата (х =1), ключ размокнут и лампочка не горит, т.е. f (x)=0; при отпущенной кнопке (х =0) ключ замкнут и лампочка горит, т.е. f (x)=1.

Операциям дизъюнкции и конъюнкции соответствуют схемы с двумя нормально разомкнутыми ключами (рис.4.2, 4.3). Легко убедиться, что в схеме на рис.4.2 лампочка горит при нажатии хотя бы одной из кнопок, а в схеме на рис.4.3 – только при нажатии обеих кнопок одновременно.

Любую булеву функцию, даже самую сложную, можно представить переключательной схемой.

 

На рис.4.4 показана схема, реализующая функцию . Та же функция представляется равносильной формулой , которой соответствует более простая схема (рис.4.5). Следует иметь ввиду, что ключи, обозначенные одинаковыми буквами (например, х ₁ и ), связаны между собой и управляются общей кнопкой, так как они описываются одной и той же переменной.

Вопросы и задания

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

а) ;

б) .

 

5. Тождественные преобразования

Как видно на рис.4.4 и рис.4.5, одна и та же булева функция может быть реализована различными переключательными схемами и описана разными формулами. Далее рассмотрим правила тождественного преобразования булевых функций.

На основании таблиц соответствия нетрудно убедиться в справедливости следующих тождеств (свойств) булевой алгебры:

1) коммутативность:

;

2) ассоциативность:

;

 

3) дистрибутивность:

;

4) свойство констант:

;

5) свойство отрицания:

.

Рассмотрим для примера доказательство первого из законов дистрибутивности с помощью таблицы соответствия. Для этого построим таблицы соответствия для левой и правой частей предполагаемого тождества (см.табл.5.1).

Таблица 5.1
х	у	z

 

Как видно из табл.5.1, значения левой и правой части (выделены жирным шрифтом) совпадают при всех значениях переменных, что и требовалось доказать.

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

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

1) законы де Моргана:

;

2) законы поглощения:

;

3) законы идемпотентности:

.

Докажем справедливость первого из законов де Моргана. Для этого равенство путем последовательных преобразований сведем к очевидному тождеству.

Из равенства и свойств отрицания следует, что

т.е.

После раскрытия скобок получим следующее:

Так как и , а и , то предыдущее выражение можно представить в следующем виде:

Используя свойства констант (, , , ), получаем

– очевидное тождество.

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

 

Второй закон де Моргана может быть легко получен на основе первого путем отрицания левой и правой части и соответствующей замены переменных. Запишем первый закон де Моргана относительно переменных a и b:

.

Если равны сами выражения, то равны и их отрицания:

.

Из свойств двойного отрицания:

.

Произведем замену переменных:

После замены получим:

,

т.е. второй из законов де Моргана.

 

Также имеют место следующие тождества:

; ;

и т.д.

Вопросы и задания

5.1. Докажите с помощью таблицы соответствия справедливость законов ассоциативности и поглощения.

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

а) ;

б) ;

в) .

Сравните полученные результаты с результатами задания 3.15.