Debian Codegraph @

contrib/aci/READ-ME

raw
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.