Propositional Logic

In this lecture we are going to learn the basics of propositional logic. By the end of this lecture, you are going to understand:

The proposition as a mathematical object with its own operations
Proof as the derivation of a theorem from axioms using rules

To do this, we are going to pursue the goal of proving the equivalence of logical conditions in programming.

Along the way we're going to learn about:

Formalising reasoning
Logical deduction
Mathematical proof

Mathematics and Problem Solving

6. Propositional Logic

David Gundry

Learning Outcomes

Formalise language and pseudocode as propositional logic

Identify and provide examples of propositions from language and pseudocode
Recognise and use the names and symbols of common propositional operators
Write out the truth tables for these common propositional logic operators
Write a formula in propositional logic that corresponds to language or pseudocode

Prove (equivalence of) logical formulae

Create truth tables for propositional logic formulae
Understand common terminology used to describe propositions and propositional logic operators
Express properties of propositional logic operators as tautologies
Use axiom schemas to derive new statements of propositional logic
Prove statements of propositional logic by applying rule schemas

Learning Outcomes

Formalise language and pseudocode as propositional logic
Prove (equivalence of) logical formulae

Introduction

You are no doubt at least a bit familiar with programming. Programming is indispensable for modern life and central to computer science.

At a simple level, programming is writing a list of instructions for a computer to follow. One of the most fundamental concepts in programming is the if statement:

let x = false
if (x is true) then
    do y
endif

In this psuedocode we declare a variable x, which is set to false. Then we evaluate a condition x is true. If this condition is true then we execute a block of code (do y). If the condition is false, we do nothing. In this example, the condition would evaluate to false as false is true is not true, it is false.

In almost all programming languages we can express logical conditions. Conditions are statements in our programming language that are resolved to either true or false. In other words, they resolve to a boolean value. They can be simple:

n == 0

Or they can be complicated:

((a and b) or c) and (b or c)

Such conditions are an indispensable tool for programming. We can use them in if statements to control what code in our program will execute. We can use them to set variables that store so-called boolean values (true or false). If we dig inside our computers, we will find that such conditional logic is embedded in the hardware. Logic gates are particular collections of transistors that implement logical operations akin to those we write in if statements.

Why Logic?

Logic is a basic tool in

mathematics
computer science
programming

Logic gives us tools for formalising proof claims

Programming

Logical expressions are necessary when writing code, e.g.

let x = false
if (x is true) then
    do y
endif

Why proof?

Before we begin to dissect something that might appear trivial, let's think about why this is so important.

Programming is fundamental in computer science. A lot of computer scientists have been concerned with how to write programs that work. As you may have discovered, it is all to easy to write programs that do not work. More troubling, it is all to easy to write programs that seem to work, but in fact do not do what they are supposed to! This becomes a big deal if you are writing software to keep aeroplanes in the sky or patients in a hospital alive.

The Dutch computer scientist Edsger Dijkstra proposed that a program should be broken down into its smallest components. You could then prove mathematically that each component does what it is supposed to do, giving you a cast iron guarantee that the program does what it is supposed to.

Take, for instance, the logical condition evaluated by an if statement. You would need to prove that each condition always gives the intended result. This might be easy for a condition like x > 0 which merely translates of the desired behaviour ("the variable x should be greater than 0"). Unfortunately, code does not always remain this simple!

We are going to take up Disjkstra's challenge, in a very limited way. We are not going to worry about proving the correctness of whole programs in this course as this would be too much for an introductory course. Nevertheless, I hope by the end of this course, you'll have an appreciation of the importance of proof to computer science.

Image: CC-BY_SA 3.0 Hamilton Richards

Proof in Computer Science

How do we know what a program does?

Scientific approach: test it rigorously
Mathematical approach: prove it is correct

Edsger Dijkstra

Overview

To understand such conditions, we are going to use a tool called Formal Logic. Formal logic is a branch of mathematics dealing with the manipulation of logical symbols. We are not going to worry overly what these symbols refer to. This is our first lecture on formal logic, where we will be looking at propositional logic. In future lectures we are going to build on this system.

We will start by translating from natural language (or computer pseudo code) into formal logic. In particular, we will be using propositional logic. We will then learn the rules of propositional logic to allow us to evaluate any statement of propositional logic to decide whether or not it is true.

If you know how to program, you likely already understand most of these rules anyway. However, mathematical logic will allow us to prove the equivalence of different statements of logic. (If statements are equivalent, we can replace one with the other and get an identical output).

Overview

Translating into formal logic
Propositions
Operations
Rules of propositional logic

Propositions

In mathematical logic, a statement that is either true or false is called a proposition. For example, we might write in a program:

1 + 1 == 2

This, written in the syntax of our programming language is a proposition. We might write this in natural language: "One plus one equals two". Both of these are different ways of writing an equivalent proposition. Such a proposition can either be true or false. In this case, it is clearly false. Because it is not dependant upon the values of any other propositions, we will call it an atomic proposition.

Propositions

Introducing Propositions

We have seen propositions expressed in pseudocode. We could write many other atomic propositions in natural language, such as:

The sky is green
John is tall
The circumference of the earth is 26,000 miles

However, our goal here is not to understand arithmetic, nor whether the sky happens to be green, or whether John happens to be tall. These concepts do not exist in propositional logic. There is no way to express the content of a proposition. For our purposes, a proposition is simply a symbol, like $A$ or $B$.

Following convention, we will use the letters $A$, $B$, and $C$ to refer to particular propositions - so-called propositional constants. We will use the letters $p$, $q$, and $r$ to refer to propositional variables.

Formal logic is merely the manipulation of symbols according to rules that we define.

Propositions

A proposition is a statement of fact, e.g.

"The sky is green"

Notation

Propositional constants: $ A, B, C $
Propositional variables: $ p, q, r $
Schematic letters: $ \phi, \chi, \psi $

True and False

Let's introduce two special logical values. We will use $\top, T, 1$ or 'true' to label the proposition that is always true. We will use $\bot, F, 0$ or 'false' to label the proposition that is always false. (This is similar to true and false in many programming languages.)

True and False

A proposition $p$ can be one of two truth values

True
False

Notation

Tautology: $ \top, T, 1, \text{true} $
Contradiction: $ \bot, F, 0,\text{false} $

Equivalence

Equivalence is a relation between propositions. It is also on of the logical connectives or logical operators of propositional logic. It is written $ \Longleftrightarrow $. This allows us to say that two propositions are equivalent, meaning they always have the same truth value.

To say $A$ and $B$ are equivalent we would write:

\[ A \Longleftrightarrow B \]

Equivalence

Let $A$ and $B$ be propositions with the same truth value, we write this:

\[ A \Longleftrightarrow B \]

Properties

Commutative: $ p \Leftrightarrow q \quad \Longleftrightarrow \quad q \Leftrightarrow p $
Associative: $ (p \Leftrightarrow q) \Leftrightarrow r \quad \Longleftrightarrow \quad p \Leftrightarrow (q \Leftrightarrow r) $
Transitive: $ (p \Leftrightarrow q) \wedge (q \Leftrightarrow r) \quad \Longleftrightarrow \quad p \Leftrightarrow r $

Operators

So far in our logic we have the symbols $\top$, $\bot$, and the letters $p$, $q$, $r$, etc. and the equivalence relation $\Longleftrightarrow$. This does not allow us to say very much!

To develop this logic further, we will introduce operations. You will be familiar with some of the operations of arithmetic: addition, subtraction, multiplication, and division. I will use these as examples to clarify the meaning of operation, and then introduce operations that apply to propositions in our logic.

Operators

Operators of Propositional Logic

There are five basic operators of propositional logic. These are shown in the table below. It is important to learn their names and the symbols and truth tables associated with them.

