Булева алгебра
[предыдущая глава]  [оглавление]  [следующая глава]

Будем рассматривать булеву алгебру в той модификации, которая применяется в компьютерной технике. Иногда проводят различия между понятиями "булева алгебра" и "алгебра логики". В данном случае эти различия несущественны. Мы берем алгебру логики, которая является булевой алгеброй. В качестве двух констант будем использовать обозначения true и false. В качестве операций: отрицание "~", конъюнкцию "&", дизъюнкцию "", сложение по модулю двух: "", материальную импликацию "" и равносильность "". Соответствующие таблицы истинности:

xy~xx & yx y x y x yx y
falsefalsetrue falsefalsefalsetrue true
falsetrue  falsetrue true true false
true falsefalse falsetrue true falsefalse
true true  true true falsetrue true

Формулами в данном варианте булевой алгебры будут:

  1. константы true, false;
  2. булевы переменные;
  3. строки вида (Ψ & Ω), (Ψ Ω), (Ψ Ω), (Ψ Ω), (Ψ Ω), ~Ψ, где Ψ и Ω - формулы.

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

Далее для краткости на этот вариант булевой алгебры будем ссылаться как просто на "булеву алгебру", а на формулы, составленные согласно описанным выше правилам 1-3,- как на булевы формулы.

Введем обозначение:

TF = {true, false}

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

Булева алгебра часто используется в качестве интерпертации для разных вариантов классического исчисления высказываний. Для классического исчисления предикатов (и его расширений) в качестве интрепретации применяется некоторое расширение булевой алгебры, в которое добавлены элементы, соответствующие кванторам и предикатам. Одно такое расширение булевой алгебры рассматривается здесь.

Вопрос об аксиоматизации, полноте и непротиворечивости может ставиться по отношению к той дедуктивной системе, для которой булева алгебра (или ее расширение) является интерпретацией.

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