For any statement p and q show that: (~p v q) v (p ^ ~ q) is a tautology.
Answers
Two (molecular) statements P and Q are logically equivalent provided P is true precisely when Q is true. That is, P and Q have the same truth value under any assignment of truth values to their atomic parts.
Answer:
2.1. Tautology/Contradiction/Contingency.
Definition 2.1.1. A tautology is a proposition that is always true.
Example 2.1.1. p ∨ ¬p
Definition 2.1.2. A contradiction is a proposition that is always false.
Example 2.1.2. p ∧ ¬p
Definition 2.1.3. A contingency is a proposition that is neither a tautology
nor a contradiction.
Example 2.1.3. p ∨ q → ¬r
Discussion
One of the important techniques used in proving theorems is to replace, or sub-
stitute, one proposition by another one that is equivalent to it. In this section we will
list some of the basic propositional equivalences and show how they can be used to
prove other equivalences.
Let us look at the classic example of a tautology, p ∨ ¬p. The truth table
p ¬p p ∨ ¬p
T F T
F T T
shows that p ∨ ¬p is true no matter the truth value of p.
[Side Note. This tautology, called the law of excluded middle, is a
direct consequence of our basic assumption that a proposition is a
statement that is either true or false. Thus, the logic we will discuss
here, so-called Aristotelian logic, might be described as a “2-valued”
logic, and it is the logical basis for most of the theory of modern
mathematics, at least as it has developed in western culture. There
is, however, a consistent logical system, known as constructivist,
or intuitionistic, logic which does not assume the law of excluded
middle. This results in a 3-valued logic in which one allows fo