Propositional Calculus – A Quick Artificial Intelligence primer

Artificial Intelligence includes much more than machine learning I’ve talked about before here, and here. I thought I’d start talking about this by introducing predicate calculus. Predicate calculus, also known as first-order logic, is the collection of formal systems used in computer science to quantify non-logical objects and expressions. It breaks down artificial intelligence systems to their most atomic states.

Logic is the anatomy of thought.

John Locke

Logic is the beginning of wisdom, not the end.


A fact can be broken down into propositional expressions. The most traditional example is,

  • Socrates is a human (P)
  • All human are mortal (Q)
  • Therefore Socrates is mortal (P –> Q)

This reads P is true, and Q is true, therefore P implies Q.

Some examples of propositional operators that build our propositional expressions are,

  • ∧ : AND
  • ∨ : OR
  • ¬ : NOT

Let’s do an example. How would we express something like the exclusive-or operator ⊗, using only those operators? We can start by making a truth table of what this should look like.

Truth table for the exclusive-or

Now an exclusive-or sentence in English should say P or Q, but not P and Q. That expression in our formal propositional style is (P ⋁ Q) ⋀ ¬(P ⋀ Q). But lets check our work with truth tables.

PQP ⋁ Q¬(P ⋀ Q)(P ⋁ Q) ⋀ ¬(P ⋀ Q)
Truth table for (P ⋁ Q) ⋀ ¬(P ⋀ Q)

This truth table evaluates to the same truth values and shows P⊕Q ≡ (P ⋁ Q) ⋀ ¬(P ⋀ Q).

Modus Ponens

We can use truth tables to prove some classic logical arguments. Let’s start wtih modus ponens. Modus ponens states that P is true, therefore Q is true. The “Socrates is a human” predicate above is an example of modus ponens. A truth table for modus ponens would be:

Because we state P to be true, we only need to look at those cases. Interestingly in the case of false statements P implies Q would evaluate to false, showing that false statements imply anything!

The truth tables shows truth values of the if… then statement of P → Q. If the statement was instead,

  • Shakespeare is a human.
  • All humans are men.
  • Therefore Shakespeare is a man.

Note that although Shakespeare could be a man, the logical argument is not sound. Because Q (All humans are men) is false, we cannot state that P implies Q.


Abduction is an inference rule that infers P to be true from P → Q. Let’s look again to the P → Q truth table.

This time we consider cases where P → Q is True. We can see that there are instances were P is True and P is False, and we cannot infer that P is true from P → Q.

Abductive reasoning is common in science. Sherlock Holmes, often praised for his deductive skills, often actually uses abductive reasoning to come to his conclusions. As an example look at these two arguments.

  • Organs have been designed to be similar to machines.
  • Machines are a product of intelligent design.
  • Therefore, humans are the product of intelligent design


  • Test mice given water from a new industrial plant get sick.
  • People got sick after the plant was opened.
  • Therefore, the current sickness caused by the new plant.

Modus tollens

Finally let’s look at modus tollens. Modus tollens, or affirming the consequent is the contrapositive of modus ponens. It states Q is false, and P → Q is false, and concludes P is false. The propositional expression is ((P → Q) ⋀ ¬ Q) → ¬ P. This truth table is,

PQP → Q¬ P¬ Q((P → Q) ⋀ ¬ Q)((P → Q) ⋀ ¬ Q) → ¬ P
Assuming Q is false, P is inferred to also be false, else modus tollens evaluates to false.

Artificial Intelligence starts with these basic concepts. I encourage you to learn more about them and how to build and use truth tables in all your work.

Tags: ,

Leave a Reply