QuickReference.md

MATH 122 Quick Reference

Statements

Conjunction

Let $p$ and $q$ be statements. The conjunction of $p$ and $q$ is written:

$$ p \wedge q $$

Truth Table

$p$	$q$	$p \wedge q$
True	True	True
True	False	False
False	True	False
False	False	False

Disjunction

Let $p$ and $q$ be statements. The disjunction¹ of $p$ and $q$ is written:

$$ p \vee q $$

Truth Table

$p$	$q$	$p \vee q$
True	True	True
True	False	True
False	True	True
False	False	False

Implication

Let $p$ and $q$ be statements. The implication of $p$ to $q$ is written:

$$ p \rightarrow q $$

This implies a if p then q relationship.

Truth Table

$p$	$q$	$p \rightarrow q$
True	True	True
True	False	False
False	True	True
False	False	True

Bicondition or Double Implication

• Means $p \to q$ and $q \to p$
• $p$ and $q$ have the same truth value

$p$	$q$	$p \leftrightarrow q$
True	True	True
True	False	False
False	True	False
False	False	True

Said as "$p$ if and only if $q$" or "$p$ iff $q$"

Negation

definition: The negation of a statement $p$, written:

$$ \neg p $$

$p$	$\neg p$
True	False
False	True

Notation: $\neg$ supersedes any other notation. So:

$$ \neg p \vee q = (\neg p) \vee q $$

Contrapositive

definition: The contrapositive of $p \to q$ is written:

$$ \neg q ~ \to ~ \neg p $$

Converse

definition: The converse[^f1] of $p \to q$ is written:

$$ q \to p $$

Quantifiers

Universal Quantifier

"For all integers $n$, $2n$ is even".

For all is the quantifier as it quantifies the amount. In this case it is the universal quantifier equivalent to:

• For all... (duh)
• For each...
• For every...
• $\forall$

Existential Quantifier

definition: The existential quantifier states that this statement applies for some but not all things. It can be written:

• For some...
• There exists a...
• $\exists$

Laws of Logic

Idempotence

$$ p \vee p \iff p $$ $$ p \wedge p \iff p $$

Commutative

$$ p \vee q \iff q \vee p $$ $$ p \wedge q \iff q \wedge p $$

Associative

$$ (p \vee q) \vee r \iff p \vee (q \vee r) $$ $$ (p \wedge q) \wedge r \iff p \wedge (q \wedge r) $$

Note,

$$ (p \wedge q) \vee r \nLeftrightarrow p \wedge (q \vee r) $$

Distributive

$$ p \wedge (q \vee r) \iff (p \wedge q) \vee (p \wedge r) $$ $$ p \vee (q \wedge r) \iff (p \vee q) \wedge (p \vee r) $$

DeMorgan's Laws

$$ \neg ( p \wedge q ) = (\neg p) \vee (\neg q) $$

$$ \neg ( p \vee q ) = (\neg p) \wedge (\neg q) $$

Identity

$$ p \wedge \mathbb{1} \iff p $$ $$ p \vee \mathbb{0} \iff p $$

Dominance

$$ p \wedge \mathbb{0} \iff \mathbb{0} $$ $$ p \vee \mathbb{1} \iff \mathbb{1} $$

Other

$$ p \to q \iff \neg p \vee q $$ $$ \neg p \to q \iff p \vee q $$ $$ p \leftrightarrow q \iff (p \to q) \wedge (q \to p) \iff (\neg p \vee q) \wedge (p \vee \neg q ) $$

Proofs

Direct Proof

To show $ p \to q $, assume $p$ is true, then use known results (e.g. facts, logical equivalents) to show that $q$ is also true.

Proof by Contrapositive

Assume that $\neg q$ is true, then use known result to prove that $\neg p$ is true.

Recall
The contrapositive of $p \to q$ is $\neg q \to \neg p$.

Proof by Contradiction

To show $p \to q$ assume that $p$ and $\neg q$ are true. Then, using known results, arrive at some contradiction.

Show it's impossible for $\neg q$ to be true, and therefore for $q$ is true.

Sets

Properties

Equality

definition: Sets $A$ and $B$ are equal ($A = B$) if they have the same elements. That is,

$$ x \in A \iff x \in B $$

or

$$ A = B \iff A \subseteq B \wedge B \subseteq A $$

