Новости    Библиотека    Байки    Ссылки    О сайте


предыдущая главасодержаниеследующая глава

§ 1.5. Регулярные сети диаграмм Венна

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

Рис. 1.37
Рис. 1.37

Сеть будем называть М-регулярной, если диаграммы i-того ранга могут соединяться кривыми только с диаграммами (i - 1)-га ранга, 1 < i ≤ g, g - число рангов в сети.

Примеры М-регулярных сетей приведены на рис. 1.37, 1.38 (о диаграммах в фигурных скобках рассказывается ниже).

Очевидно, что любая двухранговая сеть является М-регулярной.

М-регулярную сеть будем называть регулярной, если она удовлетворяет следующим условиям.

1. Диаграммы первого ранга содержат одинаковое число переменных. Число переменных каждой диаграммы i-того ранга равно числу диаграмм в (i - 1)-ом ранге, 1 <i ≤ g, g - число рангов в сети.

2. На каждой диаграмме (i - 1)-го ранга может начинаться только одна кривая, оканчивающаяся на данной диаграмме i-того

ранга. Нумерация кривых, оканчивающихся на любой диаграмме t-того ранга, совпадает с нумерацией диаграмм в (i - 1)-ом ранге (слева направо), 1 < i ≤ g. В этом случае кривые на рисунках можно не чертить.

Например, сеть, показанная на рис. 1.37, регулярна, а сеть на рис. 1.38 не является регулярной.

Результирующие диаграммы первого ранга регулярных сетей совпадают с операторами первого ранга, если число переменных не увеличивается.

Обозначения для регулярных сетей:

a1,....,an - различные переменные каждой диаграммы первого ранга;

ki - число диаграмм в i-том ранге, 1 ≤ i ≤ g, g - число рангов в сети, kt равно числу переменных каждой диаграммы (i + 1)-го ранга, 1 ≤ i < g;

di,1,...,diki-1 различные переменные каждой диаграммы i-того ранга 1 < i ≤ g;

Рис. 1.38
Рис. 1.38

Φ1,1,....,Φ1,k1 - формулы, соответствующие диаграммам первого ранга Dτ1,1,..., Dτ1,k1. Эти формулы составлены из переменных a1,..., аn и являются формулами, соответствующими результирующим диаграммам первого ранга [Dτ1,1],..., [Dτ1,k1]

Φi,1,..., Φi,ki - формулы, соответствующие диаграммам i-того ранга Dτi,1,...,Dτi,ki, 1 < i ≤ g. Они составлены из переменных di,1,......,di,ki-1

