Математическая логика использует для записи утверждений и рассуждений с ними формальный (или символический) язык.

Формальный язык начинается с алфавита. Алфавит – это совокупность исходных символов (чаще всего конечная), которые только и могут использоваться в записи утверждений (предложений) языка.

Слова в алфавите – это произвольные конечные последовательности символов алфавита, а предложения или формулы – это осмысленные слова, то есть слова, удовлетворяющие некоторым синтаксическим требованиям (выполнение которых можно эффективно проверить).

Множество всех предложений (формул) формального языка мы будем обозначать через F. Предложения из множества F – это формально записанные утверждения, над которыми, собственно, мы и хотим выполнять рассуждения : из одних утверждений (которые мы предположим верными) выводить (или доказывать) другие (которые тогда тоже окажутся верными). Утверждения (предложения), которые изначально предполагаются верными, называются аксиомами. Чтобы доказывать или выводить из аксиом другие верные предложения, должны быть определены правила вывода :

k - местное правило вывода R представляет собой (k+1)местное отношение между формулами такое, что для любых формул 1, 2, …, k и формулы эффективно решается вопрос о том, находятся ли они в данном отношении или нет – и если да, то называется непосредственным следствием формул 1, 2, …, k по правилу R.

Формальное исчисление считается заданным, если 1) из множества всех формул F выделено подмножество A – множество аксиом исчисления (множество аксиом может быть конечным или бесконечным, но для любой формулы должен эффективно решаться вопрос о том, является ли она аксиомой или нет), 2) определены правила вывода R1, R2, …, Rp (правило Ri предполагается ki -местным, а натуральные числа k1, k2, …, kp могут быть произвольными).

Выводом в исчислении называется всякая последовательность формул 1, 2, …, n такая, что любая ее формула i есть либо аксиома исчисления, либо непосредственное следствие каких-либо предыдущих формул по одному из правил вывода исчисления.

Формула называется теоремой исчисления, если существует вывод в исчислении, в котором последней формулой является. Такой вывод называется выводом (доказательством) формулы.

Пусть – некоторое множество формул, то есть F. Выводом из множества в рассматриваемом исчислении называется всякая последовательность формул такая, что любая ее формула представляет собой либо аксиому, либо элемент множества, либо непосредственное следствие некоторых предыдущих формул по одному из правил вывода исчисления (элементы множества называют при этом гипотезами).

Формула называется следствием множества формул в рассматриваемом исчислении, если в этом исчислении существует вывод из множества гипотез, оканчивающийся формулой (то есть вывод формулы из множества гипотез ). В этом случае говорят, что в исчислении из множества посылок выводится формула, и пишут :

. Если представляет собой конечное множество, состоящее из формул 1, 2, …, n, то вместо можно писать 1, 2, …, n.

Таким образом, запись означает выводимость в исчислении формулы из пустого множества посылок (в этом случае является теоремой исчисления).

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

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

Пропозициональными буквами являются заглавные буквы латинского алфавита и такие же буквы с числовыми индексами, например, Любая конечная последовательность слов алфавита называется словом в этом алфавите. Так, например, словами в описанном алфавите являются :

Из множества всех слов в рассматриваемом алфавите выделяются те, которые называются пропозициональными формулами. Формальное определение пропозициональной формулы содержит три пункта :

(1) всякая пропозициональная буква есть пропозициональная (2) если и – пропозициональные формулы, то ( ), ( & ), ( ), ( ) – тоже пропозициональные формулы;

(3) только те слова в описанном алфавите являются пропозициональными формулами, для которых это следует из пунктов (1) и (2).

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

Из трех слов, рассмотренных в начале параграфа, пропозициональной формулой является только последнее: (( A & B ) C). В силу рассмотренного определения слово A & B C не является пропозициональной формулой потому, что оно не содержит требуемых скобок.

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

1) опускать внешние (окаймляющие) скобки;

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

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

а формулу из § которую без сокращений следует записывать так :

можно записать короче следующим образом :

Последнюю формулу можно записать еще короче ( но менее удобно ) :

классического исчисления высказываний Аксиомами классического исчисления высказываний являются следующие формулы и все их подстановочные примеры :

Каждая из этих десяти формул не только сама является аксиомой, но определяет множество аксиом – множество своих подстановочных примеров. Таким образом, данные формулы это не просто аксиомы – это схемы аксиом.

Единственным правилом вывода классического исчисления высказываний является правило modus ponens :,. Это правило следует понимать так: из формул и непосредственно следует формула (здесь, как обычно, и – это произвольные пропозициональные формулы).

Определение классического исчисления высказываний закончено.

Это определение не является единственно возможным: так, другие аксиоматики этого исчисления (его также называют классическим пропозициональным исчислением) можно найти в книгах [ 3 ] – [ 7 ].

Теперь, опираясь на формальное определение, можно развивать теорию доказательств (и технику доказательства) в классическом исчислении высказываний, выясняя, какие формулы будут теоремами этого исчисления и как их следует доказывать. Первым результатом в этом направлении может служить следующая Лемма. Формула является теоремой классического исчисления высказываний ( какова бы ни была формула ).

В качестве доказательства леммы можно предъявить вывод формулы в классическом исчислении высказываний. Этим выводом является следующая последовательность формул :

Для обозначения выводимости в классическом исчислении высказываний мы будем использовать символ. Таким образом, в силу доказанной леммы для любой формулы можно утверждать, Через,, будем обозначать произвольные пропозициональные формулы, а через – произвольное множество пропозициональных формул. В соответствии с общими определениями из § 7 и § известно, что значит : из множества формул выводится формула. Более удобная запись, 1, 2, …, n заменяет более Доказательство этой теоремы приводится в [ 1 ], здесь же мы обсудим только, как она используется в рамках техники формальных доказательств.

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

Формальный язык, описанный в § 9, можно рассматривать как модель языка естественного, которой явно выделены и формализованы типичные конструкции образования предложений (утверждений) естественного языка. Далее, формальное исчисление с его аксиомами и правилами вывода можно представлять уже как модель тех естественных правил логики, которую использует человек (математик), рассуждая на естественном языке и доказывая одни предложения (утверждения) исходя из других. Сами по себе формальный язык и формальное исчисление – понятия чисто синтаксические. Их основу составляет заданный алфавит – набор вполне определенных знаков. Все предложения (утверждения) формального языка и все доказательства формального исчисления представляют собой в конечном итоге только последовательности этих знаков: предложения – это определенного вида слова в алфавите, а доказательства – это определенного вида конечные последовательности таких слов. Между тем, для естественного языка важно то, что все его синтаксические конструкции осмысленны (предложения естественного языка имеют тот или иной смысл, могут быть истинными или ложными), а это означает, что естественный язык имеет не только синтаксис, но и семантику. Соответственно этому и нашему формальному языку следует сопоставить семантику.

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

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

