To help understanding combinations of boolean operators: Truth table – Wikipedia
Posted by jpluimers on 2018/10/04
Most software developers know they exist, but some (including me) find them hard to visualise, especially for combinations of operators, or for less common operators: the Truth table – Wikipedia.
The common operators that everyone seems to understand are these:
- logical
true - logical
false - logical
negation - logical
and - logical
or - logical
xor
It becomes harder with a series of combinations, for instance series of and (not ...) and (not ...) and (not ...) – not to be confused with nand, similarly or (not ...) or (not ...) or (not ...) – not to be confused with nor, which both can be transformed according to the De Morgan’s laws – Wikipedia:
In set theory and Boolean algebra, these are written formally as
Using truth tables
It helps to extend simple truth columns with intermediate results into complete results, so lets look at the two examples tabulated in …
A series of (not p) or (not q) is equivalent with NAND: not (p and q)
Logical NAND
The logical NAND is an operation on two logical values, typically the values of two propositions, that produces a value of false if both of its operands are true. In other words, it produces a value of true if at least one of its operands is false.
The truth table for p NAND q (also written as p ↑ q, Dpq, or p | q) is as follows:
Logical NAND p q p ↑ q T T F T F T F T T F F T It is frequently useful to express a logical operation as a compound operation, that is, as an operation that is built up or composed from other operations. Many such compositions are possible, depending on the operations that are taken as basic or “primitive” and the operations that are taken as composite or “derivative”.
In the case of logical NAND, it is clearly expressible as a compound of NOT and AND.
The negation of a conjunction: ¬(p ∧ q), and the disjunction of negations: (¬p) ∨ (¬q) can be tabulated as follows:
p q p ∧ q ¬(p ∧ q) ¬p ¬q (¬p) ∨ (¬q) T T T F F F F T F F T F T T F T F T T F T F F F T T T T
A series of(not p) and (not q) is equivalent with NOR: not (p or q)
Logical NOR
The logical NOR is an operation on two logical values, typically the values of two propositions, that produces a value of true if both of its operands are false. In other words, it produces a value of false if at least one of its operands is true. ↓ is also known as the Peirce arrowafter its inventor, Charles Sanders Peirce, and is a Sole sufficient operator.
The truth table for p NOR q (also written as p ↓ q, or Xpq) is as follows:
Logical NOR p q p ↓ q T T F T F F F T F F F T The negation of a disjunction ¬(p ∨ q), and the conjunction of negations (¬p) ∧ (¬q) can be tabulated as follows:
p q p ∨ q ¬(p ∨ q) ¬p ¬q (¬p) ∧ (¬q) T T T F F F F T F T F F T F F T T F T F F F F F T T T T
Wikipedia then continues to explain De Morgan’s laws:
Inspection of the tabular derivations for NAND and NOR, under each assignment of logical values to the functional arguments p and q, produces the identical patterns of functional values for ¬(p ∧ q) as for (¬p) ∨ (¬q), and for ¬(p ∨ q) as for (¬p) ∧ (¬q). Thus the first and second expressions in each pair are logically equivalent, and may be substituted for each other in all contexts that pertain solely to their logical values.
16 truth functions
Another difficulty is that there are 16 possible truth functions of two binary variables as described by these two tables from Truth table: Binary operations – Wikipedia.
First the row-oriented table:
Here is an extended truth table giving definitions of all possible truth functions of two Boolean variables P and Q:[note 1]
p q F0 NOR1 Xq2 ¬p3 ↛4 ¬q5 XOR6 NAND7 AND8 XNOR9 q10 if/then11 p12 then/if13 OR14 T15 T T F F F F F F F F T T T T T T T T T F F F F F T T T T F F F F T T T T F T F F T T F F T T F F T T F F T T F F F T F T F T F T F T F T F T F T Com ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ L id F F T T T,F T F R id F F T T T,F T F where
- T = true.
- F = false.
- The Com row indicates whether an operator, op, is commutative – P op Q = Q op P.
- The L id row shows the operator’s left identities if it has any – values I such that I op Q = Q.
- The R id row shows the operator’s right identities if it has any – values I such that P op I = P.[note 2]
The four combinations of input values for p, q, are read by row from the table above. The output function for each p, q combination, can be read, by row, from the table.
Then the column-oriented table which – in addition to the operator number – also has the name:
The following table is oriented by column, rather than by row. There are four columns rather than four rows, to display the four combinations of p, q, as input.
p: T T F F
q: T F T FThere are 16 rows in this key, one row for each binary function of the two binary variables, p, q. For example, in row 2 of this Key, the value of Converse nonimplication (‘{\displaystyle \nleftarrow }
‘) is solely T, for the column denoted by the unique combination p=F, q=T; while in row 2, the value of that ‘{\displaystyle \nleftarrow }
2: F F T F
and the 16-row[3] key is
[3] operator Operation name 0 (F F F F)(p, q) ⊥ false, Opq Contradiction 1 (F F F T)(p, q) NOR p ↓ q, Xpq Logical NOR 2 (F F T F)(p, q) ↚ p ↚ q, Mpq Converse nonimplication 3 (F F T T)(p, q) ¬p, ~p ¬p, Np, Fpq Negation 4 (F T F F)(p, q) ↛ p ↛ q, Lpq Material nonimplication 5 (F T F T)(p, q) ¬q, ~q ¬q, Nq, Gpq Negation 6 (F T T F)(p, q) XOR p ⊕ q, Jpq Exclusive disjunction 7 (F T T T)(p, q) NAND p ↑ q, Dpq Logical NAND 8 (T F F F)(p, q) AND p ∧ q, Kpq Logical conjunction 9 (T F F T)(p, q) XNOR p If and only if q, Epq Logical biconditional 10 (T F T F)(p, q) q q, Hpq Projection function 11 (T F T T)(p, q) p → q if p then q, Cpq Material implication 12 (T T F F)(p, q) p p, Ipq Projection function 13 (T T F T)(p, q) p ← q p if q, Bpq Converse implication 14 (T T T F)(p, q) OR p ∨ q, Apq Logical disjunction 15 (T T T T)(p, q) ⊤ true, Vpq Tautology
The verbose version of the De Morgan’s laws
The rules can be expressed in English as:
- the negation of a disjunction is the conjunction of the negations; and
- the negation of a conjunction is the disjunction of the negations;
or
- the complement of the union of two sets is the same as the intersection of their complements; and
- the complement of the intersection of two sets is the same as the union of their complements.
A different link containing the boolean gate symbols
[WayBack] Boolean Algebra Truth Tables for Logic Gate Functions Boolean Algebra Truth Tables for Digital Logic Gate Functions, their Descriptions and the Basic Truth Tables used in Digital Electronics
So I borrowed their symbols and put them in this list:
–jeroen
PS: Rudy Velthuis makes a very valid comment about bitwise operators for integer math (he used it in his big integer implementation).
Some background links when you want to get that route:
- [WayBack] DelphiBigNumbers/Velthuis.BigIntegers.pas at master · rvelthuis/DelphiBigNumbers · GitHub
- Bitwise operation – Wikipedia: NOT: If two’s complement arithmetic is used, then
NOT x = -x − 1. - Ones’ complement – Wikipedia has both positive and negative zero
- Two’s complement – Wikipedia has one zero
- Method of complements – Wikipedia
- [Archive.is] Synthesizing arithmetic operations using bit-shifting tricks
- [WayBack] Signed Binary Numbers
- [WayBack] A Tutorial on Data Representation – Integers, Floating-point numbers, and characters: 3.8 Decoding 2’s Complement Numbers
- Check the sign bit (denoted as
S). - If
S=0, the number is positive and its absolute value is the binary value of the remaining n-1 bits. - If
S=1, the number is negative. you could “invert the n-1 bits and plus 1″ to get the absolute value of negative number.
Alternatively, you could scan the remaining n-1 bits from the right (least-significant bit). Look for the first occurrence of 1. Flip all the bits to the left of that first occurrence of 1. The flipped pattern gives the absolute value. For example,n = 8, bit pattern = 1 100 0100B S = 1 → negative Scanning from the right and flip all the bits to the left of the first occurrence of 1 ⇒ 011 1100B = 60D Hence, the value is -60D
- Check the sign bit (denoted as
rvelthuis said
It gets even more interesting if you use bitwise operations.
Basically, these are the same as logical operations, but there are some additional rules.
Did you know that if A is positive, (so -A is negative), the rule “-A = not A + 1” applies? This also means that “-A = not (A – 1)”. There are more rules like that, e.g. “-A xor -B = not (A – 1) xor not (B – 1) = (A – 1) xor (B – 1)”, etc. This was a great help for my BigInteger implementation (https://github.com/rvelthuis/DelphiBigNumbers/blob/master/Source/Velthuis.BigIntegers.pas, see BigInteger.InternalBitwise).
jpluimers said
I vaguely remember that from my school days in the mid 1980s (:
Will have added some links to the article