2. Алгебра логики

1. Двойственность формул булевой алгебры. Из свойств, приведенных в (1.5.5), видно, что в булевой алгебре, как и в алгебре множеств, имеет место принцип двойственности. Взаимно двойственными операциями являются дизъюнкция и конъюнкция. Заменяя в некоторой формуле каждую операцию на двойственную ей, получаем двойственную формулу. Например, из формулы x(y ∨ z(u ∨ v)) имеем x ∨ y(z ∨ uv).

На основе законов де Моргана выводится следующее положение:

если φ(x₁, x₂, ..., x_n) и φ*(x₁, x₂, ..., x_n) - двойственные формулы, то φ̅*(x₁, x₂, ..., x_n) равносильна φ(x̅₁, x̅₂, ..., x̅_n). Отсюда следует, что

φ*(x₁, x₂, ..., x_n) = φ̅(x̅₁, x̅₂, ..., x̅_n)

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

Если формулы φ₁(x₁, x₂, ..., x_n) и φ₂(x₁, x₂, ..., x_n) равносильны, то и двойственные им формулы φ*₁(x₁, x₂, ..., x_n) и φ*₂(x₁, x₂, ..., x_n) также равносильны.

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

Функция приводится к нормальной форме следующим путем: 1) с помощью законов де Моргана формула преобразуется к такому виду, чтобы знаки отрицания относились только к отдельным переменным; 2) на основе первого (второго) дистрибутивного закона формула сводится к дизъюнкции конъюнкций (конъюнкции дизъюнкций); 3) полученное выражение упрощается и соответствии с тождествами xx = x и xx̅ = 0 (x ∨ x = x и x ∨ x̅ = 1).

- 514 -

Пример: (xy ∨ y̅z)¬(xu)=(xy ∨ y̅z)(x ∨ u̅) = (xy ∨ y̅z)x ∨ (xy ∨ y̅z)u̅ = xyx ∨ y̅zx ∨ xyu̅ ∨ y̅zu̅ = xy ∨ xyu̅ ∨ y̅zu̅

(дизъюнктивная нормальная форма); (xy ∨ y̅z)¬(xu)=(xy ∨ y̅z)(x ∨ u̅) = (x ∨ y̅z)(y ∨ y̅z)(x ∨ u̅) = (x ∨ y̅)(x ∨ z)(y ∨ y̅)(y ∨ z) x ∨ u̅) = (x ∨ y̅)(x ∨ z)(x ∨ u̅) (конъюнктивная нормальная форма).

Члены дизъюнктивной (конъюнктивной) нормальной формы, представляющие собой элементарные конъюнкции (дизъюнкции) k букв, называют минитермами (макстермами) k-го ранга. Так, в приведенных выше формах ху - минитерм второго ранга, хуг - минитерм третьего ранга, а - макстерм второго ранга.

Если исходная формула содержит другие операции, то они предварительно выражаются через дизъюнкцию, конъюнкцию и отрицание, например:

¬(x → (x̅~z))(y → z̅) ∨ ¬(x → z) = ¬(x̅ ∨ ( ∨ z)(x̅ ∨ z̅))(y̅ ∨ z̅) ∨ ¬(x̅ ∨ z) = x¬((x ∨ z)(x̅ ∨ z̅))(y̅ ∨ z̅) ∨ xz̅ = x(x̅z̅ ∨ xz)(y̅ ∨ z̅) ∨ xz̅ =(xx̅z̅ ∨ xxz)(y̅ ∨ z̅) ∨ xz̅ =xz(y̅ ∨ z̅) ∨ xz̅=xzy̅ ∨ xzz̅ ∨ xz̅ = xyz̅ ∨ xz̅.

3. Совершенные нормальные формы. Если в каждом члене нормальной формы представлены все переменные (либо в прямом, либо в инверсном виде), то она называется совершенной нормальной формой.

Можно показать, что любая булева функция, не являющаяся тождественным нулем (единицей), имеет одну и только одну совершенную дизъюнктивную (конъюнктивную) нормальную форму. Если какой-либо член j дизъюнктивной (конъюнктивной) нормальной формы не содержит переменной х, то она вводится тождественным преобразованием φ = φ(x_i ∨ x̅_i) = φx_i ∨ φx̅_i (соответственно φ = φ ∨ x_ix̅_i =(φ ∨ x_i)(φ ∨ x̅_i)). В силу тождеств φ ∨ φ = φ и φφ = φ одинаковые члены, если они появляются, заменяются одним таким членом.

