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


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

§ 1.4. Сети диаграмм Венна в исчислении высказываний

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

Чтобы предварительно пояснить, в чем тут дело, вернемся к при меру 1.6. Две формулы:


эквивалентны. Однако формула Φ содержит больше логических знаков, чем формула Φ1. В этом случае говорят, что формула Φ является избыточной по сравнению с формулой Φ1.

Аналогично формулы


эквивалентны. Однако первая формула содержит большее число переменных и знаков операций, чем вторая, и ее значение не зависит от того, какое значение принимает переменная а3. В этом случае также говорят, что первая формула является избыточной. Информацию, которую несет первая формула, можно выразить, таким образом, с помощью гораздо более короткой формулы.

Если в какую-нибудь формулу, содержащую n различных переменных, на место этих переменных поставить какие-нибудь формулы от тех же переменных, то получим новую формулу от этих n переменных, в которую в свою очередь можем подставить на место переменных какие-нибудь новые формулы от тех же переменных, и т. д. Каждая такая формула представляет собой некоторую функцию от ее переменных. Но различных функций от n переменных только 22n; представляющих же эти функции формул, можно написать сколь угодно много. Вот и получается избыточность информации о функции, задаваемой с помощью формулы. Распоряжаться такой избыточностью будем с помощью сетей диаграмм Венна.

Между диаграммами Венна и функциями n переменных легко устанавливается соответствие.

Отметим, что

1) каждой ячейке βi диаграммы Венна n переменных соответствует только один набор значений n независимых переменных, при этом номер ячейки βi, записанный в двоичной системе, совпадает с соответствующим набором значений переменных;

2) на диаграмме Венна формулы Φ в ячейке βi - тогда и только тогда находится точка, когда значение формулы Φ, соответствующее набору значений переменных, который совпадает с номером ячейки βi в двоичной системе, равно единице.

3) две формулы Φ1 и Φ2, составленные из одних и тех же переменных, эквивалентны тогда и только тогда, когда их диаграммы Венна n переменных графически совпадают.

Выше в диаграммах Венна n переменных предполагалось, что все n переменных независимы. Теперь при одновременном рассмотрении нескольких диаграмм снимем для некоторых из них требование независимости переменных; будем говорить, что все рассматриваемые диаграммы образуют сеть.

Описание строения сетей диаграмм. Каждая сеть состоит из нескольких рядов (рангов) диаграмм. Диаграммы первого ранга являются входными диаграммами, диаграммы последнего ранга - выходными.

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

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

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

Обозначения: Dτr,i- диаграмма Венна, расположенная в r-том ранге на i-том месте (ранги нумеруются сверху вниз, диаграммы в ранге - слева направо); [Dτr,i] - результирующая диаграмма оператора Dτr,i.

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

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

Одноранговые сети. Каждая диаграмма n переменных является одноранговой сетью с одним выходом. Результирующей диаграммой такой сети считаем данную диаграмму или результат операции 1 над данной диаграммой (при увеличении числа переменных). В последнем случае результирующую диаграмму помещаем в квадратных скобках справа от оператора.

Пример 1.2 (продолжение). На рис. 1.17 расположена одноранговая сеть с одним выходом, результирующая диаграмма совпадает с данной диаграммой. На рис. 1.23 - эта же сеть с результирующей диаграммой четырех переменных (для сравнения см. рис. 1.18).

k диаграмм соответственно n1,...,nk переменных, расположенных в одном ранге, образуют одноранговую сеть с к выходами. Результирующие диаграммы каждого из операторов строятся независимо от остальных. Иногда требуется, чтобы все результирующие диаграммы были диаграммами n переменных, n > max {n1,...,nk}. Пример 1.9. На рис. 1.24 дана одноранговая сеть с двумя выходами, n1 = 2, n2 = 3, n = 4.

Рис. 1.23
Рис. 1.23

Рис. 1.24
Рис. 1.24

Двухранговые сети с одним выходом. Первый ранг образуют k диаграмм соответственно n1..., nk переменных.

Диаграммы этого ранга называются входными.

