Terminology and Notation

Statement (or proposition)

A declarative sentence that is either true or false, but not both. Statements are typically denoted with the lowercase letters $p$, $q$, $r$, $s$, $t$.

Primitive statement

A statement which cannot be broken down to simpler statements.

Truth value

A value which is either true or false, but not both. Denoted either in plain text as true and false, with single letters "T" and "F", or as binary integers "1" (true) and "0" (false).

Negation

A transformation of a statement to its opposite truth value. The negation of the statement $p$ is denoted $\neg p$.

Compound statement

A combination of two or more statements using logical connectives.

Tautology

A compound statement is a tautology if it is true for all truth value assignments.

Contradiction

A compound statement is a contradiction if it is false for all truth value assignments.

Argument

An argument consists of two parts: a series of statements, called premises, and a single statement, called the conclusion. An argument can be either valid or invalid, but not both.

Examples of statements: $2 + 2 = 4$ (true), $\sqrt{16}$ is an odd number (false), $\frac{100}{5} > 10$ (true). The following are not statements: $x + 2 > 3$ (this is an open statement), "Does 3 divide 54?" (this is a question).

Logical Connectives

Conjunction

The conjunction of the statements $p$, $q$ is denoted by $p \land q$, which is read "$p$ and $q$". The conjunction of two statements is true only when both statements are true, and false otherwise.

Disjunction

The disjunction of the statements $p$, $q$ is denoted by $p \lor q$, which is read "$p$ or $q$". The disjunction of two statements is true if one or both statements are true, and false otherwise.

Exclusive "or"

The exclusive "or" is denoted by $p \veebar q$ or $p \oplus q$. The compound statement $p \veebar q$ is true if either $p$ or $q$ is true, but is false if both are true.

Implication

The implication of $q$ by $p$ is written $p \rightarrow q$, and we say that "$p$ implies $q$". In the compound statement $p \rightarrow q$, $p$ is called the hypothesis of the implication and $q$ is called the conclusion. Note: An implication does not signify any causal relationship between the statements. "$p$ implies $q$" is true when both $p$ and $q$ are true, is false when $p$ is true and $q$ is false, and is true when $p$ is false, regardless of the truth value of $q$ ("with a false hypothesis, anything can be proved to be true"). See table 1 for clarification.

Biconditional

The biconditional of two statements $p$, $q$ is denoted by $p \leftrightarrow q$, which is read "$p$ if and only if $q$" (often abbreviated "$p$ iff $q$"), or "$p$ is necessary and sufficient for $q$". The compound statement $p \leftrightarrow q$ is true if $p$ and $q$ have equal truth values.

Dual of a statement

If a statement $s$ contains no logical connectives other than $\land$ and $\lor$ (i.e. no implication, biconditional, exclusive "or"), then the dual of $s$, denoted $s^d$, is the statement obtained from $s$ by replacing each occurrence of $\land$ by $\lor$ and vice versa, and replacing each occurence of $T_0$ by $F_0$ and vice versa. Note that since $\neg$ is not a logical connective, $\neg p \equiv (\neg p)^d$.

Principle of duality

Let $s$ and $t$ be statements that contain no logical connectives other than $\land$ and $\lor$. If $s \equiv t$, then $s^d \equiv t^d$. In other words, if two statements are equivalent, then their duals are also equivalent.

Other ways to express "$p$ implies $q$" are:

• "If $p$, then $q$"
• "$p$ is sufficient for $q$"
• "$q$ is necessary for $p$"
• "$p$ only if $q$"

Truth Tables

The truth value of a compound statement depends only on the truth values of its components. The above definitions can be summarized by the following truth table (table 1). Note how $\neg p \lor q$ has the same truth values as $p \rightarrow q$, which means they are equivalent statements. Here we write "1" for true and "0" for false, but "T" and "F" may also be used in a truth table.

Using truth tables you can prove theese two theorems:

The Laws of Logic