Ψi,1,.....,Ψi,ki - формулы, соответствующие результирующим диаграммам i-того ранга [Dτi,1],..., [Dτi,ki1,..., аn и являются совершенными дизъюнктивными нормальными формами формул Хi,1,...,Xi,ki где

(1.13)

Если i = 2,то формула Ψi-1,t совпадает с формулой Φ1,t, t = 1,...,k1.

Если i > 2, то формулы Ψi-1,1,...,Ψi-1, составленные из переменных а1,..., аn, являются совершенными дизъюнктивными нормальными формами формул Хi-1,1,..., Хi-1,ki-1, где

(1.14)

В силу определения совершенных дизъюнктивных нормальных

формул Xi,j = X'i,j, 2 < i ≤g, j = 1,..., ki,

(1.15)

Подставив Xi-1,t, t = 1,...., ki-1 из (1.14) в (1.15), получим

(1.16)

(используется известное свойство операции подстановки: результат подстановки в некоторую формулу Φ вместо ее переменных d1,..., dk, формул φ1,..., φk, которые в свою очередь являются результатами подстановки соответственно в формулы ψ1,...,ψk, составленные из одних и тех же переменных а1,...,a1 вместо их переменных а1,..., аn формул τ1,....., τn, равен результату подстановки вместо переменных а1,...,an соответственно формул τ1,..., τn в результат подстановки в формулу Φ вместо ее переменных d1,..., dk соответственно формул ψ1,....,ψk).

Если i = 3, то формула Ψi-2,t в (1.14) - (1.16) совпадает с формулой Φ1,t, t = 1,..., k1.

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

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

На рисунках результирующие диаграммы, заменяющие два последних ранга, помещаем в фигурных скобках слева от соответствующих операторов. На втором шаге диаграммы в фигурных скобках рассматриваются как операторы над диаграммами (g - 2) -го ранга исходной сети. Если g > 3, то результирующие диаграммы этих операторов помещаем в фигурных скобках слева от соответствующих операторов. Если g = 3, то результирующие диаграммы совпадают с результирующими диаграммами исходной сети (располагаются в квадратных скобках справа от выходных диаграмм исходной сети). Общее число диаграмм, находящихся в фигурных скобках слева от выходной диаграммы сети, равно g - 2.

Формулами регулярной сети G будем называть следующие формулы Xt, t = 1,..., kg, где kg - число диаграмм в последнем, g-том, ранге сети G:

(1.17)

где


u = 1,..., kg-1, kg-1 - число диаграмм в (g - 1)-ом ранге сети G и т. д.;


v = 1,..., k3; k3 - число диаграмм в третьем ранге сети G;


w = 1,..., k2; k2 - число диаграмм во втором ранге, k1 - в первом ранге сети.

Введем также формулу X (G) ↔ (Х & ... &Xkg).

Определим понятие избыточности относительно двух эквивалентных регулярных сетей G1 и G2. Будем говорить, что сеть G1 избыточнее сети G2, если формула X (G1) избыточнее формулы X(G2).

Например, четырехранговая регулярная сеть с двумя выходами (рис. 1.37) эквивалентна менее избыточной трехранговой регулярной сети (рис. 1.39), отличающейся от исходной только тем, что два последних ранга заменены их результирующими диаграммами.

Рис. 1.39
Рис. 1.39

Следовательно, описанный второй способ построения результирующих диаграмм позволяет заменить любую данную регулярную сеть эквивалентной регулярной сетью с меньшим числом рангов и поэтому являющейся менее избыточной по сравнению с исходной.

Этот процесс обратим, т. е. для любых заданных диаграмм можно построить такую регулярную сеть с любым требуемым числом рангов и с указанным количеством диаграмм в рангах, что данные диаграммы будут являться результатами ее работы. Сеть при этом строится неоднозначно. С ростом числа рангов и числа диаграмм в рангах избыточность сети увеличивается. Очевидно также, что избыточность сети увеличивается с увеличением числа точек на ее диаграммах; само собой разумеется, что речь идет о построении сетей более избыточных, но эквивалентных исходной.

Естественно, возникает вопрос о связи регулярных сетей с сетями более сложной природы (сети без обратных связей, более сложные, чем регулярные, описаны в предыдущем параграфе; о сетях с обратными связями рассказывается в следующем параграфе).

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

Покажем, что для любой сети (без обратных связей) можно построить эквивалентную ей регулярную сеть.

Начнем с М-регулярных сетей. Опишем способ построения эк-вивалентных им регулярных сетей, после чего перейдем к произвольным сетям. Укажем способ построения для любой сети (без обратных связей) эквивалентной ей М-регулярной сети. Тем самым поставленная задача о нахождении для любой сети эквивалентной ей регулярной сети будет решена.

В § 1.2 даны четыре операции над диаграммами Венна, .введем еще две операции.

5. Изменение нумерации кривых оператора. Пусть дана двух-ранговая сеть с одним выходом. Пусть β1,...,βh - все ячейки, в которых на Dτ2,1 находятся точки. Пусть 1,..., m - номера кривых сети.

Построим новую двухранговую сеть с одним выходом, операторы этой сети будем обозначать D̂τ2,1.

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

Переменные D̂τ2,1, обозначим d'1,....,d'm- Каждая ячейка β на Dτ2,1 имеет вид d̃β1,....,d̃βm, где


Каждой ячейке β диаграммы Dτ2,1 поставим в соответствие ячейку β' диаграммы D̂τ2,1, β' ↔ d̃'β1 ,...,d̃'βm , где


Получаем, что ячейке d1...dm соответствует ячейка d'1...d'm, а ячейке d̄1...d̄m - ячейка d̄'1 ...d̄'m.

В качестве выходной диаграммы сети возьмем оператор D̂τ2,1 (d'1,...,d'm), у которого точки находятся только в ячейках β'1,...,β'h соответствующих ячейкам β1,..., βh диаграммы Dτ2,1.

Нетрудно убедиться, что построенная сеть эквивалентна исходной. Ее будем называть результатом операции 5 при данном изменении нумерации кривых исходной сети. В дальнейшем при применении операции 5 будем предполагать, что нумерация кривых изменяется так, что получается регулярная сеть.

Пример 1.10 (продолжение). Сеть (рис. 1.25) эквивалентна регулярной двухранговой сети с одним выходом (рис. 1.40).

6. Увеличение числа кривых оператора. Пусть дана двухранговая сеть с одним выходом. Пусть β1,..., βh - все ячейки, в которых на Dτ2,1 находятся точки. Пусть 1,..., m - номера кривых сети.

Построим новую одновыходную двухранговую сеть, операторы которой будем обозначать D̄τ2,1.

Рис. 1.40
Рис. 1.40

Диаграммами первого ранга будем считать результирующие диаграммы первого ранга исходной сети и какую-то произвольную диаграмму, т. е. число диаграмм первого ранга равно k + 1, где k - число диаграмм в первом ранге исходной сети. Новая диаграмма может быть расположена в любом месте первого ранга. Будем предполагать, что все диаграммы первого ранга новой сети имеют одинаковое число переменных n, n = max (n1,....,nk), где ni - число переменных на Dτ1,i , i = 1,..., k.

Сеть имеет m + 1 кривую: m кривых по расположению и нумерации совпадают с кривыми исходной сети, (m + 1)-я кривая начинается на новой (k + 1)-й диаграмме первого ранга.

Оператором D̄;τ2,1 будем считать результат операции 1 над диаграммой Dτ2,1 при увеличении числа переменных на единицу; новая переменная соответствует (m + 1)-й кривой.

Полученную сеть будем называть результатом операции 6. Нетрудно убедиться, что результат операции 6 эквивалентен исходной сети, но построенная новая сеть избыточнее исходной. Например, сеть на рис. 1.32 можно заменить эквивалентной сетью с большим числом диаграмм в первом ранге (рис. 1.41.)

Рис. 1.41
Рис. 1.41

Построение регулярных сетей, эквивалентных данной М-р егулярной сети. Дана произвольная М-регулярная сеть G. Опишем способ построения регулярной сети, эквивалентной данной.

1. Диаграммы первого ранга заменим их результирующими диаграммами с одним и тем же числом переменных n, n = max (n1,....., nk), где ni - число переменных на i-той диаграмме, i = 1,.., - число диаграмм в первом ранге исходной сети. Получим сеть G1 эквивалентную G.

2. Если на некоторой диаграмме Dτr,j сети G1 начинается l кривых, l > 1, оканчивающихся на одной диаграмме Dτr+1,t, то в r-том ранге добавляем l - 1 диаграмму, каждая из которых отличается от Dτr,j только тем, что на ней начинается только одна кривая, связывающая ее с Dτr+1,t, при этом на Dτr,j из l кривых оставляем только одну; нумерация кривых, оканчивающихся на Dτr+1,t, не изменяется.

В результате получаем, что на каждой диаграмме r-того ранга может начинаться одна кривая из числа оканчивающихся на данной диаграмме (r + 1)-го ранга, r = 1,..., g - 1, g - число рангов в исходной сети. Построенная сеть G2 эквивалентна G1.

3. Увеличим число кривых, оканчивающихся на каждом операторе Dτr,j сети G2, начиная со второго ранга, так, чтобы число переменных каждой диаграммы r-того ранга стало равным числу диаграмм в (r - 1)-ом ранге, 1 < r ≤ g, и чтобы на каждой диаграмме (r - 1)-го ранга начиналась только одна кривая, оканчивающаяся на рассматриваемом операторе Dτr,j. При этом используется операция 6, она может применяться последовательно несколько раз: при первом применении роль диаграмм первого ранга играют диаграммы (r - 1)-го ранга исходной сети, связанные с Dτr,j роль новой диаграммы - одна из диаграмм (r - 1)-го ранга, не связанная с Dτr,j.

В результате получаем, что число переменных на каждой диаграмме r-того ранга равно числу диаграмм в (r - 1)-ом ранге, на каждой диаграмме (r - 1)-го ранга начинается только одна кривая, оканчивающаяся на а число кривых, начинающихся на каждой диаграмме (r - 1)-го ранга, равно числу переменных каждой диаграммы r-того ранга. Получим сеть G3, эквивалентную G2.

4. Изменим нумерацию кривых, оканчивающихся на каждой, диаграмме r-того ранга сети G3 так, чтобы она совпадала с нумерацией диаграмм в (r - 1)-ом ранге (слева направо), r = 2,..., g. При этом используется операция 5, роль диаграмм первого ранг& играют все диаграммы (r - 1)-го, а роль оператора Dτ2,1 - диаграмма Dτr,j изменения при применении операции 5 могут происходить только на диаграмме Dτr,j.

Рис. 1.42
Рис. 1.42

В результате получаем регулярную сеть G4 эквивалентную исходной сети G.

Пример 1.14. На рис. 1.42 построена регулярная сеть, эквивалентная М-регулярной сети рис. 1.38.

Построение М-регулярных сетей, эквивалентных данной. Дана произвольная сеть G. Требуется построить М-регулярную сеть, эквивалентную G.

Пусть кривая а начинается на диаграмме Dτr,j и оканчивается операторе Dτr+i,j, i > 1, 1 ≤ r < g - 1 - число рангов сети G.

Кривую α заменим последовательностью диаграмм одной переменной, в первой ячейке которых находится точка, а нулевая ячейка пуста.

К (r+1)-ому рангу добавим диаграмму Dτr+1,kr+1+1 одной переменной, в первой ячейке которой содержится точка, где kr+1 - число диаграмм в (r + 1)-ом ранге. Соединим эту диаграмму кривой с диаграммой Dτr,t.

Аналогично добавляем диаграмму Dτr+u,kr+u+1 одной переменной с точкой в первой ячейке к (r + u)-ому рангу. От диаграммы Dτr+u-1,kr+u-1+1 (1) К диаграмме Dτr+u,kr+u+1 (1) проводим кривую, u = 2,..., i - 1.

От диаграммы Dτr+i-1,kr+u+1 (1) проводим кривую, оканчивающуюся на диаграмме Dτr+i,j Этой кривой присваиваем номер кривой α сети G.

Таким способом можно заменить все кривые сети G, начинающиеся в r-том ранге и оканчивающиеся в (r + i)-ом ранге, i > 1, 1 ≤ r < g - 1. В результате получаем М-регулярную сеть G1, эквивалентную исходной сети G. Для сети G1 можно построить эквивалентную ей регулярную сеть G2.

Следовательно, для любой сети можно построить эквивалентную ей регулярную сеть.

Пример 1.13 (продолжение). Трехранговая сеть G с двумя выходами (рис. 1.36) нерегулярна. На рис. 1.43 построена M-регулярная сеть, эквивалентная G.

Рис. 1.43
Рис. 1.43

Вернемся к соответствию между диаграммами Венна и формулами исчисления высказываний (см. § 1.3.). Покажем, что для каждой формулы Φ можно построить одновыходную сеть, результирующей диаграммой которой будет диаграмма формулы Φ.

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

Пример 1.15. Пусть формула Φ есть (2 а3) & (а1 ⊃ a2))- На рис. 1.44 показано одно из деревьев ее построения, в вершинах расположены логические знаки формулы.

