We can do this using propositional logic. With some mild short-cuts for brevity, we have:
1. Assume: (p ∨ ¬q) ∧ (¬p ∨ ¬q)
2. Conclude: p ∨ ¬q (from 1)
3. Conclude: ¬p ∨ ¬q (from 1)
4. Suppose p:
5. Conclude ¬q (from 2,4)
6. Conclude p → ¬q (from 4-5)
7. Conclude ¬q ∨ ¬q (from 2, 6)
8. Conclude ¬q (from 7)
I'll note that it is common to conclude 6 directly from 2.
So, this shows that
((p ∨ ¬q) ∧ (¬p ∨ ¬q)) → ¬q . However, now we have to ask: Does it show anything else? Let's apply basic substitution to check:
(p ∨ ¬q) ∧ (¬p ∨ ¬q)
(p ∨ ⊤) ∧ (¬p ∨ ⊤) (We know ¬q, so we can learn nothing further about q. Replace ¬q with T.
⊤ ∧ T (Anything ∨ T) is always true, regardless of the value anything. So that tells us nothing.
So, we can now conclude:
p ∨ ¬p (This is a tautology due to law of excluded middle, so it can remain unstated)
An even simpler proof would be proof by contradiction (i.e., assume q, then get
(p) ∧ (¬p)). This is the approach taken by J.G.