Discrete Mathematics - Final

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

The fallacies stem from the fact that an implication is true, and the truth value of either \(p,q\).

Affirming the consequent

\(((p \to q) \land q) \to p\). We falsely assume that the premise is true because the consequence is true

Nageting the antecedent

\(((p \to q) \land \neg p) \to \neg q\). We falsely assume that the consequence is false because the premise is false.

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.

This is a proposition created from the values in the truth table.

These are various way you can arrive at some conclusion given a few basic propositions.

A proposition is satisfiable if it has at least one case for which it is true, it is anything but a contradiction.

For the following, create a truth table and a DNF for each (a DNF is a proposition created from the values in the truth table)

1. \(p \lor \neg p\)

   Truth Table:

   \begin{array}{|c|c|c|} \hline p & \neg p & p \lor \neg p \\ \hline T & F & T \\ \hline F & T & T \\ \hline \end{array}

   DNF:

   \[ p \lor \neg p = \top \]

2. \(p \land \neg p\)

   Truth Table:

   \begin{array}{|c|c|c|} \hline p & \neg p & p \land \neg p \\ \hline T & F & F \\ \hline F & T & F \\ \hline \end{array}

   DNF:

   \[ p \land \neg p = \bot \]

3. \(p \lor (p \land q)\)

   Truth Table:

   \begin{array}{|c|c|c|} \hline p & q & p \lor (p \land q) \\ \hline T & T & T \\ \hline T & F & T \\ \hline F & T & F \\ \hline F & F & F \\ \hline \end{array}

   DNF:

   \[ p \lor (p \land q) = p \]

4. \(p \land (p \lor q)\)

   Truth Table:

   \begin{array}{|c|c|c|} \hline p & q & p \land (p \lor q) \\ \hline T & T & T \\ \hline T & F & T \\ \hline F & T & F \\ \hline F & F & F \\ \hline \end{array}

   DNF:

   \[ p \land (p \lor q) = p \]

Now for implications:

1. \(p \to q\)

   Truth Table:

   \begin{array}{|c|c|c|} \hline p & q & p \to q \\ \hline T & T & T \\ \hline T & F & F \\ \hline F & T & T \\ \hline F & F & T \\ \hline \end{array}

   DNF:

   \[ p \to q = \neg p \lor q \]

2. \(p \to \neg q\)

   Truth Table:

   \begin{array}{|c|c|c|} \hline p & q & p \to \neg q \\ \hline T & T & F \\ \hline T & F & T \\ \hline F & T & T \\ \hline F & F & T \\ \hline \end{array}

   DNF:

   \[ p \to \neg q = \neg p \lor \neg q \]

3. \((\neg p) \to q\)

   Truth Table:

   \begin{array}{|c|c|c|} \hline p & q & (\neg p) \to q \\ \hline T & T & T \\ \hline T & F & T \\ \hline F & T & T \\ \hline F & F & F \\ \hline \end{array}

   DNF:

   \[ (\neg p) \to q = p \lor q \]

4. \(\neg p \to \neg q\)

   Truth Table:

   \begin{array}{|c|c|c|} \hline p & q & \neg p \to \neg q \\ \hline T & T & T \\ \hline T & F & T \\ \hline F & T & F \\ \hline F & F & T \\ \hline \end{array}

   DNF:

   \[ \neg p \to \neg q = p \lor \neg q \]

Prove the following:

1. \(p \to q \equiv \neg p \lor q\)

   Proof:

   \begin{array}{|c|c|c|} \hline p & q & p \to q & \neg p \lor q \\ \hline T & T & T & T \\ \hline T & F & F & F \\ \hline F & T & T & T \\ \hline F & F & T & T \\ \hline \end{array}

   Therefore \(p \to q \equiv \neg p \lor q\) is true.

2. \(p \to q \equiv \neg q \to \neg p\)

   Proof:

   \begin{array}{|c|c|c|} \hline p & q & p \to q & \neg q \to \neg p \\ \hline T & T & T & T \\ \hline T & F & F & F \\ \hline F & T & T & T \\ \hline F & F & T & T \\ \hline \end{array}

   Therefore \(p \to q \equiv \neg q \to \neg p\) is true.

Which of the following are satisfiable:

1. \(p \land \neg p\)

   \begin{array}{|c|c|c|} \hline p & \neg p & p \land \neg p \\ \hline T & F & F \\ \hline F & T & F \\ \hline \end{array}

   Therefore \(p \land \neg p\) is unsatisfiable.

2. \(p \lor \neg p\)

   \begin{array}{|c|c|c|} \hline p & \neg p & p \lor \neg p \\ \hline T & F & T \\ \hline F & T & T \\ \hline \end{array}

   Therefore \(p \lor \neg p\) is satisfiable.

3. \(p \to q\)

   \begin{array}{|c|c|c|} \hline p & q & p \to q \\ \hline T & T & T \\ \hline T & F & F \\ \hline F & T & T \\ \hline F & F & T \\ \hline \end{array}

   Therefore \(p \to q\) is satisfiable.

4. \(p \to \neg q\)

   \begin{array}{|c|c|c|} \hline p & q & p \to \neg q \\ \hline T & T & F \\ \hline T & F & T \\ \hline F & T & T \\ \hline F & F & T \\ \hline \end{array}

   Therefore \(p \to \neg q\) is satisfiable.

