Xor
Xor[bool,..]
...returns True if an odd number of its Boolean arguments, ("bool,.."), are True and False otherwise.
Not[Xor][bool,..]
...returns True if an even, nonzero number of its Boolean arguments, ("bool,.."), are True and False otherwise.
Xor[{a1, b1, .., i1}, {a2, b2, .., i2},
.., {aj, bj, .., ij}]
...is equivalent to...
{Xor[a1, a2,..., aj], Xor[b1, b2,..., bj],..., Xor[i1, i2,..., ij]}
Similarly...
Not[Xor][{a1, b1, .., i1}, {a2, b2, ..,
i2},
.., {aj, bj, .., ij}]
...is equivalent to...
{Not[Xor][a1, a2,..., aj], Not[Xor][b1, b2,..., bj],..., Not[Xor][i1, i2,..., ij]}
With the plural argument, sets,
Xor or Not[Xor]
generate Sets with
elements in an odd
or an even, nonzero number
of sets.
Formally:
Xor[sets]
...matches elements in an odd number of elements in "sets".
Not[Xor][sets]
...matches elements in an even, nonzero
number of elements in sets.
See English definition for "xor" and "complement".
(1a)
Xor[bools]
...returns True if an odd number of
the bools are True,
and False otherwise.
Conversely...
(1b)
Not[Xor][bools]
...returns True
if an even,
nonzero number of
the bools are True,
and False
otherwise.
(1c)
Not[Xor][]
...returns unchanged. In other words, the above Expression is intentionally unassigned.
By contrast,
Not[Xor[bools]]
...returns True
if zero or any
even number of
the bools are True,
and False
otherwise.
Unlike And[...]
or Or[...] constructions, each
element in Xor[bools]
& Not[Xor][bools]
constructions are evaluated
before returning a result.
Xor and Not[Xor] interpret Boolean List arguments as Logic Matrixes as follows:
(2a) Xor[{a1, b1, .., i1}, {a2, b2, .., i2}, .., {aj, bj, .., ij}]
...is equivalent to...
(3a) {Xor[a1, a2,..., aj], Xor[b1, b2,..., bj],..., Xor[i1, i2,..., ij]}
(2b) Not[Xor][{a1, b1, .., i1}, {a2, b2, .., i2}, .., {aj, bj, .., ij}]
...is equivalent to...
(3b) {Not[Xor][a1, a2,..., aj], Not[Xor][b1, b2,..., bj],..., Not[Xor][i1, i2,..., ij]}
If the List
arguments fed to Xor or Not[Xor] are
not the same length, the above Xor-Matrix
interpretation
will not be elicited.
...defines the Set
matching an odd number of elements in the setii.
(4b)
Not[Xor][setii__Set]
...defines the Set
of elements matching a nonzero,
even number
of elements in the setii.
Specifically, if an element is not
in any of the setii, or if it is in an odd number of the setii,
then (4b) returns False.
However...
(4c)
Not[Xor][]
...is intentionally unassigned.
By contrast, Not[Xor[]]
evaluates as True.
Not[Xor[setii__Set]]
The above Expression
is the PatternSet
matching zero
or an even number
of elements in the setii. Membership in the above is
determined by what
it is not; an element matches if it is not in an odd
number of the setii. By contrast, Not[Xor][setii__Set] (4b)
actually generates the Set containing elements in a nonzero, even number of the setii.
Several basic results follow directly from the
above definitions.
In the following, set, is a Set, and sets
is one or more Sets.
(5a)
Xor[set] == set
Why? Because every element in set is in an
odd number of the "Sets"
in the one "set" argument.
Xor[sets] & Not[Xor][sets] both "flatten" out as follows:
(6a)
Xor[set, sets]
== Xor[set, Xor[sets]]
(6b) Not[Xor][set, sets] == Not[Xor][set, Not[Xor[sets]]]
These two proofs are left to the reader.
Note that in (6b), the last argument on the right-hand-side is Not[Xor[sets]] and not Not[Xor][sets]. This
allows (6b) to be defined if "sets" is empty, but otherwise
the choice between Not[Xor[sets]]
and Not[Xor][sets]
is irrelevant with respect to symbolic logic manipulations.
Nonetheless, Not[Xor[sets]]
and Not[Xor][sets]
are quite different; the first matches elements not in Xor[sets], while Not[Xor][sets] matches actual elements
in sets
that are not
in Xor[sets].
There are logical Set identities
interelating the `Logic`
keywords. Set union, for example,
can be
realized with Xor and Not[Xor] constructions as follows.
(7)
Or[sets] == Xor[Xor[sets], Not[Xor][sets]]
The proof is left to the reader.
Xor can be used to construct set complement.
Complement[set, sets,.. ] gives the elements
in set
which are not in any of the "sets,..".
The verbal definition for Set-complement can be
written as follows...
Complement[set_PatternSet,
sets__PatternSet] = And[set, Not[Or[sets]]]
The above construction is a Logical
Pattern
Set, and not an actual Set.
The actual Set
containing elements matching the same elements as the above can be generated as follows:
(8)
Complement[set_Set,
sets__Set]
=
(* The Complement
Construction *)
Not[Xor[
(* (a)
*)
(* (b) *)
Xor[set, Xor[sets]],
Xor[set , Not[Xor][sets]]
]
]
The reason Not[Xor][...]
constructions are used in the above, rather
then Not[Xor[...]],
is that in both cases, that "Not[Xor[...]]"
is a boundless Logical Pattern
Set, (defined by what it is not), whereas
Not[Xor][...] is an actual, itemizable Set. (8)
is both a logic
identity
and the outline for an efficient algorithm to generate Set
complements.
Xor[sets] has
elements in 1, 3,.. of sets,
and
Not[Xor][sets] has
elements in 2, 4,.. sets.
An element that is not
in "Xor[sets]" and not in "Not[Xor][sets]", is not in
any of the sets. (See (7).)
And[sets__Set]
matches elements in the intersection of sets.
This is distinct from actually generating
the Set
intersection.
This can be computed with Not[Xor][...]
elegantly as follows:
SetIntersect[set_Set]
= set
SetIntersect[___Set,
Set[], ___Set]
= Set[]
SetIntersect[set1_Set, set2_Set] = Not[Xor][set1, set2]
SetIntersect[set1_Set,
set2_Set,
sets__Set] = SetIntersect[SetIntersect[set1, set2], sets]
exclusive OR
...A logic element with two inputs and one output.
The output is true if either of the two inputs is true, but is not if
both are true.
See Mathematica's Xor[...]
function.
Complement n.
1. a That which fills up or completes.
b The quantity or number required to fill a thing or make it complete; full allowance.
c That which is required to supply a deficiency, to make perfect, or to complete a symmetrical whole; one of two mutually completing parts or fact of being complete.
Boolean Logic. The set with
elements from set1 found
in
zero or any even number of other sets. This
set is called the complement to
set1.
In (this context,) the "Exclusive-Or" function, (Xor[set1
, sets]), and the complement are the
same. See 1.c. above.
(c)
2004-2007 by
John Van Wie Bergamini
All rights reserved.