Notation

Let p, q, and r be logical statements below and let A, B, C, E, and F all be subsets of a set S.

Logic

Truth Tables

 p \sim \! p T F F T
 p q p \land q p \lor q p \to q p \leftrightarrow q T T T T T T T F F T F F F T F T T F F F F F T T

Equivalent Statements

definition Two statements p and q are said to be equivalent, denoted p \equiv q, if the statement p \leftrightarrow q is a tautology.

The following equivalent statements are important to know:

• Commutative Law for Statements
• p \lor q \equiv q \lor p

• p \land q \equiv p \land q

• Associative Law for Statements
• (p \lor q) \lor r \equiv p \lor (q \lor r)

• (p \land q) \land r \equiv p \land (q \land r)

• Distributive Law for Statements
• p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)

• p \land (q \lor r) \equiv (p \land q) \lor (p \land r)

• p \land (q \land r) \equiv (p \land q) \land (p \land r)

• p \lor (q \lor r) \equiv (p \lor q) \lor (p \lor r)

• DeMorgan's Laws for Statements

• \sim \! (p \lor q) \equiv \sim \! p \, \land \sim \! q

• \sim \! (p \land q) \equiv \sim \! p \, \lor \sim \! q

• Absorption Laws for Statements
• (p \land q) \lor p \equiv p

• (p \lor q) \land p \equiv p

• Conditional as "or"
• p \rightarrow q \equiv \sim \! p \lor q

Arguments

Four valid arguments that are important to know:

• Modus Ponens
    \begin{tabular}{l}
$p \to q$\\
$p$\\
\hline
$q$
\end{tabular}
• Modus Tollens
    \begin{tabular}{l}
$p \to q$\\
$\sim \! q$\\
\hline
$\sim \! p$
\end{tabular}
• Disjunctive Syllogism
    \begin{tabular}{l}
$p \lor q$\\
$\sim \! p$\\
\hline
$q$
\end{tabular}
• Reasoning by Transitivity
    \begin{tabular}{l}
$p \to q$\\
$q \to r$\\
\hline
$p \to r$
\end{tabular}

Sets

definition A is said to be a subset of B, denoted A \subseteq B, if the logical statement x \in A \to x \in B is a tautology.

definition The intersection of A and B, denoted A \cap B, is equal to the set \{x \in S | x \in A \land x \in B\}.

definition The union of A and B, denoted A \cup B, is equal to the set \{x \in S | x \in A \lor x \in B\}.

definition The complement of A with respect to S, denoted A', is equal to the set \{x \in S | x \not \in A\}.

definition Two sets A and B are said to be disjoint if A \cap B = \emptyset.

Set Laws

The following equalities of sets are important to know:

• Commutative Law for Sets
• A \cup B = B \cup A

• A \cap B = A \cap B

• Associative Law for Sets
• (A \cup B) \cup C = A \cup (B \cup C)

• (A \cap B) \cap C = A \cap (B \cap C)

• Distributive Law for Sets
• A \cup (B \cap C) = (A \cup B) \cap (A \cup C)

• A \cap (B \cup C) = (A \cap B) \cup (A \cap C)

• A \cap (B \cap C) = (A \cap B) \cap (A \cap C)

• A \cup (B \cup C) = (A \cup B) \cup (A \cup C)

• DeMorgan's Laws for Sets

• (A \cup B)' = A' \cap B'

• (A \cap B)' = A' \cup B'

• Absorption Laws for Sets
• (A \cap B) \cup A = A

• (A \cup B) \cap A = A

Probability

Basic Probability

definition A probability measure, P, on a set S is a function P: 2^S \rightarrow [0,1] such that:

1. P(\emptyset) = 0

2. P(S) = 1

3. If A and B are disjoint, then P(A \cup B) = P(A) + P(B).

P(E \cup F) + P(E \cap F) = P(E) + P(F)
Complement Rule The Complement Rule for Probability is
P(E) + P(E') = 1
Partition Rule 1 The Partition Rule 1 is
P(E \cup F) = P(E) + P(E' \cap F)
Partition Rule 2 The Partition Rule 2 is
P(E) = P(E \cap F) + P(E \cap F')

Conditional Probability

definition The conditional probability of E given F provided P(F) \neq 0 is:

P(E|F) = \frac{P(E \cap F)}{P(F)}

Product Rule The Product Rule for Probability is

P(E \cap F) = P(E|F) \cdot P(F) = P(F|E) \cdot P(E)

definition Two events E and F are said to be independent if any of the following equivalent conditions are true:

1. P(E|F) = P(E)

2. P(F|E) = P(F)

3. P(E \cap F) = P(E) \cdot P(F)