Учебное пособие: Дискретная мат-ка_УП, страницы 61-65

61

8.

законы поглощения:

a

∨ a ∧b = а, a ∧ (а ∨ b) = а;

9.

законы Порецкого:

a

∨ a ∧b = а ∨ b, a ∧ (a ∨ b) = а ∧b;

10.

законы, определяющие действия с константами 0 или 1:

a

∨ = а,

a

∧ 0 = 0,

a

∨ 1 = 1,

a

∧ 1 = а,

a

∨ a = 1,

a

∧ a = 0.

Правило подстановки:

если в равносильных формулах

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

Правило замены:

если в формуле заменить некоторую под-

формулу на равносильную, то получится равносильная формула.

6.3

Нормальные

формулы

.

Совершенные

нор

-

мальные

формулы

Обозначим х

о

=

x

, х

1

= х,

⎩

⎨

⎧

=

δ

=

δ

=

δ

.

0

,

x

;

1

,

x

Любую конъюнкцию ранга n можно представить в виде:

Элементарной конъюнкцией

называется конъюнкция пе-

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

Или: элементарной конъюнкцией называется выражение ви-

да

n

2

1

n

2

1

x

...

x

,

x

δ

,

n

2

1

n

2

1

x

...

x

,

x

δ

.

То

есть

элементарная

конъюнкция

есть

логическое

произве

-

дение

переменных

,

взятых

в

некоторой

степени

δ

,

в

которой

ни

одна

переменная

не

употребляется

два

раза

.

Число

переменных

в

конъюнкции

или

дизъюнкции

назовем

ее

рангом.

Дизъюнкция

различных

элементарных

конъюнкций

называ

-

ется

дизъюнктивной нормальной формой (ДНФ).

Конъюнкция

различных

элементарных

дизъюнкций

называ

-

ется

конъюнктивной нормальной формой (КНФ).

Число

конъюнкций

в

ДНФ

называется

длиной

ДНФ

.

62

Если

мы

возьмем

любую

формулу

из

символов

a, b, c,…, x,

y, z,

∧

,

∨

, ¬,

→

, ~,

⊕

, (, ),

то

можно

ее

заменить

равносильной

ДНФ

.

a

→

b =

a

∨

b, a ~ b =

a

b

∨

a b, a

⊕

b = a b

∨

a

b.

Пример

(

а

∧

b )

→

(

с

∨

d) =

( )

b

a

∧

∨

с

∨

d =

a

∨

b

∨

c

∨

d;

ДНФ

весьма

просто

получается

из

таблицы

истинности

.

Достаточно

поставить

в

соответствие

каждому

значению

вектор

аргумента

,

на

котором

функция

принимает

значение

1,

элемен

-

тарную

конъюнкцию

,

называемую

полной

и

состоящую

из

всех

аргументов

.

Такая

ДНФ

,

членами

которой

являются

неповто

-

ряющиеся

полные

элементарные

конъюнкции

,

называется

со-

вершенной ДНФ (СДНФ),

а

ее

члены

констатуэнтами едини-

цы.

С

ДНФ

любой

булевой

функции

единственна

с

точностью

до

порядка

следования

членов

и

литералов

(

чего

нельзя

сказать

о

ДНФ

)

и

является

,

как

говорят

, канонической формой.

Пример

.

Пусть

задана

функция

(a

⊕

b)

→

(c ~ a).

Построим

таблицу

истинности

.

a b c a

⊕

b c ~ a (a

⊕

b)

→

(c ~ a)

0    0        0
0    0        1
0    1        0
0    1        1
1    0        0
1    0        1
0    1        0
1    1        1

0
0
1
1
1
1
0
0

1
0
1
0
0
1
0
1

1
1
1
0
0
1
1
1

Построим

СДНФ

.

КНФ

так

же

удобна

для

представления

нулей

булевой

функ

-

ции

,

как

ДНФ

для

представления

единиц

.

СКНФ

для

предыдущего

примера

запишется

abc

c

ab

c

b

a

c

b

a

c

b

a

c

b

a

∨

)

c

b

a

)(

c

b

a

(

∨

63

Каждая

из

составляющих

ее

полных

элементарных

дизъ

-

юнкций

является

конституэнтой нуля

и

определяет

значение

вектор

аргумента

,

на

котором

функция

обращается

в

нуль

.

6.4

Разложение

Шеннона

.

Декомпозиция

булевых

функций

Рассмотрим

разложение

булевой

функции

f(x

1

, x

2

,…, x

n

)

по

k

переменным

(x

1

,…, x

k

) –

разложение

Шеннона

.

Теорема 1.

Любая

функция

f(x

1

, x

2

,…, x

n

),

не

равная

тожде

-

ственно

нулю

,

представлена

в

виде

разложения

Шеннона

:

.

Заметим

,

что

,

1

x

,...,

x

,

x

k

2

1

k

2

1

=

δ

если

x

i

=

δ

i

,

для

∀

i

= k

,

1

.

Вы

-

берем

набор

δ

1

,

δ

2

,…,

δ

k

и

положим

,

что

x

i

=

δ

i

, i = 1,k.

Тогда

левая

часть

будет

равна

:

f(x

1

, x

2

,…, x

k

, x

k+1

, …, x

n

) = f(

δ

1

,…,

δ

k

, x

k+1

, …, x

n

),

а

правая

:

.

Здесь

k

1

k

1

x

,..,

x

δ

разбиваются

на

единичные

и

нулевые

набо

-

ры

.

Согласно

закону

а

∨

0 =

а

,

получаем

,

что

левая

и

правая

части

формул

равны

при

любой

подстановке

переменных

х

1

,

х

2

,…,

х

k

.

Теорема 2.

Любая

булева

функция

может

быть

представле

-

на

формулой

,

являющейся

суперпозицией

∨

,

∧

, ¬.

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

.

1)

В

начале

докажем

для

f=1

или

f=0.

f(x

1

, x

2

,…, x

n

) = 1 = x

i

∨

x

i

;

f(x

1

, x

2

,…, x

n

) = 0 = x

i

∧

x

i

;

2)

