Множества
В данной лекции мы попробуем реализовать некоторое приближение математического понятия "множество" в Прологе. Заметим, что в Прологе, в отличие от некоторых императивных языков программирования, нет такой встроенной структуры данных, как множество. И, значит, нам придется реализовывать это понятие, опираясь на имеющиеся стандартные домены. В качестве базового домена используем стандартный списковый домен, с которым мы работали на протяжении двух последних лекций.
Итак, что мы будем понимать под множеством? Просто список, который не содержит повторных вхождений элементов. Другими словами, в нашем множестве любое значение не может встречаться более одного раза.
На самом деле я не знаю ни одной реализации понятия множества, которая бы достаточно точно соответствовала этому математическому объекту. Наше подобие множества также, по большому счету, лишь отчасти будет приближаться к "настоящему" множеству.
Нам предстоит разработать предикаты, которые реализуют основные теоретико-множественные операции.
Начнем с написания предиката, превращающего произвольный список во множество, в том смысле, в котором мы договорились понимать этот термин. Для этого нужно удалить все повторные вхождения элементов. При этом мы воспользуемся предикатом delete_all, который был создан нами ранее, в седьмой лекции. Предикат будет иметь два аргумента: первый — исходный список (возможно, содержащий повторные вхождения элементов), второй — выходной (то, что остается от первого аргумента после удаления повторных вхождений элементов).
Предикат будет реализован посредством рекурсии. Базисом рекурсии является очевидный факт: в пустом списке никакой элемент не встречается более одного раза. По правде говоря, в пустом списке нет ни одного элемента, который встречался бы в нем хотя бы один раз, то есть в нем вообще нет элементов. Шаг рекурсии позволит выполнить правило: чтобы сделать из непустого списка множество (в нашем понимании этого понятия), нужно удалить из хвоста списка все вхождения первого элемента списка, если таковые вдруг обнаружатся.
После выполнения этой операции первый элемент гарантированно будет встречаться в списке ровно один раз. Для того чтобы превратить во множество весь список, остается превратить во множество хвост исходного списка. Для этого нужно только рекурсивно применить к хвосту исходного списка наш предикат, удаляющий повторные вхождения элементов. Полученный в результате из хвоста список с приписанным в качестве головы первым элементом и будет требуемым результатом (множеством, т.е. списком, образованным элементами исходного списка и не содержащим повторных вхождений элементов).
Закодируем наши рассуждения.
list_set([],[]). /* пустой список является списком в нашем понимании */ list_set ([H|T],[H|T1]) :– delete_all(H,T,T2), /* T2 — результат удаления вхождений первого элемента исходного списка H из хвоста T */ list_set (T2,T1). /* T1 — результат удаления повторных вхождений элементов из списка T2 */
Например, если применить этот предикат к списку [1,2,1,2,3, 2,1], то результатом будет список [1,2,3].
Заметим, что в предикате, обратном только что записанному предикату list_set и переводящем множество в список, нет никакой необходимости по той причине, что наше множество уже является списком.
Теперь займемся реализацией теоретико-множественных операций, таких как принадлежность элемента множеству, объединение, пересечение, разность множеств и т.д.
При реализации этих предикатов можно было бы воспользоваться предикатами, предназначенными для работы с обыкновенными списками, но в результате их применения могут получаться списки, содержащие некоторые элементы несколько раз, даже если исходные списки были множествами, в нашем понимании этого слова.
Можно, конечно, после каждого применения теоретико-множественной операции превращать полученный список обратно во множество применением вышеописанного предиката list_set, но это было бы не очень удобно. Вместо этого мы попробуем написать каждую из теоретико-множественных операций так, чтобы в результате ее работы гарантированно получалось множество.
Итак, приступим.
В качестве реализации операции принадлежности элемента множеству вполне можно использовать предикат member3, который мы разработали в седьмой лекции, когда только начинали знакомиться со списками. Напомним, что факт принадлежности элемента x множеству A в математике принято обозначать следующим образом: x
Для того чтобы найти мощность множества, вполне подойдет предикат length, рассмотренный нами в седьмой лекции. Напомним, что для конечного множества мощность — это количество элементов во множестве.
Пример. Реализуем операцию объединения двух множеств. На всякий случай напомним, что под объединением двух множеств понимают множество, элементы которого принадлежат или первому, или второму множеству. Обозначается объединение множеств A и B через A
Рис. 9.1. Объединение множеств A и B
У соответствующего этой операции предиката должно быть три параметра: первые два — множества, которые нужно объединить, третий параметр — результат объединения двух первых аргументов. В третий аргумент должны попасть все элементы, которые входили в первое или второе множество. При этом нам нужно проследить, чтобы ни одно значение не входило в итоговое множество несколько раз. Такое могло бы произойти, если бы мы попытались, например, воспользоваться предикатом conc (который мы рассмотрели в седьмой лекции), предназначенным для объединения списков. Если бы какое-то значение встречалось и в первом, и во втором списках, то в результирующий список оно бы попало, по крайней мере, в двойном количестве. Значит, вместо использования предиката conc нужно написать новый предикат, применение которого не приведет к ситуации, в которой итоговый список уже не будет множеством за счет того, что некоторые значения будут встречаться в нем более одного раза.
Без рекурсии мы не обойдемся и здесь. Будем вести рекурсию по первому из объединяемых множеств.
Базис индукции: объединяем пустое множество с некоторым множеством. Результатом объединения будет второе множество. Шаг рекурсии будет реализован посредством двух правил. Правил получается два, потому что возможны две ситуации: первая — голова первого множества является элементом второго множества, вторая — первый элемент первого множества не входит во второе множество. В первом случае мы не будем добавлять голову первого множества в результирующее множество, она попадет туда из второго множества. Во втором случае ничто не мешает нам добавить первый элемент первого списка. Так как этого значения во втором множестве нет, и в хвосте первого множества оно также не может встречаться (иначе это было бы не множество), то и в результирующем множестве оно также будет встречаться только один раз.
Давайте запишем эти рассуждения:
union([ ],S2,S2). /* результатом объединения пустого множества со множеством S2 будет множество S2 */ union([H|T],S2,S):– member3(H,S2), /* если голова первого множества H принадлежит второму множеству S2, */ !, union(T,S2,S). /* то результатом S будет объединение хвоста первого множества T и второго множества S2 */ union([H |T],S2,[H|S]):– union(T,S2,S). /* в противном случае результатом будет множество, образованное головой первого множества H и хвостом, полученным объединением хвоста первого множества T и второго множества S2 */
Если объединить множество [1,2,3,4] со множеством [3,4,5], то в результате получится множество [1,2,3,4,5].
Пример. Теперь можно приступить к реализации операции пересечения двух множеств. Напомним, что пересечение двух множеств — это множество, образованное элементами, которые одновременно принадлежат и первому, и второму множествам. Обозначается пересечение множеств A и B через A
Рис. 9.2. Пересечение множеств 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\B={x|x
На рисунках разность множеств A и B (B и A) обозначена штриховкой.
Рис. 9.3. Разность множеств A и B
Рис. 9.4. Разность множеств В и А
В этой операции, в отличие от двух предыдущих, важен порядок множеств. Если в объединении или пересечении множеств поменять первый и второй аргументы местами, результат останется прежним. В то время как при 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
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
Предикат, реализующий данное отношение, будет иметь два параметра, оба входные. В качестве первого параметра будем указывать множество, включение которого мы хотим проверить. То множество, включение в которое первого аргумента нужно проверить, указывается в качестве второго параметра.
Решение, как обычно, будет рекурсивным. Базис рекурсии будет представлен фактом, утверждающим, что пустое множество является подмножеством любого множества. Шаг рекурсии: чтобы одно множество было подмножеством другого, нужно, чтобы его первый элемент принадлежал второму множеству (проверить это нам позволит предикат
member3, рассмотренный нами ранее в седьмой лекции), а его хвост, в свою очередь, должен быть подмножеством второго множества. Этих рассуждений достаточно, чтобы записать предикат, реализующий операцию включения.
subset([],_). /* пустое множество является подмножеством любого множества */ subset([H|T],S):– /* множество [H|T] является подмножеством множества S */ member3(H,S), /* если его первый элемент H принадлежит S */ subset(T,S). /* и его хвост T является подмножеством множества S */
Можно также определить это отношение, воспользовавшись уже определенными предикатами union и intersection.
Из математики известно, что A
Запишем эти математические соотношения на Прологе.
subsetU(A,B):– union(A,B,B). /* объединение множеств совпадает со вторым множеством */ subsetI(A,B):– intersection(A,B,A). /* пересечение множеств совпадает с первым множеством*/
Проверка на примерах показывает, что оба предиката, как и ранее созданный предикат subset, возвращают именно те результаты, какие и должны возвращать.
Используя только что написанный предикат, реализующий отношение включения множеств, можно создать предикат, осуществляющий проверку совпадения двух множеств. Напомним, что два множества A и 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
Закодируем это отношение:
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?B. В математических обозначениях это выглядит следующим образом: A?B={x|(x
Рис. 9.5. Симметрическая разность множеств А и В
Например, при A={1,2,3,4}, B={3,4,5}, A?B=B?A={1,2,5}.
Воспользуемся тем, что симметрическую разность можно выразить через уже реализованные нами операции. А именно, A?B=(A\B)
Запишем это на Прологе:
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.
В математических обозначениях это выглядит следующим образом: A={x|x
Давайте, для определенности, возьмем в качестве универсального множества множество цифр ({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
Запишем эти соотношения на Прологе.
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.
