Logical Operators, Truth Table, Unicode

Perm url with updates: http://xahlee.org/math/logical_operators.html

Logical Operators, Truth Table, Unicode

Xah Lee, 2010-12-14

Added a bunch symbols to Emacs xmsi-mode for Math Symbols Input.

⨯ ∮ ∲ ∳ ↦ ↤ ¬ ∧ ∨ ⊻ ⊽ ⊼ ⊻̅. Note that the 「」 is for vector/matrix multiplication. Its unicode name is “VECTOR OR CROSS PRODUCT”. It is different from 「×」 (MULTIPLICATION SIGN). It appears, that by tradition, the vector cross sign should be rendered smaller than the normal multiplication sign. This is so in Mathematica and STIX font.

Those integrals with circles are Contour integral (aka line integral, path integral). One of the symbol has a clockwise circle, the other anti-clockwise.

Truth Table and Possible Logical Operators

Also, been working on adding full set of logical operators. Here's some interesting notes. The following is the definition for “and” and “or”.

And
0 ⊕ 0 = 0
0 ⊕ 1 = 0
1 ⊕ 0 = 0
1 ⊕ 1 = 1
Or
0 ⊕ 0 = 0
0 ⊕ 1 = 1
1 ⊕ 0 = 1
1 ⊕ 1 = 1

Taking their results in a condensed way, we can say “And” can be given a code 「0001」 and “Or” can be given 「0111」. These can be considered as 4 digit binary numbers. So, number of possible logical function with 2 parameters are the same as total number of 4 digit binary numbers, and that's 16. Let's see the complete list of what they are, and what they are named, and their symbols, if any.

Truth Table; All Possible Logical Operators

DefinitionCodeNameSymbolComment
0⊕0=0;0⊕1=0;1⊕0=0;1⊕1=00000false
0⊕0=0;0⊕1=0;1⊕0=0;1⊕1=10001and
0⊕0=0;0⊕1=0;1⊕0=1;1⊕1=00010
0⊕0=0;0⊕1=0;1⊕0=1;1⊕1=10011
0⊕0=0;0⊕1=1;1⊕0=0;1⊕1=00100
0⊕0=0;0⊕1=1;1⊕0=0;1⊕1=10101
0⊕0=0;0⊕1=1;1⊕0=1;1⊕1=00110xor
0⊕0=0;0⊕1=1;1⊕0=1;1⊕1=10111or
0⊕0=1;0⊕1=0;1⊕0=0;1⊕1=01000nor
0⊕0=1;0⊕1=0;1⊕0=0;1⊕1=11001xnor⊻̅The char is a combining char in unicode.
0⊕0=1;0⊕1=0;1⊕0=1;1⊕1=01010
0⊕0=1;0⊕1=0;1⊕0=1;1⊕1=11011
0⊕0=1;0⊕1=1;1⊕0=0;1⊕1=01100
0⊕0=1;0⊕1=1;1⊕0=0;1⊕1=11101
0⊕0=1;0⊕1=1;1⊕0=1;1⊕1=01110nand
0⊕0=1;0⊕1=1;1⊕0=1;1⊕1=11111true

It is interesting to note that half of them don't have a name. Wikipedia on Logical connective gives some name to some of them. For example, the “0000” is just “false”, the “1111” is “true”, the “1101” is “if/then”. Though, much of these names are rather forced and don't make much sense. First of all, remember we are dealing with functions of 2 parameters (so-called “binary operators”). The term “true” isn't usually thought of as a binary operator, and the “if then” and “not” doesn't make sense here neither.

No symbol for “xnor”

Also interesting, that there's no symbol for “xnor” in unicode. (See: Math Symbols in Unicode.) Logically, it should be a symbol 「⊻」 with a bar above it, like this 「⊻̅」 (the “v” and the top bar should not be connected). In Mathematica, such symbol is used. (you can create such char by unicode spec thru the method of Combining character (char composition).)

Functional Completeness

Also, i learned the term Functional completeness. Quote:

In logic, a functionally complete set of logical connectives or Boolean operators is one which can be used to express all possible truth tables by combining members of the set into a Boolean expression.[1][2] A well known complete set of connectives is { AND, OR, NOT }, consisting of binary conjunction, binary disjunction and negation. The set consisting only of the binary operator NAND is also functionally complete.

In a context of propositional logic, functionally complete sets of connectives are also called (expressively) adequate.[3]

Here's a formal definition given:

Given the Boolean domain B = {0,1}, a set F of Boolean functions ƒi: Bni → B is functionally complete if the clone on B generated by the basic functions ƒi contains all functions ƒ: Bn → B, for all strictly positive integers n ≥ 1. In other words, the set is functionally complete if every Boolean function that takes at least one variable can be expressed in terms of the functions ƒi. Since every Boolean function of at least one variable can be expressed in terms of binary Boolean functions, F is functionally complete if and only if every binary Boolean function can be expressed in terms of the functions in F.

The definition above is a bit hard to understand due to its use of jargons. (i don't know what “clone” means in universal algebra (and if you look into that article, it's again esoteric, incomprehensible).) The definition is also quite general. Also, am not sure this particular definition on Wikipedia is good or well-known one. However, the concept is quite simple. Here's a simplified version for our purposes:

A set (L) of binary logical operators are “functional complete” if the semantic of any of the 16 possible logical operator can be expressed by a combination of operators in the set L.

We know that the total number of possible binary function in the binary space {1,0} is 16, from the truth table above, and by convention 6 of them have names and widely used. Others are not used much.

So, a functionally complete set of function is one that any of the possible function in truth table can be expressed by a combination of the functions in the set.

According to Wikipedia, one of the functionally complete set of function is just one single function the nand by itself. Let's see how it can express all possible functions.

First, remember that nand is defined like this: 「0⊼0=1; 0⊼1=1; 1⊼0=1; 1⊼1=0」.

The first function we'll call it “f0000”, we need 「0⊕0=0; 0⊕1=0; 1⊕0=0; 1⊕1=0」.

incomplete. Will work on this later.

Was this page useful? If so, please do donate $3, thank you donors!

Popular posts from this blog

11 Years of Writing About Emacs

does md5 creates more randomness?

Google Code shutting down, future of ErgoEmacs