Дискретка

x 1. Введение

1. Высказывания. В этом параграфе мы, не заботясь о строгости

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

Приведем несколько примеров высказываний.

(1)2 2 = 4.

(2)Волга впадает в Каспийское море.

(3)Наполеон умер 5 мая 1821 года.

(4)Третье тысячелетие началось 1 января 2000 года.

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

(6)Среди первых 10100 цифр десятичного разложения числа e+ встретятся подряд 1089 нулей.

Высказывания (1)-(3) истинны, высказывания (4) и (5) ложны. Что касается высказывания (6), то мы не знаем, и вряд ли когда сможем узнать, истинно оно или ложно; тем не менее, это высказывание, потому что оно или выполняется, или нет, независимо от того, знаем ли мы правильный ответ.

Будем обозначать высказывания большими латинскими буквами,0 и т.д. Пусть нам дан неко-

возможно, с индексами: A, B, C, Di, A

торый набор высказываний, которые мы будем называть простыми высказываниями. Из них можно составлять новые высказывания при помощи нескольких элементарных конструкций. Например, если A и B простые высказывания, то мы можем составить вы-

сказывания "A и B", "A или B", "или A; или B", "из A следует B", "A; B эквивалентны", "не B". Хотя смысл этих новых высказываний

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

Высказывание "A и B" называется конъюнкцией высказываний A и B; оно означает, что одновременно выполняются и A, и B. Для конъюнкции высказываний A и B используется обозначение A&B или ^. Высказывание A&B истинно тогда и только тогда, когда истинны оба высказывания A и B; если хотя бы одно из высказываний A, B ложно, то и их конъюнкция A&B ложна.

1

Высказывание "A или B" означает, что выполняется хотя бы одно из высказываний A, B. Подчеркнем, что могут выполняться и оба

высказывания; в разговорном русском языке слово "или" иногда понимается в том смысле, что должно выполняться в точности одно из высказываний. Обозначается высказывание " A или B" через A _ B

и называется дизъюнкцией A и B. Дизъюнкция A _ B истинна, если истинно хотя бы одно из высказываний A, B; она является ложной только в том случае, когда ложны оба высказывания A, B. Еще раз

подчеркнем разницу между дизъюнкцией и так называемой разделительной дизъюнкцией "или A; или B", которая является истинной

тогда, когда истинно в точности одно из высказываний A, B. Точный смысл высказывания "не A" совпадает с общепринятым:

оно истинно, если A ложно, и оно ложно, если A истинно. Это высказывание называется отрицанием высказывания A и обозначается

:A.

Смысл высказывания "A; B эквивалентны" тоже совпадает с общепринятым: оно истинно, если оба высказывания A, B одновремен-

но истинны или одновременно ложны, и оно ложно, если одно из высказываний A, B истинно, а другое ложно. Это высказывание на-

зывается эквивалентностью и обозначается A $ B.

Наконец, высказывание "из A следует B", называемое импликацией и записываемое в виде A ! B, считается ложным только если A истинно, а B ложно. Таким образом, из ложной посылки следует

все, что угодно, а из истинной посылки следуют только истинные высказывания. В обыденной речи мы не всегда понимаем следование именно в таком смысле, поэтому приведенное выше уточнение понятия импликации было необходимым. Отметим классический пример истинной импликации, приведенный Хаусдорфом в его "Теории множеств": если 1 = 0, то все ведьмы зеленые.

Применяя несколько раз эти операции, мы можем составить новые, более сложные высказывания. Укажем несколько примеров таких составных высказываний:

:((A&B) ! C) $ (B&C);

((A ! B) ! C) $ (A ! (B ! C));

(:(A _ B)) ! (:A&:B):

Если нам известно, истинны или ложны простые высказывания A, B, C, то мы легко можем вычислить значение истинности для любого

составного высказывания. В качестве примера проделаем это для высказывания :((A&B) ! C) $ (B&C), предположив, что A ложно, а

B и C истинны. Высказывание A&B ложно, так как ложной является одна из компонент конъюнкции; поэтому импликация (A&B) ! C истинна, Значит, отрицание этой импликации :((A&B) ! C) ложно. Далее, конъюнкция двух истинных высказываний B&C истинна,

2

и потому эквивалентность :((A&B) ! C) $ (B&C) истинного и

ложного высказываний ложна.

Тот факт, что высказывание истинно, будем обозначать буквой и, а ложным высказываниям будем сопоставлять букву л. Значение истинности высказывания A будем обозначать jAj.

