Math & Comp Sci: Symbolic Logic: contradiction

The tutor defines, in the context of symbolic logic, contradiction, with a couple of examples.

For those new to symbolic logic, my previous post leads back to others that will fill the gaps.

A contradiction is a compound statement that is always false. The fundamental example is p ∧ ¬ p, which must be a contradiction, since both p and “not p” can’t be true simultaneously.

Here is a second contradiction:

(p ⊻ q) ∧ (p ∧ q)

p ⊻ q is only true when one of p,q is true, but not both. However, both p,q must be true for p ∧ q to be. Therefore, the bracketed statements can’t be true simultaneously, meaning that the central “and” will always be false.

Source:

Grimaldi, Ralph P. Discrete and Combinatorial Mathematics. Don Mills: Addison-
  Wesley, 1994.

Jack of Oracle Tutoring by Jack and Diane, Campbell River, BC.

Tagged with: ,

Leave a Reply