Модуль 1. Математические основы баз данных и знаний
Лекция 1 Математические основы множеств 1. Терминология и обозначения 2. Определение множеств 3. Операции над множествами 4. Кортеж. Декартово произведение
Терминология и обозначения Множество - совокупность элементов, обладающих некоторым общим свойством. Г. Кантор: Под многообразием или множеством я понимаю вообще все многое, которое возможно мыслить как единое, т.е. такую совокупность определенных элементов, которая посредством одного закона может быть соединена в одно целое".
Терминология и обозначения Объекты, составляющие множество, называются элементами множества Пустое множество- множество, не содержащее ни одного элемента Множество считается определенным, если указаны все его элементы. Эти элементы могут быть указаны с помощью некоторого общего признака или с помощью некоторого списка, где обозначены все элементы.
Терминология и обозначения Конечное множество- множество, состоящее из конечного числа элементов Бесконечное множество- непустое множество, не являющееся конечным Упорядоченное множество - Множество, каждому элементу которого поставлено в соответствие некоторое число (номер этого элемента) от 1 до n, где n - число элементов множества, так что различным элементам соответствуют различные числа.
Терминология и обозначения элемент Х принадлежит множеству А множество В является подмножеством множества А Подмножество В множества А называется собственным подмножеством, если:
Терминология и обозначения Z множество целых чисел; Q множество рациональных чисел; I множество иррациональных чисел; R множество действительных чисел; C множество комплексных чисел.
Терминология и обозначения Индивидная константа (или просто константа) с областью значений А обозначает фиксированный элемент множества А. Например, обозначения (записи в определенной системе счисления) действительных чисел: 0; 2; 7,34. Для двух констант а и b с областью значений А будем писать а = b, понимая под этим совпадение обозначаемых ими элементов множества А.
Терминология и обозначения Индивидное переменное (или просто переменное) с областью значений А обозначает произвольный, заранее не определенный элемент множества А. Можно фиксировать значение переменного х, записав x = а, где а константа с той же областью значений, что и x. Равенство переменных х = у понимается так: всякий раз, когда переменное х принимает произвольное значение а, переменное у принимает то же самое значение а, и наоборот. Равные переменные синхронно" принимают всегда одни и те же значения.
Терминология и обозначения операции над высказываниями Дизъюнкция : высказывание P Q истинно тогда и только тогда, когда истинно хотя бы одно из высказываний Р и Q. Конъюнкция : высказывание P Q истинно тогда и только тогда, когда истинны оба высказывания Р и Q. Отрицание ¬: высказывание ¬Р истинно тогда и только тогда, когда Р ложно. Импликация : высказывание Р Q истинно тогда и только тогда, когда истинно высказывание Q или оба высказывания ложны. Эквивалентность (или равносильность) : высказывание P Q истинно тогда и только тогда, когда оба высказывания Р и Q либо одновременно истинны, либо одновременно ложны. Любые два высказывания Р и Q, такие, что истинно Р Q, называют логически эквивалентными или равносильными.
Терминология и обозначения порядок операций Операция отрицания (ее в скобки не заключают). операция конъюнкции, Дизъюнкция импликация и эквивалентность. ¬P Q ¬Q P ¬Q (((¬P) Q) ((¬Q) P)) (¬Q)
Терминология и обозначения Таблицы истинности для логических операций PQP V Q ЛЛИИЛЛИИ ЛИЛИЛИЛИ ЛЛЛИЛЛЛИ PQ p q ЛЛИИЛЛИИ ЛИЛИЛИЛИ ЛЛЛИЛЛЛИ Р¬Р ЛИЛИ ИЛИЛ
Терминология и обозначения Таблицы истинности для логических операций Таблица 1.4 Таблица 1.5 PQ P Q ЛЛИ ЛИЛ ИЛЛ ИИИ PQ ЛЛИИЛЛИИ ЛИЛИЛИЛИ ИИЛИИИЛИ
Терминология и обозначения Таблицы истинности (¬P Q) (¬Q P) Обозначим: ¬P Q через А ¬Q P через В Исходное высказывание - А => В. РQАВ А В ЛЛЛЛИ ЛИИЛЛ ИЛЛИИ ИИЛЛИ
Терминология и обозначения Предикат - высказывание, содержащее одно или несколько индивидных переменных. Предикат с несколькими индивидными переменными: «х есть сын у«, х, у и z учатся в одной и той же группе" Предикаты записываются в виде: Р(х), Q(х,y), R(x,у,z) Конкретные значения: 2 есть четное число", Исаак Ньютон есть студент НАУ, поступивший в 2006 г.« Предикат, выполняющийся на любом наборе входящих в него переменных, называют тождественно истинным, а предикат, не выполняющийся ни на одном наборе значений входящих в него переменных, тождественно ложным.
Терминология и обозначения Кванторы: - существования; всеобщности. Высказывание ( x А)Р(х) (для каждого элемента x, принадлежащего множеству А, истинно Р(х)", тогда и только тогда, когда предикат Р(х) выполняется для каждого значения переменного х. В общем случае используют формы высказываний вида (Q1x1 A1)(Q2x2 А2)... (Qnxn An)P(x1,x2,...,xn), где вместо Q с индексом может быть подставлен любой из кванторов или. Например, высказывание ( x А)( у В)Р(х,у) читается так: для всякого х А существует у В, такой, что истинно Р(x,у)".
Определение множеств Элементы конечного множества перечисляют в фигурных скобках в произвольном фиксированном порядке {1,3,5}. Запись {1,3,3,5,5} задает то же самое множество, что и запись {1,3,5}. конечное множество, заданное записью {a1,...,an}, состоит из n элементов. Это - поэлементное множество. 1-й способ 2-й способ указание некоторого свойства, которым должны обладать все элементы описываемого множества, и только они. A = x : P(x) Предикат Р - характеристический предикат множества А А = {х: х есть четное натуральное число} G = {х: х есть студент 1-го курса НАУ, поступивший в 2006 г.},
Определение множеств Предикат, задающий коллективизирующее свойство, может быть тождественно ложным. Множество, определенное таким образом, не будет иметь ни одного элемента. Его называют пустым множеством и обозначают. тождественно истинный характеристический предикат задает универсальное множество. Замечание Конкретное содержание понятия универсального множества определяется тем конкретным контекстом, в котором мы применяем теоретико-множественные идеи. Например, если мы занимаемся только различными числовыми множествами, то в качестве универсального может фигурировать множество R всех действительных чисел.
Операции над множествами Для двух множеств А и В определены новые множества, называемые объединением, пересечением, разностью симметрической разностью A B = x: x A x B, A \ B = x: x A x B, A B = (A\B) (B\A),
Операции над множествами Объединение двух множеств Диаграмма Эйлера- Венна объединение А и В есть множество всех таких x, что х является элементом хотя бы одного из множеств А, В;
Операции над множествами Транслятор Редактор связей Загрузка Выполнение программы Препроцессор Пересечением двух множеств называется новое множество пересечение А и В множество всех таких x, что х одновременно элемент А и элемент B
Операции над множествами Разностью двух множеств называется новое множество разность А \ В множество всех таких х, что х элемент A, но не элемент В
Операции над множествами Симметрической Разностью двух множеств называется новое множество A B = (A\B) (B\A), симметрическая разность А В множество всех таких x, что х элемент А, но не элемент В или х элемент В, но не элемент А.
Операции над множествами Если класс объектов, на которых определяются различные множества обозначить Ω (Универсум), то дополнением множества А называют разность
Операции над множествами соотношение с логическими операциями Пусть А = {х: Р(х)}, В = {х: Q(x)}, т.е. множество А задано посредством характеристического предиката Р, а множество В посредством характеристического предиката Q. Легко показать, что A B = x: Р(х) Q(x), A \ B = x: Р(х) ¬Q(x),
Операции над множествами В есть подмножество множества А, если всякий элемент В есть элемент А. Для обозначения используют запись: В А. Говорят также, что В содержится в А, В включено в А, А включает В (имеет место включение В А). Если А = {х: Р(х)}, В = {х: Q(x)}, то В А тогда и только тогда, когда высказывание Q(x) => P(x) тождественно истинно. множество А равно множеству В тогда и только тогда, когда А есть подмножество В и наоборот, т.е. А = В ((А В) (В А)).
Операции над множествами метод двух включений Чтобы доказать равенство двух множеств X и У, т.е. что X = Y, достаточно доказать два включения X Y и Y X, т.е. доказать, что из предположения х Х (для произвольного х) следует, что х У, и, наоборот, из предположения х Y следует, что x X.
Операции над множествами Замечание. Равенство множеств {х: Р(х)} и {х: Q(x)} означает, что предикаты Р(х) и Q(x) эквивалентны, т.е. предикат Р(х) Q(x) является тождественно истинным. # Если В А, но В А, то пишут В А и В называют строгим подмножеством (или собственным подмножеством) множества А, а символ символом строгого включения.
Операции над множествами Для всякого множества А может быть образовано множество всех подмножеств множества А. Его называют булеаном множества А и обозначают 2А: 2А = {Х:Х А}. Для булеана используют также обозначения Р(А), В(А) и ехр(А). Пример, а. Булеан множества {а, b} состоит из четырех множеств, {а}, {b}, {а, b}, т.е. 2{а, b} = {, {а}, {b}, {а, b}}. б. Булеан 2N состоит из всех возможных, конечных или бесконечных, подмножеств множества N. Так, 2N, {5} 2N, вообще для любого n множество {n} 2N, множество 1,...,n} 2N, {n:n = 2k,k = l,2,...} 2N и т.n. #
Операции над множествами свойства операций 1.А В = В А; 2.А В = В А; 3.А (В С) = (А В) С; 4. A (B С) = (A В) С; 5.A (B С) = (A В) (А С); 6.A (B С) = (A В) (А С); ____ _ _ 7.А В = А В; ____ _ _ 8.А В = А В; 9.А = А; 10. А = ; 11.A U = A; 12.А U = U; _ 13. A A = U; _ 14. A A = ; 15. А U = A; 16. А A = A; _ 17. Ā = A; 18. A \ B = A B;
Операции над множествами свойства операций 19.A B = (A B)\(A B); 20. (A B) C = A (B C); 21.A B = B A; 22. A (B C) = (A B) (A C);
Операции над множествами доказательство тождества 19 прямое включение Пусть х AВ. Тогда, согласно определению симметри- ческой разности, x (А \ В) U (В \ А). Это означает, что х (А \ В) или х (В \ А). Если х (А \ В), то х А и х В, т.е. х A U В и при этом х А В. Если же х (В \ А), то х В и х А, откуда х A B и x А B. Итак, в любом случае из х (А \ В) U (В \ А) следует х А В и х А В, т.е. x (A U В) \ (А В). Таким образом, доказано, что A B (A B)\(A B).
Операции над множествами доказательство тождества 19 обратное включение Покажем обратное включение (A B)\(A B) A B. Пусть х (A U B) \ (А В). Тогда х A B и х А В. Из x A U В следует, что ж A или x В. Если x A, то с учетом х А В имеем х B, и поэтому x А \ В. Если же x В, то опять-таки в силу x А В получаем, что х A и x В\ А. Итак, x A\В или x В\А, т.е. x (A\ B) U (B\A). Следовательно, (A B)\(A B) A B.
Кортеж. Декартово произведение понятие неупорядоченной пары Пусть А и В произвольные множества. Неупорядоченная пара на множествах А и В это любое множество {а, b}, где а A, b В или а В, b А. Если А = В, то говорят о неупорядоченной паре на множестве А. Исходя из понятия равенства множеств, можно утверждать, что неупорядоченная пара {а, b} равна неупорядоченной паре {с, d} если и только если а = с и b = d или а = d и b = с.
Кортеж. Декартово произведение понятие неупорядоченной пары В том случае, когда в неупорядоченной паре {а, b} элементы а и b совпадают, получаем, что {а, b} = {а, а}. Но такая запись, как мы условились выше, задает то же самое множество, что и {а}. Таким образом, при а = b неупорядоченная пара {а, b} вырождается" в одноэлементное множество {а}. При а b неупорядоченная пара будет двухэлементным множеством.
Кортеж. Декартово произведение понятие упорядоченной пары Упорядоченная пара на множествах А и В, обозначаемая записью (а, b), определяется не только самими элементами а А и b В, но и порядком, в котором они записаны. Если А = B, то говорят об упорядоченной паре на множестве А. Существенная роль порядка, в котором перечисляются элементы упорядоченной пары, фиксируется определением равенства упорядоченных пар. Определение 1.1. Две упорядоченные пары (а, b) и (а', b) на множествах А и В называют равными, если а = а и b = b.
Кортеж. Декартово произведение понятие упорядоченной пары Замечание 1.2. Упорядоченную пару (а, b) не следует связывать с множеством {а, b}, так как упорядоченная пара характеризуется не только составом, но и порядком элементов в ней. Более того, определение этого объекта вообще не позволяет рассматривать его как множество. Но упорядоченную пару можно определить и как множество, полагая, что упорядоченная пара (а, b) есть неупорядоченная пара {{а}, {а, b}}, включающая в себя одноэлементное множество {а} и неупорядоченную пару {а, b}. При а = b получаем (а, а) = {{а}}.
Кортеж. Декартово произведение В отличие от конечного множества {a1,...,an} кортеж (a1,..., an) на множествах А1,..., Аn характеризуется не только входящими в него элементами а1 А1,..., аn Аn, но и порядком, в котором они перечисляются. Как и для упорядоченных пар, роль порядка в кортеже фиксируется определением равенства кортежей. Определение 1.2. Два кортежа (a1,..., an) и (b1,..., bn) на множествах А1,..., Аn равны, если ai = bi, i = 1, n. Число n называется длиной кортежа (или размерностъю кортежа), а элемент аi i-й проекцией (компонентой) кортежа.
Кортеж. Декартово произведение Определение 1.3. Множество всех кортежей длины n на множествах А1,..., Аn называют декартовым (прямым) произведением множеств А1,..., Аn и обозначают A1 x... x An. Таким образом, A1 х... х An = {(ai,..., an): a1 А1,..., an An} Если все множества Аi, i = 1, n, равны между собой, то указанное декартово произведение называют n-й декартовой степенью множества А и обозначают А n. В частности, при n = 2 получаем декартов квадрат, а при n = 3 декартов куб множества А.
Кортеж. Декартово произведение свойства Декартово произведение имеет следующие свойства: 1.А х (В С) = (А х В) U (A x С); 2.А х (В С) = (А х В) (A x С); 3.А х = х A =
Кортеж. Декартово произведение доказательство 1-го свойства Если (x, y) A х (В U С), то x A и у В U С. Из того, что у В U С, следует у В или у С. Если у В, то (x, у) A х В, а если у С, то (x, у) A х С. Итак, (x, у) А х В или (x, у) А х С, т.е. (x, у) (A х B) U (А х С). Следовательно, А х (B U С) (A x B) (A x C). А х (В С) = (А х В) U (A x С)