Previous: IntroductionIntroduction Up: Class notesClass notes Next: Predicate LogicPredicate Logic
Document also available in PDF, Postscript, DVI, Text, LaTeX, LyX.

Propositional Logic

Chapter 1  Propositional Logic

1.1  Introduction

1.1.1  What is a proof ?

Définition 1   A proof is a piece of text written by a human to convince another human that some fact is true.
Problem 1   [, p. 2]

You have been selected to serve on jury duty for a criminal case. The attorney for the defense argues as follow:

``If my client is guilty, then the knife was in the drawer. Either the knife was not in the drawer, or Jason Pritchard saw the knife. If the knife was not there on October 10, it follows that Jason Pritchard did not see the knife. Furthermore, if the knife was there on October 10, then the knife was in the drawer and also the hammer was in the barn. But we all know that the hammer was not in the barn. Therefore, ladies and gentlemen of the jury, my client is innocent.''
Are you convinced ?

Problems: A good proof consists of: Let's look at a very simple example:
Théorème 1   Let x and y be two integers.

If x is odd and y is odd, then xy is odd.

Proof. Assume x is odd and y is odd.

Let k be an integer such that x=2k+1.

Let l be an integer such that y=2l+1.

Then, xy=(2k+1)(2l+1)=2(2kl+k+l)+1.

Note that 2kl+k+l is an integer.

Conclusion: xy is odd.

1.1.2  Formal and Informal proofs

What do we mean by ``derives logically from the previous ones'' ?

What operations shall we consider as legal ?

To learn more about this, we need a model of what we intuitively consider as true, or logic.

This model we are going to construct is called formal logic.  Formal systems

Définition 2   A formal system is build by providing: A string that can be obtained from the axioms by applying rewriting rules is called a theorem of the formal system.

proof of a theorem is a description of the axioms and rules used to get the theorem.

The set of all theorems is called the
language defined by the formal system.
Exemple 1   The MIU formal system[]
A formal system does not need to have any meaning or semantic. It's pure syntax.

We will build formal logic as a formal system, with a meaning! Then, any theorem of this formal system shall be interpreted as true.

We will have to be very careful with the choice of the axioms and rules!  Proofs and programming

Writing a proof and a writing a program are very similar:

Proofs Programming Purpose
Theorem Function prototype How to use it
Proof Function definition How it works
Intuitive proof Comments Explanation for the reader
Informal proof Program in a high level language Human readable
Formal proof Program in assembly language Machine readable
Checking an informal proof Compiling Human readable -> Machine readable

This comparison is not gratuitous. There are deep links between proofs and programming which have been studied a lot in the last decades. This is called the Curry-Howard correspondence.

1.2  Statements, Symbolic Representation, and Tautologies

As a first step, let's define logic formulas and their interpretation.

1.2.1  Statements and Propositions

Définition 3   A statement (or proposition) is a sentence which is either true or false.
Exemple 2   Which sentences below are statements ?
Notation 1   A, B, C: symbols representing a statement.

Each of those symbols can be given a truth value, either True (T for short) or False (F for short).

1 is a statement if truth value True.

0 is a statement if truth value False.

1.2.2  Connectives

How can we combine two statements ?  And (conjunction), or (disjunction)

Exemple 3   ``The sky is cloudy'': A. ``It's raining'': B.
Définition 4   The truth table of a formula describes when it's true or not, given the truth value of the symbols.

A B A/\ B A\/ B
T T    
T F    
F T    
F F  Exclusive or

Exemple 4   ``Cheese or desert''

You get cheese: A

You get desert: B
Définition 5   A exclusive or B: A xor B.

Truth table:

A B A xor B
T T  
T F  
F T  
F F  Implication

Exemple 5   ``If I get my driver license, I will open a bottle of champagne''.

``I get my driver license'': A.

``I open a bottle of champagne'': B.
Définition 6   A implies B: A-> B.

Truth table:

A B A-> B
T T  
T F  
F T  
F F  

Why this should be true: Why this should be false:

This one can be tricky. To help you make up your mind, here are some examples: Well, as strange as it can sound, F-> T is a true formula.

If you start from an utterly false hypothesis, you can prove anything.

``Avec des si, on pourrait mettre Paris en bouteille''

``With ifs, Paris could be put in a bottle''
Remarque 1   A-> B and B-> A are not the same!
Sounds stupid ?