Two statements $s_1$ and $s_2$ are said to be logically equivalent, and we write $s_1 \equiv s_2$ (or $s_1 \Leftrightarrow s_2$), when the statement $s_1$ is true (respectively, false) if and only if the statement $s_2$ is true (respectively, false). This is the same as saying that $s_1$ and $s_2$ provide the same truth tables.

The following table lists the laws for the algebra of propositions, or "The Laws of Logic", for any primitive statements $p$, $q$, $r$, any tautology $T_0$ and any contradiction $F_0$:

Contrapositive, Converse and Inverse

The implication $p \rightarrow q$ has three special related statements:

Contrapositive

$\neg q \rightarrow \neg p$ is the contrapositive of $p \rightarrow q$. The contrapositive of an implication is generated by negating both sides and having the hypothesis and the conclusion change places.

Converse

$q \rightarrow p$ is the converse of $p \rightarrow q$. The converse of an implication is generated by having the hypothesis and conclusion change places. (Think "converse = reverse", as in reversing the direction of the arrow.)

Inverse

$\neg p \rightarrow \neg q$ is the inverse of $p \rightarrow q$. The inverse of an implication is generated by negating both the hypothesis and conclusion, but they do not change places.

Note: It is only the contrapositive which is equivalent to the original implication. That is, $$p \rightarrow q \equiv \neg q \rightarrow \neg p,$$ but $$p \rightarrow q \not\equiv q \rightarrow p \,\, \mathrm{and} \,\, p \rightarrow q \not\equiv \neg p \rightarrow \neg q.$$

This can be observed in the following truth table.

Logical Implication

If $p \rightarrow q$ is a tautology (always true), then we say that "p logically implies q" and we write $p \Rightarrow q$. The notation $p \not\Rightarrow q$ is used to indicate that $p \rightarrow q$ is not a tautology, and so it is not a logical implication.

Open Statements

A declarative sentence is a open statement if

1. it contains one or more variables (e.g. $x$), and
2. it is not a statement, but
3. it becomes a statement when the variables in it are replaced by certain allowable choices.

These allowable choices constitute what is called the universe or universe of discourse for the open statement. The universe comprises the choices we wish to consider or allow for the variable(s) in the open statement.

An example of an open statement with a single variable: $$p(x)\!: \; \text{ The number } x + 2 \text{ is an even integer.}$$

An example of an open statement with two variables: $$q(x, y)\!: \; \text{ The numbers } y + 2, x - y \text{ and } x + 2y \text{ are even integers.}$$

Given a universe of integers, we can make the following true statements:

1. For some $x$, $p(x)$
2. For some $x$, $y$, $q(x, y)$

The phrases "For some x" are said to quantify the open statements $p(x)$ and $q(x, y)$, respectively. There are two kinds of quantifiers; the existential and the universal quantifiers.

Quantifiers

The existential quantifier

The existential quantifier is denoted by $\exists x$ and can be expressed as "For some $x$", "For at least one $x$", "There exists and $x$ such that". Thus, "For some $x$, $p(x)$" is written $\exists x \; p(x)$ in symbolic form. "For some $x$, $y$, $q(x, y)$" is written $\exists x \, \exists y \; q(x, y)$ in symbolic form, which can be abbreviated to $\exists x,y \; q(x, y)$.

The universal quantifier

The universal quanitifier is denoted by $\forall x$ and can be expressed as "For all $x$", "For any $x$", "For each $x$" or "For every $x$". Same as with the existential quantifier, "For all $x$, $p(x)$" is written $\forall x \; p(x)$ in symbolic form, and "For all $x$ and $y$" is written $\forall x \, \forall y$, abbreviated to $\forall x, y$.

Note: The statements $\forall{x} \; \exists{y} \; p(x, y)$ and $\exists{y} \; \forall{x} \; p(x, y)$ are generally not logically equivalent.

The truth values of quantified open statements are summarized in table 5.

Terminology and Notation

Set

A well-defined collection of objects. Sets are typically denoted with uppercase letters, such as $A$, $B$, $C$, etc. The specification of a set is done with set braces. Example: $A = \{1, 2, 3\} = \{x|x \in \mathbb{Z} \text{ and } 1 \leq x \leq 3 \}$.

