Propositional Logic
The goal is to become comfortable with formal proof in propositional logic. At the end of this practical you will be asked to prove
If you are not yet comfortable working with propositional logic, you may wish to start with the "Propositional Logic Basics" section.
Once you know the basics of propositional logic, get some practice with formal proofs in the "Formal Proof" section.
After that, take on the challenge of proving the above in the final section.
Task 1: Getting Started
If you need to revise your knowledge of propositional logic, start here. This section will take you through some exercises that will make sure you know the fundamentals of propositional logic.
Exercise 1
From memory, write out the truth tables for the following operators. If you don't know what a symbol means, look it up and learn it!
Exercise 2
- List three propositions in natural language, such as: "Bach invented hop hop in the third century BC". Call them $p$, $q$, and $r$.
- Write out (in natural language) the negation of each of these, i.e. the meaning of $(\neg p)$, $(\neg q)$, and $(\neg r)$.
- Write out the meanings of $(\neg(\neg p))$, $(\neg(\neg q))$, and $(\neg(\neg r))$. Compare these to the meanings of $p$, $q$, and $r$. What do you notice?
Exercise 3
Translate the following into propositional logic. When doing so make each proposition ($p$, $q$, $r$, etc.) atomic, i.e. something that cannot be further simplified. For instance. ``I am cold and you are cold'' could be redued to the conjunction of two atomic propositions, e.g. $(p \wedge q)$.
- I am cold if and only if I am not wearing socks.
- "If I were not Alexander, then I should wish to be Diogenes" (Alexander the Great to Diogenes, a famous philosopher and contemporary of Plato. Diogenes famously replied, ``If I were not Diogenes, I would also wish to be Diogenes.'')
- "If you do not take an interest in the affairs of your government, then you are doomed to live under the rule of fools" (Plato)
- "I am the wisest man alive, for I know one thing, and that is that I know nothing" (Also Plato, but probably through his mouthpiece Socrates)
- "I think therefore I am" (Descartes' cogito from his Meditations) (That I am thinking implies that I exist)
Exercise 4
Translate both of these statements into propositional logic. What is the difference in their logical structure?
- Leibniz and Newton invented calculus
- John and Mary are a happy couple
Calculate truth value
Use the truth tables for the various propositional logic operators to work out the truth value for the following statements of propositional logic.
- $( true \wedge false )$
- $((\neg false ) \wedge true )$
- $(( \neg (\neg true)) \wedge true)$
- $( true \implies (\neg true) )$
- $( true \Longleftrightarrow true )$
- $( false \vee true )$
- $((\neg false ) \vee true )$
- $(true \vee true)$
- $( true \vee (\neg (\neg true)))$
- $( false \implies (\neg true ))$
Proof with truth tables
The following questions ask you to use and construct truth tables to prove statements of propositional logic.
You might find the following tool helpful
Use the ampersand(&) for conjunction, the pipe character (|) for disjunction, and the exclamation mark (!) for negation. There is no symbol for implication, but implication ($p \implies q$) is equivalent to negation and disjunction ($\neg p \vee q$)
| a | b | \( a \vee b \) |
|---|---|---|
| a: T | b: T | T |
| a: T | b: F | T |
| a: F | b: T | T |
| a: F | b: F | F |
Truth tables
The truth table for $(\neg p) \wedge q$ is expressed as shown here.
| $p$ | $q$ | $(\neg p)$ | $((\neg p) \wedge q)$ |
|---|---|---|---|
| T | T | F | F |
| T | F | F | F |
| F | T | T | T |
| F | F | T | F |
On the basis of this example create truth tables for the following statements of propositional logic. Work towards the final statement step-by-step as I have done above. Do not just show the variables and the final column without additional steps shown. Make sure you can do this by hand as well as using the tool above.
- $(p \wedge (\neg q))$
- $((\neg p) \implies (\neg q))$
Can you find a simpler equivalent way of expressing the following statements of propositional logic?
- $\neg ((p \vee q) \wedge r) \vee (\neg p \wedge q)$
- $((\neg p) \wedge (\neg q)) \vee (p \wedge q)$
Task 2: Formal Proof
In this part of the practical, the goal is to be able to formally prove statements of propositional logic. For this, make use of the following numbered list of propositional logic laws.
Laws of Propositional Logic
Law 1.1: Complement Law of Negation
Law 1.2: Double Negation
Law 2.1: Idempotence of Conjunction
Law 2.2: Conjunction identity
Law 2.3: Domination Law of Conjunction
Law 2.4: Complement law
Law 2.5: Commutativity of Conjunction
Law 2.6: Associativity of Conjunction
Law 3.1: de Morgan’s Laws
Law 3.2: Idempotence of Disjunction
Law 3.3: Disjunction Identity
Law 3.4: Domination Law of Disjunction
Law 3.5: Associativity of Disjunction
Law 3.6: Commutativity of Disjunction
Law 3.7: Complement law
Law 3.8: Disjunction distributes through conjunction
Law 3.9: Conjunction distributes through disjunction
Law 4.1: Definition of Implication
Law 5.1: Associativity of Equivalence
Law 5.2: Commutativity of Equivalence
Law 5.3: Equivalence Identity
Law 5.4: Complement Law
Law 5.5: Definition of Equivalence
Example Proofs
When we take a statement of logic and try to establish whether it is true or false, we are constructing a proof. Equational reasoning is one way to structure a proof.
On our first line, numbered 1, we write out the statement we want to prove. On the next line, we give a law of propositional logic. Here I have numbered the laws according to the handout. After this, on a line numbered 2, we re-write the statement having applied that law. We continue in this way until we reach `true', or `false'. See the example below:
- $(p \implies p)$ = (Law 4.1: Conditional Identity)
- $(\neg p \vee p)$ = (Law 3.7: Complement Law)
- true
If we show a proposition is equivalent to true (as above), then we know that proposition is a tautology. If it is equivalent to false, we know it is a contradiction.
This time I will prove \( p \wedge (\text{false} \wedge q) \) is a contradiction, i.e. equivalent to false.
- \( ( \neg (true) \wedge p ) \wedge q \) = ( Law 1.1: Definition of Negation)
- \( ( \text{false} \wedge p ) \wedge q \) = ( Law 2.5: Commutativity of Conjunction)
- \( ( p \wedge \text{false} ) \wedge q \) = ( Law 2.3: Domination Law of Conjunction)
- \( \text{false} \wedge q \) = ( Law 2.5: Commutativity of Conjunction)
- \( q \wedge \text{false} \) = ( Law 2.3: Domination Law of Conjunction)
- false
Look through the above proof and make sure you understand what is happening at each step. Note the importance of using the laws of commutativity to rearrange the statement to be in the correct format for subsequent rules to apply.
Complete the proof
Working step by step, we can work out the truth value of any statement of propositional logic which doesn't contain variables. Finish the example below. The first few steps are done for you. You might be tempted to skip a step to avoid writing out the whole statement again. Resist that temptation!
- \( ( ( \neg true ) \vee ((\neg true) \Longleftrightarrow false) ) \) = ( Law 1.1: Definition of Negation)
- \( ( false \vee ((\neg true) \Longleftrightarrow false) ) \) ...
- \( true \)
Check that your final answer is true. If it isn't, you've gone wrong somewhere.
Prove the equivalence of logical propositions
Prove whether or not the following statements of propositional logic are equivalent.
Applying the laws above, calculate the truth values for the following logical propositions. Format each as a proof using equational reasoning. Your last line will either be true, false, or $p$.
- \( ((\neg \text{true}) \wedge \text{false}) \)
- \( ((\neg \text{false}) \wedge (p \wedge \text{true})) \)
- \( ((\neg \text{true}) \vee (p \wedge (\neg \text{false}))) \)
- \( ((\text{false} \wedge q) \implies \text{true}) \)
- \( ((\neg p) \implies (p \Longleftrightarrow \text{false})) \)
Challenge
Prove the following using a truth table (easier) and provide a formal proof (harder).
This question is slightly unfair as I have used an unfamiliar format. Previously we have been working with individual statements of propositional logic. The notation we have been working with is the object language of propositional logic, i.e. it is the language that statements of propositional logic is written in. Now I am asking you to reason about what given propositions entail (i.e. if they are true, what do they make true).
Two of these, $P \implies Q$ and $Q \implies R$ are premises: things that the argument assumes to be true. The last of these, $P \implies R$ is the conclusion. The symbol $\therefore$ is read "therefore". To translate, the argument that I want you to prove is "if we assume that $P \implies Q$ and $Q \implies P$, then we conclude that $P \implies R$ must be true".
Provide a proof using a truth table and a formal proof.
This is one of three common rules of inference called Hypothetical Syllogism. Two other common rules of inference are:
Modus Ponens
Modus Tollens
See if you can prove both of these as well.