2. Предикаты на множестве. Пусть M некоторое множество, и пусть для каждого набора c1; : : : ; cn 2 M задано высказывание P (c1; : : : ; cn). Мы говорим тогда, что P n-местный предикат на множестве M. Для любых c1; : : : ; cn 2 M высказывание P (c1; : : : ; cn) истинно или ложно; предикат P полностью определяется заданием множества PM Mn всех тех наборов (c1; : : : ; cn) 2 Mn, для которых высказывание P (c1; : : : ; cn) истинно.

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

Предикат сложения. Высказывание P (a; b; c) истинно тогда и только тогда, когда a + b = c.

Предикат строгого неравенства. Высказывание P (a; b) истинно тогда и только тогда, когда a < b.

Предикат равенства. Высказывание P (a; b) истинно тогда и только тогда, когда a = b. Поскольку предикат равенства играет особую

роль, мы будем обозначать его привычным образом, то есть записывать высказывание не в виде P (a; b), а в виде "a = b".

Из высказываний, связанных с предикатами, можно по правилам исчисления высказываний строить новые высказывания. Например, если P (c1; c2; c3), Q(c), R(c1; c2) предикаты на множестве M, и a; b; c 2 M, то можно составить высказывания

(P (a; b; b)&:Q(a)) _ R(b; a); ((a = c)&Q(b)) ! P (a; b; c)

è äð.

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

типа. Пусть некоторое высказывание A(c1; : : : ; cn) зависит от пара- метров c1; : : : ; cn; пусть, далее, это высказывание истинно не только в случае, когда первый параметр равен c1, но и при любом его зна- чении c 2 M (и тех же значениях остальных параметров). В этой

ситуации мы будем переменный первый параметр обозначать x, а

утверждение о том, что высказывание справедливо при любом зна- чении x записывать так: 8x(A(x; c2; : : : ; cn)). Аналогично, если среди

высказываний A(c; c2; : : : ; cn), c 2 M, есть хоть одно верное, будем писать: 9x(A(x; c2; : : : ; cn)).

Введенные только что символы 8 и 9 называются квантором все-

общности и квантором существования. Отметим, что в случае конеч- ного множества M в них нет необходимости: утверждения

3

равносильны соответственно высказываниям

Однако, для бесконечных множеств, и тем более в ситуации, когда множество M не зафиксировано, не удается свести кванторы к опе-

рациям исчисления высказываний.

x 2. Исчисление высказываний

1. Высказывания. В этом и следующем параграфах мы строим

формальные системы, в которые вкладываются содержательные рассмотрения предыдущего пункта. Эти построения аналогичны переходу от арифметики к алгебре, когда мы вместо конкретных натуральных чисел начинаем рассматривать произвольные числа, обозначаемые буквами x, y и т.д., а затем из этих букв составляем различные

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

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

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

è ë ( ) & _ : ! $ xn (n = 1; 2; 3; : : : ):

Этот алфавит бесконечен. Часто бывает неудобно использовать бес-

конечный алфавит; этого можно избежать, введя вместо бесконечной серии букв xn букву x и еще одну букву 0 и обозначив x1 = x, x2 = x0,

x3 = x00 и т.д. Буквы xi называются символами переменных.

Высказывания, в которые не входят символы переменных, состоят лишь из символов и, л, скобок и логических связок &, _, !, $,

:. Каждому такому высказыванию можно присвоить значение истинности и или л по обычным правилам, описанным в x 1. Еще удоб-

нее считать такие высказывания с одинаковым значением истинности равными. Точнее, положим

(è & è) = è; (è & ë) = (ë & è) = (ë & ë) = ë;

4

(è $ è) = (ë $ ë) = è; (è $ ë) = (ë $ è) = ë; (:è) = ë; (:ë) = è:

Пусть теперь A(x1; : : : ; xn) высказывание, в которое входят только символы переменных x1; : : : ; xn. Для любых "1; : : : ; "n 2 fи,лg обозначим через A("1; : : : ; "n) слово, получающееся заменой в слове A(x1; : : : ; xn) всех вхождений букв x1; : : : ; xn на соответствующие "1; : : : ; "n. Слово A("1; : : : ; "n) является высказыванием, в которое не

входят символы переменных, а только символы и, л и логические связки; каждое такое высказывание мы отождествили с одним из высказываний и, л. Таким образом, высказыванию A(x1; : : : ; xn) мы сопоставили функцию от n переменных из множества fи,лg со значени-