Element

A member of a set. Members of sets are typically denoted with lowercase letters. If $x$ is an element of $A$, we write $x \in A$, and if $y$ is not an element of A, we write $y \not\in A$.

Universe (of discourse)

Specifies what "bag" of elements we are choosing from when forming a set. The set $\{x|1 \leq x \leq 3\}$ with $x$ from the universe of all integers is not the same set as $\{x|1 \leq x \leq 3\}$ with $x$ from the universe of all real numbers. We will use the notation $\mathcal{U}$ for the universe here.

Cardinality

The number of elements in a set. The cardinality of a set $A$ is denoted by $|A|$.

Finite set

A set which has a finite number of elements. Think of it as a set you can count and finish counting at some point. Formally, it is a set whose cardinality is less than the cardinality of the natural numbers.

Infinite set

Simply put, a set that is not a finite set. Infinite sets are either countable or uncountable, but that is not important for this course.

Subset

If every element in set $A$ is also an element of set $B$, we say that $A$ is a subset of $B$ and write $A \subseteq B$ (also,$B \supseteq A$). If $A$ i not a subset of $B$ we write $A \not\subseteq B$.

Proper subset

If every element in set $A$ is also an element of set $B$ and $B$ contains an element (or more) which is not in $A$, $A$ is a proper subset of $B$, and we write $A \subset B$ (also $B \supset A$). If $A$ is not a proper subset of $B$ we write $A \not\subset B$.

Equality of sets

If $A$ is a subset of $B$ and $B$ is a subset of $A$, they are equal and we write $A = B$. This is the same as saying that $A$ and $B$ contain exactly the same elements. Note that the order in which the elements appear in a set does not matter.

Null set or empty set

The set containing no elements. It is denoted by $\emptyset$ or { }. Its cardinality is 0. If $A$ is a set, then the empty set is always a subset of $A$ ($\emptyset \subseteq A$), and if $A$ is not empty ($A \neq \emptyset$), then the empty set is a proper subset of $A$ ($\emptyset \subset A$).

Power set

The collection of all subsets of a given set $A$. It is denoted by $\mathcal{P}(A)$. The total number of subsets of a set $A$ where $|A| = n$ is $2^n$. Stated differently, $|\mathcal{P}(A)| = 2^{|A|}$.

Union

The union of two sets $A$ and $B$ is written $A \cup B$. If an element is either in $A$ or $B$ (or both), it is in the set $A \cup B$. In symbolic form their union is given by $A \cup B = \{x|x \in A \lor x \in B \}$. Note that in the same way that $1 +2 +3 + \dots + n = \Sigma^n_{i=1}i$, we can write the union of multiple sets with the big union notation, for example: $S_1 \cup S_2 \cup S_3 \cup \dots \cup S_n = \bigcup^n_{i=1}S_i$.

Intersection

The intersection of two sets $A$ and $B$ is written $A \cap B$. If an element is in $A$ and also in $B$, it is in the set $A \cap B$. In symbolic form their intersection is given by $A \cap B = \{x|x \in A \land x \in B \}$. As above with unions, the intersection of multiple sets can be written with the big intersection notation, for example: $S_1 \cap S_2 \cap S_3 \cap \dots \cap S_n = \bigcap^n_{i=1}S_i$.

Symmetric difference

The symmetric difference of two sets $A$ and $B$ is written $A \vartriangle B$. If an element is in either $A$ or $B$ but not in both, it is in the set $A \vartriangle B$. In symbolic form the symmetric difference is given by $A \vartriangle B = \{x|x \in A \cup B \land x \not\in A \cap B\}$.

Disjoint

Two sets in the same universe are called disjoint or mutually disjoint when they do not share any elements. For the sets $S, T \subseteq \mathcal{U}$, we write this as $S \cap T = \emptyset$.

Complement

