Остаточная булева алгебра

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

Определение

Остаточная булева алгебра — это алгебраическая структура $( L , ∧, ∨, ¬, 0, 1, •, I , \, /)$ такая, что

$( L , ∧, ∨, •, I , \, /)$ — остаточная решетка и
$(L, \land, \lor, \neg, 0, 1)$ — булева алгебра.

Эквивалентная сигнатура, лучше подходящая для в реляционной алгебре, применения $— это (L, \land, \lor, \neg, 0, 1, •, I, ▷, ◁)$ , где унарные операции x \ и x ▷ взаимопереводимы в духе законов Де Моргана. с помощью

x \ y = ¬( x ▷¬ y ), x ▷ y = ¬( x \¬ y ),

и двойственно / y и ◁ y как

x / y = ¬(¬ x ◁ y ), x ◁ y = ¬(¬ x / y ),

с аксиомами остатка в оставшейся статье решетки, реорганизованными соответствующим образом (заменив z на ¬ z ), чтобы читать

(x ▷ z)\land y = 0

⇔

(x • y)\land z = 0

⇔

(z ◁ y)\land x = 0

Эта двойная переформулировка Де Моргана мотивирована и более подробно обсуждается в разделе о сопряженности ниже.

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

Примеры

Любая булева алгебра, в которой моноидное умножение • рассматривается как конъюнкция, а обе остатки считаются материальной импликацией x → y . Из оставшихся 15 двоичных логических операций, которые можно рассматривать вместо конъюнкции при умножении моноида, только пять соответствуют требованию монотонности, а именно 0, 1, x , y и $x \lor y$ . Полагая y = z = 0 в аксиоме вычета y ≤ x \ z ⇔ x • y ≤ z , мы имеем 0 ≤ x \0 ⇔ x •0 ≤ 0, что опровергается принятием x = 1, когда x • y = 1 , Икс или $Икс \lor y$ . Двойной аргумент для z / y исключает x • y = y . Это просто оставляет x • y = 0 (постоянная бинарная операция, независимая от x и y ), что удовлетворяет почти всем аксиомам, когда оба остатка считаются постоянной операцией x / y = x \ y = 1. Аксиома это терпит неудачу: $x • I = x = I • x$ из-за отсутствия подходящего значения для $I$ . Следовательно, конъюнкция - единственная бинарная булева операция, делающая умножение моноида результирующей булевой алгеброй.
Силовой набор 2 ^{Х ²} сделал булеву алгебру, как обычно, с ∩, ∪ и дополнением относительно X ²и сделал моноид с реляционной композицией. Моноидная единица $I$ — это тождественное отношение {( x , x )| х € Икс }. Правая невязка R \ S определяется как x ( R \ S ) y тогда и только тогда, когда для всех z в X zRx из следует zSy . Двойственным образом левый остаток S / R определяется как y ( S / R ) x тогда и только тогда, когда для всех z в X xRz из следует ySz .
Силовой набор 2 ^С* сделал булевую алгебру, как в примере 2, но с языковой конкатенацией для моноида. Здесь набор Σ используется в качестве алфавита, а Σ* обозначает набор всех конечных (включая пустые) слов в этом алфавите. Конкатенация LM языков L и M состоит из всех слов uv таких, u ∈ L и v ∈ M. что Моноидной единицей является язык {ε}, состоящий только из пустого слова ε. Правая невязка M \ L состоит из всех слов w над Σ таких, что Mw ⊆ L . Левый остаток L / M такой же, как и wM вместо Mw .

Сопряжение

Дуальные де Моргана ▷ и ◁ неостатка возникают следующим образом. Среди результирующих решеток булевы алгебры являются особенными благодаря наличию операции дополнения ¬. Это позволяет альтернативное выражение трех неравенств

y ≤ x \ z ⇔ x • y ≤ z ⇔ x ≤ z / y

в аксиоматизации двух остатков с точки зрения дизъюнктивности посредством эквивалентности x ≤ y ⇔ x ∧¬ y = 0. Сокращение x ∧ y = 0 до x # y в качестве выражения их непересекаемости и замена ¬ z вместо z в аксиомы, они становятся после небольшой логической манипуляции

¬( x \¬ z ) # y ⇔ x • y # z ⇔ ¬(¬ z / y ) # x

Теперь ¬( x \¬ z ) напоминает двойственность Де Моргана , предполагая, что x \ можно рассматривать как унарную операцию f , определяемую формулой f (y) = x \ y , которая имеет двойственную по Де Моргану ¬ f (¬ y ), аналогично ∀ x φ( x ) = ¬∃ x ¬φ( x ). Обозначая эту двойственную операцию как x ▷, мы определяем x ▷ z как ¬( x \¬ z ). Аналогично мы определяем другую операцию z ◁ y как ¬(¬ z / y ). По аналогии с x \ как остаточной операцией, связанной с операцией x •, мы будем называть x ▷ сопряженной операцией или просто сопряженной операцией x •. Аналогично ◁ y сопряжено с • y . В отличие от остатков, сопряженность представляет собой отношение эквивалентности между операциями: если f является сопряженным с g , то g также является сопряженным с f , т. е. сопряженным с сопряженным с f является f . Другое преимущество сопряжения состоит в том, что становится ненужным говорить о правом и левом сопряжении, поскольку это различие теперь унаследовано от разницы между x • и • x , которые имеют в качестве соответствующих сопряженных x ▷ и ◁ x . (Но это преимущество распространяется и на остатки, когда x \ считается остаточной операцией для x •.)

Все это дает (наряду с аксиомами булевой алгебры и моноида) следующую эквивалентную аксиоматизацию резидуированной булевой алгебры.

y # x ▷ z ⇔ x • y # z ⇔ x # z ◁ y

С этой сигнатурой остается случай, когда эту аксиоматизацию можно выразить в виде конечного числа уравнений.

Конверсы

В примерах 2 и 3 можно показать, что $x ▷ I = I ◁ x$ . В примере 2 обе части равны обратному x ˘ к x , тогда как в примере 3 обе стороны равны $I,$ когда x содержит пустое слово, и 0 в противном случае. В первом случае x ˘ = x . Для последнего это невозможно, поскольку $x ▷ I$ почти не сохраняет никакой информации о x . Следовательно, в примере 2 мы можем заменить x ˘ на x в $x ▷ I = x ˘ = I ◁ x$ и сократить (разумно), чтобы получить

Икс ˘▷ я знак равно Икс знак равно я ◁ Икс ˘

.

x ˘˘ = x можно доказать из этих двух уравнений. алгебры Понятие Тарского отношений можно определить как результирующую булеву алгебру, имеющую операцию x ˘, удовлетворяющую этим двум уравнениям.

Шаг отмены, описанный выше, невозможен для примера 3, который, следовательно, не является алгеброй отношений, поскольку x ˘ однозначно определяется как $x ▷ I$ .

Следствия этой аксиоматизации обратного включают x ˘˘ = x , ¬( x ˘) = (¬ x )˘, $(x \lor y)˘ = x ˘ \lor y ˘$ и ( x • y )˘ = y ˘• x ˘.

Ссылки

Бьярни Йонссон и Константин Цинакис, Алгебры отношений как результирующие булевы алгебры , Algebra Universalis, 30 (1993) 469-478.
Питер Джипсен, Компьютерные исследования алгебр отношений , доктор философии. Диссертация, Университет Вандербильта, май 1992 г.