Теорема о полноте классического исчисления высказываний Для любых пропозициональноц формулы и множества пропозициональных формул выполнено:.

Если в этой теореме в качестве множества взять пустое множество формул, то получится так называемая слабая форма теоремы о полноте, которая утверждает:

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

Теорема о полноте классического исчисления высказываний, по существу, подтверждает то обстоятельство, что аксиомы и правила вывода этого исчисления подобраны правильно. Доказательство этой теоремы можно найти в [ 8 ], доказательство её слабой формы приводится в [ 1 ], здесь же мы рассмотрим только наиболее простую часть последнего доказательства.

Теорема о полноте классического исчисления высказываний в слабой форме может быть разбита на две части:

1) Всякая теорема классического исчисления высказываний является тавтологией ( если, то );

2) Всякая тавтология является теоремой классического исчисления высказываний ( если, то ).

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

Лемма 1. Каждая аксиома классического исчисления высказываний является тавтологией.

То, что все десять формул, определяющие аксиомы классического исчисления высказываний, представляют собой тавтологии, можно непосредственно проверить. В силу леммы 2 а) из § 6 любой подстановочный пример тавтологии также является тавтологией. Таким образом, все аксиомы – это тавтологии, и лемма 1 доказана.

Лемма 2. Если формулы и – тавтологии, то и формула тоже тавтология.

В самом деле, предположим, что формулы и являются тавтологиями, но формула тавтологией не является. Тогда существует оценка v V такая, что (v)=л. Поскольку – это тавтология, то (v)=и. Но тогда формула при оценке v оказывается ложной и потому не может быть тавтологией. Полученное противоречие и доказывает лемму 2.

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

Глава

АЛГЕБРА МНОЖЕСТВ

Символы и отношений принадлежности и включения имеют свой обычный смысл:

x A означает, что элемент x принадлежит множеству A ;

A B означает, что множество A включено в множество B :

(перечеркнутый символ отношения принадлежности или включения означает, что соответствующее отношение не выполнено).

Обычным образом понимаются и схемы образования множеств:

{ x P ( x ) } обозначает множество всех тех элементов x, для которых выполнено условие P ( x ) ; { x X P ( x ) } обозначает множество всех тех принадлежащих множеству X элементов x, для которых выполнено условие P ( x ).

Два множества A и B называются равными, если A B и B A.

Таким образом, равные множества состоят из одних и тех же элементов :

Наряду с отношением включения часто используется также и строгое отношение включения, которое определяется следующим образом :

Множество, которое не содержит ни одного элемента, называется пустым и обозначается символом :

Для произвольных множеств A и B определены их пересечение, объединение, разность и симметрическая разность:

Чаще всего в качестве множеств, над которыми выполняются эти операции, выступают подмножества какого-то одного исходного множества M (это множество в таком случае называют универсальным множеством; даже если это множество изначально не задано, его легко образовать, взяв объединение всех тех множеств, которые участвуют в данном рассмотрении). Если имеется такое исходное множество M, то к описанным операциям может быть добавлена еще одна:

дополнение. Дополнением множества A M называется множество M \ A. Таким образом, к четырем записанным выше строкам можно добавить еще и такую:

Пусть M – произвольное множество. Множество всех его подмножеств обозначается через P ( M ) :

На множестве P ( M ) определены описанные операции: пересечение, объединение, дополнение, разность и симметрическая разность.

Говорят, что P ( M ) вместе с этими операциями представляет собой алгебру подмножеств множества M.

Если множество M представить как множество всех точек, принадлежащих прямоугольнику на плоскости, то рассмотренным операциям будут естественно соответствовать следующие иллюстрации:

использовать в дальнейшем для обозначения Апустого множества наряду с символом также символ 0, а для обозначения универсального множества M – Дополнение A § 13. Универсальные выражения и тождества Пусть выбрано некоторое множество M, объявленное универсальным. Тогда из множеств A, B, C, … (представляющих собой подмножества универсального множества M ) при помощи операций, определенных в предыдущем параграфе, можно получать новые множества, например:

Каждая из этих четырех записей представляет собой выражение.

Символы 0 и 1 в последнем выражении (как и было объявлено в конце предыдущего параграфа) служат обозначениями пустого и универсального множеств. Буквы A, B, C, …, входящие в состав выражений, можно рассматривать как переменные, значениями которых являются множества: если значения переменных зафиксировать, то и каждое выражение также определяет некоторое множество.

Какое множество определяет первое из рассмотренных выражений, очевидно, зависит от того, какие множества сопоставлены его переменным; то же самое можно сказать и о последнем выражении.

Но второе и третье выражения всегда (какие бы множества ни взять для сопоставления его переменным) определяют универсальное множество M. Такие выражения, которые независимо от значений своих переменных (и независимо от того, каково универсальное множество M ) всегда определяют универсальное множество M, мы будем называть универсальными выражениями.

Равенство двух выражений называется тождеством (или тождественно истинным равенством), если при любом выборе универсального множества M и при любых значениях переменных эти выражения определяют равные множества. Так например, равенство A A = A A является тождеством, в то время как равенство A A = A B тождеством не является.

Буквами p, q мы будем обозначать произвольные выражения, и, соответственно, равенство p = q может являться (или не являться) тождеством.

Теорема. Равенство p = q является тождеством в том и только в том случае, когда выражение p q является универсальным.

Доказательство. Из определения операции симметрическая разность легко получить следующее свойство этой операции:

Отсюда и из определения операции дополнение вытекает, что Это соотношение делает утверждение теоремы очевидным.

§ 14. Тождественные преобразования Лемма 1. Следующие равенства представляют собой тождества:

Эти тождества могут быть доказаны исходя непосредственно из определений операций. Рассмотрим, например, доказательство тождества (a16).

Требуется доказать, что для произвольных множеств A, B и для всякого элемента x верно: x A B x A B.

и x B и, следовательно, x A B, а потому снова x A B.

Таким образом, тождество (a16) доказано. Подобным же образом могут быть доказаны и другие тождества из леммы 1. Следует иметь в виду, однако, что более удобный способ устанавливать справедливость подобных тождеств будет описан в § 15.

Тождества (a1) – (a17) из данной леммы естественно сравнить с эквивалентностями (e1) – (e17) из леммы 1, рассмотренной в § 6. Если в тождествах (a1) – (a17) заменить символы операций пересечение, объединение и дополнение на пропозициональные связки конъюнкция, дизъюнкция и отрицание соответственно, а знак равенства заменить знаком эквивалентности, то получатся как раз соотношения (e1) – (e17) (замеченная связь между выражениями и пропозициональными формулами не является случайной, она ещё будет рассматриваться в § 16).

