next up previous
Next: 16.6 同値類(equivalence classes) Up: 16 集合 Previous: 16.4 巾集合(power set)

16.5 集合族の同等性

集合の集合(集合族 family of sets)が等しいかどうかを調べることを考える. subsetpを作ったときに,ある要素が集合の要素であるかどうかを調べるために memberを使っていたが,要素が集合の集合に対して,ある集合がそこに含ま れているかどうかを調べるset-memberを作る必要がある.
(defun set-member (s data)
  (cond
      ((null data) nil)
    ((set= s (car data)) data)
    (t (set-member s (cdr data)))))
となり,subsetpと同様に,集合を要素とする 集合のサブセットかどうかを調べるset-subsetp を作れば,
(defun set-subsetp (a b)
  (cond
      ((null a) t)
    ((set-member (car a) b)
     (set-subsetp (cdr a) b))
    (t nil)))
結局,集合を要素とする2つの集合が互いに 等しいということを調べる関数 set-set= は,

(defun set-set= (a b)
  (and (set-subsetp a b) (set-subsetp b a)))
となり,
> (set-set= '((a b) (b c)) '((c b) (b a)))
t
> (set-set= (power-set '(1 2 3))
 '(nil (1) (2) (3) (1 2) (2 3) (1 3) (1 2 3)))
t
ということになる.

generated through LaTeX2HTML. M.Inaba 平成18年5月7日