Эквивалентность формул и тождества

Таблица 9

x	y	Ø х	Ø у

Рассмотрим формулы: и . Их таблицы истинности представлены таблице 12.

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

Две формулы А и В называются эквивалентными, если функции f_A и f_B, соответствующие им, эквивалентны или равны, т.е. f_A = f_B. Для обозначения эквивалентных формул традиционно используется запись А = В, которую называют тождеством.

Следующие тождества характеризуют важнейшие свойства элементарных функций: {0, 1, Ø, &, Ú}. (Обозначим «∘» любую из функций: {&, Ú, Å}.)

((x ∘ y)∘ z)=(x ∘(y ∘ z)) – свойство ассоциативности;

(x ∘ y)=(y ∘ х) – коммутативность;

конъюнкция и дизъюнкция дистрибутивны друг относительно друга: ((x Ú y) & z) = ((x & z) Ú (y & z))
((x & y) Ú z) = ((x Ú z) & (y Ú z));

– закон двойного отрицания;

– законы Де Моргана для конъюнкции и дизъюнкции;

(х & х) = x; (x Ú x) = x – законы идемпотентности;

– закон исключенного третьего;

– закон противоречия;

(х & 0) = 0, (x Ú 0) = x – умножение на ноль и сложение с нулем;

(х & 1) = х, (x Ú 1) = 1 – умножение на единицу и сложение с единицей;

((х & y) Ú x) = x, ((х Ú y) & x) = x – законы поглощения.

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

Упрощение формул

Введем некоторые соглашения о записи и вычислениях формул.

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

По закону ассоциативности для операции «∘» вместо формулы ((x ∘ y) ∘ z) или (x ∘(y ∘ z)) можно использовать выражение без скобок: x ∘ y ∘ z. Для восстановления формулы достаточно расставить скобки, порядок которых не является существенным для вычислений.

Введем также соглашения о старшинстве операций: если в выражении с помощью скобок специально не указан порядок выполнения операций, то одинаковые по старшинству операции выполняются последовательно слева направо. Если в выражении имеются различные операции, то сначала выполняется отрицание, затем конъюнкция, дизъюнкция, импликация и т.д., самой последней выполняется эквиваленция. Скобки восстанавливаются по тому же правилу, например, в выражении х ÚØ у ® z º t скобки восстанавливаются в следующем порядке:

х Ú(Ø у)® z º t

(х Ú(Ø у))® z º t

((х Ú(Ø у))® z)º t

(((х Ú(Ø у))® z)º t)

Ввиду введенного старшинства операций не всякая формула может быть записана без скобок. Например, в выражениях х ®(у ® z) или х &(y Ú z) дальнейшее исключение скобок невозможно, т.к. это может повлиять на значение, вычисленное по формуле.

В дальнейшем для компактности будем использовать следующую запись вместо х ₁& x ₂&…& x_s, а также вместо х ₁Ú x ₂Ú…Ú x_s.

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

а) если один из сомножителей логического произведения равен нулю, то значение произведения также равно нулю;

б) если логическое произведение содержит не менее двух сомножителей, один из которых равен единице, то этот сомножитель можно сократить;

в) если логическая сумма содержит не менее двух слагаемых, одно из которых принимает значение ноль, то его можно сократить;

г) если хотя бы одно из слагаемых логической суммы принимает значение единица, то и вся логическая сумма равна единице;

д) пусть U¹ – подформула формулы U; если в формуле U заменить любые вхождения подформулы U¹ эквивалентной ей формулой В¹, то в результате будет получена формула В, эквивалентная исходной формуле U.

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

Рассмотрим эквивалентные преобразования формулы: ¹= ²= ³= ⁴= ⁵=

Тождество 1 записано по правилу сокращения единичного сомножителя, тождество 2 – по правилу замены подформулы эквивалентной формулой, а именно: здесь для замены использовался закон исключенного третьего. В тождестве 3 применяется закон дистрибутивности. Тождество 4 получено по закону коммутативности. И, наконец, тождество 5 записано по закону поглощения, причем для наглядности «поглощающие элементы» подчеркнуты одинарной и двойной чертой.

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