Question

a) What does it mean for two propositions to be logically equivalent?

b) Describe the different ways to show that two compound propositions are logically equivalent.

c) Show in at least two different ways that the compound propositions\( - p \vee \left( {r \to - q} \right)\)and\( - p \vee - q \vee - r\)are equivalent.

Short answer

(a) If two propositions are logically equivalent then both propositions will have the same truth value.

(b) Logical equivalence of two compound propositions can be shown using either truth table or by using logical identities.

Step-by-step solution

Introduction

A compound proposition is a proposition that consists of a group of multiple statements.

Part (a) meaning

(a) If two propositions are logically equivalent then both propositions will have the same truth value.

Part (b) Ways of presenting logical equivalence

(b) One way to determine whether two compound propositions are equivalent is to use a truth table, In particular, using compound propositions p and q are equivalent if and only if use columns giving their truth value agree. Another way is to illustrate how to use logical identities that we already know to establish logical identities, something that is of practical importance for establishing equivalences of compound propositions with a large number of variables. So we will establish this equivalence by developing a series of logical equivalences.

Using truth table

(c) (i) By using the truth table shows that \( - p \vee \left( {r \to - q} \right)\)and\( - p \vee - q \vee - r\)are equivalent.

p	q	r	-p	-q	-r	\(r \to - q\)	\( - p \vee - q\)	\( - p \vee \left( {r \to - q} \right)\)	\( - p \vee - q \vee - r\)
T	T	T	F	F	F	F	F	F	F
T	T	F	F	F	T	T	F	T	T
T	F	F	F	T	T	T	T	T	T
T	F	F	F	T	T	T	T	T	T
F	T	T	T	F	F	F	T	T	T
F	T	F	T	F	T	T	T	T	T
F	F	T	T	T	F	T	T	T	T
F	F	F	T	T	T	T	T	T	T

From the truth table\( - p \vee \left( {r \to - q} \right)\)and\( - p \vee - q \vee - r\)have the same truth values, so those are equivalent.

Using logical identities

(ii) Now use logical equivalence to demonstrate \( - p \vee \left( {r \to - q} \right)\)and\( - p \vee - q \vee - r\)are equivalent.

\(\begin{aligned}{} - p \vee - q \vee - r \equiv - p \vee \left( { - q \vee - r} \right)\\\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \equiv - p \vee \left( { - r \vee - q} \right)\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,(by\,associativity)\\\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \equiv - p \vee \left( { - \left( { - r} \right) \to - q} \right)\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,(As\,\,a \vee b = - a \to b)\\\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \equiv - p \vee \left( {r \to - q} \right)\end{aligned}\)

Therefore

\( - p \vee - q \vee - r \equiv - p \vee \left( {\left( {r \to - q} \right)} \right)\)

i.e.,\( - p \vee \left( {r \to - q} \right)\) and\( - p \vee - q \vee - r\)are equivalent.