Look carefully around you! This is the most common logic error in peoples argumentations.

And it's not always an involuntary error.
Exercice 1   Give the antecedent and the consequent in the following sentences  Equivalence

Exemple 6   The knight will win if and only if his armor is strong

The knight will win: A.

His armor is strong: B.

This sentence contains two informations:
Définition 7   A is equivalent to B: A<-> B.

Truth table:

A B A<-> B
T T  
T F  
F T  
F F  Not

So far we defined binary connectives, that is connectives which took two arguments.

Here is now a unary connective, taking just one argument.
Exemple 7   It will not rain tomorrow

The knight will win: A.

His armor is strong: B.

This sentence contains two informations:
Définition 8   not A: A' (more usual notation: ¬ A)

Truth table:

A A'

1.2.3  Complex Well Formed Formulas

Définition 9   A formula is a string of A well formed formula (or wff) is a formula which satisfies certain syntax rules.
Notation 2   Symbols representing wff: P, Q, R.  Order of precedence

The formula A/\ B-> C' is ambiguous. It can be read as: Solution 1: always put all parenthesis (not very readable).

Solution 2: put an order of precedence between the operators:
  1. Connectives within parentheses, innermost parenthesis first
  2. '
  3. /\, \/
  4. ->, <-
  5. <->
With this order of preference, A/\ B-> C' unambiguously refer to (A/\ B)->(C)'.  Evaluation of a wff

From the truth values of the basic statements, and the elementary truth tables, one can evaluate the truth value of a wff.
Exemple 8   A/\ B-> C', with A true, B false and C true:

A/\ B: false

C': false

A/\ B-> C': true
There is a recursive algorithm to compute the evaluation of a wff.  Truth table of a wff

This yields an algorithm for computing the truth table of a wff.

A B C A/\ B C' (A/\ B)->(C')
T T T      
T T F      
T F T      
T F F      
F T T      
F T F      
F F T      
F F F      

Problem 3   What's the size of a truth table?

Problem 4   Can any truth table be obtained by a wff?

1.2.4  Tautologies and Contradictions

Définition 10   A tautology is a statement that is always true.

A c
ontradiction is a statement that is always false.
Exemple 9   A\/ A'

``Today the sun shine or today the sun does not shine''.
Exercice 2   Are the following wff tautologies or contradictions ?
  1. A/\ A'
  2. A<-> A
  3. (A/\ B)<->(B/\ A)
  4. (A/\ B)-> A
Algorithm to check for a tautology?

Compute the truth table!

It's slow (2n, where n is the number of propositions), but it works.

For certain simple forms of propositions, there is a much faster algorithm (see [, Tautology test, p. 13]).
Exemple 10   Is [(A/\ B-> C')/\(E<- D)]<->[(E<- D)/\(A/\ B-> C')] a tautology ?