The complement of a set $A \subseteq \mathcal{U}$ consists of all the elements in the universe except the elements in $A$. It is denoted $\overline{A}$ (sometimes $\mathcal{U} - A$). In symbolic form the complement is given by $\overline{A} = \{x|x \in \mathcal{U} \land x \not\in A\}$.

Relative complement

The (relative) complement of $A$ in $B$, denoted $B - A$, consists of all the elements of $B$ except the elements which are in $A$. In symbolic form the relative complement of $A$ in $B$ is given by $B - A = \{x|x \in B \land x \not\in A\}$.

Duality of set expressions

The dual of a set expression is obtained by replacing all "$\emptyset$" with "$\mathcal{U}$" and vice versa, and replacing all "$\cap$" with "$\cup$" and vice versa.

Principle of Duality

Simply put, if two set expressions are equal, then their duals are also equal.

Laws of Set Theory

Law of Double Complement

$\begin{equation} \overline{\overline{A}} = A \end{equation}$

DeMorgan's Laws

$\begin{equation} \overline{A \cup B} = \overline{A} \cap \overline{B} \\ \overline{A \cap B} = \overline{A} \cup \overline{B} \end{equation}$

Generalized DeMorgan's Laws

$\begin{equation} \text{Let } I \text{ be an index set,} \\ \overline{\bigcup_{i \in I}A_i} = \bigcap_{i \in I} \overline{A_i} \\ \overline{\bigcap_{i \in I}A_i} = \bigcup_{i \in I} \overline{A_i} \end{equation}$

Commutative Laws

$\begin{equation} A \cup B = B \cup A \\ A \cap B = B \cap A \end{equation}$

Associative Laws

$\begin{equation} A \cup (B \cup C) = (A \cup B) \cup C \\ A \cap (B \cap C) = (A \cap B) \cap C \end{equation}$

Distributive Laws

$\begin{equation} A \cup (B \cap C) = (A \cup B) \cap (A \cup C) \\ A \cap (B \cup C) = (A \cap B) \cup (A \cap C) \end{equation}$

Idempotent Laws

$\begin{equation} A \cup A = A \\ A \cap A = A \end{equation}$

Identity Laws

$\begin{equation} A \cup \emptyset = A \\ A \cap \mathcal{U} = A \end{equation}$

Inverse Laws

$\begin{equation} A \cup \overline{A} = \mathcal{U} \\ A \cap \overline{A} = \emptyset \end{equation}$

Domination laws

$\begin{equation} A \cup \mathcal{U} = \mathcal{U} \\ A \cap \emptyset = \emptyset \end{equation}$

Absorption Laws

$\begin{equation} A \cup (A \cap B) = A \\ A \cap (A \cup B) = A \end{equation}$

A Few Important Sets of Numbers

Note! We have defined the set of natural numbers to include 0. This is a convention in discrete mathematics/number theory (c.f. Grimaldi, Rosen), but it is not the most common practice in mathematics as a whole (where the natural numbers usually start at 1). An unambiguous notation for the set of non-negative integers is $\mathbb{N^0}$ or $\mathbb{N_0}$, and either $\mathbb{N^+}$ or $\mathbb{Z^+}$ for the set of positive integers. But if you want to read about how including or not including 0 are just two sides of the same coin, check this out.

Boolean Functions

Boolean Algebra

Terminology and Notation

Cartesian product or cross product

For sets $A$ and $B$, the cartesian product $A \times B$ is the set of all ordered pairs $(a, b)$ where $a \in A$ and $b \in B$.

Relation

Any subset of $A \times B$ is called a relation from $A$ to $B$. Any subset of $A \times A$ is called a relation on $A$. We use $\mathcal{R}$ to denote a relation, and if $(a, b) \in \mathcal{R}$ we can use the infix notation $a~\mathcal{R}~b$ (and if $(a, b) \not\in \mathcal{R}$, $a~\mathord{\not\mathrel{\mathcal{R}}}~b$).

Function

A function $f$ from set $A$ to set $B$, denoted $f\!: A \to B$, is a special kind of relation from $A$ to $B$, in which every element of A appears exactly once as the first component of an ordered pair in the relation. If $(a, b)$ is an ordered pair in the relation, we write $f(a) = b$. Also, $f(A) = \{b\in B|b = f(a)$, for some $a \text{ in } A \}$.