Поскольку эквивалентности (e1) – (e17) использовались в главе 2 для выполнения эквивалентных преобразований над пропозициональными формулами, то естественно найти аналогичное применение и тождествам (a1) – (a17).

Тождественными преобразованиями выражений будем называть преобразования, переводящие выражения в тождественно равные выражения (два выражения тождественно равны, если соответствующее равенство является тождеством). Технику тождественных преобразований выражений можно развивать так же, как и технику эквивалентных преобразований пропозициональных формул. Следующая лемма подобна лемме 3 из § 6.

Лемма 2. Для всякого выражения существует тождественно равное ему выражение, построенное из переменных только при помощи а) операций пересечение и дополнение, б) операций объединение и дополнение, в) операций разность и дополнение, г) универсального множества и операции разность, д) универсального множества и операций пересечение и симметрическая разность, е) универсального множества и операций объединение и симметрическая разность.

Доказательство леммы (подобно рассмотренному в § 6 доказательству леммы 3) можно провести, выражая одни операции через другие. Исходное выражение может содержать все операции, определенные в § 12, а также константы 0, 1 (которые можно трактовать как нульместные операции). Однако некоторые из операций могут быть выражены через другие (и затем при помощи очевидных тождественных преобразований исключены):

а) операции объединение, разность, симметрическая разность и константы 0 и 1 можно выразить через операции пересечение и дополнение при помощи тождеств б) операции пересечение, разность, симметрическая разность и константы 0 и 1 можно выразить через операции объединение и дополнение при помощи тождеств в) операции пересечение, объединение, симметрическая разность и константы 0 и 1 можно выразить через операции разность и дополнение при помощи тождеств г) операции пересечение, объединение, симметрическая разность, дополнение и константу 0 можно выразить через константу 1 и операцию разность при помощи тождеств д) операции объединение, разность, дополнение и константу можно выразить через операции пересечение, симметрическая разность и константу 1 при помощи тождеств е) операции пересечение и разность можно выразить через операции объединение и симметрическая разность при помощи тождеств Эти тождества вместе с тождествами ( j23) – ( j24) доказывают утверждение е). Этим доказательство леммы закончено.

Разницу в свойствах операций разность и симметрическая разность подчеркивает следующая Лемма 3. а) Для любых множеств A, B, C Лемма 3 утверждает, что равенства ( s1) и ( s2) являются тождествами, в то время как подобные равенства, отвечающие соотношениям ( r1) и ( r2), тождествами не являются. Это значит, что операция симметрическая разность обладает свойствами коммутативности и ассоциативности, в то время как операция разность этими свойствами не обладает. В этой связи можно заметить, что для операций пересечение и объединение свойство коммутативности вытекает из тождеств ( a4) и ( a5), а свойство ассоциативности – из тождеств ( a6) и ( a7). Доказать справедливость тождеств ( s1) и ( s2) можно при помощи рассуждений, подобных тем, которые применялись при доказательстве леммы 1 (удобнее, однако, воспользоваться методом, который будет описан ниже в § 33). Доказать же соотношения ( r1) и ( r2) – то есть доказать, что соответствующие равенства опровергаются – можно, указав конкретные множества A, B и C. Так, для соотношения ( r1) подойдут в качестве A пустое множество и в качестве B универсальное множество, а в соотношении ( r2) достаточно каждой переменной сопоставить универсальное множество.

Рассмотрение выражений (которые могут быть универсальными) и равенств (которые могут быть тождествами) может быть переведено на более точный и формальный уровень. Для этого должен быть описан формальный язык алгебры множеств (подобно тому, как в § был описан формальный язык логики высказываний).

Алфавит формального языка алгебры множеств состоит из пяти символов операций алгебры множеств : \, Переменными (которые необходимы для обозначения множеств) являются заглавные буквы латинского алфавита и такие же буквы с числовыми индексами (таким образом, эти переменные выглядят так же, как и пропозициональные переменные, описанные в § 8).

Формальное определение выражения (аналогичное определению пропозициональной формулы из § 8) содержит следующие пункты:

(1) каждый символ - константа есть выражение, (2) всякая переменная есть выражение, (3) если p и q – выражения, то Разумеется, здесь предполагается, что никаких других выражений, кроме определяемых пунктами (1) – (3), в данном формальном языке нет. Следует заметить, что третий пункт этого определения содержит некоторую вольность, поскольку выражение, имеющее черту сверху, формально словом не является. Этой коллизии легко избежать, поставив знак операции дополнение впереди соответствующего выражения, однако мы, следуя определенной традиции, оставим черту сверху. При записи выражений мы будем позволять себе (подобно тому, как мы это делали при записи пропозициональных формул) опускать некоторые скобки из тех, которые очевидным образом восстанавливаются (например, внешние окаймляющие).

Для того, чтобы формально определить равенство выражений, достаточно к алфавиту формального языка добавить символ = и объявить равенством выражений слово p = q.

Для того, чтобы определить семантику описанного формального языка, рассмотрим произвольное множество M и алгебру всех его подмножеств P ( M ). Оценкой v в алгебре подмножеств множества M назовем всякое отображение множества { A, B, С, … } всех переменных языка в множество P ( M ). Таким образом, оценка v ставит в соответствие каждой переменной какое-нибудь подмножество множества M. Множество всех оценок в алгебре подмножеств множества M обозначим через V( M ). Для всякого выражения p и любой оценки vV(M ) естественным образом определено значение p(v) выражения p при оценке v, которое представляет собой элемент множества P ( M ), то есть является подмножеством множества M (это значение вычисляется по правилам, описанным в § 12 и § 13). Таким образом, в соответствии с определениями из предыдущего параграфа выражение p является универсальным M vV(M ) (p(v) = 1);

равенство p = q является тождеством M vV(M ) (p(v) = q(v)).

В соответствии с этими соотношениями для проверки, является ли данное выражение универсальным или является ли данное равенство тождеством, следует перебирать всевозможные множества M, выясняя как ведут себя данные выражение или равенство в соответствующей алгебре P ( M ). Между тем, на самом деле достаточно в качестве M рассмотреть только одно непустое множество (и притом всё равно какое). Лучше всего в качестве M взять множество, состоящее из единственного элемента. Об этом подробно рассказано в главе пособия [ 1 ], здесь же мы рассмотрим без доказательства только одну теорему, которая определяет алгоритм распознавания универсальных выражений и тождеств. Через Mо обозначаем одноэлементное множество.

Теорема. Для любых выражений p и q выполнено а) выражение p является универсальным vV(Mо) (p(v) = 1);

б) равенство p = q является тождеством vV(Mо) (p(v) = q(v)).

