UML_4256

логики. Например, x → x, x x , x x , x ~ x – тавтологии. Они называются соответственно законом тождества, исключения третьего и двойного отрицания.

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

Пример 3. Обозначим высказывание «диагональ квадрата не соизмерима с его стороной» через А, а высказывание «зимний день короче летнего» через В, и рассмотрим их импликацию A → B = C . Так как A =1 и B =1, то и A ~ B = C , C =1. То есть высказывание «Если сторона квадрата не соизмерима с его стороной, то зимний день короче летнего» истинно, но его нельзя понимать в обычном смысле, как причинную связь между этими высказываниями.

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

Предикат называют n-арным, если в логическую формулу входят n логических переменных. Обозначают P(x1, x2 ,..., xn ) . В частности

P(x) – унарный предикат, P(x, y) – бинарный, P(x, y, z) – тернарный.

Унарный предикат, в отличие от высказывания, отражает содержание высказывания, он выражает общее свойство множества. Предложения «х – простое число», « x ≤ 3» – примеры унарного предиката P(x) .

Предикат n-арный выражает не только содержание высказывания, но и связь между высказываниями. Например, предложение «x – есть наибольший общий делитель между 20 и y» – бинарный предикат

P(x, y).

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

Запись x P(x) означает «для всех x имеет место P(x) ». xP(x) – «существует x , обладающий свойством P(x) ».

Словам «такой, что» соответствует двоеточие или вертикальная черта (:,|). Знак « = » может означать тождество, например, 2 = 2. Этот знак может служить для определения нового

символа, например, y = f (x), C = (A ~ B) → (A B) . Знак « = » может

11

служить и знаком эквивалентности. Например, 23 = 64 . Иногда пишут

def

= , что означает «равно по определению», «эквивалентно по определению».

Отметим, что язык алгебры предикатов удобен для записи составных высказываний. Например, предложение «Для всяких x существует единственный y такой, что x + y = 5» можно записать так:

x !y : x + y = 5 .

§2. Понятие множества

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

Кантор не накладывает никаких ограничений на природу объектов. Это может быть множество студентов данной аудитории, множество звезд, видимых на небе, множество воинов погибших на войне. Обратим внимание, что мы не можем собрать этих воинов, никто даже не знает, сколько их погибло. Но мы можем мысленно представить это множество, это объекты нашего интеллекта. Слово «различаемых» предполагает возможность различать элементы множества, то есть предполагает, что введено понятие эквивалентности элементов.

Слово «определенных» предполагает, что есть признак (свойство) элементов, по которому они собраны в множество, то есть задан унарный предикат P(x) . Слова «единое целое» означают, что само

собрание объектов является объектом. Это приемлемо интуитивно и отражается в нашем языке такими словами, как «стадо», «стая», «свора», «коллектив» и пр.

Множества обозначают большими латинскими буквами, а элементы множества – малыми. Если a – элемент множества A , то пишут a A . Запись a A означает, что a не является элементом множества A .

Множества бывают конечными (они содержат конечное число

12

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

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

Например, A ={2,4,6} – первые три четные числа. Если элементов

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

действительных чисел интервала (1,2).

X3 ={x N : x = 3k, k N} – множество натуральных чисел кратных 3. A ={(x, y), x R, y R : x2 + y2 =1} – множество точек плоскости,

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

Множества A и B называют равными, если они состоят из одних и тех же элементов, то есть все элементы множества A являются элементами множества B и наоборот. Пишут A = B .

Если каждый элемент множества A является одновременно и элементом множества B , то пишут A B . Читают так: множество А является подмножеством множества В, или А включено в В, или В содержит А. Причем A B B A .

Основные свойства отношений равенства и включения следующие:

1)(A = B) (B = C) A = C ;

2)(A B) (B C) A C ;

3)(A B) (B A) A = B ;

4)A , для любого не пустого множества А.

Вкачестве примера докажем третье свойство.

Пусть х – произвольный (любой) элемент множества А, то есть x A .

множества В и наоборот. Это и означает, что A = B . Что и требовалось доказать.

§3. Операции над множествами

Определение 1. Объединением (суммой) двух множеств А и В называют множество С, состоящее из всех элементов, принадлежащих

13

