How to obtain $\quad P \Rightarrow Q \;\equiv\; (P \wedge Q \;\equiv\; P)$

Question

I'm well aware that $$\quad( P \Rightarrow Q )\;\equiv\; (\neg P\;\lor\;Q)$$

But I saw this guy use this: $$\quad (P \Rightarrow Q )\;\equiv\; (P \wedge Q \;\equiv\; P)$$

In this thread: https://math.stackexchange.com/a/449158/536430

How was this obtained? I can't find the proof for this anywhere. I know this can be easily confirmed via truth tables, and I did, but I just don't understand how he got this thereom. Anyone can show me how? Thanks!

Answer 1

I just ran into that very equivalence the other day when doing some Knights and Knaves puzzles!

Here is an example:

A very special island is inhabited only by knights and knaves. Knights always tell the truth, and knaves always lie.

You meet two inhabitants: Bart and Mel. Bart claims, “Both I am a knight and Mel is a knave.” Mel tells you, “I would tell you that Bart is a knight.”

Can you determine who is a knight and who is a knave?

Now, to put this into logic, we can just use:

$B:$ Bart is a knight

$M:$ Mel is a knight

Since what anyone says is true if and only if they are a knight, we can symbolize the provided information as:

$$B \leftrightarrow (B \land \neg M)$$

$$M \leftrightarrow (M \leftrightarrow B)$$

To solve this, we'd like to do some algebra ... but how do you simplify $B \leftrightarrow (B \land \neg M)$? Or, more general: how can we simplify $P \leftrightarrow (P \land Q) $?

Well:

$$P \leftrightarrow (P \land Q)\iff$$

$$((P \land Q) \to P) \land (P \to (P \land Q)) \iff$$

$$(\neg (P \land Q) \lor P) \land (\neg P \lor (P \land Q)) \iff$$

$$(\neg P \lor \neg Q \lor P) \land (\neg P \lor P) \land (\neg P \lor Q) \iff$$

$$\top \land \top \land (\neg P \lor Q)) \iff$$

$$(\neg P \lor Q)) \iff$$

$$P \to Q$$

So there you go: $$(P \land Q) \leftrightarrow P \iff P \to Q$$

And, of course, now that I started it, we need to solve the puzzle! OK, so we have:

$$B \leftrightarrow (B \land \neg M) \iff B \rightarrow \neg M$$

but also:

$$M \leftrightarrow (M \leftrightarrow B) \iff (M \leftrightarrow M) \leftrightarrow B \iff \top \leftrightarrow B \iff B$$

... so Bart is a knight, and hence by $B \rightarrow \neg M$, Mel is a knave.

BONUS:

Here is another Knights and Knaves puzzle:

A very special island is inhabited only by knights and knaves. Knights always tell the truth, and knaves always lie.

You meet two inhabitants: Bob and Mel. Bob tells you, “At least one of the following is true: that I am a knight or that Mel is a knave.” Mel claims, “Only a knave would say that Bob is a knave.”

Can you determine who is a knight and who is a knave?

OK, so now we have:

$$B \leftrightarrow (B \lor \neg M)$$

$$M \leftrightarrow (\bot \leftrightarrow \neg B)$$

Hmm, does $B \leftrightarrow (B \lor \neg M)$ simplify? Yes, it turns out that in general: $$P \leftrightarrow (P \lor Q) \iff Q \rightarrow P$$

(I'll leave that as an exercise for you!)

Anyway, I've dubbed these equivalences:

Knight's Rule: $$P \leftrightarrow (P \land Q)\iff P \to Q$$

Knave's Rule: $$P \leftrightarrow (P \lor Q) \iff Q \to P$$

Answer 2

Let's work through it in words as that may help elucidate things. Consider the sentence $(P\land Q)\iff P$. In words, the statement says "if and only if P and Q is true, then P is true". Now consider that this is an if and only if, so we see that P being true implies 'P and Q' is true and hence Q is true. So we see P implies Q . So we see that $(P\land Q)\iff P$ implies $(P\implies Q)$. Now consider that if P implies Q then of course P also implies 'P and Q', and further that 'P and Q' always implies P. And so we see $(P\implies Q)$ implies $(P\land Q)\iff P$. And so we get that $(P\implies Q)\iff ((P\land Q)\iff P)$

Answer 3

$(P\to Q)\leftrightarrow (P\land Q)\leftrightarrow P$

How was this obtained? I can't find the proof for this anywhere.

Now, the Biconditional connective is associative, so this may be read as $(P\to Q)\leftrightarrow ((P\land Q)\leftrightarrow P)$, which may be proven constructively.

$\def\fitch#1#2{~\begin{array}{|l}#1\\\hline #2\end{array}}$

$$\begin{array}{|l}\hline\fitch{1.~P\to Q\qquad:\textsf{assumption}}{\fitch {2.~P\qquad:\textsf{assumption}}{3.~Q\qquad:\textsf{conditional elimination (1,2)}\\4.~P\wedge Q\qquad:\textsf{conjunctive introduction (2,3)}}\\5.~P\to(P\wedge Q)\qquad:\textsf{conditional introduction (2-4)}\\\fitch{6.~P\wedge Q\qquad:\textsf{assumption}}{7.~P\qquad:\textsf{conjunctive elimination (6)}}\\8.~P\wedge Q\to P\qquad:\textsf{conditional introduction (6-7)}\\9. ~(P\to (P\land Q))\wedge((P\wedge Q)\to P)\qquad:\textsf{conjunctive introduction (5,8)}\\10. ~(P\wedge Q)\leftrightarrow P\qquad:\textsf{biconditional introduction (9)}}\\11.~(P\to Q)\to((P\wedge Q)\leftrightarrow P)\qquad:\textsf{conditional introduction (1-10)}\\\fitch{12.~(P\land Q)\leftrightarrow P\qquad:\textsf{assumption}}{13.~((P\wedge Q)\to P)\land(P\to(P\wedge Q))\qquad:\textsf{biconditional elimination (12)}\\14.~P\to(P\wedge Q)\qquad:\textsf{conditional elimination (13)}\\\fitch{15.~P\qquad:\textsf{assumption}}{16.~P\wedge Q\qquad:\textsf{conditional elimination (14,15)}\\17.~Q\qquad:\textsf{conjunction elimination (16)}}\\18.~P\to Q\qquad:\textsf{conditional introduction (15-17)}}\\19.~((P\wedge Q)\leftrightarrow P)\to(P\to Q)\qquad:\textsf{conditional introduction (12-18)}\\20.~{((P\to Q)\to((P\wedge Q)\leftrightarrow P)))\wedge((P\to Q)\gets((P\wedge Q)\leftrightarrow P))\quad:\textsf{conjunction introduction (11,19)}}\\21.~(P\to Q)\leftrightarrow((P\wedge Q)\leftrightarrow P))\quad:\textsf{biconditional introduction (20)}\end{array}$$

Which basically says:

• If $P\to Q$ then clearly $P\to (P\land Q)$ and, trivially, $(P\land Q)\to P$
• If $P\to (P\land Q)$ and, optionally, $(P\land Q)\to P$, then $P\to Q)$