1
$\begingroup$

After proving that implication distributes over conjunction using the example below,

$$p \to (q \land r) \leftrightarrow (p \to q) \land (p \to r)$$

I need to "Find a similar transformation for $(p \lor q) \to r$"

I cannot for the life of me figure out what to do with the second part of the problem. Implication only distributes over disjunction on the left, correct? I think they want me to somehow expand the equation but I cannot figure out how. Thank you in advance for your help.

$\endgroup$
3
  • $\begingroup$ You said, "after proving", so what method was used to prove it? $\endgroup$
    – Graham Kemp
    Commented Feb 15, 2016 at 6:51
  • $\begingroup$ Start by rewriting implication in terms of negation and disjunction. $\endgroup$
    – hardmath
    Commented Feb 16, 2016 at 2:28
  • $\begingroup$ I used a truth table. $\endgroup$
    – helpmeeeee
    Commented Feb 16, 2016 at 11:26

3 Answers 3

Reset to default
3
$\begingroup$

If it is Tuesday or Wednesday, then it is raining.

What can we conclude if it is Tuesday? What if it is Wednesday?

$\endgroup$
2
  • $\begingroup$ That it's raining? I tried "(p->r) or (q->r)", but then I checked it with a truth table and it didn't work. Maybe I did it wrong? $\endgroup$
    – helpmeeeee
    Commented Feb 16, 2016 at 11:28
  • $\begingroup$ @helpmeeeee If I wrote $A, B \vdash A \text{ and } B$, would you know what that means? $\endgroup$
    – DanielV
    Commented Feb 16, 2016 at 23:30
0
$\begingroup$

Here's a hint. You can write $A \to B$ as $B^A$, $A\lor B$ as $A+B$, $A\land B$ as $AB$, truth as 1 and falsity as 0. Now all the rules from high school algebra hold. For example, the one you proved is $(AB)^C =A^CB^C$.

$\endgroup$
6
  • 1
    $\begingroup$ That's not a proof. You still have to prove that "the rules from high school algebra hold". $\endgroup$
    – 5xum
    Commented Feb 15, 2016 at 6:45
  • $\begingroup$ @5xum Completely agree. In fact, proving all of them is an excellent exercise and is very broadly applicable. $\endgroup$
    – Derek Elkins left SE
    Commented Feb 15, 2016 at 6:46
  • $\begingroup$ (Not that I'm recommending this in this case, but almost all of them are immediate consequences of continuity of adjoints. In that sense, these can actually be made into proofs "for free" with little effort, albeit it's like cracking a walnut with a sledgehammer.) $\endgroup$
    – Derek Elkins left SE
    Commented Feb 15, 2016 at 6:48
  • 1
    $\begingroup$ $A \lor B$ should be $A + B - AB$, but otherwise yes, if those relations characterize the logical operators in their domain of $\{0, 1\}$ (a finite thing to establish), then you don't actually have to prove that the laws of arithmetic apply. $\endgroup$
    – DanielV
    Commented Feb 15, 2016 at 8:00
  • $\begingroup$ @DanielV I'm only making a notational analogy (that's more than analogy). I am not saying A+B is addition of numbers, though you can make that work too. $\endgroup$
    – Derek Elkins left SE
    Commented Feb 15, 2016 at 8:20
0
$\begingroup$

We can use implication equivalence and distribution to show that:

$$\begin{align}p\to(q\wedge r) \iff & ~ \neg p\vee(q\wedge r) \\ \iff & ~ (\neg p\vee q)\wedge (\neg p\vee r) \\ \iff & ~ (p\to q)\wedge (p\to r)\end{align}$$

Similarly: $$\begin{align}(p\vee q)\to r \iff & ~ \\ \vdots \quad & ~ \\ \iff & ~ \end{align}$$

$\endgroup$
1
  • $\begingroup$ I don't believe that we have covered implication equivalence in class yet. So far we've gone over basic semantics, DeMorgan's law, and truth tables. Thank you for the reply. I'm going to look up implication equivalence. $\endgroup$
    – helpmeeeee
    Commented Feb 16, 2016 at 11:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .