Введение в анализ, синтез и моделирование систем




Функционирование и развитие системы - часть 10


  1. коммутативности - х+у = у+х, ху = ух;
  2. ассоциативности - (х+у)+z = х+(у+z), (xy)z = x(yz);
  3. идемпотентности - х+х = х, xx = x;
  4. дистрибутивности - (x+y)z = xz+yz, xy+z = (x+z)(y+z);
  5. инволюции (двойной инверсии) -
    ;
  6. поглощения - x(x+y) = x, x+xy = x;
  7. де Моргана - x+y = xy, xy = x+y
  8. нейтральности: x(y+y) = x, x+yy = x.
  9. существования двух особых элементов (называемых "единица -1" и "нуль-0"), причем 0 = 1, 1 = 0, x+x = 1, xx = 0.

Группоид - алгебра A=<X, f> с одной двухместной операцией f.

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

Пример. Пусть Х={x1, x2, ..., xn} - некоторый алфавит. Тогда он образует полугруппу относительно операции конкатенации слов из S(X). В таких (называемых свободными) полугруппах рассматривается одна из важнейших алгебраических проблем информатики в полугруппах - проблема тождества слов: указать конструктивный процесс установления совпадения двух слов из полугруппы S(X). Эта проблема алгоритмически неразрешима и встречается, например, при разработке архитектуры процессора.

Группа - полугруппа с единицей (с элементом е: еа=ае=а), в которой бинарная операция f является однозначно обратимой, т.е. на этом множестве (на его носителе) разрешимы однозначно уравнения вида xfa=b, afx=b.

Пример. Пусть Х={x1, x2, ..., xn} - некоторая свободная полугруппа. Каждому из хi, i=1, 2,..., n сопоставим его обратный элемент xi-1, а единицу положим равной пустому слову

. Тогда Х образует (свободную) группу, если в качестве критерия разрешимости уравнений выбрать соотношения: xixi-1=
, xi-1xi=
. Одна из важнейших алгебраических проблем информатики в группах - проблема изоморфизма (преобразования с сохранением групповой операции) двух групп: указать конструктивный процесс установления такого преобразования одной группы к другой. Эта проблема возникает при обработке информации, преобразовании одной информационной системы к другой с сохранением информации.

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




Содержание  Назад  Вперед