## 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

falseif both of its operands are true. In other words, it produces a value oftrueif at least one of its operands is false.The truth table for

p NAND q(also written asp ↑ q,Dpq, orp | q) is as follows:

Logical NANDpqp↑qT 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:

pqp∧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

trueif both of its operands are false. In other words, it produces a value offalseif 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 asp ↓ q, orXpq) is as follows:

Logical NORpqp↓qT 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:

pqp∨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

pandq, 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]}

pqF ^{0}NOR ^{1}Xq ^{2}¬p^{3}↛ ^{4}¬q^{5}XOR ^{6}NAND ^{7}AND ^{8}XNOR ^{9}q ^{10}if/then ^{11}p ^{12}then/if ^{13}OR ^{14}T ^{15}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
Comrow indicates whether an operator,op, is commutative –P op Q = Q op P.- The
L idrow shows the operator’s left identities if it has any – valuesIsuch thatI op Q = Q.- The
R idrow shows the operator’s right identities if it has any – valuesIsuch thatP 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 }‘ operation is F for the three remaining columns of p, q. The output row for {\displaystyle \nleftarrow } is thus

2: F F T F

and the 16-row

^{[3]}key is

^{[3]}operator Operation name 0 (F F F F)(p, q) ⊥ false, OpqContradiction 1 (F F F T)(p, q) NOR p↓q,XpqLogical NOR 2 (F F T F)(p, q) ↚ p↚q,MpqConverse nonimplication 3 (F F T T)(p, q) ¬p,~p¬p,Np,FpqNegation 4 (F T F F)(p, q) ↛ p↛q,LpqMaterial nonimplication 5 (F T F T)(p, q) ¬q,~q¬q,Nq,GpqNegation 6 (F T T F)(p, q) XOR p⊕q,JpqExclusive disjunction 7 (F T T T)(p, q) NAND p↑q,DpqLogical NAND 8 (T F F F)(p, q) AND p∧q,KpqLogical conjunction 9 (T F F T)(p, q) XNOR pIf and only ifq,EpqLogical biconditional 10 (T F T F)(p, q) qq,HpqProjection function 11 (T F T T)(p, q) p→qif pthenq,CpqMaterial implication 12 (T T F F)(p, q) pp,IpqProjection function 13 (T T F T)(p, q) p←qpifq,BpqConverse implication 14 (T T T F)(p, q) OR p∨q,ApqLogical disjunction 15 (T T T T)(p, q) ⊤ true, VpqTautology

### 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

## 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