ями в том же множестве. Эта функция называется функцией истинности высказывания A(x1; : : : ; xn). Например, функция истинности высказывания A(x; y; z), заданного словом :((x&y) ! z) $ (y&z),

описывается следующей таблицей значений:

Пусть I некоторое конечное множество индексов; мы будем обо-

значать через W Ai è V Ai дизъюнкцию и конъюнкцию высказыва-

i2I i2I

íèé Ai, i 2 I, взятых в произвольном порядке (все утверждения,

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

юнкция пустого множества высказываний высказыванию л. Напомним, что для множества S через Sn обозначается n-я декар-

това степень S. В частности, fи,лgn n-я декартова степень мно-

жества fи,лg, то есть множество всех наборов ("1; : : : ; "n), таких что "i = è èëè "i = л для любого i, 1 i n.

Теорема 1. Для подмножества I множества fи,лgn обозначим че- ðåç AI (x1; : : : ; xn) высказывание

_ ^ ^

(( xi)&( :xj)):

Равенство AI ("1; : : : ; "n) = и выполняется тогда и только тогда, когда ("1; : : : ; "n) 2 I.

Доказательство. Пусть ( 1; : : : ; n) 2 fè,ëgn; конъюнкция

^^

( "i)&( :"j)

i; i=è j; j=ë

5

истинна тогда и только тогда, когда из того, что i = и, следует, что "i = è, à èç òîãî, ÷òî j = л, следует, что "j = л; иными словами, эта конъюнкция истинна тогда и только тогда, когда ("1; : : : ; "n) = ( 1; : : : ; n). Высказывание AI ("1; : : : ; "n) является дизъюнкцией тех из этих конъюнкций, которые отвечают наборам ( 1; : : : ; n), принадлежащим I; оно истинно тогда и только тогда, когда истинна одна из этих конъюнкций, то есть когда ("1; : : : ; "n) 2 I.

Следствие 1. Если подмножества I, J множества fи,лgn íå ñîâ-

падают, то и функции истинности, отвечающие высказываниям

AI (x1; : : : ; xn), AJ (x1; : : : ; xn) не совпадают.

Следствие 2. Для любой функции f(x1; : : : ; xn) : fè,ëgn ! fи,лg существует высказывание A(x1; : : : ; xn), такое что

A("1; : : : ; "n) = f("1; : : : ; "n)

äëÿ âñåõ "1; : : : ; "n 2 fè,ëg.

Доказательство. Таковым является высказывание AI (x1;: : : ;xn), ãäå I fè,ëgn множество всех тех наборов ("1; : : : ; "n), для которых

f("1; : : : ; "n) = и. Действительно, AI ("1; : : : ; "n) = и тогда и только тогда, когда ("1; : : : ; "n) 2 I, то есть когда f("1; : : : ; "n) = è.

2. Тавтологии. Правило подстановки. Некоторые высказывания

A(x1; : : : ; xn) являются истинными при любых значениях истинно- сти символов переменных x1; : : : ; xn; такие высказывания называют-

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

(1)(x1 $ x2) ! ((x1 ! x2)&(x2 ! x1));

(2)((x1 ! x2)&(x2 ! x1)) ! (x1 $ x2);

(3)(x1 ! x2) $ (:x1 _ x2);

(4)x1 ! (x1 _ x2);

(5)(x1&x2) ! x1;

(6)(x1&x2) $ (x2&x1);

(7)((x1&x2)&x3) $ (x1&(x2&x3));

(8)(x1&x1) $ x1;

(9)(x1 _ x2) $ (x2 _ x1);

(10)((x1 _ x2) _ x3) $ (x1 _ (x2 _ x3));

(11)(x1 _ x1) $ x1;

(12)(x1&(x2 _ x3)) $ ((x1 _ x3)&(x2 _ x3));

(13)(x1 _ (x2&x3)) $ ((x1&x3) _ (x2&x3));

(14)(:(x1&x2)) $ (:x1 _ :x2);

(15)(:(x1 _ x2)) $ (:x1&:x2);

(16)(:(:x1)) $ x1;

(17)(x1&è) $ x1;

(18)(x1 _ ë) $ x1;

(19)x1 ! (x2 ! (x1&x2));

6

(20) (((x1&x2) ! (ë))&((:x1&x3) ! (ë))) ! ((x2&x3) ! (ë)).

Докажем, например, что (20) тавтология. Пусть "1; "2; "3 çíà- чения истинности элементарных высказываний x1; x2; x3. Åñëè "2 = ë èëè "3 = ë, òî (("2&"3) ! (л)) = и, а всякая импликация с истинным заключением истинна. Если же "2 = "3 = и, то одна из конъюнкций (("1&"2)), (:"1&"3) истинна, поэтому одна из импликаций (("1&"2) ! (ë), ((:"1&"3) ! (л)) ложна, а значит, ложна и их конъ-

юнкция. Остается заметить, что импликация с ложной посылкой истинна.

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

Предложение 1 (правило подстановки). Пусть F (x1; : : : ; xm) тавтология, и пусть Y1, . . . ,Ym произвольные высказывания; тогда высказывание F (Y1; : : : ; Ym), полученное из F (x1; : : : ; xm) подстановкой вместо каждого вхождения букв x1, . . . , xm соответству- ющих высказываний Y1, . . . ,Ym, является тавтологией.

Например, для любых высказываний Y1; : : : ; Ym тавтологией явля- ется высказывание

(Y1& : : : &Ym 1) ! (Ym ! (Y1& : : : &Ym 1&Ym));

полученное из (19) подстановкой Y1& : : : &Ym 1 вместо x1, Ym вместо x2.

3. Булевы алгебры. Рассмотрим один тип алгебраических струк-

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

Определение. Булевой алгеброй называется множество B, на ко-

тором заданы две бинарных операции сложение " + " и умножение " ", одна унарная операция дополнение a ! a , и в котором

выделены две константы 0 и 1, причем для любых элементов a; b; c 2 B выполняются следующие соотношения:

(1) (законы поглощения) a + a = a, a a = a;

(2)(коммутативность) a + b = b + a, a b = b a;

(3)(ассоциативность) a + (b + c) = (a + b) + c, a (b c) = (a b) c;

(4)(дистрибутивность) a (b + c) = (a b) + (a c), (a b) + c = (a + c) (b + c);

(5)(свойства 0 и 1) a 0 = 0, a 1 = a, a + 0 = a, a + 1 = 1;

(6)(свойства дополнения) a a = 0, a + a = 1, (a + b) = a b ,

(a b) = a + b , (a ) = a.

Важнейшим примером булевой алгебры является множество P (A) всех подмножеств некоторого множества A; действия над подмножествами определены следующим образом: для любых X; Y A

X + Y = X [ Y; X Y = X \ Y; X = A n X = fa 2 X j a 2= Xg:

7

Единицей булевой алгебры P (A) является все множество A, а нулем

пустое подмножество.

Âдальнейшем мы часто будем опускать знак умножения и часть

скобок, пользуясь привычными соглашениями о том, что умножение предшествует сложению. Например, выражение xy + ztu в разверну-

том виде выглядит так: (x y) + (z (t u)).

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

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

пусть " равно 1 или -1; через b" мы будем обозначать элемент b, если " = 1, и элемент b , если " = 1.

Пусть B произвольная булева алгебра, и пусть b1,. . . ,bn какие- то элементы из B. Если I подмножество n-й декартовой степени

Кроме того, для любого s, 1 s n, элемент bs совпадает с bI(s), ãäå I(s) множество всех тех наборов ("1; : : : ; "n), в которых "s = 1. Таким образом, множество S(b1; : : : ; bn) всех элементов bI являет- ся подалгеброй булевой алгебры B; она содержит элементы b1; : : : ; bn и содержится в любой подалгебре булевой алгебры B, обладающей этим свойством.

Доказательство. Утверждение bI + bJ = bI[J сразу следует из зако- на поглощения для суммы. Заметим теперь, что если ("1; : : : ; "n) 6= ( 1; : : : ; n), то существует номер s, такой что "s 6= s; поэтому произ-

nn

ведение (Q b"ii ) (Q bii ) содержит сомножители bs, bs и потому равно

i=1 i=1

0. Из дистрибутивности и законов поглощения для умножения и сложения следует, что произведение

8

Пусть теперь J = f1; 1gn n I; из уже доказанного следует, что

Будем говорить, что построенная в только что доказанной лемме подалгебра S(b1; : : : ; bn) порождена элементами b1; : : : ; bn. Åñëè

S(b1; : : : ; bn) = B, то говорим, что b1; : : : ; bn

булевой алгебры B; если к тому же все элементы bI , I f1; 1gn, различны, то говорим, что B свободная булева алгебра со сво- бодными образующими b1; : : : ; bn. Из этого определения следует, что свободная булева алгебра с n свободными образующими состоит из 22n элементов.

Пусть теперь fbi j i 2 Ig какое-то, вообще говоря, бесконеч- ное семейство элементов из B. Будем говорить, что булева алгебра B порождена этим семейством, если для любого элемента x 2 B

существует его конечное подсемейство fbi1 ; : : : ; bin g, такое что x 2 S(bi1 ; : : : ; bin ). Далее, если булева алгебра B порождена семейством fbi j i 2 Ig и если для каждого конечного подсемейства fbi1 ; : : : ; bin g множество S(bi1 ; : : : ; bin ) является свободной булевой алгеброй со сво- бодными образующими bi1 ; : : : ; bin , то мы говорим, что B свободная булева алгебра со свободными образующими fbi j i 2 Ig.

4. Идеалы и дуальные идеалы булевой алгебры. Пусть B булева алгебра; е¼ непустое подмножество I называется идеалом алгебры B, если для любых x; y 2 I, b 2 B элементы x + y, bx принадлежат I.

Во всякой булевой алгебре есть два тривиальных идеала 0 и вся алгебра. Пусть теперь S B; очевидно, пересечение всех идеалов

булевой алгебры B, содержащих S, снова является идеалом алгебры B, содержащим S. Этот идеал называется идеалом, порожденным множеством S, и является наименьшим идеалом, содержащим это множество элементов.

Теорема 2. Пусть B булева алгебра, и пусть S B. Идеал алгебры B, порожденный множеством S, является объединением идеалов, порожденных всеми конечными подмножествами S. Иде-

ал, порожденный конечным множеством fb1; : : : ; bng, порождается одним элементом b = b1 + +bn

ab, a 2 B.

Доказательство. Обозначим через J объединение всех идеалов, порожденных конечными подмножествами S; каждый из этих идеалов содержится в идеале I, порожденном множеством S, и потому J I. Обратно, ясно, что J является идеалом алгебры B, содержащим множество S и, поскольку I наименьший идеал, содержащий S, находим, что I J.

9

Если идеал I порожден конечным множеством fb1; : : : ; bng, то элемент b = b1 + + bn принадлежит I. Обратно, элемент

b1 = b1 1 = b1(1 + b2 + + bn) = b1 + b1(b2 + + bn) =

= b1b1 + b1(b2 + + bn) = b1(b1 + b2 + + bn) = b1b

принадлежит идеалу, порожденному одним элементом b, и точно так же элементы b2 = b2b, . . . , bn = bnb принадлежат идеалу, порожденному b. Итак, эти два идеала совпадают. Остается заметить, что идеал, порожденный единственным элементом b, состоит из всех элементов вида ab, a 2 B.

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

Пусть B булева алгебра; е¼ непустое подмножество I называется дуальным идеалом алгебры B, если для любых x; y 2 I, b 2 B элементы xy, b + x принадлежат I.

Во всякой булевой алгебре есть два тривиальных дуальных идеала1 и вся алгебра. Пусть теперь S B; очевидно, пересечение всех

дуальных идеалов булевой алгебры B, содержащих S, снова является дуальным идеалом алгебры B, содержащим S. Этот дуальный идеал называется дуальным идеалом, порожденным множеством S, и яв-

ляется наименьшим дуальным идеалом, содержащим это множество элементов.

Теорема 3. Пусть B булева алгебра, и пусть S B. Дуальный идеал алгебры B, порожденный множеством S, является объедине-

нием дуальных идеалов, порожденных всеми конечными подмножествами S. Дуальный идеал, порожденный конечным множеством

fb1; : : : ; bng, порождается одним элементом b = b1 bn и состоит из всех элементов вида a + b, a 2 B.

5. Булева алгебра высказываний. Будем говорить, что два высказывания A, B эквивалентны, если высказывание A $ B являет-

ся тавтологией. Поскольку эквивалентность истинна тогда и только тогда, когда обе е¼ части имеют одинаковое значение истинности, приходим к выводу: два высказывания A(x1; : : : ; xn), B(x1; : : : ; xn) эквивалентны тогда и только тогда, когда

A("1; : : : ; "n) = B("1; : : : ; "n)

äëÿ âñåõ "1; : : : ; "n 2 fи,лg. Отсюда и из того факта, что значение истинности высказываний A&B, A _ B, :A, A ! B, A $ B вполне

10