Ch1 - Propositional Logic(1) PDF

Preview

Summary

C O M 2 0 6 M AT H E M AT I C S F O R C O M P U T I N G §1 Propositional Logic Learning outcomes By the end of this topic you should be able to: 1. say whether a sentence is a true proposition, a false proposition, a conjecture or not a proposition. 2. recognise whether a proposition is primitive or...

Description

C OM 206 M AT H E M AT I C S F OR C OM P U T I N G

§1 Propositional Logic Learning outcomes By the end of this topic you should be able to: 1. say whether a sentence is a true proposition, a false proposition, a conjecture or not a proposition. 2. recognise whether a proposition is primitive or compound. 3. understand how to determine the truth values of a compound proposition involving conjunction, disjunction, negation and material implication. 4. be able to rewrite a compound proposition in disjunctive normal form. 5. determine whether a proposition is a tautology, a contradiction, or neither. 6. determine whether two propositions are logically equivalent using truth tables. 7. show that one proposition is logically equivalent to another using fundamental equivalences.

Item 1.1

Primitive propositions A proposition is a sentence which is either true or false but not both. • The truth should be objective and not subjective. For example, ‘Messi is a better player than Ronaldo’ is a matter of opinion (subjective), and is not a proposition.

Example 1.1

Examples of true propositions include: 1. Hydrogen is the lightest element 2. The smallest prime number is 2 3. Mark Zuckerberg is a co-founder of Facebook

Example 1.2

Examples of false propositions include: 1. There are 29 hours in a day 2. 3 < 2 3. Barack Obama is the prime minister of the UK

A U T H OR : G L E N N H AW E

©U L S T E R U N I V E R S I T Y

1

C OM 206 M AT H E M AT I C S F OR C OM P U T I N G

Conjectures

2

Some sentences are propositions (i.e they must be either true or

false), but we do not know whether they are true or false. These propositions are called conjectures. For example, Fermat’s last theorem, given by: There do not exist any positive integers a, b , c for which a n + b n = c n , for any value of n > 2. was a conjecture until 1994, when it was proven to be a true proposition by Andrew Wiles. Example 1.3

Examples of conjectures include: Goldbach’s conjecture: Every even number greater than 2 is the sum of two prime numbers. P = NP: Every problem whose solution can be quickly verified by a computer can also be quickly solved by a computer.

Exercise 1.1

For each of the following sentences, say whether it is a true proposition, a false proposition, a conjecture, or not a proposition. 1. Belfast is the capital of Northern Ireland. 2. New York is the capital of the USA. 3. 50 = 1 4. Turn right at the next junction. 5. This sentence is false. 6. Life exists on other planets in the universe. 7. There is no odd perfect number. 8. x + y = y + x for every pair of real numbers x and y .

A perfect number is a natural number equal to the sum of its divisors.

9. Hamlet is Shakespeare’s best play. 10. 0.999. . . = 1

Item 1.2

Compound propositions • Many propositions are composite, i.e. composed of sub-statements and various connectives. • Such composite propositions are called compound propositions. • A proposition that cannot be broken down into simpler propositions is called primitive.

Example 1.4

The following are examples of compound propositions: • Bob studies module COM206 and studies module COM180. • Bob will either pass COM206 or fail COM206. • If Bob attends COM206 lectures then he will pass COM206.

The propositions in the previous item were all primitive.

C OM 206 M AT H E M AT I C S F OR C OM P U T I N G

Item 1.3

3

Logical operators: conjunction, disjunction and negation

■ Conjunction p ∧ q • Any two propositions p and q can be combined by the word ‘and’ to form a compound proposition.

We often use letters to represent a primitive proposition.

• This compound proposition is called the conjunction of p and q, and is denoted by p ∧ q.

Also written p AND q.

• The truth value of p ∧ q depends on the truth values of p and q as follows: If p and q are both true, then p ∧ q is true. Otherwise p ∧ q is false. • This may be represented in the form of a table, known as a truth table, as follows: p

q

p ∧q

T

T

T

T

F

F

F

T

F

F

F

F

Truth tables are useful for examining the truth values of compound propositions over the complete range of combinations of truth values of the primitive propositions. In these notes, we use T to represent True, and F to represent False.

– The first row of this table represents the situation where p is true ( T) and q is true (T). In this situation, p ∧ q is true ( T). – The second row of this table represents the situation where p is true ( T) and q is false (F). In this situation, p ∧ q is false (F). – The third row of this table represents the situation where p is false (F) and q is true (T). In this situation, p ∧ q is false (F). – The final row of this table represents the situation where p is false (F) and q is false (F). In this situation, p ∧ q is false (F).

Exercise 1.2

For each of the following propositions p and q, state whether the conjunction p ∧ q is true or false: 1. p : ‘Belfast is the capital of Northern Ireland’; q : ‘3 + 3 = 6’ 2. p : ‘Belfast is the capital of Northern Ireland’; q : ‘3 + 3 = 7’ 3. p : ‘Belfast is the capital of Scotland’; q : ‘3 + 3 = 6’ 4. p : ‘Belfast is the capital of Scotland’; q : ‘3 + 3 = 7’

■ Disjunction p ∨ q • Any two propositions p and q can be combined by the word ‘or’ to form a compound proposition. • This compound proposition is called the disjunction of p and q, and is denoted by p ∨ q. • The truth value of p ∨ q depends on the truth values of p and q as follows: If p and q are both false, then p ∨ q is false. Otherwise p ∨ q is true.

Also written p OR q .

C OM 206 M AT H E M AT I C S F OR C OM P U T I N G

4

• This may be represented in a truth table as follows: p

q

p ∨q

T

T

T

T

F

T

F

T

T

F

F

F

Note that in English usage, the word ‘or’ can be used in two different ways. p or q could mean either (1) p is true or q is true, but not p and q simultaneously, or (2) p is true or q is true, and it may be the case that p and q are both true. The mathematical meaning of p ∨ q means the second version: p and q are allowed to both be true.

For each of the following propositions p and q, state whether the disjunc-

Exercise 1.3

tion p ∨ q is true or false: • p : ‘Belfast is the capital of Northern Ireland’; q : ‘3 + 3 = 6’ • p : ‘Belfast is the capital of Northern Ireland’; q : ‘3 + 3 = 7’ • p : ‘Belfast is the capital of Scotland’; q : ‘3 + 3 = 6’ • p : ‘Belfast is the capital of Scotland’; q : ‘3 + 3 = 7’

■ Negation ¬p • Any proposition p can be turned into a proposition with the opposite truth value by forming its negation, ‘NOT p’ or ¬p . • This may be represented in a truth table as follows: p

Exercise 1.4

¬p

T

F

F

T

If p is the proposition ‘Today is Friday’ and q is the proposition ‘Yesterday it rained’, write the negation of the following propositions in English: 1. p

Exercise 1.5

2. q

3. p ∧ q

4. p ∨ q

Consider the Dennis Skinner quote: ‘Half the Tory members opposite are crooks.’ When he was told to retract this statement, he then said ‘OK, half the Tory members aren’t crooks’. Is this the negation of his original statement? If not, what is?

Item 1.4

Logical operators: (material) implication • Consider the following statement: ‘If you pass all your 1st year modules then you will proceed to 2nd year’ • This statement is an example of a conditional proposition. • If we let p and q be propositions as follows:

Conditional propositions are of the form ‘If . . . Then . . . ’

p : ‘you pass all your first year modules’ q : ‘you will proceed to second year’, then the conditional proposition above is denoted by p → q . • Proposition p is called the ‘antecedent’ and q the ‘consequent’.

→ is the logical connective used to connect two propositions to form a conditional statement. Some texts use =⇒ instead of →.

C OM 206 M AT H E M AT I C S F OR C OM P U T I N G

5

■ Constructing the truth table for p → q Question: In which of the following four scenarios could you say that the conditional proposition above was false? Case 1 You pass all your 1st year modules and proceed to 2nd year. Case 2 You pass all your 1st year modules and do not proceed to 2nd year. Case 3 You do not pass all your 1st year modules and proceed to 2nd year. Case 4 You do not pass all your 1st year modules and do not proceed to 2nd year. • Cases 1 and 4: Probably correspond to what you would expect if the statement was true. • Case 2: Probably corresponds to what you would expect if the statement was false. • Case 3: You may be surprised to proceed to second year, but this does not contradict the statement. So Case 2 is the only scenario where the conditional proposition is false. Therefore the truth table for the compound proposition p → q is as follows: p

q

p→q

T

T

T

T F

F T

F T

F

F

T