хотя бы одному из множеств А или В. Обозначают C = A B . Таким образом,

Пример 2. A ={1,2}, B ={2,3}, C ={3,4} A B C ={1,2,3,4}

Определение 2. Пересечением (произведением) множеств А и В называют множество С, состоящее из всех элементов, принадлежащих и множеству А и множеству В. Обозначают A ∩ B.

Таким образом,

Если A ∩ B = , то множества называются непересекающимися.

Пример 3. A ={1,2,3}, B ={1,3,4}, C ={4,5} A ∩ B ={1,3},

A ∩C = , B ∩C ={4}.

Пересечение также можно распространить на любое число множеств

Xα , α A.

множество, элементы которого являются элементами множества А, но не являются элементами множества В. Обозначают А\В.

Xα Xα = Ω.

Определение 4. Симметрической разностью множеств А и В

14

Пример 6. A ={1,2,3}, B ={1,3,4} A B ={2} {4} ={2,4}.

Для графической иллюстрации отношений между универсальным множеством Ω и его подмножествами А, В, С и т.д. используют диаграммы Венна.

(Д. Венн, 1834г.–1923г. – английский логик и математик). Универсальное множество Ω изображается множеством точек некоторого прямоугольника, а его подмножество А – частью прямоугольника, лежащей внутри некоторой замкнутой линии (см. диаграммы ниже).

(x X , y Y ). Говорят, что элементы х и у образуют упорядоченную

пару (х,у), если важен порядок, в котором стоят элементы х и у, х называется первой координатой пары, а у – второй.

упорядоченную n-ку (энку), или кортеж.

Определение 5. Прямым (декартовым) произведением двух множеств Х и Y называют множество упорядоченных пар (х, у), где x X , y Y . Обозначают X ×Y . Таким образом,

A× A = A2 ={(1,1),(1,2),(2,1),(2,2)}. B × B = B2 ={(1,1),(1,3),(3,1),(3,3)}.

Декартово произведение n множеств X1, X 2 ,..., X n – это

множество кортежей, то есть X1 × X 2 ×...× Xn ={(x1, x2 ,..., xn ) | xk Xk }. Вводят также степень множества. Если X1 = X 2 = ... = X n = X , то

X1 × X2 ×...× Xn = X n . В частности R0 = , R1 = R – числовая прямая,

R2 = R × R – плоскость, R3 = R × R × R – трехмерное пространство, Rn

– n-мерное пространство.

§4. Свойства операций над множествами

Теорема 1. Для любых подмножеств А, В, и С универсального множества Ω следующие равенства являются тождествами:

Тождества 1 − 3 и 1′−3′ справедливы для любых множеств, необязательно подмножеств Ω.

Тождества 1,1′ выражают ассоциативный (сочетательный) закон объединения и пересечения. Он аналогичен ассоциативному закону сложения и умножения чисел:

a + (b + c) = (a +b) + c, a(bc) = (ab)c .

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

Тождество 3, 3′ – дистрибутивный (распределительный) закон сложения относительно умножения и умножения относительно

Законы 4 – 9 прямого аналога для чисел не имеют.

Тождества 6, 6′ – называются законами идемпотентности, 7, 7′ –

16

законом двойного отрицания, 8, 8′ – законом де Моргана, 9, 9′ – закон поглощения.

Доказательство. Тождества 1, 2, 4, 5, 6, 9 (1′,2′,4′,5′,6′,9′)

следуют непосредственно из определения операций.

Докажем тождество 3. Пусть х – произвольный элемент левой части

тожества 3

x A (B ∩C). x A B ∩C.

любом случае х принадлежит и левой части. Что требовалось доказать.

Наоборот, пусть x A = c(cA) , то есть левой части.

Тогда x cA, следовательно x A , то есть правой части. Тождество 7 доказано.

x A ∩ B , то есть x принадлежит и правой части 8. Противоположное включение устанавливается прохождением использованной цепочки рассуждений в обратном направлении. Теорема доказана.

Заметим, что k − е тождество теоремы получается из тождества k′ путем замены на ∩, ∩ на , на Ω и Ω на . Эти тождества называются двойственными.

Справедливо более общее утверждение, а именно:

