Множества

Пример. Теперь можно приступить к реализации операции пересечения двух множеств. Напомним, что пересечение двух множеств — это множество, образованное элементами, которые одновременно принадлежат и первому, и второму множествам. Обозначается пересечение множеств A и B через $$A\cap B$$. В математических обозначениях это выглядит следующим образом: $$A\cap B=\{ x|x\in A и x\in B\}$$ . На рисунке пересечение множеств A и B обозначено штриховкой.

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

Этот предикат, наверное, будет немного проще объединения. Его мы также проведем рекурсией по первому множеству. Базис рекурсии: пересечение пустого множества с любым множеством будет пустым множеством. Шаг рекурсии так же, как и в случае объединения, разбивается на два случая в зависимости от того, принадлежит ли первый элемент первого множества второму. В ситуации, когда голова первого множества является элементом второго множества, пересечение множеств получается приписыванием головы первого множества к пересечению хвоста первого множества со вторым множеством. В случае, когда первый элемент первого множества не встречается во втором множестве, результирующее множество получается пересечением хвоста первого множества со вторым множеством.

Запишем это.

intersection([],_,[]). /*  в результате пересечения 
                    пустого множества с любым 
                    множеством получается пустое 
                    множество */
intersection([H|T1],S2,[H|T]):– 
              member3(H,S2), 
                /* если голова первого множества H 
                  принадлежит второму множеству S2 */
              !,
              intersection(T1,S2,T). 
                /* то результатом будет множество, 
                  образованное головой первого 
                  множества H и хвостом, полученным
                  пресечением хвоста первого 
                  множества T1 со вторым 
                  множеством S2 */
intersection([_|T],S2,S):–
              intersection(T,S2,S). 
                /* в противном случае результатом 
                  будет множество S, полученное 
                  объединением хвоста первого 
                  множества T со вторым 
                  множеством S2 */

Если пересечь множество [1,2,3,4] со множеством [3,4,5], то в результате получится множество [3,4].

Пример. Следующая операция, которую стоит реализовать, — это разность двух множеств. Напомним, что разность двух множеств — это множество, образованное элементами первого множества, не принадлежащими второму множеству. Обозначается разность множеств A и B через A–B или A\B. В математических обозначениях это выглядит следующим образом: $$A\setminus B=\{ x|x\in A и х\notin B\}$$ .

На рисунках разность множеств A и B ( B и A ) обозначена штриховкой.

В этой операции, в отличие от двух предыдущих, важен порядок множеств. Если в объединении или пересечении множеств поменять первый и второй аргументы местами, результат останется прежним. В то время как при A={1,2,3,4}, B={3,4,5}, A\B={1,2}, но B\A={5}.

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

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

Запишем эти рассуждения.

minus([],_,[]). /* при вычитании любого множества 
              из пустого множества получится пустое 
              множество */
minus([H|T],S2,S):–
              member3(H,S2), 
                /* если первый элемент   первого 
                  множества H принадлежит второму 
                  множеству S2*/
              !,
              minus(T,S2,S). 
                /* то результатом S будет разность 
                  хвоста первого множества T 
                  и второго множества S2 */
minus([H|T],S2,[H|S]):–
                  minus(T,S2,S). 
                /* в противном случае,   результатом 
                  будет множество, образованное 
                  первым элементом первого 
                  множества H и хвостом, полученным 
                  вычитанием из хвоста первого 
                  множества T второго множества S2 */

Можно попробовать реализовать пересечение через разность. Из математики нам известно тождество $$A\cap B=A\setminus (A\setminus B)$$. Попробуем проверить это тождество, записав соответствующий предикат, реализующий пересечение множеств, через взятие разности.

intersection2(A,B,S):–
            minus(A,B,A_B), /*A_B=A\B */
            minus(A,A_B,S). /* S = A\A_B = A\(A\B) */

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

Пример. Не помешает иметь предикат, позволяющий проверить, является ли одно множество подмножеством другого. В каком случае одно множество содержится в другом? В случае, если каждый элемент первого множества принадлежит второму множеству. Тот факт, что множество A является подмножеством множества B, обозначается через $$A\subseteq B$$. В математической записи это выглядит следующим образом: $$A\subseteq B\Leftrightarrow \forall x(x\in A \to x\in B)$$.

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

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

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

subset([],_). /* пустое множество является  
                 подмножеством любого множества */
subset([H|T],S):– /* множество [H|T] является 
                подмножеством множества S */
          member3(H,S), /* если его первый элемент H 
                       принадлежит S */
          subset(T,S). /* и его хвост T является 
                       подмножеством множества S */

Можно также определить это отношение, воспользовавшись уже определенными предикатами union и intersection.

Из математики известно, что $$A\subseteq B\Leftrightarrow A\cup B=B$$. То есть одно множество является подмножеством другого тогда и только тогда, когда их объединение совпадает со вторым множеством. Или, аналогично, $$A\subseteq B\Leftrightarrow A\cap B=A$$. То есть одно множество является подмножеством другого тогда и только тогда, когда их пересечение совпадает с первым множеством.

Запишем эти математические соотношения на Прологе.

subsetU(A,B):–
        union(A,B,B). /* объединение множеств 
            совпадает со вторым множеством */
subsetI(A,B):–
        intersection(A,B,A). 
                  /* пересечение множеств 
                    совпадает с первым множеством*/

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

Используя только что написанный предикат, реализующий отношение включения множеств, можно создать предикат, осуществляющий проверку совпадения двух множеств. Напомним, что два множества A и B называются равными, если одновременно выполнено $$A\subseteq B$$ и $$B\subseteq A$$, т.е. множество A содержится во множестве B и множество B содержится во множестве A. Другими словами, два множества равны, если все элементы первого множества содержатся во втором множестве, и наоборот. Отсюда следует, что эти множества состоят из одних и тех же элементов.

