Файл: Горелик, А. Л. Некоторые вопросы построения систем распознавания.pdf

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 23.10.2024

Просмотров: 119

Скачиваний: 1

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

Для представления в двоичном коде номера столбца базиса (или, что то же, повернутого столбца), соответствующего той ис­ ходной импликанте, которую мы попытаемся упростить, припишем справа столбец степенных разрядов, отмеченных элементами А, В, С. Пусть 001— представление проверяемой импликанты А - В - С в дво­ ичном коде. Запишем в столбец степенных разрядов число 001 и от­

метим знаком

Д

против 1, что это число соответствует импликанте,

изображающее

число

которой

«покрывает» единицу в 1-м разряде

Ф А

(ф Л-В-С = 0100

0000).

Теперь проверим, имеются ли

среди

номеров единичных разрядов

Ф F оба числа 0X1.

Так как (011) =3

имеется, а (001) = 1

было исходным, то в

столбце

степенных

разря­

дов

записываем

0x1

вместо 001, а против

3 ставим V в знак того,

что изображающее число импликанты. представленной как 0X1, по­ крывает единицу в 3-м разряде Ф А (фЛ • С=0101 0000):

1

2

3

5

С

в

А

А

 

V

 

0

X

1

 

А

 

 

0

1

0

Если бы среди номеров единичных рзарядов

Ф F имелись все четыре

числа

ХХІ , т . е. (111) =7, (011) =3, (101) =5 и (001) = 1, то от числа

0X1

можно было бы перейти

к

числу

XXI. Аналогично, если бы

в исходном наборе чисел (1, 2,

3,

5) имелись четыре числа 0ХХ, т. е.

(000) =0, (001) = 1, (010) =2 и

(011) = 3,

то мы могли бы перейти от

0X1

к 0ХХ. Но так как числа

7 и 0

отсутствуют,

мы переходим

к следующему номеру единичного разряда

ФА т. е. к 2—(010), и

в соответствии с этим против 2 ставим знак

Д а в

столбец степен­

ных разрядов записываем число 010.

 

 

 

Как и раньше, проверим, имеются ли среди номеров единичных

разрядов ф F два числа 01 X : (011) =3

и (010) = 2 . Число 2 является

исходным, а 3 имеется в соседней группе номеров, поэтому перей­ дем от 010 к 01X, а против 3 поставим знак V :

Дальнейшее упрощение 01 X невозможно,

так как числа

111=7

и 000 =

0

отсутствуют. «Непокрытым»

остается только

5-й

разряд

ф А Запишем в столбец степенных разрядов

число 101 и

отметим

знаком

А

число 5. Поскольку число

001 = 1

имеется

в

соседней

группе,

мы переходим от 101 к Х01 и ставим знак V

против 1:

117

1

2

3

5

 

 

 

с

 

в

 

А

 

Первые импликанты

А

 

V

 

 

 

 

0

 

X

 

1

 

 

А-С

 

 

А

V

 

 

 

 

0

 

1

 

X

 

 

в - с

 

 

V

 

 

А

 

 

 

X

 

0

 

1

 

 

А-В

 

 

Так как среди номеров единичных

разрядов

# F

отсутствуют

числа (000) =0 и (111) =7, мы не можем перейти_от х01_ни к

XXI,

ни к ХОХ. Как легко заметить, импликанты В ■С и А •

В покрывают

все единичные разряды

 

 

Следовательно,

процесс построения пер­

вых

импликант

по

#.F= 0111

0100

закончен: Р=А-В+В- С.

 

Ь[А, Вг

 

Рассмотрим

еще один

 

пример

[13].

Пусть

относительно

С, D] задано

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0

1

2

3

4

5

6 7

8

9

10

11

12

13

14

15

# Н (А, В, С, D) = 0 1 0 1 1 1 1 1

0 1 0 1

0

0 1

Г

Разобьем номера единичных разрядов # # на группы по количеству единиц в соответствующих колонках базиса и разместим их в рабо­ чей таблице

 

4

3 5

6

9

7

11 13 14

15 D с

В А

 

 

 

 

 

 

 

 

 

 

8

4

2

і

 

V V

 

V V V V

V X X X

1

Возьмем 1-ю колонку

базиса (отметим это

знаком

Д )

и запишем

в

столбце

степенных

разрядов

число

0001.

Так

как

среди

чисел

во

второй

группе имеется

(0011) = 3,

то 0001 заменяется

на

00X1,

а

против

3 ставится V- Далее

среди

чисел

второй

группы имеется

число (0101) =5,

отличающееся на единицу в степенном разряде 4 (С)

от

первоначального числа

(0001) = 1,

а среди чисел третьей группы

есть число

(0111) =7,

т. е. среди номеров единичных разрядов # Pf

есть все 22 = 4 числа 0ХХІ = 1,

3, 5, 7. Поэтому 00X1

можно

заме­

нить на

OX XI

и поставить против чисел 5 и 7 знак)/-

Далее мы

убедимся в том, что в соответствующих группах рабочей таблицы

имеются числа

(1001) =9,

(1011) = 11,

(1101) = 13 и

(1111) =*15 и, сле­

довательно, все

