# Discrete Mathematics/Logic/Exercises

## Logic Exercise 1

edit1

- Which of the following are propositions?

- (a) Buy Premium Bonds!

- (b) The Apple Macintosh is a 16 bit computer.

- (c) There is a largest even number.

- (d) Why are we here?

- (e) 8 + 7 = 13

- (f)
*a*+*b*= 13

2

*p*is "1024 bytes is known as 1MB"

*q*is "A computer keyboard is an example of a data input device".

- Express the following compound propositions as English sentences in as natural a way as you can. Are the resulting propositions true or false?

- (a) p q

- (b) p ∨ q

- (c) ¬p

3

*p*is "*x*< 50";*q*is "*x*> 40".

- Write as simply as you can:

- (a) ¬
*p*

- (b) ¬
*q*

- (c)
*p**q*

- (d)
*p*∨*q*

- (e) ¬
*p**q*

- (f) ¬
*p*¬*q*

- One of these compound propositional functions always produces the output
*true*, and one always outputs*false*. Which ones?

4

*p*is "I like Maths"

*q*is "I am going to spend at least 6 hours a week on Maths"

- Write in as simple English as you can:

- (a) (¬
*p*)*q*

- (b) (¬
*p*) ∨*q*

- (c) ¬(¬
*p*)

- (d) (¬
*p*) ∨ (¬*q*)

- (e) ¬(
*p*∨*q*):

- (f) (¬
*p*) (¬*q*)

5

- In each part of this question a proposition
*p*is defined. Which of the statements that follow the definition correspond to the proposition ¬*p*? (There may be more than one correct answer.)

- (a)
*p*is "Some people like Maths".

- (i) "Some people dislike Maths"

- (ii) "Everybody dislikes Maths"

- (iii) "Everybody likes Maths"

- (You may assume in this question that no-one remains neutral: they either like or dislike Maths.)

- (b)
*p*is "The answer is either 2 or 3".

- (i) "Neither 2 nor 3 is the answer"

- (ii) "The answer is not 2 or it is not 3"

- (iii) "The answer is not 2 and it is not 3"

- (c)
*p*is "All people in my class are tall and thin".

- (i) "Someone in my class is short and fat"

- (ii) "No-one in my class is tall and thin"

- (iii) "Someone in my class is short or fat"

- (You may assume in this question that everyone may be categorised as
*either*tall*or*short,*either*thin*or*fat.)

Back to Logic.

## Logic Exercise 2

edit1

- Construct truth tables for:

- (a) ¬
*p*∨ ¬*q*

- (b)
*q*(¬*p*∨*q*)

- (c)
*p*(*q*∨*r*)

- (d) (
*p**q*) ∨*r*

2

- Construct truth tables for each of the following compound propositions. What do you notice about the results?

- (a)
*p*∨ (¬*p**q*)

- (b)
*p*∨*q*

3

- Repeat question 2 for:

- (a)
*p*(*q**p*)

- (b)
*p**q*

Back to Logic.

## Logic Exercise 3

edit1

- For each pair of expressions, construct truth tables to see if the two compound propositions are logically equivalent:

- (a)
- (i)
*p*∨ (*q*¬*p*) - (ii)
*p*∨*q*

- (b)
- (i) (¬
*p**q*) ∨ (*p*¬*q*) - (ii) (¬
*p*¬*q*) ∨ (*p**q*)

2

- Construct the truth table for each of the following expressions. Try to find a simpler logical equivalent in each case:

- (a)
- ¬
*a*∨ ¬*b*∨ (*a**b*¬*c*)

- (b)
- (
*a**b*) ∨ (*a**b*¬*c*d) ∨ (¬*a**b*)

3

- Use the
*Laws of Logic*or truth tables to simplify as far as possible:

- (a)
- ¬(¬
*a*¬*b*)

- (b)
- (
*a**b*) ∨ (*a*¬*b*) ∨ (¬*a**b*)

- (c)
- (
*q*¬*p*) ∨*p*

4

- Use a truth table to show that the proposition
*p*∨ (*q*∨ ¬*p*) is always true (T), whatever the values of*p*and*q*.

5

*p*,*q*and*r*represent conditions that will be true or false when a certain computer program is executed. Suppose you want the program to carry out a certain task only when*p*or*q*is true (but not both) and*r*is false.

- Using
*p*,*q*,*r*, , ∨ and ¬, write a statement that will only be true under these conditions.