Напишем предикат, реализующий отношение равенства двух множеств.

equal(A,B):–   /* множество A совпадает 
                        со множеством B, */
        subset(A,B), /* если множество A содержится 
                    во множестве B */ 
        subset(B,A). /* и множество B является 
                    подмножеством множества A*/

Убедимся, что множество [1,2,3] и множество [3,4,5] не равны, а множества [1,2,3] и [2,1,3] совпадают.

Если множество A содержится во множестве B, причем во множестве В имеются элементы, не принадлежащие множеству А, то говорят, что А — собственное подмножество множества В. Обозначается этот факт как $$A\subset B$$.

Закодируем это отношение:

Prop_subset(A,B):–
          subset(A,B), 
          /* множество A содержится 
                     во множестве B */
          not(equal(A,B)). 
          /* множества A и B не совпадают*/

Проверим, что множество [1,3] является собственным подмножеством множества [1,2,3], в отличие от множеств [1,4] и [2,1,3].

Пример. Рассмотрим еще одну операцию на множествах. Она называется симметрическая разность и, как видно из ее названия, в отличие от обычной разности, не зависит от порядка ее аргументов. Симметрической разностью двух множеств называется множество, чьи элементы либо принадлежат первому и не принадлежат второму множеству, либо принадлежат второму и не принадлежат первому множеству. Она не столь известна, как предыдущие рассмотренные нами операции, однако тоже имеет право на существование. Обозначается симметрическая разность множеств A и B через $$A\Delta B$$. В математических обозначениях это выглядит следующим образом: $$A\Delta B=\{ x|(x\in A и x\notin B) или (x\in B и x\notin A)\}$$. В отличие от обычной разности, в симметрической разности, если поменять аргументы местами, результат останется неизменным ( $$A\Delta B=B\Delta A$$ ).

Например, при A={1,2,3,4}, B={3,4,5}, $$A\Delta B=B\Delta A=\{ 1,2,5\}$$.

Воспользуемся тем, что симметрическую разность можно выразить через уже реализованные нами операции. А именно, $$A\Delta B=(A\setminus B)\cup (B\setminus A)$$. Словесно эта формула читается так: симметрическая разность двух множеств есть разность первого и второго множеств, объединенная с разностью второго и первого множеств.

Запишем это на Прологе:

Sim_minus(A,B,SM):–
          minus(A,B,A_B), /* A_B — это разность 
                         множеств A и B */
          minus(B,A,B_A), /* B_A — это разность 
                         множеств B и A */
          union(A_B,B_A,SM). /* SM — это объединение 
                           множеств A_B и B_A */

Убедимся, что симметрическая разность множеств [1,2,3,4] и [3,4,5] равна множеству [1,2,5], а симметрическая разность множеств [3,4,5] и [1,2,3,4] равна множеству [5,1,2]. Множество [1,2,5] с точностью до порядка элементов совпадает с множеством [5,1,2]. Таким образом, мы выяснили, что результат не зависит от порядка аргументов.

Пример. Еще одна операция, которую обычно используют при работе со множествами, это дополнение. Дополнением множества обычно называется множество, чьи элементы не принадлежат исходному множеству. Обозначается дополнение множества A через A. В математических обозначениях это выглядит следующим образом: $$\overline A=\{ x|x\notin A\}$$ . Обычно имеет смысл говорить о дополнении только в ситуации, когда имеется некоторое универсальное множество, т.е. множество, которому принадлежат все рассматриваемые элементы. Оно может зависеть от решаемой задачи. Например, в качестве такого множества может выступать множество натуральных чисел, множество русских букв, множество символов, обозначающих арифметические действия и т.д.

Давайте, для определенности, возьмем в качестве универсального множества множество цифр ( {0,1,2,3,4,5,6,7,8,9} ). Напишем дополнение над этим универсальным множеством.

Воспользуемся при этом очередным тождеством, которое известно в математике. А именно, тем, что A=U\A, где символ U обозначает универсальное множество. Операция разности двух множеств у нас уже реализована.

Закодируем вышеприведенную формулу на Прологе.

supp(A,D):–
      U=[0,1,2,3,4,5,6,7,8,9],
      minus(U,A,D). /* D — это разность  
                универсального множества U
                и множества A */

Проверяем, что дополнение множества [1,2,3,4] равно множеству [0,5,6,7,8,9].

Имея дополнение, можно выразить операцию объединения через пересечение и дополнение, или, наоборот, операцию пересечения через объединение и дополнение, используя законы де Моргана ( $$A\cup B=\overline {\overline A \cap \overline B}$$ и $$A\cap B=\overline {\overline A \cup \overline B}$$ ).

Запишем эти соотношения на Прологе.

unionI(A,B,AB):–
        supp(A,A_), /* A_ — это дополнение 
                    множества A */
        supp(B,B_), /* B_ — это дополнение 
                    множества B */
        intersection(A_,B_,A_B), 
                 /* A_B — это пересечение 
                 множеств A_ и B_ */
        supp(A_B,AB). /* AB — это дополнение 
                     множества A_B */
intersectionU(A,B,AB):–
        supp(A,A_), /* A_ — это дополнение 
                   множества A */
        supp(B,B_), /* B_ — это дополнение 
                    множества B */
        union(A_,B_,A_B), /* A_B — это объединение 
                        множеств A_ и B_ */
        supp(A_B,AB). /* AB — это дополнение 
                     множества A_B */

Проверка на примерах показывает, что оба предиката работают на множествах, являющихся подмножествами универсального множества (в нашем примере это множество {0,1,2,3,4,5,6,7,8,9} ), как и ранее созданные предикаты union и intersection.

Самостоятельные задания