Intuitive logic behind the following equivalences in propositional logic

52 Views Asked by At

I was going through the text Discrete mathematics and its applications by Kenneth H. Rosen where I came across few logical equivalences as follows:

$1. (p→q)∧(p→r)≡p→(q∧r)$

$2. (p→r)∧(q→r)≡(p∨q)→r$

$3. (p→q)∨(p→r)≡p→(q∨r)$

$4. (p→r)∨(q→r)≡(p∧q)→r$

Now the thing is that the text does not deal with any intuition behind the same, though there is the obvious method of proof by truth table or using boolean laws, I was thinking about some intuitive logic, which would help me understand the actual essence behind each of these equivalences. So I came up with an intuition for each equivalence, going from left to right, in each case.


$1. (p→q)∧(p→r)≡p→(q∧r)$ : Since, we have $p$ as the hypothesis in each of the ANDed terms on the LHS, I assume that $p$ is true, if $p$ is true, then both $q$ as well as $r$ have to be true. So we have the equivalence of the RHS as: if $p$ is true then both $q$ and $r$ are true.


$2. (p→r)∧(q→r)≡(p∨q)→r$ : Since we have $r$ as the conclusion in each of the ANDed terms on the LHS, I assume that $r$ is false, then $\lnot r$ is true. Now if $r$ is false, then both $p$ as well as $q$ have to be false, so have $(\lnot r \rightarrow (\lnot p \land \lnot q)) \equiv (\lnot r \rightarrow \lnot (p \lor q)) \equiv ((p∨q)→r)$


$3. (p→q)∨(p→r)≡p→(q∨r)$ : [Similar to 1.] Since, we have $p$ as the hypothesis in each of the ORed terms on the LHS, I assume that $p$ is true, if $p$ is true, then either $q$ or $r$ or both have to be true. So we have the equivalence of on the RHS as: if $p$ is true then ($q$ or $r$) is true.


$4. (p→r)∨(q→r)≡(p∧q)→r$ : [Similar to 2] Since we have $r$ as the conclusion in each of the ORed terms on the LHS, I assume that $r$ is false, then $\lnot r$ is true. Now if $r$ is false, then either $p$ or $q$ or both have to be false, so have $(\lnot r \rightarrow (\lnot p \lor \lnot q)) \equiv (\lnot r \rightarrow \lnot (p \land q)) \equiv ((p \land q)→r)$


I just made an attempt to convince myself intuitively, I might be wrong, or a better intuitive approach might exist, if so please guide me. Thank you.

2

There are 2 best solutions below

1
On

I believe there is a more concise and intuitive explanation for parts $2$ and $4$.

For $2$, if both $p$ and $q$ imply $r$ independently of each other, then if either are true (the OR), then $r$ is true.

For $4$, if one of $p$ and $q$ implies $r$, then if both are true, then the one that truly implies $r$ must be true, meaning $r$ is true.

2
On

One issue is that in all your explanations, you only show that the RHS follows from the LHS, and not that the LHS follows from the RHS.

Also, I am not sure that your explanations are really all that more 'intuitive' than going through a truth-table or using boolean algebra. What might help more, is to come up with some concrete examples.

For example, for the second equivalence $(p \to r) \land (q \to r) \equiv (p \lor q) \to r $ you could say that the LHS says that if you are a fruit ($p$) then you are delicious ($r$), and also being a vegetable ($q$) makes you delicious ($r$), whereas the RHS says that if you are either a fruit of a vegetable ($p \lor q)$ then you are delicious ($r$). And these two claims are really saying the same thing: both fruits and vegetables are delicious!