I used Chapter 1 in “Mathematical Proofs: A Transition to Advanced Mathematics” as the main resource for studying this topic.
Introduction
A formal system to express statements about objects, properties, relations, and if they are true or not.
Statements
A statement is a declarative sentence or assertion that has a truth value, meaning it is either true or false, but not both. The integer 3 is odd is an example of a statement. This statement has the truth value true ($T$).
Open Sentences
An open sentence is a declarative sentence that contains one or more variables. An open sentence becomes a statement when each variable is assigned a value from their respective domains. The integer n is odd is an example of an open sentence.
Truth Tables
A truth table lists all the possible truth values for a set of statements. Below is the truth table for two statements, $P$ and $Q$. Recall that a statement is either true or false.
| $P$ | $Q$ |
|---|---|
| T | T |
| T | F |
| F | T |
| F | F |
Operations on Statements
We can construct new statements (sometimes called compound statements) by applying operations (sometimes called logical connectives).
Negation
The negation of a statement $P$ is the new statement: not $P$. or ~$P$. or It is not the case that $P$.
The negation of a true statement is always false, and the negation of a false statement is always true. The truth table for negation is listed below.
| $P$ | ~$P$ |
|---|---|
| T | F |
| F | T |
Disjunction
For two statements $P$ and $Q$, the disjunction is the new statement: $P$ or $Q$. or $P \lor Q$.
The disjunction of the statements $P$ and $Q$ is true exactly when at least one of $P$ and $Q$ is true.
| $P$ | $Q$ | $P \lor Q$ |
|---|---|---|
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
Conjunction
For two statements $P$ and $Q$, the conjunction is the new statement: $P$ and $Q$. or $P \land Q$.
The conjunction of the statements $P$ and $Q$ is true exactly when both $P$ and $Q$ is true.
| $P$ | $Q$ | $P \land Q$ |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
Implication
For two statements $P$ and $Q$, the implication is the new statement: If $P$ then $Q$. or $P \rightarrow Q$. or $P$ implies $Q$.
The truth table for the implication is given below:
| $P$ | $Q$ | $P \rightarrow Q$ |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
The truth table for the implication is perhaps not as intuitive as the preceding operations. The implication is only false exactly when the premise ($P$) is true, but the conclusion ($Q$) is false. Even when the premise doesn’t hold, the implication is true. This is usefully illustrated with an example:
“If I win the lottery ($P$), I’ll buy you a car ($Q$)”. If I win the lottery and don’t buy you a car I have broken my promise, and the implication is false. However, if I don’t win the lottery, the implication makes no commitment, so it is considered true, regardless of whether I buy you a car or not.
Biconditional
For two statements $P$ and $Q$, the biconditional is the new statement: $(P \rightarrow Q) \land (Q \rightarrow P)$. or $P \leftrightarrow Q$. or $P$ if and only if $Q$. or $P$ is true exactly when $Q$ is true.
The biconditional is true when both implications are true. When the biconditional is true it therefore follows that the two statements are logically equivalent - they are both true, or they are both false. The truth table for the biconditional is given below:
| $P$ | $Q$ | $P \rightarrow Q$ | $Q \rightarrow P$ | $P \leftrightarrow Q$ |
|---|---|---|---|---|
| T | T | T | T | T |
| T | F | F | T | F |
| F | T | T | F | F |
| F | F | T | T | T |
Properties of Statements
Tautology
A tautology is a statement which is always true. For example, the statement $P \lor (\sim P)$ is intuitively always true.
Contradiction
A contradiction is a statement which is always false. For example, the statement $P \land (\sim P)$ is intuitively never true.
Logical Equivalence
Statements that have the exact same truth table are called logically equivalent. We sometimes use the symbol $\equiv$ to denote this fact.
For two statements $P$ and $Q$, $P \equiv Q$ if and only if $P \leftrightarrow Q$ is a tautology.
Laws
Disjunction and conjunction is both commutative and associative.
All operations are distributive, i.e: $P \lor (Q\ \land R)$ can be rewritten as $(P \lor Q) \land (P \lor R)$
De Morgan’s laws are logically equivalent, intuitive, and useful: $\sim (P \land Q) \equiv (\sim P) \lor (\sim Q)$
$\sim (P \lor Q) \equiv (\sim P) \land (\sim Q)$
Quantified Statements
Quantified statements uses qualifiers to assert how many elements of a domain a given open sentence applies to.
Universal Qualifier
The universal qualifier, $\forall$ states that a given open statements applies to all elements of the given domain. The universal quantifier is thus exactly true if the predicate ($P(x)$ in the case below) is true for every element of the given domain.
Given the open sentence $P(x) : x + 0 = x$, and the domain $x \in \mathbb{Z}$, we can write: $\forall x \in \mathbb{Z}, P(x)$ which states that for every $x$ in $\mathbb{Z}$, $P(x)$ is true.
An equivalent statement would be to write if $x \in \mathbb{Z}$, then $P(x)$.
Existential Qualifier
The existential qualifier, $\exists$ states that a given open statements applies to at least one element of the given domain. The existential quantifier is thus true if the predicate is true for at least one element of the given domain.