Продолжая второй пример, приведем данную функцию к совершенной дизъюнктивной нормальной форме: xy̅z ∨ xz̅ = xy̅z ∨ xz̅(y ∨ y̅) = xy̅z ∨ xy̅z̅.

Приведение к совершенной конъюнктивной нормальной форме иллюстрируется следующим примером:

¬(x ∨ yz̅)(x ∨ z)=x̅¬(yz̅)(x ∨ z)=x̅(y̅ ∨ z)(x ∨ z)=(x̅ ∨ yy̅)(y̅ ∨ z ∨ xx̅)(x ∨ z ∨ yy̅) =

=(x̅ ∨ y)(x̅ ∨ y̅)(y̅ ∨ z ∨ x)(y̅ ∨ z ∨ x̅)(x ∨ z ∨ y)(x ∨ z ∨ y̅)=

= (x̅ ∨ yzz̅)(x̅ ∨ y̅ ∨ zz̅)(x ∨ y̅ ∨ z)(x̅ ∨ y̅ ∨ z)(x ∨ y ∨ z)(x ∨ y̅ ∨ z)=

=(x̅ ∨ y ∨ z)(x̅ ∨ y ∨ z̅)(x̅ ∨ y̅ ∨ z)(x̅ ∨ y̅ ∨ z̅)(x ∨ y̅ ∨ z)(x̅ ∨ y̅ ∨ z)(x ∨ y ∨ z)(x ∨ y̅ ∨ z)=

=(x̅ ∨ yCz)(x̅ ∨ y ∨ z̅)(x̅ ∨ y̅ ∨ z̅)(x̅ ∨ y̅ ∨ z)(x ∨ y̅ ∨ z)(x ∨ y ∨ z).

- 515 -

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

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

При большом количестве переменных такой способ практически неосуществим из-за огромного числа возможных наборов значений переменных. Более удобный путь - приведение формулы к нормальной форме. Если в процессе такого приведения формула не обращается в тождественный 0 или 1, то это свидетельствует о ее выполнимости.

5. Конституенты и представление функции. Для совокупности переменных x₁, x₂, .., x_n выражение x̃₁x̃₂... x̃_n называют конституентой единицы, а выражение x̃₁ ∨ x̃₂ ∨... ∨ x̃_n - конституентой нуля (x̃_i означает либо x_i, либо x̅_i). Данная конституента единицы (нуля) обращается в единицу (нуль) только при одном соответствующем ей наборе значений переменных, который получается, если все переменные принять равными единице (нулю), а их отрицания - нулю (единице). Например, конституенте единицы x₁x̅₂x₃x₄ соответствует набор (1011), а конституенте нуля x̅₁∨x₂∨x₃∨x̅₄- набор (1001).

Так как совершенная дизъюнктивная (конъюнктивная) нормальная форма является дизъюнкцией (конъюнкцией) конституент единицы (нуля), то можно утверждать, что представляемая ею булева функция f(x₁, x₂, ..., x_n) обращается в единицу (нуль) только при наборах значений переменных x₁, x₂, .., x_n, соответствующих этим конституентам. На остальных наборах эта функция обращается в нуль (единицу).

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

Например функции, заданной таблицей

- 516 -

соответствуют совершенные нормальные формы:

y = x̅₁x̅₂x₃ ∨ x̅₁x₂x̅₃ ∨ x₁x̅₂x̅₃ =

= (x₁ ∨ x₂ ∨ x₃) (x₁ ∨ x̅₂ ∨ x̅₃) (x̅₁ ∨ x₂ ∨ x̅₃) (x̅₁ ∨ x̅₂ ∨ x₃)

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

6. Алгебра Жегалкина. Другая замечательная алгебра булевых функций строится на основе операций сложения по модулю 2 и конъюнкции. Она называется алгеброй Жегалкина по имени предложившего ее советского ученого. Непосредственной проверкой по таблицам соответствия устанавливаются следующие основные свойства этой алгебры:

