Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

Группоид, число различных группоидов порядка n. Полугруппа, моноид. Примеры.




Операции над множествами: объединение, пересечение, разность, дополнение, декартово произведение. Булеан конечного множества, его порядок.

На подмножествах X и Y некоторого универсума заданы теоретико-множественные операции.

1) Объединение: X È Y ={ x: x Î X или x Î Y }, отсюда max{ï Y ï,ï X ï}£ï X È Y ï£ï Y ï+ï X ï.

2) Пересечение: X Ç Y ={ x: x Î X и x Î Y }, отсюда 0£ï X Ç Y ï£min{ï Y ï,ï X ï}.

3) Разность: X \ Y ={ x: x Î X и x Ï Y }, отсюда 0£ï X \ Y ï£ï X ï.

4) Дополнение множества X (Если Y Í X, то множество X \ Y называют дополнением множества Y до X.): = U \ X, отсюда ï ï=ï U ï-ï X ï.

5) Декартово произведение: X ´ Y ={(x, y): x Î X, y Î Y }, отсюда ï X ´ Y ï=ï X ï×ï Y ï.

Декартовым произведением множеств X 1,…, Xm называется множество наборов {(x 1,…, xm)}, где xi Î Xi, , m Î N. | X 1´…´ Xm |=| X 1|×…×| Xm |.

Система всех подмножеств множества X называется булеаном множества X, обозначается 2 X. Утверждение. Если X есть п -множество, то |2 X |=2 n.

 

Частично упорядоченное множество (ч.у.м.). Прямое произведение ч.у.м. Диаграмма ч.у.м. Сравнимые и несравнимые элементы. Цепи и антицепи. Длина и ширина ч.у.м.

Множество X называется частично упорядоченным, если для любых x, y, z Î X выполнены свойства: 1) рефлексивность (x £ x); 2) антисимметричность (если x £ y, y £ x,то x = y); 3) транзитивность (если x £ y, y £ z,то x £ z);

Прямым произведением ч.у.м. á X, ñ и ч.у.м. á Y, ñ называется ч.у.м. á X ´ Y,£ñ, где (x, y)£(x ¢, y ¢) Û x x ¢ и y y ¢ для любых x, x ¢Î X и y, y ¢Î Y. Если сомножители одинаковы, то имеет место декартова степень ч.у.м.

Конечное ч.у.м. X часто задается диаграммой, представляющей собой специальный неориентированный граф с множеством вершин X, где пара (x, y) соединена ребром Û yx.

Цепь в ч.у.м. á X,£ñ - это подмножество С множества X, обладающее свойством линейности. Элементы x, y ч.у.м. X называются сравнимыми, если они принадлежат некоторой цепи, и несравнимыми в противном случае. Антицепь в ч.у.м. á X,£ñ - это подмножество множества X, любые два различных элемента которого несравнимы.

Длина ч.у.м. X (обозначим её l (X)) определяется как длина самой длинной из цепей множества X,то есть l (X)= n, если в X найдётся цепь длины n и не найдётся цепи длины n +1.

Ширина ч.у.м. X (обозначим её h (X)) определяется как мощность самой мощной из антицепей множества X, то есть h (X)= п, если в X найдётся антицепь, состоящая из n элементов и не найдётся антицепи, состоящей из n +1 элементов.

 

Определение sup(x,y) и inf(x,y) для элементов x,y ч.у.м. Решетки. Порядок и длина решетки D(n). Порядок, длина и ширина решётки двоичных n-мерных векторов. Бинарное отношение покрытия на ч.у.м. Атомы и коатомы решетки, максимальные и минимальные элементы ч.у.м.

Нижняя (верхняя) граница x множества Y называется его нижней (верхней) гранью, если z £ x (x £ z) для любой нижней (верхней) границы z множества Y. При этом обозначается: x =inf Y (x =sup Y).

