Выведенная булева алгебра

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

• 1 Определение
• 2 Примеры
• 3 Спряжение
• 4 кеды
• 5 ссылки

Residuated Булева алгебра является алгебраической структурой ( L, ∧, ∨, ¬, 0, 1, •, я, \, /) таким образом, что

1. ( L, ∧, ∨, •, I, \, /) решетка с делениями и
2. ( L, ∧, ∨, ¬, 0, 1) - булева алгебра.

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

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

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

х / у = ¬ (¬ х ◁ у),   х ◁ у = ¬ (¬ х / у),

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

( x ▷ z) ∧ y = 0 ⇔ ( x • y) ∧ z = 0 ⇔ ( z ◁ y) ∧ x = 0

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

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

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

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

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

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

¬ ( 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). По аналогии с й \ в качестве остаточной операции, связанной с операцией х • мы ссылаемся х ▷ как операция сопряженной, или просто сопряжено, из й •. Точно так же ◁ y является сопряженным с • y. В отличие от остатков, сопряжение - это отношение эквивалентности между операциями: если f является сопряженным с g, то g также сопряжено с f, т. Е. Сопряжение сопряженного с f является f. Другое преимущество сопряжения состоит в том, что становится ненужным говорить о правых и левых сопряжениях, это различие теперь унаследовано от разницы между x • и • x, которые имеют в качестве соответствующих сопряженных x ▷ и ◁ x. (Но это преимущество распространяется также на остатки, когда х \ принимается как остаточная операция для х •.)

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

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

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

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

х ˘ ▷ I = х = я ◁ х ˘.

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

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

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

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