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.1. Licence
This work is licensed under a Creative Commons AttributionShareAlike 4.0 International License.
1.2. Forum
If you have any comments on this book, please visit https://groups.google.com/forum/#!forum/glimpseofmathematics.
The source code for the book is at https://github.com/tlocke/maths.
1.3. Formats
This book is available in the following formats:
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:
This is a question, so not a statement.
Yay, an actual statement! It’s a sentence that is either true or false.
This isn’t true or false, it sounds like someone admonishing somebody. Not a statement.
Yes, a statement.
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.
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?’.
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

Which of the following are statements?

Who is John Galt?

He’s over there.

Three divided by three is one.

Belgium is a European country.

Praise be!

Blue is a colour.


Are the following statements true or false?

Four is greater than two.

Tennis is a colour.

A square has eight sides.

A cube has eight corners.

Birmingham is a city in England.

The word ‘rotavator’ is a palindrome.

Answers


Not a statement.

Not a statement.

A statement.

A statement.

Not a statement.

A statement.



True.

False.

False.

True.

True.

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 cake.
And a compound statement formed from these two simple statements is:
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:
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

Are the following compound statements true or false?

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

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

Some people have brown eyes and humans lay eggs.

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

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

Answers


True.

True.

False.

False.

False.

2.3. Formulas
Rather than always writing statements out in full, those workshy 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:
the two simple statements can have the atomic formulas P and Q:
Q: Abelard likes cake.
and the compound statement can be written as the compound formula:
Now that we’ve said what P and Q stand for we can take this compound statement:
and write it using the atomic formulas to give the compound formula:
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:
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:
(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:
(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

Write the following compound statements as formulas:

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

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

Some people have brown eyes and humans lay eggs.

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

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


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

Write the following compound statements as formulas:

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) 
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) 
Some people have brown eyes and humans lay eggs.
P: Some people have brown eyes.
Q: Humans lay eggs.
(P ∧ Q) 
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) 
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)


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

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 
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. 
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. 
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. 
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:
Assigning labels to the simple statements:
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))
‘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:
((true ∨ false) ∧ false)
(true ∧ false)
false
and the second formula evaluates to:
(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

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

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

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


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

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.
Two is less than four or Alaska begins with A and purple is a number.
(P ∨ (Q ∧ R))
((P ∨ Q) ∧ R) 
Purple is a number and Alaska begins with A or two is less than four.
(R ∧ (Q ∨ P))
((R ∧ Q) ∨ P)


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
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 
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:
To logicians, an interpretation (also called a truth assignment) is the assignment of true or false to P and Q. So one interpretation is:
Q is false
and another is:
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

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

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 {and) Q) means the same as (Q ∧ P).
Questions

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

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 
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:
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:
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

Give the truth tables for:

¬(P ∧ Q)

(P ∨ ¬Q)

¬¬P

¬((P ∨ Q) ∨ R)

¬((P ∨ Q) ∧ R)

Answers

Give the truth tables for:

¬(P ∧ Q)
P Q (P ∧ Q) ¬(P ∧ Q) T
T
T
F
F
T
F
T
T
F
F
T
F
F
F
T

(P ∨ ¬Q)
P Q ¬Q (P ∨ ¬Q) T
T
F
T
F
T
F
F
T
F
T
T
F
F
T
T

¬¬P
P ¬P ¬¬P T
F
T
F
T
F

