Section 1.2 Useful Logic for Constructing Proofs
A statement is a declarative sentence that is either true or false but not both. A compound statement is a statement that contains one or more operators. Because some operators are used so frequently in logic and mathematics, we give them names and use special symbols to represent them.
The conjunction of the statements \(P\) and \(Q\) is the statement “\(P\) and \(Q\)” and its denoted by \(P \wedge Q\) . The statement \(P \wedge Q\) is true only when both \(P\) and \(Q\) are true only when both \(P\) and \(Q\) are true.
The disjunction of the statements \(P\) and \(Q\) is the statement “\(P\) or \(Q\)” and its denoted by \(P \vee Q\text{.}\) The statement \(P \vee Q\) is true only when at least one of \(P\) or \(Q\) is true.
The negation (of a statement) of the statement \(P\) is the statement “not \(P\)” and is denoted by \(\neg P\) . The negation of \(P\) is true only when \(P\) is false, and \(\neg P\) is false only when \(P\) is true.
The implication or conditional is the statement “If \(P\) then \(Q\)” and is denoted by \(P \to Q\text{.}\) The statement \(P \to Q\) is often read as “\(P\) implies \(Q\)”. The statement \(P to Q\) is false only when \(P\) is true and \(Q\) is false.
The biconditional statement is the statement “\(P\) if and only if \(Q\)” and is denoted by \(P \leftrightarrow Q\text{.}\) The statement \(P \leftrightarrow Q\) is true only when both \(P\) and \(Q\) have the same truth values.
Definition.
Two expressions \(X\) and \(Y\) are logically equivalent provided that they have the same truth value for all possible combinations of truth values for all variables appearing in the two expressions. In this case, we write \(X \equiv Y\) and say that \(X\) and \(Y\) are logically equivalent.
Theorem 1.1 states some of the most frequently used logical equivalencies used when writing mathematical proofs.
Theorem 1.1.
For statements \(P\text{,}\) \(Q\text{,}\) and \(R\text{,}\)
- De Morgan's Laws
-
\(\neg \left( P \wedge Q \right) \equiv \neg P \vee \neg Q\)
\(\neg \left( P \vee Q \right) \equiv \neg P \wedge \neg Q\)
- Conditional Statements
-
\(P \to Q \equiv \neg Q \to \neg P \text{ (contrapositive)}\)
\(P \to Q \equiv \neg P \vee Q\)
\(\neg \left( P \to Q \right) \equiv P \wedge \neg Q\)
- Biconditional Statement
\(\displaystyle \left( P \leftrightarrow Q \right) \equiv \left( P \to Q \right) \wedge \left( Q \to P \right)\)
- Double Negation
\(\displaystyle \neg \left( \neg P \right) \equiv P\)
- Distributive Laws
-
\(P \vee \left( Q \wedge R \right) \equiv \left( P \vee Q \right) \wedge \left( P \vee R \right)\)
\(P \wedge \left( Q \vee R \right) \equiv \left( P \wedge Q \right) \vee \left( P \wedge R \right)\)
- Conditionals with Disjunctions
-
\(P \to \left( Q \vee R \right) \equiv \left( P \vee \neg Q \right) \to R\)
\(\left( P \wedge \neg Q \right) \to R \equiv \left( P \to R \right) \wedge \left( Q \to R \right)\)
Definition.
The phrase “for every” (or its equivalents) is called a universal quantifier. The phrase “there exists” (or its equivalents) is called an existential quantifier. The symbol \(\forall\) is used to denote a universal quantifier, and the symbol \(\exists\) is used to denote an existential quantifier.
Theorem 1.2.
For any open sentence \(P (x)\text{,}\)