Logical vs. intuitive or (expressibility)

That’s one way of distinguishing between the logical or (and/or) and xor (either or/er), because xor is much more intuitive to those of us who have to make value judgments on a regular basis. “Do I want X or Y?” translates to X xor Y in philosospeak.

This begs the question why logicians didn’t use the more intuitive form in the first place, especially since it matches the colloquial use of the term. Were they trying to be difficult? Did they think it made them look smarter?

The only thing I can think of is that xor might be unable to express other logical functions in terms of itself and the “and” operator (hereafter shown as “+”). So I’m going to think out loud for a bit on the expressibility of xor (hereafter “/”), because that sounds like more fun than simply reading up on the subject.

(Coincidentally, I just noticed that “hereafter” is the perfect modifier for value assignments in an English-based logical language. E.g. “Int x := 3;” becomes “The integer x is hereafter 3.”)


Well, I got bored of trying to brute force the idea, so I looked it up. Turns out,

Although the operators \wedge (conjunction) and \lor (disjunction) are very useful in logic systems, they fail a more generalizable structure in the following way:
The systems (\{T, F\}, \wedge) and (\{T, F\}, \lor) are monoids. This unfortunately prevents the combination of these two systems into larger structures, such as a mathematical ring.
However, the system using exclusive or (\{T, F\}, \oplus) is an abelian group. The combination of operators \wedge and \oplus over elements \{T, F\} produce the well-known field F_2. This field can represent any logic obtainable with the system (\land, \lor) and has the added benefit of the arsenal of algebraic analysis tools for fields.
More specifically, if one associates F with 0 and T with 1, one can interpret the logical “AND” operation as multiplication on F_2 and the “XOR” operation as addition on F_2:
\begin{matrix} r = p \land q & \Leftrightarrow & r = p \cdot q \pmod 2 \\ \\ r = p \oplus q & \Leftrightarrow & r = p + q \pmod 2 \\ \end{matrix}
Using this basis to describe a boolean system is referred to as algebraic normal form

Exclusive Or; Relation to Modern Algebra

I think it would be far better to use “and” and “or” (exclusive), seeing as the colloquial “X and/or Y” just means “(X and Y) or (X or Y)”.

About Aeoli Pera

Maybe do this later?
This entry was posted in math. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s