Let P:=(A/\ B-> C') and Q:=(E<- D).

The formula above is [P/\ Q]<->[Q/\ P].

Let's prove it's a tautology.

Take some truth values for A, B, C, D, E.

P and Q will then have some truth value.

But we know that (A/\ B)<->(B/\ A) is a tautology.

So [P/\ Q]<->[Q/\ P] will be true!

We don't actually need to compute the truth table of P and Q.
Remarque 2   Whenever you have some tautology, if you replace ALL occurrences of some basic statement (say A) by a more complicated wff, you still get a tautology.

1.2.5  Equivalence of wff

Let P and Q be two wff, and suppose P<-> Q is a tautology.

Then P and Q have the same truth table.
Définition 11   P and Q are equivalent (noted P <=> Q) if they have the same truth table.
Remarque 3   Writing P<-> Q or P <=> Q is different.

In the first case, you just represent a formula, which can be true or false.

In the second case, you claim that the wff P<-> Q is a tautology.  Basic equivalent wff

What is the negation of ``Peter is tall and thin'' ?

Identity (id) A\/0 <=> A
  A/\1 <=> A
Complement (comp) A\/ A' <=> 1
  A/\ A' <=> 0
Commutativity (comm) A\/ B <=> B\/ A
  A/\ B <=> B/\ A
Associativity (ass) (A\/ B)\/ C <=> A\/(B\/ C) <=> A\/ B\/ C
  (A/\ B)/\ C <=> A/\(B/\ C) <=> A/\ B/\ C
Distributivity (dist) A\/(B/\ C) <=> (A\/ B)/\(A\/ C)
  A/\(B\/ C) <=> (A/\ B)\/(A/\ C)
Double negation (dn) A'' <=> A
De Morgan's Law (dm) (A\/ B)' <=> A'/\ B'
  (A/\ B)' <=> A'\/ B'
Implication (imp) A'\/ B <=> A-> B

Remarque 4   Notice the duality between \/ and /\.

Unlike + and · they play a perfectly symmetric role in all formulas.  More equivalent wff using substitution

Exemple 11   (A/\ B)/\1 <=> (A/\ B).
Remarque 5   Let P and Q be equivalent wff.

If you replace all occurrences of some basic statement by another wff, you still get two equivalent wff's.
Exemple 12   A/\(B\/ C) <=> A/\(C\/ B)
Remarque 6   Let P and Q be equivalent wff.

If P appears
exactly as a subformula of a bigger wff, then you can substitute P by Q and get an equivalent wff.  What's the point ?

Rewriting a formula to simplify it:
Exercice 3   [, Example 7 p.12]
If ((outflow > inflow) and not ((outflow>inflow) and (pressure < 1000)))

  Do something;


  Do something else;

Write the wwf corresponding to the test.

Rewrite this wwf using equivalence rules.
Electronic circuits and logical gates:
Exercice 4   Build an electronic circuit for (A/\ B)-> C'.

1.3  Propositional logic

1.3.1  Arguments

We have seen propositions, well formed formula for formalizing statements.

We now need to formalize arguments.
Exemple 13   [, Example 17 p. 28]

Let's formalize the following argument:

``If interest rates drop, the housing market will improve.

Either the federal discount rate will drop, or the housing market will not improve.

Interest rates will drop.

Therefore the federal discount rate will drop.''

Basic statements:
Argument: (I-> H)/\(F\/ H')/\ I -> F
Définition 12   An argument is a wff of the form P1/\ P2/\···/\ Pn -> Q.

1,···,Pn are the hypothesis.

Q is the

The argument is
valid iff P1/\ P2/\···/\ Pn -> Q is a tautology.
Exercice 5   Prove that the following arguments are valid:
  1. [A->(B-> C)] -> [(A/\ B)-> C]
  2. [(A/\ B)-> C] -> [A->(B-> C)]
Why is this reasonable ?

``If the sun shine then if you don't put sun cream, you will get burned'': A
-> (B-> C)

``If the sun shine and you don't put sun cream, then you will get burned'': (A/\ B) -> C
Exemple 14   ``George Washington was the first president of the United States.

Therefore everyday has 24 hours.''
We put some more restrictions to only keep ``meaningful'' arguments.

1.3.2  Proof sequences

So now, how to prove that an argument is a tautology ?
  1. Use the truth table
  2. Use formal logic!
Exemple 15   Let's prove that the argument A\/(A\/ B)' -> (A\/ B') is valid.

We are lazy to compute the truth table.

Instead, we assume that the hypothesis is valid, and use a series of equivalences to deduce that the conclusion is valid.
1. A\/(A\/ B)' (Hypothesis)
2. A\/(A'/\ B') (De Morgan's, 1)
3. (A\/ A')/\(A\/ B') (Distributivity, 2)
4. 1/\(A\/ B') (Complement, 3)
5. (A\/ B') (Identity, 4)

What we just did is called a proof sequence.

This is our first proof using formal logic.
Exercice 6   Prove that the following argument is valid:

(A\/ B)'\/(A'/\ B)
-> A'
Définition 13   Formal Logic: wff + set of derivation rules (formal system).
What derivation rules shall we accept?

We want our formal logic to be:

1.3.3  Looking for derivation Rules

Exemple 16   A/\ B -> A
Equivalences rules are not enough.

We can't prove the previous statement, because A/\ B is strictly stronger than A.

We have build equivalence rules from equivalences P<-> Q.

We can build Inference rules from any valid argument P-> Q.

Rule name From Can derive
modus ponens (mp) P, (P-> Q) Q
modus tollens (mt) (P-> Q), Q' P'
conjunction (con) P, Q P/\ Q
simplification (sim) P/\ Q P, Q
addition (add) P P\/ Q

Exemple 17   A/\(A-> B)/\(B-> C) -> C
1. A/\(A-> B)/\(B-> C) (Hypothesis)
2. A (Simplification, 1)
3. A-> B (Simplification, 1)
4. B (Modus ponens, 2, 3)
5. B-> C (Simplification, 1)
6. C (Modus ponens, 4, 5)

Exemple 18   (A->(B\/ C))/\ B'/\ C' -> A'
1. (A->(B\/ C))/\ B'/\ C' (Hypothesis)
2. (A->(B\/ C)) (Simplification 1)
3. (B'/\ C') (Simplification 1)
4. (B\/ C)' (De Morgan's 3)
5. A' (Modus tollens 4, 5)

Exercice 7   Prove the validity of the following arguments using formal logic:
  1. A/\(B-> C)/\[(A/\ B)->(D\/ C')]/\ B-> D
  2. A'/\(A\/ B)-> B
  3. A'/\ B/\[B->(A\/ C)]-> C
  4. A/\ A'-> B
Theorem 1   This formal logic is correct and complete.
The correctness of the formal logic comes from the way we built the rules from valid arguments.

Proving it's complete is far more difficult.

1.3.4  Methods to make it easier

Our logic is complete, but still not very practical to use.

Here are some tricks to make it easier.

Most of the time, the proofs start like this:
1. (A->(B\/ C))/\ B'/\ C' (hyp)
2. (A->(B\/ C)) (Simp 1)
3. (B'/\ C') (Simp 1)
··· ··· ···

The steps 2 and 3 are pretty trivial, and it's reasonable to start directly with:
1. (A->(B\/ C)) (hyp)
2. (B'/\ C') (hyp)
··· ··· ···  The deduction method

Exemple 19   (A-> B)/\(B-> C) -> (A-> C)

The obvious start is:
1. (A-> B) (hyp)
2. (B-> C) (hyp)

But then it's pretty painful:
3. A'\/ B (imp 1)
4. A'\/(B-> C) (add 2)
5. (A'\/ B)/\(A'\/(B-> C)) (con 3, 4)
6. A'\/(B/\(B'-> C)) (dist 5)
7. A'\/ C (mp 6)
8. A-> C (imp 7)

Here it's easier to first rewrite the argument into an equivalent argument.

We have seen that P->(Q-> R) and (P/\ Q)-> R are equivalent.

So we can prove A/\(A-> B)/\(B-> C)
-> C instead, which is straightforward:
1. A (hyp)
1. (A-> B) (hyp)
2. (B-> C) (hyp)
3. B (mt 1, 3)
4. C (mt 2, 4)

This trick is called the deduction method.

It's powerful because we have:
Exercice 8   (A-> B)/\[B->(C-> D)]/\[A->(B-> C)] -> (A-> D)  Additional deduction rules

As we have seen, any valid argument could be transformed into a new rule.
Exemple 20   Here are two useful rules.

Rule name From Can derive
hypothetical syllogism (hs) P-> Q, Q-> R P-> R
contraposition P-> Q Q'-> P'

Adding those new rules won't change the power of the formal logic, but can make it more convenient. On the other hand, a minimal formal logic is nice since it's less error prone, and it's easier to remember all the rules.

It's up to you to choose which rules you want to use (and learn).
Exemple 21   (P-> Q)/\(P'-> Q)-> Q.

1.4  Verbal arguments

We can now start checking verbal arguments.
Exemple 22   Let's prove the following verbal argument[, Example 17 p. 28]:

``If interest rates drop, the housing market will improve.

Either the federal discount rate will drop, or the housing market will not improve.

Interest rates will drop.

Therefore the federal discount rate will drop.''
Exercice 9   Prove the following verbal argument[, Ex. 30 p. 32]:

``If the program is efficient, it executes quickly.

Either the program is efficient or it has a bug.

However, the program does not execute quickly.

Therefore it has a bug.''

1.5  Summary

1.5.1  Different levels of logic

Three levels for arguments: Any verbal argument based on propositions can be translated into a formal argument.

The propositional logic system is complete and correct:

1.5.2  Syntactic proof versus semantic proof

Testing an argument by computing it's truth table is purely mechanical.

So, what's the point of formal logic ?
Valid HTML 4.0! Previous: IntroductionIntroduction Up: Class notesClass notes Next: Predicate LogicPredicate Logic
Propositional Logic / CSM MACS-358 / Nicolas M. Thiéry
Last modified: Fri Jan 19 13:12:15 2007