Будем называть упорядоченной парой (a, b) расположение двух элементов a и b в указанном порядке: a - первый элемент, b- второй элемент. Упорядоченной тройкой (a, b, c) - расположение трех элементов a, b, c в указанном порядке: a - первый элемент, b- второй, с - третий. Вообще упорядоченная n-ка (a 1, а 2, …, an) - расположение n элементов a 1, а 2, …, an в указанном порядке: a 1 - первый элемент, а 2 - второй, …, an - n- ый элемент.
Очень часто слово "упорядоченная" опускают и для краткости речи говорят "пара", "тройка", " n -ка". Упорядоченную n -ку называют также кортежем длины n. Элементы, из которых состоит n -ка, называются ее компонентами или координатами.
Определение 4.1. Две n-ки (a 1, а 2, …, an) и (b 1, b 2, …, bn) называются равными, если соответствующие компоненты n-к равны, т.е. (a 1, а 2, …, an) = (b 1, b 2, …, bn) тогда и только тогда, когда a 1 = b 1, а 2 = b 2, …, an = bn.
Например, (1, 2) = (1, 2), (2, 1) ¹ (1, 2).
Определение 4.2. Декартовым или прямым произведением множеств А и В называется множество, обозначаемое А ´ В и состоящее из всех упорядоченных пар (a, b) таких, что a Î A, b Î B:
А ´ В ={(a, b)½ a Î A, b Î B }.
Декартовым или прямым произведением n множеств A 1, A 2, …, An называется множество, обозначаемое A 1´ A 2´…´ An и состоящее из всех упорядоченных n -к (a 1, а 2, …, an) таких, что a 1 Î A 1, а 2 Î A 2, …, an Î An:
A 1´ A 2´…´ An ={(a 1, а 2 ,…, an)½ a 1 Î A 1, а 2 Î A 2, …, an Î An }.
Примеры. 6.1. Пусть A = {1, 2}, B = { a, b }, C = {5}. Тогда
A ´ B = {(1, a), (1, b), (2, a), (2, b)}, B ´ A = {(a, 1), (b, 1), (a, 2), (b, 2)},
A ´ B ´ C = {(1, a, 5), (1, b, 5), (2, a, 5), (2, b, 5)}.
2. Пусть A = [1, 2], B = [1, 4]. Тогда A ´ B изображает множество всех точек P(x, y) плоскости xOy с координатами x, y, где 1 £ x £ 5, 1 £ y £ 4. Если A изобразить отрезком оси Ox, а B - отрезком оси Oy, то множество A ´ B изобразится прямоугольником, указанным на Рис. 1.4.
Определение 4.3. Декартовой n -й степенью множества A называется множество, обозначаемое An и являющееся декартовым произведением множества A на себя n раз:
.
Мы считаем, что A 1 = A. Множества A 2 и A 3 называются соответственно декартовым квадратом и декартовым кубом множества A.
Например, если A = {1, 2}, то A 2 = {(1, 1), (1, 2), (2, 1), (2, 2)}.
Наглядным образом декартова квадрата R 2 = R ´ R является множество всех точек плоскости xOy, декартова куба R 3 = R ´ R ´ R является множество точек трехмерного пространства Oxyz.
Теорема 4.1. Прямое произведение A 1´ A 2´…´ An - непустое множество тогда и только тогда, когда непустым является каждое из множеств A 1, A 2, …, An.
Доказательство. ТУ 4.1.
Теорема 4.1. Для любых множеств А, В, С справедливы дистрибутивные законы:
1.1. A ´(B È C) = (A ´ B) È (A´ C), 1.2. (A È B)´ C = (A ´ C) È (B ´ C);
2.1. A ´(B Ç C) = (A ´ B) Ç (A´ C), 2.2. (A Ç B)´ C = (A ´ C) Ç (B ´ C);
3.1. A ´(B \ C) = (A ´ B) \ (A´ C), 3.2. (A \ B)´ C = (A ´ C) \ (B ´ C).
Доказательство. ТУ 4.2.
Замечание 4.1. Отметим, что для декартова произведения множеств не справедливы коммутативный и ассоциативный законы. Это легко установить, приведя контр примеры.
Упражнения: 4.1. Изобразить множество A ´ B, если A = { x Î R | x 2- x -6³0}, B = { x Î R | x 2+ x -6³0}.
4.2. Привести примеры, показывающие не выполнимость коммутативного и ассоциативного законов операции декартова произведения.
4.3. Доказать теорему 4.1.
Предикаты и кванторы.
Переменные x, y, …, которых служат для обозначения элементов множества X, называются переменными или предметными переменными, определенными на множестве X.
Определение 5.1. Предикатом (n - местным предикатом) называется предложение, содержащее n предметных переменных, определенных на одном или различных множествах, и которое превращается в высказывание истинное или ложное, если мы заменим предметные переменные их значениями.
n -местный предикат P, содержащий переменные x 1, x 2, …, xn, определенные соответственно на множествах M 1, M 2, …, Mn, обозначается также символом P (x 1, x 2, …, xn). Если x 1 = a 1Î M 1, x 2 = a 2Î M 2, …, xn = an Î Mn,то через P (a 1, a 2, …, an) обозначаем значение предиката.
Отметим, что сам предикат высказыванием не является, но каждое значение предиката высказывание. Так как в логике нас не интересует содержание высказывания, то можно сказать, что предикат принимает два значения 1 и 0, где 1 обозначает "истинное высказывание", 0 - " ложное высказывание".
Определение 5.2. Областью истинности предиката P называется множество, обозначаемое ОИ(P) и состоящее из всех значений переменных (a 1, …, an)Î M 1´ …´ Mn, при которых предикат P принимает значение 1:
ОИ(P) ={(a 1, …, an)Î M 1´ …´ Mn | P (a 1, a 2, …, an) =1}.
Область истинности одноместного предиката, определенного на R удобно изображать на числовой прямой, а двуместного предиката, определенного на R 2 изображают на координатной плоскости x O y.
Пример 1. Пусть P (x) = [ x - простое число] - одноместный предикат, определенный на N. Тогда P (1) = 0, P (2) = 1, P (4) = 0.
5.2. Пусть Q (x) = [| x | <1] - предикат, определенный на R. Тогда ОИ(Q) = (-1, 1).
5.3. Пусть R (x, y) = [ x 2 + y 2£ 4] - двуместный предикат, определенный на R 2, для которого ОИ(R) изображена на рис. 21.
Некоторые, часто встречающиеся, предикаты обозначаются специальными символами. Например, x < y (" x меньше y "); x = y (" x равно y "); A Í B (" A включено в B ").
Так как принимают значения 1(истинно), 0 (ложно), то к ним применимы все логические операции над высказываниями. Поэтому, если P, Q - предикаты, то P & Q, P Ú Q, P Þ Q, P Û Q,Ø P, Ø Q также есть предикаты.
Теорема 5.1. Пусть предикаты P и Q, определенные на одном и том же множестве. Тогда
1. ОИ(P & Q) = ОИ(P)ÇОИ(Q); 2. ОИ(P Ú Q) = ОИ(P)ÈОИ(Q);
3. ОИ(P Þ Q) = СM(ОИ(P)) È ОИ(Q); 3. ОИ(Ø P) = СM(ОИ(P)).
Доказательство. Докажем равенство 1.
Пусть a ÎОИ(P & Q). Тогда по определению 5.2 и по определению конъюнкции P (a) = 1 и Q (a) = 1. Следовательно, по определению 5.2 a ÎОИ(P) и a ÎОИ(Q) и по определению пересечения a ÎОИ(P) Ç ОИ(Q).
Аналогично доказывается, что, если a ÎОИ(P)ÇОИ(Q), то a ÎОИ(P & Q). Откуда по определению равенства множеств следует доказываемое равенство.
Определение 5.3. Предикаты P и Q, определенные на одном и том же множестве называется равносильными, обозначается P º Q, если ОИ(P) = ОИ(Q).
Определение 5.4. Предикат Q называется следствием предиката P, если ОИ(P) Í ОИ(Q).
Например, предикаты [| x | £1] и [ x 2 £ 1], определенные на R,равносильны, а предикат [ x 2 > 1] - следствие предиката [ x > 1].
Замечание 5.1. С точки зрения логики предикатов имеем.
1) Всякое уравнение или неравенство есть предикат; система уравнений или неравенств - конъюнкция предикатов; совокупность уравнений или неравенств - дизъюнкция предикатов.
2) Множество решений уравнения или неравенства, система (совокупности) уравнений или неравенств - область истинности некоторого предиката.
3) Равносильные уравнения или неравенства, системы (совокупности) уравнений или неравенств - равносильные предикаты.
Определение 5.5. Пусть P (x) - одноместный предикат, определенный на множестве M.
1. Символ "(x Î M) P (x) или " x P (x) обозначает высказывание, которое истинно тогда и только тогда, когда ОИ(P) = M,т.е., когда высказывание P (x) истинно для каждого x Î M.
2. Символ $(x Î M) P (x) или $ x P (x) обозначает высказывание, которое истинно тогда и только тогда, когда ОИ(P) ¹ Æ,т.е., когда высказывание P (x) истинно хотя бы для одного x Î M.
Символы " и $ называются соответственно кванторами общности и существования. Выражение "(x Î M) P (x) читается "для любого x Î M P (x)", выражение $(x Î M) P (x) - "существует такое x Î M, что P (x)". Про переменную x говорят, что она связана квантором. Если известно, о каком множестве идет речь, то кванторы можно записывать так " xP (x), $ xP (x)
Например, для предикатов Q (x) = [ x 2 ³ 0], R (x) = [ x 2 < 0 ], P (x) = =[ x - простое число], определенный на Z, имеем " xQ (x)=0, $ xQ (x)=1, " xP (x)=0, $ xP (x)=1, " xR (x)=0, $ xR (x)=0,
Соединяя высказывания и предикаты операциями алгебры высказываний и кванторными операциями, мы получим формулы логики предикатов. Например, A Þ P (x). " x (P (x)Ú Q (x)). Аналогично тому, как это сделано в алгебре высказываний можно ввести понятие формулы и равносильности формул в алгебре предикатов.
Все равносильности, имеющие место в алгебре высказываний имеют место и в алгебре предикатов. Кроме того справедлива теорема.
Теорема 5.2. Пусть P (x) и Q (x) - произвольные предикаты, определенные на множестве М. Тогда справедливы равносильности:
1. " x P (x) &" x Q (x) º " x (P (x) & Q (x)),
1¢. $ x P (x) Ú $ x Q (x) º $ x (P (x) Ú Q (x)),
2. Ø($ x P (x)) º " x (Ø P (x)), 2¢. Ø(" x P (x)) º $ x (Ø P (x))
(Формулы А. де Моргана).
Доказательство. Докажем равносильность 2.
Пусть Ø($ x P (x)) - истинно. Тогда высказывание $ x P (x) - ложно и по определению 5.5 ОИ(P) =Æ. По теореме 5.1 ОИ(Ø P) = =СM(ОИ(P))= СMÆ= M и по определению 5.5 " x (Ø P (x)) - истинно.
Пусть Ø($ x P (x)) - ложно. Тогда высказывание $ x P (x) - истинно и по определению 5.5 ОИ(P) ¹ Æ. По теореме 5.1 ОИ(Ø P) = =СM(ОИ(P)) ¹ M и по определению 5.5 " x (Ø P (x)) - ложно.
Из доказанного следует равносильность 2.