Свойства конъюнкции, дизъюнкции и инверсии

Конъюнкция переменных x₁ и x₂ равна лог.1 в том случае, когда и x₁ и x₂ равны лог.1 (отсюда возникло название операции логическое И).

Дизъюнкция переменных x₁ и x₂ равна лог.1, если или x₁ или x₂ равна лог.1 (отсюда понятно возникновение названия операции: логическое ИЛИ).

В тех случаях, когда число переменных больше двух, конъюнкция их равна лог.1 при равенстве лог.1 всех переменных; дизъюнкция равняется лог.1, если хотя бы одна из них равна лог.1.

В математике установлен определенный порядок выполнения операций в сложном выражении. Например, в выражении x₁+x₂·х₃ вначале выполняется операция умножения x₂·х₃ и затем операция сложения. Если требуется изменить этот порядок, используются скобки. Например, (x₁+x₂)·х₃. Здесь вначале выполняется операция в скобках.

Подобно этому и для сложного логического выражения установлен определенный порядок выполнения операций: вначале выполняются операции инверсии, затем операции конъюнкции и в последнюю очередь операции дизъюнкции. Например, запись логического выражения x₁Vx₂·x₃Vx₄·x₂ предполагает, что при вычислении выражения вначале выполняются операции инверсии x₃ и x₄, затем операции конъюнкции x₂·x₃ и x₄·x₂ и в последнюю очередь операции дизъюнкции. А если требуется нарушить это правило, используются скобки. Например, (x₁Vx₂) ·(x₃Vx₄). В этом случае вначале выполняются операции в скобках (а если одни скобки вложены в другие, то вначале выполняются операции в самых внутренних скобках).

Операции конъюнкции и дизъюнкции обладают рядом свойств:

сочетательный закон: x₁·(x₂·x₃) = (x₁·x₂)·x₃, x₁V(x₂Vx₃) = (x₁Vx₂)Vx₃;

переместительный закон: x₁·x₂ = x₂·x₁, x₁Vx₂ = x₂Vx₁;

распределительный закон: x₁·(x₂Vx₃) = x₁·x₂ V x₁·x₂, x₁V(x₂·x₃) = (x₁Vx₂)·(x₁Vx₂).

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

Покажем справедливость так называемых формул де Моргана:

= x1 V x2.

(1.2)

В выражении = x₁·x₂ левая часть обращается в 1 только в том случае, если x₁Vx₂ = 0, для чего необходимо x₁=0 и x₂=0. Правая часть выражения обращается в 1 только при x₁=1 и x₂=1, т.е. при x₁=0 и x₂=0. Таким образом, только набор x₁=0 и x₂=0 обращает в 1 и правую и левую части выражения; следовательно, при отсальных наборах значений аргументов правая и левая части выражения будут равны 0, что и доказывает справедливость рассматриваемого равенства.

В выражении = x₁Vx₂ и правая и левая части обращаются в 0 при x₁=1 и x₂=1, при остальных наборах значений аргументов обе части выражения равны 1, что и доказывает справедливость данного равенства.

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