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$
6
  • 1
    $\begingroup$ 1. What is $\equiv$? $\endgroup$
    – Kenny Lau
    Jun 27, 2016 at 13:34
  • 1
    $\begingroup$ 2. A proof by a truth table is a formal proof. $\endgroup$
    – Kenny Lau
    Jun 27, 2016 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$ Jun 27, 2016 at 13:36
  • $\begingroup$ ≡ is logical equivalence $\endgroup$
    – user350509
    Jun 27, 2016 at 13:36
  • $\begingroup$ Yes, that's what I meant. using logical laws like p∨c≡p, p∧t≡p and others. $\endgroup$
    – user350509
    Jun 27, 2016 at 13:37

4 Answers 4

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$
12
  • $\begingroup$ Thanks! never thought I could use such method. $\endgroup$
    – user350509
    Jun 27, 2016 at 13:46
  • $\begingroup$ Could you please approach this problem in another way? $\endgroup$
    – user350509
    Jun 27, 2016 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$
    – user350509
    Jun 27, 2016 at 13:46
  • $\begingroup$ How do I draw q from there? any methods I could make use of? $\endgroup$
    – user350509
    Jun 27, 2016 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$ Jun 27, 2016 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$

You must log in to answer this question.