0
$\begingroup$

I just began logic and proofs there is a proof in the midterm of $2019$ that I could not do.

Here is the statement :

$p \vee [(\neg p \vee \neg q) \vee (p \vee q)] \iff \top.$

I started using Distributive Laws and got a really long mess. I thought maybe if I developed maybe I'd use De Morgan's law or Absorption Laws but none really came up.

Any HELP would be a lot appreciated ( I'm not looking for a full answer but maybe going step by step )

$\endgroup$
3
  • $\begingroup$ what are you using the distributive law for? there is nothing to distribute over, all are disjunctions $\endgroup$
    – Physor
    Sep 24 '20 at 17:27
  • 2
    $\begingroup$ Since there are only two primitives, $p$ and $q$, perhaps it would be easiest to just write out a truth table? $\endgroup$
    – Gteal
    Sep 24 '20 at 17:28
  • 1
    $\begingroup$ No Distributive Law needed: disjunction is associative. $\endgroup$ Sep 24 '20 at 18:40
0
$\begingroup$

Let $p$ and $q$ be propositions, and consider the expression $$p \vee [(\neg p \vee \neg q) \vee (p \vee q)].$$

Applying the Associative Law, we have that

$$p \vee [(\neg p \vee \neg q) \vee (p \vee q)] \iff [p \vee (\neg p \vee \neg q)] \vee (p \vee q).$$

Applying once more the same rule yields

$$[p \vee (\neg p \vee \neg q)] \vee (p \vee q) \iff [(p \vee \neg p) \vee \neg q] \vee (p \vee q).$$

Note that $p \vee \neg p$ is a tautology. So $p \vee \neg p \iff \top.$ So

$$[(p \vee \neg p) \vee \neg q] \vee (p \vee q) \iff [\top \vee \neg q] \vee (p \vee q).$$

Since $\top$ is a tautology, the disjunction on any proposition with $\top$ will be always true, and hence a tautology. So

$$[\top \vee \neg q] \vee (p \vee q) \iff \top \vee (p \vee q) \iff \top.$$

$\square$

$\endgroup$
2
  • 1
    $\begingroup$ I think it's Associative Law $\endgroup$
    – user824627
    Sep 29 '20 at 5:41
  • $\begingroup$ @SteveMorris well done! Thank you for correcting me, I really appreciate it! $\endgroup$
    – Air Mike
    Sep 29 '20 at 12:12

Your Answer

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