Теорема 2 (принцип двойственности). Пусть задан класс подмножеств множества Ω. Если верно некоторое равенство или включение между подмножествами множества Ω, то верно и двойственное равенство или включение. (Без доказательства).

Теоремы 1, 2 часто используются для упрощения выражений. Пример 1. Упростить: M = ( A ∩ B ∩C) ( A ∩ B ∩C) B C.

§5. Основные множества действительных чисел

Вспомним числовые множества, известные нам из школьной программы.

17

1. Множество натуральных чисел N ={1,2,3,...}.

0 1 √2 2 3

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

Какие же операции возможны в множестве натуральных чисел? Очевидно, сложение, умножение, возвышение в степень. Однако, вычитание не всегда возможно, то есть уравнение n + x = m, n,m N не всегда разрешимо (разрешимо не для n, m N ). Чтобы это

уравнение всегда имело решение, необходимо расширить множество натуральных чисел, то есть добавить другие, не натуральные числа. Рассмотрим множество натуральных чисел, добавив число 0 и отрицательные числа –1, –2, –3… . Получим множество целых чисел

Z ={0,±1,±2,...}.

На числовой оси нулю сопоставим начало отсчета, а числа –1, –2, –3,… изобразим точками, симметричными точкам 1,2,3,… относительно нуля. Таким образом, всем целым числам поставим в соответствие точки числовой оси.

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

не всегда возможна, то есть уравнение x2 = a, a > 0, a Q не всегда

18

разрешимо. Например, x2 = 2 не разрешимо, то есть x = 2 не является рациональным числом. Докажем это. От противного. Пусть

несократимая. Возведем обе части равенства в квадрат. Получим

Левая часть равенства (1) – число четное, следовательно, число в правой части – также четное. Тогда и m – число четное, то есть m = 2k .

является рациональным числом. Это число иррациональное. Иррациональным называют число, которое нельзя представить в

виде конечной или бесконечной периодической десятичной дроби. Оно представляется бесконечной непериодической десятичной дробью. Если к рациональным числам добавить иррациональные, то получим множество действительных (вещественных) чисел R. Каждому иррациональному числу также можно сопоставить точку числовой оси.

Например, 2 – это длина диагонали единичного квадрата. Откладывая эту диагональ от начала отсчета, получим точку на оси,

соответствующую числу 2 .

Таким образом, каждому действительному числу соответствует единственная точка на числовой оси. Позже мы убедимся, что и каждой точке числовой оси соответствует единственное действительное число. Говорят, что имеет место биекция между множеством действительных чисел R и множеством точек числовой оси.

Заметим, что уравнение x2 = −1 не разрешимо в множестве действительных чисел. Однако, если расширить множество

действительных чисел, то есть ввести новое (комплексное) число −1 , то уравнение будет разрешимо. Что такое расширение множества действительных чисел возможно, убедимся позже.

§6. Основные свойства действительных чисел

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

19

I группа. Свойства упорядоченности.

1) Для любых двух действительных чисел a и b имеет место одно и только одно из соотношений: a < b, a = b, a > b. При этом запись

a < b равнозначна записи b > a . Свойство 1 называют свойством сравнения действительных чисел.

2)Если a = b и b = c , то a = c. Если a < b и b < c , то a < c . Это свойство называется свойством транзитивности знаков = и < .

3)Если a < c , то найдется число b такое, что a < b < c. Это свойство называется свойством плотности действительных чисел.

IIгруппа. Свойства операции сложения.

Для каждой пары действительных чисел a и b сопоставляется действительное число, называемое их суммой и обозначаемое a + b или b + a . Сумма обладает следующими свойствами:

1) a + b = b + a – переместительное свойство операции сложения (коммутативность).

3)Существует число 0 (нуль) такое, что для любых a a + 0 = a .

4)Для всякого действительного числа a существует противоположное ( −a) такое, что a + (−a) = 0. Это свойство дает

возможность определить операцию вычитания (разность) действительных чисел a и b

a−b = a + (−b).

IIIгруппа. Свойства операции умножения.

Для каждой упорядоченной пары действительных чисел a и b существует действительное число, называемое произведением этих

(ассоциативность).

3)a 1 = a .

4)Для всякого действительного числа a ≠ 0 существует обратное

Это свойство дает возможность ввести операцию деления

20