Во втором ранге находится одна выходная диаграмма nk+1 переменных, на которой оканчиваются стрелками nk+1 кривых, начинающихся на диаграммах первого ранга. Все кривые перенумерованы (см., например, рис. 1.25). Если каждая диаграмма первого ранга связана только одной кривой с выходной диаграммой (в этом случае nk+1 = k), и нумерация кривых совпадает с нумерацией всех диаграмм первого ранга (слева направо), то кривые чертить на рисунках не будем (см., например, рис. 1,26, 1.27). Иногда будем опускать не кривые, а только числа - номера кривых; например, на рис. 1.28 кривые нумеруются слева направо.

Рис. 1.25
Рис. 1.25

Рис. 1.26
Рис. 1.26

Рис. 1.27
Рис. 1.27

Рис. 1.28
Рис. 1.28

Результирующие диаграммы* первого ранга строятся аналогично случаю одноранговых сетей. Все они имеют n переменных, n ≥ max {n1,.....,nk}.

* (Для краткости часто слова "результирующие диаграммы операторов r-того ранга" заменяем словами "результирующие диаграммы r-того ранга".)

Построение результирующей диаграммы сети. Пусть на диаграмме Dτ2,1 в ячейках β1,...,βh и только в них находятся точки. Переменные оператора Dτ2,1 обозначим через d1 ,..., dm где m = nk+1 индексы 1, ..., m совпадают с номерами кривых, оканчивающихся на Dτ2,1. Образуем диаграммы Dτ1,...., Dτm если i-тая кривая начинается на диаграмме Dτ1,j, j = 1,....,k, то Dτi↔[Dτ1,j] i = 1,...,m; при этом если на диаграмме Dτ1,j начинается t кривых, t > 1, то в указанном перечне Dτ1,..., Dτm диаграмма [Dτ1,j] повторяется t раз.

Построим символ Венна n переменных. Пусть (для определенности) ячейка β1 есть d1.....dii+1... d̄m.

В ячейках символа Венна, совпадающих.с ячейками, в которых на всех диаграммах Dτ1 ,...,Dτi находятся точки, а на всех диаграммах Dτi+1,....,Dτm нет точек, и только в них поставим по одной точке; если i = 0, то точки ставятся во всех тех ячейках, которые пусты на всех диаграммах Dτ1,.....,Dτh.

Аналогично поступаем с остальными ячейками βi оператора Dτ2,1, 1<i≤h, при этом ранее занятые точками ячейки результирующей диаграммы (для β1,...,βi-1 ) не рассматриваются. Понятно, что если на операторе Dτ2,1 нет точек, то результирующая диаграмма пуста, т. е. не содержит точек.

На рисунках результирующие диаграммы будем помещать в квадратных скобках справа от их операторов.

Пример 1.10. На рис. 1.25 дана двухранговая сеть с одним выходом, k = 3, n1 = 2, n2 = 3, n3 = 3, n4 = 3, n = 3. На выходной диаграмме Dτ2,1 (d1, d2, d3) точки расположены в ячейках 0, 3 и 4, т. е. β112d3, β212d3, β3 d123.


Поставим точки, соответствующие ячейке β1 оператора Dτ2,1. На диаграммах Dτ1, Dτ2, Dτ3 только одна пустая ячейка - четвертая, поэтому на результирующей диаграмме [Dτ2,1] в ячейке 4 ставим точку.

Перейдем к ячейке β2 оператора Dτ2,1.

На диаграммах Dτ2, Dτ3 в ячейках 0 и 3 находятся точки, а на диаграмме Dτ1 эти ячейки пусты, поэтому в ячейках 0 и 3 диаграммы [Dτ2,1] ставим точку; больше таких ячеек, как 0 и 3, на диаграммах Dτ1, Dτ2, Dτ3 нет.

Перейдем к ячейке β3 оператора Dτ2,1.

На диаграмме Dτ1 в ячейке 5 есть точка, а ячейка 5 диаграмм Dτ2 и Dτ3 пуста, поэтому в ячейке 5 диаграммы [Dτ2,1] ставим точку; больше таких ячеек, как пятая, на диаграммах Dτ1, Dτ2 и Dτ3 нет.

Пример 1.11. На рис. 1.28 дана двухранговая сеть с одним выходом; на операторе Dτ2,1 (3) оканчиваются две кривые, начинающиеся на диаграмме Dτ1,1(3), и одна кривая, начинающаяся на Dτ1,3(3); Dτ1 ↔ [Dτ1,1], Dτ2 ↔ [Dτ1,1], Dτ3 ↔ [Dτ1,2].

