2
$\begingroup$

I am trying to prove this theorem : $((p ⇒ ¬ r) ∧ (s ∧ r ≡ ¬ q) ≢ ¬ ((r ⇒ ¬ s) ≡ q) ⇒ r ∧ p) ≡ p ∧ (p ⇒ r)$, but I am not sure where to start.

$$((p ⇒ ¬ r) ∧ (s ∧ r ≡ ¬ q) ≢ ¬ ((r ⇒ ¬ s) ≡ q) ⇒ r ∧ p)$$ $$= ⟨ \text{Definition of ≢ with } p, q ≔ (p ⇒ ¬ r) ∧ (s ∧ r ≡ ¬ q), ¬ (r ⇒ ¬ s ≡ q) ⇒ r ∧ p) ⟩$$ $$¬ ((p ⇒ ¬ r) ∧ (s ∧ r ≡ ¬ q) ≡ ¬ ((r ⇒ ¬ s) ≡ q) ⇒ r ∧ p)$$

Can you give me a hint how to continue? I am interested in a proof using logical laws instead a truth table.

$\endgroup$
9
  • $\begingroup$ You could just write out a truth table with 32 rows ... $\endgroup$ Mar 8 '21 at 23:50
  • $\begingroup$ I don't want to use a truth table, but logic laws instead $\endgroup$
    – Leo
    Mar 8 '21 at 23:54
  • $\begingroup$ Ah ... so you're not looking for a proof, but for a particular KIND of proof. Glad I didn't bother writing out an answer. I see you're new here, so let me offer a hint: ask exactly the question that interests you (not the one you think might be closely related), and be sure to say what kind of answer you're looking for. Otherwise you end up wasting the time of the people who are helping out, and that's not nice. $\endgroup$ Mar 8 '21 at 23:58
  • $\begingroup$ So...you want logic laws. What deductive system are you using? I'd hate to use some law and have you say "But that's not one of the ones I want to see used!" or "That one's not allowed in my deductive system!" $\endgroup$ Mar 8 '21 at 23:59
  • 1
    $\begingroup$ @ user400188 true, but this isn't at all my niche, so I defer to others. OP might benefit from knowing that truth tables are a highly systematic application of logic laws (in most deductive systems, I guess), but I'm probably not the one to explain that. $\endgroup$ Mar 9 '21 at 11:08
1
$\begingroup$

Using material implication we can replace $(p \Rightarrow \lnot r)$ by $(\lnot p \lor \lnot r)$. Using the Morgan's law we can then replace it by $\lnot (p\land r)$.

Using material implication we can replace $(r \Rightarrow \lnot s)$ by $(\lnot r \lor \lnot s)$. Using the Morgan's law we can then replace it by $\lnot (r\land s)$. Using commutativity of conjuction, we can then replace it by $\lnot (s\land r)$

We have an expression $(\lnot (s\land r) \equiv q)$. It can be replaced by $((s\land r) \equiv \lnot q)$.

We have an expression $\lnot((s\land r) \equiv \lnot q) \Rightarrow (r \land p)$. Using material implication it can be replaced by $\lnot\lnot((s\land r) \equiv \lnot q) \lor (r \land p)$. Using double negation it can be replaced by $((s\land r) \equiv \lnot q) \lor (r \land p)$. Using commutativity of conjuction, we can then replace it by $((s\land r) \equiv \lnot q) \lor (p \land r)$.

We have an expression $$ (\lnot (p \land r) \land ((s\land r) \equiv \lnot q)) ≢ ((s\land r) \equiv \lnot q) \lor (p \land r) $$ which is of the form $ (\lnot x \land y) ≢ (y \lor x)$ where $x = p\land r$, $y = (s\land r) \equiv \lnot q$. By the definition of $≢$, it can be replaced by $$ \big((\lnot x \land y) \land \lnot(y \lor x)\big) \lor \big(\lnot(\lnot x \land y) \land (y \lor x)\big)$$ Using de Morgan's laws it can be replaced by $$ \big((\lnot x \land y) \land (\lnot y \land \lnot x)\big) \lor \big((\lnot\lnot x \lor \lnot y) \land (y \lor x)\big)$$

Using assosciativity of conjugation, $(\lnot x \land y) \land (\lnot y \land \lnot x)$ can be replaced by $\lnot x \land (y \land \lnot y) \land \lnot x$, which is a conjuction that includes a alwayys false expression $y \land \lnot y$. Therefore, this whole expression can be replaced by ${\bf 0}$. Using double negation, $\lnot\lnot x$ can be replaced by $x$ so we get $$ {\bf 0} \lor \big((x \lor \lnot y) \land (y \lor x)\big)$$ which can be replaced by $$ (x \lor \lnot y) \land (y \lor x)$$ $$ (x \lor \lnot y) \land (x \lor y)$$ $$ x \lor (\lnot y \land y)$$ $$ x \lor {\bf 0}$$ $$ x$$ In this way, the whole expression is now $$ x \equiv p \land (p \Rightarrow r)$$ that is $$ p \land r \equiv p \land (p \Rightarrow r)$$ I'll leave proving that to you, it should be simple enough.

$\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.