2
$\begingroup$

I gotta draw $p \lor q ↔ q$ from $p → q$, logically. not by a truth table.

While it seems obvious, I cannot find a formal proof.

This is how far I came up to:

$\quad p \lor q$

$\equiv (p \land T) \lor q$

$\equiv q \lor (p \land T)$

$\equiv (q \lor p) \land (q \lor T)$

$\equiv (q \lor p) \land T$

$\equiv (q \lor p) \land (\neg p \lor q)$

I know that by drawing a venn-diagram here i can intuitively know that it is equivalent to q, but how do I draw such conclusion logically?

$\endgroup$
  • 1
    $\begingroup$ 1. What is $\equiv$? $\endgroup$ – Kenny Lau Jun 27 '16 at 13:34
  • 1
    $\begingroup$ 2. A proof by a truth table is a formal proof. $\endgroup$ – Kenny Lau Jun 27 '16 at 13:34
  • $\begingroup$ @KennyLau I think by "logically," they mean using logical laws like modus ponens, material implication, De Morgan's Laws, etc.. Also, $\equiv$ means "logically equivalent." $\endgroup$ – Noble Mushtak Jun 27 '16 at 13:36
  • $\begingroup$ ≡ is logical equivalence $\endgroup$ – MJAY Jun 27 '16 at 13:36
  • $\begingroup$ Yes, that's what I meant. using logical laws like p∨c≡p, p∧t≡p and others. $\endgroup$ – MJAY Jun 27 '16 at 13:37
2
$\begingroup$

$(p\lor q)↔q$

$=((p\lor q)→q)\land((p\lor q)←q)$

$=(\overline{(p\lor q)}\lor q)\land((p\lor q)\lor \overline {q})$

$=((\overline{p}\land \overline{q})\lor q)\land(p\lor (q\lor \overline {q}))$

$=((\overline{p}\land \overline{q})\lor q)\land(p\lor T)$

$=((\overline{p}\land \overline{q})\lor q)\land T$

$=((\overline{p}\land \overline{q})\lor q)$

$=(\overline{p}\lor q)\land (\overline{q}\lor q)$

$=(\overline{p}\lor q)\land T$

$=(\overline{p}\lor q)$

$=(p→q)$

$\endgroup$
1
$\begingroup$

You got this far: $$p \vee q \equiv (\sim p \vee q) \wedge (p \vee q)$$ Use distributivity: $$p \vee q \equiv (\sim p \wedge p) \vee q$$ By Law of Contradiction, we know that the former part of this disjunction is always false, so using disjunctive syllogism we can conclude: $$p \vee q \equiv q$$

$\endgroup$
  • $\begingroup$ Thanks! never thought I could use such method. $\endgroup$ – MJAY Jun 27 '16 at 13:46
  • $\begingroup$ Could you please approach this problem in another way? $\endgroup$ – MJAY Jun 27 '16 at 13:46
  • $\begingroup$ This is how far i came up to: pVq ≡(p∧t)Vq ≡qV(p∧t) ≡(qVp)∧(qVt) ≡(qVp)∧t ≡(qVp)∧(~pVq) $\endgroup$ – MJAY Jun 27 '16 at 13:46
  • $\begingroup$ How do I draw q from there? any methods I could make use of? $\endgroup$ – MJAY Jun 27 '16 at 13:47
  • $\begingroup$ @MJAY I am confused about your first step: $$p \vee q \equiv (p \wedge t) \vee q$$ This is not true if we make $p$ true, $q$ false, and $t$ false. $\endgroup$ – Noble Mushtak Jun 27 '16 at 13:48
0
$\begingroup$

so we must prove: $(p\Rightarrow q)\Leftrightarrow [(p\vee q)\Leftrightarrow q)]$.

suppose $(p\Rightarrow q)$ and prove the equivalence $(p\vee q)\Leftrightarrow q$

$\Rightarrow$): $ (p\Rightarrow q)\Rightarrow[ (p\Rightarrow q) \wedge (q\Rightarrow q)] \Rightarrow [(p\vee q)\Rightarrow q]$.

$\Leftarrow$): $q\Rightarrow(p\vee q)$ obvious

suppose $(p\vee q)\Leftrightarrow q$ and prove that $p\Rightarrow q$

so $[(p\vee q)\Leftrightarrow q)]\Rightarrow [(p\vee q)\Rightarrow q)]\Rightarrow [(p\Rightarrow q)\wedge (q\Rightarrow q)]\Rightarrow (p\Rightarrow q)$.

$\endgroup$
0
$\begingroup$

One way to prove that the statements $p \rightarrow q$ and $p \vee q \iff q$ are logically equivalent is as follows. It suffices to show that their truth tables (which have $4$ rows each) are the same. Recall that the only assignment of truth values for $p$ and $q$ for which $p \rightarrow q$ evaluates to $F$ is when $p$ is $T$ and $q$ is $F$. For which truth values does $p \vee q \iff q$ evaluate to $F$? Precisely when $p \vee q$ and $q$ have different truth values. If $q$ is $T$, so is $p \vee q$. If $q$ is $F$, the only way for $p \vee q$ to be $T$ is if $p$ is $T$. So, the only truth values for which $p \vee q \iff q$ is $F$ is when $p$ is $T$ and $q$ is $F$. This truth table is the same as that of $p \rightarrow q$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.