Дерево построения формулы Φ можно преобразовать в сеть диаграмм Венна.

Диаграммы, соответствующие переменным а1,..., аn, образуют первый ранг сети. Они строятся так же, как в § 1.3.

Логическому знаку отрицания соответствует оператор отрицания (см. выходную диаграмму на рис. 1.26).

Логическому знаку конъюнкции & соответствует оператор конъюнкции (см. выходную диаграмму на рис. 1.27).

Остальные логические операции можно выразить, как известно, через отрицание и конъюнкцию:

(1.18)
(1.19)

где Φ1 и Φ2 - произвольные формулы.

Используя (1.18), построим оператор дизъюнкции двух переменных как результирующую диаграмму сети на рис. 1.45.

Используя (1.19), построим оператор импликации как результирующую диаграмму сети на рис. 1.46.

Рис. 1.44
Рис. 1.44

Рис. 1.45
Рис. 1.45

Рис. 1.46
Рис. 1.46

Рис. 1.47
Рис. 1.47

Таким образом, сеть диаграмм G, соответствующая дереву построения формулы Φ, имеет вид: первый ранг образуют диаграммы переменных a1,...,an из которых составлена формула Φ; остальные ранги получаются заменой логических знаков в дереве построения формулы на соответствующие операторы.

Построенная сеть G имеет только одну выходную диаграмму, результат ее работы является диаграммой формулы Φ. При этом сеть G, как правило, не является М-регулярной. Но можно построить эквивалентную G регулярную сеть G1, формула X (G1) которой является более избыточной, чем исходная формула Ф.

Пример 1.15 (продолжение). Из дерева Φ ((a2a3)&(a1⊃a2)) (рис. 1.44) получим сеть G диаграмм (рис. 1.47). Результат работы сети G есть диаграмма, соответствующая формуле Φ, совершенной дизъюнктивной нормальной формой которой является формула (а1 & а2 & а3), построенная по результирующей диаграмме сети.

предыдущая главасодержаниеследующая глава





Пользовательский поиск


Диски от INNOBI.RU




© Злыгостев Алексей Сергеевич, подборка материалов, оцифровка, статьи, оформление, разработка ПО 2001-2017
При копировании материалов проекта обязательно ставить активную ссылку на страницу источник:
http://informaticslib.ru/ "InformaticsLib.ru: Информатика"