Реферат по основам дискретной математики на тему: “Универсальные алгебры”
Содержание
TOC \o "1-1" \h \z \u Понятия моделей и универсальных алгебр
Подалгебры. Системы образующих.
Структура подалгебр универсальной алгебры
Понятия моделей и универсальных алгебр
Пусть А — некоторое непустое множество; {x1, x2, … ,xs, …} — система n-отношений на множестве А (конечная или бесконечная). Каждому n-отношению x на множестве А можно сопоставить n-местную логическую функцию (предикат) p :А®{и,л} так, что p (ai1, ai2, …. ,ain) = тогда и только тогда, когда выполняется n-отношение x (ai1, ai2, … , a in) (и, л —логические значения истины и лжи соответственно; а i1,а i2, … , a in ÎА).
Моделью МA= <A;p> называется система, состоящая из множества А и определенной на данном множестве совокупности предикатов p={ps | s=1,2,…}. Множество А называется основным множеством данной модели; предикаты, принадлежащие p, — её основными или главными предикатами. Последовательность называется типом модели МA, а совокупность p={ps | s=1,2,…} — ее сигнатурой.
Модель МA1= <А1;p¢> (A1 — непустое подмножество множества А) называется подмоделью модели MA= <A;p>. Множество однотипных моделей, т. е. моделей, типы которых совпадают, образует класс моделей по данному типу.
Однотипные модели называются изоморфными, если существует взаимно-однозначное отображение j множества А на множество В такое, что для любого s = 1, 2, ... предикат ps (a1, a2,….,ans) справедлив тогда и только тогда, когда выполняется предикат ss ((a1)j, (a2)j,…., (ans)j) для произвольных a1, a2,….., ans Î A . Отображение в этом случае называется изоморфизмом модели MA на MB.
Рассмотрим модель МA= <A;p>, где каждый n-местный предикат, входящий в p, соответствует функциональному отношению j на множестве А. С каждым таким отношением связана некоторая частично определенная (n-1) местная функция Fj(x1, x2,…,xn-1).
Частично определенная функция Fj (x1,…, xn) называется n-арной частичной операцией на множестве A. Бинарными являются известные арифметические операции над числами (сложение, умножение и др.), а также теоретикo-множественные операции (объединение, пересечение, декартово произведение др.). Унарная (n=1) операция F(x) однозначно сопоставляет каждому элементу aÎA некоторый элемент F(a)ÎA, т.е. является отображением множества А в себя (дополнение). Нульарные (n = 0) операции, каждая из которых фиксирует в основном множестве А некоторый элемент aÎA, не зависящий от других элементов из множества А или от их систем.
Система UA= <A;y>, состоящая из основного множества А и определенной на нем совокупности частичных операций y={Fs (x1,… xns)|s=1,2…}, называется частичной универсальной алгеброй типа (ns|s=1,2…) c сигнатурой операций y={Fs|s=1,2…}. Если каждая из операций, принадлежащих сигнатуре y, всюду определена на множестве А, говорят просто об универсальной алгебре UA= <A;y>.
Как и в модели, сигнатура операций y в частичной универсальной алгебре может быть конечной или бесконечной. Однотипные универсальные алгебры часто рассматриваются как алгебры с одной и той же сигнатурой операций. Пусть UA= <A;y> и UB= <B;y> — однотипные алгебры. Алгебра UA изоморфна алгебре UB,если существует взаимно-однозначное отображение y множества А на В такое, что произвольная m-местная операция удовлетворяет соотношению
[F(a1,a2,…,am)] y=F((a1) y, (a2) y,…,(am) y)
для любого набора элементов (a1,a2,…,am)ÎA. Отображение j в этом случае называется изоморфизмом алгебры UA на алгебру UB.
Примеры универсальных алгебр:
Пример 1. Система <N;{+}>, состоящая из основного множества N всех натуральных чисел с единственной бинарной операцией “+”, образует универсальную алгебру типа 2 с сигнатурой {+}.
Пример 2. Система <N;{´}>, состоящая из основного множества N, на котором определена бинарная операция “´” образует универсальную алгебру типа 2 с сигнатурой {´}.
Пример 3. Система <N;{+,-,´,:}>, состоящая из основного множества N с определенными на нем бинарными арифметическими операциями, образует частичную универсальную алгебру типа (2, 2, 2, 2) с сигнатурой {+,-,´,:}.
Конкатенацией или умножением цепочек s1,s2 Î F(u) называется бинарная операция, которая каждой паре цепочек s1,s2, ставит в соответствие новую цепочку s1s2, полученную в результате приписывания справа к цепочке s1,цепочки s2. Причем пустая цепочка е удовлетворяет соотношению
es=se=s
для любого sÎF(u). Операция конкатенации ассоциативна.
Введение промежуточного языка позволяет сократить число необходимых трансляторов до г+s. В программировании известны два подхода к выделению промежуточного языка при решении проблемы трансляции. 1. Промежуточный язык может быть ориентирован на класс машин. Такой подход применен при создании языка АЛМО. 2. Промежуточный язык может быть ориентирован на класс входных языков. В этом случае он представляет собой параметрическую систему, которая включает в себя ядро, отражающее общие черты класса входных языков, и параметры, отражающие специфику отдельного входного языка из заданного класса .
Пусть {M} — множество машин, каждая из которых характеризуется лишь своим языком LM так, что машины M1 и M2 совпадают, если LM1=LM2. Тогда существуют программы, преобразующие одни машины в другие. Пусть RM — язык машины М. Тогда интерпретатор с языка высокого уровня L, реализованный на машине M, позволяет выполнять на данной машине программы на языке L. Тем самым интерпретатор преобразует машину M в новую машину M¢ с языком LM¢=L. Такого рода программами являются также эмуляторы, моделирующие математическое обеспечение (MО) одной машины на другой .В частности, для автоматизации процесса разработка современных ЭВМ часто используют рабочую машину M1 на которой моделируют систему МО проектируемой машины M2. Машина M1, в таком случае называется инструментальной, а система, моделирующая математическое обеспечение машины M2 — имитатором. Интерпретаторы, эмуляторы и имитаторы можно рассматривать как операции, определенные на множестве машин и принимающие значения в атом же множестве. Применение аппарата универсальных алгебр для формализации процессов программировании позволяет изучать их свойства, соотношения и взаимодействия.
Подалгебры. Системы образующих.
Пусть UA= <A;y> — универсальная алгебра и A1ÍA — некоторое непустое подмножество A. Множество [A1]FÍA называется замыканием множества A1 в алгебре UA по n-местной операции FÎy, если а) A1Í[A1]F; б) для любых элементов q1,q2,…qnÎ[A1]F таких, что значение F(q1,q2,…qn) определено, F(q1,q2,…qn)Î[A1]F, при этом любой элемент из [A1]F порождается в конечном счете из элементов A1 посредством операции F.
Множество [A1]FÍA называется замыканием множества A1, в алгебре UA, если [A1] состоит из всех элементов, которые порождаются из элементов, принадлежащих A1, с помощью основных и производных операции алгебры UA.
Пусть множество A1ÍA замкнуто в алгебре UA. Toгда систему UA1= <A1;y> можно рассматривать как универсальную алгебру. Алгебра UA1= <A1;y> называется подалгеброй универсальной алгебры UA= <A;y>. Примером несобственной подалгебры алгебры является сама эта алгебра.
Пример. Система <N(r); {+}>, где N(r)={n|n³r}ÍN, является подалгеброй алгебры <N; {+}> .
Теорема 3.1. Пусть {UAa|aÎI} — совокупность подалгебр алгебры UA= <A;y>, где AaÍA – замкнутые множества в алгебре UA. Непустое пересечение совокупности {UAa|aÎI} подалгебр алгебры UA также образует подалгебру данной алгебры.
Теорема 3.2. Пусть åÍA — некоторое непустое подмножество множества А. Тогда подалгебра U{å} является пересечением совокупности {UAa|aÎI}.
Теорема 3.3. Пусть UA= <A;y> — конечно-порожденная алгебра. Тогда в любой системе образующих å алгебры UA можно выделить конечную подсистему å¢Íå, которая также порождает алгебру UA.
При изучении системы образующих универсальных алгебр и их подалгебр важное значение имеет установление эффективных критериев, позволяющих определить, является ли некоторая фиксированная система элементов системой образующих данной алгебры (соответственно подалгебры). Сформулированная проблема называется проблемой полноты для данной алгебры (соответственно подалгебры), а ее решение может быть связано с изучением так называемых максимальных подалгебр.
Пусть UA= <A;y> — произвольная универсальная алгебра. Собственная подалгебра AMÌA называется максимальной подалгеброй относительно алгебры UA, если не существует собственной подалгебры A¢ÌA для которой выполнялось бы строгое включение AMÌA. Очевидно, подалгебра AM тогда и только тогда максимальна относительно UA, когда присоединение любого элемента qÎA\AM к подалгебре AM приводит к соотношению [AMÈq].
Подалгебра A¢ÌA универсальной алгебры UA может быть расширена до подалгебры AMÌA, максимальной относительно UA, если AÍAM. Для конечно-порожденных алгебр cправедлива следующая теорема Неймана.
Теорема 3.4. Всякая подалгебра A¢ÌA конечно-порожденной алгебры UA может быть расширена до некоторой подалгебры AM ,максимальной относительно UA.
Теорема 3.5. (критерий Поста). Пусть М — множество всех подалгебр, максимальных относительно конечно-порожденной алгебры UA. Система åÌA тогда и только тогда является системой образующих алгебры UA, когда для каждой подалгебры AMÎM в системе å найдется по крайней мере один элемент, не принадлежащий данной подалгебре.
Необходимость следует на замкнутости множеств AMÎM, а также из строгого включения AMÌA.
Достаточность. Пусть åÌA — система элементов такая, что для каждой максимальной подалгебры AMÎM в системе å существует qkÎAM. Покажем, что å — система образующих алгебры А. Предположим, что система å неполная. Тогда вследствие [å]¹A и вследствие конечной порожденности алгебры А по доказанной выше теореме 3.4 подалгебру [å]ÌA можно расширить до некоторой подалгебры AMsÎM, максимальной относительно алгебры А.
При программировании автоматов (в частности, ЭВМ) систему исходных элементов необходимо выбрать так, чтобы с их помощью можно было реализовать любой автомат данного класса (предполагается, естественно, что любой элемент исходной системы имеется в неограниченном количестве экземпляров). Точно так же при создании алгоритмического языка, ориентированного на некоторый класс алгоритмов, необходимо учитывать, что с помощью основных операторов данного языка должен записываться любой из алгоритмов данного класса .
Структура подалгебр универсальной алгебры
Одной из важных проблем универсальных алгебр является изучение структуры их подалгебр. Особый интерес представляют вопросы, связанные с построением структурного графа подалгебр данной универсальной алгебры. Структурный граф подалгебр универсальной алгебры представляет собой граф, вершинами которого являются подалгебры; вершина Ai соединяется с вершиной Aj дугой или отрезком, если подалгебра Aj максимальна относительно подалгебры Ai; при этом вершина Ai располагается выше вершины Aj. Посту удалось полностью построить структурный граф подалгебр алгебры логики. В частности, им показано, что каждая подалгебра алгебры логики имеет конечную систему образующих и множество всех подалгебр счетно. Множество всех подалгебр k-значных алгебр Поста (k³3) является множеством мощности континуума. Алгебры, множества подалгебр которых являются множествами мощности не менее континуума, называются алгебрами континуального типа. С алгебрами континуального тина часто связано существование бесконечно порожденных подалгебр, имеющих счетный базис.
Система образующих åÍA универсальной алгебры UA= <A;y> называется базисом данной алгебры, если [å\ai]¹A для каждого элемента aiÎå.
Пример. Каждая система å такая , что åÎ1, является системой образующих алгебры <N;{+}>. В то же время алгебра <N;{+}> имеет единственный базис å={1}.
Теорема 3.6. Всякая конечно-порожденная алгебра имеет конечный базис.
Теорема 3.7. Если цепь С плотна и для каждого i найдется конечная система åÍAi+1\Ai такая, что AiÌ[åi], то алгебра А не имеет базиса.
Как показывает следующая теорема, универсальная алгебра является алгеброй континуального типа, если она имеет хотя бы одну подалгебру с бесконечным базисом.
Теорема 3.8. Пусть алгебра UA= <A;y> имеет подалгебру UA, с бесконечным счетным базисом. Тогда мощность множества всех подалгебр алгебры UA не меньше континуальной.
Таким образом, всякая алгебра, имеющая хотя бы одну подалгебру со счетным базисом, является алгеброй континуального типа. К последним, в частности, относятся k-значные алгебры Поста (k³3), а также некоторым их модификации, (связанные с преобразованием на регистрах.
Следствие. Алгебрами континуального типа являются алгебра всех конечных языков и алгебра всех языков над алфавитом n={a1,a2,…,an}.
При изучении структуры подалгебр важно установить критерии бесконечной порожденности, а также существования базиса универсальных алгебр. Универсальная алгебра UA= <A;y> называется плотной, если любая собственная подалгебра A¢ÌA может быть расширена до некоторой подалгебры, максимальной относительно UA, либо если при A=ÈiAi, последовательность A1Ì…ÌAiÌ… образует цепь, отвечающую условию плотности (т. е. для всякой подалгебры A¢ÌA найдется номер n такой, что A¢ÍAn).
Теорема 3.9. Пусть плотная алгебра А' имеет базис. Тогда любая ее собственная подалгебра UA может быть расширена до некоторой подалгебры, максимальной относительно UA.
Из данной теоремы следует, в частности, теорема 3.4. Кроме того, для плотной алгебры справедливы следствия.
Следствие 1. Алгебра UA не имеет базиса, если существует по крайней мере одна собственная подалгебра A¢ÌA не допускающая расширения до подалгебры, максимальной относительно UA.
Следствие 2, Алгебра UA с бесконечным базисом имеет бесконечную совокупность максимальных подалгебр.
Следствие 3. Система åÌA тогда и только тогда является системой образующих алгебры UA, имеющей базис, когда для каждом подалгебры AMÎM в системе å найдется по крайнем мере один элемент, не принадлежащий подалгебре AM (M — множество всех максимальных подалгебр алгебры UM).
Для плотных алгебр с базисом справедлив следующий критерий конечной порожденности.
Теорема 3.10. Пусть UА — плотная алгебра с базисом. Алгебра UA имеет конечный базис тогда и только тогда, когда для множества M={AMi|iÎI}всех подалгебр, максимальных относительно UA, существует конечное разбиение R(I)={I1,I2,…,Ik} такое, что для любого r=1,2,…,k
Ç AMir¹Æ где AM=A\AM.
Подалгебра А алгебры UB=<B;y> называется достижимой сверху в структурном графе подалгебр алгебры UB, если существует но крайней мере одна монотонно убывающая последовательность конечно-порожденных подалгебр A1ÉA2É… такая, что A=ÇiAi, где, и при каждом i=1,2… подалгебра Ai максимальна относительно Ai-1 либо Ai=Ça<iAa. Множество всех достижимых сверху конечно-порожденных подалгебр алгебры UB называется поверхностью этой алгебры.
Подалгебра А называется достижимой снизу в структурном графе подалгебр алгебры UB, если существует монотонно возрастающая последовательность конечно-порожденных подалгебр A1ÌA2Ì… такая, что A=ÈiAi ,где A1 один из минимальных элементов структуры подалгебр алгебры UB, и при каждом i=1,2…, подалгебра Ai максимальна относительно Ai+1 либо Ai=Èa<iAa. Множество всех достижимых снизу конечно-порожденных подалгебр алгебры UB называется основанием данной алгебры.
Если каждая подалгебра UB конечно-порожденная, то поверхность данной алгебры совпадает с ее основанием и полностью представляет структурный граф данной алгебры . Так, поверхность (основание) двузначной алгебры Поста совпадает со всем структурным графом (диаграммой включений) подалгебр данной алгебры. Если алгебра UB имеет бесконечно-порожденные подалгебры, построение поверхности (основания) данной алгебры позволяет изучить ограничивающие эту поверхность (основание) бесконечно порожденные подалгебры.
Пример 6. Рассмотрим структуру подалгебр, входящих в подалгебру O9 — всех одноместных функций и констант двузначной алгебры Поста. Поверхность подалгебры O9 является частью всей поверхности рассматриваемой алгебры и содержит конечное число (9) подалгебр:
O9={0,1,x,x}, O8={0,1,x}, O7={0,1}
O6={0,x}, O5={1,x}, O4={x,x}
O3={0}, O2={1}, O1={x}
Каждая из перечисленных подалгебр, очевидно, конечно-порожденная. Поэтому поверхность подалгебры O9 совпадает с ее основанием и полностью представляет структурный граф подалгебр, входящих в O9 (рис. 1).