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

В частности, если

f

имеет ДНФ

U = K1 … Kl , то NKi N f ,

(i =1,…,l ). Таким образом, весь

интервал

NK

i

располагается внутри множества

N f

и

N f = NK NK

2

… NK

l

, т. е. интервалы,

N f .

1

соответствующие ДНФ,

покрывают

множество

Верно и обратное утверждение: всякому

покрытию множества N f

интервалами, расположенными внутри множества N f , соответствует ДНФ

функции

f .

Пример 5

Рассмотрим две ДНФ таблично заданной функции в примере 1

x1x2 x3 x1x2 x3 x1x2 x3 x1x2 x3 x1x2 x3 и

x1 x2 x3 .

Этим двум ДНФ соответствуют два покрытия:

N f

= = NK

NK

2

NK

3

NK

4

NK

5

и N f

= NK′

NK′ , где

NK ={(000)}, NK

2

={(100)},

1

1

2

1

NK

3

={(101)},

NK

4

={(110)}

,

NK

5

={(111)},

NK′ ={(100), (101), (110), (111)},

NK′ =

1

2

=

{(

000

, 100

)}

. Первое покрытие состоит из пяти интервалов ранга 3, второе − из интервала ранга 1 и

) (

интервала ранга 2.

l

обозначим ri

Для некоторого покрытия множества интервалами

N f = NKi

− ранг интервала

i=1

для

данного

множества

N f

такое

покрытие

интервалами,

принадлежащи-

получается

некоторая ДНФ

D1 . Если проведено k ≥1

этапов, то на (k +1)-м этапе операции

неполного

склеивания и

поглощения применяются

к конъюнкциям ранга n −k для

х3х4 00

01

11

10

х1х2

00

1

1

1

01

1

1

11

1

1

1

10

1

Рис. 2.2. Пример построения карты Карно

дизъюнкцию Dα = K1 K2 …Ks ,

где Ki i =(1,…, s) − все такие простые импликанты f , что

K

i

(α)=1 . Положим

K ( f )= & D

. Раскрывая

скобки с помощью закона дистрибутивности и

α

α

применяя эквивалентности A A = A и A A B = A , получим из КНФ K ( f ) ДНФ M ( f ), слагаемые

которой соответствуют тупиковым ДНФ функции

f .

Пример 8

Рассмотрим

f

=(x1 x2 x3 ) (x1 x2 x3 ).

Сокращенная

ДНФ

функции

f :

x1x2 x1x3 x1x2 x2 x3 x1x3 x2 x3 . Составим таблицу Квайна.

Простые

Единичный набор

импликанты

(001)

(010)

(100)

(011)

(101)

(110)

K1 = x1x2

0

0

1

0

1

0

K2 = x1x3

0

0

1

0

0

1

K3 = x1x2

0

1

0

1

0

0

K4 = x2 x3

0

1

0

0

0

1

K5 = x1x3

1

0

0

1

0

0

K6 = x2 x3

1

0

0

0

1

0

Тогда

K(f )=(K5 K6 ) (K3 K4 ) (K1 K2 ) (K3 K5 ) (K1 K5 ) (K2 K4 )и

M(f )= K1K4K5 K2K3K6 K1K2K3K5 K1K3K4K6 K2K4K5K6.

Функция

f

имеет пять тупиковых

ДНФ. Из них две ДНФ x1x2 x2 x3 x1x3 и x1x3 x1x3 x2 x3 ,

соответствующие слагаемым K1K4K5 и

K2K3K6 , являются минимальными.

6. Полнота системы логических функций

Любая

логическая

функция

может быть выражена в виде формулы

через

функции

системы

{&, , −}. Существуют ли другие системы функций, обладающие таким свойством?

Система

логических функций {f1,…,

fs ,…} называется

функционально

полной,

если любая

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

Теорема 1

U ={f1, f2 ,…},

{g1, g2 ,…}. Пусть система U полна и

Пусть даны две системы функций из P2

B =

каждая

ее

функция

может

быть

выражена

в

виде

формулы

через

функции

систе-

мы B . Тогда система B является полной.

Опираясь на эту теорему, можно установить полноту следующих систем:

1. Система

{&, −}

является

полной.

Для

доказательства

возьмем

U ={&, ,−} и B ={&, −}.

Функция

x1 x2 выражается

через

функции

системы

B

с

помощью

закона

де

Моргана

x1 x2 =

x1 & x2

.

2. Аналогично можно показать, что система { , −}является полной.

3. Система {}| является полной, так как x1 = x1 | x1 и x1 x2 =

= (x1 | x2 ) | (x1 | x2 ) .

x1 | x2

4. Система {0,1,&, } является полной, так как x = x 1 и x1x2 = x1 & x2 .

Формула, построенная из констант 0,1 и функций

x1x2

и

x1 x2 ,

после раскрытия скобок и

несложных

преобразований

переходит

в

полином

по

mod 2 ,

т. е. выражение вида

P = ∑ ai …i

xi

…xi , где сложение производится по mod 2 , т. е. ;

ai …i

принимают значения 0 или

…

1

s

1

s

1

s

Пример 1

1.

Пусть M = P2 . Очевидно [M]= P2 .

2.

M = {1, x1 x2}. Замыканием этого множества будет класс

L всех линейных функций вида

f (x1,…, xn )= = c0 c1x1 … cn xn , где ci {0,1}, i = 0,…, n .

Свойства замыкания:

1) [M] M ;

2) [[M]]=[M];

3) если M1 M2 , то [M1] [M2 ] ;

4) [M1 M2 ] [M2 ] [M2 ] .

Класс (множество) M называется замкнутым, если [M]= M .

С помощью понятия замыкания

можно сформулировать другое определение полноты. Система M полна, если [M]= P2 . Приведем

важнейшие замкнутые классы в алгебре логики.

1.

T0 − класс всех логических функций, сохраняющих константу 0 ., т. е. f (0,…,0) = 0 . К таким

3.

S −

класс

самодвойственных

функций,

т. е. функций

f P

таких,

что

f * = f .

Самодвойственными функциями являются x , x , x1x2 x1x3 x2 x3 .

2

4.

M − класс монотонных функций.

Для двух

наборов α =(α1,…,αn )

и

β =(β1,…,βn ) выполнено

отношение

α ≤β,

если

αi ≤βi

(i =1,…, n). Это отношение есть частичный порядок на множестве наборов длины n.

Функция

f (x1,…, xn ) называется монотонной,

если для любых

α , β таких, что

α ≤β, имеет

место неравенство

f (α)≤ f (β).

Примеры монотонных функций: 0, 1, x1 & x2 , x1 x2 .

Функция,

имеющая

вид

5.

L −

класс

всех

линейных

функций.

f (x1,…, xn )= c0 c1x1 … cn xn , где

ci {0,1}

( i = 0,…, n ), называется линейной.

Линейными

являются функции 0,1, x , x ,

x1 x2 . Функции x1 & x2 , x1 x2 линейными не являются.

Пусть

A ={f1,…,

fs ,…}

−

произвольная

система

функций

содержалась ни в одном из пяти замкнутых классов T0 , T1, S ,

M ,

L .

Следствие 1. Всякий замкнутый класс

M функций из

P2

такой, что M ≠ P2 ,

содержится по

крайней мере в одном из классов T0 , T1, S ,

M , L .

Класс N функций из P2 называется предполным, если N неполный, а для любой функции

f P2

и f N класс {f } N полный.

Следствие 2. В алгебре логики существуют только пять предполных классов T0 , T1,

S , M ,

L .