| 1 |
|
| 2 |
============================================================================== |
| 3 |
DESCIPTION: Generalizing an associative and commutative operation |
| 4 |
with identity to finite sets. |
| 5 |
AUTHOR: Ching-Tsun Chou |
| 6 |
DATE: Tue Oct 6 14:47:00 PDT 1992 |
| 7 |
============================================================================== |
| 8 |
|
| 9 |
File "aci.ml" contains the definitions and theorems for generalizing |
| 10 |
an associative and commutative operation "op" with identity "id" |
| 11 |
to finite sets. More precisely, a constant |
| 12 |
|
| 13 |
ACI_OP : (** -> ** -> **) -> ** -> (* -> **) -> (* -> bool) -> **" |
| 14 |
|
| 15 |
is specified (via constant specification) such that |
| 16 |
|
| 17 |
|- ? ACI_OP : (** -> ** -> **) -> ** -> (* -> **) -> (* -> bool) -> ** . |
| 18 |
! op id . ASSOC_COMM_ID op id ==> |
| 19 |
( ! f . ACI_OP op id f { } = id ) /\ |
| 20 |
( ! f s x . FINITE s ==> |
| 21 |
( ACI_OP op id f (x INSERT s) = (x IN s) => (ACI_OP op id f s) |
| 22 |
| (op (f x) (ACI_OP op id f s)) ) ) |
| 23 |
|
| 24 |
where ASSOC_COMM_ID has the obvious meaning. Summation and product |
| 25 |
over sets can now be defined using ACI_OP: |
| 26 |
|
| 27 |
|- set_SUM = ACI_OP $+ 0 |
| 28 |
|- set_PROD = ACI_OP $* 1 |
| 29 |
|
| 30 |
Maximum (minimum) can also be so generalized if there is a least |
| 31 |
(greatest) element in the type. |
| 32 |
|
| 33 |
The basic ideas were stolen from Tom Melham's definition of cardinality |
| 34 |
(CARD) in the new `pred_sets` library. I would appreciate any comments. |