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.
Spock
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.
| P | Q | P⊗Q |
| T | T | F |
| T | F | T |
| F | T | T |
| F | F | F |
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.
| P | Q | P ⋁ Q | ¬(P ⋀ Q) | (P ⋁ Q) ⋀ ¬(P ⋀ Q) |
| T | T | T | F | F |
| T | F | T | T | T |
| F | T | T | T | T |
| F | F | F | T | F |
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:
| P | Q | P → Q |
| T | T | T |
| T | F | F |
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
Abduction is an inference rule that infers P to be true from P → Q. Let’s look again to the P → Q truth table.
| P | Q | P → Q |
| T | T | T |
| F | T | T |
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
or,
- 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,
| P | Q | P → Q | ¬ P | ¬ Q | ((P → Q) ⋀ ¬ Q) | ((P → Q) ⋀ ¬ Q) → ¬ P |
| T | F | F | F | T | F | F |
| F | F | T | T | T | T | T |
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: logic, predicate calculus