Полукольца и булевы алгебры

Теория

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

  • Полукольца. Основные примеры

    Определение 3.1. Полукольцо — это алгебра с двумя бинарными и двумя нульарными операциями S = (S,+,⋅,0, 1), такая, что для произвольных элементов а, b, с множества S выполняются следующие равенства, называемые аксиомами полукольца:Подробнее
  • Замкнутые полукольца

    При изучении колец большое внимание было уделено полям. Связано это прежде всего с тем, что в полях разработана техника решения систем линейных уравнений. Оказывается, можно выделить специальный класс идемпотентных полуколец, в которых также удается находить решения систем уравнений, рассматриваемых в качестве аналогов систем линейных алгебраических уравнений [III].Подробнее
  • Решение систем линейных уравнений

    Операции сложения и умножения матриц определяют точно так же, как и в числовом случае [III], — с учетом того, что сложение и умножение элементов матриц понимаются в смысле данного идемпотентного полукольца S, а именно: 1) суммой матриц А = (аij) и В = (bij) типа m×n называют матрицу С = (cij) того же типа с элементами сij = aij + bij, i = 1, m, j = 1,n, и используют обозначение С = А + В; Подробнее
  • Булевы алгебры

    Теория булевых алгебр является классическим разделом дискретной математики. Булевы алгебры возникли в трудах английского математика Дж. Буля в 50-х годах XIX века как аппарат логики. При этом элементы булевой алгебры трактовались как высказывания, а операциями являлись дизъюнкция, конъюнкция и отрицание.Подробнее
  • Решетки

    Напомним, что полурешеткой называют полугруппу, операция которой коммутативна и идемпотентна. Таким образом, полурешетка — это алгебра L = (L, V), в которой для любых a, b, c ∈ L выполнены равенстваПодробнее
  • Вопросы и задачи

    3.1. Проверив аксиомы, убедиться, что алгебры, приведенные в примере 3.3, являются полукольцами.Подробнее