¬((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

¬((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:
Q is true
the formula:
evaluates to:
(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:
B is true
C is true
the formula:
evaluates to:
(true ∨ false)
true
and so this interpretation satisfies this formula.
Questions

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

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

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

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

Answers

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

(P ∨ Q) when P is true and Q is false.
(P ∨ Q)
(true ∨ false)
true
so the interpretation satisfies the formula. 
(¬P ∨ ¬Q) when P is true and Q is false.
(¬P ∨ ¬Q)
(¬true ∨ ¬false)
(false ∨ true)
true so the interpretation satisfies the formula. 
(¬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:
Q is true
the formula:
evaluates to:
(false ∧ true)
false
since it’s false, we can say that this interpretation falsifies this formula. Under the interpretation:
B is true
C is true
the formula:
evaluates to:
(true ∧ false)
false
and so this interpretation satisfies this formula.
Questions

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

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

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

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

Answers

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

(P ∨ Q) when P is false and Q is false.
(P ∨ Q)
(false ∨ false)
false
so the interpretation falsifies the formula. 
(¬P ∨ ¬Q) when P is true and Q is true.
(¬P ∨ ¬Q)
(¬true ∨ ¬true)
(false ∨ false)
false so the interpretation falsifies the formula. 
(¬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:
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

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

((P ∨ Q) ∨ ¬P)

Answers

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

((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:
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

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

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

(P ∧ (Q ∧ ¬P))

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

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

Answers

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

((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.

(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.

(((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.

(((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:
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

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

(P ∧ ¬Q)

P

P ∨ Q

¬P

Answers

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

(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.

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

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.

¬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:
The cafe is open.
Joining the two with an implication could give the compound statement:
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:
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:
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

Write the following English statements as logical formulas:

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

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

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


Create a truth table for each of the following formulas:

(¬P → Q)

(Q → ¬Q)

((P → Q) ∨ P)

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

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

Answers

Write the following English statements as logical formulas:

The washing is out only if it’s a dry day.
P: The washing is out.
Q: It’s a dry day.
(P → Q) 
If Keith is in Bath, then Keith is in England.
A: Keith is in Bath.
B: Keith is in England.
(A → B) 
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)


Create a truth table for each of the following formulas:

(¬P → Q)
P Q ¬P (¬P → Q) T
T
F
T
F
T
T
T
T
F
F
T
F
F
T
F

(Q → ¬Q)
Q ¬Q (Q → ¬Q) T
F
F
F
T
T

((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

(¬(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

((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:
is written:
Q: It’s the 25th of December.
(P ↔ Q)
which of course is true. An example that is false is:
which is written:
Q: It’s the 2nd of March.
(P ↔ Q)
Questions

Translate the following English sentences into formulas:

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

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


Give the truth table for each of the following formulas:

(A ↔ (B ∧ C))

(B ∨ (A ↔ B))

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

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

Answers

Translate the following English sentences into formulas:

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) 
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)


Give the truth table for each of the following formulas:

(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

(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

(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

((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)
are an identity, then:
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:
is called the material implication identity.
Questions

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

(A → B)

(¬A ∨ B)

(A → ¬B)

(A ∨ B)

Answers

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

(A → B)
(¬A ∨ B) 
(¬A ∨ B)
(A → B) 
(A → ¬B)
(¬A ∨ ¬B) 
(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:
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

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

(P ↔ Q)

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

((P ↔ Q) ∧ P)

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

Answers

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

(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)
((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:
This identity is called conjunction commutativity. Not all binary connectives are commutative though. For example the pair of formulas:
(B → A)
is not an identity because:
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

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

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

∧ 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.

∨ 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.

→ 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.

↔ 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:
because the formula:
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

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

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

∧ 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.

∨ 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.

→ 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.

↔ 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:
Questions

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

∧ over ∧

→ over ↔

∨ over {equals}

Answers

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

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 ∧.

→ 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 ↔.

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
‘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:
and the ∨ connective is idempotent because:
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:
is valid, as shown by truth table:
P  (P ∨ P)  ((P ∨ P) ↔ P) 

T 
T 
T 
F 
F 
T 
and → is not idempotent because:
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:
is valid.
Questions

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

↔

∧


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

(P ∨ ¬¬Q)

¬¬(P ∨ Q)

(¬¬A ∧ ¬¬B)

Answers

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

↔ 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

∧ 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


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

(P ∨ ¬¬Q)
(P ∨ Q) 
¬¬(P ∨ Q)
(P ∨ Q) 
(¬¬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:
and:
Some say they’re obvious. Do you find them obvious? I don’t.
Questions

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

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

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.

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:
To convert the premises and conclusion from English into logical formulas, we first of all define the atomic formulas:
B: Abelard ordered cake.
So the premises and conclusion becomes:
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:
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:
Here’s another example of some premises and a conclusion in English:
In logic symbols the argument is:
B: Get to the wedding on time.
C: Lose our way.
Premises: (A → ¬B), (C → ¬B), A
Conclusion: ¬B
It’s an entailment if:
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:
Questions

Construct logical formulas for the following premises and conclusions:

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

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

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.

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.

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.


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

Construct logical formulas for the following premises and conclusions:

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 
A: Scheherazade bought black paint.
B: Scheherazade bought grey paint.
Premises: (A ∨ B), ¬B
Conclusion: A 
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 
P: Bill orders 6x.
Q: Bill orders Tribute.
R: The pub is open.
Premises: (P ∨ Q), ((P ∨ Q) → R), ¬Q
Conclusion: (R ∧ P) 
P: The light switch is on.
Q: The light switch is off.
Premises: (P ∨ Q), ¬(P ∧ Q), ¬P Conclusion: Q


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

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 ⊨ QP 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

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 ⊨ AA 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

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

Premises: (P ∨ Q), P ∨ Q) → R), ¬Q + Conclusion: (R ∧ P) + The truth table below shows that the formula: + ((((P ∨ Q) ∧ implies((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) ∧ implies((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

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 ⊨ QP 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

3. Sets
‘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

Write out the following sets in set notation:

Vowels

Minutes on a clock

Days of the week


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

Write out the following sets in set notation:

Vowels
{A, E, I, O, U} 
Minutes on a clock
{0, 1, 2, …, 57, 58, 59} 
Days of the week
{Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday}


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} 
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:
if A and B aren’t equal they write:
Let’s say we’ve got two sets S and T:
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:
Let’s make up two sets A and B:
B is {1, 2}
Sets don’t have any duplicates so the two sets A and B are equal and we can write:
‘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

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

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

{1, 5, 8, 1} and {1, 5, 8}

{8, 5, 1} and {1, 5, 8}

Answers

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

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

{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:
The number 1.5 is not in Z. They write this as:
Questions

Translate the following into set notation:

1.6 is a member of R.

Monday is not in {Tuesday, Friday}

2009 is in N


Say whether the following mathematical statements are true or false:

0.5 ∈ Z

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

0 ∈ R

Answers

Translate the following into set notation:

1.6 is a member of R.
1.6 ∈ R 
Monday is not in {Tuesday, Friday}
Monday ∉ {Tuesday, Friday} 
2009 is in N
2009 ∈ N


Say whether the following mathematical statements are true or false:

0.5 ∈ Z
False. 
5 ∉ {6, 7, 8, …, 99, 100, 101}
True 
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:
which specifies the set:
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 reuses the connectives from Propositional Logic. Another example of set builder notation is:
which specifies the set:
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

Define the following sets in set builder notation:

{34, 35, 36, …}

{34, 35, 36, …, 102, 103, 104}

{Real numbers greater than 8.1}


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

{x  x = 0}

{x  x ∈ Z ∧ x < 30}

{x  x = 1 ∧ x = 0}

Answers

Specify the following sets in set builder notation:

{34, 35, 36, …}
{x  x ∈ Z ∧ x > 33} 
{34, 35, 36, …, 102, 103, 104}
{x  x ∈ Z ∧ x > 33 ∧ x < 105} 
{Real numbers greater than 8.1}
{x  x ∈ R ∧ x > 8.1}


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

{x  x = 0}
{0} 
{x  x ∈ Z ∧ x < 30}
{…, 27, 28, 29} 
{x  x = 1 ∧ x = 0}
{}

3.6. Universal Set
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:
Going back to our universal set of books, let’s define two sets:
F = {written by female authors}
then:
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:
A proof is an argument made up of small, incontrovertible steps that lead to the theorem. A proof that S ⊆ S is:

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

Every element of S must be in S.

Therefore S ⊆ S.
Another theorem that I came across says that for any set S:
A proof of ∅ ⊆ S is:

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

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.

Therefore it must be true that ∅ ⊆ S.
Questions

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’.

Say whether the following statements are true or false:

U ⊆ E

U ⊆ S

U ⊆ U

E ⊆ S

S ⊆ E

E ⊆ E

S ⊆ S


Draw a Venn diagram of U, S and E.

Answers

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’.

Say whether the following statements are true or false:

U ⊆ E
False 
U ⊆ S
False 
U ⊆ U
True 
E ⊆ S
True 
S ⊆ E
False 
E ⊆ S
True 
S ⊆ S
True


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:
With the universal set of books and the two sets:
F = {written by female authors}
then:
drawn as a Venn diagram:
Questions

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’.

Say whether the following statements are true or false:

U ⊂ E

U ⊂ S

U ⊂ U

E ⊂ S

S ⊂ E

E ⊂ E

S ⊂ S


Draw a Venn diagram of U, S and E.

Answers

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’.

Say whether the following statements are true or false:

U ⊂ E
False 
U ⊂ S
False 
U ⊂ U
False 
E ⊂ S
True 
S ⊂ E
False 
E ⊂ E
True 
S ⊂ S
True


Draw a Venn diagram of U, S and E.

3.9. Cardinality
Cardinality is the size of a set. For a finite set this is the number of elements of the set. So for:
the cardinality of D is 7. Set theorists write this as:
Questions

Give the cardinality of the following sets:

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

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

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

∅

Answers

Give the cardinality of the following sets:

V = {A, E, I, O, U}
V = 5 
M = {0, 1, 2, …, 57, 58, 59}
M = 60 
T = {2, 4, 6, 8, 10, 12}
T = 6 
∅
∅ = 0

3.10. 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:
Take for example the set of primary colours:
The subsets of C are:

∅

{red}

{green}

{blue}

{red, green}

{red, blue}

{green, blue}

{red, green, blue}
so the power set is:
Questions

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

∅

{1}

{1, 2}

{1, 2, 3}

{True, False}

Answers

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

∅
{∅} 
{1}
{∅, {1}} 
{1, 2}
{∅, {1}, {2}, {1, 2}} 
{1, 2, 3}
{∅, {1}, {2}, {1, 2}, {3}, {1, 3}, {2, 3}, {1, 2, 3}} 
{True, False}
{∅, {True}, {False}, {True, False}}

3.11. Cardinality Of The Power Set
Set theorists have shown that if a set S has cardinality S = n, then:
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) = 2^{n} 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 watertight argument for why a mathematical statement is true.
Here’s a proof of 𝓟(S) = 2^{n}:

Looking at the case for n = 0

If n = 0 then S = ∅, so

𝓟(∅) = {∅}

{∅} = 1

1 = 2^{0}

So the theorem is correct for the case n = 0


Take a set S with cardinality n.

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.

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

So 𝓟(T) = 2 * 𝓟(S)

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

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

which is the same as the series generated by 2^{n}

So for a set S of cardinality n, 𝓟(S) = 2^{n}
3.12. Proof By Induction
I’m told that the proof we just did of 𝓟(S) = 2^{n} 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.

Basis for the induction
In this step we show that P is true when n = 0. 
Induction hypothesis
We assume that P is true for n. 
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:
Our proposition P is:

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. 
Induction hypothesis
Assume that P is true for n. 
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/2n^{2} + 1/2n + n + 1 = 1/2n^{2} + 3/2n + 1
1/2n^{2} + 3/2n + 1 = 1/2n^{2} + 3/2n + 1
and so the proposition is true for all n.
Query: Is this similar to recursion in say Haskell?
3.13. Set Difference
Set difference
3.14. Russell’s Paradox
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.
3.15. Other Paradoxes
Curry’s Paradox is:
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.
4.1. 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:
So what’s the proof of that? Well, if an interpretation satisfies {A, B, C}, then it must satisfy P, and therefore it can’t satisfy not(P). So for every interpretation, {A, B, C, not(P)} is unsatisfiable.
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 selfevidently true steps that lead to the theorem.
Questions

Write the following formulas in CNF notation:

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))

Answers


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’] 
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’] 
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’] 
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] 
and(and(A, B), and(A, C))
and(and(and(A, B), A), C) [‘and’ is associative]

4.2. 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:
not(P)
A clause is a number of literals joined by the ‘or’ function. Eg:
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))) 

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:
Applying step 1, Material Implication, we get:
applying Material Implication again gives us:
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:
Idempotence of ‘not’ alert!
We’re so nearly in CNF, but not quite. Since ‘or’ is associative:
Hah! We’re now in CNF. Okay, in the second example we’ve got to convert:
into CNF. Starting with step 1, Implications:
there aren’t any negations to do, so skipping on to step 3, distributivity:
using the associativity of ∨:
we’ve got it in CNF.
Questions

Write the following formulas in CNF notation:

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))

Answers


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’] 
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’] 
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’] 
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] 
and(and(A, B), and(A, C))
and(and(and(A, B), A), C) [‘and’ is associative]

4.3. 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(B, A)
well yes, that’s easy because since ‘or’ is commutative:
Here are all the different ways of arranging three literals:
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(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(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(B, A)
since ‘and’ is commutative:
Here are all the different ways of arranging three clauses:
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(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(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:
then since ‘or’ is idempotent we can replace it with:
and with a more complicated example:
since we know that we can put the brackets and literals anywhere we can write:
or(A, B) [idempotence]
Likewise, if we’ve got a CNF formula:
them since ‘and’ is idempotent we can replace it with:
and with a more complicated example:
since we know that we can put the brackets and literals anywhere we can write:
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:
which written in set notation is:
Okay, in the second example we’ve got to convert:
into set notation which gives:
So to go from CNF to CNF set notation:

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

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

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

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

Write the answers to the CNF section in CNF set notation:
Answers


and(or(C, A), or(C, not(B)))
{{C, A}, {C, not(B)}} 
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] 
and(and(and(or(A, A), or(B, A)), or(A, C)), or(B, C))
{{A}, {B, A}, {A, C}, {B, C}} [set notation] 
and(and(and(A, B), A), C)
and(and(B, A), C) [‘and’ associativity, commutativity and idempotence]
{{B}, {A}, {C}} [Set notation]

4.4. 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.5. 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 socalled 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:
Using the above rules of replacement we can rewrite it as:
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:
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.6. 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:
You can see this is a valid argument because the formula:
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:
and another:
These two rules are called ∧ reduction. And so, armed with these rules, lets find out if the following argument is valid:
The steps to show this is valid are:

A ∧ B → A (assumption)

B → A (1. and ∧ reduction)

B (assumption)

A (2. and 3. and modus ponens)
Case solved! Another one:

(R ∧ P) ∧ (R ∧ Q) → P (assumption)

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

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

Q → P (3. and ∧ reduction)

Q (assumption)

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

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

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


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 

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 

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 

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 

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 

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

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 

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 

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 

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 


P: It’s a silent film.
Q: There’s no sound.
P → Q, P ⊨ Q
P → Q (assumption)

P (assumption)

Q (1. and 2. and modus ponens)


A: Scheherazade bought black paint.
B: Scheherazade bought grey paint.
A ∨ B, ¬B ⊨ A
A ∨ B (assumption)

¬B (assumption)

A (1. and 2. and ∨ syllogism)


P: Ben won a tennis match.
Q: Toby won a tennis match.
¬(P ∧ Q), Q ⊨ ¬P
P (assume as part of ¬ elimination)

Q (assumption)

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

¬(P ∧ Q) (assumption)

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


P: Bill orders 6x.
Q: Bill orders Tribute.
R: The pub is open.
P ∨ Q, P ∨ Q → R, ¬Q ⊨ R ∧ P
¬P (assume for ¬ elimination)

¬Q (assumption)

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

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

P ∨ Q (assumption)

P (4 and 5 and ¬ elimination)

P ∨ Q → R (assumption)

R (7 and 5 and modus ponens)

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


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

¬P (assumption)

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

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

P ∨ Q (assumption)

Q (4 and 5 and ¬ elimination)


4.7. 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) 
4.7.1. Answers
Answers on their way…
4.8. Rosetta Stone
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.8.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.8.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.8.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 
Truth assignment 

Valid formula 
Tautology 
Unsatisfiable formula 
Contradiction 
≡ 
⇔ 
Identity 
Rule of replacement 

All the rules of inference. and equivalence
4.8.4. Antecedent and Consequent
The formula before the → is called the antecedent and the formula after the → is the consequent.
4.8.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:
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:
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

Write out the truth tables for:

P ∧ Q ∨ R

P ∧ Q ∧ R

P ∨ Q ∨ R

P ∧ (Q ∨ R)

Answers
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 
4.9. Sources

http://en.wikibooks.org/wiki/Formal_Logic/Sentential_Logic (Referred to this throughout, very good.)

Mathematics for Computing by Robert Callen 1998, Letts Educational. (This book first got me going on propositional logic.)

http://en.wikipedia.org/wiki/Propositional_calculus (This and related pages on Wikipedia continually useful).

http://logic.stanford.edu/intrologic/notes/notes.html (Excellent notes).

https://www.trinity.edu/cbrown/logic/alter.pdf (Shows the different systems of propositional logic)
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:
Now adding alphabetical ordering:
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:
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:
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 Z^{1}:
The codomain of add_one
is Z, and the relationship is:
and if you want to talk about individual inputs and outputs of a function, you can write:
add_one(70) ≡ 71
add_one(4002) ≡ 4003
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:
They’ll often use the letter x
, but it needn’t be. Could be anything. Eg:
Another example. Let’s make up another function called mult_ten
. The domain
will be Z^{1} and the codomain Z as in the previous example. The relationship
is defined as:
Let’s try it out with some inputs and see what the outputs are:
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 Z^{2}. Now Z^{2} 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:
Let’s try it out with some inputs and see what the outputs are:
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:
so:
7.3. Direct Product
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:
Conversely, they use the symbol ∉ to mean ‘is not an element of’. Eg.
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('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:
Following this definition of a subset, every set is a subset of itself. So it’s always true that:
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:
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
A, B ↦ {x  x ∈ A or x ∈ B}
7.10. Intersection
A, B ↦ {x  x ∈ A and x ∈ B}
7.11. Complement
A, B ↦ {x  x ∈ A and x ∉ B}
7.12. Universal Class
Uc