The Wiert Corner – irregular stream of stuff

Jeroen W. Pluimers on .NET, C#, Delphi, databases, and personal interests

  • My badges

  • Twitter Updates

  • My Flickr Stream

  • Pages

  • All categories

  • Enter your email address to subscribe to this blog and receive notifications of new posts by email.

    Join 1,425 other followers

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

{\displaystyle {\begin{aligned}{\overline {A\cup B}}&={\overline {A}}\cap {\overline {B}},\\{\overline {A\cap B}}&={\overline {A}}\cup {\overline {B}},\end{aligned}}}

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 ↑ qDpq, 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 F

There 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 }\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 }\nleftarrow ‘ operation is F for the three remaining columns of p, q. The output row for {\displaystyle \nleftarrow }\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) falseOpq Contradiction
1 (F F F T)(p, q) NOR p ↓ qXpq Logical NOR
2 (F F T F)(p, q) p ↚ qMpq Converse nonimplication
3 (F F T T)(p, q) ¬p~p ¬pNpFpq Negation
4 (F T F F)(p, q) p ↛ qLpq Material nonimplication
5 (F T F T)(p, q) ¬q~q ¬qNqGpq Negation
6 (F T T F)(p, q) XOR p ⊕ qJpq Exclusive disjunction
7 (F T T T)(p, q) NAND p ↑ qDpq Logical NAND
8 (T F F F)(p, q) AND p ∧ qKpq Logical conjunction
9 (T F F T)(p, q) XNOR p If and only if qEpq Logical biconditional
10 (T F T F)(p, q) q qHpq Projection function
11 (T F T T)(p, q) p → q if p then qCpq Material implication
12 (T T F F)(p, q) p pIpq Projection function
13 (T T F T)(p, q) p ← q p if qBpq Converse implication
14 (T T T F)(p, q) OR p ∨ qApq Logical disjunction
15 (T T T T)(p, q) trueVpq 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:

  • boolean algebra AND gate truth table          NAND gate truth table
  • boolean algebra OR gate truth table          NOR gate truth table
  • Ex-OR gate truth table          Ex-NOR gate truth table
  • boolean algebra NOT gate truth table

–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:

2 Responses to “To help understanding combinations of boolean operators: Truth table – Wikipedia”

  1. 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).

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

 
%d bloggers like this: