# Discrete Mathematics - Midterm 1

Exam Date
28th of October

## 1. Propositional Logic

### 1.1. Propositions

• A proposition is a sentence which can be given a truth value of True or False.
• Propositions can be related to each other using operators

#### 1.1.1. Tautology

It is a proposition that can only be True.

$p \lor \neg q = \top$

It is a proposition that can only be False.

$p \land \neg q = \bot$

### 1.2. Operators

There are three main operators which can be used to express any logical expression. These consists of Not, Conjunction, Disjunction.

#### 1.2.1. Not

It flips the truth value of a proposition.

$\neg p, \bar{A}$

#### 1.2.2. Conjunction

This operators returns a new truth value which is true if both of the propositions are true

$p \land q, AB$

#### 1.2.3. Disjunction

Like the conjunction, it operates on two propositions. It will return true as long as either of the propositions is true.

$p \lor q, A+B$

#### 1.2.4. Exclusive OR (XOR)

It is very similar to the Disjunction except that it must be exclusively one value that is true.

$\oplus = (p \lor q) \land \neg(p \land q)$

#### 1.2.5. Conditional Statements / Implication

A conditional statement consists of two parts, the premise and consequence. The truth value is only false when $$T \to F$$.

$p \to q \equiv \neg p \lor q$

• If $$p$$ is True, then $$q$$ must also be True, we say that p is a sufficient condition for $$q$$. $$T \to T$$
• If $$p$$ is False, $$q$$ could still be True. $$F \to T$$
• $$p$$ cannot be true if $$q$$ is not true. $$F \to F$$
• $$p$$ could still be false, even if $$q$$ is true. $$F \to T$$

$((p \to q) \land p) \to q$

$((p \to q) \land \neg q) \to \neg p$

1. Fallacies
Affirming the consequent
$$((p \to q) \land q) \to p$$
Nageting the antecedent
$$((p \to q) \land \neg p) \to \neg q$$
2. Converse, Contrapositive, Inverse
Converse
$$q \to p$$
Contrapositive
$$\neg q \to \neg p$$
Inverse
$$\neg p \to \neg q$$

The fallacies are a product of assuming that the Converse and Inverse are equivalent to the conditional statement.

#### 1.2.6. Bi-conditionals

It expressed a sufficient and necessary conditional relationship between two propositions. It is read as if and only if p, then q.

$p \Leftrightarrow q$

This operator will return True only if both p and q have equal values. The expression can be represented with the 3 basic operators as:

$(p \to q) \land (q \to p) \equiv (\neg p \land \neg q) \lor (p \land q)$

$p \equiv q = \neg (p \oplus q)$

#### 1.2.7. Order of Operators

1. $$\neg$$
2. $$\land$$
3. $$\lor$$
4. $$\to$$
5. $$\Leftrightarrow$$

### 1.3. Equivalence

Two propositions are said to be equivalent only if both have equivalent truth tables.

$p \equiv q$

#### 1.3.1. Disjunctive Normal Form

It allows us to represent an un-known proposition by analyzing the truth table and constructing a new proposition using the 3 basic operators.

### 1.4. Morgan Laws

\begin{align} \neg (p \land q) \equiv \neg p \lor \neg q \\ \neg (p \lor q) \equiv \neg p \land q \end{align}

### 1.5. Logical Equivalences

#### 1.5.1. Identity Laws

$p \land \top \equiv p$

$p \lor \bot \equiv p$

#### 1.5.2. Denomination Laws

$p \lor \top \equiv \top$

$p \land \bot \equiv \bot$

#### 1.5.3. Idempotent Laws

$p \lor p \equiv p$

$p \land p \equiv p$

#### 1.5.4. Double Negation Law

$\neg ( \neg p) \equiv p$

#### 1.5.5. Commutative Laws

$p \lor q \equiv q \lor p$

$p \land q \equiv q \land p$

#### 1.5.6. Associative Laws

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

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

#### 1.5.7. Distributive Laws

$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)$

#### 1.5.9. Absorption Laws

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

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

#### 1.5.10. Negation Laws

$p \lor \neg p \equiv \top$

$p \land \neg p \equiv \bot$

### 1.6. Satisfiability

Any proposition is satisfiable if it is True for at least one case, that is, a proposition is satisfiable if its not a contradiction

## 2. Predicate Logic

It is away of breaking down a complex proposition into various parts. The way we go about this is by using Predicates and Quantifiers.

### 2.1. Predicates

A predicate is a statement which is similar to a proposition, but it is parametric.

\begin{array}{l} X \text{ is faster than me} \\ = \text{Subject} + \text{Predicate} \\ \to P(x) \end{array}

Once the parameters have been passed to the predicate, it becomes a proposition with an appropriate truth value. A predicate with $$n$$ number of variables can be represented by:

$P(x_1, x_2, x_3, \ldots, x_n)$

And once instantiated with variables:

$P(a_1, a_2, a_3, \ldots, a_n) \equiv p$

#### 2.1.1. Domains

Naturals $$\mathbb{N}$$
$$[1,2,3,\ldots,\infty)$$
Integers $$\mathbb{Z}$$
$$(-\infty,\ldots,-2,0,2,\ldots,\infty)$$
Rationals $$\mathbb{Q}$$
Fractions of integers $$\{ \frac{p}{q} \vert p \in Z \land q \in Z \land q \ne 0 \}$$
Reals $$\mathbb{R}$$
All real numbers

#### 3.6.5. Proof by Cases

This is a proof which can be used a used as a part of another proof when proving implications. If we have an implication where the premise consists of disjunctions, we can apply the following:

\begin{align} (p_1 \lor p_2 \lor \ldots \lor p_n) \to q \\ (p_1 \to q) \land (p_2 \to q) \land \ldots \land (p_n \to q) \end{align}

This proof is very helpful when we want to prove that a condition is satisfiable for a group of elements.

1. Example

Prove that if $$n$$ is not a multiple of 3, $$2n$$ is not a multiple of 3.

Solution
To define a value as not a multiple of 3, we have two formulas $$n = 3k + 1 \quad n = 3k + 2$$. We can reformulate the proposition by saying $$(n = 3k+1) \lor (n = 3k^\prime) \to \neg (2n = 3k^{\prime\prime})$$. We then have to show that both cases imply the consequence.

#### 3.6.6. Equivalence Proof

As previously mentioned $$p \leftrightarrow q = p \equiv q$$, so if we want to prove some equivalence, we can use $$(p \to q) \land (q \to p)$$.

#### 3.6.7. Existential Statements Proof

We have two strategies for this.

Constructive Proof
We show an example that verifies a predicate and apply existential generalization to prove the proposition.
Non Constructive Proof
We show that there exists an element which validates the predicate but we dont specify which one. This is most commonly proof by contradiction.

#### 3.6.8. Universal Statements Proof

Proving
We show that a predicate holds for an arbitrary value and then apply universal generalization.
Counterexamples
To disprove a universal statement we need to find a counterexample. This action is a process of negation, making the US an ES.

#### 3.6.9. Strategy for Proofs

So what the fuck should you use? It comes down to trial and error, but also practice and intuition.

Trial and error
If direct proof doesnt work, try indirect lol.
Complex propositions
If there are complex propositions in an implication, they quite possibly can be negated, allowing use to use an indirect method.
Using proof by contradiction with conditional statements
We show that $$\neg (p \to q)$$ implies $$\bot$$.
Proof by cases
Yeah… no.

## 4. Set Theory

### 4.1. Sets

The definition of a set is a collection of unordered unique objects. Each object in that set is a member.

$$a$$ is a member of $$A$$
$$a \in A$$
$$a$$ is not a member of $$A$$
$$a \not\in A$$

We can define a set in various way. We can list all its elements or skip some obvious elements. If our set were to consist of a larger number of objects, listing them all is impractical, to overcome this we can use predicates.

\begin{array}{c} x \text{ such that } P(x) \\ A = \{ x \vert P(x)\} \end{array}

#### 4.1.1. Logical Definition

The way we can express a set by using logic is with the following expression:

$\forall x ((x \in A) \Leftrightarrow P(x))$

#### 4.1.2. Interval Definition

A very common way to define a set is to use an interval such as $$(a,b) \quad [a,b) \quad (a,b] \quad [a,b]$$. in this notation the meaning of the parenthesis and bracket is open and closed interval respectively.

#### 4.1.3. Equal Sets

The set $$A$$ is equal to $$B$$ if and only if all the elements of $$A$$ are also elements of $$B$$.

$(A = B) \Leftrightarrow \forall x (x \in A \Leftrightarrow x \in B)$

$(A = B) \Leftrightarrow (A \subseteq B) \land (B \subseteq A)$

Disproving
We need to give a counterexample, this can be represented by $$\exists x (x\in A \oplus x \in B)$$

#### 4.1.4.Important Sets

Sets as Elements
A set can also be an element of a set
Empty Set $$\emptyset$$
The empty set is a set with no elements in it. $$\emptyset \ne \{\emptyset\}$$
Universal Set U
A set containing all elements under consideration

### 4.2. Subsets

The set $$A$$ is a subset of $$B$$ if and only if all elements of $$A$$ are also elements of $$B$$. If this is so, $$B$$ is the superset of $$A$$.

$A \subseteq B$

$\forall x ((x \in A) \to (x \in B))$

It is true for every set that it has at least 2 subsets, the empty set and itself.

$\forall X ((X \supseteq \emptyset) \land (X \supseteq X))$

Finally, if a set $$A$$ is a subset of $$B$$ but they are not equal, we say that $$A$$ is proper subset of $$B$$.

### 4.3. Set Cardinality

The cardinality of a set is the number of elements in that set. This is represented by $$\vert A \vert$$. If a set has infinite elements, its cardinality is infinity.

### 4.4. The Power Set

A power set is a set of all the subsets of $$A$$. If $$A$$ is a finite set, the cardinality of the power set will be given by $$2^n$$ where $$n = \vert A \vert$$

Given that $$A = \{a,b,c\}$$
The power set of $$A$$ is $$P(A) = \{\emptyset, \{a\}, \{b\}, \{c\} \{a, b\} \{a,c\} \{b,c\}\{a,b,c\} \}$$

### 4.5. Cartesian Product

In discrete mathematics, an ordered collection is called a relation. If we have two sets, $$A,B$$ each with a different cardinality, the Cartesian product of these two sets is a set of all possible two-term relations that can be constructed using the two sets.

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

If the sets used for a Cartesian product are all finite, the cardinality of the Cartesian product for $$n$$ sets will be as follows:

$\vert A_1 \times A_2 \times \ldots \times A_n \vert = \vert A_1 \vert \times \vert A_2 \vert \times \ldots \times \vert A_n \vert$

### 4.6. Set Operations

#### 4.6.1. Union

The union operator produces a new set of elements which are both in set $$A$$ and $$B$$.