5. \(\neg p \to q\)

   \begin{array}{|c|c|c|} \hline p & q & \neg p \to q \\ \hline T & T & T \\ \hline T & F & T \\ \hline F & T & T \\ \hline F & F & F \\ \hline \end{array}

   Therefore \(\neg p \to q\) is satisfiable.

It is a statement, which is made up of a proposition, with the only difference being that it can take a parameter.

We say that the it is instantiated once it gets evaluated with the passed parameter.

\[ 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 \]

With a quantifier, we can specify for which values on a certain domain, a predicate is true of false. There are various ways to express this: (for all, for many, for at least one, for none).

If we have some predicate for which we can say that all the possible values in a certain domain will make it true, we use the universal quantifier.

• To prove that this quantifier is true, we must demonstrate that it holds true for all the possible values.
• To dis-prove the quantifier, it is sufficient to show that there exists just one that does not satisfy the predicate
• If we are considering an empty set, it will always be false.

• To prove this quantifier, we must find at least one value for which the predicate holds true
• To disprove the quantifier, we must show that all the values will not hold for the predicate
• Again, if we consider and empty set, it will always be false

We can also use the existential quantifier, and with a bit of modification we can use it to specify how many values will satisfy the predict.

The definition for this is as follows:

\[ \exists x (P(x) \land \forall y (P(y) \Leftrightarrow x = y)) \]

We can generalize this to a specific number \(n\) for which the predicate is satisfiable.

\[ \exists_n x P(x) \]

When negating a quantifier, we have to consider both the outside and inside, that being the quantifier itself and the predicate.

\[ \neg \forall x P(x) \equiv \exists x \neg P(x) \]

\[ \neg \exists x P(x) \equiv \forall x \neg P(x) \]

If we have more than one variable for which we quantify a predicate, we have to consider the order.

\[ \exists x \forall y P(x,y) \not \equiv \forall y \exists x P(x,y) \]

Evaluate the following:

1. \(\forall x \exists y P(x,y)\) where \(P(x,y) = x > y\)

   This quantifier is true, because for any value of \(x\), there will always be a value of \(y\) that will satisfy the predicate.

2. \(\exists x \forall y P(x,y)\) where \(P(x,y) = x > y\)

   This quantifier is false, because there will always be a value of \(x\) for which there will not be a value of \(y\) that will satisfy the predicate.

3. \(\forall x \exists y P(x,y)\) where \(P(x,y) = x < y\)

   This quantifier is true, because for any value of \(x\), there will always be a value of \(y\) that will satisfy the predicate. This because no matter the value of \(x\), there will always be a value of \(y\) that will be greater than \(x\).

Prove the following:

1. \(\forall x \exists y P(x,y) \equiv \exists y \forall x P(x,y)\)

Nested quantifiers:

1. \(\exists x \forall y \exists z P(x,y,z)\) where \(P(x,y,z) = x > y \land y > z\)

Negating quantifiers:

1. \(\neg \forall x \exists y P(x,y)\) where \(P(x,y) = x > y\)

An argument form which would generate a valid implication falls under the rules of inference

Use the rules of inference to prove the following:

1. \(\neg (p \lor q) \to \neg p \land \neg q\)

   \begin{array}{r} \neg (p \lor q) \\ p \lor q \\ \hline \therefore \neg p \land \neg q \end{array}

   The rules of inference used are Modus Tollens and Disjunctive Syllogism.

2. \(\neg (p \land q) \to \neg p \lor \neg q\)

   \begin{array}{r} \neg (p \land q) \\ p \land q \\ \hline \therefore \neg p \lor \neg q \end{array}

   The rules of inference used are Modus Tollens and Conjunction.

Prove the following using the rules of inference for quantified propositions:

1. \(\forall x P(x) \to P(c)\) where \(P(x) = x > 0\)

   \begin{array}{r} \forall x P(x) \\ P(c) \\ \hline \therefore P(c) \end{array}

   The rules of inference used are Universal Instantiation.

2. \(\exists x P(x) \to P(c)\) where \(P(x) = x > 0\)

   \begin{array}{r} \exists x P(x) \\ P(c) \\ \hline \therefore P(c) \end{array}

   The rules of inference used are Existential Instantiation.

Turn the following phrases into logical statements using the rules of inference for quantified propositions:

1. For all \(x\), \(x > 0\)

   \(\forall x (x > 0)\)

2. There exists \(x\) such that \(x > 0\)

   \(\exists x (x > 0)\)

3. There exists \(x\) such that \(x > 0\) and \(x < 10\)

   \(\exists x (x > 0 \land x < 10)\)

Upon deciding which axioms to use, you then need to use some method of proof. The most common statements we will be proving are implications.

