Кочергин В.И. Теория многомерных цифро-векторных множеств

Подождите немного. Документ загружается.

Глава 1

соответствия двоичного принципа кодирования представятся записью: 0 ↔ 0,

1 ↔ 1, 2 ↔ 2, 3 ↔ 3 , 4 ↔ 4, 5 ↔ 5, 6 ↔ 6, 7 ↔ 7, а другой вариант кодирова-

ния будет представлен, например, иной записью соответствия: 0 ↔ 0, 1 ↔ 2,

2 ↔ 1, 3 ↔ 3 , 4 ↔ 4, 5 ↔ 5, 6 ↔ 6, 7 ↔ 7 и т.д.

Поставив на первое место в ряду кодов двоичный код, представляет опре-

деленный интерес определить место в этом ряду каждому коду. Для этого не-

обходимо принять определенное правило для формирования остальных типов

кодов.

Для основания n=2 все просто: число различных перестановок равно двум

(0 1) и (1 0). Первая перестановка определяет двоичный код, вторая – обрат-

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

разом:

( 0 1)

( 1 0)

n = 2 (1.2.1)

Для основания n=3 число различных перестановок представляется также

весьма просто матрицей размерами 3 × 2

( 0 1 2) ( 0 2 1)

( 1 0 2) ( 1 2 0)

( 2 1 0) ( 2 0 1)

n = 3 (1.2.2)

В (1.2.2) содержится шесть перестановок, а дальнейшее представление

принципов кодирования оснований n = 4, 5, 6, ... может быть сформулировано

следующим правилом.

Первый столбец матрицы перестановок i-го основания системы счисления

образуется из элементов первого столбца матрицы перестановок (i – 1)-го ос-

нования системы счисления, где в каждой перестановке добавляется цифра

(i – 1), а последний i элемент первого столбца матрицы перестановок i-го

ос-

нования состоит из цифр в последовательности (i – 1) (i – 2) ... 0.

В матрице перестановок i-го основания число столбцов совпадает с чис-

лом элементов матрицы перестановок (i – 1)-го основания, где в матрице i-го

основания каждый первый элемент столбца содержит первую цифру 0, а ос-

тальные цифры этого элемента равны цифрам элементов матрицы перестано-

вок (i – 1)-го основания при их прохождении сверху вниз и слева направо, уве-

личенным на единицу.

Все последующие цифры элементов в каждом из столбцов задаются по-

рядком расположения цифр первого столбца матрицы перестановок искомого

i-го основания.

Основные положения теории

Тогда следующая матрица размерами 4 × 6 определяет все коды основания

n = 4:

( 0 1 2 3) ( 0 2 1 3) ( 0 3 2 1) ( 0 1 3 2) ( 0 2 3 1) ( 0 3 1 2)

( 1 0 2 3) ( 1 2 0 3) ( 1 3 2 0) ( 1 0 3 2) ( 1 2 3 0) ( 1 3 0 2)

( 2 1 0 3) ( 2 0 1 3) ( 2 3 0 1) ( 2 1 3 0) ( 2 0 3 1) ( 2 3 1 0)

( 3 2 1 0) ( 3 1 2 0) ( 3 0 1 2) ( 3 2 0 1) ( 3 1 0 2) ( 3 0 2 1)

n = 4 (1.2.3)

и т.д.

Для неизбыточных кодов, где основание системы счисления кратно двум

n = 2

, матрицы перестановок непосредственно определяют все типы возмож-

ных кодов. Если первая перестановка и ее цифровые эквиваленты от 0 до

– 1) соответствуют кодовым комбинациям двоичного принципа кодирова-

ния, то все остальные перестановки этих цифр дают только порядок располо-

жения этих кодовых комбинаций в других принципах кодирования, а эквива-

лентные им сигналы ОЦК должны также располагаться в последовательности

от 0 до (2

– 1).

Принимая для любых типов кодов неизменность кодового слова для циф-

ры 0, равенство нулю всех сигналов кода, число кодов для основания n

уменьшается до значения (n – 1)!, а с учетом необходимости иметь каждому

коду его обратный код число кодов равно 2[(n – 1)!]. Так, для основания n = 4

число прямых кодов будет определяться первой строкой матрицы (1.2.3).

Кроме понятия «нулевых» кодов введем понятие «дружественных» кодов,

в которых, дополнительно к постоянству кодовой комбинации сигналов циф-

ры 0, устанавливается такое же постоянство комбинации сигналов для цифры

(n – 1) – равенство их всех логической единице. Число «дружественных» ко-

дов равно (n – 2)!.

Число эквивалентных кодов S

, т.е. кодов одинаковой структуры, опреде-

ляет число классов неизбыточного кода мерности K. Очевидно, что число

классов неизбыточного кода мерности K равно n!/ S

Число «дружественных» кодов каждого класса определяется числом пере-

становок K аргументов кода, в образовании которых будем также придержи-

ваться представленного выше порядка.

Для избыточных кодов n < 2

их общее число кодов определяется зависи-

мостью C

×(n!), а с учетом равенства нулю всех сигналов кода, эквивалент-

ных цифре 0 основания системы счисления, число кодов уменьшается до ве-

личины 2C

(n–1)

(2K–1)

×[(n – 1)!]. Число избыточных кодов огромно и не поддает-

ся счету.

Поэтому остановим пока внимание только на неизбыточных кодах. В этом

случае каждый код основания n имеет свой порядковый номер в последова-

тельности перестановок П

(n–1)

. Все двоичные коды при таком подходе имеют

нулевой номер для любого основания системы счисления.

Глава 1

В этих кодах любая цифра основания позиционной системы счисления оп-

ределяется как конъюнкция всех K аргументов кода. Поэтому знание числа

конъюнкций определенного ранга и общего числа конъюнкций всех рангов, а

также определенного порядка их образования требует уделить этому вопросу

некоторое внимание.

Определение конъюнкций первого ранга тривиально – в качестве конъ-

юнкций здесь выступают сами аргументы x

и их инверсии x

. При K аргумен-

тах число таких конъюнкций 2K. Это значение конъюнкций может быть

представлено так же, как число сочетаний из 2K по 1, т.е. C

= 2K.

Для нахождения конъюнкций второго ранга можно определить число соче-

таний из 2K по 2 и в этом числе сочетаний вычеркнуть такие, где содержатся

произведения x

. Таким же образом можно определить все конъюнкции j-го

ранга, находя все сочетания из 2K по j и убирая нулевые произведения. Этот

способ определения конъюнкций не продуктивен, не имеет определенного по-

рядка их образования, не дает их общего числа и каждого числа конъюнкций

определенного ранга.

Изложение предложенной процедуры определения числа конъюнкций

начнем на

примере шести аргументов (x

, x

, … , x

)

кода, который затем рас-

пространим на их любое число.

Матричная форма записи числа конъюнкций второго ранга, где элементар-

ная матрица содержит четыре конъюнкции второго ранга

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

дующим образом:

(1.2.4)

Из этой записи следует, что число конъюнкций второго ранга здесь равно

60. В самом деле, каждая элементарная матрица содержит четыре конъюнкции

второго ранга, например:

а число таких элементарных матриц равно 15.

Основные положения теории

Элементарная матрица для конъюнкций третьего ранга a

ijs

, которая состо-

ит из восьми конъюнкций третьего ранга, записывается через элементарные

матрицы второго порядка:

ijs

или

ijs

(1.2.5)

Тогда конъюнкции третьего ранга в координатах прямых и инверсных сиг-

налов аргументов второго ранга имеют вид

123

124

125

126

134

135

136

145

146

156

234

235

236

245

246

256

345

346

356

456

ijs

(1.2.6)

Элементарная матрица конъюнкций четвертого ранга a

ijst

, которая состоит

из шестнадцати конъюнкций четвертого ранга, равна

ijs

ijst

(1.2.7)

Конъюнкции четвертого ранга в координатах прямых и инверсных сигна-

лов аргументов и конъюнкций третьего ранга записываются следующим обра-

зом:

Глава 1

Элементарная матрица конъюнкций пятого ранга состоит из тридцати двух

конъюнкций пятого ранга

ijst

ijstl

(1.2.9)

Конъюнкции пятого ранга в координатах прямых и инверсных сигналов

аргументов и конъюнкций четвертого ранга представляются следующим обра-

зом:

1234

12345

12346

1235

12356

1245

12456

1345

13456

2345

23456

ijstl

(1.2.10)

Элементарная матрица конъюнкций шестого ранга состоит из шестидесяти

четырех конъюнкций шестого ранга и равна

12345

123456

(1.2.11)

Приведенные выражения для шести аргументов позволяют представить

общую зависимость числа конъюнкций любого ранга при неограниченном

числе аргументов K.

Число сочетаний из 2К по j , где j = 1, 2, …, К, определяется следующими

простыми выражениями:

123

1234

1235

1236

124

1245

1246

125

1256

134

1345

1346

135

1356

145

1456

234

2345

2346

235

2356

245

2456

345

3456

(1.2.8)

Основные положения теории

= 2K = 2C

=0) =2

[(K

–

1) +(K

–

2) + ... + 1]= 2

(

=0) =2

[{(K

–

2) + ... + 1}+{(K

–

3) + ... + 1}+ ... +1]= 2

(

=0) =2

[{(K

–

3) + ... + 1}+{(K

–

4) + ... + 1}+ ... +1]= 2

…

=0) = 2

. (1.2.12)

Поскольку конъюнкцию любого ранга можно записать как произведение K

сомножителей, каждый из которых может принимать значение x, x либо от-

сутствовать, то общее число конъюнкций всех рангов, включая и нулевой ранг

(

= 0), равно 3

. В этом легко убедиться непосредственно из (1.2.12) для

конкретного значения K.

1.3. Основные логические операции над подмножествами

многомерного цифрового пространства

Создатель основ теории множеств выдающийся немецкий математик

Г. Кантор рассматривал множество как объединение в одно целое объектов,

различимых нашей интуицией или мыслью. Понятие «множество» относится к

неопределенным понятиям науки, но в нашем случае под множеством будем

понимать, как отмечено выше, числа натурального ряда от 0 до (2

– 1), пред-

ставленные в любой позиционной системе счисления. Очевидно, что все из-

вестные правила действия над множествами [14] полностью распространяются

на эти цифровые множества. Поэтому здесь приведем только те из них, кото-

рые определяются нашими ограничениями.

Принадлежность цифры i множеству A обозначается i ∈ A (i принадлежит

A); непринадлежность обозначается i ∉ A (i не принадлежит A).

Если A

(i – разряд числа A ), то запись A = {A

, ..., A

} означает разряды

, ... суть элементы множества (числа) A .

Запись A

= {

, 1

, ... , (n

–

} = {

0, 1, ... , (n

–

}

озна-

чает цифры разряда i (0, 1, ... , (n – 1)), где n – основание системы счисления,

суть элементы подмножества (разряда) A

Одноэлементное множество – множество, состоящее из одного элемента,

например {

} или {A

}, где в первом случае элементом является цифра раз-

ряда A

, а во втором случае – это i-й разряд числа A (иерархия элементов,

подмножеств).

Пустое множество ∅ – множество, не содержащее элементов (цифр) вооб-

ще. Множества A и ∅ называются несобственными подмножествами множе-

ства A, а все остальные подмножества A – его собственными подмножествами.

Например, множества натуральных чисел являются подмножеством всех це-

Глава 1

лых чисел, а последние, в свою очередь, – подмножеством множества всех ра-

циональных чисел.

Известно [14], что «множества, встречающиеся в рассуждениях той или

иной математической теории, являются подмножествами некоторого фиксиро-

ванного множества E, называемого универсальным для данной теории». Уни-

версальным для нашего случая является множество, где во всех ячейках мно-

гомерного цифрового пространства расположены логические единицы 1*.

Множества A и B называются равными, A = B, если они состоят из одних и

тех же элементов на всех ступенях иерархии.

Если все элементы множества A являются также элементами множества B,

то A – подмножество B, или A включается в B, что обозначается как A ⊆B.

Если A ⊆ B, причем A ≠ B, то записывается A ⊂ B. Знак ⊂ в, отличие от знака

⊆, называется знаком строгого включения.

Для любого множества A выполняется включение ∅ ⊂ A, A ⊂ A (реф-

лексность).

Множества A и ∅ называются несобственными подмножествами множест-

ва A, а все остальные подмножества A – его собственные подмножества.

Если A ⊆ B и B ⊆ C , то A ⊆ C (транзитивность).

Если в качестве элементов множества используются другие множества,

например A = {A

, A

, ..., A

}, то это семейство множеств {A

| i ∈ I}, где

– некоторое множество, например, i-го разряда натурального числа A , а

I – множество индексов, которое может быть конечным или бесконечным.

Очевидно, что множества, состоящие из конечного числа элементов, назы-

ваются конечными; в противном случае говорят о бесконечных множествах.

Бесконечным множеством является множеств цифр расширенного натурально-

го ряда, а множество цифр конкретного основания n позиционной системы

счисления является конечным.

Говорят, что «элементы множеств Α и Β находятся во взаимно однозначном

соответствии, если каждому элементу a множества Α сопоставлен по некоторому

закону единственный элемент в множестве Β, причем каждый элемент b∈Β ока-

зывается сопоставленным одному и только одному элементу a ∈Α». Взаимно

однозначное соответствие

элементов множеств Α и Β обозначается как a ↔ b.

Множества Α и Β называются эквивалентными или равномощными (Α ∼ Β),

если можно установить взаимно однозначное соответствие их элементов. Это

определение распространяется на конечные и бесконечные множества. Очевид-

но, что конечные множества Α и Β эквивалентны лишь тогда, когда они содер-

жат одинаковое число элементов. Причем если Α ∼ Β', где Β' ⊂ Β, то множество

Α содержит меньше элементов, чем множество Β. Таким образом, понятие чис-

ла элементов множества эквивалентно понятию мощности множества.

Общеизвестно, что непротиворечивость любой теории заключается в том,

что в ней не может быть получено противоречие, т.

е. не может быть доказано

некоторое утверждение А и его отрицание А.

Основные положения теории

Выдающийся математик Д. Гильберт полагал, что «парадоксы возникают

тогда, когда пользуются недопустимыми и бессмысленными образованиями

понятий». При этом необходимо различать действительные и идеальные пред-

ложения классической т.е. «чистой математики». Первые должны включать со-

держательный смысл, а вторые могут его и не включать.

Например, предложения, употребляющие понятия бесконечности, идеаль-

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

ниям о бесконечных множествах.

Для бесконечных множеств можно также задать вопрос: нельзя ли «беско-

нечность» одного множества считать большей, равной или меньшей, чем «бес-

конечность» другого множества? Здесь ответ заключается в понятии одинако-

вой мощности этих множеств, если между их элементами можно установить

взаимно однозначное соответствие, т.е. если одно множество можно также

отобразить на другое, что каждому элементу первого взаимно однозначно со-

ответствует некоторый элемент второго. Если же подобное отображение не-

осуществимо, то множества имеют различную мощность; при этом оказывает-

ся, что в последнем случае, как бы мы ни пытались привести в соответствие

элементы обоих множеств, всегда останутся лишние элементы и притом по-

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

мощность».

Бесконечное множество чисел натурального ряда N

и бесконечное мно-

жество ячеек многомерного цифрового пространства при любом числе мерно-

сти этого пространства имеют одинаковую мощность и, следовательно, по оп-

ределению эквивалентны.

Фиксированное множество Ε, определяющее все многомерное цифровое

пространство, где множества Α, Β,... являются его подмножествами, как уже

отмечалось выше, называется универсальным.

Каждому подмножеству A ⊆ Ε сопоставим функцию y

такую, что y

= 1*,

если подмножество A не пустое (A ≠ ∅), и y

= 0*, если A =∅. Тем самым

достигается полное соответствие: между операцией объединения ∪ и логиче-

ским сложением ∨, между операцией пересечения ∩

и логическим умножени-

ем &, между операцией дополнения Α

и логической операцией отрицания Α.

Для перехода от конкретной фигуры цифрового множества к логической

функции, по которой строится принципиальная схема логического блока, не-

обходимо дать определение покрытия цифрового множества: покрытием дан-

ного цифрового множества называется конечная совокупность его подмно-

жеств, дающая в своей сумме всё это цифровое множество.

Классической постановкой задачи определения покрытия «длины», «пло

щади», «объема» цифровых множеств является поиск нормальной минималь-

ной дизъюнктивной формы (ДНФ), когда лучшей считается логическая схема,

соответствующая этой ДНФ и занимающая меньшую площадь кристалла

большой интегральной схемы (БИС). Представленный критерий оптимизации

в тесном сочетании с технологическими требованиями регулярности структу-

ры БИС привел к отображению на плоскости либо объеме кристалла ДНФ ло-

Глава 1

гической функции или системы функций в виде матричных схем, которые по-

лучили название программируемых логических матриц (ПЛМ), а также других

микросхем программируемой матричной логики (ПМЛ).

Предлагаемая теория многомерных цифровых множеств является инстру-

ментом, наилучшим образом ориентированным на автоматизацию синтеза та-

ких БИС, когда конструкция каждой из них имеет не только аналитическую

запись в ДНФ, но и физический геометрический образ цифрового множества

многомерного цифрового пространства.

Это есть стремление к наглядности, которая, по мнению Д. Гилберта,

«стремится к живому пониманию объектов и их внутренних соотношений».

Именно наглядность играет в теории многомерных цифровых множеств

первостепенную роль как обладающая большой доказательной силой для по-

нимания и оценки результатов автоматизированного синтеза ЛФ, что будет

доказано ниже.

Особое значение здесь придается изучению симметрии цифрового про-

странства и его подмножеств, как свойству содержать в себе равные и однооб-

разно расположенные части, где законы преобразования фигур в пространстве

являются следствием симметрии законов самого многомерного цифрового

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

1.4. Бинарные логические операции в двухмерном цифровом

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

Общепринятое аналитическое рассмотрение бинарных логических опера-

ций, как правило, начинается с представления ЛФ двух аргументов x

, что

представлено табл. 1.4.1.

Таблица 1.4.1

оцк x

Не будем перечислять известные из учебной литературы названия и обо-

значения логических операций, представленных в этой таблице.

Поскольку концепция эквивалентности вариантов покрытия «длины»,

«площади», «объема» лежит в основе конкретной реализации логического

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

этих фигур.

На рис. 1.5 приведены геометрические образы всех шестнадцати бинар-

ных ЛФ в двухмерном пространстве E

, которое имеет пять осей симмет-

рии 1–5. Допуская, что входы и выходы логических блоков имеют шины

прямых и инверсных сигналов, число рассматриваемых фигур в пространстве

любой кратности значительно сокращается. Для нашего случая y

= y

, y

= y

, y

= y

, y

= y

, y

= y

, y

= y

, y

= y

, y

= y

Основные положения теории

Дальнейшее сокращение количества рассматриваемых фигур связано с

симметрией пространства E

Мысленный поворот вокруг оси 1 приводит к записи аргумента x

ЛФ в

обратном коде x

→ x

; поворот вокруг оси 2 – к записи аргумента x

в ис-

ходной ЛФ в обратном коде x

→ x

; поворот вокруг оси 3 приводит к смене

местами аргументов (x

, x

) → (x

, x

); поворот вокруг оси 4 приводит к сме-

не местами аргументов, а также записи их в обратном коде (x

, x

) → (x

, x

);

каждый последовательный мысленный поворот вокруг оси 5 на 90º против ча-

совой стрелки приводит к смене местами аргументов с одновременной запи-

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

зом: → (x

, x

) → → (x

, x

) → (x

, x

) → (x

, x

)→ (x

, x

), а при вращении в

противоположном направлении – к смене аргументов в обратном направлении.

Исходя из симметрии двухмерного цифрового пространства и убрав из рас-

смотрения тривиальные функции y

= ∅ = 0*, y

= E

= 1*, конструкцию любо-

Рис. 1.5

= y

(1) = y

(2) = y

(3) = y

(4) = y

(1) = y

(2) = y

(3) = y

= y

= E

(1) = y

(2) = y

(3) = y

(4) = y

(6) = y

(5) = y

(4) = y