23 чисел Х Х Х І = 1,

3, 5,

7, 9, 11,

13, 15 содержатся

среди номеров

единичных

разрядов

# Я .

В

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

с

этим

заменим

число OX XI на

Х Х Х І и отметим числа

9, 11, 13,

15 зна­

ком V-

Дальнейшее упрощение проверяемой импликанты невозмож­

но, так

как число 0= (0000) отсутствует в исходном наборе

чисел.

Число Х Х Х І показывает, что одной из первых импликант функ­

ции Н является А и, как

можно заметить из рабочей таблицы,

# Л

не покрывает только 4, 6

и 14-й единичные

разряды # # .

Продол­

жая вычисления, возьмем

в качестве второй

исходной импликанты

118

0100 и в соответствии с этим поставим против числа 4 в первой группе знак Д :

1 4

3 5 6

9 7 11 13

14 15 D

С

Б

А

Первые

 

 

 

8

4

2

1

импликанты

А

V V

V V V V

V X X X 1

А

А

V V

V

0 1

X X

С ■В

 

V

V

А V X 1

1 X

в-с

Поскольку число (1100) = 12 отсутствует в исходном наборе номеров

единичных разрядов

# # , то

8-й степенной разряд числа

0100 нель­

зя изменить; числа

(0000) =0

также нет и поэтому 4-й

степенной

разряд числа 0100 остается без изменения. Однако число (ОНО) =6 содержится во второй группе исходного набора номеров и, следова­ тельно, мы можем заменить число 0100 на 01X0 и отметить это зна­

ком V

против числа 6 во второй группе. Так как оба числа (0101) =

= 5 и

(0111) =7 имеются, то можно

дополнительно упростить им-

пликанту и перейти

от представления 01X0 к 01 XX, отметив числа

5 и 7 в рабочей таблице знаком V -

Представлению дшпликанты

01 XX

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

булева функция

С ■D, причем С -D имеет еди­

ницы в 4, 5, 6 и 7-м разрядах.

 

 

 

Теперь «непокрытым» остается только 14-й разряд изображаю­

щего числа # Я . Запишем в столбец степенных разрядов число

1110

и отметим число 14 знаком Д . Числа

(0110) =6, (0111) = 7 и (1111) =

= 15 имеются в исходном наборе, а

числа (1010) = 10 и (1100) = 12

отсутствуют, так что мы можем заменить число 1110

на х П Х ,

соот­

ветствующее первой

импликанте В- С, и записать

V против

чисел

6, 7 и 15.

_

 

 

 

Таким образом,

Н=А + С • (B + D).

 

 

5.5.ЛОГИЧЕСКАЯ ЗАВИСИМОСТЬ И НЕЗАВИСИМОСТЬ ВЫСКАЗЫВАНИИ. МЕТОД НАХОЖДЕНИЯ ЯВНОГО ВИДА ЛОГИЧЕСКОЙ ЗАВИСИМОСТИ

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

нию, га

булевых функций /і(Л,

В, С

, .,fn {A, В,

С,. . .)

являются независимыми,

если в совокупности при

всевозможных значениях аргументов А, В, С,... они мо­

гут принимать все 2" комбинаций значений истинности.

Следовательно,

для проверки независимости

функций

fi(A, В, С

,

.,fn(A, В, С,... ) необходимо

по отно­

119

шению к Ь[А, В, С, ... ] вычислить

# / , (А, В, С,...)

(5.5)

#L ( A , В, С,...)

ипроверить, образуют ли столбцы набора (5.5) все 2п чисел 0, 1, . . 2п— 1; если все 2" чисел имеются, то функ­

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

двоичных чисел, представленных столбцами набора (5.5) , возрастают вдоль столбца сверху вниз.

Например, пусть_ требуется установить, являются ли функции А • B + Ä- В и В независимыми или нет. Запи­

шем их изображающие числа в виде последовательных

строк:

3 2 0 1

#( А - В + Л - 1 ) = 1 00 1

# £ = 1 1 0 0 .

Колонки набора представляют все возможные комби­ нации значений истинности, соответствующие числам 0, 1, 2, 3. Следовательно, рассматриваемые функции не­

зависимы.

_

__

_ _

Три функции

А- В+ А - В ,

В и А - В + А - В зависимы

так как в наборе

 

 

 

#( Л . Д + Л-£)=Ю01

=1100

#( А - Ъ + Л - В ) = 0ПО

содержатся только числа 1, 3, 4, 6, а числа 0, 2, 5, 7 от­ сутствуют.

Для того чтобы найти явную форму логической связи зависимых булевых функций fi(A, В, С, . . . ), . . .,fn (А, В,

С, ... ) в виде

Д(/і,...,/п)= І ,

(5.6)

поступают следующим образом. Выписывают в последо­ вательные строки изображающие числа вычисленные по отношению к базису Ь[А, В, С,...], и

определяют, какие числа отсутствуют в наборе столбцов

(5.5)

, причем

повторяющиеся значения

имеющихся чи­

сел считают один раз. Столбцы

набора

(5.5)

представ­

ляют

собой все

те комбинации

значений

истинности

120

Смотрите также файлы