Автор неизвестен - Бионика интелекта информация язык интеллект№ 3 (77) 2011научно-технический журналоснован в октябре 1967 г - страница 25

Страницы:
1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77 

 

1

0

0

0

0

0

 

 

 

 

Наибольшего упрощения формулы для преди­ката В можно достичь, замещая все нули едини­цами, но тогда формула В превратится в истину, а формула С совпадет с формулой А, и в результате эффективная декомпозиция формулы А не будет достигнута. В табл. 3 даны значения предиката В, полученного в результате более умеренного заме­щения нулей единицами. Очень сильно упрощать формулу для предиката В не следует, так как это может привести к неоправданному усложнению формулы С. По табл. 3 находим минимальную ДНФ: B=y1t1vx0z0. В табл. 4 переносим все едини­цы предиката А (то есть все единицы табл. 2) и все нули предиката Av В.

Таблица 4

zt

xy

0

0

1

1

 

0

1

1

0

0

0

1

 

 

0

 

 

 

 

0

1

1

1

 

1

 

 

 

 

1

 

1

0

 

1

 

 

 

 

1

 

 

 

 

0

 

 

 

 

Нули надо ставить только в тех ячейках, в кото­рых в табл. 3 стоят единицы, «лишние» по сравне­нию с табл. 2. В ячейках табл. 4, оставшихся неза­полненными, можно проставить нули и единицы произвольным образом, руководствуясь сообра­жениями минимизации формулы С. Предикат Сзадаем табл. 5, ей соответствует следующая мини­мальная ДНФ:

C=x0t1vy1z0.

Таблица 5

zt

xy

0

0

1

1

 

0

1

1

0

0

 

1

1

0

0

 

 

 

 

0

1

1

1

0

1

 

 

 

 

1

1

1

 

0

1

 

 

 

 

1

0

0

0

0

0

 

 

 

 

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

y1^t1vx0y1t1vx0y1^vx0z0t1=(y1t1vx0^)A(x0t1vy1^). Мы совершили декомпозицию уравнения

y1z0t1Vx0y1t1Vx0y1z0Vx0z0t1=1

на систему более простых уравнений:

(б)

[ y1t1 V x 0 z 0 [x 0t1 v y1z0

(в)

Заметим, что в данном примере декомпозиция уравнения привела не только к уменьшению длины каждого уравнения, но и к упрощению полной его записи, поскольку общее число узнаваний буквы в системе уравнений (в) меньше, чем в исходном уравнении (8 против 12).

Если бы мы в качестве первого сомножителя выбрали более простую формулу, B'=y1vt1, что со­ответствует табл. 6, то в роли второго сомножителя вынуждены были бы взять более сложное выраже­ние (см. табл. 7 и 8):

CWzVyWvxVt1.

Такое построение приводит к системе уравне­ний

y1Vt1

1,

x0 z0 v y1z 0t1 v x0 y1t1

1,

(г)

более сложной, чем система (в) (10 узнаваний буквы против 8).

Таблица 6

zt

xy

0

0

1

1

0

0

 

 

 

 

0

1

1

1

1

1

 

 

 

 

1

1

1

1

1

1

 

 

 

 

1

0

1

1

0

0

 

 

 

 

В'

zt

xy

Таблица 7

1

0

0

 

1

0

 

0

 

 

 

 

0

1

1

1

0

1

 

 

 

 

1

0

1

0

0

1

 

 

 

 

1

 

0

0

 

0

 

 

 

 

Наиболее сложное уравнение в системе (в) име­ет 4 узнавания буквы, в системе (г) — 8 узнаваний буквы. Таким образом, вариант декомпозиции (в) по обоим показателям удачнее варианта (г). Ре­зультат декомпозиции, вообще говоря, оказыва­ется различным в зависимости от того, будем ли мы стремится к минимизации наиболее сложного уравнения системы или же к минимизации сум­марной сложности уравнений системы. Общий метод решения этих задач здесь не приводится.

Таблица 8

zt

xy

0011 0110

0

1

1

0

 

0

 

 

 

 

0

1

1

1

0

1

 

 

 

 

1

0

1

0

0

1

 

 

 

 

1

0

0

0

0

0

 

 

 

 

С

Задачу декомпозиции уравнения можно сфор­мулировать и по-другому. Требуется заменить уравнение А=1 равносильной ему системой урав­нений {А1=1, А2=1,..., An=1}, причем число n урав­нений нас не лимитирует и может быть принято достаточно большим. Однако важно, чтобы каждое уравнение А;=1 (1</<n) было как можно более про­стым. Похожую задачу решает школьный учитель, излагающий первоклассникам свою мысль в виде последовательности достаточно простых выска­зываний. Метод решения этой задачи продемон­стрируем на примере. Задано уравнение (б). Пре­дикату, стоящему в левой части этого уравнения, соответствует табл. 2. Единицы таблицы охватыва­ем какой-нибудь системой прямоугольников мак­симального размера, соответствующих наиболее коротким простым импликантам (табл. 9).

В результате получаем предикат A1=y1vt1. Кре­стиками в таблице отмечены «лишние» ячейки, по­павшие внутрь прямоугольников. Содержательно эти ячейки будем интерпретировать как признак неполноты выражения мысли А высказыванием

С

А1. Чем больше крестиков содержится в таблице, тем менее полно выражена мысль. Далее формиру­ем предикаты A2=y1vz0, A3=x0vy1, A4=z0vt1, A5=x0vt1, A6=x°vz° с таким расчетом, чтобы, во-первых, каж­дый из них был возможно более простым и, во-вторых, чтобы с введением очередного предиката сокращалось число крестиков (таблицы 10-5-13).

Таблица 9

Таблица 14

Таблица 10

Таблица 11

Таблица 12

После введения предиката А6 все крестики исчеза­ют (табл. 14). Это значит, что мы достигли полного выражения мысли А системой высказываний А1-А6. Таким образом, мы совершили декомпозицию урав­нения (б) на систему простых уравнений

y1vt1=1, y1 vz°=1, x°vy1=1, z°vt1=1, x°vt1=1, x°vz°=1.

Заметим, что в результате декомпозиции сум­марное число узнаваний буквы в системе уравне­ний осталось таким же, как и в исходном уравне­нии (12 узнаваний буквы).

Таблица 13

ху 00 01 11 10

zt 00

01 11

10

 

(1

 

 

1

1

Страницы:
1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77 


Похожие статьи

Автор неизвестен - 13 самых важных уроков библии

Автор неизвестен - Беседы на книгу бытие

Автор неизвестен - Беседы на шестоднев

Автор неизвестен - Богословие

Автор неизвестен - Божественность христа