Other

• Any set $S$ has $S \subseteq S$.
• Any set $S$ has $\varnothing \subseteq S$.
• An $n$ element set has $2^n$ subsets.

Note:

• Sets are unordered,

$$ { 1,2,3 } = { 3,1,2 } $$

• Unless specified repeated elements are ignored,

$$ { 1,2,2,3,3,3 } = { 1,2,3 } $$

Subsets

definition: Let $A$ and $B$ be sets. $A$ is a subset of $B$ ($A \subseteq B$) if every element in $A$ is also in $B$ (but not necessarily the reverse). That is $x \in A \Rightarrow x \in B$.

• If $A$ is not a subset of $B$ we write $A \not\subseteq B$
• If $A$ is only a subset of $B$ ($A \neq B$), we call is a proper subset we write $A \subsetneq B$.

Special Sets

Empty Set

definition: The empty set is the set with no elements written, $\varnothing$ or ${}$.

Universe

definition: The universe is all the objects that can occur in the set. Written,

$$ \mathcal U $$

Power Sets

defnition: The power set of a set $A$ (denoted $\mathcal{P}(A)$) is the set whose elements are the subsets of $A$.

Let $A = { a, b, }$.

$$ \mathcal{P}(A) = {{ a }, { b }, { a, b }, \varnothing } $$

Properties

Let $\mathcal{P}(A)$ be a power set of $A$.

• Every element of $\mathcal{P}(A)$ is a set.
• If $A$ has $n$ elements, $\mathcal{P}(A)$ has $2^n$ elements.
• $\varnothing \in \mathcal{P}(A)$
• $A \in \mathcal{P}(A)$
• $X \in \mathcal{P}(A) \iff X \subseteq A$
• $A \subseteq B \iff \mathcal{P}(A) \subseteq \mathcal{P}(B)$

Operations

Union

definition: Let $A$ and $B$ be sets. The union of $A$ and $B$ (denoted $A \cup B$) is the set,

$$ A \cup B = { x : x \in A \vee x \in B } $$

Intersection

defninition: The intersection of $A$ and $B$ (denoted $A \cap B$) is the set,

$$ A \cap B = { x : x \in A \wedge x \in B } $$

Set Difference

$$ A \setminus B = B \cap A^C $$

Symmetric Difference

$$ A \oplus B = B \oplus A $$

Compliment

$$ A^C = \mathcal U \setminus A $$

Cartesian Product

definition: The cartesian product of $A$ and $B$ is,

$$ A \times B = { (a,b): a \in A, b \in B } $$

Note:

In ordered pairs,

$$ (a,b) \neq (b,a) $$

Example

$$ A = { 1,2 } $$ $$ B = { x,y,z } $$

Solution

$$ A \times B = { (1,x), (1,y), (1,z), (2,x), (2,y), (2,z) } $$ $$ B \times A = { (x,1), (x,2), (y,1), (y,2), (z,1), (z,2) } $$

Relations

definition: A binary relation from a set $A$ to a set $B$ is a subset,

$$ \mathcal R \subseteq A \times B. $$

Note:

Binary refers to a relationship between 2 sets, and we will only consider binary relationships in this course.

Notation

When an ordered pair $(a,b)$ is in a relationship $\mathcal R$ we say "$a$ is related to $b$" and write $(a,b) \in \mathcal R$ or, using Infix notation,

$$ a \mathcal R b $$

Types

For a relation $\mathcal R_1$ on a $A \times A, \mathcal R$ is,

Reflexive

If $(x,x) \in \mathcal R$ for all $x \in A$.

Symmetric

If $(y,x) \in \mathcal R$ whenever $(x,y) \in \mathcal R$.

Antisymmetric

If $(x,y) \in \mathcal R$ and $(y,x) \in \mathcal R$ then $x = y$.

Note:

This is not the same as not symmetric (Antisymmetric $\not\Leftrightarrow$ not Symmetric ).

Transitive

If $(x,y) \in \mathcal R$ and $(y,z) \in \mathcal R$ then $(x,z) \in \mathcal R$.

Note:

It is possible for $x = z$.

Equivalence

definition: A relation $\mathcal R$ on a set $A$ is an equivalence relationship if it is,

1. Reflexive
2. Symmetric
3. Transitive

Footnotes

1. In mathematics or is always inclusive. ↩