Докажем

для

функции

,

не

равной

константе

,

f(x

1

, x

2

,…, x

n

)

разложим

по

n

переменным

.

Получим

.

)

x

,...,

,

,...,

,

(

x

&

V

)

x

,...,

x

,

x

,...,

x

,

x

(

f

n

1

k

2

1

i

k

1

i

)

,...,

,

(

n

1

k

n

2

1

i

k

2

1

+

δ

=

δ

∀

+

δ

=

)

x

,...,

x

,

,...,

,

(

f

)

x

,...,

x

,

,...,

,

(

f

x

,...,

Vx

n

1

k

2

1

n

1

k

2

1

k

1

k

1

+

δ

=

δ

=

δ

n

1

n

1

n

1

,...,

x

...

Vx

)

...

(

f

x

...

x

V

1

n

1

n

1

64

Это

совершенная

ДНФ

.

Из

этой

формулы

следует

способ

построения

СДНФ

.

Заметим

,

что

f

может

быть

разложена

(

в

булевой

алгебре

справедлив

принцип

двойственности

).

Согласно

закону

двойного

отрицания

(

)

(

)

.

x

...

x

)

,...,

,

(

f

x

...

x

)

,...,

(

f

x

,...,

x

V

)

x

,...,

x

,

x

,...,

x

,

x

(

f

)

x

,...,

x

,

x

(

f

n

2

1

n

1

n

2

1

n

1

n

1

n

1

n

2

1

,..,

n

2

1

n

2

1

,..,

n

1

n

1

,...,

n

1

k

2

1

n

2

1

δ

+

∨

∧

=

δ

∨

∧

=

δ

=

(1)

Таким

образом

,

любая

булева

функция

f(x

1

, x

2

,…, x

n

),

не

равная

тождественно

единице

,

представлена

в

виде

выражения

1.

Покажем

связь

между

разложением

Шеннона

и

таблицами

Вейча

.

Представим

пространство

P

n

(X)

в

виде

декартова

произве

-

дения

пространств

P

k

(X

a

)

и

P

g

(X

b

), X

a

∪

X

b

= X, X

a

∩

X

b

=

∅

,

k + g = n:

P

n

(X) = P

k

(X

a

)

×

P

g

(X

b

).

Каждой

строке

таблицы

Вейча

взаимно

однозначно

сопоста

-

вим

точку

пространства

P

k

(X

a

),

столбцу

–

точку

пространства

P

g

(X

b

)

и

рассмотрим

разложение

Шеннона

булевой

функции

по

первым

k

переменным

.

Тогда

i-

строка

таблицы

Вейча

,

иден

-

тифицируемая

конъюнкцией

k

2

1

a

x

...

x

δ

∧

,

соответствует

остаточной

функции

.

Будем

называть

разложение

Шеннона

булевой

функции

f(X)

строчным

,

если

разложение

осуществляется

по

переменным

,

со

-

ответствующим

строкам

таблицы

Вейча

.

)

,...,

(

f

x

,...,

x

V

)

x

,...,

x

(

f

n

1

n

1

,...,

n

1

n

1

n

1

δ

=

δ

(

)

g

2

1

k

2

1

b

,

a

x

,...,

x

,

x

,...,

x

,

x

f

(

)

g

2

1

k

2

1

b

,

a

x

,...,

x

,

x

,...,

x

,

x

f

65

6.5

Представление

булевой

функции

картами

Карно

(

Вейча

)

Карта

Карно

–

это

диаграмма

,

состоящая

из

правильно

рас

-

положенных

квадратов

,

каждый

из

которых

соответствует

одной

из

2

n

полных

конъюнкций

соответствующих

функции

от

n

пере

-

менных

.

Значения

данной

функции

f

из

таблицы

истинностей

вносят

в

нужные

квадраты

.

Тогда

функция

f

равна

дизъюнкции

всех

полных

конъюнкций

,

для

которых

в

соответствующих

квад

-

ратах

стоит

единица

.

Рассмотрим

построение

карт

Карно

.

Пусть

задана

функция

от

двух

переменных

.

Тогда

карта

Карно

будет

выглядеть

x

1

00 01
x

2

10 11

Чтобы

наборы

не

мешали

внутри

клеток

,

их

можно

вынести

за

пределы

таблицы

x

1

0 1
0
x

2

1

В

карте

Карно

соседние

клетки

различаются

одной

компо

-

нентой

.

Для

кодировки

используется

код

Грея

.

Код

Грея

получа

-

ется

из

обыкновенного

весового

кода

сложением

по

mod 2.

Иско

-

мое

число

вычисляется

следующим

образом

.

Берем

весовой

код

в

качестве

первого

слагаемого

,

в

качестве

второго

слагаемого

бе

-

рем

тот

же

код

,

но

сдвинутый

на

один

разряд

вправо

.

Произво

-

дим

сложение

по

mod 2.

Тогда

карта

Карно

для

трех

переменных

будет

выглядеть

:

Учебное пособие: Дискретная мат-ка_УП

Смотрите также: