WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 || 3 | 4 |   ...   | 11 |

3. Обозначим через P2 множество всех (двузначных) булевых функций, через 0 тождественный нуль и через 1 тождественную единицу. Тогда АС P2,,, ¬, 0, 1 есть булева алгебра. Её называют булевой алгеброй логических функций.

4. Пусть N свободное от квадратов натуральное число. Это означает, что справедливо представление N = p1... pk, где p1,..., pk различные простые числа. Совокупность всех делителей N обозначим D(N). Например, для N = 30 = 2 · 3 · имеем D(30) = { 1, 2, 3, 5, 6, 10, 15, 30 }.

Наименьшее общее кратное чисел m и n обозначим mn, а их наибольший общий N делитель mn. Положим m =. Тогда АС D(N),,,, 1, N, как нетрудно m проверить, есть булева алгебра.

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

Из данных контактов можно строить электрические двухполюсные (один вход и один выход) цепи. Если соединять друг с другом только входные и выходные полюсы, то имеется только два способа объединения таких цепей: последовательное и параллельное. Таким образом получают класс т.н. параллельно-последовательных контактных схем. Их ещё называют П-схемами.

Под произведением A · B будем понимать цепь, образованную из сетей A и B путём присоединения выходного полюса цепи A к входному полюсу цепи B с сохранением входного полюса A в качестве входного полюса всей полученной цепи, в выходного полюса B в качестве её выходного полюса. Под суммой A + B будем понимать цепь, полученную объединением соответственно входных и выходных полюсов цепей A и B. Обозначим через I постоянно замкнутый, а через O постоянно разомкнутый контакты. При этом проводимость получаемых цепей будут описываться т.н. безповторными формулами, в которых каждому контакту цепи соответствует выражающая его проводимость единственная пропозициональная переменная, встречающаяся в формуле ровно один раз.

Две цепи будем считать одинаковыми, если можно так сопоставить контактам переменные, что при одном и том же состоянии контактов, соответствующим одной переменной и всех произвольных состояниях остальных контактов, обе рассматриваемые цепи являются одновременно либо проводящими, либо не проводящими. Введенное отношение, очевидно, является отношением эквивалентности на множестве цепей. Обозначим через C множество всех попарно неэквивалентных П-схем. Тогда АС C, +, ·,, O, I есть, как нетрудно видеть, булева алгебра.

Применение формульного аппарата булевых алгебр для анализа и синтеза электрических схем имеет огромное прикладное значение. Однако кроме параллельнопоследовательных, существует ещё т.н. “мостиковые” схемы, когда входные или выходные контакты одной цепи присоединяется к внутреннему полюсу другой, образуя, тем не менее, двухполюсную цепь (см. рис. 1).

x1 x• x• x2 x Рис. 1: Мостиковая схема (входной и выходной полюсы обозначены • ).

Для описания таких цепей язык булевой алгебры оказывается недостаточным: не удаётся так усовершенствовать обычный булев аппарат алгебры логики, добавив к нему ещё несколько (конечное число!) операций так, чтобы он стал содержать средства для описания строения не только параллельно-последовательных, но и мостиковых схем, притом описания адекватного, т.е. такого, при котором каждому контакту в схеме соответствует ровно одна буква в формуле, выражающая проводимость данной схемы 3.

Действительно, проводимость мостиковой схемы на рис. 1 описывается булевой функцией, которая задается формулой (x1 (x3 (x4 x5))) (x2 (x4 (x3 x5))), не являющейся, однако, безповторной, и никакое её эквивалентное преобразование не приведёт, как нетрудно убедится, к безповторной форме4.

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

Пример 4. Для любых действительных чисел a, b из отрезка [0, 1] положим a b = max {a, b}, a b = min {a, b}, a = 1 - a.

Система [0, 1],,,, 0, 1 не будет являться булевой алгеброй, поскольку в ней не выполняются, скажем, законы Де Моргана.

Определение 1.3. Пусть даны две булевы алгебры B1 и B2 и взаимнооднозначная функция : B1 B2 такая, что равенства 1) (x y) = (x) (y) 2) (x y) = (x) (y) 3) (x ) = (x) справедливы для всех x и y из B1. Тогда говорят, что булев изоморфизм между B1 и B2, данные алгебры (булево) изоморфны и пишут B1 B2.

= Замечание. Легко показать, что из 1) – 3) следует 4) (o) = o и 5) () =.

А.В. Кузнецов. О безповторных контактных схемах и безповторных суперпозициях функций алгебры логики // Труды матем. ин-та им. В.А. Стеклова, т. LI. М.: 1958.

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

Алгебра двухполюсных сетей / Формальная логика и методология науки. М.: Наука, 1964.

Действительно, (o) = (x x ) = (x) (x ) = (x) (x) = o и аналогично по двойственности для ().

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

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

Пример 5. Тотальная алгебра над n-элементным множеством Булевым изоморфизмом здесь будет является отображение : Bn P(A), ставящее в соответствие вектору (1,..., n) множество { ai,..., ai | i = 1, k = 1, n }.

1 k k Алгебра высказываний, очевидно, изоморфна тривиальной алгебре множеств.

Существует простой критерий изоморфности тотальных алгебр множеств.

Теорема 1.4. Для того, чтобы тотальные алгебры множеств P(A) и P(B) были изоморфны, необходимо и достаточно, чтобы A и B имели одинаковую мощность.

Доказательство. (, необходимость) Пусть существует изоморфизм между алгебрами P(A) и P(B). Тогда взаимнооднозначное соответствие между множествами A и B, откуда следует их равномощность.

(, достаточность) Пусть множества A и B равномощны. Тогда между их элементами можно установить взаимнооднозначное соответствие. Распространим отображение на подмножества множеств A и B, поставив в соответствие произвольному подмножеству X множества A его образ (X) = (a) в B. Простая проверка показыaX вает, что полученное расширение не только устанавливает взаимнооднозначное соответствие между подмножествами A и B, но и является булевым изоморфизмом между P(A) и P(B).

1.1.4 Теорема Стоуна Справедлива следующая основная теорема о представлении произвольных булевых алгебр алгебрами множеств.

Теорема 1.5 (Стоуна). Всякая булева алгебра изоморфна подходящей алгебре множеств.

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

Определение 1.4. Ненулевой элемент a булевой алгебры называется атомом, если для любого её элемента x справедливо либо a x = o, либо a x = a. В последнем случае то говорят, что элемент x содержит атом a.

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

Булева алгебра, в которой каждый ненулевой элемент содержит атом, называется атомной. Обе рассмотренные алгебры атомные. Булеву алгебру, не содержащую ни одного атома называют безатомной или непрерывной. Пример безатомной булевой алгебры будет приведён в п. 2.3.

Множество всех атомов, содержащихся в элементе x булевой алгебры будем обозначать At(x). Без доказательства укажем два утверждения относительно конечных булевых алгебр.

Лемма 1.6. Всякий ненулевой элемент конечной булевой алгебры может быть представлен в виде объединения содержащихся в нём атомов:

x = a.

aAt(x) Например, в тотальной алгебре над множеством {1, 2, 3, 4} элемент x = {1, 2, 3} содержит атомы {1}, {2}, {3} и равен их объединению: x = {1} {2} {3}.

Лемма 1.7. Конечная булева алгебра является атомной.

Для конечного случая теорема Стоуна допускает следующее усиление.

Теорема 1.8. Всякая конечная булева алгебра изоморфна подходящей тотальной алгебре множеств.

Доказательство. Пусть B конечная булева алгебра. Обозначим через At(B) множество всех её атомов. Построим тотальную алгебру множеств над At(B) и покажем, что она изоморфна B.

Рассмотрим функцию, сопоставляющую каждому элементу x из B множество At(x) содержащихся в нём атомов. Покажем, что является искомым изоморфизмом между B и P(At(B)),,,,, At(B).

Убедимся сначала, что (x) = At(x) биекция5 между B и P(At(B)). Действительно, если (b1) = (b2), то b1 = a = a = a = a = b2, aAt(b1) a(b1) a(b2) aAt(b2) и, значит, инъективно. Далее, пусть A произвольное подмножество атомов булевой алгебры B. Определим x соотношением x = a. Тогда (x) = At(x) = A, т.е.

aA сюръективно. Таким образом, биективность отображения показана.

Теперь удостоверимся, что для выполнены свойства (1)–(3) определения 1.3 (нижеприведённые выкладки проведены для произвольных атома a и элементов x, y из B ).

Во-первых, ясно, что At(x y) = At(x) At(y), и поэтому (x y) = At(x y) = At(x) At(y) = (x) (y)).

Таким образом, показано выполнение свойства 1).

Во-вторых, законы дистрибутивности обеспечивают равенство x y = a b = a b = a, aAt(x) aAt(x) bAt(y) aAt(x)At(y) bAt(y) т.е. (x y) = (x) (y), и поэтому свойство 2) выполнено.

В-третьих, (x ) = At(x ) = At(B) At(x) = (x), т.е. свойство 3) выполнено.

Надеемся, читателю известны свойства инъективности, сюръективности и биективности отображений. Их определения даны в п. 1.4.2.

Доказанная теорема имеет следующие простые Следствия. 1. Если конечная булева алгебра имеет n атомов, то общее число её элементов равно 2n.

2. Любые две конечные булевы алгебры с одинаковым числом элементов изоморфны.

3. Любая конечная булева алгебра изоморфна подходящей алгебре n-мерных двоичных векторов.

В некоторых булевых алгебрах удается определить объединение и пересечение произвольной совокупности её элементов. Такая булева алгебра называется полной. Ясно, например, что тотальная алгебра множеств является полной булевой алгеброй, а -алгебра, где операции объединения и пересечения могут браться по счётной совокупности множеств, является “промежуточной” между обычной и полной булевыми алгебрами.

Оказывается возможным распространить доказанный вариант теоремы Стоуна на случай всех полных атомных алгебр, и справедливой является следующая Теорема 1.9 (О представлении полных атомных булевых алгебр). Пусть B полная атомная булева алгебра с носителем B и At(B) множество всех её атомов. Тогда B P(At(B)).

= 1.2 Декартово произведение множеств. Отношения. Однородные отношения 1.2.1 Основные определения Пусть I = { i1, i2,... } произвольное конечное или бесконечное подмножество натурального ряда, которое мы будем называть множеством индексов и каждому i I сопоставлено множество Xi. Декартовым (или прямым) произведением непустых множеств {Xi}iI называют множество последовательностей ( ai, ai,... ), где ai Ai.

1 Декартово произведение обычно определяют для произвольной совокупности индексов. Нам, однако, будет достаточно данного определения. Более того, в дальнейшем мы будем, как правило, рассматривать конечный случай I = {1,..., k}, обозначая декартово произведение k A1 A2... Ak или Ai.

i =k Считается, что Ai Ai. Заметим, что AB = BA. Также ABC, (AB)C i =и A (B C) суть разные множества.

В частном случае A1 =... = Ak = A декартово произведение обозначают Ak и называют k-ой декартовой степенью множества A. Под A0 понимают некоторое одноэлементное подмножество из A. Ясно, что A1 = A и Am An = Am+n.

Определение 1.5. Отношения суть подмножества декартовых произведений множеств.

Число множеств в соответствующем декартовом произведении определяет местность или арность отношения. Говорят об унарных (одноместных), бинарных (двуместных), тренарных (трёхместных) и т.д. отношениях.

n Пусть Ai = A. Отношение = A называют полным; мы будем обозначать его i=.

A Через P r1 обозначают совокупность всех таких элементов a1 A1 для которых найдутся такие a2 A2,..., ak Ak, что (a1, a2,..., ak). P r1 называют проекцией отношения на множество A1 или первой проекцией. Аналогично определяются вторые, третьи и т.д. проекции.

Отношение на A1 A2... Ak называется полным, если его первая проекция совпадает с A1, вторая с A2 и т.д.