Для одноэлементного множества Mо алгебра его подмножеств P (Mо) состоит только из двух элементов 0 (пустое множество) и (само множество Mо). Поэтому, в силу рассмотренной теоремы, чтобы проверить, является ли данное выражение универсальным или является ли данное равенство тождеством, нужно перебрать все ограниченные оценки в алгебре подмножеств множества Mо (которых конечное число). Эта процедура проверки подобна процедуре распознавания тавтологий (применявшейся в главе 1), в основе которой лежит метод истинностных таблиц. При распознавании тавтологий основу всех вычислений составляли таблицы истинности, определяющие смысл основных пропозициональных связок. Точно так же при проверке универсальности выражения или справедливости тождества основу вычислений должны составить следующие таблицы, определяющие действие операций дополнение, пересечение, объединение, разность, и симметрическая разность в самой простой алгебре множеств, содержащей только два элемента 0 и 1 :

Эти таблицы естественно сравнить с таблицами истинности из § 1 (первые три из рассмотренных таблиц превратятся в первые три таблицы из § 1, если A и B заменить на и, и и л заменить на 1 и 0, и, наконец, дополнение, пересечение и объединение заменить на отрицание, конъюнкцию и дизъюнкцию соответственно). Применение таблиц истинности для распознавания тавтологий уже было подробно описано в главе 1, аналогичное применение рассмотренных здесь таблиц позволяет таким же образом распознавать универсальные выражения и тождества.

§ 16. Выражения и пропозициональные формулы Связь между выражениями и пропозициональными формулами, отмеченная еще в § 14, может быть описана более отчетливо. Если сравнить таблицы, рассмотренные в предыдущем параграфе, с таблицами истинности для пропозициональных связок, то станет очевидным следующее соответствие :

симметрическая разность – отрицание эквивалентности.

Далее, имея в виду это принципиальное соответствие, мы определим два формальных перевода : перевод, переводящий выражения в пропозициональные формулы, и перевод, переводящий пропозициональные формулы в выражения. Естественные теоремы об этих переводах и сделают связь между выражениями и пропозициональными формулами ясной и понятной.

Формальный перевод, сопоставляющий каждому выражению q пропозициональную формулу (q), определяется следующим образом:

Пункты этого индуктивного определения следуют пунктам формального определения выражения из § 15. В связи с пунктом 2) данного определения следует иметь в виду, что множества переменных двух формальных языков (языка алгебры множеств и пропозиционального языка) совпадают.

а) Выражение q является универсальным тогда и только тогда, когда пропозициональная формула ( q) является тавтологией.

б) Равенство p = q является тождеством тогда и только тогда, когда пропозициональная формула ( p) ( q) является тавтологией.

Теперь определим формальный перевод, сопоставляющий каждой пропозициональной формуле выражение ( ). Мы будем допускать возможность использования в записи формулы производных пропозициональных связок (ложь), Т (истина) и (эквивалентность). Формальное определение перевода таково :

а) Пропозициональная формула является тавтологией тогда и только тогда, когда выражение ( ) является универсальным.

б) Пропозициональная формула является тавтологией тогда и только тогда, когда равенство ( ) = ( ) является тождеством.

Доказательства теорем 1 и 2 легко получить, сравнив таблицы из § 1 и § 15 (подробно эти доказательства обсуждаются в [ 1 ] ).

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

Глава

БУЛЕВЫ АЛГЕБРЫ

Подобным же образом можно определить k - тую декартову степень множества A :

Операцией на множестве A местности k ( k - местной операцией ) называется всякое отображение f : Ak A, ставящее в соответствие каждому упорядоченному набору (a1, a2, …, ak ) из k элементов множества A снова элемент множества A. Этот элемент обозначается f (a1, a2, …, ak ), а в обозначении самой операции f часто добавляется (в скобках) верхний индекс, указывающий её местность: f ( k ).

Значение индекса k может быть равно единице, в этом случае f является одноместной операцией. Поскольку A1 совпадает с A, то одноместная операция f ( 1 ) представляет собой отображение множества A в множество A. Если значение индекса k равно двум, то соответствующая двуместная (или бинарная) операция f ( 2 ) является отображением множества A2 в множество A.

Операцию f ( k ) можно рассматривать как функцию, зависящую от k аргументов: эти аргументы принимают всевозможные значения из множества A и значениями функции f ( k ) тоже являются элементы множества A. Функция, принимающая всегда одно и то же значение, называется константой. Значение такой функции не зависит от значений каких бы то ни было аргументов, а потому можно считать, что число её аргументов равно нулю. В этой связи естественно допускать в качестве значения индекса k и число ноль. Этому случаю отвечает нульместная операция f ( 0), которая представляет собой константу.

Принято отождествлять эту постоянную функцию f ( 0) с тем единственным значением, которое она принимает. Таким образом, константа f ( 0) – это один элемент, выделенный в множестве A.

Множество A с определёнными на этом множестве операциями f 1 1, f 2( k2 ), …, f n( kn ) называется универсальной алгеброй сигнатуры k1, k2, …, kn. Если обозначить эту алгебру через, то можно записать:

Множество A называется носителем универсальной алгебры.

Часто в тех случаях, когда определённые на множестве A операции известны, обозначение заменяется обозначением A, и, таким образом, универсальная алгебра отождествляется с её носителем. Сигнатура универсальной алгебры указывает, сколько операций и какой именно местности в ней определены. Иногда, задавая сигнатуру, записывают не только значения k1, k2, …, kn, но и символы, обозначающие соответствующие операции.

В математическом обиходе встречается огромное множество примеров универсальных алгебр. Так, множество натуральных чисел с операциями сложение и умножение представляет собой универсальную алгебру сигнатуры 2, 2, множество квадратных матриц порядка n с операциями транспонирование и сложение является универсальной алгеброй сигнатуры 1, 2, множество геометрических векторов с нулевым вектором, сложением и векторным произведением представляет собой универсальную алгебру сигнатуры 0, 2, 2, и так далее. Заметим, что каждом из выше приведённых примеров для записи двуместной операции сложения вместо символа f ( 2 ) используется знак + и результат сложения элементов a и b записывается не в виде f (a, b), а более удобно: a + b. Подобным же образом дело обстоит и с другими примерами универсальных алгебр: для обозначения и записи их операций обыкновенно выбираются наиболее удобные способы (что, разумеется, не меняет дела по существу).

Алгебра подмножеств множества M, введённая в § 12, тоже представляет собой пример универсальной алгебры. В самом деле, если в качестве носителя универсальной алгебры выбрать множество P (M ) всех подмножеств некоторого множества M, то на этом носителе окажутся определены следующие операции, описанные в § 12 (их называют теоретико - множественными операциями): две нульместные операции (константы) 0 и 1, одноместная операция дополнение и четыре двуместные операции – пересечение, объединение, разность \ и симметрическая разность. Таким образом, множество P (M ) с этими операциями представляет собой универсальную алгебру сигнатуры 0, 0, 1, 2, 2, 2, 2. Между тем, среди теоретико - множественных операций удобно выделить как основные следующие три :