Name	Translation	Symbol	Java	Python
Conjunction	and	$\wedge$	&&	and
Disjunction	or	$\vee$	\|\|	or
Negation	not	$\neg$	!	not
Implication	implies	$\implies$
Equivalence	if and only if	$\Longleftrightarrow$	==	==

A precise definition for each operation can be given using truth tables, as shown below. However, before you try and memorise these tables, you will find it easier if you can understand them in natural language.

For example, is like English "and". To take an example in natural language, "John is happy and Mary is happy" is true only when both John and Mary are happy.

Conjunction uses the symbol $ \wedge $

$ p $	$ q $	$ p \wedge q $
true	true	true
true	false	false
false	true	false
false	false	false

We can now translate any pseudocode expression of boolean logic (or indeed any statement of natural language) into propositional logic. Of course, doing so may lose some information because propositional logic does not represent what a proposition means, only its logical structure.

Operators of Propositional Logic

Name	Translation	Symbol	Java	Python
Conjunction	and	$\wedge$	&&	and
Disjunction	or	$\vee$	\|\|	or
Negation	not	$\neg$	!	not
Implication	implies	$\implies$
Equivalence	if and only if	$\Longleftrightarrow$	==	==

Conjunction

\[ p \wedge q \]

"John loves Mary and John is happy"

$p$	$q$	$p \wedge q$
true	true	true
true	false	false
false	true	false
false	false	false

Disjunction

\[ p \vee q \]

"John loves Mary or John is happy"

$p$	$q$	$p \vee q$
true	true	true
true	false	true
false	true	true
false	false	false

Negation

\[ \neg p \]

"John does not love Mary"

$p$	$ \neg p$
true	false
false	true

Implication

\[ p \implies q \]

"If John loves Mary, then Mary is happy"

Vacuous Truth

If the antecedent is false, the statement is always (vacuously) true

$p$	$q$	$p \implies q$
true	true	true
true	false	false
false	true	true
false	false	true

Equivalence

Equivalence (Biconditional)

\[ p \Longleftrightarrow q \]

"Mary loves John if and only if John loves Mary"

$p$	$q$	$p \Longleftrightarrow q$
true	true	true
true	false	false
false	true	false
false	false	true

Logical Operators

Which are the appropriate logical operators for formalising these statements?

Zebras do not have coloured stripes
Lions are animals and they have four legs
If an animal lays eggs it is not a mammal
Pandas eat bamboo or they starve

Logical Operators Question

Question

Which are the appropriate logical operators for formalising these statements?

Zebras do not have coloured stripes
Lions are animals and they have four legs
If an animal lays eggs it is not a mammal
Pandas eat bamboo or they starve

Formalising in Propositional Logic

Let's imagine we had the function:

Function A(a: boolean, b: boolean, c: boolean):
    if ((a and b) or (!(b or c)))
        return true
    else 
        return false

This function takes three boolean values (true or false) as arguments. Just by looking at it, try to answer the following questions:

When does this function return true (and when does it return false)?
Does it vary depending on a, b, and c, or does it always return the same value regardless of the values of a, b, and c?
If if does always return the same value, which value is it?
Is there a simpler way to write the same test?

Such answers are not obvious. If this function was performing a critical role in, say, flying an aeroplane, would you be confident to trust your safety to your answers to the above?

Let's translate the logical condition in the above pseudocode into a statement of propositional logic. (In theory we could automate this to ensure we don't make any transcription errors).

\[ (p \wedge q) \vee (\neg(q \vee r )) \]

This does not answer our questions, but its the first necessary step. Continue reading to see how we can prove properties about statements like this one using truth tables.

When we talk to each other, we often confuse our meaning.

For example, imagine I said to you:

"Bill is happy if John or Mary are happy"

Now consider whether the statement is still true in the following circumstances:

What if John and Mary are both happy?
What if neither of John or Mary are happy?

Both of these questions are ambiguous meaning you could interpret the statement as being either true or false! While this might not matter in a casual conversation where differences of opinion can soon be resolved, such ambiguities cause philosophers headaches.

Happily, we can resolve all ambiguity by formalising our statement in logic:

\[ (p \vee q) \implies r \]

Which literally translates to:

"If John is happy or Mary is happy then Bill is happy"

Note that despite looking similar in natural language, the propositions "John is happy", "Mary is happy" and "Bill is happy" are completely unrelated when it comes to propositional logic. We will see how to get closer to the natural language meaning when we learn about predicate logic in a later lecture.

Atomic and compound propositions

An atomic proposition contains no logical operators, e.g.

$ A = $ "John loves Mary"

A compound proposition combines atomic propositions, e.g.

\[ (A \vee B) \vee \neg A \]

"John loves Mary or John is happy, or John does not love Mary"

Formalising language

Question

What are the atomic propositions in the sentence

"Bill is happy if John or Mary are happy"

Formalising language

Take the sentence

"Bill is happy if John or Mary are happy"

Given the atomic propositions:

A = John is happy

B = Mary is happy

C = Bill is happy

We can formalise this:

$ (A \vee B) \implies C $
$ (A \vee B) \Longleftrightarrow C $
$ ((A \vee B) \wedge \neg(A \wedge B)) \implies C $

Reasoning about code

Complex logical expressions are hard to debug

if ( ( a and b ) or ( ! ( b or c ) ) )

We might formalise this using logic

\[ (A \wedge B) \vee (\neg(B \vee C)) \]

We will see techniques for simplifying and proof

Truth Tables

We have been busy formalising pseudocode and natural language into propositional logic. Formalising means to convert into a string of symbols following well defined rules. The symbols, and their meanings have now been introduced. We will get to the rules of this system a little later on.

However, now that we can formalise logical statements into propositional logic, what next? If doing this did not give any benefit, there would be no use in doing so. The payoff for the work of formalising is rigour. The more rigorous, the less possibility for error. At the highest level of rigour we will see the formal proof.

We can go about constructing proofs in different ways. We will start with a method of proof called a truth table. Later in this lecture we will create formal proofs.

Let's say we want to show that a statement of propositional logic is always true; or conversely, always false; or perhaps we want to show that two statements are equivalent. Perhaps we want to show that there is precisely one assignment of variables for which a statement is true.

Truth tables are a way of exhaustively proving claims in propositional logic by enumerating all possible situations. They are a structured form of representing the truth or falsity of a statement of propositional logic given a particular assignment of truth values to its atomic propositions.

Truth Tables

Proof using a truth table

We approach proof using a truth table by working step by step in the same way. We begin by writing the truth values that the atomic propositions can take. Then, in each subsequent column, we apply a single operation to what we have calculated before. Thus our first columns would be $p$ and $q$, because these are our atomic propositions (and these are always written first). Then we calculate $p \vee q$ for each value of $p$ and $q$ in our table. This gives us another column. Looking at the above statement, we can see we will also need to calculate $\neg p$. Once we have calculated the values of these, we can calculate $(p \vee q) \vee \neg p$ by applying just a single operation, in this case, disjunction.

$p$	$q$	$p \vee q$	$\neg p$	$(p \vee q) \vee \neg p $
true	true	true	false	true
true	false	true	false	true
false	true	true	true	true
false	false	false	true	true

In this case we can see that, no matter the assignment of truth values to $p$ and $q$, the statement $(p \vee q) \vee \neg p $ is always true. The above truth table constitutes a proof of this claim.

Now we know that whenever this statement appears its value will alway be true.

\[ (p \vee q) \vee \neg p \Longleftrightarrow \top \]

Observe that this holds no matter how we label $p$ and $q$. That we have written $p$ using the symbol 'p' has no bearing on the proof. We could rewrite the whole thing labeling $p$ as $r$, or indeed any other symbol. Thus any time the above pattern appears (even if $p$ and $q$ are themselves compound propositions), we can rewrite it as $true$.

Proof with truth tables

Task

Prove $ (p \vee q) \vee \neg p $ is a tautology

Approach

Create columns for propositional variables

