1. Introduction

I’m a mathematical barbarian, but a few days ago I broke into the ivory tower of mathematics and learnt some of the basics. In order to help me learn it, I wrote this tutorial. It helped me, and perhaps you’ll find it useful too.

1.2. Forum

If you have any comments on this book, please visit https://groups.google.com/forum/#!forum/glimpse-of-mathematics.

The source code for the book is at https://github.com/tlocke/maths.

1.3. Formats

This book is available in the following formats:

 Web http://maths.tlocke.org.uk/ EPUB http://maths.tlocke.org.uk/maths.epub

2. Propositional Logic 2.1. True and false

In the realm of Propositional Logic, I found that they deal with things that are either true or false. In the English language, sentences that are either true or false are known as statements. Here are some sentences together with explanations of whether they are statements or not:

How many miles to Crinnis?

This is a question, so not a statement.

Elephants have four legs.

Yay, an actual statement! It’s a sentence that is either true or false.

Don’t dilly-dally.

This isn’t true or false, it sounds like someone admonishing somebody. Not a statement.

The capital of France is Paris.

Yes, a statement.

He likes chocolate.

This sounds like a statement, but according to those logicians in the ivory tower it doesn’t count because it relies on knowing who ‘he’ is.

Don’t spoil the ship for a ha’peth of tar.

This is a proverb, not a statement.

I’ve got this nagging doubt in my mind. Most statements I can think of aren’t totally ambiguous. Take the ‘Elephants have four legs’ example. Maybe there’s a three legged elephant in existence, perhaps one in a zoo got gangrene or something and had to have a leg amputated…​ Nevertheless, let’s suspend our disbelief and imagine all those perfect statements.

At that point, Alfred Tarski spoke up, ‘What about this then?’.

This statement is false.

Well, I’m not sure what to do. It seems like a statement, but if it’s true then it’s false, and if it’s false then it’s true! Okay, let’s get round it by saying that this isn’t really a statement. What do you think Taski? But Tarski’s mind was on other things…​

Questions

1. Which of the following are statements?

1. Who is John Galt?

2. He’s over there.

3. Three divided by three is one.

4. Belgium is a European country.

5. Praise be!

6. Blue is a colour.

2. Are the following statements true or false?

1. Four is greater than two.

2. Tennis is a colour.

3. A square has eight sides.

4. A cube has eight corners.

5. Birmingham is a city in England.

6. The word ‘rotavator’ is a palindrome.

1. Not a statement.

2. Not a statement.

3. A statement.

4. A statement.

5. Not a statement.

6. A statement.

1. True.

2. False.

3. False.

4. True.

5. True.

6. True.

2.2. Compound Statements

It seems that the next thing the logicians do is string together simple statements to make compound statements. So two simple statements might be:

Abelard likes coffee.
Abelard likes cake.

And a compound statement formed from these two simple statements is:

Abelard likes coffee and Abelard likes cake.

We’ve joined the two simple statements together with the logical conective ‘and’. This compound statement is true if both the simple statements are true, otherwise it is false. Another compound statement we can make from our two simple statements is:

Abelard likes coffee or Abelard likes cake.

Here’s we’ve joined the two simple statements together with the logical connective ‘or’. This compound statment is false if both simple statements are false, otherwise it’s true.

Questions

1. Are the following compound statements true or false?

1. The film Erin Brokovich stars Julia Roberts and 16 is greater than 4.

2. London is the capital of France or Paris is the capital of France.

3. Some people have brown eyes and humans lay eggs.

4. Four multiplied by two is twenty or it has never rained in Wales.

5. Toothpaste is harder than diamond and less than 100 films have ever been made.

1. True.

2. True.

3. False.

4. False.

5. False.

2.3. Formulas

Rather than always writing statements out in full, those work-shy logicians write them in a shorthand. First they label each simple statement with a capital letter of the alphabet. They call the label an atomic formula. Then they use funny symbols to denote logical connectives. Here’s a table of the symbols used for logical connectives:

Logical connective Symbol

and

or

So for the compound statement:

Abelard likes coffee and Abelard likes cake.

the two simple statements can have the atomic formulas P and Q:

P: Abelard likes coffee.
Q: Abelard likes cake.

and the compound statement can be written as the compound formula:

(P ∧ Q)

Now that we’ve said what P and Q stand for we can take this compound statement:

Abelard likes coffe or Abelard likes cake.

and write it using the atomic formulas to give the compound formula:

(P ∨ Q)

You’ll notice that the formulas have brackets round them. This is useful for later on when formulas get more complicated.

Let’s say that Abelard does like coffee, but doesn’t like cake. Then:

P is true
Q is false

Then using our common sense reasoning we know that it isn’t true that Abelard likes coffee and likes cake, so this is written formally as:

(P ∧ Q)
(true ∧ false)
false

and also we know that it is true that either Abelard likes coffee or Abelard likes cake and this is written formally as:

(P ∨ Q)
(true ∨ false)
true

This process of taking a formula and substituting in the true or false values and working out if the formula as a whole is true or false, they call evaluating the formula for particular values.

Questions

1. Write the following compound statements as formulas:

1. The film Erin Brokovich stars Julia Roberts and 16 is greater than 4.

2. London is the capital of France or Paris is the capital of France.

3. Some people have brown eyes and humans lay eggs.

4. Four multiplied by two is twenty or it has never rained in Wales.

5. Toothpaste is harder than diamond and less than 100 films have ever been made.

2. For each of the formulas in your answers to question 1, evalute them using values of the atomic formulas from your general knowledge.

1. Write the following compound statements as formulas:

1. The film Erin Brokovich stars Julia Roberts and 16 is greater than 4.
P: The film Erin Brokovich stars Julia Roberts.
Q: 16 is greater than 4.
(P ∧ Q)

2. London is the capital of France or Paris is the capital of France.
A: London is the capital of France.
B: Paris is the capital of France.
(A ∨ B)

3. Some people have brown eyes and humans lay eggs.
P: Some people have brown eyes.
Q: Humans lay eggs.
(P ∧ Q)

4. Four multiplied by two is twenty or it has never rained in Wales.
P: Four multiplied by two is twenty.
Q: It has never rained in Wales.
(P ∨ Q)

5. Toothpaste is harder than diamond and less than 100 films have ever been made.
P: Toothpaste is harder than diamond.
Q: Fewer than 100 films have ever been made.
(P ∧ Q)

2. For each of the formulas in your answers to question 1, evalute them using values of the atomic formulas from your general knowledge.

1. The film Erin Brokovich stars Julia Roberts and 16 is greater than 4.
P: The film Erin Brokovich stars Julia Roberts.
Q: 16 is greater than 4.
(P ∧ Q)
P is true
Q is true
(true ∧ true) is true

2. London is the capital of France or Paris is the capital of France.
A: London is the capital of France.
B: Paris is the capital of France.
(A ∨ B)
A is false.
B is true.
(false ∨ true) is true.

3. Some people have brown eyes and humans lay eggs.
P: Some people have brown eyes.
Q: Humans lay eggs.
(P ∧ Q)
P is true.
Q is false.
(true ∧ false) is true.

4. Four multiplied by two is twenty or it has never rained in Wales.
P: Four multiplied by two is twenty.
Q: It has never rained in Wales.
(P ∨ Q)
P is false.
Q is false.
(false ∨ false) is false.

5. Toothpaste is harder than diamond and less than 100 films have ever been made.
P: Toothpaste is harder than diamond.
Q: Fewer than 100 films have ever been made.
(P ∧ Q)
P is false.
Q is false.
(false ∧ false) is false.

2.4. Ambiguous Compound Statements

Here’s an ambiguous compound statement:

London is the capital of the UK or London is the capital of France and Paris is the captital of the UK.

Assigning labels to the simple statements:

P: London is the capital of the UK.
Q: London is the capital of France.
R: Paris is the capital of the UK.

the compound statement can be transated into two formulas with different meanings:

((P ∨ Q) ∧ R)
(P ∨ (Q ∧ R))

‘Hold on, you blithely said that these two formulas have different meanings, but how do you know that?’. Good point, erm, what would Bertrand Russell do? Bear with me. Okay, using our geography knowledge we know that P is true, Q is false and R is false and so evaluating the first formula gives:

((P ∨ Q) ∧ R)
((true ∨ false) ∧ false)
(true ∧ false)
false

and the second formula evaluates to:

(P ∨ (Q ∧ R))
(true ∨ (false ∧ false))
(true ∨ false)
true

So when substituting in the same values, the first formula evaluates to false and the second evaluates to true, and so the two formulas are different.

I think what the Ivory Tower is teaching me here is that even though I started out translating from English (what they call a natural language) to formulas (what they call a formal language), it turns out that as well as being shorter, formulas are unambiguous. It seems to me that the English statements are just a jumping off point, and formulas are much better at describing this mathematical realm. W00t, I said, ‘mathematical realm’!!!

Questions

1. For the following ambiguous compound statements in English, write down all the possible meanings as formulas.

1. Two is less than four or Alaska begins with A and purple is a number.

2. Purple is a number and Alaska begins with A or two is less than four.

2. For each of the answers in question 1, evaluate the formulas using the values that you know from general knowledge.

1. For the following ambiguous compound statements in English, write down all the possible meanings as formulas.
P: Two is less than four.
Q: Alaska begins with A.
R: Purple is a number.

1. Two is less than four or Alaska begins with A and purple is a number.
(P ∨ (Q ∧ R))
((P ∨ Q) ∧ R)

2. Purple is a number and Alaska begins with A or two is less than four.
(R ∧ (Q ∨ P))
((R ∧ Q) ∨ P)

2. For each of the answers in question 1, evaluate the formulas using the values that you know from general knowledge. P: Two is less than four.
Q: Alaska begins with A.
R: Purple is a number. P is true
Q is true R is false

1. Two is less than four or Alaska begins with A and purple is a number.
(P ∨ (Q ∧ R))
(true ∨ (true ∧ false))
(true ∨ false)
true

((P ∨ Q) ∧ R)
((true ∨ true) ∧ false)
(true ∧ false)
false

2. Purple is a number and Alaska begins with A or two is less than four.
(R ∧ (Q ∨ P))
(false ∧ (true ∨ true))
(false ∧ true)
false

((R ∧ Q) ∨ P)
((false ∧ true) ∨ true)
(false ∨ true)
true

2.5. Interpretations

Say you’ve got a formula:

(P ∧ Q)

To logicians, an interpretation (also called a truth assignment) is the assignment of true or false to P and Q. So one interpretation is:

P is false
Q is false

and another is:

P is true
Q is false

so for a compound formula with two atomic formulas, there are four possible interpretations:

P Q

True

True

False

True

True

False

False

False

and to make it easier to write they use T for true and F for false:

P Q

T

T

F

T

T

F

F

F

Questions

1. For a compound formula with three atomic formulas, there are eight possible interpretations. Show those eight possible interpretation in a table.

1. For a compound formula with three atomic formulas, there are eight possible interpretations. Show those eight possible interpretation in a table.

P Q R

T

T

T

F

T

T

T

F

T

F

F

T

T

T

F

F

T

F

T

F

F

F

F

F

2.6. Truth Tables

A truth table. A medieval device for extracting a confession? No, a mathematical device for showing if a formula is true or false for every possible interpretation. The truth table for (P ∧ Q) is:

P Q (P ∧ Q)

T

T

T

F

T

F

T

F

F

F

F

F

so what we’ve done is written a row for each interpretation of P and Q, and then in the final column we’ve put the result of evaluating (P ∧ Q). The truth table for (P ∨ Q) is:

P Q (P ∨ Q)

T

T

T

F

T

T

T

F

T

F

F

F

You can use a truth table to show that (P ∧ Q) means the same as (Q ∧ P):

P Q (P ∧ Q) (Q ∧ P)

T

T

T

T

F

T

F

F

T

F

F

F

F

F

F

F

For each interpretation, the last two columns are the same, and so (P ∧ Q) means the same as (Q ∧ P).

Questions

1. Use a truth table to show that (P ∨ Q) means the same thing as (Q ∨ P).

1. Use a truth table to show that (P ∨ Q) means the same thing as (Q ∨ P).

P Q (P ∨ Q) (Q ∨ P)

T

T

T

T

F

T

T

T

T

F

T

T

F

F

F

F

For each row of the truth table, the last two columns are the same, and so (P ∨ Q) means the same as (Q ∨ P).

2.7. Not

There’s another logical connective called not, which has the symbol ¬ and the truth table:

P (¬P)

T

F

F

T

Usually the brackets are omitted for ¬, so when you see:

¬P

it’s taken to mean:

(¬P)

Anyway, let us cast it loose amongst the other functions and employ the truth table to see what results. Picking a formula at random, let’s try:

((¬P) ∨ Q)

which gives the truth table:

P Q ¬P (¬P ∨ Q)

T

T

F

T

F

T

T

T

T

F

F

F

F

F

T

T

Let us now extract a full confession from:

¬(P ∨ Q)

which gives the truth table:

P Q (P ∨ Q) ¬(P ∨ Q)

T

T

T

F

F

T

T

F

T

F

T

F

F

F

F

T

One other thing, the first two logical connectives we encountered (∧ and ∨) both acted on two formulas, and so they’re known as binary connectives. The ¬ connective acts on one formula and so is called a unary connective.

Questions

1. Give the truth tables for:

1. ¬(P ∧ Q)

2. (P ∨ ¬Q)

3. ¬¬P

4. ¬((P ∨ Q) ∨ R)

5. ¬((P ∨ Q) ∧ R)

1. Give the truth tables for:

1. ¬(P ∧ Q)

P Q (P ∧ Q) ¬(P ∧ Q)

T

T

T

F

F

T

F

T

T

F

F

T

F

F

F

T

2. (P ∨ ¬Q)

P Q ¬Q (P ∨ ¬Q)

T

T

F

T

F

T

F

F

T

F

T

T

F

F

T

T

3. ¬¬P

P ¬P ¬¬P

T

F

T

F

T

F

4. ¬((P ∨ Q) ∨ R)

P Q R (P ∨ Q) ((P ∨ Q) ∨ R) ¬((P ∨ Q) ∨ R)

T

T

T

T

T

F

F

T

T

T

T

F

T

F

T

T

T

F

F

F

T

F

T

F

T

T

F

T

T

F

F

T

F

T

T

F

T

F

F

T

T

F

F

F

F

F

F

T

5. ¬((P ∨ Q) ∧ R)

P Q R (P ∨ Q) ((P ∨ Q) ∧ R) ¬((P ∨ Q) ∧ R)

T

T

T

T

T

F

F

T

T

T

T

F

T

F

T

T

T

F

F

F

T

F

