-2

I've been having difficulty figuring out this problem: ¬p∨(p∧q) = p→q

If I use distribution law, I'm stuck with (¬p∨p)∧(¬p∨q) and can't use idempotent law.

If I use conditional Law, I get p→(p∧q) and am stuck.

Edit: we need to only use the following laws without a truth table: Idempotent, commutative, complement, identity, associative, demorgan's, contraposition, conditional, biconditional and distributive law.

cherrykookie
  • 1
  • 1
    How about using a truth table? – JDZ Jun 08 '17 at 04:12
  • 1
    If you can't use a truth table (which is the easiest -- meaning least amount of brain power -- method) then can you list all of the laws you've got? –  Jun 08 '17 at 04:15

2 Answers2

0

Suppose $\neg p \vee (p\wedge q)$.

Case 1: Suppose $\neg p$. Then $p\to q$ is true.

Case 2: Now suppose $p\wedge q$. Then $q$ is true and therefore $p\to q$.

Hence $p\to q$ is true.

Conversely suppose $p\to q$. Then either $p\vee\neg p$. If $p$ is true then $q$ is true, otherwise $p\to q$ would be false; therefore $p\wedge q$ is true. Thus in either case $\neg p\vee(p\wedge q)$ is true.

Now the proof is complete.

P.S. You should always use truth table technique if you are stuck.

$\neg p \vee (p\wedge q)\equiv (\neg p\vee p)\wedge (\neg p\vee q)\equiv \neg p\vee q\equiv p\to q$.

Janitha357
  • 3,049
  • 1
    Another way of explaining the forward direction might be that we either have $\lnot p$ or $p\land q$, so if $\lnot q$, then as we can't have $p\land q$, we have $\lnot p$, so $\lnot q\to \lnot p$, and the contrapositive of this is $p\to q$. – Michael L. Jun 08 '17 at 04:27
  • How did you get (¬p∨p)∧(¬p∨q)≡¬p∨q? Doesn't it have to be (¬p∨q)∧(¬p∨q) for it to ≡¬p∨q? We are suppose to use idempotent, commutative, complement, identity, associative, demorgan's, contraposition, conditional, biconditional and distributive laws without truth tables to prove logical equivalence. – cherrykookie Jun 08 '17 at 04:34
  • $\neg p\vee p$ is a tautology. So for the compound statement $(\neg p\vee p)\wedge (\neg p \vee q) $ to be true $(\neg p \vee q) $ must be true, and the opposite direction also holds. – Janitha357 Jun 08 '17 at 04:40
0

Making some educated guesses about what those laws you list actually mean, try this: $$\begin{align*}\neg p\vee(p\wedge q) &\equiv (\neg p \vee p)\wedge (\neg p\vee q) &\text{Distributive Law} \\ &\equiv T\wedge (\neg p\vee q)&\text{Complement Law} \\ &\equiv \neg p\vee q &\text{Identity Law} \\ &\equiv p\rightarrow q &\text{Conditional Law}\end{align*}$$