$p$	$q$
T	T
T	F
F	T
F	F

Proof with truth tables

Task

Prove $ (p \vee q) \vee \neg p $ is a tautology

Approach

Create columns for propositional variables
Create a column for $p \vee q$

$p$	$q$	$p \vee q$
T	T	T
T	F	T
F	T	T
F	F	F

Proof with truth tables

Task

Prove $ (p \vee q) \vee \neg p $ is a tautology

Approach

Create columns for propositional variables
Create a column for $p \vee q$
Create a column for $\neg p$

$p$	$q$	$p \vee q$	$\neg p$
T	T	T	F
T	F	T	F
F	T	T	T
F	F	F	T

Proof with truth tables

Task

Prove $ (p \vee q) \vee \neg p $ is a tautology

Approach

Create columns for propositional variables
Create a column for $p \vee q$
Create a column for $\neg p$
Create a column for $(p \vee q) \vee \neg p $

$p$	$q$	$p \vee q$	$\neg p$	$(p \vee q) \vee \neg p $
T	T	T	F	T
T	F	T	F	T
F	T	T	T	T
F	F	F	T	T

Proof with truth tables

Proof

$(p \vee q) \vee \neg p $ is true for every value of $p$ and $q$, therefore it is a tautology

$p$	$q$	$p \vee q$	$\neg p$	$(p \vee q) \vee \neg p $
T	T	T	F	T
T	F	T	F	T
F	T	T	T	T
F	F	F	T	T

Proving statements are equivalent

To generalise this, Whenever we have two columns in a truth table with identical values for all truth-value assignments to its atomic propositions, we can say those two propositions are equivalent. This is obvious if you think about it: we have shown that for every possible value of each atomic proposition, the propositions return the same value.

In the following example, we prove that $p \implies q$ and $(\neg p) \vee q$ are equivalent:

$p$	$q$	$p \implies q$	$(\neg p) \vee q$
true	true	true	true
true	false	false	false
false	true	true	true
false	false	true	true

Thus it is the case that

\[ p \implies q \Longleftrightarrow (\neg p) \vee q \]

Equivalence proof application

Imagine we have the following functions in our code. What is the effect of replacing function A with function B?

The examples here are kept simple, but you could imagine a similar situation arising with more complex propositions.

Function A(a, b):
    if (!a or !b)
        return true
    else
        return false

Function B(a, b):
    if (!(a and b))
        return true 
    else
        return false

In this case, we can formalise the relevant conditions as $\neg p \vee \neg q $ and $\neg (a \wedge b) $. We can construct a truth table as follows:

$p$	$q$	$\neg p$	$\neg q$	$p \wedge q $	$\neg p \vee \neg q$	$\neg (a \wedge b) $
true	true	false	false	true	false	false
true	false	false	true	false	true	true
false	true	true	false	false	true	true
false	false	true	true	false	true	true

Thus from this truth table we have proved that

\[ \neg p \vee \neg q \Longleftrightarrow \neg (a \wedge b) \]

Therefore we can see that function A and function B are indeed identical.

Proving equivalence

Task

Prove $p \implies q$ and $(\neg p) \vee q$ are logically equivalent

Approach

Create columns for propositional variables

$p$	$q$
T	T
T	F
F	T
F	F

Proving equivalence

Task

Prove $p \implies q$ and $(\neg p) \vee q$ are logically equivalent

Approach

Create columns for propositional variables
Complete the column for $p \implies q$

$p$	$q$	$p \implies q$
T	T	T
T	F	F
F	T	T
F	F	T

Proving equivalence

Task

Prove $p \implies q$ and $(\neg p) \vee q$ are logically equivalent

Approach

Create columns for propositional variables
Complete the column for $p \implies q$
Complete the column for $(\neg p) \vee q$

$p$	$q$	$p \implies q$	$(\neg p) \vee q$
T	T	T	T
T	F	F	F
F	T	T	T
F	F	T	T

Proving equivalence

Proof

