Продолжение таблицы

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

φ₁(х₁, х₂) - конъюнкция (логическое умножение, операция И), обозначается:

х₁ & х₂, х₁ · х₂ (часто х₁ х₂), х₁ Λ х₂;

φ₇(х₁, х₂) - дизъюнкция (логическое сложение, операция ИЛИ), обозначается:

х₁ ٧ х₂, иногда х₁ + х₂ и т.п.

Логические функции трех и более переменных обычно за­даются (наряду с таблицами истинности) также формулами бинарных операций. Например, выражение f (х₁, х₂, х₃) = (х₁ ٧ х₂) → (х₁ & х₃) означает, что функция трех переменных f задана формулой, состоящей из символов этих перемен­ных х₁, х₂, х₃, над которыми выполняются одна унарная операция отрицания и три бинарные операции: дизъюнкция (٧), импликация (→) и конъюнкция (&).

Наиболее употребляемыми являются операции:, ٧, &, →, ~, mod2, |, ↓. Значение любой логической формулы, со­держащей знаки этих операций, можно вычислить для лю­бого набора значений переменных, используя табл. 3.1 и 3.2.

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

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

Стандартный метод установления эквива­лентности двух формул:

1) по каждой формуле восстанавливается таблица истин­ности;

2) полученные таблицы сравниваются по каждому набо­ру значений переменных, (стандартный метод требует 2 • 2ⁿ вычислений).