F

T

T

T

F

T

F

T

F

T

F

T

F

T

T

F

F

T

F

T

F

F

F

F

F

T

2.8. Satisfaction

‘Sir, I demand satisfaction!’. Yeah, we’re not in Poldark, they don’t watch that in their Ivory Tower. Why waste time on TV dramas when you could be doing maths?

An interpretation satisfies a formula if it is true under that interpretation. An example you say? An example? Okay, okay, you started off humble and now you’re making demands. I just feel you need to take a moment to think about your attitude to this whole thing.

Under the interpretation:

P is false
Q is true

the formula:

(¬P ∧ Q)

evaluates to:

(¬false ∧ true)
(true ∧ true)
true

since it’s true, we can say that this interpretation satisfies this formula. ‘Could you show me another example please?’, ‘Certainly dear reader’. Under the interpretation:

A is true
B is true
C is true

the formula:

((B ∨ A) ∨ ¬C)

evaluates to:

((true ∨ true) ∨ ¬true)
(true ∨ false)
true

and so this interpretation satisfies this formula.

Questions

1. For the following pairs of formulas and interpretations, show that the interpretation satisfies the formula:

1. (P ∨ Q) when P is true and Q is false.

2. (¬P ∨ ¬Q) when P is true and Q is false.

3. (¬A ∧ B) when A is false and B is true.

1. For the following pairs of formulas and interpretations, show that the interpretation satisfies the formula:

1. (P ∨ Q) when P is true and Q is false.
(P ∨ Q)
(true ∨ false)
true
so the interpretation satisfies the formula.

2. (¬P ∨ ¬Q) when P is true and Q is false.
(¬P ∨ ¬Q)
(¬true ∨ ¬false)
(false ∨ true)
true so the interpretation satisfies the formula.

3. (¬A ∧ B) when A is false and B is true.
(¬A ∧ B)
(¬false ∧ true)
(true ∧ true)
true
so the interpretation satisfies the formula.

2.9. Falsification

This is the opposite of satisfaction. An interpretation falsifies a formula if it is false under that interpretation. Under the interpretation:

P is true
Q is true

the formula:

(¬P ∧ Q)

evaluates to:

(¬true ∧ true)
(false ∧ true)
false

since it’s false, we can say that this interpretation falsifies this formula. Under the interpretation:

A is true
B is true
C is true

the formula:

((B ∨ A) ∧ ¬C)

evaluates to:

((true ∨ true) ∧ ¬true)
(true ∧ false)
false

and so this interpretation satisfies this formula.

Questions

1. For the following pairs of formulas and interpretations, show that the interpretation falsifies the formula:

1. (P ∨ Q) when P is false and Q is false.

2. (¬P ∨ ¬Q) when P is true and Q is true.

3. (¬A ∧ B) when A is false and B is false.

1. For the following pairs of formulas and interpretations, show that the interpretation falsifies the formula:

1. (P ∨ Q) when P is false and Q is false.
(P ∨ Q)
(false ∨ false)
false
so the interpretation falsifies the formula.

2. (¬P ∨ ¬Q) when P is true and Q is true.
(¬P ∨ ¬Q)
(¬true ∨ ¬true)
(false ∨ false)
false so the interpretation falsifies the formula.

3. (¬A ∧ B) when A is false and B is false. (¬A ∧ B)
(¬false ∧ false)
(true ∧ false)
false
so the interpretation falsifies the formula.

2.10. Valid Formula

The formula:

(P ∨ ¬P)

has the truth table:

P ¬P (P ∨ ¬P)

T

F

T

F

T

T

which shows that every possible interpretation satisfies the formula. In the Tower such a formula is called a valid formula.

Questions

1. Using a truth table, show that the following formula is valid:

1. ((P ∨ Q) ∨ ¬P)

1. Using a truth table, show that the following formula is valid:

1. ((P ∨ Q) ∨ ¬P)

P Q ¬P (P ∨ Q) ((P ∨ Q) ∨ ¬P)

T

T

F

T

T

F

T

T

T

T

T

F

F

T

T

F

F

T

F

T

so the formula is valid.

2.11. Unsatisfiable Formula

The formula:

(P ∧ ¬P)

has the truth table:

P ¬P (P ∨ ¬P)

T

F

F

F

T

F

which shows that every possible interpretation falsifies the formula. In the Tower such a formula is called an unsatisfiable formula.

Questions

1. Using truth tables, show that the following formulas are unsatisfiable:

1. ((P ∧ Q) ∧ ¬(P ∧ Q))

2. (P ∧ (Q ∧ ¬P))

3. ((¬P ∧ ¬Q) ∧ ¬(¬P ∧ ¬Q))

4. (((P ∧ ¬P) ∧ Q) ∧ R)

1. Using truth tables, show that the following formulas are unsatisfiable:

1. ((P ∧ Q) ∧ ¬(P ∧ Q))

P Q (P ∧ Q) ¬(P ∧ Q) ((P ∧ Q) ∧ ¬(P ∧ Q))

T

T

T

F

F

F

T

F

T

F

T

F

F

T

F

F

F

F

T

F

so unsatisfiable.

2. (P ∧ (Q ∧ ¬P))

P Q ¬P (Q ∧ ¬P) (P ∧ (Q ∧ ¬P))

T

T

F

F

F

F

T

T

T

F

T

F

F

F

F

F

F

T

F

F

so the formula is unsatisfiable.

3. (((P ∧ ¬P) ∧ Q) ∧ R)

P Q ¬P ¬Q (¬P ∧ ¬Q) ¬(¬P ∧ ¬Q) ((¬P ∧ ¬Q) ∧ ¬(¬P ∧ ¬Q))

T

T

F

F

F

T

F

F

T

T

F

F

T

F

T

F

F

T

F

T

F

F

F

T

T

T

F

F

so the formula is unsatisfiable.

4. (((P ∧ ¬P) ∧ Q) ∧ R)

P Q R ¬P (P ∧ ¬P) ((P ∧ ¬P) ∧ Q) (((P ∧ ¬P) ∧ Q) ∧ R)

T

T

T

F

F

F

F

F

T

T

T

F

F

F

T

F

T

F

F

F

F

F

F

T

T

F

F

F

T

T

F

F

F

F

F

F

T

F

T

F

F

F

T

F

F

F

F

F

F

F

F

F

T

F

F

F

so unsatisfiable.

2.12. Contingent Formula

A formula that is neither valid nor unsatisfiable is said to be contingent. For example the formula:

P ∧ Q

has the truth table:

P Q P ∧ Q

T

T

T

F

T

F

T

F

F

F

F

F

which shows that the formula is neither valid not unsatisfiable and so it is contingent. Another way of putting it is to say that a formula is contingent if it is both satisfiable and falsifiable.

Questions

1. Using truth tables, show that the following formulas are contingent:

1. (P ∧ ¬Q)

2. P

3. P ∨ Q

4. ¬P

1. Using truth tables, show that the following formulas are contingent:

1. (P ∧ ¬Q)

P Q ¬Q (P ∧ ¬Q)

T

T

F

F

F

T

F

T

T

F

T

T

F

F

T

F

so the formula is neither valid or unsatisfiable and so it’s contingent.

2. P

P

T

F

so the formula is neither valid or unsatisfiable and so it’s contingent.

3. P ∨ Q

P Q P ∨ Q

T

T

T

F

T

T

T

F

T

F

F

F

so the formula is neither valid or unsatisfiable and so it’s contingent.

4. ¬P

P ¬P

T

T

F

F

T

F

T

F

T

F

F

T

so the formula is neither valid or unsatisfiable and so it’s contingent.

2.13. Implies

There’s another binary connective called implies that has the truth table:

P Q (P → Q)

T

T

T

F

T

T

T

F

F

F

F

T

Take the two simple statements:

Abelard is at the cafe.
The cafe is open.

Joining the two with an implication could give the compound statement:

Abelard is at the cafe only if the cafe is open.

If Abelard really is at the cafe and the cafe really is open, then this compound statement is true. If Abelard isn’t at the cafe, then whether or not the cafe is open, the compound statement is still true (another way of putting it is to say that if Abelard is not at the cafe, then this is still consistent with with the statement that ‘Abelard is at the cafe only when the cafe is open’). The only time the compound statement is false is if Abelard is at the cafe but the cafe is not open.

There are a few different ways that ‘implies’ occurs in English. The statement:

Abelard is at the cafe only if the cafe is open.

could be written in these alternative ways:

• If Abelard is at the cafe then the cafe is open.

• Abelard being at the cafe implies that the cafe is open.

• The cafe being open is a necessary condition for Abelard to be at the cafe.

• The cafe being open follows from Abelard being at the cafe.

Here’s an example of → in action. The formula:

((P ∧ ¬Q) → Q)

Has the truth table:

P Q ¬Q (P ∧ ¬Q) P ∧ ¬(Q → Q)

T

T

F

F

T

F

T

F

F

T

T

F

T

T

F

F

F

T

F

T

Another example; the truth table for (Q → (P ∧ ¬Q)) is:

P Q ¬Q (P ∧ ¬Q) (Q → (P ∧ ¬Q))

T

T

F

F

F

F

T

F

F

F

T

F

T

T

T

F

F

T

F

T

Questions

1. Write the following English statements as logical formulas:

1. The washing is out only if it’s a dry day.

2. If Keith is in Bath, then Keith is in England.

3. The sky being red at night implies that the shepherds are delighted.

2. Create a truth table for each of the following formulas:

1. (¬P → Q)

2. (Q → ¬Q)

3. ((P → Q) ∨ P)

4. (¬(P ∧ Q) → (¬P ∨ ¬Q))

5. ((P ∧ (P → Q)) → ¬P)

1. Write the following English statements as logical formulas:

1. The washing is out only if it’s a dry day.
P: The washing is out.
Q: It’s a dry day.
(P → Q)

2. If Keith is in Bath, then Keith is in England.
A: Keith is in Bath.
B: Keith is in England.
(A → B)

3. The sky being red at night implies that the shepherds are delighted. A: The sky is red at night.
B: The shepherds are delighted.
(A → B)

2. Create a truth table for each of the following formulas:

1. (¬P → Q)

P Q ¬P (¬P → Q)

T

T

F

T

F

T

T

T

T

F

F

T

F

F

T

F

2. (Q → ¬Q)

Q ¬Q (Q → ¬Q)

T

F

F

F

T

T

3. ((P → Q) ∨ P)

P Q (P → Q) ((P → Q) ∨ P)

T

T

T

T

F

T

T

T

T

F

F

T

F

F

T

T

4. (¬(P ∧ Q) → (¬P ∨ ¬Q))

P Q (P ∧ Q) ¬(P ∧ Q) ¬P ¬Q (¬P ∨ ¬Q) (¬(P ∧ Q) → (¬P ∨ ¬Q))

T

T

T

F

F

F

F

T

F

T

F

T

T

F

T

T

T

F

F

T

F

T

T

T

F

F

F

T

T

T

T

T

5. ((P ∧ (P → Q)) → ¬P)

P Q (P → Q) ¬P (P ∧ (P → Q)) ((P ∧ (P → Q)) → ¬P)

T

T

T

F

T

F

F

T

F

T

F

T

T

F

F

F

F

T

F

F

F

T

F

T

2.14. Biconditional

The biconditional connective is a binary connective with the truth table:

P Q (P ↔ Q)

T

T

T

F

T

F

T

F

F

F

F

T

Translating from English to a formula, the sentence:

It’s Christmas Day if and only if it’s the 25th of December.

is written:

P: It’s Christmas Day.
Q: It’s the 25th of December.
(P ↔ Q)

which of course is true. An example that is false is:

It’s Christmas Day if and only if it’s the 2nd of March.

which is written:

P: It’s Christmas Day.
Q: It’s the 2nd of March.
(P ↔ Q)

Questions

1. Translate the following English sentences into formulas:

1. The bike’s back brake comes on if, and only if, the left brake lever is applied.

2. The fridge light is on if, and only if, the fridge door is open.

2. Give the truth table for each of the following formulas:

1. (A ↔ (B ∧ C))

2. (B ∨ (A ↔ B))

3. (P ∧ ¬(P ↔ (Q ∨ P)))

4. ((Q ↔ ¬P) ∧ (P ↔ ¬¬Q))

1. Translate the following English sentences into formulas:

1. The bike’s back brake comes on if, and only if, the left brake lever is applied.
P: The bike’s back brake comes on.
Q: The left brake lever is applied.
(P ↔ Q)

2. The fridge light is on if, and only if, the fridge door is open.
P: The fridge light is on.
Q: The fridge door is open.
(P ↔ Q)

2. Give the truth table for each of the following formulas:

1. (A ↔ (B ∧ C))