- коммутативность х + у = у +х; ху = ух;

- ассоциативность х + (у + z) = (х + у) + z; х(уz) = (ху)z;

- дистрибутивность умножения относительно сложения х(у + z ) = ху + хz;

- свойства констант x·1=x; x·0=0; x+0=x

Все эти свойства подобны обычной алгебре, но в отличие от булевой алгебры закон дистрибутивности сложения относительно умножения не имеет силы (xy + z ≠ xz +yz). Справедливы также следующие тождества:

- закон приведения подобных членов при сложении х + х =0;

- закон идемпотентности для умножения хх = х.

Таким образом, в формулах алгебры Жегалкина, как и в булевой алгебре, не могут появляться коэффициенты при переменных и показатели степени. С помощью табл. 6 выводятся также следующие соотношения:

x̅ = 1 + x; x₁ ∨ x₂ = x₁ + x₂ +x₁x₂; x₁ + x₂ = x₁x̅₂∨x̅₁x₂

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

x(x̅ ∨ y)= x[(1+x)+y+(1+x)y] = x(1+x+y+y+xy) =

= x(1+x+xy)= x+xx+xxy=x+x+xy=xy;

1+x+y+xy=(1+x)(1+y)=x̅ y̅.

Через операции алгебры Жегалкина можно выразить все другие булевы функции:

x₁→x₂=x̅₁∨x₂=1+x₁+x₁x₂;

x₁~x₂=(x̅₁∨x₂)(x₁∨x̅₂)=1+x₁+x₂;

x₁ ← x₂=x₁→x₂=x₁+x₁x₂;

x₁/x₂=¬(x₁x₂)=1+x₁x₂;

x₁ ↓ x₂=¬(x₁∨x₂)=1+x₁+x₂+x₁x₂.

- 517 -

7. Канонические многочлены. Любая булева функция приводится к каноническому многочлену, члены которого не содержит числовых коэффициентов и линейны относительно любой из переменных (переменные входят только в первой степени).

Действительно, если привести данную функцию к совершенной нормальной форме и заменить все дизъюнкции через суммы по модулю 2, а отрицание переменных представить в соответствии с тождеством x̅ = 1 + x, то после раскрытия скобок получим некоторое алгебраическое выражение. Оно приводится к каноническому многочлену на основе соотношений х + х = 0 и хх = х. Такое представление всегда возможно и единственно (с точностью до порядка расположения членов).

Пример.

(1 + х + у) (1 + ху) + (х + ху) у = 1 + х + у + ху + хху + уху + ху + хуу =

= 1 + х + у + ху + ху + ху + ху + + ху = 1 + х + у + ху.

Проблема разрешимости в алгебре Жегалкина сводится к указанным преобразованиям, в процессе которых делается вывод о выполнимости той или иной формулы.

Пример.

х(х→ у) → у = х (1 + х + ху) → у = ху → у = 1 + ху + хуу =1 + ху + ху = 1

Так как эта формула является тождественной единицей, то она невыполнима.

Преимущество алгебры Жегалкина состоит в арифметизации логики, что позволяет выполнять преобразования булевых функций, используя опыт преобразования обычных алгебраических выражений. Ее недостаток по сравнению с булевой алгеброй - сложность формул, что особенно сказывается при значительном числе переменных, например:

х ∨ у ∨ z = х + у + z + ху + хz + уz + хуz.

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

8. Типы булевых функций. В алгебре логики из множества v = 2²ⁿ различных булевых функций n переменных у= f(x₁, x₂, ..., x_n ) выделяются следующие пять типов булевых функций.

1) Функции, сохраняющие константу 0, т. е. такие f(x₁, x₂, ..., x_n), что f(0,0,…,0) = 0. Так как на одном из 2ⁿ наборов (x₁, x₂, ..., x_n ) значения таких функций фиксированы, то их число равно 2^2n-1 = 1/2 2²ⁿ = 1/2 v, т. е. половина всех функций n переменных сохраняет константу 0.

2) Функции, сохраняющие константу 1, т. е. такие f(x₁, x₂, ..., x_n ), что f(1,1,…,1) = 1. Их число, как и в предыдущем случае, равно половине общего числа всех функций n переменных.

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

- 518 -

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