Правила работы оператора двухранговой сети тесно связаны с операциями над диаграммами Венна.

Если оператор Dτ2,1 имеет только две ячейки (рис. 1.1), в ячейке ā1 (номер 0) есть точка, а в ячейке а1 (номер 1) нет точки, то его результирующая диаграмма совпадает с отрицанием результирующей диаграммы первого ранга. В этом случае оператор будем называть оператором отрицания. Например на рис. 1.26 приведен оператор отрицания диаграммы Венна трех переменных.

Если оператор Dτ2,1 есть диаграмма m переменных, содержащая точку только в ячейке номер 2m - 1, то его результирующая диаграмма совпадает с конъюнкцией результирующих диаграмм первого ранга, с которыми связан этот оператор. В этом случае оператор будем называть оператором конъюнкции. Например, на рис. 1.27 содержится оператор конъюнкции двух переменных (для сравнения см. пример 1.4).

Рис. 1.29
Рис. 1.29

Рис. 1.30
Рис. 1.30

Если оператор Dτ2,1 есть диаграмма m переменных, m > 1, содержащая только одну точку, например в ячейке d1... dl dl+1... dm, то результат работы этого оператора совпадает с диаграммой (...((... (Dτ1&Dτ2)&...&Dτi)& Dτi+1)& ... & Dτm). Например, на рис. 1.29 дана двухранговая сеть, результирующая диаграмма которой совпадает с диаграммой ((Dτ1 &Dτ2)&Dτ3), где Dτ1 ↔ [Dτ1,1], Dτ2 ↔ [Dτ1,2] и Dτ3 ↔ [Dτ1,3].

Действительно, диаграмма Dτ2 есть результат операции 2 над диаграммой Dτ2 (рис. 1.30), (Dτ1 & Dτ2) - результат операции 3 над Dτ1 и Dτ2 (рис. 1,31), ((Dτ1&Dτ2)&Dτ2) - результат операции 3 над (Dτ1&Dτ2) и Dτ3, графически равный результирующей диаграмме рассматриваемой сети.

Рис. 1.31
Рис. 1.31

Если оператор Dτ2,1 есть диаграмма m переменных, содержащая h точек, h > 1, то для каждой точки отдельно можно построить диаграммы Dτ1,..., Dτh, тогда результат работы этого оператора совпадает с диаграммой (...(Dτ1 ∨ Dτ2) ∨... ∨ Dτh). Например, на рис. 1.32 находится двухранговая сеть, результирующая диаграмма которой совпадает с диаграммой ((((Dτ1 & Dτ2) & Dτ3) ∨(( Dτ1&Dτ2)&Dτ3)) ∨ ((Dτ1 & Dτ2) & Dτ3)), где Dτ1, Dτ2 и Dτ3 - результирующие диаграммы первого ранга.

Рис. 1.32
Рис. 1.32

Оператору Dτ2,1 (m) соответствует формула Φ, составленная из переменных d1,...., dm, где индексы 1,..., m совпадают с номерами кривых, оканчивающихся на Dτ2,1. i-той кривой соответствует диаграмма Dτi, i = 1,..., m, если кривая начинается на диаграмме Dτ1,j, j = 1,..., k, то Dτi ↔ [Dτ1,j]. Диаграмме D] соответствует формула Φi, составленная из n графически различных переменных, i = 1,....., m.

Пусть а1,..., аn - все графически различные переменные формул Φ1,..., Φm. Пусть формула Ψ, составленная из n переменных а1,...,аn, соответствует результирующей диаграмме [Dτ2,1] сети. Тогда формула Y есть совершенная дизъюнктивная нормальная форма формулы X, где X - результат подстановки в формулу Φ вместо переменных d1,..., dm соответственно формул Φ1,..., Φm:

XFd1.....dmΦ1....ΦmΦ, (1.6)

Это предложение вытекает из рассмотренных правил работы оператора Dτ2,1 двухранговой сети, связанных с операциями над диаграммами Венна в исчислении высказываний.

Пример 1.10 (продолжение). Для сети на рис. 1.25


Ψ - совершенная дизъюнктивная нормальная форма формулы X.