■ Thinking about p → q correctly • You should interpret p → q as meaning ‘the truth of p implies the truth of q’, i.e. if proposition p is true, then proposition q must be true. • Often p → q is read as ‘p implies q’. This type of implication is called material implication and importantly does not require there to be a causal relationship between p and q . • For example p → q is true for p : ‘1 + 1 = 2’ and q : ‘Belfast is the capital of Northern Ireland’. In this case, the antecedent is true and the consequent is true, and so p → q is true. However obviously the consequent does not follow logically from the antecedent: Belfast is not the capital of Northern Ireland because 1 + 1 = 2. • Note that a false antecedent may imply either true or false consequents. For example, consider the two conditional propositions: 1. If 9 is prime, then it is not divisible by 5 2. If 9 is prime, then it is not divisible by 3 Both propositions have the same antecedent (‘9 is prime’), but the first has a true consequent (‘9 is not divisible by 5’) and the second has a false consequent (‘9 is not divisible by 3’). Both propositions are true.

For discussion on why this is the case see: http://legacy.earlham.edu/ ~peters/courses/log/mat-imp.htm

C OM 206 M AT H E M AT I C S F OR C OM P U T I N G

6

For each of the following, is p → q true or false?

Exercise 1.6

1. p : ‘2 + 2 = 40’; q : ‘London is the capital of France’ 2. p : ‘London is the capital of France’; q : ‘2 + 2 = 50’ 3. p : ‘8 < 70’; q : ‘7 < 80’ 4. p : ‘7 < 80’; q : ‘London is the capital of England’

Let p and q represent the propositions

Exercise 1.7

p : ‘You drive over 80 miles per hour’ q : ‘You get a speeding ticket’ Write the following compound propositions using p and q and using logical connectives: 1. You do not drive over 80 miles per hour. 2. You drive over 80 miles per hour, but do not get a speeding ticket. 3. If you drive over 80 miles per hour you will get a speeding ticket. 4. If you do not drive over 80 miles per hour you will not get a speeding ticket. 5. You get a speeding ticket but did not drive over 80 miles per hour. 6. Whenever you get a speeding ticket, you are driving over 80 miles per hour.

■ The order of precedence of logical connectives • The order of precedence of logical connectives (highest to lowest) is: ¬, ∧, ∨, →,↔

↔ is introduced in Item 1.5.

• For example, consider p ∧ q ∨ r . Does this mean (p ∧ q) ∨ r or p ∧ (q ∨ r )? – As ∧ has higher precedence than ∨, it means (p ∧ q) ∨ r .

Item 1.5

Truth tables for compound propositions • Truth tables are useful for examining the truth values of compound propositions over the complete range of combinations of truth values of the primitive propositions. • Each column of the truth table represents a proposition. The first columns represent the primitive propositions; subsequent columns represent different compound propositions which make up the overall compound proposition. The final column represents the overall compound proposition. • Each row of the truth table represents a unique combination of truth values for the primitive propositions. • If there are n primitive propositions, there should be 2n rows in your truth table.

For example, the truth table for a compound proposition involving 3 primitive propositions p, q and r should have 23 = 8 rows.

C OM 206 M AT H E M AT I C S F OR C OM P U T I N G

7

• Try to fill out the truth values for the primitive propositions systematically, i.e. not in a random manner. For example, for 3 primitive propositions you could follow the pattern TTT, TTF, TFT, TFF, FTT, FTF, FFT, FFF.

Example 1.5

Write the truth table for the compound proposition (¬p ∨ q) → (p ∧ q ) • There are two primitive propositions p and q, so we know there will be 22 = 4 rows in our truth table. • We use the first two columns of our truth table to represent the truth values of the primitive propositions p and q. We follow the pattern TT, TF, FT, FF. • We use the 3rd column we use to represent the truth values of ¬p. These truth values are the opposite of the truth values in column 1. • We use the 4th column we use to represent the truth values of ¬p ∨ q. This is the antecedent of the overall compound proposition. • We use the 5th column we use to represent the truth values of p ∧ q, the consequent of the overall compound proposition. • Finally, we use the the 6th column to hold the truth values of the overall compound proposition (¬p ∨ q) → (p ∧ q). The truth values in this column are determined by whether the antecedent (column 4) implies the consequent (column 5). – For the 1st row, column 6 represents T → T, which is true. – For the 2nd row, column 6 represents F → F, which is true. – For the 3rd row, column 6 represents T → F, which is false. – For the 4th row, column 6 represents T → F, which is false.