A B C (B ∧ C) (A ↔ (B ∧ C)

T

T

T

T

T

F

T

T

T

F

T

F

T

F

F

F

F

T

F

T

T

T

F

F

F

F

T

F

F

T

T

F

F

F

F

F

F

F

F

T

2. (B ∨ (A ↔ B))

A B (A ↔ B) (B ∨ (A ↔ B))

T

T

T

T

F

T

F

T

T

F

F

F

F

F

T

T

3. (P ∧ ¬(P ↔ (Q ∨ P)))

P Q (Q ∨ P) (P ↔ (Q ∨ P) ¬(P ↔ (Q ∨ P)) (P ∧ ¬(P ↔ (Q ∨ P)))

T

T

T

T

F

F

F

T

T

F

T

F

T

F

T

T

F

F

F

F

F

T

F

F

4. ((Q ↔ ¬P) ∧ (P ↔ ¬¬Q))

P Q ¬P (Q ↔ ¬P) ¬Q ¬¬Q (P ↔ ¬¬Q) ((Q ↔ ¬P) ∧ (P ↔ ¬¬Q))

T

T

F

F

F

T

T

F

F

T

T

T

F

T

F

F

T

F

F

T

T

F

F

F

F

F

T

F

T

F

T

F

2.15. Identity

If two formulas are an identity (also called logically equivalent), then they mean the same under all interpretations. In other words if two formulas are an identity, then the formula formed by joining them with the ↔ connective will be valid. For example, if the pair of formulas:

(A → B)
(¬A ∨ B)

are an identity, then:

((A → B) ↔ (¬A ∨ B))

will be valid. Its truth table is:

A B (A → B) ¬A (¬A ∨ B) ((A → B) ↔ (¬A ∨ B))

T

T

T

F

T

T

F

T

T

T

T

T

T

F

F

F

F

T

F

F

T

T

T

T

and so indeed we can say that this pair of formulas is an identity. The symbol for identity is ≡, and so we can write the identity as:

(A → B) ≡ (¬A ∨ B)

The two formulas in an identity can be substituted for each other in other formulas, without changing the meaning of those other formulas. The commonly used identities have their own names. The identity that we’ve just found:

(A → B) ≡ (¬A ∨ B)

is called the material implication identity.

Questions

1. Use the material implication identity to rewrite the following formulas while preserving their meaning:

1. (A → B)

2. (¬A ∨ B)

3. (A → ¬B)

4. (A ∨ B)

1. Use the material implication identity to rewrite the following formulas while preserving their meaning:

1. (A → B)
(¬A ∨ B)

2. (¬A ∨ B)
(A → B)

3. (A → ¬B)
(¬A ∨ ¬B)

4. (A ∨ B)
(¬A → B)

2.15.1. Material Equality Identity

Hot on the heels of meeting the Material Implication identity, I encountered the Material Equality identity:

(P ↔ Q) ≡ ((¬P ∨ Q) ∧ (P ∨ ¬Q))

Actually I found loads of these identities in the Tower, some with names, some without. I noted down the ones I thought were important, and the ones that had a pattern to them and skipped over the rest. Is this the right approach?

Questions

1. Use the material equality identity to rewrite the following formulas while preserving their meaning:

1. (P ↔ Q)

2. ((¬P ∨ Q) ∧ (P ∨ ¬Q))

3. ((P ↔ Q) ∧ P)

4. (((P ∨ Q) ∧ (¬P ∨ ¬Q)) ∨ ¬P)

1. Use the material equality identity to rewrite the following formulas while preserving their meaning:

1. (P ↔ Q)
((¬P ∨ Q) ∧ (P ∨ ¬Q))

2. ((¬P ∨ Q) ∧ (P ∨ ¬Q))
(P ↔ Q)

3. ((P ↔ Q) ∧ P)
(((¬P ∨ Q) ∧ (P ∨ ¬Q)) ∧ P)

4. (((P ∨ Q) ∧ (¬P ∨ ¬Q)) ∨ ¬P)
((P ↔ Q) ∨ ¬P)

2.16. Commutativity

A special type of identity that some binary connectives have is commutativity. The connective ∧ is commutative which means that:

(A ∧ B) ≡ (B ∧ A)

This identity is called conjunction commutativity. Not all binary connectives are commutative though. For example the pair of formulas:

(A → B)
(B → A)

is not an identity because:

((A → B) ↔ (B → A))

is not a valid formula, and so → is not commutative. Here’s a table showing the binary functions, and whether they’re commutative or not, and if they are, giving the name of the associated identity.

Binary Function Commutative? Name Of Identity

Yes

conjunction commutativity

Yes

disjunction commutativity

No

Yes

biconditional commutativity

Questions

1. For each of the four binary functions use a truth table to show if they are or are not commutative.

1. For each of the four binary functions use a truth table to show if they are or are not commutative.

1. ∧ is commutative if ((A ∧ B) ↔ (B ∧ A)) is valid.

A B (A ∧ B) (B ∧ A) ((A ∧ B) ↔ (B ∧ A))

T

T

T

T

T

F

T

F

F

T

T

F

F

F

T

F

F

F

F

T

so it is valid and so ∧ is commutative.

2. ∨ is commutative if ((A ∨ B) ↔ (B ∨ A)) is valid.

A B (A ∨ B) (B ∨ A) ((A ∨ B) ↔ (B ∨ A))

T

T

T

T

T

F

T

T

T

T

T

F

T

T

T

F

F

F

F

T

so it is valid and so ∨ is commutative.

3. → is commutative if ((A → B) ↔ (B → A)) is valid.

A B (A → B) (B → A) ((A → B) ↔ (B → A))

T

T

T

T

T

F

T

T

F

F

T

F

F

T

F

F

F

T

T

T

it is not valid and so → is not commutative.

4. ↔ is commutative if ((A ↔ B) ↔ (B ↔ A)) is valid.

A B (A ↔ B) (B ↔ A) ((A ↔ B) ↔ (B ↔ A))

T

T

T

T

T

F

T

F

F

T

T

F

F

F

T

F

F

T

T

T

it is valid and so ↔ is commutative.

2.17. Associativity

Another type of identity that some binary connectives have is associativity. The ∧ connective is associative, which means:

(P ∧ (Q ∧ R)) ≡ ((P ∧ Q) ∧ R)

because the formula:

((P ∧ (Q ∧ R)) ↔ ((P ∧ Q) ∧ R))

is valid. So if you’ve got three formulas joined by ∧, it doesn’t make any difference if the first two are evaluated first, or the last two. This identity is called conjunction associativity. Here’s a table showing all the binary connectives, and whether they’re associative or not, and if they are, giving the name of the identity:

Binary Connective Associative? Name Of Identity

Yes

Conjunction associativity

Yes

Disjunction associativity

No

Yes

Biconditional associativity

Questions

1. For each of the four binary connectives use a truth table to show if they are or are not associative (big truth tables ahoy!).

1. For each of the four binary connectives use a truth table to show if they are or are not associative (big truth tables ahoy!).

1. ∧ is associative if (((A ∧ B) ∧ C) ↔ (A ∧ (B ∧ C))) is valid.

A B C (A ∧ B) ((A ∧ B) ∧ C) (B ∧ C) (A ∧ (B ∧ C)) (((A ∧ B) ∧ C) ↔ (A ∧ (B ∧ C)))

T

T

T

T

T

T

T

T

F

T

T

F

F

T

F

T

T

F

T

F

F

F

F

T

F

F

T

F

F

F

F

T

T

T

F

T

F

F

F

T

F

T

F

F

F

F

F

T

T

F

F

F

F

F

F

T

F

F

F

F

F

F

F

T

it is valid and so ∧ is associative.

2. ∨ is associative if (((A ∨ B) ∨ C) ↔ (A ∨ (B ∨ C))) is valid.

A B C (A ∨ B) ((A ∨ B) ∨ C) (B ∨ C) (A ∨ (B ∨ C)) (((A ∨ B) ∨ C) ↔ (A ∨ (B ∨ C)))

T

T

T

T

T

T

T

T

F

T

T

T

T

T

T

T

T

F

T

T

T

T

T

T

F

F

T

F

T

T

T

T

T

T

F

T

T

T

T

T

F

T

F

T

T

T

T

T

T

F

F

T

T

F

T

T

F

F

F

F

F

F

F

T

it is valid and so ∨ is associative.

3. → is associative if (((A → B) → C) ↔ (A → (B → C))) is valid.

A B C (A → B) ((A → B) → C) (B → C) (A → (B → C)) (((A → B) → C) ↔ (A → (B → C)))

T

T

T

T

T

T

T

T

F

T

T

T

T

T

T

T

T

F

T

F

T

T

T

T

F

F

T

T

T

T

T

T

T

T

F

T

F

F

F

T

F

T

F

T

F

F

T

F

T

F

F

F

T

T

T

T

F

F

F

T

F

T

T

F

it is not valid and so → is not associative.

4. ↔ is associative if (((A ↔ B) ↔ C) ↔ (A ↔ (B ↔ C))) is valid.

A B C (A ↔ B) ((A ↔ B) ↔ C) (B ↔ C) (A ↔ (B ↔ C)) (((A ↔ B) ↔ C) ↔ (A ↔ (B ↔ C)))

T

T

T

T

T

T

T

T

F

T

T

F

F

T

F

T

T

F

T

F

F

F

F

T

F

F

T

T

T

F

T

T

T

T

F

T

F

F

F

T

F

T

F

F

T

F

T

T

T

F

F

F

T

T

T

T

F

F

F

T

F

T

F

T

it is valid and so ↔ is associative.

2.18. Distributivity

Another ‘itivity’. Here are the distributivity identities:

Identity Name

(A ∧ (B ∧ C)) ≡ ((A ∧ B) ∧ (A ∧ C))

Distribution of ∧ over ∧

(A ∧ (B ∨ C)) ≡ ((A ∧ B) ∨ (A ∧ C))

Distribution of ∧ over ∨

(A ∨ (B ∧ C)) ≡ ((A ∨ B) ∧ (A ∨ C))

Distribution of ∨ over ∧

(A ∨ (B ∨ C)) ≡ ((A ∨ B) ∨ (A ∨ C))

Distribution of ∨ over ∨

(A → (B → C)) ≡ ((A → B) → (A → C))

Distribution of → over →

(A → (B ↔ C)) ≡ ((A → B) ↔ (A → C))

Distribution of → over ↔

(A ∨ (B ↔ C)) ≡ ((A ∨ B) ↔ (A ∨ C))

Distribution of ∨ over ↔

Here’s the pattern as I see it. If there are two binary connectives y and z, then if y distributes over z then:

(A y (B z C)) ≡ ((A y B) z (A y C))

Questions

1. For the following distributivity identities use a truth table to show that they really are identities.

1. ∧ over ∧

2. → over ↔

3. ∨ over {equals}

1. For the following distributivity identities use a truth table to show that they really are identities.

1. If ∧ is distributive over ∧ then:
((P ∧ (Q ∧ R)) ↔ ((P ∧ Q) ∧ (P ∧ R))) is valid.

P Q R (Q ∧ R) (P ∧ (Q ∧ R)) (P ∧ Q) (P ∧ R) ((P ∧ Q) ∧ (P ∧ R)) ((P ∧ (Q ∧ R)) ↔ ((P ∧ Q) ∧ (P ∧ R)))

T

T

T

T

T

T

T

T

T

F

T

T

T

F

F

F

F

T

T

F

T

F

F

F

T

F

T

F

F

T

F

F

F

F

F

T

T

T

F

F

F

T

F

F

T

F

T

F

F

F

F

F

F

T

T

F

F

F

F

F

F

F

T

F

F

F

F

F

F

F

F

T

the formula is indeed valid, so ∧ is distributive over ∧.

2. → over ↔ If → is distributive over ↔ then:
((P → (Q ↔ R)) ↔ ((P → Q) ↔ (P → R)))
is valid.

P Q R (Q ↔ R) (P → (Q ↔ R)) (P → Q) (P → R) ((P → Q) ↔ (P → R)) ((P → (Q ↔ R)) ↔ ((P → Q) ↔ (P → R)))

T

T

T

T

T

T

T

T

T

F

T

T

T

T

T

T

T

T

T

F

T

F

F

F

T

F

T

F

F

T

F

T

T

T

T

T

T

T

F

F

F

T

F

F

T

F

T

F

F

T

T

T

T

T

T

F

F

T

T

F

F

T

T

F

F

F

T

T

T

T

T

T

the formula is indeed valid, so → is distributive over ↔.

3. If ∨ is distributive over ↔ then:
((P ∨ (Q ↔ R)) ↔ ((P ∨ Q) ↔ (P ∨ R)))
is valid.

P Q R (Q ↔ R) (P ∨ (Q ↔ R)) (P ∨ Q) (P ∨ R) ((P ∨ Q) ↔ (P ∨ R)) ((P ∨ (Q ↔ R)) ↔ ((P ∨ Q) ↔ (P ∨ R)))

T

T

T

T

T

T

T

T

T

F

T

T

T

T

T

T

T

T

T

F

T

F

T

T

T

T

T

F

F

T

F

F

F

T

F

T

T

T

F

F

T

T

T

T

T

F

T

F

F

F

T

F

F

T

T

F

F

T

T

T

T

T

T

F

F

F

T

T

F

F

T

T

the formula is indeed valid, so ∨ is distributive over ↔.

2.19. Idempotence Figure 2. Benjamin Peirce by www.pragmaticism.net. Licensed under Public Domain via Wikimedia Commons.

‘Hey, Tony’, Benjamin Peirce said as he tapped me on the knee and leaned over confidentially, ‘there’s another type of identity that I call idempotence’. The ∧ connective is idempotent because:

(P ∧ P) ≡ P

and the ∨ connective is idempotent because:

(P ∨ P) ≡ P

but → is not idempotent. So I think what Peirce was telling me is that a connective is idempotent if, when it joins a formula with itself, you end up with the formula again. Like those tricks where you end up with the number you first thought of. Ben showed me that ∨ is idempotent by doing the following:

((P ∨ P) ↔ P)

is valid, as shown by truth table:

P (P ∨ P) ((P ∨ P) ↔ P)

T

T

T

F

F

T

and → is not idempotent because:

((P → P) ↔ P)

is not valid, as shown by the truth table:

P (P → P) ((P → P) ↔ P)

T

T

T

F

T

F

Here’s a table showing whether each function is idempotent or not.

Connective Idempotent? Identity Name

¬

Yes

Idempotence of negation

Yes

Idempotence of conjunction

Yes

Idempotence of disjunction

No

No

The unary connective ¬ is idempotent because:

¬¬P ↔ P

is valid.

Questions

1. For the following connectives, use a truth table to show whether or not the connective is idempotent.

2. Use the idempotence of negation identity to simplify the following formulas:

1. (P ∨ ¬¬Q)

2. ¬¬(P ∨ Q)

3. (¬¬A ∧ ¬¬B)

1. For the following connectives, use a truth table to show whether or not the connective is idempotent.

1. ↔ is not idempotent because:
((P ↔ P) ↔ P)
is not valid, as shown by truth table:

P (P ↔ P) ((P ↔ P) ↔ P)

T

T

T

F

T

F

2. ∧ is idempotent because:
((P ∧ P) ↔ P)
is valid, as shown by truth table:

P (P ∧ P) ((P ∧ P) ↔ P)

T

T

T

F

F

T

2. Use the idempotence of negation identity to simplify the following formulas:

1. (P ∨ ¬¬Q)
(P ∨ Q)

2. ¬¬(P ∨ Q)
(P ∨ Q)

3. (¬¬A ∧ ¬¬B)
(A ∧ B)

2.20. De Morgan’s Laws

I found in the Tower that Mathematicians are often good at music too. De Morgan was a flautist. I’ve got no musical ability. De Morgan’s Laws are a couple of identities:

(A ∧ B) ≡ ¬(¬A ∨ ¬B)

and:

(A ∨ B) ≡ ¬(¬A ∧ ¬B)

Some say they’re obvious. Do you find them obvious? I don’t.

Questions

1. For De Morgan’s laws, use a truth table to show that they are identities.

1. For De Morgan’s laws, use a truth table to show that they are identities.

1. If:
(A ∧ B) ≡ ¬(¬A ∨ ¬B)
then:
((A ∧ B) ↔ ¬(¬A ∨ ¬B))
is valid. The truth table is:

A B (A ∧ B) ¬A ¬B (¬A ∨ ¬B) ¬(¬A ∨ ¬B) ((A ∧ B) ↔ ¬(¬A ∨ ¬B))

T

T

T

F

F

F

T

T

F

T

F

T

F

T

F

T

T

F

F

F

T

T

F

T

F

F

F

T

T

T

F

T

which shows it is valid, and so the two formulas are equivalent.

2. If:
(A ∨ B) ≡ ¬(¬A ∧ ¬B)
then:
((A ∨ B) ↔ ¬(¬A ∧ ¬B))
is valid. The truth table for this formula is:

A B (A ∨ B) ¬A ¬B (¬A ∧ ¬B) ¬(¬A ∧ ¬B) ((A ∨ B) ↔ ¬(¬A ∧ ¬B))

T

T

T

F

F

F

T

T

F

T

T

T

F

F

T

T

T

F

T

F

T

F

T

T

F

F

F

T

T

T

F

T

which shows it is valid, and so the pair of formulas we started with is an identity.

2.21. Entailment

‘What does that entail, lol!’, yeah thanks for that. In English you might have some premises leading to a conclusion such as:

Abelard ordered coffee or Abelard ordered cake. Abelard didn’t order cake. Therefore Abelard ordered coffee.

To convert the premises and conclusion from English into logical formulas, we first of all define the atomic formulas:

A: Abelard ordered coffee.
B: Abelard ordered cake.

So the premises and conclusion becomes:

Premises: (A ∨ B), ¬B
Conclusion: A

Now, do the premises entail the conclusion? In other words, for every interpretation where the premises are true, is the conclusion true? If the premises entail the conclusion, the following formula must be valid:

(((A ∨ B) ∧ ¬B) → A)

In effect we’ve joined the premises together with ∧ and then added on the conclusion with an → to get the formula. Bring on the table of truth!

A B (A ∨ B) ¬B ((A ∨ B) ∧ ¬B) (((A ∨ B) ∧ ¬B) → A)

T

T

T

F

F

T

F

T

T

F

F

T

T

F

T

T

T

T

F

F

F

T

F

T

The last column is always true, so the formula is valid, so the premises do entail the conclusion. Logicians denote an entailment with the ⊨ symbol. So the entailment we’ve just found can be written:

(A ∨ B), ¬B ⊨ A

Here’s another example of some premises and a conclusion in English:

If we run out of petrol we won’t get to the wedding on time. If we lose our way we won’t get to the wedding on time. We’ve run out of petrol. We won’t get to the wedding on time.

In logic symbols the argument is:

A: Run out of petrol.
B: Get to the wedding on time.
C: Lose our way.
Premises: (A → ¬B), (C → ¬B), A
Conclusion: ¬B

It’s an entailment if:

((A → ¬B) ∧ (C → ¬B ∧ A) → ¬B)

is valid. Doing a giant truth table:

A B C ¬B (A → ¬B) (C → ¬B) A → ¬B) ∧ (C → ¬B (A → ¬B) ∧ (C → ¬B ∧ A) ((A → ¬B) ∧ (C → ¬B ∧ A) → ¬B)

T

T

T

F

F

F

F

F

T

F

T

T

F

T

F

F

F

T

T

F

T

T

T

F

F

F

T

F

F

T

T

T

T

T

F

T

T

T

F

F

F

T

F

F

T

F

T

F

F

T

T

T

F

T

T

F

F

T

T

T

T

T

T

F

F

F

T

T

T

T

F

T

Shows that the formula is valid and so we can write that:

(A → ¬B), (C → ¬B), A ⊨ ¬B

Questions

1. Construct logical formulas for the following premises and conclusions:

1. If it’s a silent film then there’s no sound. It’s a silent film. Therefore there’s no sound.

2. Scheherazade bought black paint or Scheherazade bought grey paint. Scheherazade did not buy grey paint. Therefore Scheherazade bought black paint.

3. It is not the case that Ben won a tennis match and Toby won a tennis match. Toby won a tennis match. Therefore Ben did not win a tennis match.

4. Bill orders 6x or Bill orders Tribute. If Bill orders 6x or Tribute then the pub is open. Bill does not order Tribute. Therefore the pub is open and Bill orders 6x.

5. The light switch is on or the light switch is off. The light switch is not on and off. This light switch is not on. Therefore the light switch is off.

2. For the arguments given in question 1, show whether they are valid or not.

1. Construct logical formulas for the following premises and conclusions:

1. If it’s a silent film then there’s no sound. It’s a silent film. Therefore there’s no sound.
P: It’s a silent film.
Q: There’s no sound.
Premises: (P → Q), P
Conclusion: Q

2. A: Scheherazade bought black paint.
B: Scheherazade bought grey paint.
Premises: (A ∨ B), ¬B
Conclusion: A

3. It is not the case that Ben won a tennis match and Toby won a tennis match. Toby won a tennis match. Therefore Ben did not win a tennis match.
P: Ben won a tennis match.
Q: Toby won a tennis match.
Premises: ¬(P ∧ Q), Q
Conclusion: ¬P

4. P: Bill orders 6x.
Q: Bill orders Tribute.
R: The pub is open.
Premises: (P ∨ Q), ((P ∨ Q) → R), ¬Q
Conclusion: (R ∧ P)

5. P: The light switch is on.
Q: The light switch is off.
Premises: (P ∨ Q), ¬(P ∧ Q), ¬P Conclusion: Q

2. For the premises and conclusions given in question 1, show whether they are entailments not.

1. Premises: (P → Q), P
Conclusion: Q
The truth table below shows that the formula (((P → Q) ∧ P) → Q) is valid, and so
(P → Q), P ⊨ Q

P Q (P → Q) ((P → Q) ∧ P) (((P → Q) ∧ P) → Q)

T

T

T

T

T

F

T

T

F

T

T

F

F

F

T

F

F

T

F

T

2. Premises: (A ∨ B), ¬B
Conclusion: A
The truth table below shows that the formula (((A ∨ B) ∧ ¬B) → A) is valid, and so:
(A ∨ B), ¬B ⊨ A

A B (A ∨ B) ¬B ((A ∨ B) ∧ ¬B) (((A ∨ B) ∧ ¬B) → A)

T

T

T

F

F

T

F

T

T

F

F

T

T

F

T

T

T

T

F

F

F

T

F

T

3. Premises: ¬(P ∧ Q), Q
Conclusion: ¬P
The truth table below shows that the formula:
((¬(P ∧ Q) ∧ Q) → ¬P)
is valid and so the premises entail the conclusion.

P Q (P ∧ Q) ¬(P ∧ Q) (¬(P ∧ Q) ∧ Q) ¬P ((¬(P ∧ Q) ∧ Q) → ¬P)

T

T

T

F

F

F

T

F

T

F

T

T

T

T

T

F

F

T

F

F

T

F

F

F

T

F

T

T

4. Premises: (P ∨ Q), ((P ∨ Q) → R), ¬Q
Conclusion: (R ∧ P)
The truth table below shows that the formula:
((((P ∨ Q) ∧ ((P ∨ Q) → R)) ∧ ¬Q) → (R ∧ P))
is valid and so:
(P ∨ Q), ((P ∨ Q) → R), ¬Q ⊨ (R ∧ P)

P Q R (P ∨ Q) ((P ∨ Q) → R) ¬Q P ∨ Q) ∧ ((P ∨ Q) → R (P ∨ Q) ∧ ((P ∨ Q) → R ∧ ¬Q) (R ∧ P) (P ∨ Q) ∧ ((P ∨ Q) → R ∧ ¬Q) → (R ∧ P)

T

T

T

T

T

T

F

T

F

T

F

T

T

F

T

F

F

F

F

T

T

F

T

F

F

T

T

F

F

T

F

F

T

F

T

F

T

F

F

T

T

T

F

T

F

F

F

F

F

T

F

T

F

F

T

F

F

F

F

T

T

F

F

F

T

F

T

F

F

T

F

F

F

F

T

F

T

F

F

T

5. Premises: (P ∨ Q), ¬(P ∧ Q), ¬P
Conclusion: Q
The truth table below shows that the formula:
((P ∨ Q) ∧ ¬(P ∧ Q ∧ ¬P) → Q)
is valid and so:
(P ∨ Q), ¬(P ∧ Q), ¬P ⊨ Q

P Q (P ∨ Q) (P ∧ Q) ¬(P ∧ Q) P ∨ Q) ∧ ¬((P ∧ Q) ¬P (P ∨ Q) ∧ ¬(P ∧ Q ∧ ¬P) ((P ∨ Q) ∧ ¬(P ∧ Q ∧ ¬P) → Q)

T

T

T

T

F

F

F

F

T

F

T

T

F

T

T

T

T

T

T

F

T

F

T

T

F

F

T

F

F

F

F

T

F

T

F

T

2.22. Implicit parentheses

Writing down formulas involves writing a lot of parentheses. There are a couple of conventions for reducing the number of parentheses you have to write, while still keeping a formula unambiguous. I’ve already discovered that logicians write:

¬P

to mean:

(¬P)

They also assume that if brackets aren’t explicitly written, then they they implicity exist from left to right. For example the following formula has no explicit parentheses:

A ∨ B ∧ C

But the implied formula is:

(\(A ∨ B) ∧ C)

Questions

1. For the following formulas, rewrite the formulas with explicit parentheses:

1. ¬P ∧ Q

2. ¬(P ∧ Q)

3. ¬P ∧ Q ∨ R

2. For the following formulas, rewrite the formulas with implicit parentheses:

1. (\(P ∨ Q) ∨ R)

2. (¬R)

3. (¬(P ∧ (Q ∨ R)))

1. For the following formulas, rewrite the formulas with explicit parentheses:

1. ¬P ∧ Q
(\(¬P) {and) Q)

2. ¬(P ∧ Q)
(¬(P ∧ Q))

3. ¬P ∧ Q ∨ R
(\(\(¬P) ∧ Q) ∨ R)

2. For the following formulas, rewrite the formulas with implicit parentheses:

1. (\(P ∨ Q) ∨ R)
P ∨ Q ∨ R

2. (¬R)
¬R

3. (¬(P ∧ (Q ∨ R)))
¬(P ∧ (Q ∨ R))

3. Sets Figure 3. Gottlob Frege Licensed under Public Domain via Wikimedia Commons.

‘Tony’, ‘Yes Professor Frege?’, ‘You should really learn about sets’, ‘Okay, whatevs Prof’.

3.1. What’s A Set?

A set is a collection of distinct elements, where there’s no order, and duplicates aren’t allowed. Some example are:

• Primary colours.

• Even integers

• Letters of the alphabet.

• Natural numbers.

Written out in set notation, these look like:

• {red, green, blue}

• {…​, -4, -2, 0, 2, 4, …​}

• {a, b, c, …​, x, y, z}

• {0, 1, 2, 3, …​}

When the set includes an elipsis (…​) at one end or both, it denotes an infinite series. An ellipsis in the middle of a set of elements is used to save writing out all the items of an obvious set.

The terms finite set and infinite set mean what you think they mean, a set with a finite number of elements and a set with an infinite number of elements.

Questions

1. Write out the following sets in set notation:

1. Vowels

2. Minutes on a clock

3. Days of the week

2. For the sets in question 1, say whether they are finite or infinite.

1. Write out the following sets in set notation:

1. Vowels
{A, E, I, O, U}

2. Minutes on a clock
{0, 1, 2, …​, 57, 58, 59}

3. Days of the week
{Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday}

2. For the sets in question 1, say whether they are finite or infinite.
They are all finite.

3.2. Common Sets Of Numbers

Some sets of numbers are common enough to have their own names and symbols:

Name Symbol Definition

Real Numbers

R

{All the numbers on a continuous line from negative infinity to positive infinity}

Integers

Z

{…​, -2, -1, 0, 1, 2, …​}

Natural Numbers

N

{0, 1, 2, …​}

Positive Integers

Z+

{1, 2, 3, …​}

Boolean Values

B

{1, 0}
By convention, 1 is interpreted as true, and 0 as false.

Rational Numbers

Q

Numbers of the form p / q, where p and q are integers and p ≠ 0

Empty Set

{}

3.3. Equality

If two sets have exactly the same elements in them, then they are equal. In set notation, if sets A and B are equal, set theorists write:

A = B

if A and B aren’t equal they write:

A ≠ B

Let’s say we’ve got two sets S and T:

S is {1, 2}
T is {2, 1}

S and T are equal because all that matters for identity is that the two sets have the same elements in them. So we can write:

S = T

Let’s make up two sets A and B:

A is {1, 2, 2}
B is {1, 2}

Sets don’t have any duplicates so the two sets A and B are equal and we can write:

A = B

‘Hey, you said that sets can’t have duplicates, but then you wrote {1, 2, 2}. What gives?’. When you write {1, 2, 2}, you’re describing a set with two elements, 1 and 2. So {1, 2, 2} = {1, 2}. So these are two ways of describing the same set. ‘Well, okay I suppose. I have to say I’m not entirely convinced, but carry on for now’.

And another thing, it’s the convention for sets to be represented by capital letters, and elements to represented by lower case letters.

Questions

1. For the following sets, say if they’re equal or not:

1. {1, 5, 8} and {1, 6, 8}

2. {1, 5, 8, 1} and {1, 5, 8}

3. {8, 5, 1} and {1, 5, 8}

1. For the following sets, say if they’re equal or not:

1. {1, 5, 8} and {1, 6, 8}
Not equal.

2. {1, 5, 8, 1} and {1, 5, 8} Duplicates don’t matter, so equal.

3. {8, 5, 1} and {1, 5, 8} Order doesn’t matter, so equal.

3.4. Set Membership

I learnt from Common Sets Of Numbers that Z stands for the set of integers. So the number 1 is an element of Z. Or equivalently the number 1 is a member of Z, or simply 1 is in Z. Set theorists write this as:

1 ∈ Z

The number 1.5 is not in Z. They write this as:

1.5 ∉ Z

Questions

1. Translate the following into set notation:

1. 1.6 is a member of R.

2. Monday is not in {Tuesday, Friday}

3. 2009 is in N

2. Say whether the following mathematical statements are true or false:

1. 0.5 ∈ Z

2. 5 ∉ {6, 7, 8, …​, 99, 100, 101}

3. 0 ∈ R

1. Translate the following into set notation:

1. 1.6 is a member of R.
1.6 ∈ R

2. Monday is not in {Tuesday, Friday}
Monday ∉ {Tuesday, Friday}

3. 2009 is in N
2009 ∈ N

2. Say whether the following mathematical statements are true or false:

1. 0.5 ∈ Z
False.

2. 5 ∉ {6, 7, 8, …​, 99, 100, 101}
True

3. 0 ∈ R
True

3.5. Set Builder Notation

Up to this point I’d seen sets specified in three ways:

• Written in natural language eg. R = {All the numbers on a continuous line from negative infinity to positive infinity}

• Each element in the set given explicitly eg. W = {Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday}.

• Using ellipses to imply elements, eg. M = {0, 1, 2, …​, 57, 58, 59}

Then I came across a method of defining a set by specifying a rule in a mathematical notation called set builder notation. For example:

{x | x ∈ Z ∧ x > 7}

which specifies the set:

{8, 9, 10, …​}

This rule is read as, ‘the set consists of all values of x such that x is an integer and x is greater than 7.’ The condition on the right hand side of the bar re-uses the connectives from Propositional Logic. Another example of set builder notation is:

{x | x ∈ R ∧ x = x2}

which specifies the set:

{0, 1}

This rule is read as, ‘the set consists of all values of x such that x is a real number and x equals x squared.’

Questions

1. Define the following sets in set builder notation:

1. {34, 35, 36, …​}

2. {34, 35, 36, …​, 102, 103, 104}

3. {Real numbers greater than 8.1}

2. Write down the sets specified by the following set builder notation:

1. {x | x = 0}

2. {x | x ∈ Z ∧ x < 30}

3. {x | x = 1 ∧ x = 0}

1. Specify the following sets in set builder notation:

1. {34, 35, 36, …​}
{x | x ∈ Z ∧ x > 33}

2. {34, 35, 36, …​, 102, 103, 104}
{x | x ∈ Z ∧ x > 33 ∧ x < 105}

3. {Real numbers greater than 8.1}
{x | x ∈ R ∧ x > 8.1}

2. Write down the sets specified by the following set builder notation:

1. {x | x = 0}
{0}

2. {x | x ∈ Z ∧ x < 30}
{…​, 27, 28, 29}

3. {x | x = 1 ∧ x = 0}
{}

3.6. Universal Set Figure 4. Venn stained glass gonville caius by User:Schutz. The stained glass was designed by Maria McClafferty and installed in 1989. Licensed under CC BY-SA 2.5 via Wikimedia Commons.

Let’s say we’re talking about a set of books:

U = {Emma by Jane Austen, Anna Karenina by Leo Tolstoy, Crime and Punishment by Fyodor Dostoevsky, Use of Weapons by Ian Banks, Wuthering Heights by Charlotte Bronte, The New Men by C. P. Snow}

Since we’re only considering this set for the time being, it’s called the universal set. In different situations we can specify a different universal set. For example if we’re only talking about natural numbers, then that would be our universal set. A Venn diagram of our universal set: 3.7. Subset

For two sets A and B, A is a subset of B if and only if every element of A is a member of B. The set theorist will write:

A ⊆ B

Going back to our universal set of books, let’s define two sets:

T = {written before the 20th century}
F = {written by female authors}

then:

F ⊆ T

written as a Venn diagram: In other words we’re saying that for the books in our univeral set, those written by female authors are a subset of those written before the 20th century.

A theorem is a mathematical statement that has been proven to be true. It’s a theorem that for any set S you can say that:

S ⊆ S

A proof is an argument made up of small, incontrovertible steps that lead to the theorem. A proof that S ⊆ S is:

1. A ⊆ B is defined as being true if and only if every element of A is in B.

2. Every element of S must be in S.

3. Therefore S ⊆ S.

Another theorem that I came across says that for any set S:

∅ ⊆ S

A proof of ∅ ⊆ S is:

1. A ⊆ B is defined as being true if and only if every element of A is in B.

2. If it were false that ∅ ⊆ S, then there would be an element of ∅ that wasn’t in S. There are no elements of ∅, so that isn’t possible.

3. Therefore it must be true that ∅ ⊆ S.

Questions

1. Assume U is {0, 1, 2, …​, 7, 8, 9} and S is the set ‘less than 5’ and E is the set ‘less than 3’.

1. Say whether the following statements are true or false:

1. U ⊆ E

2. U ⊆ S

3. UU

4. E ⊆ S

5. S ⊆ E

6. E ⊆ E

7. S ⊆ S

2. Draw a Venn diagram of U, S and E.

1. Assume U is {0, 1, 2, …​, 7, 8, 9} and S is the set ‘less than 5’ and E is the set ‘less than 3’.

1. Say whether the following statements are true or false:

1. U ⊆ E
False

2. U ⊆ S
False

3. UU
True

4. E ⊆ S
True

5. S ⊆ E
False

6. E ⊆ S
True

7. S ⊆ S
True

2. Draw a Venn diagram of U, S and E. 3.8. Proper Subset

For two sets A and B, A is a proper subset of B if and only if A ⊆ B and A ≠ B. Set theorists write:

A ⊂ B

With the universal set of books and the two sets:

T = {written before the 20th century}
F = {written by female authors}

then:

F ⊂ T

drawn as a Venn diagram: Questions

1. Assume U is {0, 1, 2, …​, 7, 8, 9} and S is the set ‘less than 5’ and E is the set ‘less than 3’.

1. Say whether the following statements are true or false:

1. U ⊂ E

2. U ⊂ S

3. UU

4. E ⊂ S

5. S ⊂ E

6. E ⊂ E

7. S ⊂ S

2. Draw a Venn diagram of U, S and E.

1. Assume U is {0, 1, 2, …​, 7, 8, 9} and S is the set ‘less than 5’ and E is the set ‘less than 3’.

1. Say whether the following statements are true or false:

1. U ⊂ E
False

2. U ⊂ S
False

3. UU
False

4. E ⊂ S
True

5. S ⊂ E
False

6. E ⊂ E
True

7. S ⊂ S
True

2. Draw a Venn diagram of U, S and E. 3.9. Union

The set that you get from adding two sets together is the union of the the two sets. As I’ve come to expect, there’s a special symbol for this operation, ∪. Going back to our example with the universal set of books we could define two sets

T = {written before the 20th century} = {Emma by Jane Austen, Anna Karenina by Leo Tolstoy, Crime and Punishment by Fyodor Dostoevsky, Wuthering Heights by Charlotte Bronte}
F = {written by female authors} = {Emma by Jane Austen, Wuthering Heights by Charlotte Bronte}

then:

F ∪ T = {Emma by Jane Austen, Anna Karenina by Leo Tolstoy, Crime and Punishment by Fyodor Dostoevsky, Wuthering Heights by Charlotte Bronte}

Questions

1. Write the union of the following sets:

1. P = {0, 2, 4, 6}
Q = {1, 3, 5, 7}

2. P = {0, 1, 2, 3}
Q = {3, 4, 5, 6}

3. D = {Monday, Tuesday, Wednesday}
W = {Monday, Tuesday, Wednesday}

4. P = ∅
Q = {0, -6}

2. Write A ∪ B in set builder notation.

1. Write the union of the following sets:

1. P = {0, 2, 4, 6}
Q = {1, 3, 5, 7}
P ∪ Q = {0, 1, 2, 3, 4, 5, 6, 7}

2. P = {0, 1, 2, 3}
Q = {3, 4, 5, 6}
P ∪ Q = {0, 1, 2, 3, 4, 5, 6}

3. D = {Monday, Tuesday, Wednesday}
W = {Monday, Tuesday, Wednesday}
D ∪ W = {Monday, Tuesday, Wednesday}

4. P = ∅
Q = {0, -6}
P ∪ Q = {0, -6}

2. Write A ∪ B in set builder notation.
A ∪ B = {x | x ∈ A ∨ x ∈ B}

3.10. Intersection

For two sets A and B, the intersection of A and B is the set of elements that and in both A and B. The symbol for this operation is ∩. Going back to the example with the universal set of books we could define two sets:

T = {written before the 20th century} = {Emma by Jane Austen, Anna Karenina by Leo Tolstoy, Crime and Punishment by Fyodor Dostoevsky, Wuthering Heights by Charlotte Bronte}
F = {written by female authors} = {Emma by Jane Austen, Wuthering Heights by Charlotte Bronte}

then:

F ∩ T = {Emma by Jane Austen, Wuthering Heights by Charlotte Bronte}

Questions

1. Write the intersection of the following sets:

1. P = {0, 2, 4, 6}
Q = {1, 3, 5, 7}

2. P = {0, 1, 2, 3}
Q = {3, 4, 5, 6}

3. D = {Monday, Tuesday, Wednesday}
W = {Monday, Tuesday, Wednesday}

4. P = ∅
Q = {0, -6}

2. Write A ∩ B in set builder notation.

1. Write the intersection of the following sets:

1. P = {0, 2, 4, 6}
Q = {1, 3, 5, 7}
P ∩ Q = ∅

2. P = {0, 1, 2, 3}
Q = {3, 4, 5, 6}
P ∩ Q = {3}

3. D = {Monday, Tuesday, Wednesday}
W = {Monday, Tuesday, Wednesday}
D ∩ W = {Monday, Tuesday, Wednesday}

4. P = ∅
Q = {0, -6}
P ∩ Q = ∅

2. Write A ∩ B in set builder notation.
A ∩ B = {x | x ∈ A ∧ x ∈ B}

3.11. Cardinality

Cardinality is the size of a set. For a finite set this is the number of elements of the set. So for:

D = {days of the week}

the cardinality of D is 7. Set theorists write this as:

|D| = 7

Questions

1. Give the cardinality of the following sets:

1. V = {A, E, I, O, U}

2. M = {0, 1, 2, …​, 57, 58, 59}

3. T = {2, 4, 6, 8, 10, 12}

1. Give the cardinality of the following sets:

1. V = {A, E, I, O, U}
|V| = 5

2. M = {0, 1, 2, …​, 57, 58, 59}
|M| = 60

3. T = {2, 4, 6, 8, 10, 12}
|T| = 6

4. |∅| = 0

3.12. Power Set

The power set of a set S is the set of all the subsets of S. The power set of S is written:

𝓟(S)

Take for example the set of primary colours:

C = {red, green, blue}

The subsets of C are:

• {red}

• {green}

• {blue}

• {red, green}

• {red, blue}

• {green, blue}

• {red, green, blue}

so the power set is:

𝓟(C) = {∅, {red}, {green}, {blue}, {red, green}, {red, blue}, {green, blue}, {red, green, blue}}

Questions

1. Write down the power set of each of the following sets:

1. {1}

2. {1, 2}

3. {1, 2, 3}

4. {True, False}

1. Write down the power set of each of the following sets:

1. {∅}

2. {1}
{∅, {1}}

3. {1, 2}
{∅, {1}, {2}, {1, 2}}

4. {1, 2, 3}
{∅, {1}, {2}, {1, 2}, {3}, {1, 3}, {2, 3}, {1, 2, 3}}

5. {True, False}
{∅, {True}, {False}, {True, False}}

3.13. Cardinality Of The Power Set

Set theorists have shown that if a set S has cardinality |S| = n, then:

|𝓟(S)| = 2n

Looking at the cardinalities of the power sets of sets with cardinality 0, 1, 2, 3 we get:

• |𝓟(∅)| = |{∅}| = 1

• |𝓟({1})| = |{∅, {1}}| = 2

• |𝓟({1, 2})| = |{∅, {1}, {2}, {1, 2}}| = 4

• |𝓟({1, 2, 3})| = |{∅, {1}, {2}, {1, 2}, {3}, {1, 3}, {2, 3}, {1, 2, 3}}| = 8

I find that writing this out in a table makes it easier to spot what’s going on:

S 𝓟(S)

{∅}

{1}

{∅, {1}}

{1, 2}

{∅, {1}, {2}, {1, 2}}

{1, 2, 3}

{∅, {1}, {2}, {1, 2}, {3}, {1, 3}, {2, 3}, {1, 2, 3}}

So I saw that the next S is the previous S with the new element added. Also, the next 𝓟(S) is all the sets in the previous 𝓟(S) and also all the sets in the previous 𝓟(S) with the new element added to each one.

So the theorem |𝓟(S)| = 2n is working for all the cardinalities of S we’ve tried. From wandering round in the Ivory Tower, I found that in maths you have to have things nailed down inescapably, it’s no good to just say that it looks like it works after a few tries. That’s the purpose of a proof, to give a water-tight argument for why a mathematical statement is true.

Here’s a proof of |𝓟(S)| = 2n:

1. Looking at the case for n = 0

1. If n = 0 then S = ∅, so

2. |𝓟(∅)| = |{∅}|

3. |{∅}| = 1

4. 1 = 20

5. So the theorem is correct for the case n = 0

2. Take a set S with cardinality n.

3. If a new set T were formed that had all the elements of S but also a new element x, then T would have cardinality n + 1.

4. Then 𝓟(T) would be 𝓟(S) combined with each set in 𝓟(S) having the element x added to it.

5. So |𝓟(T)| = 2 * |𝓟(S)|

6. In other words if the cardinality if a set increases by 1, then the cardinality of the power set is multiplies by 2.

7. Starting at n = 0 we get the series 1, 1 * 2, 1 * 2 * 2, 1 * 2 * 2 * 2, …​

8. which is the same as the series generated by 2n

9. So for a set S of cardinality n, |𝓟(S)| = 2n

3.14. Proof By Induction

I’m told that the proof we just did of |𝓟(S)| = 2n was an example of proof by induction. I tried to find out the underlying form of proof by induction and it turns out to have three parts:

Say we’ve got a mathematical statment P that depends on n ∈ N. It’s the purpose of the proof to show that P is true for all values of n.

1. Basis for the induction
In this step we show that P is true when n = 0.

2. Induction hypothesis
We assume that P is true for n.

3. Induction step
We show that if P is true for n, then P is true for n + 1.

Here’s another example of proof by induction. Say we’ve got a set:

S = {0, 1, 2, …​, n}

Our proposition P is:

The sum of all the elements of S is n(n + 1) / 2
1. Basis for the induction
If n = 0, S = {0} and so the sum is 0. Working this out for n = 0 using the proposition gives 0(0 + 1) / 2 = 0. So we’ve shown that the proposition is true for n = 0.

2. Induction hypothesis
Assume that P is true for n.

3. Induction step
We need to show that if P is true for n, then it’s true for n + 1. So we need to show that
(0 + 1 + 2 + …​ + n) + (n + 1) = (n + 1)(n + 2) / 2
From the induction hypothesis we’re assuming P is true for n then the above can be rewritten:
n(n + 1) / 2 + (n + 1) = (n + 1)(n + 2) / 2
1/2n2 + 1/2n + n + 1 = 1/2n2 + 3/2n + 1
1/2n2 + 3/2n + 1 = 1/2n2 + 3/2n + 1
and so the proposition is true for all n.

Query: Is this similar to recursion in say Haskell?

3.15. Counterexample

Sometimes a mathematician will come up with statement that she thinks is true, a conjecture in other words, then another mathematician could disprove the conjecture with a counterexample. A conjecture might be:

All sets have cardinality greater than 3.

Another mathematician can say, ‘that can’t be true, what about the set {1}, that has cardinality one?’. Thus the conjecture has been disproved by counterexample.

Questions

1. Disprove the following conjectures by coming up with a counterexample:

1. There is no higher number than 100.

2. For all prime numbers p, 2p + 1 is prime.

3. For two sets A and B, |A ∪ B| = |A| + |B|

4. For two sets A and B, |A ∩ B| = |A| - |B|

1. Disprove the following conjectures by coming up with a counterexample:

1. There is no higher number than 100.
Counterexample: 100

2. For all prime numbers p, 2p + 1 is prime.
Counterexample: 7

3. For any two sets A and B, |A ∪ B| = |A| + |B|
Counterexample: A = {1} and B = {1}

4. For any two sets A and B, |A ∩ B| = |A| - |B|
Counterexample: A = {1} and B = {1}

Set difference

3.17. Set Intersection

Set Intersection ∩.

On your first day as an assistant librarian, you’re asked to compile a book that is a catalogue of all of the books in the library that don’t mention themselves. Eventually you present the chief librarian with your completed catalogue. The chief librarian asks, ‘Does the catalogue mention the catalogue?’. Well no, you answer…​but then if the catalogue doesn’t mention itself, then it should be in the catalogue, in which case it shouldn’t…​

You’ve become a victim of Russell’s Paradox, and you’re fired. Lol!

In terms of sets, Russell’s Paradox is asking, what’s the set of all sets that don’t have themselves as an element? That set doesn’t exist.

So, that’s solved it in maths language, but how should you have answered the chief librarian? Well, you could say that the book (set) he’s asked for can’t exist. But you can write a book (set), which has the same contents as has been requested, except that it doesn’t contain itself.

If this sentence is true, then you owe me a million pounds.

Do you owe me a million pounds then? Anyway, they told me that there’s an equivalent paradox for sets.

They also told me that there’s a paradox with the set of all sets, so that doesn’t exist either. As it seems to me, a paradox is something that is clearly incorrect, but you can’t see the flaw in the argument. Of course, all paradoxes can be resolved, and the resolution deepens one’s understanding. ‘Ooh, hark at him pontificating on the philosophy of it all!!’ Okay, okay.

4. Propositional Logic II

This is propositional logic that requires a knowledge of sets. In which we get to use Greek capital letters!

4.1. Theory

I’m not quite sure why yet, but in maths land they talk about sets of formulas, calling them theories and often giving them Greek capital letters! So they say:

Γ = {φ1, …​,φn}

Also, if ψ is a formula then:

Γ ⊨ ψ

stands for:

φ1 ∧ φ2 ∧ …​ ∧ φn ⊨ ψ

Questions

1. If Δ = {φ1, φ2} and Γ = {φ2, φ3} then write the following in terms of individual formalas:

1. Δ ⊨ ψ

2. Δ ∩ Γ ⊨ ψ

3. Γ ∪ Δ ⊨ ψ

2. If Δ and Γ are theories, say whether the following are true or false:

1. If Δ ⊨ ψ and Γ ⊨ ψ then Δ ∪ Γ ⊨ ψ.

2. If Δ ⊨ ψ and Γ ⊨ ψ then Δ ∩ Γ ⊨ ψ.

3. If Δ ⊨ ψ and Γ ⊭ ψ then Δ ∪ Γ ⊨ ψ.

4. If Δ ⊭ ψ then Δ ⊨ ¬ψ.

1. If Δ = {φ1, φ2} and Γ = {φ2, φ3} then write the following in terms of individual formulas:

1. Δ ⊨ ψ
φ1 ∧ φ2 ⊨ ψ

2. Δ ∩ Γ ⊨ ψ
φ2 ⊨ ψ

3. Γ ∪ Δ ⊨ ψ
φ1 ∧ φ2 ∧ φ3 ⊨ ψ

2. If Δ and Γ are theories, say whether the following are true or false:

1. If Δ ⊨ ψ and Γ ⊨ ψ then Δ ∪ Γ ⊨ ψ.
If:

Δ = {φ1, φ2, …​, φn}
Γ = {σ1, σ2, …​, σn}

and if:

Δ ⊨ ψ

then:

φ1 ∧ φ2 ∧ …​ ∧ φn → ψ

is valid. Adding extra ∧ terms on to the left hand side of the → can never make it true if it was already false, and so the expression:

φ1 ∧ φ2 ∧ …​ ∧ φn ∧ σ1 ∧ σ2 ∧ …​ σn → ψ

is valid, and so:

Δ ∪ Γ ⊨ ψ

is true.

2. If Δ ⊨ ψ and Γ ⊨ ψ then Δ ∩ Γ ⊨ ψ.

Proof by counter-example! Say:

Δ = {P ∨ ¬P, P ∧ ¬P}
Γ = {P ∨ ¬P, Q ∧ ¬Q}

then:

Δ ∩ Γ = {P ∨ ¬P}

and:

{P ∨ ¬P} → ψ

Is not valid, and so:

Δ ∩ Γ ⊨ ψ

is not true.

3. If Δ ⊨ ψ and Γ ⊭ ψ then Δ ∪ Γ ⊨ ψ.
If:

Δ = {φ1, φ2, …​, φn}

and:

Δ ⊨ ψ

then:

φ1 ∧ φ2 ∧ …​ ∧ φn → ψ

is valid. Adding extra ‘and’ terms to the left hand side can never make the formula invalid so the expression:

φ1 ∧ φ2 ∧ …​ ∧ φn ∧ σ1 ∧ σ2 ∧ …​ σn → ψ

is also valid. So if:

Γ = {σ1, σ2, …​, σn}

then:

Δ ∪ Γ ⊨ ψ

is true.

4. If Δ ⊭ ψ then Δ ⊨ ¬ψ.

Proof by counter-example. If:

Δ = {φ ∨ ¬φ}

then:

φ ∨ ¬φ → φ

is not valid, so:

Δ ⊭ φ

but if:

Δ ⊨ ¬φ

then:

φ ∨ ¬φ → ¬φ

which isn’t valid, so:

Δ ⊨ ¬φ

is not true.

4.2. Semantic Consistency

A theory is semantically consistent if and only if there’s an interpretation where all the formulas of the theory are true. In other words if there’s a theory Δ:

Δ = {φ1, …​,φn}

Then Δ is semantically consistent if:

φ1 ∧ φ2 ∧ …​ ∧ φn

is satisfiable. An example you say? Okay, if:

Γ = {P, Q ∧ P, Q ∨ P, Q}

then Γ is consistent if:

P ∧ (Q ∧ P) ∧ (Q ∨ P) ∧ Q

is satisfiable. Using a truth table:

P Q Q ∧ P Q ∨ P P ∧ (Q ∧ P) ∧ (Q ∨ P) ∧ Q

T

T

T

T

T

F

T

F

T

F

T

F

F

T

F

F

F

F

F

F

the formula is satisfiable and so Δ is semantically consistent.

Questions

1. Say whether the following theories are consistent or not:

1. Δ = {Q, ¬Q}

2. Γ = {P ∧ Q, Q}

3. Γ = {P ∨ Q, ¬Q}

4. Γ = {P → Q, Q → ¬P}

5. Γ = {¬P, ¬Q, P ↔ Q}

2. Disprove the following conjectures with a counterexample:

1. If {ψ, φ} is consistent, then ψ ≡ φ.

2. If {ψ, φ} is consistent, then ψ ⊨ φ.

3. If ψ ≡ φ, then {ψ, φ} is consistent.

4. If ψ ⊨ φ, then {ψ, φ} is consistent.

1. Say whether the following theories are consistent or not:

1. Δ = {Q, ¬Q}
Δ is consistent if Q ∧ ¬Q is satisfiable:

Q ¬Q Q ∧ ¬Q

T

F

F

F

T

F

So the theory Δ is not consistent.

2. Γ = {P ∧ Q, Q}
Γ is consistent if P ∧ Q ∧ Q is satisfiable

P Q P ∧ Q P ∧ Q ∧ Q

T

T

T

T

F

T

F

F

T

F

F

F

F

F

F

F

So the theory Γ is consistent.

3. Γ = {P ∨ Q, ¬Q}
Γ is consistent if (P ∨ Q) ∧ ¬Q is satisfiable

P Q P ∨ Q ¬Q (P ∨ Q) ∧ ¬Q

T

T

T

F

F

F

T

T

F

F

T

F

T

T

T

F

F

F

T

F

So the theory Γ is consistent.

4. Γ = {P → Q, Q → ¬P}
Γ is consistent if (P → Q) ∧ (Q → ¬P) is satisfiable.

P Q P → Q ¬P Q → ¬P (P → Q) ∧ (Q → ¬P)

T

T

T

F

F

F

F

T

T

T

T

T

T

F

F

F

T

F

F

F

T

T

T

T

So the theory Γ is consistent.

5. Γ = {¬P, ¬Q, P ↔ Q}
Γ is consistent if ¬P ∧ ¬Q ∧ (P ↔ Q) is satisfiable

P Q ¬P ¬Q P ↔ Q ¬P ∧ ¬Q ∧ (P ↔ Q)

T

T

F

F

T

F

F

T

T

F

F

F

T

F

F

T

F

F

F

F

T

T

T

T

So the theory Γ is consistent.

2. Disprove the following conjectures with a counterexample:

1. If {ψ, φ} is consistent, then ψ ≡ φ.
If {ψ, φ} is consistent then (ψ ∧ φ) is satisfiable. Say ψ is (P ∨ ∨P) and φ is P, then (ψ ∧ φ) is satisfiable, but ψ is not equivalent to φ, so the conjecture is false.

2. If {ψ, φ} is consistent, then ψ ⊨ φ.
If {ψ, φ} is consistent then (ψ ∧ φ) is satisfiable. If ψ ⊨ φ then (ψ → φ) is valid. But if ψ is (P ∧ ¬P) and φ is P, then (ψ ∧ φ) is satisfiable and (ψ → φ) is not valid, so the conjecture is false.

3. If ψ ≡ φ, then {ψ, φ} is consistent.
If ψ ≡ φ then (ψ ↔ φ) is valid. If {ψ, φ} is consistent then (ψ ∧ φ) is valid. But if ψ is ( the theory {ψ, φ} is consistent, then (ψ ∧ φ) is

4. If ψ ⊨ φ, then {ψ, φ} is consistent.

4.3. Unsatisfiability Theorem

I would like, dear reader, to present to you a mathematical theorem. ‘Oooh, hark at him with his theorems! He’s just got started in maths and now he thinks he’s Bertrand Russell!’. Well, okay reader maybe I was being a bit pompous, but anyway I found that a theorem is a statement about maths that’s been proven to be true. The Unsatisfiability Theorem states that for a set of formulas Δ and a formula φ:

Δ ⊨ φ if and only if Δ ∪ {¬φ} is unsatisfiable.

So what’s the proof of the Unsatisfiability Theorem? Well, if an interpretation satisfies Δ, then it must satisfy φ, and therefore it can’t satisfy ¬φ. So for every interpretation, Δ ∪ {¬φ} is unsatisfiable. That’s looking at it from one direction, it says 'if and only if' , so we have to look at it from the other direction too. If Δ ∪ {¬φ} is unsatisfiable, then every interpretation that satisfies Δ must not satisfy ¬φ (so must satisfy φ). So Δ must entail φ.

I found that I had to think about that for quite a long time before I accepted it to be true. So what’s a proof exactly? It’s a chain of small self-evidently true steps that lead to the theorem.

While we’re on the subject of theorems, in the Entailment section I actually encountered the Deduction Theorem but I didn’t know it was called that at the time. The Deduction Theorem is a statement about formulas (a metalogical statement no less) that says that for a theory Δ:

Δ = {ψ1, …​,ψn}

if:

Δ ⊨ φ

then:

1 ∧ …​ ∧ ψn} → φ

And in the Identity section I came across the idea that for two formulas φ and ψ if:

φ ≡ ψ

then:

φ ↔ ψ

is valid. That idea is called the equivalence theorem.

Questions

. .. or(A, implies(not(B), A)) .. implies(implies(A, B), C) .. or(P, equals(Q, not(P))) .. or(and(A, B), and(A, C)) .. and(and(A, B), and(A, C))

1. or(A, implies(not(B), A))
or(A, or(not(not(B)), A)) [Material Implication]
or(A, or(B, A)) [Idempotence of ‘not’]
or(or(A, B), A) [Associativity of ‘or’]

2. implies(implies(A, B), C)
implies(or(not(A), B), C) [Material Implication]
or(not(or(not(A), B)), C) [Material Implication]
or(and(not(not(A), not(B)), C) [De Morgan’s Laws]
or(and(A, not(B)), C) [Idempotence of ‘not’]
and(or(C, A), or(C, not(B))) [Distribute ‘or’ over ‘and’]

3. or(P, equals(Q, not(P)))
or(P, and(or(not(Q), not(P)), or(Q, not(not(P))))) [Material Equality]
or(P, and(or(not(Q), not(P)), or(Q, P))) [Idempotence of ‘not’]
and(or(P, or(not(Q), not(P))), or(P, or(Q, P))) [Distribute ‘or’ over ‘and’]

4. or(and(A, B), and(A, C))
and(or(and(A, B), A), or(and(A, B), C)) [Distribute ‘or’ over ‘and’]
and(and(or(A, A), or(B, A)), and(or(A, C), or(B, C))) [Distribute ‘or’ over ‘and’]
and(and(and(or(A, A), or(B, A)), or(A, C)), or(B, C)) [‘and’ is associative]

5. and(and(A, B), and(A, C))
and(and(and(A, B), A), C) [‘and’ is associative]

4.4. Conjunctive Normal Form (CNF)

When I got to this point in the Ivory Tower, John Alan Robinson took me by the scruff of the neck and said, ‘Look, you’ve just got to learn this, don’t ask why’. ‘Okay, I replied meekly’.

A literal is an atomic formula or the ‘not’ of an atomic formula. Eg:

P
not(P)

A clause is a number of literals joined by the ‘or’ function. Eg:

or(not(P), Q)
P
or(or(P, Q), not(R))

A formula in CNF is a number of clauses joined by the ‘and’ function. Eg:

and(and(or(not(P), Q), P), or(or(P, Q), not(R)))

Anyway, John Alan Robinson went on to tell me the most remarkable thing, any formula can be written in CNF. You simply (!) use the following identities (which we’ve previously encountered), applying them in the given order:

 Step 1: Implications Material Implication implies(P, Q) ≡ or(not(P), Q) Material Equivalence equals(P, Q) ≡ and(or(not(P), Q), or(P, not(Q))) Step 2: Negations Idempotence of ‘not’ not(not(P)) ≡ P De Morgan’s Laws and(A, B) ≡ not(or(not(A), not(B))) or(A, B) ≡ not(and(not(A), not(B))) Step 3: Distributivity ‘and’ over ‘and’ and(A, and(B, C)) ≡ and(and(A, B), and(A, C)) ‘and’ over ‘or’ and(A, or(B, C)) ≡ or(and(A, B), and(A, C)) ‘or’ over ‘and’ or(A, and(B, C)) ≡ and(or(A, B), or(A, C)) ‘or’ over ‘or’ or(A, or(B, C)) ≡ or(or(A, B), or(A, C)) Step 4: Associativity ‘and’ and(A, and(B, C)) ≡ and(and(A, B), C) ‘or’ or(A, or(B, C)) ≡ or(or(A, B), C)

Here’s are a couple of examples that I was shown. We start out with an example formula in the normal logical notation:

implies(and(A, not(B)), implies(C, B))

Applying step 1, Material Implication, we get:

implies(and(A, not(B)), or(not(C), B))

applying Material Implication again gives us:

or(not(and(A, not(B))), or(not(C), B))

so now we’ve got rid of the ‘implies’ functions. Now let’s plough on with step 2, Negations, where the application of De Morgan’s Laws, gives:

or(or(not(A), not(not(B))), or(not(C), B))

Idempotence of ‘not’ alert!

or(or(not(A), B), or(not(C), B))

We’re so nearly in CNF, but not quite. Since ‘or’ is associative:

or(or(or(not(A), B), not(C)), B)

Hah! We’re now in CNF. Okay, in the second example we’ve got to convert:

or(equals(A, B), not(C))

into CNF. Starting with step 1, Implications:

or(and(or(not(A), B), or(A, not(B))), not(C))

there aren’t any negations to do, so skipping on to step 3, distributivity:

and(or(not(C), or(not(A), B)), or(not(C), or(A, not(B))))

using the associativity of ∨:

and(or(or(not(C), not(A)), B), or(or(not(C), A), not(B)))

we’ve got it in CNF.

Questions

1. Write the following formulas in CNF notation:

1. or(A, implies(not(B), A))

2. implies(implies(A, B), C)

3. or(P, equals(Q, not(P)))

4. or(and(A, B), and(A, C))

5. and(and(A, B), and(A, C))

1. or(A, implies(not(B), A))
or(A, or(not(not(B)), A)) [Material Implication]
or(A, or(B, A)) [Idempotence of ‘not’]
or(or(A, B), A) [Associativity of ‘or’]

2. implies(implies(A, B), C)
implies(or(not(A), B), C) [Material Implication]
or(not(or(not(A), B)), C) [Material Implication]
or(and(not(not(A), not(B)), C) [De Morgan’s Laws]
or(and(A, not(B)), C) [Idempotence of ‘not’]
and(or(C, A), or(C, not(B))) [Distribute ‘or’ over ‘and’]

3. or(P, equals(Q, not(P)))
or(P, and(or(not(Q), not(P)), or(Q, not(not(P))))) [Material Equality]
or(P, and(or(not(Q), not(P)), or(Q, P))) [Idempotence of ‘not’]
and(or(P, or(not(Q), not(P))), or(P, or(Q, P))) [Distribute ‘or’ over ‘and’]

4. or(and(A, B), and(A, C))
and(or(and(A, B), A), or(and(A, B), C)) [Distribute ‘or’ over ‘and’]
and(and(or(A, A), or(B, A)), and(or(A, C), or(B, C))) [Distribute ‘or’ over ‘and’]
and(and(and(or(A, A), or(B, A)), or(A, C)), or(B, C)) [‘and’ is associative]

5. and(and(A, B), and(A, C))
and(and(and(A, B), A), C) [‘and’ is associative]

4.5. CNF Set Notation

As we’ve seen, the ‘or’ function is commutative and associative. Dr Robinson told me that this means that for any CNF clause it doesn’t matter how you arrange the brackets and literals, each arrangement will be equivalent. Let’s try that out:

or(A, B)
or(B, A)

well yes, that’s easy because since ‘or’ is commutative:

or(A, B) ≡ or(B, A)

Here are all the different ways of arranging three literals:

or(or(A, B), C)
or(or(A, C), B)
or(or(B, A), C)
or(or(B, C), A)
or(or(C, A), B)
or(or(C, B), A)
or(A, or(B, C))
or(A, or(C, B))
or(B, or(A, C))
or(B, or(C, A))
or(C, or(A, B))
or(C, or(B, A))

I’ll try and transform the second clause to be the same as the first:

or(or(A, C), B)
or(A, or(C, B)) [associativity]
or(A, or(B, C)) [commutativity]
or(or(A, B), C) [associativity]

and transforming the third clause to be the same as the first:

or(or(B, A), C)
or(or(A, B), C) [commutativity]

Okay, so a collection of literals in any order is enough to specify a clause. ‘But wait’, cries Robinson, ‘there’s more! Since AND is commutative and associative, all ways of arranging the clauses and brackets of a CNF formula are equivalent’. Well let’s try that out with two clauses A and B:

and(A, B)
and(B, A)

since ‘and’ is commutative:

and(A, B) ≡ and(B, A)

Here are all the different ways of arranging three clauses:

and(and(A, B), C)
and(and(A, C), B)
and(and(B, A), C)
and(and(B, C), A)
and(and(C, A), B)
and(and(C, B), A)
and(A, and(B, C))
and(A, and(C, B))
and(B, and(A, C))
and(B, and(C, A))
and(C, and(A, B))
and(C, and(B, A))

I’ll try and transform the second formula to be the same as the first:

and(and(A, C), B)
and(A, and(C, B)) [associativity]
and(A, and(B, C)) [commutativity]
and(and(A, B), C) [associativity]

and then transform the third formula to be the same as the first:

and(and(B, A), C)
and(and(A, B), C) [commutativity]

With that under my belt, Robinson exclaimed, ‘Idempotence! We can ignore any repeated literals in a CNF clause or repeated clauses in a CNF formula’. Robinson was used to quicker minds than mine, so I asked him to elaborate. If we’ve got a clause:

or(A, A)

then since ‘or’ is idempotent we can replace it with:

A

and with a more complicated example:

or(or(A, B), A)

since we know that we can put the brackets and literals anywhere we can write:

or(or(A, A), B)
or(A, B) [idempotence]

Likewise, if we’ve got a CNF formula:

and(A, A)

them since ‘and’ is idempotent we can replace it with:

A

and with a more complicated example:

and(and(A, B), A)

since we know that we can put the brackets and literals anywhere we can write:

and(and(A, A), B)
and(A, B) [idempotence]

‘Do keep up Locke! I now want to introduce the idea of a set, which is a collection of items which is unordered and no item is repeated. A CNF clause can be written as a set of literals, and a CNF formual can be written as a set of clauses’.

Here are some example clauses in the left hand column, and the clauses in set notation in the right hand column:

CNF Clause Set Notation

or(not(P), Q)

{not(P), Q}

P

{P}

or(or(P, Q), not(R))

{P, Q, not(R)}

So an example formula:

and(and(or(not(P), Q), P), or(or(P, Q), not(R)))

is written in CNF set notation as:

{{not(P), Q}, {P}, {P, Q, not(R)}}

Yes, I like this CNF set notation. Much clearer and easier to write. How do you find it? Here’s another example:

or(or(not(A), B), not(C))

which written in set notation is:

{{not(A), B, not(C)}}

Okay, in the second example we’ve got to convert:

and(or(or(not(C), not(A)), B), or(or(not(C), A), not(B)))

into set notation which gives:

{{not(C), not(A), B}, {not(C), A, not(B)}}

So to go from CNF to CNF set notation:

1. Remove repeated literals in clauses (‘or’ associativity, commutativity and idempotence)

2. Remove repeated clauses in the formula (‘and’ associativity, commutativity and idempotence)

3. Rewrite clauses as a comma separated list of literals surrounded by braces.

4. Rewrite formula as comma separated list of clauses surrounded by braces.

Questions

1. Write the answers to the CNF section in CNF set notation:

1. and(or(C, A), or(C, not(B)))
{{C, A}, {C, not(B)}}

2. and(or(P, or(not(Q), not(P))), or(P, or(Q, P)))
and(or(P, or(not(Q), not(P))), or(P, Q)) [‘or’ associativity, commutativity and idempotence]
{{P, not(Q), not(P)}, {P, Q}} [set notation]

3. and(and(and(or(A, A), or(B, A)), or(A, C)), or(B, C))
{{A}, {B, A}, {A, C}, {B, C}} [set notation]

4. and(and(and(A, B), A), C)
and(and(B, A), C) [‘and’ associativity, commutativity and idempotence]
{{B}, {A}, {C}} [Set notation]

4.6. Propositional Resolution

The logicians have discovered / invented other ways of showing if an argument is valid or not. One of these methods is Propositional Resolution.

Writing out truth tables gets tedious, especially as the number of rows grows exponentially with the number of atomic formulas. The logicians have discovered

4.7. Mendelson’s Axiomatic System

Writing out truth tables gets tedious, especially as the number of rows grows exponentially with the number of atomic formulas. The logicians have discovered / invented other ways of showing if an argument is valid or not. One of these methods is Mendelson’s Axiomatic System. They tell me it may not be easier than truth tables but enables them to introduce Big Ideas. I can’t help but feel that’s somewhat patronising. These so-called Big Ideas better be worth it. Mendelson’s System only works if an argument is expressed using only the functions ¬ and →. You have to rewrite the argument using the following rules of replacement:

• (P ∨ Q) ≡ (¬P → Q)

• (P ∧ Q) ≡ ¬(P → ¬Q)

• (P ↔ Q) ≡ ¬P → Q) → ¬(Q → P

So for example we looked at this argument previously:

(A ∨ B), ¬B ⊨ A

Using the above rules of replacement we can rewrite it as:

(¬A → B), ¬B ⊨ A

about theseSo, I’ll press on

and I find this attitude somewhat patronising. It involves rewriting the assumptions in a progressively simpler and simpler form until you end up with the conclusion. The simplifying substitutions are valid arguments that are known as rules of inference. One rule of inference is:

(A ∨ B), ¬B ⊨ A

Writing out truth tables gets tedious, especially as the number of rows grows exponentially with the number of atomic formulas. The logicians have discovered / invented an easier way of showing if an argument is valid or not. It involves rewriting the assumptions in a progressively simpler and simpler form until you end up with the conclusion. The simplifying substitutions are valid arguments that are known as rules of inference. One rule of inference is:

4.8. Rules Of Inference

Writing out truth tables gets tedious, especially as the number of rows grows exponentially with the number of atomic formulas. The logicians have discovered / invented an easier way of showing if an argument is valid or not. It involves rewriting the assumptions in a progressively simpler and simpler form until you end up with the conclusion. The simplifying substitutions are valid arguments that are known as rules of inference. One rule of inference is:

P, P → Q ⊨ Q

You can see this is a valid argument because the formula:

((P ∧ (P → Q)) → Q)

has the truth table:

 P Q (P → Q) (P ∧ (P → Q)) ((P ∧ (P → Q)) → Q) 1 1 1 1 1 0 1 1 0 1 1 0 0 0 1 0 0 1 0 1

which shows that the formula is valid and so the argument is valid. This rule of inference has the typically recondite name of…​modus ponens!!!

Another rule of inference is:

A ∧ B ⊨ B

and another:

A ∧ B ⊨ A

These two rules are called ∧ reduction. And so, armed with these rules, lets find out if the following argument is valid:

A ∧ B → A, B ⊨ A

The steps to show this is valid are:

1. A ∧ B → A (assumption)

2. B → A (1. and ∧ reduction)

3. B (assumption)

4. A (2. and 3. and modus ponens)

Case solved! Another one:

Q, (R ∧ P) ∧ (R ∧ Q) → P ⊨ P
1. (R ∧ P) ∧ (R ∧ Q) → P (assumption)

2. R ∧ (R ∧ Q) → P (1. and ∧ reduction)

3. R ∧ Q → P (2. and ∧ reduction)

4. Q → P (3. and ∧ reduction)

5. Q (assumption)

6. P (4. and 5. and modus ponens)

Here’s a list of rules of inference:

Name Rule

Modus ponens

(A → B), A ⊨ B

Modus tollens

(A → B), ¬B ⊨ ¬A

→ introduction

A ⊨ (B → A)

∨ introduction

A ⊨ (A ∨ B)

∨ elimination

(A → C), (B → C), (A ∨ B) ⊨ C

↔ introduction

(A → B), (B → A) ⊨ (A ↔ B)

↔ elimination

(A ↔ B) ⊨ (A → B)

∧ introduction

A, B ⊨ (A ∧ B)

∧ elimination

(A ∧ B) ⊨ A

¬ elimination

Assume ¬A, derive B and ¬B ⊨ A

transitive

A → B, B → C ⊨ A → C

Questions

1. Show that the rules of inference are valid by using a truth table.

2. For all the arguments in the questions for Entailment, show that they are valid by using rules of inference.

1. The following truth table shows that A ∧ (A → B) → B is valid, and so the rule of inference is valid.

 1 2 3 4 5 A B A → B A ∧ col_3 col_4 implies B 1 1 1 1 1 0 1 1 0 1 1 0 0 0 1 0 0 1 0 1
1. The following truth table shows that A ∧ B → (A → B) is valid, and so the rule of inference is valid.

 1 2 3 4 5 A B A ∧ B A → B col_3 → col_4 1 1 1 1 1 0 1 0 1 1 1 0 0 0 1 0 0 0 1 1
1. The following truth table shows that (A → B) ∧ ¬B → ¬A is valid, and so the rule of inference is valid.

 1 2 3 4 5 6 7 A B A → B ¬B ¬A col_3 ∧ col_4 col_6 → col_5 1 1 1 0 0 0 1 0 1 1 0 1 0 1 1 0 0 1 0 0 1 0 0 1 1 1 1 1
1. The following truth table shows that ¬¬A → A is valid, and so the rule of inference is valid.

A ¬A ¬¬A ¬¬A → A

1

0

1

1

0

1

0

1

1. The following truth table shows that A ∧ B → A is valid, and so the rule of inference is valid.

A B A ∧ B A ∧ B → A

1

1

1

1

0

1

0

1

1

0

0

1

0

0

0

1

1. The following truth table shows that A ∧ B → A ∧ B is obviously valid, and so the rule of inference is valid.

2. The following truth table shows that (A → C) ∧ (B → C) ∧ (A ∨ B) → C is valid, and so the rule of inference is valid.

 1 2 3 4 5 6 7 8 9 A B C A → C B → C A ∨ B col_4 ∧ col_5 col_7 ∧ col_6 col_8 → C 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 0 1 1 1 0 1 0 1 1 1 0 0 0 1 0 0 1 0 1 0 1 0 1 0 0 1 1 0 0 0 1 1 0 0 1 0 0 0 1 1 0 1 0 1
1. The following truth table shows that A → A ∨ B is valid, and so the rule of inference is valid.

A B A ∨ B A → A ∨ B

1

1

1

1

0

1

1

1

1

0

1

1

0

0

0

1

1. The following truth table shows that (A ∨ B) ∧ ¬B → A is valid, and so the rule of inference is valid.

 1 2 3 4 5 6 A B A ∨ B ¬B col_3 ∧ col_4 col_5 → A 1 1 1 0 0 1 0 1 1 0 0 1 1 0 1 1 1 1 0 0 0 1 0 1
1. The following truth table shows that (A → B) ∧ (B → C) → (A → C) is valid, and so the rule of inference is valid.

 1 2 3 4 5 6 7 8 9 A B C A → B B → C A → C col_4 ∧ col_5 col_7 → col_6 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 0 1 1 0 1 0 0 1 1 1 1 1 1 1 1 0 1 0 0 0 1 0 1 0 1 0 1 0 1 1 0 0 0 1 0 0 1 0 0 0 1 1 1 1 1
1. P: It’s a silent film.
Q: There’s no sound.
P → Q, P ⊨ Q

1. P → Q (assumption)

2. P (assumption)

3. Q (1. and 2. and modus ponens)

2. A: Scheherazade bought black paint.
B: Scheherazade bought grey paint.
A ∨ B, ¬B ⊨ A

1. A ∨ B (assumption)

2. ¬B (assumption)

3. A (1. and 2. and ∨ syllogism)

3. P: Ben won a tennis match.
Q: Toby won a tennis match.
¬(P ∧ Q), Q ⊨ ¬P

1. P (assume as part of ¬ elimination)

2. Q (assumption)

3. P ∧ Q (1. and 2. and ∧ introduction)

4. ¬(P ∧ Q) (assumption)

5. ¬P (3. and 4. and ¬ elimination)

4. P: Bill orders 6x.
Q: Bill orders Tribute.
R: The pub is open.
P ∨ Q, P ∨ Q → R, ¬Q ⊨ R ∧ P

1. ¬P (assume for ¬ elimination)

2. ¬Q (assumption)

3. ¬P ∧ ¬Q (1. and 2. ∧ introduction)

4. ¬(P ∨ Q) (3. and De Morgan’s law)

5. P ∨ Q (assumption)

6. P (4 and 5 and ¬ elimination)

7. P ∨ Q → R (assumption)

8. R (7 and 5 and modus ponens)

9. P ∧ R (7 and 8 and ∧ introduction) 10.

5. P: The light switch is on.
Q: The light switch is off.
P ∨ Q, ¬(P ∧ Q), ¬P ⊨ Q

1. ¬Q (assume for ¬ elimination)

2. ¬P (assumption)

3. ¬P ∧ ¬Q (1 and 2 and ∧ introduction)

4. ¬(P ∨ Q) (3 and De Morgan’s laws)

5. P ∨ Q (assumption)

6. Q (4 and 5 and ¬ elimination)

4.9. Sentential Logic: Summary

Name Rule

∨ associativity

(P ∨ (Q ∨ R)) ≡ (\(P ∨ Q) ∨ R)

∧ associativity

(P ∧ (Q ∧ R)) ≡ (\(P ∧ Q) ∧ R)

↔ associativity

(P ↔ (Q ↔ R)) ≡ (\(P ↔ Q) ↔ R)

∨ commutativity

(P ∨ Q) ≡ (Q ∨ P)

∧ commutativity

(P ∧ Q) ≡ (Q ∧ P)

Answers on their way…​

4.10. Rosetta Stone Figure 5. Rosetta Stone by Hans Hillewaert - Own work. Licensed under CC BY-SA 4.0 via Wikimedia Commons.

I’ve found that in maths, the same thing is often called different names by different authors. Also, some authors take different philosophical approaches to the same area of maths. This point of this section is to help us understand what other authors are saying, in terms that we already understand.

4.10.1. Sentential Logic versus Propositional Logic versus Boolean Algebra

Some authors talk of Sentential Logic, and some talk of Propositional Logic. This is a philosophical difference. Say there are two statements that mean the same thing but use a different form of words. The sentential school of thought uses a different label for each statement, but the proposition school would use just one label.

Where does Boolean Algebra come in? Once you’ve decided on labels and formulas, then as far as I can see Propositional Logic and Sentential logic are both Boolean Algebras.

4.10.2. Functional Notation Versus Operational Notation

The formula:

and(or(A, B), C)

would be written in operational notation as:

(\(A ∨ B) ∧ C)

I’ve chosen to use functional notation because functions are more general than operations. So in learning maths you have to learn functional notation, but you don’t necessarily have to learn operational notation.

4.10.3. Synonyms

Name Synonym

True, 1

T

False, 0

F

Function

Operation, connective

Sentential Logic

Sentential Calculus

Not

~, negation, ¬

And

Conjunction, ∧

Or

Disjunction, ∨

Implies

Conditional, →, material implication

Atomic formula

Atom, simple proposition, atomic sentence, simple sentence, proposition constant, logical constant

Compound formula

compound proposition, compound sentence

Interpretation

Truth assignment

Valid formula

Tautology

Unsatisfiable formula

Identity

Rule of replacement

• All the rules of inference. and equivalence

4.10.4. Antecedent and Consequent

The formula before the → is called the antecedent and the formula after the → is the consequent.

4.10.5. Precedence

In many parts of the Ivory Tower they adopt the convention of precedence of functions Let’s say we’ve got three atomic formulas P, Q and R. What’s the truth table for:

P ∨ Q ∧ R

But wait, do I do the P ∨ Q first and then apply the ∧ to the result? Or do I do Q ∧ R first and then apply P ∨ to the result? And does it even matter? The Rules Of Propositional Logic that I read while in the Ivory Tower are quite clear on the point. They say that ∧ is evaluated before ∨. Okay, so the truth table for P ∨ Q ∧ R is:

P Q R Q ∧ R P ∨ Q ∧ R

1

1

1

1

1

0

1

1

1

1

1

0

1

0

1

0

0

1

0

0

1

1

0

0

1

0

1

0

0

0

1

0

0

0

1

0

0

0

0

0

So what would you write if you want to do P ∨ Q and then apply ∧ R? The Rules say that anything in brackets gets evaluated first. So you’d write:

(P ∨ Q) ∧ R

and the truth table is:

P Q R P ∨ Q (P ∨ Q) ∧ R

1

1

1

1

1

0

1

1

1

1

1

0

1

1

1

0

0

1

0

0

1

1

0

1

0

0

1

0

1

0

1

0

0

1

0

0

0

0

0

0

Questions

1. Write out the truth tables for:

1. P ∧ Q ∨ R

2. P ∧ Q ∧ R

3. P ∨ Q ∨ R

4. P ∧ (Q ∨ R)

P Q R P ∧ Q P ∧ Q ∨ R

1

1

1

1

1

0

1

1

0

1

1

0

1

0

1

0

0

1

0

1

1

1

0

1

1

0

1

0

0

0

1

0

0

0

0

0

0

0

0

0

P Q R P ∧ Q P ∧ Q ∧ R

1

1

1

1

1

0

1

1

0

0

1

0

1

0

0

0

0

1

0

0

1

1

0

1

0

0

1

0

0

0

1

0

0

0

0

0

0

0

0

0

P Q R P ∨ Q P ∨ Q ∨ R

1

1

1

1

1

0

1

1

1

1

1

0

1

1

1

0

0

1

0

1

1

1

0

1

1

0

1

0

1

1

1

0

0

1

1

0

0

0

0

0

P Q R Q ∨ R P ∧ (Q ∨ R)

1

1

1

1

1

0

1

1

1

0

1

0

1

1

1

0

0

1

0

0

1

1

0

1

1

0

1

0

1

0

1

0

0

0

0

0

0

0

0

0

5. Number Theory

The study of integers.

6. Real Analysis

The study of real numbers. Also known as calculus.

7. Complex Analysis

The study of complex numbers.

7.1. Tuples

‘Wait, you say that with sets, ordering doesn’t matter, but in lots of things ordering does matter. What about a list of countries in alphabetical order?’

Yes, good point reader. Remember I’m still learning this stuff too, you know. I’ll get back to you…​

…​I’m back, got it all worked out. Here’s our set of countries:

{‘UK’, ‘Germany’, ‘Spain’}

Now adding alphabetical ordering:

{{‘UK’, 3}, {‘Germany’, 1}, {‘Spain’, 2}}

So we’ve made a set of sets. The inner sets have the country and their position in the alphabetical order. Ordered sets occur quite often in maths, so they’re given the name tuples and denoted by surrounding the elements with brackets, so:

{{‘UK’, 3}, {‘Germany’, 1}, {‘Spain’, 2}} ≡ ('Germany', ‘Spain’, ‘UK’)

Here are the names of tuples based on the number of elements they contain…​

Number Of Elements Name Example

0

Nuple

()

1

Single

(8)

2

Double or Ordered Pair

(7, 4)

3

Triple

(‘bear’, ‘tiger’, ‘sheep’)

Actually, I made up ‘nuple’. It’s commonly called ‘the empty tuple’.

7.2. Functions

In the tower they fiddle around a lot with functions. A function is a set that relates a set of tuples (the domain) to another set (the codomain). For any tuple (called the ‘input’) of the domain there’s a double in the function of the form:

(input, output)

where ‘output’ is an element of the codomain.

‘That sounds all very clever and fancy, but what do you actually mean?’ Well an example I found in the tower is the add_one function which has as its domain Z1:

Z1 ≡ {…​, (-2), (-1), (0), (1), (2), …​}

The codomain of add_one is Z, and the relationship is:

add_one ≡ {…​, ( (-2), -1), ( (-1), 0), ( (0), 1), ( (1), 2), …​}

and if you want to talk about individual inputs and outputs of a function, you can write:

We’ve defined the function add_one in words and through examples and using the ellipses (and the clue is in the name of the function!) but I saw that mostly, mathematicians will define a function using mathematical notation, so they’ll write:

add_one(x) ≡ x + 1

They’ll often use the letter x, but it needn’t be. Could be anything. Eg:

add_one(H) ≡ H + 1

Another example. Let’s make up another function called mult_ten. The domain will be Z1 and the codomain Z as in the previous example. The relationship is defined as:

mult_ten(x) ≡ x * 10

Let’s try it out with some inputs and see what the outputs are:

mult_ten(1) ≡ 10
mult_ten(8) ≡ 80
mult_ten(0) ≡ 0

In the previous examples we chose domains of singles, but let’s create a function that has a domain of doubles. So let’s create a function called mult_add with the domain Z2. Now Z2 is the set of doubles which are all possible combinations of an element of Z followed by another element of Z which is shown in this table:

…​ -2 -1 0 1 2 …​

…​

(…​, …​)

(…​, -2)

(…​, -1)

(…​, 0)

(…​, 1)

(…​, 2)

(…​, …​)

-2

(-2, …​)

(-2, -2)

(-2, -1)

(-2, 0)

(-2, 1)

(-2, 2)

(-2, …​)

-1

(-1, …​)

(-1, -2)

(-1, -1)

(-1, 0)

(-1, 1)

(-1, 2)

(-1, …​)

0

(0, …​)

(0, -2)

(0, -1)

(0, 0)

(0, 1)

(0, 2)

(0, …​)

1

(1, …​)

(1, -2)

(1, -1)

(1, 0)

(1, 1)

(1, 2)

(1, …​)

2

(2, …​)

(2, -2)

(2, -1)

(2, 0)

(2, 1)

(2, 2)

(2, …​)

…​

(…​, …​)

(…​, -2)

(…​, -1)

(…​, 0)

(…​, 1)

(…​, 2)

(…​, …​)

The codomain of mult_add is Z, and the relationship between the domain and codomain is defined by:

mult_add(x, y) ≡ x * 2 + y

Let’s try it out with some inputs and see what the outputs are:

mult_add(1, 6) ≡ 8
mult_add(8, 3) ≡ 19
mult_add(0, 2) ≡ 2

Functions whose input is a single are called unary functions, and functions whose input is a double are called binary functions. Can we have functions whose input is the nuple? Let’s define a function called five, it’ll have the domain {()} and the codomain Z. The function just contains one double:

( (), 5)

so:

five() ≡ 5

The

7.4. Is In

Set theoreticians use the symbol ∈ to mean ‘is an element of’. So if there was an element x that was in a set A we could abbreviate that to:

x ∈ A

Conversely, they use the symbol ∉ to mean ‘is not an element of’. Eg.

x ∉ A

7.5. Indicator Function

Those wacky mathematicians have come up with a binary function called the indicator function, denoted by 1, that has as its input a double consisting of an element and a set. The function is defined as:

• Domain: The set of doubles of all possible combinations of (element, set).

• Codomain: B

• 1(x, A) ≡ true if x ∈ A otherwise false

1(1, Z) ≡ true
1('France', Z) ≡ false
1(-1000, {red, green, blue}) ≡ false

7.6. Subset

Another binary function with codomain B is the subset function that has the symbol ⊆. The subset function is defined as:

• Domain: The set of doubles of all possible combination of (set, set)

• Codomain: B

• ⊆(A, B) ≡ true if and only if all the elements of A are also in B, otherwise false.

So if A is a subset of B we can write:

⊆(A, B) ≡ true

Following this definition of a subset, every set is a subset of itself. So it’s always true that:

⊆(A, A) ≡ true

By the way, the domain of ⊆ crops up quite a lot in definitions of functions, so I’ll give it the name S, so from now on:

S ≡ The set of doubles of all possible combination of (set, set)

7.7. Equals

The symbol for the equals function is =, and it’s defined as:

• Domain: S

• Codomain: B

• =(A, B) ≡ true if A and B form an identiy, otherwise false.

7.8. Proper Subset

The symbol for the proper subset function is , and it’s defined as:

• Domain: S

• Codomain: B

• ⊂(A, B) ≡ true if ⊆(A, B) is true and A ≢ B.

7.9. Union

∪: S {rarr} S
A, B ↦ {x | x ∈ A or x ∈ B}

7.10. Intersection

∩: S {rarr} S
A, B ↦ {x | x ∈ A and x ∈ B}

7.11. Complement

\\: S {rarr} S
A, B ↦ {x | x ∈ A and x ∉ B}

Uc