operation terminology for Boolean algebras, logic, set theory, and computer science
Daniel J. Greenhoe
{true,false}x{true,false}-->{true,false}. These 16 operations can all
be represented using the logic operations of disjunction ("or"),
conjunction ("and"), and negation ("not"). Using these
representations, all 16 operations can be generalized to Boolean
algebras using the equivalent Boolean algebra/lattice operations of
join, meet, and complement. In addition to Boolean algebras, the 16
operations can also have equivalent operations in set theory where the
logic operations simply define the set operations as in
A union B = { x in X | (x in A) disjunction (x in B) }
A intersect B = { x in X | (x in A) conjunction (x in B) }
etc.
Computer science also makes use of some of the 16 logic operations,
where disjunction=or, conjunction=and, etc.
So, there are four fields (Boolean algebra, logic, set theory,
computer science) that all use essentially the same operations, but
sometimes call them different names. My question is about the proper
names for the operations in these different fields.
Below is an incomplete list of each operation along with a name for
the operation in each field. Could someone help me complete the list?
Suggest more standard names? Good references would be especially
appreciated.
Many thanks in advance,
Dan
0000
ba: greatest lower bound
logic: false
sets: empty set
cs: zero
0001
ba: Sheffer stroke
logic: joint denial
sets: ?
cs: nor
0010
ba: exception
logic: inhibit x
sets: difference
cs: ?
0011
ba: complement
logic: negation
sets: complement
cs: not
0100
ba: adjunction
logic: inhibit y
sets: ?
cs: ?
0101
ba: complement
logic: negation
sets: complement
cs: not
0110
ba: ?
logic: ?
sets: symmetric difference
cs: exclusive-or
0111
ba: ?
logic: alternate denial
sets: ?
cs: nand
1000
ba: meet
logic: conjuction
sets: intersection
cs: and
1001
ba: equivalence
logic: equivalence
sets: equivalence
cs: equivalence
1010
ba: ?
logic transfer y
sets: ?
cs: ?
1011
ba:
logic: implies
sets:
cs:
1100
ba:
logic: transfer x
sets:
cs:
1101
ba:
logic: implied by
sets:
cs:
1110
ba: join
logic: disjunction
sets: union
cs: or
1111
ba: least upper bound
logic: true
sets: universal set one
cs:
References:
Shiva (1998): Introduction to Logic Design,
http://books.google.com/books?vid=ISBN0824700821&pg=PA83
Givant and Halmos (2009): Introduction to Boolean Algebras,
http://books.google.com/books?vid=ISBN0387402934&pg=PA32
Sheffer, Henry Maurice: A set of five independent postulates for
Boolean algebra, with
application to logical constants. Transactions of the American
Mathematical Society, 14 October
1913, Nr. 4, 481–488 ⟨URL: http://www.jstor.org/stable/1988701⟩
Whitesitt (1995): Boolean Algebra and Its Applications,
http://books.google.com/books?vid=ISBN0486684830&pg=PA69
Quine (1979): Mathematical Logic,
http://books.google.com/books?vid=ISBN0674554515&pg=PA45
Mitch Harris
> 0000
> ba: greatest lower bound
> logic: false
> sets: empty set
> cs: zero
for ba, 'greatest lower bound' is the same as 'meet'. 0000 is rather
the constant like 'false' (it's not called false in ba?), it might be
called 'bottom' (respectively for 1111: 'lub' = 'join', 'top')
> 0110
> ba: ?
> logic: ?
> sets: symmetric difference
> cs: exclusive-or
not equal ?
logic: exclusive-or?
> 1011
> ba:
> logic: implies
> sets:
> cs:
sets: difference, A - B ?
> 1100
> ba:
> logic: transfer x
> sets:
> cs:
projection?
> 1101
> ba:
> logic: implied by
> sets:
> cs:
set: difference again
> 1110
> ba: join
> logic: disjunction
> sets: union
> cs: or
least upper bound, lub?
> 1111
> ba: least upper bound
> logic: true
> sets: universal set one
> cs:
top?
try google/wikipedia for corroboration.
disclaimer: training in CS.
--
Mitch
Jan Burse
There is kind of danger in comparing sets with boolean algebras.
For example in set theory, the general complement is not defined.
From a set A, we cannot form the set:
A^C (superscript c indicates complement)
There is a simple reason. If it were always defined we could form
for example the following set:
V = 0^C (The set of all sets)
Which does not exist in ZFC. All one can savely do in set theory
is we can form e relative complement, which exists by the
separation axiom:
B \ A := {x in B | x not in A }
The above holds for ZFC, other set theories might have different
restrictions on the complement.
Maybe a deeper reason that there are problems with the
complement is that set theories have a productive operator.
Namely the power-set operator, which is not found in a
boolean algebra.
A further source might be another axiom of set theory,
namely that every set A has a completion U A. Also not
found in boolean algebras.
Best Regards
Daniel J. Greenhoe schrieb:
Paul E. Black
> There are a total of 2^4=16 binary operations on the logical set
>
> So, there are four fields (Boolean algebra, logic, set theory,
> computer science) that all use essentially the same operations, but
> sometimes call them different names. My question is about the proper
> names for the operations in these different fields.
>
> Below is an incomplete list of each operation along with a name for
> the operation in each field. Could someone help me complete the list?
>
> 0000
> ba: greatest lower bound
> logic: false
> sets: empty set
> cs: zero
constant zero
> 1111
> ba: least upper bound
> logic: true
> sets: universal set one
> cs:
constant one
-paul-
Richard Harter
<janb...@fastmail.fm> wrote:
>Hi
>
>There is kind of danger in comparing sets with boolean algebras.
>For example in set theory, the general complement is not defined.
> From a set A, we cannot form the set:
>
> A^C (superscript c indicates complement)
>
>There is a simple reason. If it were always defined we could form
>for example the following set:
>
> V = 0^C (The set of all sets)
>
>Which does not exist in ZFC. All one can savely do in set theory
>is we can form e relative complement, which exists by the
>separation axiom:
>
> B \ A := {x in B | x not in A }
>
>The above holds for ZFC, other set theories might have different
>restrictions on the complement.
>
>Maybe a deeper reason that there are problems with the
>complement is that set theories have a productive operator.
>Namely the power-set operator, which is not found in a
>boolean algebra.
>
>A further source might be another axiom of set theory,
>namely that every set A has a completion U A. Also not
>found in boolean algebras.
>
>Best Regards
There are set theories in which there is a universal set and
complement, e.g., Quines NF. ZFC is not the totality of set
theory and mathematical logic.
More importantly, one really should distinguish between general
set theory (sets are members of sets) and set algebra (a domain
of atoms are members of sets.)
Richard Harter, c...@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.
Marko Amnell
On a related note, Dover reissued J. Barkley Rosser's
_Logic for Mathematicians_ last year:
http://store.doverpublications.com/0486468984.html
The book is based on Quine's New Foundations system
(Rosser avoids calling NF "set theory"; he only
calls Zermelo-style systems "set theory"). Rosser
claims for his book:
"By using techniques invented since its writing,
we have succeeded in condensing most of
'Principia Mathematica''s three large volumes
into the present text." (Preface, p. vii).
On page 206 he issues this warning:
"There is a warning in this. The problem of the
exact relationship between classes and
statements is a difficult and subtle one
and must be approached quite warily. Undoubtedly
the last word on the subject has not yet been
said. All the present suggestions for avoiding
the paradoxes retain a tinge of artificiality.
Certainly the theory of types is artificial.
In Zermelo set theory, the distinction between
sets and nonsets is irksome, and the various
criteria for deciding between sets and
nonsets not intuitively very natural.
"In the system of the present text, Quine's
New Foundations, it is irksome that not all
conditions determine classes, and the criterion
of stratification for deciding which condition
shall determine classes is not intuitively
natural.
"Both set theory and Quine's New Foundations
reproduce mathematical reasoning with a
remarkably close approximation to the unhampered
methods in use before the discovery of the
paradoxes. Certain regions of the theory of
cardinals and ordinals are too near the paradoxes
to survive unchanged, but it has been possible
to amputate the known paradoxes with remarkably
little injury to the main body of mathematics."
>
> More importantly, one really should distinguish between general
> set theory (sets are members of sets) and set algebra (a domain
> of atoms are members of sets.)
>
> Richard Harter, c...@tiac.nethttp://home.tiac.net/~cri,http://www.varinoma.com
> Save the Earth now!!
> It's the only planet with chocolate.- Hide quoted text -
>
> - Show quoted text -
Daniel J. Greenhoe
> ...
> So, there are four fields (Boolean algebra, logic, set theory,
> computer science) that all use essentially the same operations, but
> sometimes call them different names. My question is about the proper
> names for the operations in these different fields.
Thank you to everyone for your help with my terminology question. I
thought Mitch Harris had some good suggestions. In particular, I have
adopted the following (with slight modification) of his suggestions
for use in a project I am working on:
0000: ba = bottom
1111: ba = top
1100: ba = projection x
1010: ba = projection y
On Feb 3, 8:33 am, Jan Burse <janbu...@fastmail.fm> wrote:
> There is kind of danger in comparing sets with boolean algebras.
I think my original choice of the term "set theory" was a poor one. I
have changed this to "algebra of sets". While I am certainly no expert
in set theory, I might think that this term could be fairly safely
used in relation to Boolean algebras. One reason for this is the
"Stone Representation Theorem" which states that a lattice L is a
Boolean algebra if and only if L is isomorphic to an algebra of sets.
Here are some references for this theorem:
1. Levy (2002): Basic Set Theory, page 257
http://books.google.com/books?vid=ISBN0486420795&pg=PA257
2. Gr¨atzer (1998): General Lattice Theory, page 85
http://books.google.com/books?vid=ISBN0817652396&pg=PA85
3. Joshi (1989): Foundations of Discrete Mathematics, page 224
http://books.google.com/books?vid=ISBN8122401201&pg=PA224
4. Stone (1936): Transactions of the American Mathematical Society
volume 40
http://www.jstor.org/stable/1989664
Thank you again to everyone :)
Dan (original poster)
On Feb 3, 1:17 am, "Daniel J. Greenhoe" <dgreen...@yahoo.com> wrote:
> So, there are four fields (Boolean algebra, logic, set theory,
> computer science) that all use essentially the same operations, but
> sometimes call them different names. My question is about the proper
> names for the operations in these different fields.
> Shiva (1998): Introduction to Logic Design,http://books.google.com/books?vid=ISBN0824700821&pg=PA83
>
> Givant and Halmos (2009): Introduction to Boolean Algebras,http://books.google.com/books?vid=ISBN0387402934&pg=PA32
Daniel J. Greenhoe
> So, there are four fields (Boolean algebra,
> logic, set theory, computer science)
> that all use essentially the same operations,
> but sometimes call them different names.
> My question is about the proper names
> for the operations in these different fields.
On Feb 5, 5:51 am, "Daniel J. Greenhoe" wrote:
> Thank you to everyone for your help with my
> terminology question.
I have put a proposed table of operator terminology as well as symbols
in a 1 page pdf file (43kBytes) and put it here:
http://banyan.cm.nctu.edu.tw/~dgreenhoe/sro/symbols.pdf
If anyone has any interest in these things and would like to give
feedback/suggestions, that would be great.
Note to TeX users: The document is typeset using XeLaTeX. I avoided
using the mathabx library because of past difficulties. Typesetting
suggestions are also welcome.
Dan