Image and preimage

For $(a, b) \in f$, $b$ is called the image of $a$ under $f$ and $a$ is a preimage of $b$. Similarly, if $f\!: A \to B$ and $A_1 \subseteq A$, $f(A_1)$ is called the image of $A_1$ under $f$.

Domain

The set the function is defined upon to have as input. For the function $f\!: A \to B$, $A$ is called the domain. Every $a$ in $A$ maps to some $b$ in $B$.

Codomain

The set which contains all possible outputs of a function. For the function $f\!: A \to B$, $B$ is called the codomain. For each $b$ in $B$, there may or may not be an $a$ in $A$ such that $f(a) = b$. In other words, not all functions have mappings to all of the elements in the codomain. See injective and surjective below for the definitions of different types of functions in this regard.

Range

For $f\!: A \to B$, $f(A)$ is the range of the function. This is the subset of the codomain $B$ consisting of the elements $b$ for which there exist an $a$ in $A$ such that $f(a) = b$.

Restriction

Restrictin the domain of a function to a subset of the original domain. If $f\!: A \to B$ and $A_1 \subseteq A$, then the restriction of $f$ to $A_1$ is denoted $f|_{A_1}\!: A_1 \to B$, and it is valid as long as $f|_{A_1}(a) = f(a)$ for all $a$ in $A_1$.

Extension

Expanding a function beyond its original domain. Let $A_1 \subseteq A$ and $f\!: A_1 \to B$. If $g\!: A \to B$ and $g(a) = f(a)$ for all $a$ in $A$, then we call $g$ an extension of $f$ to $A$.

Injective or one-to-one

A function $f\!: A \to B$ is injective if each element of $B$ appears at most once as the image of an element of $A$. Therefore, given an injective function, no two elements $x_1, x_2$ in $A$ can map to the same element $y$ in $B$. If they do, then $x_1 = x_2$.

Surjective or onto

A function $f\!: A \to B$ is surjective if each element of $B$ appears at least once as the image of an element of $A$. Therefore, given a surjective function, for every $b$ in $B$ there exists at least one $a$ in $A$ such that $f(a) = b$. For a surjective function, the range and the codomain of the function are the same, $f(A) = B$.

Bijective or one-to-one correspondence

A function is bijective if it is both injective and surjective. Therefore, a function $f\!: A \to B$ is bijective if each element of $B$ appears only once as the image of an element of $A$.

Number of onto functions

May or may not be exam relevant. For finite sets $A$, $B$ with $|A| = m$ and $|B| = n$ there are $\sum^n_{k=0}(-1)^k\binom{n}{n \;-\; k}(n - k)^m$ onto functions from $A$ to $B$.

Equality of functions

Two functions are equal if and only if their domains and codomains are equal, and $f(x) = g(x)$ for all $x$ in their domain. As a counterexample, if $f\!: \mathbb{Z} \to \mathbb{Z}$, $g\!: \mathbb{Z} \to \mathbb{Q}$, where $f(x) = g(x)$ for all $x$ in $\mathbb{Z}$, then $f$ and $g$ are not equal ($f \neq g$), since their domains are not equal, even though they have equal outputs for every possible input.

Identity function

The identity function for a set $A$, $1_A\!: A \to A$, is defined by $1_A(a) = a$ for all $a$ in $A$.

Composition of functions

The composite function of $f\!: A \to B_1$ and $g\!: B \to C$ is denoted $g \circ f\!: A \to C$ and is defined by $(g \circ f)(a) = g(f(a))$, for each $a$ in $A$, as long as $B_1 \subseteq B$. You can think of it as the first function $g$ "eating" the output of the second function $f$. If the range of $f$ is not a subset of the domain of $g$, then the composite function $g \circ f$ is not defined.

Powers of functions

If $f\!: A \to A$ we define $f^1 =f$, and for a positive integer $n$, $f^{n+1} = f \circ (f^n)$.

