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

Операция эквиваленции соответствует построению "тогда и только тогда" и обозначается символом "ó" или "≡". Эквиваленция определяется как сложное высказывание вида . Построим таблицу соответствия (табл.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. При помощи таблиц соответствия проверьте, какие из следующих выражений являются верными тождествами:

а) ;

б) ;

в) ;

г) .