дополнение, пересечение и объединение. Как утверждает лемма 2 из § 14, через эти операции могут быть выражены все другие теоретико множественные операции. В этой связи алгебру подмножеств множества M чаще рассматривают как алгебру именно с этими тремя операциями, то есть, как универсальную алгебру сигнатуры 1, 2, 2.

Итак, алгебра подмножеств множества M представляет собой множество P (M ) всех подмножеств множества M с операциями дополнение, пересечение, объединение. Как утверждает лемма 1 из § 15, эти операции обладают свойствами (a1) – (a17).

Пусть имеется произвольное непустое множество A, и пусть на этом множестве каким-либо образом определены одна одноместная и две двуместные операции, которые обозначены теми же символами, что и дополнение, пересечение, объединение. Если эти операции обладают свойствами (a1) – (a17), то множество A вместе с рассматриваемыми операциями называется булевой алгеброй. В совокупности свойств (a1) – (a17) можно выделить ядро, состоящее из соотношений (a4) – (a13), из которого вытекают все остальные свойства данной совокупности. Поэтому булеву алгебру можно определить как множество A вместе с тремя такими определенными на этом множестве операциями, для которых выполнены требования (a4) – (a13). Таким образом, в силу этого определения булевой алгеброй является всякая универсальная алгебра сигнатуры 1, 2, 2, для которой выполнены условия (a4) – (a13). Это означает, что соотношения (a4) – (a13) представляют собой аксиомы булевой алгебры. Выпишем ещё раз эти аксиомы, пронумеровав их заново и обозначая через x, y, z произвольные элементы из множества A:

Хотя не все аксиомы из этого списка независимы (некоторые из них выводятся из остальных), он удобен тем, что отчетливо указывает свойства, которыми должны обладать операции булевой алгебры. Так, аксиомы (b1) и (b2) требуют от операций пересечение и объединение коммутативности, аксиомы (b3) и (b4) – ассоциативности, аксиомы (b5) и (b6) постулируют законы поглощения, а аксиомы (b7) и (b8) – свойства дистрибутивности. Аксиомы (b9) и (b10) не только описывают свойства операции дополнение, но и определяют существование нуля и единицы. В самом деле, из аксиом (b1) и (b9) вытекает, что все элементы вида (y y) равны между собой и потому можно опреy y). Подобным делить единицу булевой алгебры соотношением же образом, из аксиом (b2) и (b10) вытекает, что все элементы вида (y y) также равны между собой и потому можно определить ноль булевой алгебры соотношением единица булевой алгебры оказываются нульместными производными операциями. Ещё две производные операции в булевой алгебре можно определить соотношениями из алгебры множеств:

Другие две производные операции в булевой алгебре можно определить соотношениями из логики высказываний:

Следует отметить, что константы 0 и 1 часто включают в сигнатуру булевой алгебры. Это значит, что булеву алгебру определяют как универсальную алгебру сигнатуры 0, 0, 1, 2, 2, в которой вместе с операциями дополнение, пересечение и объединение заданы ещё и нульместные операции 0 и 1. Аксиомами в этом случае служат соотношения (b1) – (b8) вместе с двумя следующими, заменяющими прежние (b9) и (b10) :

Очевидно, что алгебра подмножеств множества M с носителем P (M ) представляет собой пример булевой алгебры. Это булева алгебра множеств. Наиболее простая булева алгебра – это двухэлементная булева алгебра o, которая может быть представлена как алгебра подмножеств одноэлементного множества Mо. Эта алгебра содержит два элемента: 0 (пустое множество) и 1 (само множество Mо). Как именно определены булевы операции в этой алгебре, можно видеть из таблиц, приведённых в конце § 15. Элементы алгебры o могут быть интерпретированы и как истинностные значения: 1 соответствует значению и (истина), а 0 – значению л (ложь).

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

§ 19. Булева семантика для выражений и тождеств В § 15 был описан формальный язык алгебры множеств. Теперь, изучая произвольные булевы алгебры, мы вполне можем пользоваться этим языком (с поправкой только на обозначение переменных: вместо A, B, C, … мы теперь пишем x, y, z, …).

Напомним, что оценкой в булевой алгебре подмножеств множества M является всякое отображение множества всех переменных в множество P (M ). Множество всех таких оценок было обозначено через V(M ). Оценкой в булевой алгебре назовем всякое отображение множества всех переменных в множество A (носитель булевой алгебры ). Такая оценка сопоставляет каждой переменной определённый элемент булевой алгебры. Множество всех оценок в булевой алгебре обозначим через V( ). Если имеется некоторое выражение p (зависящее от переменных x, y, z, … ) и некоторая оценка v из множества V( ), то очевидным образом может быть вычислено значение p(v) выражения p при оценке v. Это значение будет представлять собой элемент булевой алгебры.

Напомним, что в соответствии с определениями из § выражение p является универсальным M vV(M ) (p(v) = 1), равенство p = q является тождеством M vV(M ) (p(v) = q(v)).

Таким образом, для этих определений важны значения выражений при всевозможных оценках в булевых алгебрах множеств. Между тем, если в соответствующих соотношениях булевы алгебры множеств заменить произвольными булевыми алгебрами, то определения по существу не изменятся – именно это утверждает теорема, рассмотренная ниже (через A в формулировке этой теоремы обозначен класс всех булевых алгебр).

Теорема 1. Для любых выражений p и q выполнено а) выражение p является универсальным A vV( ) (p(v)=1), б) равенство p=q является тождеством A vV( )(p(v)=q(v)).

Доказательство этой теоремы здесь не рассматривается (его можно найти, например, в книге [ 9 ] ). Между тем, для того, чтобы определить, является ли выражение универсальным или является ли равенство двух выражений тождеством, не нужно перебирать все булевы алгебры, но достаточно взять одну, любую из них:

Теорема 2. Для любых выражений p, q и произвольной булевой алгебры выполнено а) выражение p является универсальным vV( ) (p(v) = 1), б) равенство p=q является тождеством vV( ) (p(v) = q(v)).

Эта теорема является следствием предыдущей теоремы 1 и теоремы из § 15, которую мы переформулируем в следующем виде:

Теорема 3. Для любых выражений p и q выполнено а) выражение p является универсальным vV(o ) (p(v) = 1), б) равенство p=q является тождеством vV(o ) (p(v) = q(v)).

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

Отношением на множестве A называется всякое подмножество множества A2 = AA. Таким образом, представляет собой некоторое множество упорядоченных пар (x, y), состоящих из элементов x, y A. В случае, когда (x, y), обычно пишут x y и говорят, что для элементов x и y выполнено отношение.

