THE TRUTH, THE WHOLE TRUTH AND NOTHING BUT THE TRUTH Part 1 of 3

1: Propositions and Connectives, Variables and Symbols (there are 3 subsections A B and C

Why do we learn logic? Well, the reasoning begins with something much more exciting. Artificial Intelligence (AI).

AI is about getting machines to behave as humans do. This includes making decisions and performing other human tasks like classification, or even creation of artwork! In doing this, a machine can be useful in ways that were not possible before now.

How do we begin with this?

Dartmouth professor John McCarthy coined the term “AI” in the summer of 1956, and was soon asking himself the same question. He had high hopes of a breakthrough towards human-level machine operation, but then he realised solving logic problems was the most important first step.

Why is understanding logic useful?

Many readers will be familiar with the phrase ‘know your enemy’, meaning that you must first understand your enemy before you will be able to resolve a conflict.

Machines are not our enemies, despite being featured as such in many dystopian novels and films, but the idea still stands. We must understand machines before we can work with them.

How do we begin to understand machines?

Machines interpret the world via logic, which is what this two-part course will cover. By studying logic, you will be well on your way to understanding machines.

Ready to begin?

Excellent!

Section A: Propositions

Logic is based on working with propositions. A natural, and very important, first question is:

What is a proposition?

Propositions are statements that are not questions, commands or opinions. They are either true or false but not both.

That’s the definition, but to get it clear in our minds we should unpack it.

Two important points from the definition about what a proposition is:

1. A proposition is a statement.
2. The statement can be true or false, depending on current conditions, but not both.

Examples include:

• 3+3=7 (False)
• Earth goes round the sun (True)
• 2 is prime (True)
• Today is Sunday (The truth of this depends on the day, but it is always just one, never both)

A further thing to note from the definition is what a proposition is not. Propositions are not questions, commands or opinions.

Why do these not count as propositions?

A question is not a statement. A command is an instruction and as such has no truth value associated with it. An opinion is subjective and holds no universal truth value.

The following are not propositions

• How are you? (Question)
• Go over there! (Command)
• That’s a nice dress! (Opinion)

Try it yourself! Sort the following into two lists- Propositions and Not Propositions

1. It is Monday
2. Did they complete it?
3. Eat your breakfast!
4. The trousers cost £10
5. The trousers look good
6. 2 is odd
7. 11 is odd
8. It is raining
9. Work out 3+3
10. It’s late

Answers-

1 4 6 7 and 8 are propositions

2 is a question, 3 and 9 are commands, 5 and 10 are opinions (good trousers and late times will differ from person to person)

Section B: Connectives

Just as it is possible to make complex sentences through the use of conjunctions to link clauses, it is equally possible to make complex propositions through the use of connectives to modify and combine propositions.

We will cover 4 different types of connective: Negation (NOT), Conjunction (AND), Disjunction (OR) and Implication.

For negation, conjunction and disjunction, we will begin to see how these affect the truth of a proposition. The effect of implication on truth will be covered when we study truth tables, where it can be better explained.

Negation (NOT)

Negation of a proposition is often done by adding ‘not’ to the proposition, or by changing ‘equal to’ to ‘not equal to’, as in the following examples

‘3+3=7’ becomes ‘3+3≠7’

‘Earth goes round the Sun’ becomes ‘Earth does not go round the Sun’

‘2 is prime’ becomes ‘2 is not prime’

‘Today is Sunday’ becomes ‘Today is not Sunday’

You could equally swap these round so that the negated statements are the originals and vice versa. If you negate a proposition twice you get back the original.

The effect of negation on truth is that true propositions become false, and false propositions become true.

As ‘3+3=7’ was false, ‘3+3≠7’ is true

As ‘2 is prime’ was true, ‘2 is not prime’ is false

Conjunction (AND)

We can connect two or more propositions into a compound proposition using the connective AND, as in these examples

Examples with two:

2 is prime, 5 is prime becomes ‘2 is prime and 5 is prime’

2 is prime, Earth is flat becomes ‘2 is prime and Earth is flat’

3+3=7, 5 is prime becomes ‘3+3=7 and 5 is prime’

3+3=7, Earth is flat becomes ‘3+3=7 and Earth is flat’

When using AND, the output proposition is only true when both input propositions are true. If one is true and the other false, or both are false, then the output is false.

Thus we can say that

2 is prime (True), 5 is prime (True) becomes ‘2 is prime and 5 is prime’ (True)

2 is prime (True), Earth is flat False becomes ‘2 is prime and Earth is flat’ (False)

3+3=7 (False), 5 is prime (True) becomes ‘3+3=7 and 5 is prime’ (False)

3+3=7 (False), Earth is flat (False) becomes ‘3+3=7 and Earth is flat’ (False)

We can tabulate this so that it shows the behaviour of any two propositions

Logical Connectives : AND

Proposition 1 + Proposition 2 = Output

True + True = True

True + False = False

False + True = False

False + False = False

The behaviour of AND can be generalized to any number of propositions and AND connectives.

You will need n-1 AND connectives for n propositions.

The output proposition will only be true if all the input propositions were true. If at least one was false, the output is false.

This example with three or more illustrates this nicely

2 is prime AND 5 is prime AND 3 is prime AND (other true propositions of any form)

This will be true as all input propositions are true.

If there was at least one proposition of form p is not prime (where p is prime) or X is prime (where X is not prime) or any other false proposition then these are false and the entire output proposition is false.

So ‘2 is not prime AND (other propositions)’ is false, as is ‘4 is prime AND (other propositions)’ and so is ‘3+3=7 AND (other propositions)’

I’ll repeat this because of its importance:

When connecting using AND, the output is only true when all inputs are true.

Disjunction (OR)

We can connect two or more propositions into a compound proposition using the connective OR, as in these examples

Examples with two:

2 is prime, 5 is prime becomes 2 is prime or 5 is prime

2 is prime, Earth is flat becomes 2 is prime or Earth is flat

3+3=7, 5 is prime becomes 3+3=7 or 5 is prime

3+3=7, Earth is flat becomes 3+3=7 or Earth is flat

When using OR, the output proposition is true when at least one input proposition is true- in the case of 2 propositions that is to say both or just one. It is only when both are false that the output is false.

Thus we can say that

2 is prime (True), 5 is prime (True) becomes 2 is prime or 5 is prime (True)

2 is prime (True), Earth is flat False becomes 2 is prime or Earth is flat (True)

3+3=7 (False), 5 is prime (True) becomes 3+3=7 or 5 is prime (True)

3+3=7 (False), Earth is flat (False) becomes 3+3=7 or Earth is flat (False)

We can tabulate this so that it shows the behaviour of any two propositions

Logical Connectives : OR

Proposition 1 + Proposition 2 = Output

True + True = True

True + False = True

False + True = True

False + False = False

The behaviour of OR can be generalized to any number of propositions and OR connectives.

You will need n-1 OR connectives for n propositions.

The output proposition will be true if at least one of the input propositions were true. If all were false, the output is false.

This example with three or more illustrates this nicely

2 is not prime OR 3 is not prime OR 4 is prime OR (other false propositions of any form)

This is false because all inputs are false.

If there was at least one proposition of form ‘p is prime’ (with p prime) or ‘X is not prime’ (with X not prime) or any other true proposition then these are true and so the entire output is true.

So ‘2 is prime OR (other propositions)’ is true, as is ‘4 is not prime OR (other propositions)’ and so is ‘Earth goes round the Sun OR (other propositions)’.

I’ll repeat this because of its importance:

When connecting using OR, the output is only false when all inputs are false.

Implication

This relates two propositions in a conditional sense. You can link more than two but you’d have to be careful about the overall meaning. We’ll look at two for now.

There are two types-

1. One Way Implication- This is where one proposition is the premise (or IF statement), and the other is the consequence (or THEN statement). It is a one way implication only when the propositions cannot be swapped to still make sense. We can relate them in a complex proposition in an ‘If, then’ structure like so

If (IF statement), then (THEN statement)

2. Both Ways Implication (also called Biconditional)- We start by calling one proposition the premise and the other the consequence and setting up an ‘If, then’ structure as before. We then try swapping the statements to see if is still holds. In both-ways implication cases, the propositions can be swapped so you can have them either way around and it still makes sense. We relate such propositions in an ‘If and only If’ structure like so

(One proposition) if and only if (other proposition)

As an example, consider the two propositions

‘It is raining’ and ‘The streets are wet’

We can put these into an If then structure in one way like so:

‘If it is raining, then the streets are wet’

I hope you’d agree that this makes logical sense

If we swap them, we get

‘If the streets are wet, then it is raining’

This isn’t necessarily true, as the streets could be wet from previous rain or from some other source of water like a burst pipe.

This is then just a one-way implication, written as so

‘If it is raining, then the streets are wet’

Next, consider the two propositions

‘I am alive’ and ‘I am breathing’

Putting them into an If then structure results in

‘If I am alive, then I am breathing’

I hope you’d agree that this makes logical sense.

Swapping them gives

‘If I am breathing, then I am alive’

This also makes logical sense.

Thus this is a both-ways implication, written as so

‘I am alive if and only if I am breathing’

As stated earlier, the truth of implication statements will be discussed when we look at truth tables. It is important at this stage to get a sense of the difference between a one-way implication and a both-ways implication.

Quiz Time!

Let’s test your understanding of Negation, AND and OR

Q1- Fill in the blank

Negation changes true propositions to _____ ones and false propositions to ______ ones.

Answer: false, true

Q2- Choose the right statement about the connective AND

1. AND changes true to false and false to true
2. AND outputs are true if all the input propositions are true
3. AND outputs are true if just one input proposition is true

2 is correct

Q3- Choose the right statement about the connective OR

1. OR changes true to false and false to true
2. OR outputs are false if all the input propositions are false
3. OR outputs are false if just one input proposition is false

2 is correct

Q4- Which connective’s output is true if all input propositions are true?

1. AND
2. OR
3. Both

3 is correct

Q5- Which connective’s output is true if just one input proposition Is true?

1. AND
2. OR
3. Both

2 is correct

Q6- Which connective’s output is false if just one input proposition is false?

1. AND
2. OR
3. Both

1 is correct

Q7- Which connective’s output is false if all input propositions are false?

1. AND
2. OR
3. Both

3 is correct

Q8- ‘If Proposition 1, then Proposition 2’ is the structure for what connective?

1. Both-Ways Inference
2. Both-Ways Implication
3. One-Way Inference
4. One-Way Implication

4 is correct

Q9- ‘Proposition 1 if and only if Proposition 2’ is the structure for what connective?

1. Both-Ways Inference
2. Both-Ways Implication
3. One-Way Inference
4. One-Way Implication

2 is correct

Q10- Which connectives show a conditional relationship between propositions?

1. One-Way Implication
2. Both-Ways Implication
3. Both of these

3 is correct

Section C: Variables and Symbols

While the approach we’ve taken so far is great for an initial understanding, the longer and more complex propositions are difficult to write out in full. That’s where the need for variables and symbols comes in.

Readers who are at least at GCSE level in school will be familiar with algebra and the use of letters to represent quantities in equations and formulae, for example

F=ma for Force= mass x acceleration

Formulae like this exist because we want to make an expression or equation as compact as possible so it’s easy to work with. As long as we know what each letter represents then we’re ok.

It is a more mathematical approach, and is closer to the way that a machine works.

From graphing in GCSE Maths, x and y are the variables that represent numbers linked by an equation.

X and y are numeric variables, in that they can take any number as their value.

We can work with x and y using a combination of addition, subtraction, multiplication and division.

In logic, we use variables to represent propositions. We work with them using our connectives, which are represented by symbols.

This is the mathematical approach to logic, and is how a machine would generally use logic.

Every proposition within a complex proposition needs to be assigned a separate letter variable eg. A, B, C,…… Y, Z. If we run out of letters we can put numbers in too, eg A1, A2, A3,…. B1, B2,….,. Z. This is because we need to represent them separately and keep them distinct.

When we use a variable, this can represent a known proposition, or be a general proposition. We use them as general propositions when looking at the fundamentals of logic, especially in our further sections on truth tables (this article), logic gates (next article) and logic laws (next article).

The effect of the connective on the truth of the output statement remains the same when it’s in variable and symbol form, so look back at the relevant sections if you need a refresher.

We are going to look at the symbols that represent the different connectives, but here’s a summary

~ NOT

∧ AND

∨ OR

⇒ONE-WAY IMPLICATION

⇔ BOTH-WAYS IMPLICATION

In our examples we say that P, Q and R are particular propositions to help with the formulation of the output proposition. Be aware that they could denote any propositions (or in fact just be generic propositions not denoting anything) and the theory would still apply.

Negation (NOT)

P = “2 is Prime”

~ denotes NOT

So then we have

~P = “2 is not Prime”

In general, ~P means ‘not P’

Conjunction (AND)- 2 propositions

P = “2 is Prime”

Q = “5 is Prime”

∧ denotes AND

So then we have:

P ∧ Q = “2 is Prime and 5 is Prime”

In general, P∧Q means ‘P and Q’

Conjunction (AND)- 3 propositions

P = “2 is Prime”

Q = “5 is Prime”

R = “3 is Prime”

∧ denotes AND

So then we have:

P ∧ Q ∧ R = “2 is Prime and 5 is Prime and 3 is Prime”

In general, P ∧ Q ∧ R means ‘P and Q and R’

Disjunction (OR)- 2 propositions

P = “2 is Prime”

Q = “5 is Prime”

∨ denotes OR

So then we have:

P V Q = “2 is Prime or 5 is Prime”

In general, P ∨ Q means ‘P or Q’

Disjunction (OR)- 3 propositions

P = “2 is Prime”

Q = “5 is Prime”

R = “3 is Prime”

∨ denotes OR

So then we have:

P ∨ Q ∨ R = “2 is Prime or 5 is Prime or 3 is Prime”

In general, P ∨ Q ∨R means ‘P or Q or R’

One-Way Implication- 2 propositions

P = “2 is Prime”

Q = “5 is Prime”

→ denotes ONE-WAY IMPLICATION

So then we have:

P → Q = “If 2 is Prime, then 5 is Prime”

In general, P→Q means ‘If P, then Q’

One-Way Implication- 3 propositions

P = “2 is Prime”

Q = “5 is Prime”

R = “3 is Prime”

→ denotes ONE-WAY IMPLICATION

So then we have:

P → Q → R = “If 2 is Prime, then 5 is Prime, then 3 is Prime”

In general, P→Q→R means ‘If P, then Q, then R’

Both-Ways Implication- 2 propositions

P = “2 is Prime”

Q = “5 is Prime”

↔ denotes BOTH-WAYS IMPLICATION

So then we have:

P ↔ Q = “2 is Prime if and only if 5 is Prime”

In general, P ↔Q means ‘P if and only if Q’

(note that iff can sometimes be used to denote “IF AND ONLY IF”)

Both-Ways Implication- 3 propositions

P = “2 is Prime”

Q = “5 is Prime”

R = “3 is Prime”

↔ denotes BOTH-WAYS IMPLICATION

(note that iff can sometimes be used to denote “IF AND ONLY IF”)

So then we have:

P ↔ Q ↔ R = “2 is Prime iff 5 is Prime iff 3 is Prime”

In general, P ↔Q ↔R means ‘P if and only if Q if and only if R’

Combining Connectives

Example 1- One-Way Implication, Or, Not

P = “2 is Prime”

Q = “5 is Prime”

R = “3 is Prime”

→ denotes ONE-WAY IMPLICATION

∨ denotes OR

~ denotes NOT

So then we have:

P → (Q ∨ ~R) = “If 2 is Prime, then 5 is Prime or 3 is not Prime”

In general, If P, then Q and not R

Example 2- Both-Ways Implication, And

P = “2 is Prime”

Q = “5 is Prime”

R = “3 is Prime”

(note that iff can sometimes be used to denote “IF AND ONLY IF”)

↔ denotes BOTH-WAYS IMPLICATION

∧ denotes AND

So then we have:

P → (Q ∧ R) = “2 is Prime iff 5 is Prime and 3 is Prime”

In general, P if and only if Q and R

Quiz Time!

Match the proposition and connective forms to the corresponding variable and symbol forms

1)Not P

2)P and Q

3)P or Q

4)P and Q and R

5)P or Q or R

6)If P then Q

7)If Q then P

8)If P then Q then R

9)P if and only if Q

10)P if and only if Q if and only if R

a)P∨Q∨R

b)P⇔Q

c)P⇒Q

d)P∨Q

e)P∧Q

f)Q⇒P

g)P∧Q∧R

h)P⇔Q⇔R

i)P⇒Q⇒R

j)P

k)~P

Answers- 1k, 2e, 3d, 4g, 5a, 6c, 7f, 8i, 9b, 10h