Exercise 1.8

¬p

¬p ∨ q

p ∧q

(¬p ∨ q) → (p ∧ q)

T

F

T

T

T

F

F

F

F

T

F

T

T

T

F

F

F

F

T

T

F

F

p

q

T T

Assume p and q are true propositions, and r and s are false propositions. What is the truth value of each of the following? 1. (¬p ∧ p) → q 2. (p ∧ r ) → q 3. (p → q) → (r → s ) 4. (r → ¬s) ∧ (q → ¬r )

Exercise 1.9 Exercise 1.10

Construct a truth table for the proposition: (p ∧ (q ∨ ¬(r ∧ p))) ∨ (p ∧ ¬r ) The biconditional statement p ↔ q means (p → q) ∧ (q → p). Construct a truth table for p ↔ q. How would you translate p ↔ q into English?

C OM 206 M AT H E M AT I C S F OR C OM P U T I N G

Item 1.6

8

Tautologies and contradictions • A compound proposition is called a tautology if it is always true, regardless of the truth values of the primitive propositions that it is composed from. • A compound proposition is called a contradiction if it is always false, regardless of the truth values of the primitive propositions that it is composed from. • A compound proposition which can sometimes be true and sometimes be false, depending on the truth values of the primitive propositions that it is composed from, is neither a tautology nor a contradiction.

Example 1.6

Determine whether or not (p ∧ ¬q) ∧ (¬p ∨ q) is a tautology, contradiction, or neither. • We do this by constructing the truth table for (p ∧ ¬q) ∧ (¬p ∨ q ): (p ∧ ¬q ) ∧ (¬p ∨ q )

p

q

T

T

F

T

F

F

F

T

T

F

F

T

F

F

F

T

T

F

T

F

¬p

p ∧ ¬q

¬p ∨ q

F

F

T

F

T

T

F

F

¬q

• (p ∧ ¬q) ∧ (¬p ∨ q) is a contradiction as it is always False.

Exercise 1.11

Determine whether (p ∧ q) ∨ (¬p ∨ (p ∧ ¬q)) is a contradiction, tautology, or neither.

Item 1.7

Logical equivalence using truth tables • Two compound propositions are logically equivalent if they have exactly the same truth values for every combination of truth values for the primitive propositions. • To check if two compound propositions P and Q are logically equivalent construct a truth table with a column for P and a column for Q. Then: – If in each row the truth value of P is the same as the truth value for Q, then P and Q are logically equivalent. – If there is at least one row where P and Q have different truth values, then they are not equivalent. • If two compound propositions P and Q are logically equivalent, we write P ≡ Q.

Example 1.7

Determine whether or not p ∨ (p ∧ q) is logically equivalent to p . • We construct a truth table for p ∨ (p ∧ q) and compare its truth values to p :

Here we use P and Q to denote compound propositions, e.g. P could equal something like p ∨ q and Q could equal something like (¬p ∧ q) → q)

C OM 206 M AT H E M AT I C S F OR C OM P U T I N G

9

p

q

p ∧q

p ∨ (p ∧ q)

p

T

T

T

T

T

T

F

F

T

T

F

T

F

F

F

F

F

F

F

F

• p ∨(p ∧ q) and p are logically equivalent as they always have the same truth values.

Example 1.8

Show that p → q ≡ ¬p ∨ q – We construct a truth table with columns for p → q and ¬p ∨ q : p

q

p→q

¬p

¬p ∨ q

T

T

T

F

T

T

F

F

F

F

F

T

T

T

T

F

F

T

T

T

– The truth values for p → q and ¬p ∨ q are the same for every combination of truth values of p and q. Therefore p → q ≡ ¬p ∨ q .

There are several fundamental logical equivalences connecting very basic compound propositions. These are listed below. 1. 2. 3. 4. 5. 6. 7. 8.

9. 10. 11.

p ∨q

≡

q ∨p

p ∧q

≡

q ∧p

p ∨ (q ∨ r )

≡

(p ∨ q) ∨ r

p ∧ (q ∧ r )

≡

(p ∧ q) ∧ r

p ∧ (q ∨ r )

≡

(p ∧ q) ∨ (p ∧ r )

p ∨ (q ∧ r )

≡