Converse of a relation

If $\mathcal{R}$ is a relation from $A$ to $B$, then the converse of $\mathcal{R}$, denoted $\mathcal{R}^c$, is the relation from $B$ to $A$ defined by $\mathcal{R}^c = \{(b, a)|(a, b) \in \mathcal{R} \}$. Simply put, it is the relation $\mathcal{R}$ just in reverse. The converse of a function is a relation which may or may not be a function.

Inverse of a function

For a function to have an inverse, it must be invertible. A function $f\!: A \to B$ is invertible if there exists a function $g\!: B \to A$ such that $g\circ f = 1_A$ and $f \circ g = 1_B$. You could also say that a function is invertible if it has a converse which is also a function. More specifically, a function is invertible if and only if it is injective (one-to-one) and surjective (onto), i.e. it is bijective (one-to-one correspondence). The notation for the inverse of $f$ is $f^{-1}$, and since $f$ is invertible, $f^{-1} = f^c$.

More on Relations

Reflexivity

A relation $\mathcal{R}$ on a set $A$ is called reflexive if for all $x$ in $A$, $(x, x)$ is in $\mathcal{R}$. So if $x$ is related to anything else ($x$ occurs as a member of an ordered pair in the relation), it also means that $x$ is related to itself.

Symmetry

A relation $\mathcal{R}$ on a set $A$ is called symmetric if $(x, y) \in \mathcal{R} \Rightarrow (y, x) \in \mathcal{R}$, for all $(x, y)$ in $A$. So if $x$ is related to $y$, it means that $y$ is related to $x$.

Transitivity

For a set $A$, a relation $\mathcal{R}$ on $A$ is called transitive if, for all $x, y, z \in A$, $(x, y), (y, z) \in \mathcal{R} \Rightarrow (x, z) \in \mathcal{R}$. So if $x$ is related to $y$ and $y$ is related to $z$, then $x$ is also related to $z$,.

Antisymmetry

Given a relation $\mathcal{R}$ on a set $A$, $\mathcal{R}$ is called antisymmetric if for all $a, b \in A$, $(a~\mathcal{R}~b \text{ and } b~\mathcal{R}~a) \Rightarrow a = b$. So the only way that we can have both "$a$ is related to $b$" and "$b$ is related to $a$" is if $a$ and $b$ are the same.

Partial ordering relation or partial order

A relation is called a partial ordering relation if it is reflexive, antisymmetric and transitive.

Equivalence relation

A relation is called an equivalence relation if it is reflexive, symmetric and transitive.

Composition of relations

If $A$, $B$ and $C$ are sets with $\mathcal{R}_1 \subseteq A \times B$ and $\mathcal{R}_2 \subseteq B \times C$, then the composite relation $\mathcal{R}_1 \circ \mathcal{R}_2$ is a relation from $A$ to $C$ defined by $\mathcal{R}_1 \circ \mathcal{R}_2 = \{(a, c)|a \in A, c \in C$ and there exists $b\in B$ with $(a, b) \in \mathcal{R}_1, (b, c)\in \mathcal{R}_2 \}$. Be careful in the composition in relations, since the order the composition is written in is different from the order function compositions are written in!

Partially ordered set or poset

If a relation $\mathcal{R}$ on a set $A$ is a partial ordering relation, we call the pair $(A, \mathcal{R})$ a partially ordered set or poset. If we call $A$ a poset, this is shorthand for saying that there is a partial order $\mathcal{R}$ on $A$ that makes $A$ into this poset.

Hasse diagram

A graphical representation of a partially ordered set, as a directed graph with an implied upward orientation. We construct a Hasse diagram for a poset by drawing an edge from $x$ up to $y$ if $x \mathcal{R} y$ and, most important, if there is no other element $z$ such that $x~\mathcal{R}~z$ and $z \mathcal{R} y$, i.e. it is the most "direct" way of relating. See the figure below.

Totally ordered poset

Also called linearly ordered. Let $(A, R)$ be a poset,