4) Линейные функции, т. е. такие, которые представляются в алгебре Жегалкина каноническим многочленом, не содержащим произведений переменных: a₀ + a₁x₁ + a₂x₂ + ... + a_nx_n , где коэффициенты a₁, a₂, ..., a_n принимают значения 0 или 1. Так как всего коэффициентов n+1, то число различных линейных многочленов будет 2ⁿ⁺¹ . В силу однозначности представления функции каноническим многочленом это число выражает и количество линейных функций.

5) Монотонные функции, т.е. такие, которые для любых двух наборов из множества значений переменных, частично упорядоченного соотношением (α₁, α₂, ..., α_n) ≤ (β₁, β₂, ..., β_n) при α_i ≤ β_i (i = 1, 2, ..., n), удовлетворяют неравенству f (α₁, α₂, ..., α_n) ≤ f (β₁, β₂, ..., β_n).

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

9. Функциональная полнота. Система функций, суперпозицией которых может быть представлена любая функция из некоторого множества булевых функций, называется функционально полной. Если в такой системе допускаются константы 0 и 1, то ее называют ослабленно функционально полной. Говорят, что функционально полная система функций образует базис в логическом пространстве. Система функций называется минимально полным базисом, если удаление из нее любой функции превращает эту систему в неполную.

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

- 519 -

С помощью табл. 6 можно следующим образом охарактеризовать свойства булевых функций с позиций функциональной полноты (звездочкой отмечены свойства, которыми обладает данная функция:

Отсюда видно, что рассмотренные в (9.4) системы операций (дизъюнкция и отрицание, конъюнкция и отрицание, штрих Шеффера, стрелка Пирса) удовлетворяют теореме о функциональной полноте. Система операций алгебры Жегалкина (сумма по модулю 2 и конъюнкция) вместе с константой 1 образует ослабленно функционально полную систему.

Выбрав любую элементарную функцию и дополнив ее одной или несколькими другими функциями так, чтобы все они вместе удовлетворяли теореме о функциональной полноте, можно выразить через них все другие булевы функции. Например, в основу одного из таких комплектов можно положить импликацию и константу 0. Тогда x₁ ∨ x₂ = (x₁ → x₂) → x₂ и x̅ = x → 0, а через дизъюнкцию и отрицание выразятся и все остальные функции. В качестве другого функционально полного комплекта можно взять конъюнкцию, эквиваленцию и константу 0. При этом x̅ = x~0 и формулы алгебры логики, построенной на этих операциях, будут двойственны формулам алгебры Жегалкина, если в качестве двойственных символов принять + и ~, а также 1 и 0.

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

- 520 -

10. Булевы алгебры. Алгебра, основные свойства которой приведены в (1.5.4) и (1.5.5), является лишь частным и простейшим случаем широкого класса так называемых булевых алгебр. Обычно при определении булевой алгебры одну из операций (дизъюнкцию) называют сложением, а другую (конъюнкцию) — умножением и наделяют их свойствами, аналогичными уже рассмотренным свойствам.

Сравнив свойства булевой алгебры и алгебры множеств (2.1.1), легко убедиться, что алгебра множество также является булевой алгеброй относительно операции объединения ∪ и пересечения ∩. Роль единицы и нуля играют соответственно исходное множество (универсум) U и пустое множество ∅, а операции отрицания соответствует дополнение до исходного множества. В то же время алгебра Жегалкина (6) не относится к классу булевых алгебр, так как одна из ее операций (сложение по модулю 2) не является дистрибутивной относительно другой операции (конъюнкции).

Приведем еще один пример булевой алгебры на ограниченном множестве М действительных чисел, содержащем верхнюю p и нижнюю q грани. Операции сложение и умножения (дизъюнкции и конъюнкции) можно определить как x ∨ y = max(x,y) и xy = min(x,y). Роль 1 и 0 играют соответственно p и q. Отрицание x определяется числом, симметричным числу x относительно центра множества 1/2(p+q), т.е. предполагается, что множество М симметрично относительно своего центра (сам центр может и не входить в состав множества). Эта алгебра включает и двоичную алгебру как частный случай, когда множество М состоит только из двух чисел 0 и 1, причем p = 1 и q = 0 (центр 1/2 не входит в М).