6

- Use truth tables to show that:

- ¬((
*p*∨ ¬*q*) ∨ (r (*p*∨ ¬*q*))) ≡ ¬*p**q*

7

- Use the laws of logical propositions to prove that:

- (
*z**w*) ∨ (¬*z**w*) ∨ (*z*¬*w*) ≡*z*∨*w*

- State carefully which law you are using at each stage.

Back to Logic.

## Logic Exercise 4

edit1

- Propositions
*p*,*q*,*r*and*s*are defined as follows:

*p*is "I shall finish my Coursework Assignment"

*q*is "I shall work for forty hours this week"

*r*is "I shall pass Maths"

*s*is "I like Maths"

- Write each sentence in symbols:

- (a) I shall not finish my Coursework Assignment.

- (b) I don’t like Maths, but I shall finish my Coursework Assignment.

- (c) If I finish my Coursework Assignment, I shall pass Maths.

- (d) I shall pass Maths only if I work for forty hours this week and finish my Coursework Assignment.

- Write each expression as a sensible (if untrue!) English sentence:

- (e)
*q*∨*p*

- (f) ¬
*p*⇒ ¬*r*

2

- Draw up truth tables to determine whether or not each of the following propositions is always true:

- (a)
*p*⇒ (*p*∨*q*)

- (b) (
*p*⇒*q*) ⇒ (*q*⇒*p*)

- (c) (
*p*(*p*⇒*q*)) ⇒*q*

- (d) (
*p**q*) ⇒*p*

- (e)
*q*⇔ (¬*p*∨ ¬*q*)

3

- Draw up truth tables to show that
*p*⇒*q*, ¬*p*∨*q*and ¬*q*⇒ ¬*p*are all logically equivalent.

Back to Logic Page 2.

## Logic Exercise 5

editThe following predicates are defined:

*friend*is "… is a friend of mine"

*wealthy*is "… is wealthy"

*clever*is "… is clever"

*boring*is "… is boring"

Write each of the following propositions using predicate notation:

1 Jimmy is a friend of mine.

2 Sue is wealthy and clever.

3 Jane is wealthy but not clever.

4 Both Mark and Elaine are friends of mine.

5 If Peter is a friend of mine, then he is not boring.

6 If Jimmy is wealthy and not boring, then he is a friend of mine.

Back to Logic Page 2.

## Logic Exercise 6

edit1

- Using the same predicates you defined in Exercise 5, symbolise each of the following.

- (a) Some of my friends are clever.

- (b) All clever people are boring.

- (c) None of my friends is wealthy.

- (d) Some of my wealthy friends are clever.

- (e) All my clever friends are boring.

- (f) All clever people are either boring or wealthy.

2

- Define suitable propositional functions, and hence symbolise:

- (a) All pop-stars are overpaid.

- (b) Some RAF pilots are women.

- (c) No students own a Rolls-Royce.

- (d) Some doctors cannot write legibly.

Back to Logic Page 2.

## Logic Exercise 7

edit1

- In each of the following, define suitable one-place predicates and a suitable universe of discourse. Then symbolise the statements.

- (a) Some computer programmers can’t understand spreadsheets.

- (b) Every prisoner deserves a fair trial.

- (c) There are some intelligent people who support Crystal Palace Football Club.

- (d) Some stupid people don’t like curry.

- (e) All university students are good-looking or intelligent.

- (f) Not all cars are noisy and dirty.

2

- In the following, the universe of discourse is {people}. One-place predicates are defined as follows:

*cheats*is "... cheats at cards"

*punk*is "… has punk hair"

*scout*is "... is a Boy Scout"

- Write the following propositions as sensible English sentences:

- (a) ∃
*x*,*scout*(*x*)*cheats*(x)

- (b) ∀
*x*,*punk*(*x*) ⇒*cheats*(*x*)

- (c) ∀
*x*,*scout*(*x*) ⇒ ¬(*punk*(*x*) ∨*cheats*(*x*))

- (d) ∃
*x*,*cheats*(*x*) ¬*punk*(*x*)

3

- Translate the following into symbolic form, using two-place predicates, defining a suitable universe of discourse in each case.

- (a) All cows eat grass.

- (b) Harry is better at Maths than someone.

- (c) Somebody likes the Rolling Stones.

- (d) No-one expects the Spanish Inquisition.

Back to Logic Page 2.