Реферат по основам дискретной математики на тему: “Универсальные алгебры”
Содержание
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).
Рис. – 1
Функции алгебры логики
В настоящем параграфе рассмотрены элементы теории булевых функций или функций алгебры логики, используемые при проектировании ЭВМ и программировании.
Рассмотрим всюду определенные булевы функции, т. е. функции, принимающие значение 1 или 0 на каждом из своих двоичных наборов. Поскольку каждая переменная может принимать лишь, два значения, любая булева функция имеет конечную область определения.
Область определения n-местной булевой функции состоит из наборов значений переменных. Конечность области определения и области значения произвольной булевой функции позволяет задавать функцию с помощью таблиц истинности. Двоичные наборы значений переменных записываются как некоторые целые числа в двоичной системе счисления. Набор a=(a1,a2,…,an) отождествляется с записью числа
a1×2 +a2×2 +…+an-1×2+an
Это число называется номером соответствующего набора.
Номера наборов n-местной булевой функции изменяются от нуля до 2 – 1. Расположив наборы в столбец в порядке роста их номеров и указав значения функции на каждом наборе, получим таблицу истинности булевой функции (табл. 1).
Булевыми функциями являются логические операции: дизъюнкция, конъюнкция, отрицание. К другим известным булевым функциям относятся импликация, эквивалентность, сложение, обратная импликация, прямая антиимпликация, обратная антиимпликация, штрих Шеффера, стрелка Пирса.
Эти функции определены в таблице 2.
В связи с тем что на каждом наборе булева функция может принимать одно из двух значений (1 или 0), независимо от значений, которые она принимает на остальных наборах, существуют 2 различных n-местных булевых функций.
Таблицы истинности булевых функций с ростом числа аргументов становятся громоздкими и неудобными. Более удобный аналитический способ задания булевых функций основан на рассмотрении алгебры ФЕ2, с операцией суперпозиции над множеством булевых функций — двузначной алгебры Поста. Зафиксировав в качестве системы образующих алгебры булевый набор операций произвольную булеву функцию можно представить как суперпозицию этих булевых операций.
Одной из интересных систем образующих алгебры ФЕ2, является набор Жегалкина (Å,×,1). Операции Å и × ассоциативны и коммутативны, кроме того, для Å выполняются следующие соотношения:
x×(yÅz)=x×yÅx×z
xÅx=0
xÅ0=x
Двойственным образом заменяя в приведенных определениях нули единицами и наоборот, дизъюнкции — конъюнкциями и наоборот, определяем понятия элементарной дизъюнкции, конституанты 0, конъюнктивной нормальной формы (к .н. ф.), совершенной конъюнктивной нормальном формы (с. к. н. ф.).
Теорема 3.11. Всякая булева функция f(x1,x2,…,xn)¹0 может быть однозначно представима в совершенной дизъюнктивной нормальной форме.
Следствие. Любая функция может быть представлена в виде суперпозиции булевых операций.
Пример. Построим с. д. н. ф. функции f(x,y,z), заданной таблицей истинности (табл. 3).
Конституанты 1, соответствующие наборам, на которых данная функция обращается в единицу, имеют вид xyz, xyz, xyz, xyz. Таким образом
f(x,y,z)=xyzVxyzVxyzVxyz
Отметим, что произвольная функция может быть представлена в классе д. п. ф. различными способами. Так, для приведенного выше примера наряду с выше приведённым равенством выполняется также равенство
f(x,y,z)=xyVxzVyz
Поэтому в результате применения теории булевых функций при синтезе комбинационных схем возникла проблема нахождения минимальной по числу букв д. н. ф. для произвольной булевой функции (проблема минимизации).
Теорема 3.12. Каждая булева функция может быть представлена в форме полинома Жегалкина.
Системы образующих алгебры ФЕ2, называются функционально полными системами. В частности, функционально полными являются рассмотренные выше булева система операции и базис Жегалкина.
Заметим, что система {V,×,-} не является базисом в алгебре ФЕ2. Действительно ввиду того ,что
xVy=xy,
xy=xVy
из булевой системы операций можно исключить дизъюнкции или конъюнкции так, что системы {V,-} и {×,-} также будут функционально полными.
Таким образом алгебра ФЕ2, конечно-порожденная и на основании теоремы 3.5 для нее справедлив критерий Поста, обеспечивающий необходимые и достаточные уcловия при которых произвольная система åÌ ФЕ2, является системой образующих данной алгебры.
Булевой функцией, сохраняющей константу 0, называется функция f(x1,x2,…,xn) такая, что f(0,0,…,0)=0. Например, сохраняют константу 0 дизъюнкция и конъюнкция, а отрицание и импликация не сохраняют ее (см. табл. 2).
Булевой функцией, сохраняющей константу 1, называется функция f(x1,x2,…,xn) такая, что f(1,1,…,1)=1. Coхpaняют константу 1, например, конъюнкция, дизъюнкции, тогда как отрицание и сумма, не сохраняют ее (см. табл. 2).
Функция f(x1,x2,…,xn) называется самодвойственной, если f(x1,x2,…,xn)= f(x1,x2,…,xn). Примерами самодвойственных функций являются отрицание (все остальные функции, заданные табл. 2, не самодвойственны) и функция f(x,y,z) (см. табл. 3).
Теорема 3.13 (Критерий функциональной полноты). Система функционально полна тогда и только тогда, когда содержит
-хотя бы одну функцию, не сохраняющую константу 0,
-хотя бы одну функцию, не сохраняющую константу 1,
-хотя бы одну несамодвойственную функцию,
-хотя бы одну немонотонную функцию.
-хотя бы одну нелинейную функцию.
Необходимость следует из того, что каждый из классов в пяти перечисленных условиях образует собственную подалгебру алгебры ФЕ2.
Следствие (ослабленная теорема о функциональной полноте). Для полноты системы булевых функций, включающей константы 0 и 1, необходимо и достаточно, чтобы эта система содержала:
-хотя бы одну немонотонную функцию,
-хотя бы одну нелинейную функцию.
В частности, из доказанной теоремы следует, что алгебра ФЕ2, имеет базисы, состоящие из одной функции. Примерами таких базисов служат штрих Шеффера и стрелка Пирса (см. табл. 2).
Как подчеркивалось, удалось не только описать множество всех максимальных подалгебр алгебры логики, но и построить поверхность, которая включает псе подалгебры данной алгебры.
Литература