$\forall ((x \in A \cup B) \Leftrightarrow ((x \in A) \land (x \in B))$

$A \cup B = \{x \vert (x \in A) \lor (x \in B)\}$

Cardinality
$$\vert A \cup B \vert = \vert A \vert + \vert B \vert - \vert A \cap B \vert$$

#### 4.6.2. Intersection

The intersection produces a set of elements which are only in set $$A$$ and $$B$$ at the same time.

$\forall x (( x \in A \cap B) \Leftrightarrow ((x \in A) \land (x \in B)))$

$A \cap B = \{x \vert (x \in A) \land (x \in B)\}$

#### 4.6.3. Subtraction

When subtracting two sets, the difference will consist of all elements in $$A$$ that are not in $$B$$.

$\forall x ((x \in A - B) \Leftrightarrow ((x \in A) \land (x \not \in B)))$

$A - B = \{x\vert(x \in A) \land (x \not \in B)\}$

Cardinality
$$\vert A - B \vert = \vert A \vert - \vert A \cap B \vert$$

### 4.7. Complementary Set

This is a set of all elements in the sample space that are not in $$A$$.

$\bar{A} = U - A = \{ x \vert (x \in U ) \land (x \not \in A)\}$

$\bar{A} = \{ x \vert x \not \in A\}$

### 4.8. Logic and Set Equivalences

For sets, we can apply almost any logical transformation assuming the following:

\begin{array}{l} A \cup B \sim p \lor q \\ A \cap B \sim p \land q \\ \bar{A} \sim \neg p \end{array}

This is due to the role of predicates in the definition of sets.

$A = \{ x \vert P(x)\}$

## 5. Functions

A function is an assignment of a single value $$b$$ in $$B$$ for every value $$a$$ in $$A$$. A function is also refereed to as a mapping, transformation or black box (possibly and oracle).

\begin{array}{l} f(a) = B \\ f : A \to B \end{array}

What makes a function a function? The relationship can be described with the following expression:

$\forall a \in A \exists ! b \in B (f(a) = b)$

Why would some assignments not be functions?
Not all elements in $$A$$ are assigned a value in $$B$$. Some values in $$A$$ are assigned more than one value in $$A$$. TLDR: Some element in $$A$$ doesnt have a value or it has multiple

### 5.1. Domain, Codomain and Range

If $$f(a) = b$$ we call $$b$$ the image of $$a$$ and vice versa $$a$$ is the preimage.

Domain
The set $$A$$
Codomain
The set $$B$$
Range
The set of all images for all values of $$A$$

### 5.2. One to One Functions

A function is said to be one to one or injective if for every value $$b$$ there is at most one value $$a$$.

$\forall a \in A \forall b \in B ((f(a) = f(b)) \Leftrightarrow (a = b))$

How can we tell if a function is injective?
As per the definition, above we use two different variables and test that if $$f(a) = f(b)$$ it must be, that $$a = b$$, if this is so, the function is injective.

### 5.3. Onto Functions

A function is onto or surjective if and only if for each value in $$B$$ there is at least one value in $$A$$

$\forall b \in B \exists a \in A(f(a) = b)$

How can we tell if a function is onto?
We define some arbitrary image of the function as $$c$$ and then solve for $$x$$. If we have $$f(x) = \sqrt{x}$$ we then proceed to insert the image $$c = \sqrt{x} \Rightarrow x = c^2$$. Since for a square, the range is only positive reals, this is not an onto.

### 5.4. Composite Functions

A common expression to denoted nested or composed function is the following: $(f \circ g) (x) = f(g(x))$ In this scenario the value returned by g is then the input for f.

• If the co-domain of the inside function is not a subset of the domain of the outer function, the composition will not be defined.

### 5.5. Partial Functions

This is a function which has certain points or ranges which cannot be a part of the domain.

## 6. Sequences

A sequence is a collection of elements which can be intuitively continued by knowing the first terms. in broader terms, a sequence assigns some order or pattern represented by some index - Therefore, it is a function. We use $$a_n$$ to represent the image of $$n$$.

### 6.1. Arithmetic Progression

In its most abstract form, it is a linear function. Commonly represented in sequence form as:

$a, a + d,a + 2d, \ldots, a + nd, \ldots$

$a_n = a + dn$

It is composed of an initial term($$a$$) and common difference($$d$$).

### 6.2. Geometric Progression

This progression is of exponential form. It is composed of an initial term ($$a$$) and common ration ($$r$$).

$a, a * r, a*r^2, ... , a * r^n$

$a_n = ar^n$

### 6.3. Recurrence Relation

A recurrent relation is a rule which defines a value for the nth term as a function of some previous terms. The implicit formula for a recurrent relationship is called a closed formula, it is the solution to given relation.

• To find the closed formula, we should use iteration to see a pattern in the sequence.

## 7. Summations

A summation is defined as the sum of all the terms of the sequence between $$i,n_0$$ and $$n_f$$, including both. The summation term is defined by \$∑i=0n, where $$i$$ is the initial term and $$n$$ the final.

### 7.1. First $$n$$ Integers Sum

$\sum_{i=1}^{n}{i} = \frac{n(n+1)}{2}$

### 7.2. Other Rules

$\sum_{n=s}^t {C * f(n)} = C * \sum_{n=s}^{t} {f(n)}$

$\sum_{n=s}^{t} {f(n)} = \sum_{n=s+p}^{t+p} {f(n-p)}$

$\sum_{i=0}^{n-1} {a^i} = \frac{1-a^n}{1-a}$

### 7.3. Nested Summations

If we have an expression where there are two sums $$\sum\sum$$, we expand the far right summation and include it in the second sum.

1. Example

Calculate $$\sum_{i=1}^2 \sum_{i=1}^3 ij^2$$

Solution
$$\sum_{i=1}^2 \sum_{i=1}^3 ij^2 = \sum_{i=1}^2(i + 4i + 9i) = (1+4+9) + (2+4*2+9*2)$$

Created: 2022-10-30 Sun 22:35

Validate