Ясно, что без использования оператора Dτ2,1 построение совершенной дизъюнктивной нормальной формы, составленной из переменных а1, а2, a3 формулы X будет более громоздким. Этот пример показывает, как сети диаграмм можно использовать для преобразования формул.

Выше (§ 1.3.) отмечалось, что по диаграмме Венна переменных аn можно также строить формулы с меньшей логической длиной, чем их совершенная дизъюнктивная нормальная форма, в каждый дизъюнктивный член которой входят все переменные а1...аn (может быть с отрицанием). В случае, когда число пустых ячеек диаграммы меньше числа ячеек, занятых точками, построение удобнее начинать с пустых ячеек. Можно идти дальше, выделяя те фигуры, все ячейки которых пусты. Так, формула Φ3, логическая длина которой равна 21, эквивалентна формуле Φ'3 (a1 & а2& а3) ∨ (а1 & а2)) логической длины 8; обе ячейки а1а̄2а̄3 а1а̄2а̄3 фигуры а1а̄2 на диаграмме Dτ1,3 (рис. 1.25) пусты.

Аналогично при построении формул по ячейкам, занятым точками, можно выделять те фигуры, в каждой ячейке которых находятся точки, при этом получится ДНФ. Так, формула Φ2 логической длины 19 эквивалентна формуле Φ'2 а1 логической длины 1; ячейки ā123, а̄1а̄2a3, ā1a23 и ā1a2a3 фигуры ах на диаграмме [Dτ1,1] (или ячейки ā12 и а̄1а2 фигуры ах на диаграмме Dτ1,1) заполнены точками. Формула Ψ эквивалентна формуле Ψ' (а2 & a3) ∨ (a1& a2 & a3) ∨ (a1 & а2)) с меньшей логической длиной.

