Discrete Mathematics/Logic/Exercises

Logic Exercise 1

1

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 $\scriptstyle \wedge$ 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 $\scriptstyle \wedge$ q

(d) p ∨ q

(e) ¬p $\scriptstyle \wedge$ q

(f) ¬p $\scriptstyle \wedge$ ¬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) $\scriptstyle \wedge$ q

(b) (¬p) ∨ q

(c) ¬(¬p)

(d) (¬p) ∨ (¬q)

(e) ¬(p ∨ q):

(f) (¬p) $\scriptstyle \wedge$ (¬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.)

Answers

Back to Logic.

Logic Exercise 2

1

Construct truth tables for:

(a) ¬p ∨ ¬q

(b) q $\scriptstyle \wedge$ (¬p ∨ q)

(c) p $\scriptstyle \wedge$ (q ∨ r)

(d) (p $\scriptstyle \wedge$ q) ∨ r

2

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

(a) p ∨ (¬p $\scriptstyle \wedge$ q)

(b) p ∨ q

3

Repeat question 2 for:

(a) p $\scriptstyle \wedge$ (q $\scriptstyle \wedge$ p)

(b) p $\scriptstyle \wedge$ q

Answers

Back to Logic.

Logic Exercise 3

1

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

(a)

(i) p ∨ (q $\scriptstyle \wedge$ ¬p)

(ii) p ∨ q

(b)

(i) (¬p $\scriptstyle \wedge$ q) ∨ (p $\scriptstyle \wedge$ ¬q)

(ii) (¬p $\scriptstyle \wedge$ ¬q) ∨ (p $\scriptstyle \wedge$ 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 $\scriptstyle \wedge$ b $\scriptstyle \wedge$ ¬c)

(b)

(a $\scriptstyle \wedge$ b) ∨ (a $\scriptstyle \wedge$ b $\scriptstyle \wedge$ ¬c $\scriptstyle \wedge$ d) ∨ (¬a $\scriptstyle \wedge$ b)

3

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

(a)

¬(¬a $\scriptstyle \wedge$ ¬b)

(b)

(a $\scriptstyle \wedge$ b) ∨ (a $\scriptstyle \wedge$ ¬b) ∨ (¬a $\scriptstyle \wedge$ b)

(c)

(q $\scriptstyle \wedge$ ¬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, $\scriptstyle \wedge$, ∨ and ¬, write a statement that will only be true under these conditions.

6

Use truth tables to show that:

¬((p ∨ ¬q) ∨ (r $\scriptstyle \wedge$ (p ∨ ¬q))) ≡ ¬p $\scriptstyle \wedge$ q

7

Use the laws of logical propositions to prove that:

(z $\scriptstyle \wedge$ w) ∨ (¬z $\scriptstyle \wedge$ w) ∨ (z $\scriptstyle \wedge$ ¬w) ≡ z ∨ w

State carefully which law you are using at each stage.

Answers

Back to Logic.

Logic Exercise 4

1

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 $\scriptstyle \wedge$ (p ⇒ q)) ⇒ q

(d) (p $\scriptstyle \wedge$ 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.

Answers

Back to Logic Page 2.

Logic Exercise 5

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

Answers

Back to Logic Page 2.

Logic Exercise 6

1

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.

Answers

Back to Logic Page 2.

Logic Exercise 7

1

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) $\scriptstyle \wedge$ cheats(x)

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

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

(d) ∃ x, cheats(x) $\scriptstyle \wedge$ ¬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.

Answers

Back to Logic Page 2.