Propositional Calculus – Part 1: Introduction

Propositional calculus is one of the oldest forms of logic.  It lies at the heart of all syllogisms, deductions, inductive inferences, and the like.  It is the system that allows us to deal with logic problems such as determining the truth of the following argument:

or of this argument:

Note that is doesn’t judge the truth or falsehood of the premises (It is raining or it is sunny) or of the conditionals (If it is…), it only judges the truth content of the conclusion based on these assumptions (premises and conditionals).  It won’t know whether or not it is raining, but it will be able to tell me that I am depressed when it is raining (not true – I like the rain) or that I shouldn’t wear a raincoat when it is sunny.  Note also that the system is not equipped to handle syllogism using the quantifiers all, some, or none.  Thus the true syllogism

and the false syllogism

are outside of its ability to evaluate.

Despite these limitations, the system is fairly powerful and can be used in successful applications of artificial intelligence to solve real-world, interesting problems.

Amazingly propositional logic is able to pack a lot of power into a fairly brief amount of symbolism.  The system as a whole consists of 2 objects, 5 expressions that define relations between the objects, 10 rules for manipulating the relations, and 3 helper symbols that act as traffic cops to impose order on the steps.

The simplest object of the system is an atomic proposition, like the statement ‘It is raining’.  This proposition, usually denoted by a single capital letter – ‘R’ for ‘It is raining’.  More complex propositions are built out of the atomic propositions using the 5 logical expressions, subject to certain rules.  Any primitive proposition and all valid compound propositions are collectively known as well-formed formulae (wffs – pronounce ‘woofs’, like the sounds dogs make).  Often wffs are denoted by Greek symbols, like $\phi$ or $\psi$.

The 5 logical expressions denote relations associated with the propositions.  There is one prefix expression, where the expression symbol operators on only one proposition, and 4 infix expressions that link two propositions together.

The prefix expression is the ‘not’ which translates the proposition ‘It is raining’ into the negative proposition ‘It is not the case that it is raining’.  This somewhat more clunky way of expressing the negation (rather than ‘It is not raining’) seems to be preferred since it makes adding or removing a negation as simple as adding or removing the phrase ‘It is not the case that’ to the front of an existing proposition.

The four infix expressions link two propositions together.  These are:

• Conjunction – ‘It is raining’ and ‘It is cold’
• Disjunction – Either ‘it is raining’ or ‘it is sunny’
• Conditional – If ‘it is raining’ then ‘the ground is wet’
• Biconditional – ‘It is raining’ if and only if ‘water droplets are falling from sky’

Since the conjunction, disjunction, and biconditional expressions are symmetric upon interchange of the two propositions (or wffs) there is no special name for the first or second slots.  The conditional, however, requires a sense of cause-and-effect and, as result, the first slot is called the antecedent and the second slot the consequent.  In the conditional ‘If it is raining then I am depressed’, ‘it is raining’ is the antecedent and ‘I am depressed’ is the consequent.

The systems objects and expressions can be summarized as

In addition to the expression symbols, there are a few additional helper symbols that keep things neat.  The first is the ‘implies’ symbol $\implies$. It is sometimes called ‘infer that’ and then is denoted by $\vdash$. Either basically denotes the final conclusion (the output) of the argument.  So the first proposition translates into

where $R$ is the proposition ‘It is raining’ and $D$ is the proposition ‘I am depressed’.  The second set of symbols are the parentheses ‘(‘ and ‘)’ which are used to group terms together to avoid ambiguous expressions such as $A \land B \land C$, which could mean ‘I did A and then I did B and C’ or ‘I did A and B and then I did C’ or other meanings.

The next piece is the rules of inference that allow proper manipulation of one set of wffs into another.  These rules are:

1. Modus ponens: a conditional implies the consequent if the antecedent is true
2. Negation Elimination: $\neg \neg \phi \implies \phi$
3. Conjunction Introduction: $\phi, \psi \implies \phi \land \psi$
4. Conjunction Elimination: $\phi \land \psi \implies \phi, \psi$
5. Disjunction Introduction: $\phi \implies \phi \lor \psi$ for any $\psi$
6. Disjunction Elimination: $\phi \lor \psi, \phi \rightarrow \chi, \psi \rightarrow \chi \implies \chi$
7. Biconditional Introduction: $(\phi \rightarrow \psi), (\psi \rightarrow \phi) \implies \phi \leftrightarrow \psi$
8. Biconditional Elimination: $\phi \leftrightarrow \psi \implies \phi \rightarrow \psi, \psi \rightarrow \phi$
9. Conditional Proof (CP): accepting a proposition $P$ that proves another $Q$ then $P \rightarrow Q$
10. Reductio ad Absurdum (RAA): A contradiction to $\neg \phi \implies \phi$

Note that the truth value of the propositions are assumed to be known from the outset (with the exception of the conditional proof and reduction ad absurdum, where the assumption is made during the course of the argument).  The purpose of the system is to determine the truth of the conclusion based on the truth values of assumptions.  The formal inference rules act as a computer program that transforms input to output.

Next week’s column will apply the Propositional Calculus to prove some interesting outcomes and to show how unexpected inferences can result.  All of that is a prelude to the final, fun application of preventing an AI explorer from dying due to misadventure before he can go ‘there and back again’.