$p \implies q$ and $(\neg p) \vee q$ have the same truth value for every assignment of $p$ and $q$.

$p$	$q$	$p \implies q$	$(\neg p) \vee q$
T	T	T	T
T	F	F	F
F	T	T	T
F	F	T	T

Tautologies, Contradictions, and Contingencies

Tautology

Always true no matter the values of its atomic propositions, e.g.

$p \Leftrightarrow p $
$p \vee ¬p$

We can generalise this schematically. Let $\phi$ be a well-formed formula of propositional logic, then:

$\phi ⟺ \phi$
$\phi \vee ¬\phi$

Contradiction

Always false no matter the truth values of its atomic propositions, e.g.

$p ⟺ ¬p $
$p \wedge ¬p $

Where $\phi$ is a well-formed formula of propositional logic, the following are contradictions:

$\phi ⟺ \neg \phi$
$\phi \vee ¬\phi$

Contingency

Either true or false depending on the truth values associated with it, e.g.

$p \Longleftrightarrow q$
$p \implies q$
$p \vee q$

Axiom Schema

There is something inelegant about such exhaustive proofs. What we are doing is enumerating every possible situation. so far this has been fine, because we have been dealing with only a small number of atomic propositions, and a logic with only two truth values. However, to limit ourselves to only exhaustive proofs would become limiting.

Thus we will learn a bit more about proof. In particular, formal proof.

In mathematics, a mathematician may believe something is true. This is called a conjecture. There are some famous conjectures that no one has yet managed to prove, such as Goldbach's conjecture. Once a proof has been found for a conjecture, it is called a theorem. For example, Pythagoras' theorem is named such because there exists a proof of it (in fact, many proofs).

All proofs depend on a number of axioms. Axioms are assumptions that are taken, for the purposes of the proof to be true. While usually axioms are obviously true, there have been famous examples when axioms have been assumed that are not necessarily true (for example, the discovery of Non-Euclidean Geometry).

An axiom schema is a template that allows you to derive an infinite number of axioms for a formal system. Any well-formed formula of the formal system can be substituted for a schematic letter (e.g. $\phi, \chi, \psi$) to generate an axiom.

The axiom schema $ \neg \neg \phi \Longleftrightarrow \phi $ defines an infinite set of axioms, obtained by substituting formulas for $\phi$, including

$ \neg \neg (p) \Longleftrightarrow (p) $
$ \neg \neg (p \vee q) \Longleftrightarrow (p \vee q) $
$ \neg \neg (p \wedge q) \Longleftrightarrow (p \wedge q) $
...

Axiom Schema

Logical Reasoning

We will formalise deduction with axiom schema, e.g.

\[ \phi \vee ¬\phi \]

Let $\phi$, $\chi$, $\psi$ stand for any well-formed statements of propositional logic

An axiom schema is a tautology in terms of these schematic letters

Axiom Schema

The axiom schema $ \neg \neg \phi \Longleftrightarrow \phi $ defines an infinite set of axioms, e.g.

$ \neg \neg (p) \Longleftrightarrow (p) $
$ \neg \neg (p \vee q) \Longleftrightarrow (p \vee q) $
$ \neg \neg (p \wedge q) \Longleftrightarrow (p \wedge q) $
...

As these are equivalences, they can be read as rewriting rule, e.g.

\[ \neg \neg (p) \curvearrowright (p) \]

Negation Laws

Negation laws

Law 1.1: Complements

\[ (\neg \top) \Longleftrightarrow \bot \]

\[ (\neg \bot) \Longleftrightarrow \top \]

Law 1.2: Double Negation

\[ (\neg \neg \phi) \Longleftrightarrow \phi \]

Simple proof example

A proof in propositional logic is a series of statements of propositional logic. Each statement is a theorem (i.e. something that is proved)

The statements present a step-by-step argument. They must be connected by inference rules (the laws of our logic). Eventually we relate all of our statements to an axiom. We either start with an axiom and derive theorems from it; or start with the thing to prove and work backwards to an axiom