Строго говоря, определённое таким образом на множестве A отношение является двуместным отношением. Помимо двуместных отношений на множестве A могут быть определены k - местные отношения как подмножества множества Ak (такие отношения фактически уже рассматривались в § 7 при определении правил вывода формального исчисления). Однако, поскольку теперь мы будем иметь дело только с двуместными отношениями, то прилагательное «двуместное» допустимо опускать.

В математическом обиходе встречаются самые разные отношения, однако, наиболее употребительным представляется отношение порядка, которое и рассматривается в настоящем параграфе. С этим отношением связаны привычные обозначения, одно из которых мы и будем использовать: вместо символа будем писать символ и запись x y будем читать « x меньше или равно y ». Перейдём теперь к соответствующим определениям.

Отношение на множестве A называется отношением частичного порядка, если для любых элементов x, y, z A выполнены следующие требования:

Множество A с определённым на этом множестве отношением частичного порядка называется частично упорядоченным множеством.

Соотношения (p1) – (p3) называют аксиомами частичного порядка.

Если к этим трём аксиомам добавить четвёртую то получится список аксиом линейного порядка (соответствующее множество называется линейно упорядоченным).

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

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

Последний пример показывает, что у булевой алгебры подмножеств множества M помимо булевых операций имеется ещё и отношение частичного порядка. Между тем, отношение частичного порядка с аналогичными свойствами может быть определено и для произвольной булевой алгебры следующим образом: для любых элементов x и y алгебры отношение x y считается выполненным в том случае, когда x y = x, то есть Можно проверить, что это отношение для любой булевой алгебры будет отношением частичного порядка (а для двухэлементной булевой алгебры o оно будет также и отношением линейного порядка).

Можно также установить, что Легко видеть, что в булевой алгебре подмножеств множества M так определённое отношение окажется в точности отношением включения.

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

Если булева алгебра имеет носителем множество A, то атомами этой алгебры называются минимальные элементы множества A\{0 }, то есть того множества, которое получается из множества A исключением нуля (частичный порядок на этом множестве очевидным образом сохраняется). Понятие атома булевой алгебры может быть определено и по-другому, при помощи отношения строгого неравенства <.

Для любых элементов x и y произвольного частично упорядоченного множества A положим тогда элемент x булевой алгебры с носителем A, будет её атомом, если Таким образом, атомами булевой алгебры являются те её элементы, меньше которых может быть только ноль этой алгебры. Не всякая булева алгебра имеет атомы. Булева алгебра, имеющая атомы, называется атомной, булева алгебра, не имеющая атомов, называется безатомной. Легко проверить, что булева алгебра всех подмножеств множества M является атомной: атомами этой алгебры служат одноэлементные подмножества множества M.

Пусть B является подмножеством частично упорядоченного множества A. Элемент x A называется нижней гранью множества B, если y B ( x y ), элемент x A называется верхней гранью множества B, если y B ( y x ). Наибольшая нижняя грань множества B называется точной нижней гранью множества B (или инфинумом множества B) и обозначается inf B, наименьшая верхняя грань множества B называется точной верхней гранью множества B (или супремумом множества B) и обозначается sup B. Таким образом, для элемента x множества A Точная нижняя грань (инфинум) множества B может не существовать (множество всех нижних граней множества B может не иметь наибольшего элемента), но если она существует, то единственна. Точная верхняя грань (супремум) множества B может не существовать (множество всех верхних граней множества B может не иметь наименьшего элемента), но если она существует, то единственна.

Частично упорядоченное множество называется решёткой, если каждое его двухэлементное подмножество имеет точную нижнюю и точную верхнюю грани. Для любых двух элементов x и y решётки A элемент inf{x,y} называется их пересечением и обозначается x y, а элемент sup{x,y} называется их объединением и обозначается x y :

Легко проверить, что множество P (M ) всех подмножеств множества M с отношением включения является решёткой, в которой пересечением и объединением оказываются теоретико-множественные пересечение и объединение. Вообще, булева алгебра с отношением порядка, введённым в предыдущем параграфе, является решёткой, в которой пересечением и объединением оказываются соответствующие операции булевой алгебры (соответствующие доказательства можно найти, например, в книге [ 10 ] ).

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

