Соотношения алгебры логики

Эквивалентность формул. Основные эквивалентные

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

Определение.Формулы и называются эквивалентными или равносильными (обозначается , ), если они представляют одну и ту же функцию.

Пример 2.2.3 - Построим таблицы истинности для формул и .

Т а б л и ц а 2.2.3

x	y

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

.

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

Другим методом являются эквивалентные преобразования формул, которые используют эквивалентные соотношения (законы) и правила подстановки и замены.

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

а) (правило подстановки): если в исходном эквивалентном соотношении

все вхождения переменной х одновременно заменены формулой , то получим новое эквивалентное соотношение;

б) (правило замены): если какая-либо формула , описывающая функцию

, содержит подформулу , то замена на ( ) не изменит функции .

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

Т а б л и ц а 2.2.4

	Коммутативность
	Ассоциативность
	Дистрибутивность
	Идемпотентность
	Закон поглощения
	Закон де Моргана
	Закон двойного отрицания
	Свойство констант
	- закон противоречия	- закон исключённого третьего

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

Т а б л и ц а 2.2.5

	Закон склеивания
10 а	Закон расщепления
	Обобщённое склеивание

Определение.Формула называется выполнимой (опровержимой), если существует такой набор значений переменных, при котором формула принимает значение 1 (0).

Пример 2.2.4 - Формула = является одновременно и выполнимой, и опровержимой, т.к. и .

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

Пример 2.2.5 - Формула тождественно истинна, т.к. =1 для всех х; формула тождественно ложна, т.к. =0 для всех х.

Т а б л и ц а 2.2.6

Заметим, что, так как формула может представлять какое-то логическое высказывание или рассуждение, то это рассуждение будет логически правильным, если представляющая его формула тождественно истинна.

Дата добавления: 2014-12-27