Выведенная булева алгебра - Residuated Boolean algebra

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

Определение

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 2 , и сделал моноид с реляционной композицией. Единицей моноида 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

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

Converse

В примерах 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 ˘.

использованная литература