Как видно из сделанных определений, всякая решётка может рассматриваться как универсальная алгебра сигнатуры 2, 2 с двумя бинарными операциями пересечение и объединение. Можно установить, что эти решёточные операции всегда обладают свойствами (b1) – (b6), то есть они коммутативны, ассоциативны и подчиняются законам поглощения. Как показано в [ 10 ] (упражнение 22 и теорема из §1 главы 1) всякая универсальная алгебра сигнатуры 2, 2 с двумя бинарными операциями пересечение и объединение, которые коммутативны, ассоциативны и подчиняются законам поглощения, может быть превращена в решётку введением отношения прядка слеx y = x (или же равносильным ему:

дующим соотношением: x y алгебры (b1) – (b6) представляют собой алгебраические аксиомы решётки. Между тем, последние четыре аксиомы из списка аксиом булевой алгебры не выполняются в произвольной решётке. Аксиомы (b9) и (b10) не выполняются потому, что в произвольной решётке ещё нет операции дополнение. Аксиомы же (b7) и (b8), постулирующие закон дистрибутивности, в некоторых решётках могут выполняться. Такие решётки называются дистрибутивными.

Решётка называется ограниченной, если в ней имеется наименьший элемент (который называется нулём решётки) и наибольший элемент (который называется единицей решётки). Элемент x ограниченной решётки с нулём 0 и единицей 1 называется дополнением элемента x, если x x = 0 и x x = 1. Вообще говоря, для элемента ограниченной решётки может найтись одно или несколько дополнений, но может не найтись и ни одного. Ограниченная решётка, в которой каждый элемент имеет дополнение, называется решёткой с дополнениями. Дистрибутивная решётка с дополнениями называется булевой решёткой.

Поскольку в ограниченной дистрибутивной решётке любой элемент имеет не более одного дополнения (это утверждает лемма 1 из § 6 главы 1 книги [ 10 ] ), то в булевой решётке каждый элемент x имеет единственное дополнение x. Таким образом, в булевой решётке помимо двуместных операций пересечение и объединение определена ещё одна одноместная операция дополнение. Булева решётка, рассматриваемая как множество с определёнными на нём операциями пересечение, объединение и дополнение, представляет собой булеву алгебру в смысле определения из § 18 (легко проверить, что аксиомы булевой алгебры (b1) – (b10) оказываются выполнены). Разумеется, верно и обратное: всякая булева алгебра с отношением порядка, введённым в § 20, является булевой решёткой.

Из всех универсальных алгебр чаще других в математическом обиходе встречаются группы. Группой называется алгебра сигнатуры 0, 2 с константой 0 и бинарной операцией + такими, что для любых её элементов x, y, z выполнено соотношение, определяющее свойство ассоциативности а также следующие условия:

Последнее условие определяет существование обратного элемента: можно установить (см., например, [ 11 ] ), что для всякого элемента x должен существовать единственный элемент y, требуемый соотношением (c3). Этот элемент y называется обратным элементом для элемента x и обозначается через (– x), а производная операция вычитание вводится следующим соотношением:

Следует отметить, что описанная здесь группа является аддитивной потому, что бинарная операция обозначена символом + (и называется сложением), а константа обозначена 0 (и называется нулём).

В классической алгебре чаще рассматриваются мультипликативные группы, в которых вместо сложения используется умножение (обозначаемое точкой), а вместо константы ноль – константа единица (в этом случае аксиомы (c1) – (c3) очевидным образом переписываются в новых обозначениях, обратный элемент для элемента x записывается как x-1, а операция вычитание заменяется операцией деление: x / y = x · y -1 ).

Между тем, аддитивные группы в классической алгебре чаще всего бывают абелевыми, то есть обладают дополнительно свойством коммутативности:

(предполагается, что это соотношение так же, как и соотношение (c1), выполняется для любых элементов группы).

Итак, соотношения (c1) – (c3) являются аксиомами группы, а соотношения (c1) – (c4) – аксиомами абелевой группы. Примеров групп в математике имеется огромное множество. Очевидным примером абелевой группы может служить и множество всех целых чисел, и множество всех рациональных чисел, и множество всех действительных чисел с естественным сложением и нулём.

Рассмотрим универсальную алгебру сигнатуры 0, 0, 2, 2 с двумя константами 0 (ноль) и 1 (единица) и двумя бинарными операциями + (сложение) и · (умножение). Эта алгебра называется коммутативным кольцом, если она удовлетворяет аксиомам (c1) – (c4) (и, таким образом, представляет собой абелеву группу относительно сложения), а кроме того для любых её элементов x, y, z выполнены следующие равенства:

(c5) (x· y)·z = x·(y·z) (ассоциативность умножения), (c7) (x + y)·z = x·z + y·z (закон дистрибутивности), Таким образом, соотношения (c1) – (c8) представляют собой аксиомы коммутативного кольца (заметим, что при определении кольца не обязательно коммутативного последняя аксиома (c8) исключается, однако вместе с этим добавляется ещё один закон дистрибутивности для умножения с другой стороны; иногда также рассматривают неассоциативные кольца; наши определения следуют книге [ 11 ] ).

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

Итак, соотношения (c1) – (c9) представляют собой аксиомы булева кольца. Из них вытекает, что для любого элемента x булева кольца обратным ему (по сложению) является он сам. В самом деле, используя свойства идемпотентности и дистрибутивности, получаем и теперь, прибавляя к обеим частям полученного равенства обратный элемент для x + x (каким бы он ни был), получаем: x + x = 0. Этим же свойством обладает и симметрическая разность булевой алгебры: для всякого элемента x произвольной булевой алгебры выполнено соотношение x x = 0 (напомним, что симметрическая разность была введена как производная операция булевой алгебры в § 18 ).

Последнее наблюдение может быть развито следующим образом:

если в произвольной булевой алгебре симметрическую разность объявить сложением, а пересечение – умножением, то окажется, что для этих сложения и умножения требования (c1) – (c9) будут выполнены и, таким образом, булева алгебра превратится в булево кольцо. С другой стороны, произвольное булево кольцо можно превратить в булеву алгебру, если ввести булевы операции следующими соотношениями: x y x· y, x y x + y + x · y, x 1 + x (аксиомы булевой алгебры (b1) – (b10) для так определённых пересечения, объединения и дополнения действительно окажутся выполненными). Эта естественная связь между булевыми кольцами и булевыми алгебрами утверждается следующей теоремой (её доказательство можно найти в книге [ 12 ] ).

Теорема. а) Если в булевой алгебре определить операции слоxy, то множество элементов этой алгебры вместе с её константами и 1 и введёнными сложением и умножением будет представлять собой булево кольцо.

б) Если в булевом кольце с нулём 0 и единицей 1 определить операции пересечение, объединение и дополнение, соотношениями этого кольца вместе с нулём, единицей и введёнными пересечением, объединением, дополнением будет представлять собой булеву алгебру.

Ещё в § 6 при обсуждении эквивалентностей (e2) – (e17) было отмечено, что они расположены парами так, что каждое соотношение с чётным номером получается из соседнего соотношения с нечётным номером одновременной заменой всех конъюнкций на дизъюнкции и всех дизъюнкций на конъюнкции. Подобным же образом (по отношению к операциям пересечение и объединение) устроены тождества (a2) – (a17) из § 14 и аксиомы булевой алгебры (b1) – (b10) из § 18.

Это наблюдение может быть развито и в конечном итоге оформлено в виде так называемого принципа двойственности. Мы сформулируем здесь этот принцип в двух вариантах – для пропозициональных формул (теорема 1) и для тождеств (теорема 2).

Через и будем обозначать пропозициональные формулы, которые не содержат других пропозициональных связок, кроме следующих:, Т,, &,. Двойственной формулой для формулы будем называть формулу *, полученную одновременной заменой в формуле всех конъюнкций на дизъюнкции, всех дизъюнкций на конъюнкции, всех символов на символы Т и всех символов Т на символы.

Лемма. Если A1, A2, …, An – все пропозициональные переменные формулы, то имеет место следующая эквивалентность Эта лемма (в записи которой использованы обозначения из § 6 ) говорит о том, как проносится связка отрицание через все пропозициональные связки формулы непосредственно до переменных. Она следует из соотношений (e16) и (e17), известных под названием законы де Моргана, и по сути дела представляет собой их обобщение. Из рассмотренной леммы легко вытекает следующее Следствие. Формула является тавтологией тогда и только тогда, когда формула * является противоречием.

Принцип двойственности для пропозициональных формул выражает собой следующая Эта теорема вытекает из рассмотренной выше леммы. В самом деле, если A1, A2, …, An – все пропозициональные переменные формул и (некоторые переменные могут быть фиктивными), то Через p и q будем обозначать выражения, которые не содержат других символов операций, кроме следующих: 0, 1,,,.

Двойственным выражением для выражения p будем называть выражение p*, полученное одновременной заменой в выражении p всех пересечений на объединения, всех объединений на пересечения, всех символов 0 на символы 1 и всех символов 1 на символы 0.

Теорема 2. Равенство p = q является тождеством тогда и только тогда, когда равенство p* = q* является тождеством.

Теорема 2 следует из теоремы 1 и теорем, рассмотренных в § 16.

Тождества в этой теореме можно понимать и как тождества алгебры множеств и как тождества, выполненные в любой булевой алгебре (это следует из теорем § 19). Таким образом, теорема 2 выражает собой принцип двойственности для булевых алгебр (в § 21 булевы алгебры рассматривались как частично упорядоченные множества; распространение принципа двойственности на произвольные частично упорядоченные множества можно найти в книге [ 10 ] ).