Формула X, составленная из переменных а1, а2, а3 и определяемая сетью на рис. 1.25, является избыточной по сравнению с формулой Ψ (и еще более по сравнению с формулой Ψ'), составленной из тех же переменных а1, а2 и а3 и определяемой результирующей диаграммой этой сети.

Пример 1.11 (продолжение). Для сети на рис. 1.28

Φ1Φ2(a12a3∨a1a2a3), Φ1 ≡ Φ'1

Φ'113) (все ячейки фигуры а1а3 на Dτ1,1 содержат точки);


Формула X, составленная из переменных a1, а2 и а3 и определяемая сетью на рис. 1.28, является избыточной по сравнению с формулой Ψ, составленной из тех же переменных а1, а2 и а3 и определяемой результирующей диаграммой этой сети.

Каждой диаграмме Венна n переменных можно поставить в соответствие несколько эквивалентных между собой формул исчисления высказываний. Диаграмму можно считать результирующей диаграммой некоторой двухранговой сети с одним выходом. В этом случае число графически различных, но эквивалентных между собой формул, представляющих данную диаграмму, резко возрастает.

Совершенной дизъюнктивной нормальной формулой (СДНФ) диаграммы Венна n переменных будем называть совершенную дизъюнктивную нормальную формулу, соответствующую этой диаграмме, в каждый член которой входят все переменные а1,...,аn (может быть с отрицанием).

Число всех различных диаграмм Венна n переменных равно 22n. Следовательно, один символ Венна n переменных может выражать 22" неэквивалентных между собой формул - СДНФ различных диаграмм Венна n переменных.

В двухранговой сети с одним выходом содержится k +1 символов Венна соответственно n1, n2,..., nk, nk+1 переменных. Поэтому число всех возможных случаев расположения точек на этих символах Венна, т. е. число графически различных сетей, равно

(1.7)

(при этом порядок расположения кривых не учитывается).

Если n1 = n2 = ... = nk = nk+1 - n, то (1.7) преобразуется

(1.8)

Так как информацию, которую несет любая двухранговая сеть с одним выходом, можно выразить с помощью только одной диаграммы - результирующей диаграммы сети, то среди всех Е(n1,... ..., nk, nk+1) графически различных сетей много эквивалентных.

Две сети называем эквивалентными, если их результирующие диаграммы, построенные из одних и тех же переменных, графически совпадают.

Две сети эквивалентны тогда и только тогда, когда формулы их результирующих диаграмм эквивалентны.

Обозначим число неэквивалентных между собой двухранговых сетей с одним выходом через F(n1,..., nk, nk+1).

Если n1 = n2 = ...= nk+1 = n, то вместо F(n1,..., nk, nk+1) аналогично (1.8) пишем F(n):

F(n) = 22n (1.9)

- числу всех различных диаграмм Венна n переменных.

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

Обозначать логическую избыточность будем R2(n1,...., nk; nk+1);

(1.10)

В случае (1.8), (1.9)

(1.11)

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

Рис. 1.33
Рис. 1.33

Например, для n = 1, E(n) = 16, F(n) = 4, R2(n) = 4; на рис. 1.33 приведены все графически различные диаграммы, а на рис. 1.34 - все 16 возможных сетей для этого случая.

Рис. 1.34
Рис. 1.34

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

Число диаграмм в первом ранге обозначим k1 во втором - k2. Число переменных i-той диаграммы первого ранга обозначим ni, i = 1,..., k1 число переменных j-той диаграммы второго ранга - nj, j = k1 + 1,....., k1+k2 Переменные оператора Dτ2,u, u = 1,.....,k2 обозначим du,1,...,du,nj, где индексы 1,..., nj совпадают сномерами кривых, оканчивающихся на Dτ2,u, jτ = kτ + 1,...,k1 + k2.

Для каждого оператора Dτ2,u образуем диаграммы [Dτ]u,1, [Dτ]u,nj: если v-тая кривая начинается на диаграмме Dτ1,w w = 1,..., k1, то [Dτ]u,v ↔ [Dτ1,w], v = 1,..., nj.

Формулу, соответствующую оператору Dτ2,u(nj), фбозначим Φ2,u. Формула Φ2,u есть формула, составленная из переменных du,1 ,....,du,nj.

Формулу, соответствующую диаграмме [Dτ]u,v, обозначим Φ2, Формулу, соответствующую результирующей диаграмме [Dτ2,u], обозначим Ψ2,u.

Аналогично случаю двухранговых сетей с одним выходом формула Ψ2,u и является совершенной дизъюнктивной нормальной формой формулы Х2,u, где

(1.12)

т. е. формула Х2,u есть результат подстановки в формулу Φ2,u вместо переменных du, 1,..., du,nj соответственно формул Φ2,u,1,......,Φ2,u,nj

Рис. 1.35
Рис. 1.35

Пример 1.12. На рис. 1.35 показана двухранговая сеть с двумя выходными диаграммами. Результирующих диаграмм две, они строятся независимо друг от друга. k1 = 3, k2 = 2, n1 = 3, n2 = 3, n3 = 2.

Для первой выходной диаграммы Dτ2,1(2): n4 = 2; d1,1, d1,2 - переменные; [Dτ]1,1 ↔ [Dτ1,1], [Dτ1,1]Dτ1,1, [Dτ]1,2 ↔[Dτ1,3] точки находятся в ячейках 0 и 3;


Для второй выходной диаграммы Dτ2,2(3): n5 = 3, d2,1, d2,2, d2,3 - переменные; [Dτ]2,1 ↔ [Dτ1,2], [Dτ]2,2 ↓ [Dτ1,2], [Dτ1,2] Dτ1,2, [Dτ]2,1 [Dτ]2,2, [Dτ]2,3 ↔ [Dτ1,3] точки находятся в ячейках 1, 2, 6 и 7;

β12,12,2d2,3; β22,1d2,22,3' β3d2,1d2,22,3; β4 d2,1d2,2d2,3

заметим, что для ячейки (32 на диаграммах [Dτ]2,1, [Dτ]2,2 и [Dτ]2,3 нет таких ячеек, в которых на [Dτ]2,2 есть точки, а на [Dτ]2,1 и [Dτ]2,3 пусто, поэтому на результирующей диаграмме [Dτ2,2] нет точек, соответствующих β2.


Многоранговые сети. Сети, имеющие несколько рангов, называются многоранговыми. Каждый ранг строится аналогично первому и второму рангам двухранговой сети. В первом ранге находится k1 входных диаграмм соответственно n1,...., nk1 переменных, в i-том ранге ki диаграмм соответственно nk1+...+ki-1+1,......., nk1+...+ki; переменных, 1 < i ≤ g, где g - число рангов в сети.

Диаграммы g-ого ранга называются выходными.

На каждой из диаграмм ni переменных, i ≥ k1+1, оканчиваются стрелками ni кривых, соединяющих эту диаграмму с некоторыми из диаграмм вышестоящих рангов.

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

Построение результирующих диаграмм ведется последовательно: строятся результирующие диаграммы в первом ранге; потом - результирующие диаграммы во втором ранге, при этом диаграммы второго ранга играют роль операторов над связанными с ними результирующими диаграммами первого ранга; затем - результирующие диаграммы в третьем ранге, при этом диаграммы третьего ранга играют роль операторов над связанными с ними результирующими диаграммами в первом и во втором рангах, и т. д.; наконец, строятся результирующие диаграммы в g-том ранге, при этом выходные диаграммы играют роль операторов над связанными с ними результирующими диаграммами в вышестоящих рангах.

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

Правила работы операторов в i-том ранге, 3 ≤ i ≤ g, ничем не отличаются от правил работы операторов в одноранговых и двухранговых сетях.

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

Пример 1.13. На рис. 1.36 расположена трехранговая сеть с двумя выходами. k1 = 3, k2 = 3, k3 = 2, n1 = 3, n2 = 3, n3 = 2.

Для первой диаграммы второго ранга, т. е. для оператора Dτ2,1 (4): n4 = 4, d2,1,1, d2,1,2, d2,1,3, d2,1,4 переменные, [Dτ]2,1,1↔[Dτ1,1], [Dτ1,1]Dτ1,1, [Dτ]2,1,2↔[Dτ1,1], [Dτ]2,1,3[Dτ]2,1,1 (две кривые начинаются на первой диаграмме первого ранга), [Dτ]2,1,3 ↔ [Dτ1,2], [Dτ1,2]Dτ1,2, [Dτ]2,1,4↔[Dτ1,3], [Dτ1,3]≡Dτ1,3

точки находятся в ячейках 3,11 и 12;


Рис. 1.36
Рис. 1.36

Для второй диаграммы второго ранга, т. е. для оператора Dτ2,2 (3): n5 = 3; d2,2,1, d2,2,2, d2,2,3 - переменные; точки находятся в ячейках 1, 2 и 4;


Х2,2 (Φ̄2,2,1Φ̄2,2,2Φ̄2,2,3∨Φ̄2,2,1Φ2,2,2ΡΦ̄2,2,3 ∨ Φ̄2,2,1Φ̄2,2,2Φ̄2,2,3)

Для третьей диаграммы второго ранга Dτ2,3(3): n6 = 3; d2,3,1, d2,3,2, d2,3,3 - переменные; [Dτ]2,3,1 ↔ [Dτ1,1], [Dτ]2,3,2 ↔ [Dτ1,2], [Dτ]2,3,3 ↔ [Dτ1,3] точки находятся в ячейках 0,5 и 7;

PI J_ 4, 3, l4, 3, г4, 3, з;


Для первой диаграммы третьего ранга Dτ3,1(3): n7 = 3; d3,1,1, d3,1,2, d3,1,3 - переменные; [Dτ]3,1,1 ↔ [Dτ1,2], [Dτ]3,1,2 ↔ [Dτ2,2], [Dτ]3,1,3 ↔ [Dτ2,1]; точки находятся в ячейках 4, 5 и 7;


Для второй диаграммы третьего ранга Dτ3,2(3): n8 = 3; d3,2,1, d3,2,2, d3,2,3 - переменные; [Dτ]3,2,1 ↔ [Dτ2,1], [Dτ]3,2,2 ↔ [Dτ2,2], [Dτ]3,2,3 ↔ [Dτ2,3]; точки находятся в ячейках 0,1 и 6;


Результирующими формулами сети являются формула Ψ3,1 - СДНФ диаграммы [Dτ3,1] и формула Ψ3,2 - СДНФ диаграммы [Dτ3,2].

Формулы Х3,1 и Х3,2, составленные из переменных а1, а2 и а3 и определяемые сетью на рис. 1.36, являются избыточными по сравнению соответственно с формулами Ψ3,1 и Ψ3,2, составленными из тех же переменных а1, а2 и а3 и определяемыми результирующими диаграммами этой же сети.

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





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


Диски от INNOBI.RU




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