Quiz

Question

True or False? Explain your answer.

\( \forall P, Q: \; (P \Rightarrow Q) \; \equiv \; ((P \wedge Q) \equiv P) \)

The English version of the question, in case you are not familiar with the notation:
for all \(P, Q\): \(P\) IMPLIES \(Q\) is equivalent to \(P\) AND \(Q\) is equivalent to \(P\)

Answer

True

Here are three different ways of answering they quesion.

1. Compute Formula

\( P \wedge Q \; \equiv \; P \)
=
both sides of \(\equiv\) are True or both sides are False
\( ((P \wedge Q) \wedge P) \vee (\neg(P \wedge Q) \wedge \neg P) \)
=
\( (P \wedge Q) \vee ((\neg P \vee \neg Q) \wedge \neg P) \)
=
\( (P \wedge Q) \vee \neg P \)
=
\( Q \vee \neg P \)
=
\( P \Rightarrow Q \)

2. Truth Table

Check the formula for all possible values of the predicates.

Case: \(P, Q = True, True\):
\( P \Rightarrow Q \quad \equiv \quad (P \wedge Q \; \equiv \; P) \)
\( T \Rightarrow T \quad \equiv \quad (T \wedge T \; \equiv \; T) \)
\( T \quad \equiv \quad (T \; \equiv \; T) \)
\( T \quad \equiv \quad T \)
\( T \)

Case: \(P, Q = True, False\):
\( P \Rightarrow Q \quad \equiv \quad (P \wedge Q \; \equiv \; P) \)
\( T \Rightarrow F \quad \equiv \quad (T \wedge F \; \equiv \; T) \)
\( F \quad \equiv \quad (F \; \equiv \; T) \)
\( F \quad \equiv \quad F \)
\( T \)

Case: \(P, Q = False, True\):
\( P \Rightarrow Q \quad \equiv \quad (P \wedge Q \; \equiv \; P) \)
\( F \Rightarrow Q \quad \equiv \quad (F \wedge T \; \equiv \; F) \)
\( T \quad \equiv \quad (F \; \equiv \; F) \)
\( T \quad \equiv \quad T \)
\( T \)

Case: \(P, Q = False, False\):
\( P \Rightarrow Q \quad \equiv \quad (P \wedge Q \; \equiv \; P) \)
\( F \Rightarrow F \quad \equiv \quad (F \wedge F \; \equiv \; F) \)
\( T \quad \equiv \quad (F \; \equiv \; F) \)
\( T \quad \equiv \quad T \)
\( T \)

3. Venn Diagram

This is the diagrammatic version of the truth table. Draw a Venn diagram with arbitrary sets representing predicates \(P, Q\). Identify the region in which the predicate \(P \Rightarrow Q\) holds. Also, identify the region in which the predicate \((P \wedge Q) \equiv Q\) holds. Show that the regions are the same.

---

K. Mani Chandy, Emeritus Simon Ramo Professor, California Institute of Technology