• Show that each of the following conditional statements is a tautology using the fact that a conditional is false exactly when the hypothesis is true and the conclusion is false. (pg 38 Ex140

1. \((\neg p \land (p \lor q)) \to q\)

   Solution: If we use the laws of inference we will get that \(\neg p \land q \to q\). If we try to make this false, we will should consider the case where the premise is true, for the \(p\) is false and \(q\) is true. This will make the conclusion false, which is not possible. Therefore, the statement is a tautology.

2. \(((p\to q) \land (q\to r)) \to (p \to r)\)

   Solution: It is pretty easy to see that this is the hypothetical syllogism. We can use the laws of inference to show that \((p\to q) \land (q\to r)\) is equal to \(p \to r\). Now we just need to show that this is a tautology. We can do this by considering the case where the premise is true, and since the premise and conclusion are the same, we can conclude that the statement is a tautology.

3. \((p \land (p \to q)) \to q\)

   Solution: We transform the statement into \((p \land q) \to q\). We can see that this is a tautology by considering the case where the premise is true. For the premise to be true, the conclusion also has to be true. This makes the case of the implication being false not possible, which means that the statement is a tautology.

4. \(((p\lor q) \land (p \to r) \land (q \to r)) \to r\)

   Solution: By simplifying the premise we get that \(\top \lor r \to r\).

• Show that each of the following conditional statements is a tautology using the chain of logical identities. (Pg 38 Ex 16)

1. \((\neg p \land (p \lor q)) \to q\)

   Solution:

   \begin{align} (\neg p \land (p \lor q)) \to q \\ \neg p \land p \lor \neg p \land q \to q \\ \bot \lor \neg p \land q \to q \\ \neg ( \neg p \land q ) \lor q \\ p \lor \neg q \lor q p \lor \top \\ \top \end{align}

2. \(((p\to q) \land (q\to r)) \to (p \to r)\)

   Solution:

   \begin{align} ((p\to q) \land (q\to r)) \to (p \to r) \\ (\neg p \lor q \land \neg q \lor r) \to (\neg p \lor r) \\ \neg p \lor \bot \lor r \to \neg p \lor r \\ \neg ( \neg p \lor r ) \lor \neg p \lor r \\ p \lor \neg r \lor \neg p \lor r \\ (p \lor \neg p) \lor (r \lor \neg r) \\ \top \lor \top \\ \top \end{align}

3. \((p \land (p \to q)) \to q\)

   Solution:

   \begin{align} (p \land (p \to q)) \to q \\ (p \land (\neg p \lor q)) \to q \\ (p \land \neg p \lor p \land q) \to q \\ (\bot \lor p \land q) \to q \\ \neg (p \land q) \lor q \\ p \lor \neg q \lor q \\ p \lor \top \ \top \end{align}

4. \(((p\lor q) \land (p \to r) \land (q \to r)) \to r\)

   Solution:

   \begin{align} ((p\lor q) \land (p \to r) \land (q \to r)) \to r \\ \neg((p \lor q) \land (\neg p \lor r) \land (\neg q \lor r)) \lor r \\ \neg p \land \neg q \lor p \land \neg r \lor (q \land \neg r) \lor r \\ (\neg p \land \neg q) \lor (p \land \neg r) \lor (q \lor r) \land (\neg r \lor r) \\ (\neg p \land \neg q) \lor (p \land \neg r) \lor (q \lor r) \land \top \\ q \lor (\neg p \land \neg q) \lor r \lor (p \land \neg r) \\ q \lor \neg p \land q \lor \neg q \lor r \lor p \land r \lor \neg r \\ q \lor \neg p \land \top \lor r \lor p \land \top \\ q \lor \neg p \lor r \lor p \\ q \lor r \lor \top \\ \top \end{align}

• Express the negation of the propositions using quantifiers:

1. \(\forall x(x > 1)\)

   Solution: \(\exists x(x \leq 1)\)

2. \(\forall x ((x < -1) \lor (x > 2))\)

   Solution: \(\exists x (( x \ge -1) \land (x \le 2))\)

• Determine whether \(\forall x (P(x) \to Q(x))\) is equivalent to \(\forall x P(x) \to \forall x Q(x)\). (pg 59 ex 45) Solution:

  \begin{align} \forall x (P(x) \to Q(x)) \equiv \forall x P(x) \to \forall x Q(x) \\ \neg \exists x (P(x) \to Q(x)) \lor \exists x P(x) \to \exists x Q(x) \\ \neg \exists x (P(x) \to Q(x)) \lor \neg \exists x P(x) \lor \exists x Q(x) \\ \neg \exists x (P(x) \to Q(x)) \lor \neg \exists x P(x) \lor \neg \exists x Q(x) \end{align}

• Use rules of inference to show that the hypotheses “If it does not rain or if it is not foggy, then the sailing race will be held and the lifesaving demonstration will go on,” “If the sailing race is held, then the trophy will be awarded,” and “The trophy was not awarded” imply the conclusion “It rained.”

  First we identify the premises:

  • \(p =\) it rained
  • \(q =\) it was foggy
  • \(r =\) the race was held
  • \(s =\) the lifesaving demonstration went on
  • \(t =\) the trophy was awarded
  \begin{align} \neg p \lor \neg q \to r \land s \\ r \to t \\ \neg t \neg r \quad \text{from 2nd and 3rd (modus tollens)} \\ (\neg r \land s) \quad \text{from 1st and 4th} \\ \neg (\neg p \lor \neg q) \\ p \land q \\ p \quad \text{it rained} \end{align}
• Find the argument form for the following argument and determine whether it is valid. Can we conclude that the conclusion is true if the premises are true?

Solution: The form of the argument is Modus Tollens, which is valid.

• What rules of inference are used in this famous argument? “All men are mortal. Socrates is a man. Therefore, Socrates is mortal.”

  Solution:

  \begin{array}{r} \forall x (M(x) \to Mo(x)) \\ M(S) \\ \hline Mo(S) \end{array}

  Here we make us of universal instantiation and them modus ponens.

• Use a direct proof to show that every odd integer is the difference of two squares. Solution:

  \begin{align} n = 2k + 1 \\ n = (k+1)^2 - k^2 \\ n = k^2 + 2k + 1 - k^2 \\ n = 2k + 1 \end{align}

A set is a collection of objects. We use the notation \(\{a,b,c\}\) to denote a set. We can also use the notation \(\{x \in S \mid P(x)\}\) to denote a set of elements \(x\) in \(S\) that satisfy the predicate \(P(x)\). A set can be empty, which is denoted by \(\emptyset\).

A more concrete definition of a set using quantifiers is as follows:

\[ \forall x (( x \in S) \leftrightarrow P(x)) \]

We also often use interval definitions to define sets. These are defined as follows:

\[ \{x \in \mathbb{R} \mid a \leq x \leq b\} \]

A common way to define a interval is with brackets and parenthesis. For example, \((a,b)\) is an open interval, while \([a,b]\) is a closed interval.

Two sets are equal if they have the same elements. We denote this as \(A = B\). A more rigorous definition of this is as follows:

\[ A = B \equiv \forall x (x \in A \leftrightarrow x \in B) \]

The equality of two sets can also be defined using subsets:

\[ A = B \equiv A \subseteq B \land B \subseteq A \]

A way to disprove the equality of two sets is by showing that they have at least one element that is not in the other set. This is called a counterexample. It can be represented with an existential quantifier and XOR: \(\exists x (x \in A \oplus x \in B)\).

Some important elements are the aforementioned empty set \(\emptyset\) and the universal set \(\mathbb{U}\). The universal set is the set of all elements in a domain. The empty set is the set that contains no elements. The Domains, mentioned at the beginning are also sets.

A subset is a set that is contained in another set. We denote this as \(A \subseteq B\). A more rigorous definition of this is as follows:

\[ A \subseteq B \equiv \forall x (x \in A \to x \in B) \]

For all sets, it is true that \(A \subseteq A\) and \(\emptyset \subseteq A\). Which means that every set is a subset of itself and the empty set is a subset of every set. We can also say that \(A \subseteq B\) and \(B \subseteq A\) implies \(A = B\). This is called the subset equality.

What can be confusing is the proper subset. A proper subset is a subset that is not equal to the set. We denote this as \(A \subset B\). A more rigorous definition of this is as follows:

\[ A \subset B \equiv A \subseteq B \land A \neq B \]

A quantified version of this is as follows:

\[ \forall x ((x \in A) \to (x \in B) \land (A \neq B)) \]

This is not the absolute value of a set. It is the number of elements in a set. We denote this as \(|A|\). A more rigorous definition of this is as follows:

\[ \vert A \vert \equiv \# \{x \in A \mid x \in A\} \]

The power set is the set of all subsets of a set. We denote this as \(P(A)\). What is meant by all subsets is that the power set contains the empty set and the universal set aswell as all the subsets of the set. A more rigorous definition of this is as follows:

\[ P(A) \equiv \{B \mid B \subseteq A\} \]

The cardinality of a power set is \(2^{|A|}\).

An example of this is the power set of \(\{1,2,3\}\) is \(\{\emptyset, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\}\}\).

What is important to remember is that the power set of a power set is the original set. This is because the power set of a set is the set of all subsets of a set. So the power set of the power set is the set of all subsets of all subsets of a set. This is the original set.

The cartesian product is the set of all ordered pairs of elements from two sets. We denote this as \(A \times B\). In other words, the cartesian product is the set of all possible combinations of elements from two sets. A more rigorous definition of this is as follows:

\[ A \times B \equiv \{(a,b) \mid a \in A \land b \in B\} \]

The cardinality of the cartesian product is \(|A| \times |B|\).

An example of this is the cartesian product of \(\{1,2\}\) and \(\{3,4\}\) is \(\{(1,3), (1,4), (2,3), (2,4)\}\).

The relation of the Cartesian product to the power set is that the power set of a cartesian product is the cartesian product of the power sets. This is because the power set of a set is the set of all subsets of a set. So the power set of the cartesian product is the set of all subsets of all ordered pairs of elements from two sets. This is the cartesian product of the power sets. A mathematical proof of this is as follows:

\[ P(A \times B) = \{C \mid C \subseteq A \times B\} = \{C \mid C \subseteq \{(a,b) \mid a \in A \land b \in B\}\} = \{C \mid C \subseteq \{(a,b) \mid a \in P(A) \land b \in P(B)\}\} = P(A) \times P(B) \]

Or simply: \(P(A \times B) = P(A) \times P(B)\).

Set operations are operations that can be performed on sets. The most common set operations are union, intersection, difference, and complement.

It is important to remember that if we have an expression like \(A \subsete A \cup B\), something that could be tricky is that the order of operations is not the same as in arithmetic. In arithmetic, we would do the multiplication and division first, then addition and subtraction. In set operations, we do the complement first, then the difference, then the intersection, and finally the union. So the expression \(A \subsete A \cup B\) would be read as \(A \subsete (A \cup B)\).

Once again, the order of operations for sets is:

1. Complement
2. Difference
3. Intersection
4. Union

Simply explained, the union of two sets is the set of all elements that are in either set. We denote this as \(A \cup B\). A more rigorous definition of this is as follows:

\[ A \cup B \equiv \{x \mid x \in A \lor x \in B\} \]

And using quantifiers:

\[ \forall ((x \in A \cup B) \equiv (x \in A \lor x \in B)) \]

The cardinality of the union is \(|A| + |B| - |A \cap B|\). The reason why we have to subtract the cardinality of the intersection is because the intersection is counted twice. Once in \(A\) and once in \(B\).

An example of this is the union of \(\{1,2\}\) and \(\{2,3\}\) is \(\{1,2,3\}\). The reason why this is the union is because \(1 \in A\), \(2 \in A\), \(2 \in B\), and \(3 \in B\). So \(1,2,3\) are all in the union.

The intersection of two sets is the set of all elements that are in both sets. We denote this as \(A \cap B\). A more rigorous definition of this is as follows:

\[ A \cap B \equiv \{x \mid x \in A \land x \in B\} \]

The cardinality of the intersection is \(|A \cap B|\). What is important to remember is that the intersection of a set with itself is the set itself. This is because the intersection of a set with itself is the set of all elements that are in the set and the set itself. So the intersection of a set with itself is the set itself.

An example of this is the intersection of \(\{1,2\}\) and \(\{2,3\}\) is \(\{2\}\). The reason why this is the intersection is because \(2 \in A\) and \(2 \in B\). So \(2\) is in the intersection.

The difference of two sets is the set of all elements that are in the first set but not the second set. We denote this as \(A \setminus B\). A more rigorous definition of this is as follows:

\[ A \setminus B \equiv \{x \mid x \in A \land x \notin B\} \]

A visual representation of this is as follows:

The cardinality of the difference is \(|A \setminus B|\) or \(|A| - |A \cap B|\). The reason why we have to subtract the cardinality of the intersection is because the intersection is counted twice. Once in \(A\) and once in \(B\).

An example of this is the difference of \(\{1,2\}\) and \(\{2,3\}\) is \(\{1\}\). The reason why this is the difference is because \(1 \in A\) and \(1 \notin B\). So \(1\) is in the difference.

The complement of a set is the set of all elements that are not in the set. We denote this as \(A^c\). A more rigorous definition of this is as follows:

\[ A^c \equiv \{x \mid x \notin A\} \]

In terms of the universal set, the complement of a set is the set of all elements that are not in the set and are in the universal set. It is denoted as \(A^c = U \setminus A\). A more rigorous definition of this is as follows:

\[ A^c \equiv \{x \mid x \in U \land x \notin A\} \]

The cardinality of the complement is \(|U| - |A|\). The reason why we have to subtract the cardinality of the set is because the set is counted twice. Once in \(U\) and once in \(A\).

An example of this is the complement of \(\{1,2\}\) is \(\{3,4\}\). The reason why this is the complement is because \(3 \in U\) and \(3 \notin A\). So \(3\) is in the complement. This of course depends on the universal set being \(\{1,2,3,4\}\).

We can relate sets to logical operations. The most common logical operations are conjunction, disjunction, and negation. We can relate these to sets as follows:

The reason why we can do this is that the definition of a set, is based on a predicate. So we can relate the set to the predicate and the predicate to the logical operation. For example, the definition of a set is as follows:

\[ A \equiv \{x \mid x \in A\} \]

So we can relate the set to the predicate as follows:

\[ A \equiv \{x \mid x \in A\} \equiv \{x \mid p(x)\} \]

If \(f(a) = b\), then we call \(a\) the pre-image and \(b\) the image of \(f\). We call \(A\) the domain of \(f\) and \(B\) the codomain of \(f\). We call \(f(A)\) the range of \(f\).

The main difference between the codomain and the range is that the codomain is the set of all possible images of \(f\) and the range is the set of all images of \(f\).

A function is one-to-one if each element in the range is assigned to a unique element in the domain. We denote this as \(f: A \rightarrow B\) is one-to-one. A more rigorous definition of this is as follows:

\[ f: A \rightarrow B \text{ is one-to-one } \equiv \forall a_1, a_2 \in A \land f(a_1) = f(a_2) \implies a_1 = a_2 \]

or simply: \(f(a_1) = f(a_2) \implies a_1 = a_2\).

If we want to check if a functions is one-to-one, we have to test if \(f(a_1) = f(a_2) \implies a_1 = a_2\) for all \(a_1, a_2 \in A\). If this is true for all \(a_1, a_2 \in A\), then the function is one-to-one.

A function is onto if each element in the codomain is assigned to an element in the domain. We denote this as \(f: A \rightarrow B\) is onto. This is to say that for each element in the codomain, there is an element in the domain that maps to it. A more rigorous definition of this is as follows:

\[ f: A \rightarrow B \text{ is onto } \equiv \forall b \in B \exists a \in A \land f(a) = b \]

or simply: \(\forall b \in B \exists a \in A \land f(a) = b\).

To see if a function is onto, we have to test if \(\forall b \in B \exists a \in A \land f(a) = b\). If this is true for all \(b \in B\), then the function is onto. For example if \(f: \{1,2\} \rightarrow \{1,2,3\}\), then \(f(1) = 1\), \(f(2) = 2\) and \(f(3) = 3\). So \(f\) is onto. If \(f: \{1,2\} \rightarrow \{1,2\}\), then \(f(1) = 1\), \(f(2) = 2\) and \(f(3) = 3\). So \(f\) is not onto. In this case, the function is not onto because \(3\) is not assigned to an element in the domain.

We can combine functions to create composite functions. We can combine functions by applying one function to the output of another function. We denote this as \(f \circ g\). We can also call this function composition. A more rigorous definition of this is as follows:

\[ f \circ g \equiv \{f(g(a)) \mid a \in A\} \]

If the codomain of \(g\) is the domain of \(f\), then we can combine \(g\) and \(f\) to create a composite function. We denote this as \(f \circ g: A \rightarrow C\).

When it comes to functions properties after composition we have the following properties:

1. \(f \circ g\) is one-to-one if \(f\) is one-to-one and \(g\) is one-to-one
2. \(f \circ g\) is onto if \(f\) is onto and \(g\) is onto

If some of the functions are not one-to-one or onto, then the composite function is not one-to-one or onto.

An inverse function is a function that undoes the effects of another function. We denote this as \(f^{-1}\). The definition is as follows:

\[ f^{-1} \equiv \{a \mid f(a) = b\} \]

If \(f\) is one-to-one and onto, then \(f^{-1}\) is also one-to-one and onto.

A partial function is a function that is not one-to-one or onto. We denote this as \(f: A \rightarrow B\) is a partial function. Definition:

\[ f: A \rightarrow B \text{ is a partial function } \equiv \exists a_1, a_2 \in A \land f(a_1) = f(a_2) \land a_1 \neq a_2 \]

or simply: \(\exists a_1, a_2 \in A \land f(a_1) = f(a_2) \land a_1 \neq a_2\). If this is true for some \(a_1, a_2 \in A\), then \(f\) is a partial function.

1. Let \(f: \mathbb{R} \rightarrow \mathbb{R}\) be defined by \(f(x) = x^2\). Is \(f\) one-to-one? Is \(f\) onto? Is \(f\) a partial function?

   Solution

   \(f\) is one-to-one because \(f(x) = f(y) \implies x = y\). \(f\) is not onto because \(f(x) = x^2\) and \(x^2\) is not in the domain. \(f\) is not a partial function because \(f(x) = f(y) \implies x = y\).

2. Let \(f: \mathbb{R} \rightarrow \mathbb{R}\) be defined by \(f(x) = x^2\). Is \(f^{-1}\) one-to-one? Is \(f^{-1}\) onto? Is \(f^{-1}\) a partial function?

   Solution

   \(f^{-1}\) is one-to-one because \(f^{-1}(x) = f^{-1}(y) \implies x = y\). \(f^{-1}\) is onto because \(f^{-1}(x) = x^2\) and \(x^2\) is in the domain. \(f^{-1}\) is not a partial function because \(f^{-1}(x) = f^{-1}(y) \implies x = y\).

3. Let \(f: \mathbb{R} \rightarrow \mathbb{R}\) be defined by \(f(x) = x^2\). Is \(f \circ f\) one-to-one? Is \(f \circ f\) onto? Is \(f \circ f\) a partial function?

   Solution

   \(f \circ f\) is one-to-one because \(f\) is one-to-one and \(f\) is one-to-one. \(f \circ f\) is onto because \(f\) is onto and \(f\) is onto. \(f \circ f\) is not a partial function because \(f \circ f\) is one-to-one and \(f \circ f\) is onto.

4. Let \(f: \mathbb{R} \rightarrow \mathbb{R}\) be defined by \(f(x) = x^2\). Is \(f \circ f^{-1}\) one-to-one? Is \(f \circ f^{-1}\) onto? Is \(f \circ f^{-1}\) a partial function?

   Solution

   \(f \circ f^{-1}\) is one-to-one because \(f\) is one-to-one and \(f^{-1}\) is one-to-one. \(f \circ f^{-1}\) is onto because \(f\) is onto and \(f^{-1}\) is onto. \(f \circ f^{-1}\) is not a partial function because \(f \circ f^{-1}\) is one-to-one and \(f \circ f^{-1}\) is onto.

An arithmetic sequence is a sequence where the difference between two consecutive terms is constant. We denote this as \(\{a_n \mid n \in \mathbb{N}\}\) where \(a_n = a_1 + (n-1)d\) for some \(a_1, d \in \mathbb{R}\). We can also write this as \(a_n = a_1 + nd\), where \(n\) is the nth term of the sequence and \(d\) is the common difference.

An arithmetic sequence is defined by the following properties:

1. \(a_n = a_1 + (n-1)d\)
2. \(a_n = a_1 + nd\)

This sequence can also be thought of as a linear function. We can write this as \(a_n = f(n)\) where \(f(n) = a_1 + (n-1)d\). The main elements of a sequence are the first term and the common difference.

The expansion for the arithmetic sequence is as follows:

A geometric sequence is a sequence where the ratio between two consecutive terms is constant. We denote this as \(\{a_n \mid n \in \mathbb{N}\}\) where \(a_n = a_1 r^{n-1}\) for some \(a_1, r \in \mathbb{R}\). We can also write this as \(a_n = a_1 r^n\), where \(n\) is the nth term of the sequence and \(r\) is the common ratio.

An expansion of such as sequence can look something like this:

A recurrence relation is a sequence that is defined by a formula. We denote this as \(\{a_n \mid n \in \mathbb{N}\}\) where \(a_n = f(a_{n-1})\) for some \(f: \mathbb{R} \rightarrow \mathbb{R}\). It takes the previous term and applies a function to it to get the next term.

We can be told to find the closed formula for a sequence. This is a formula that can be used to find the nth term of a sequence.To do this, we need to use iteration and induction. We can use the following rules to find the closed formula for a sequence:

1. \(a_n = a_1 + (n-1)d\) where \(a_1, d \in \mathbb{R}\)
2. \(a_n = a_1 r^{n-1}\) where \(a_1, r \in \mathbb{R}\)
3. \(a_n = f(a_{n-1})\) where \(f: \mathbb{R} \rightarrow \mathbb{R}\)
4. \(a_n = f(a_{n-1}, a_{n-2})\) where \(f: \mathbb{R} \times \mathbb{R} \rightarrow \mathbb{R}\)

In short, we need to find the pattern in the sequence and use that to find the closed formula. A closed formula should be defined only in terms of \(n\).

We can use divisibility rules to determine if a number is divisible by another number. The rules are as follows:

1. If \(a\) divides both \(b\) and \(c\), then \(a\) divides \(b+c\). Expression: \(a \mid b \land a \mid c \Rightarrow a \mid (b+c)\)
2. If \(a\) divides \(b\), then \(a\) divides any multiple of \(b\). Expression: \(a \mid b \implies a \mid bm\) for some \(m \in \mathbb{N}\)
3. If \(a\) divides \(b\) and \(b\) divides \(c\), then \(a\) divides \(c\). Expression: \(a \mid b \land b \mid c \Rightarrow a \mid c\)

We can use the following rules to perform modular arithmetic:

1. \(a \equiv b \pmod{m} \land c \equiv d \pmod{m} \Rightarrow a+c \equiv b+d \pmod{m}\)
2. \(a \equiv b \pmod{m} \land c \equiv d \pmod{m} \Rightarrow ac \equiv bd \pmod{m}\)
3. \(a \equiv b \pmod{m} \land c \equiv d \pmod{m} \Rightarrow a-c \equiv b-d \pmod{m}\)
4. \(a \equiv b \pmod{m} \land c \equiv d \pmod{m} \Rightarrow a/c \equiv b/d \pmod{m}\)
5. \(a \equiv b \pmod{m} \land c \equiv d \pmod{m} \Rightarrow a^c \equiv b^d \pmod{m}\)

The difference between congruency and the modulo operation is that congruency is a relation between two numbers, while the modulo operation is an operation that returns a number. For example, \(a \equiv b \pmod{m}\) is a relation between \(a\) and \(b\), while \(a \pmod{m}\) is an operation that returns a number.

We can find the inverse of a modulo by using the following equation: \(a \cdot a^{-1} \equiv 1 \pmod{m}\). In other words, if we multiply the inverse of a modulo by the modulo, we get 1 modulo \(m\).

To find the inverse of a modulo, we can use the Extended Euclidean Algorithm. This algorithm is as follows:

1. Set \(a = m \cdot q + r\) where \(q\) is the quotient and \(r\) is the remainder
2. Set \(b = a \cdot q + r\) where \(q\) is the quotient and \(r\) is the remainder
3. Repeat step 2 until \(r = 0\)
4. The inverse of \(m\) modulo \(a\) is \(q\) where \(q\) is the quotient of the last step

For example, if we want to find the inverse of 3 modulo 7, we can use the Extended Euclidean Algorithm as follows:

1. \(7 = 3 \cdot 2 + 1\)
2. \(3 = 1 \cdot 3 + 0\)
3. \(r = 0\) so we stop
4. The inverse of 3 modulo 7 is 3

1. \(2 \equiv 3 \pmod{5}\)

   Solution: False, 2 is not congruent to 3 modulo 5

2. \(3 \equiv 4 \pmod{5}\)

   Solution: False, 3 is not congruent to 4 modulo 5

3. \(4x \equiv 7 \pmod{5}\)

   Solution: This is true when \(x = 0.5\) because \(4(0.5) \equiv 7 \pmod{5}\) is true.

4. \(x \equiv 3 \pmod{5} \land x \equiv 4 \pmod{5}\)

   Solution: This is not true because \(3 \not\equiv 4 \pmod{5}\) so \(x \not\equiv 3 \pmod{5} \land x \not\equiv 4 \pmod{5}\)

Practice problems using powers of modular arithmetic:

1. \(2^3 \equiv 8 \pmod{5}\)

   Solution: This is true because \(2^3 = 8 \equiv 8 \pmod{5}\)

The complexity of an algorithm is given by the relation between the input size and the number of steps required to solve the problem. We can use the following notations to describe the complexity of an algorithm:

\(O(n)\)

This notation describes the worst case scenario for an algorithm. This means that the algorithm will take at least this amount of time to solve the problem.

\(\Omega(n)\)

This notation describes the best case scenario for an algorithm. This means that the algorithm will take at most this amount of time to solve the problem.

\(\Theta(n)\)

This notation describes the average case scenario for an algorithm. This means that the algorithm will take this amount of time to solve the problem.

We will not need omega and theta notation for the exam, but it is good to know.

Big O notation is used to describe the worst case scenario for an algorithm. We can use the following rules to determine the complexity of an algorithm:

The idea of this notation is that we can use it to compare the complexity of different algorithms. For example, if we have two algorithms that solve the same problem, we can use big O notation to determine which algorithm is better. If one algorithm is \(O(n)\) and the other is \(O(n^2)\), then the first algorithm is better than the second algorithm.

Contrary to intuition, to solve a large problem you should always use the most efficient algorithm, but for a smaller size, higher complexity algorithms are better.

The least common multiple of two numbers is the smallest number that is divisible by both numbers. We can easily find this if we know the factorizations of each number. Another way to find the least common multiple is to use the following formula:

\[ \text{lcm}(a, b) = \frac{a \cdot b}{\text{gcd}(a, b)} \]

If we know the number of records in a database and who much space they take up, swell as the starting position, we can use the following formula to determine the position of the nth record:

\[ \text{position} = \text{starting position} + \text{record size} \cdot (n - 1) \]

If we want to store some records into a database, we can use a hash function which will map each record to a unique location in the database. This is done by taking the record and applying a hash function to it. The hash function will then return a number which is the location of the record in the database. We might use the \(mod\) operator to create a hash function.

If each entry has some numerical value we can use \(mod 10\) to map it to a location in the database. This method is not very practical because we might get some sort of collision. A collision is when two records map to the same location in the database. To avoid collisions we can make use of a secondary hash function.

Asymmetric encryption is a method of encryption that uses two keys. One key is used to encrypt the message and the other key is used to decrypt the message. The two keys are called the public key and the private key. The public key is used to encrypt the message and the private key is used to decrypt the message. The public key is made public and the private key is kept secret.

A relation is reflexive if it contains the ordered pair \((x, x)\) for every element \(x\) in the set. We can use the following notation to represent a reflexive relation:

\[ R = \{(x, y) \mid x \in A \land y \in A \land x = y\} \]

As a matrix, it would look like this:

A relation is symmetric if it contains the ordered pair \((x, y)\) for every ordered pair \((y, x)\). We can use the following notation to represent a symmetric relation:

\[ R = \{(x, y) \mid x \in A \land y \in A \land (y, x) \in R\} \]

As a matrix, it would look like this (or any other symmetric relation):

If a relation is antisymmetric, it will it will contain some order pair \((x,y)\) but not \((y,x)\) for every ordered pair \((x,y)\). We can use the following notation to represent an antisymmetric relation:

\[ R = \{(x, y) \mid x \in A \land y \in A \land (x, y) \in R \land (y, x) \notin R\} \]

A relation is transitive if it contains the ordered pair \((x, z)\) for every ordered pair \((x, y)\) and \((y, z)\). We can use the following notation to represent a transitive relation:

\[ R = \{(x, z) \mid x \in A \land z \in A \land (x, y) \in R \land (y, z) \in R\} \]

What its saying is that the relation will be transitive if for every \(n\) steps, we can get from \(x\) to \(z\) in just one step.

We can combine two relations to create a composite relation. The composite relation will contain the ordered pair \((x, z)\) if the first relation contains the ordered pair \((x, y)\) and the second relation contains the ordered pair \((y, z)\). We can use the following notation to represent a composite relation:

\[ R \circ S = \{(x, z) \mid x \in A \land z \in A \land (x, y) \in R \land (y, z) \in S\} \]

We can us powers of a binary relation to represent the composite relation. The $n$th power of a binary relation will contain the ordered pair \((x, z)\) if the relation contains the ordered pair \((x, y)\) and the relation contains the ordered pair \((y, z)\) \(n\) times.

Vocabulary

This is a set of symbols which we use to represent the language of the grammar. The vocabulary of the grammar is denoted by \(V\).

Grammar

This is a set of rules that can be used to generate strings. The grammar is denoted by \(G\). It is a combination of the vocabulary. By using grammar and vocabulary, we can generate strings which are part of formal language.

An example of a railroad diagram is the following:

We write the railroad diagram as follows (not the one above):

<expression> ::= <term> | <term> "+" <expression>
<term>       ::= <factor> | <factor> "*" <term>
<factor>     ::= <constant> | <variable> | "(" <expression> ")"
<variable>   ::= "x" | "y" | "z"
<constant>   ::= <digit> | <digit> <constant>
<digit>      ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

more coming soon