2

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.

Leo
  • 97
  • You could just write out a truth table with 32 rows ... – John Hughes Mar 08 '21 at 23:50
  • I don't want to use a truth table, but logic laws instead – Leo Mar 08 '21 at 23:54
  • 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. – John Hughes Mar 08 '21 at 23:58
  • 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!" – John Hughes Mar 08 '21 at 23:59
  • I am using monotonic, absorption, idempotence, commutativity, associativity, ... laws. There are a lot of law I can use. – Leo Mar 09 '21 at 00:06
  • @JohnHughes since they are asking for a hint, it probably wont matter if you use different laws, since an answer in a different deductive system will probably be a sufficient hint (so long as it's natural deduction). – user400188 Mar 09 '21 at 10:00
  • 1
    @ 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. – John Hughes Mar 09 '21 at 11:08
  • You need to put additional brackets to make the ekspression clear. For example, does $$ r \Rightarrow \lnot s \equiv q$$ mean $$ (r \Rightarrow \lnot s) \equiv q,$$ $$ r \Rightarrow ((\lnot s) \equiv q),$$ or $$ r \Rightarrow \lnot (s \equiv q)$$? There are also other places where the expresson is unclear. – Adam Latosiński Mar 09 '21 at 14:55
  • @AdamLatosiński I changed it. It is just because for me the right arrow is prioritised over the equivalence. – Leo Mar 09 '21 at 15:00

1 Answers1

1

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.

Adam Latosiński
  • 10,558