Ч.у.м. X называется нижней полурешёткой или Ù- полурешёткой, если x Ù y Î X для всех x, y Î X. Ч.у.м. X называется верхней полурешёткой или Ú- полурешёткой, если x Ú y Î X для всех x, y Î X. Если X есть Ù-полурешётка (Ú-полурешётка), то inf(x, y) (sup(x, y)) есть функция X 2® X.

Ч.у.м. X называется решёткой, если X является и нижней, и верхней полурешёткой.

На множестве D (n) натуральных делителей числа n отношение делимости индуцирует частичный порядок. Пусть ×...× - каноническое разложение натурального числа n, где 1£ k 1£…£ ks. При s =1 множество D (n) есть цепь длины k 1. ï D (n))ï= ; l (D (n))= k 1+...+ ks

Порядок 2^n

Ширина С из n по [n/2]

Длина – длина самой длинной цепи

Система множеств { X 1,…, Xk } называется покрытием множества X, если X = X 1È È Xk.

Атомом нижней (коатомом верхней) полурешётки X называют всякий элемент x со свойством x0 X (1 Xx).

Решётка á Vn,£ñ разбивается на b (п) цепей, где x n (n -2 p)= - , 0£ p £ë n /2û и минимальный (максимальный) элемент цепи есть вектор веса p (веса n - p).

 

4. Булева функция, ее таблица. Число всех булевых функций от n переменных. Вес булевой функции. Теорема о разложении булевой функции по переменным. Многочлен Жегалкина булевой функции, его степень.

x 1 xn -1 xn f (x 1,… xn -1, xn)
      f (0,…0,0)
      f (0,…0,1)
      f (0,…1,0)
      f (0,…1,1)
      f (1,…1,1)

Функцией алгебры логики или булевой функцией (б.ф.) называется функция f (x 1,…, xn), аргументы которой определены на множестве V 1= E 2={0,1}, i =1,…, n, и значения функция f принимает также во множестве V 1, n Î N. Таким образом, б.ф. f (x 1,…, xn): Vn ® V 1.

Число различных наборов равно 2 n. Число различных столбцов значений функции равно .

ç P 2(n)ç= .

Порядок множества If называется весом б.ф. f (обозначается , кратко ).

Теорема (о разложении функции по переменным). Для каждой f (x 1,…, xnP 2 при любом m =1,…, n справедливо представление: f (x 1,…, xn)= × f (s1,…,s т, xт +1,…, xn).

t Покажем, что левая и правая части равенства принимают равные значения при любом наборе значений переменных (a1,…,a n). Левая часть равна f (a1,…,a n), правая равна × f (s1,…,s т,a т +1,…,a n). Так как Û a i= s i, i =1,…, m, то слагаемое, соответствующее набору (s1,…,s т)=(a1,…,a т), равно f (a1,…,a n), а остальные слагаемые равны 0. u

Теорема (И.И. Жегалкин). Каждая б.ф. однозначно представима многочленом по mod2: f (x 1,…, xn) = , Так как число таких многочленов от переменных совпадает с числом различных б.ф., то представление функции полиномом единственно. w

Представление б.ф. называется алгебраической нормальной формой (АНФ) или многочленом Жегалкина.

 

Группоид, число различных группоидов порядка n. Полугруппа, моноид. Примеры.

Множество G с одной внутренней бинарной операцией * называется группоидом,обозначается (G;*). Число различных группоидов порядка n = n^n^2. Группоид (G;*) с заданной на нём ассоциативной операцией * называется полугруппой. (Множество натуральных чисел является полугруппой, так как операция сложения на ассоциативна.) Полугруппу с единичным элементом называют моноидом (или полугруппой с единицей). (N - множество натуральных чисел относительно умножения; множество Z целых чисел относительно умножения.).

Элемент е Î G называется нейтральным или единичным относительно операции *, если g * е = е * g = g для любого элемента g Î G.

 

Поделиться:





Воспользуйтесь поиском по сайту:



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...