Отношения можно рассматривать как предикаты, т.е. функции, принимающие два значения: истина и ложь : считают, что (a1,..., an) истинно, если (a1,..., an) и ложно в противном случае. Поэтому к отношениям можно применять операции алгебры логики: дизъюнкции ( ), конъюнкции ( ), отрицания ( ¬ ), тождества ( ), импликации ( ) и др. При чтении соответствующих формул следует иметь в виду, что, поскольку приоритет отношений выше приоритета операций алгебры логики, скобки вокруг отношений, как правило, опускают.

Унарные отношения на некотором множестве определяют те или иные свойства его элементов.

Бинарные отношения на декартовом произведении множеств A и B называют отношениями между A и B или соответствиями между данными множествами. Для соответствия A B удобно пользоваться обозначением ab, если (a, b).

Поскольку отношения суть подмножества, то для бинарных отношений определена тотальная алгебра P(A B),,,,, A B. Ясно, что теоретико-множественные операции, применённые к соответствиям, A B, имеют следующие свойства:

1) a( )b ab ab (a, b) или (a, b) ;

2) a( )b ab ab (a, b) и (a, b) ;

3) ab ¬(ab) (a, b).

/ Существует удобный способ представления соответствий конечных множеств в виде (0,1)-матриц M(). Пусть A = { a1,..., am }, B = { b1,..., bn } и A B. Зафиксируем указанный порядок следования элементов в множествах A и B. Тогда матрица отношения имеет размеры m n и определяется следующим образом: её элемент mi,j равен 1, если справедливо aibj и 0, если иначе.

Множество всех (0,1)-матриц размера mn будем обозначать Mmn, опуская индекс, когда соответствующий размер подразумевается. Во введённом множестве выделяются матрица, у которой всё элементы равны 1 и матрица, у которой всё элементы равны 0. Их называют универсальной и нуль-матрицей и обозначают I и O соответственно.

К матрицам из M можно поэлементно применять логические операции,, ¬. Легко видеть, что АС M,,, ¬, O, I является булевой алгеброй, изоморфной тотальной алгебре P(A B),,,,, A B. Изоморфизм следует из следующих равенств, очевидно справедливых для любых соответствий и между A и B :

1) M( ) = M() M() ;

2) M( ) = M() M() ;

3) M() = ¬ M().

1.2.2 Псевдообращение и произведение соответствий В данном разделе вводятся новые операции для бинарных отношений (соответствий):

унарная псевдообращения и бинарная произведения.

Определение 1.6. Пусть A B. Операция (#) псевдообращения соответствия def задаёт псевдообратное к нему отношение # B A, определяемое как b#a = ab для любых a A, b B.

Часто употребляют также термины обратное, транспонированное, инверсное или симметричное отношение и пользуются обозначениями -1, и др. Легко установить следующие свойства псевдообращения относительно теоретико-множественных операций и отношения включения:

(#)# =, # = ()#, # #, ( )# = # #, ( )# = # #.

Покажем, например, справедливость последнего равенства (a и b произвольные элементы из A и B соответственно):

b( )#a = a( )b = ab ab = b#a b#a = b(# #)a.

Определение 1.7. Пусть A, B и C непустые множества и A B, B C.

Тогда произведение (или сокращённо ) соответствий и определяется как def a( )c = b (ab bc) B для произвольных a A, c C.

Можно показать, что произведение соответствий обладает свойствами () = (), ()# = ##, ( ) =, ( ) =, но ( ) =, ( ) =.

Пусть M1 Mmn, M2 Mnr. Определим произведение M1 · M2 данных матриц:

n M1 · M2 = M1 M2, i = 1, m, j = 1, r.

i,j i,k k,j k=Легко показывается, что если A B и B C, где A, B, C конечные множества, то справедливо равенство M( ) = M() · M().

Далее нам понадобится ещё одно свойство произведения отношений. Пусть, A B и, B C. Тогда для любых a A и c C имеем a[( ) ( )]c = x [a( )x x( )c] = B = x [ax ax xc xc] B = a( )c a( )c = a[( ) ( )]c.

Pages:     | 1 || 3 | 4 |   ...   | 11 |






















© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.