B, g1( k1 ), g2( k2 ), …, gn( kn ) сигнатуры k1, k2, …, kn называются изоморфными, если существует взаимно однозначное отображение множества A на множество B такое, что для каждого значения индекса i=1, 2, …, n и любых элементов x1, x2, …, x A выполнено В соответствии с этим общим определением две булевы алгебры A,,, и B,,, изоморфны, если существует взаимно однозначное отображение множества A на множество B такое, что для любых элементов x, y A выполнено Как видно из этих определений, изоморфные алгебры могут отличаться одна от другой по сути дела только обозначением их элементов и операций (а потому такие алгебры часто вообще не различают). Следующая теорема (доказательство которой можно найти в книге [ 10 ] ) предлагает удобное описание конечных булевых алгебр.

Теорема. Всякая конечная булева алгебра изоморфна алгебре всех подмножеств некоторого конечного множества.

Если число элементов конечного множества равно n, то число всех его подмножеств, как известно [ 10 ], составляет 2n. В соответствии с рассмотренной теоремой это значит, что число элементов конечной булевой алгебры всегда представляет собой степень двойки (то есть может быть равно только одному из чисел 2, 4, 8, …, 2n, …).

Элементами булевой алгебры всех подмножеств конечного множества A являются подмножества множества A, то есть элементы множества P (A ). Если A = { a1, a2, …, an }, то каждый элемент B множества P (A ) может быть представлен n-мерным булевым вектором b следующим образом:

(координатами вектора b являются нули и единицы, причём его i-тая координата ei равна единице тогда, когда элемент ai принадлежит подмножеству B, и равна нулю тогда, когда элемент ai подмножеству B не принадлежит).

Таким образом, в силу рассмотренной в настоящем параграфе теоремы, элементы всякой конечной булевой алгебры могут быть представлены в виде n-мерных булевых векторов (размерность n равна логарифму по основанию 2 от числа элементов алгебры). Если координаты этих n-мерных векторов трактовать как координаты точек в n-мерном евклидовом пространстве, то окажется, что эти точки будут вершинами n-мерного куба, ребро которого имеет единичную длину.

Одна из вершин этого куба (соответствующая нулевому вектору) совпадает с началом координат.

Случаю n = 1 отвечает одномерный куб, имеющий единственное ребро и две вершины, соответствующие нулю и единице двухэлементной булевой алгебры (алгебры всех подмножеств множества, состоящего из одного элемента). Эта наиболее простая булева алгебра представлена на рисунке 1.

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

В случае, когда размерность n равна трём, рассматриваемый nмерный куб оказывается обычным трёхмерным кубом, у которого восемь вершин. Именно столько элементов имеет булева алгебра всех подмножеств множества, состоящего из трёх элементов. Эта восьмиэлементная булева алгебра представлена на рисунке 3.

На рисунке 4 показана шестнадцатиэлементная булева алгебра.

Это алгебра всех подмножеств множества, состоящего из четырёх элементов. Размерность n в этом случае равна четырём и потому можно сказать, что на рисунке 4 представлен четырёхмерный куб.

Следует отметить, что на этих рисунках все четыре куба развёрнуты так, чтобы удобнее воспринималось отношение порядка, определённое на представленных ими булевых алгебрах в соответствии с определениями из § 20 ( как отмечено в § 20, это отношение совпадает с отношением включения для соответствующих подмножеств). Так, отношение a b выполнено тогда, когда элементу a отвечает на рисунке вершина, лежащая ниже той, которая соответствует элементу b, причём эти вершины соединены одним или несколькими рёбрами (это условие вообще характерно для диаграмм, изображающих решётки и частично упорядоченные множества).

булева алгебра (трёхмерный куб) Шестнадцатиэлементная булева алгебра (четырёхмерный куб) 1. Шум А. А. Элементы математической логики.

Издательство ТГТУ, 2003.

2. Клини С. К. Математическая логика. М. : Мир, 1973.

3. Колмогоров А. Н., Драгалин А. Г. Введение в математическую логику. Издательство МГУ, 1982.

4. Лавров И. А., Максимова Л. Л. Задачи по теории множеств, математической логике и теории алгорифмов.

М. : Наука, 1984.

5. Марков А. А. Элементы математической логики.

М. : Издательство МГУ, 1984.

6. Мендельсон Э. Введение в математическую логику.

М. : Наука, 1976.

7. Новиков П. С. Элементы математической логики.

М. : Наука, 1973.

8. Шум А. А. Пропозициональные семантические системы // Семиотика и информатика. 1979. № 11. С. 88 - 116.

9. Расева Е., Сикорский Р. Математика метаматематики. М. :

Наука, 1972.

10. Гретцер Г. Общая теория решёток. М. : Мир, 1982.

11. Ленг С. Алгебра. М. : Мир, 1968.

12. Биркгоф Г. Теория решёток. М. : Наука, 1984.

Предисловие ……...………………………………………………………....... Глава 1. Классическая логика высказываний ………………………....... § 1. Высказывания и пропозициональные связки ….………..………… § 2. Пропозициональные формулы ………………………………………. § 3. Тавтологии и противоречия …………………………………………. § 4. Семантическое следование ………………………………………..... § 5. Эквивалентность пропозициональных формул …………………… § 6. Эквивалентные преобразования пропозициональных формул ….. Глава 2. Классическое исчисление высказываний ……………………. § 7. Формальные исчисления ………..……………….…………………... § 8. Формальный язык классического исчисления высказываний …... § 9. Аксиомы и правила вывода классического исчисления высказываний …………………………………………... § 10. Теорема дедукции.…………………………………………………... § 11. Теорема о полноте …………...….………………………………….. Глава 3. Алгебра множеств ……………………………………………… § 12. Операции над множествами ……….………………………………. § 13. Универсальные выражения и тождества …………………………. § 14. Тождественные преобразования выражений..……………………. § 15. Формальный язык и семантика для алгебры множеств ……….. § 16. Выражения и пропозициональные формулы ……….……………. Глава 4. Булевы алгебры ………………………………………………... § 17. Универсальные алгебры ……….…………………………………… § 18. Аксиомы булевой алгебры ………………………………………… § 19. Булева семантика для выражений и тождеств ………………….. § 20. Отношение порядка …………………………………………………. § 21. Булевы решётки ……….…………………………………………….. § 22. Булевы кольца ……….………………………………………………. § 23. Принцип двойственности …………………………………………... § 24. Конечные булевы алгебры …………………………………………. Библиографический список ……………………..………………………….. Содержание ………………………………………………………………… Логика высказываний и булевы алгебры Редактор :

Корректор :

Технический редактор :

Подписано в печать Тверского государственного технического университета,