Вернуться к списку примеров

Элементы теории множеств
(материал разработан с участием студентки ЗГУ О.Ганюк)

В предыдущем разделе Вы уже видели примеры использования списков в GAP. Список можно рассматривать как аналог массивов, используемых в некоторых других языках программирования, однако, в отличие от них, в GAP список может состоять из элементов различных типов, включая даже другие списки:
gap> list:=[1,2,true];
[ 1, 2, true ]
gap> list2:=[10,true,12,list,13];
[ 10, true, 12, [ 1, 2, true ], 13 ]

и даже может содержать пустые элементы:
gap> list[10]:=15;
15
gap> list;
[ 1, 2, true,,,,,,, 15 ]

Множества в GAP являются частными случаями списков, и не должны содержать пустых и повторяющихся элементов. Проверить, является ли список множеством в соответствии с этим требованием, можно с помощью функции IsSet:
gap> list:=[1,2,3,4,5,6,7,8,9,10];
[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
gap> IsSet(list);
true
gap> list1:=[1,2,2,2,5,6,7,8,9,10];
[ 1, 2, 2, 2, 5, 6, 7, 8, 9, 10 ]
gap> IsSet(list1);
false

Кроме того, любой список можно преобразовать в множество, удалив из него пустые и повторяющиеся элементы, с помощью функции Set:
gap> Set(list1);
[ 1, 2, 5, 6, 7, 8, 9, 10 ]
gap> list2:=[1,1,true,4,true, false];
[ 1, 1, true, 4, true, false ]
gap> Set(list2);
[ 1, 4, true, false ]

Над множествами можно выполнять стандартные операции. Например, зададим множества А и В:
gap> A:=[2,5,7,9];
[ 2, 5, 7, 9 ]
gap> B:=[1,5,7,12];
[ 1, 5, 7, 12 ]

Эти множества не равны:
gap> IsEqualSet(A,B);
false

Множество А не является подмножеством В:
gap> IsSubsetSet(A,B);
false

Мы можем очевидным образом вычислить:
а) пересечение множеств:
gap> IntersectionSet(A,B);
[ 5, 7 ]

в) объединение множеств:
gap> UnionSet(A,B);
[ 1, 2, 5, 7, 9, 12 ]

с) разность множеств:
gap> Difference(A,B);
[ 2, 9 ]

d) симметрическую разность множеств:
gap> UnionSet(Difference(A,B),Difference(B,A));
[ 1, 2, 9, 12 ]

С помощью функции Cartesian мы можем вычислить декартово произведение множеств А и В:
gap> Cartesian(A,B);
[ [ 2, 1 ], [ 2, 5 ], [ 2, 7 ], [ 2, 12 ], [ 5, 1 ], [ 5, 5 ], [ 5, 7 ],
  [ 5, 12 ], [ 7, 1 ], [ 7, 5 ], [ 7, 7 ], [ 7, 12 ], [ 9, 1 ], [ 9, 5 ],
  [ 9, 7 ], [ 9, 12 ] ]

Заметим, что для вычисления декартова произведения не требуетя, чтобы оба множества состояли из элементов одинакового типа. Например, мы можем вычислить декартово произведение числового множества на множество, состоящее из логических констант.
gap> N:=[2,5,7,9];
[ 2, 5, 7, 9 ]
gap> M:=[true, false];
[ true, false ]
gap> Cartesian(N,M);
[ [ 2, true ], [ 2, false ], [ 5, true ], [ 5, false ],
[ 7, true ], [ 7, false ], [ 9, true ], [ 9, false ] ]



Вернуться к списку примеров