Подмножество, на котором предикат Р(х) принимает значение "истина", называется характеристическим множеством.

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

Конъюнкция Р(х) и Q(x) - это предикат R(x)=P(x)aQ(x), который истинен для тех и только тех объектов из М, для которых оба предиката Р(х) и Q(x) истинны. Характеристическим множеством предиката R(x) является пересечение Pf] Q-

Подобным образом вводятся и другие логические операции дизъюнкции, импликации и др.

2.6. ЗАКОНЫ И ТОЖДЕСТВА БУЛЕВОЙ АЛГЕБРЫ

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

1. Идемпотентность

2. Коммутативность

3.Ассоциативность

(х а у} a z = х л (у л z)

[х v у) V z = x v (>> v z)

4.Дистрибутивность

xa(az) = (xajv)v(xaz)

x v [у a z) = (х v у) а (х v z)J

5.Универсальность верхней и нижней границы

х а0 = 0, xv 0 = х

x а 1 = x, xv 1 = 1

6.Закон де Моргана

2.7. ДВОЙСТВЕННОСТЬ И РАВНОЗНАЧНОСТЬ ФОРМУЛ БУЛЕВОЙ

АЛГЕБРЫ

В булевой алгебре взаимно двойственными операциями [2] являются дизъюнкция и конъюнкция. Заменяя в некоторой формуле ср (xj,x2, ...,jcJ каждую операцию на двойственную ей, получаем двойственную формулу (р* (xj, х2, х„). Например:

(р = х(у vz(uvv)) ,(2.15)

<р* = xv (yzv (uv)) .(2.16)

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

Формула ср (xh х2, Ху) и формула (р** (хи х2, х„) называются равносильными, если они равны (р=ср** на одинаковых и любых наборах их аргументов xi, х2, хп.

Причем, если две формулы равносильны, то двойственные им формулы также равносильны.

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

2.8. НОРМАЛЬНЫЕ ФОРМЫ

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

(xyz) v(xz) v(yz) .

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

(х vzvy)(z vx)(y vz) .

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

1. С помощью законов де Моргана (2.14) формула преобразуется к такому виду, чтобы знаки отрицания относились только к отдельным переменным.

2.На основе первого или второго дистрибутивного законов (2.12) формула сводится к дизъюнкции конъюнкций или конъюнкции дизъюнкций.

3.Полученное выражение упрощается в соответствии с тождествами идемпотентности (2.9) и универсальности верхней и нижней границ (2.13).

Для примера рассмотрим преобразование формулы

(xyvyz)xa

кДНФ.

С помощью законов де Моргана (2.14) преобразуем конъюнкцию последних двух членов (2.17) к следующему виду:

ха = х v а ,

подставив в (2.17) выражение (2.18), получим

(xyv yz)(xvd) . Раскрыв вторые скобки, найдем

(xyvyz)xv(xyvyz)d ,

преобразуем это выражение еще раз, раскрыв оставшиеся скобки

хху v yxz vaxy vd yz .

Упростив полученное выражение за счет первого его члена, кко-торому применим законы идемпотентности (2.9), запишем:

xyvyxzvdxyvdyz .(2.20)

Полученное выражение является дизъюнктивной нормальной формой - ДНФ.

Выражение (2.17) можно преобразовать также к КНФ, при этом оно предварительно приводится к виду (2.19). Обозначим в первой скобке член yz=b , при этом выражение (2.17) примет вид

xyvb = xAyvb = (xAy)vb .

Применив к этому выражению второй закон дистрибутивности (2.12) получим

(xAy)vb = (xvb)A(yvb) , и сделав обратную подстановку b = yz, запишем :

(xvyz)(yvyz) .

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

(xv yz)(yv yz) = (xv y)(xv z)(yv y)(yv z) ,

подставив это выражение в (2.19) вместо первой скобки, запишем :

(х v у)(х v z)(y v у)(у v z)(x v а) ,

сучетомтого, что у v у =1, окончательно получаем