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

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 )

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

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

• I think it's Associative Law
– user824627
Sep 29 '20 at 5:41
• @SteveMorris well done! Thank you for correcting me, I really appreciate it! Sep 29 '20 at 12:12