Discrete Mathematics - Midterm 1

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

It flips the truth value of a proposition.

\[ \neg p, \bar{A} \]

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

\[ p \land q, AB \]

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

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

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

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. \(\neg\)
2. \(\land\)
3. \(\lor\)
4. \(\to\)
5. \(\Leftrightarrow\)

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

\[ p \land \top \equiv p \]

\[ p \lor \bot \equiv p \]

\[ p \lor \top \equiv \top \]

\[ p \land \bot \equiv \bot \]

\[ p \lor p \equiv p \]

\[ p \land p \equiv p \]

\[ \neg ( \neg p) \equiv p \]

\[ p \lor q \equiv q \lor p \]

\[ p \land q \equiv q \land p \]

\[ (p \lor q) \lor r \equiv p \lor (q \lor r) \]

\[ (p \land q) \land r \equiv p \land (q \land r) \]

\[ 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 \lor (p \land q) \equiv p \]

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

\[ p \lor \neg p \equiv \top \]

\[ p \land \neg p \equiv \bot \]

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

Complex $\mathbb{C}

All complex numbers

\begin{array}{c} P(x) \text{ for all value of x within its domain} \\ \forall x P(x) \end{array}

Proving

We must show that \(P(x)\) holds true for all \(x\)

Disproving

It is sufficient to show one value of \(x \vert \neg P(x)\)

If \(x\) is empty

the proposition will always be False

\begin{array}{c} P(x) \text{ for at least one value of x within its domain} \\ \exists x P(x) \end{array}

Proving

It is sufficient to show at least one value if \(x \vert P(x)\)

Disproving

We must show that for all values of \(x\) it is true that \(\neg P(x)\)

If \(x\) is empty

the proposition will always be False.

This is a type of existential quantifier which allows for specification of the number of values for which the predicate is satisfiable.

\begin{array}{c} \text{There is exactly one } x \text{ such that } P(x) \\ \exists! x P(x) \end{array}

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

We can also restrict the domain of a quantifier by adding conditions after the quantifier and before the predicate.

\begin{array}{l} \forall x > 0 P(x) \\ \exists x \ne 0 P(x) \end{array}

If we have a finite domain for which we are evaluating a predicate, we can easily evaluate the value by simply proving all the possibilities.

If we want to negate a quantifier we must flip the outer quantifier and negate its inside.

\[ \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 a predicate with more than 1 variables, we need n quantifiers to fully instantiate the predicate. For example, given a predicate with 2 variables, we can instantiate in the following way:

\[ \forall x \forall y P(x,y) \]

For nested quantifiers, the order matters, this can be seen in example 2.

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

If an argument can establish some implication relationship between the premises and conclusion it is told to be valid.

• A valid argument implies a tautology

If the inference is valid, then \(p_1 \land p_2 \land \ldots \land p_n \to q \equiv \top\)

If an argument is valid or not, can only be determined using the logical form.

\begin{array}{r} p \to q \\ p \\ \hline \therefore q \end{array}

Logic is not quite so concerned with soundness as it is with validity.

Sound Argument

An argument for which all premises are true and is valid

Un-sound Argument

An argument for which not all premises are true

\begin{array}{r} p \\ p \to q \\ \hline q \end{array}

1. If p is true, then q is true
2. p is true
3. Therefore q is true

\begin{array}{r} \neg q \\ p \to q \\ \hline \neg p \end{array}

\begin{array}{r} p \to q \\ q \to r \\ \hline p \to r \end{array}

\begin{array}{r} p \lor q \\ \neg p \\ \hline q \end{array}

\begin{array}{r} p \\ \hline p \lor q \end{array}

\begin{array}{r} p \land q \\ \hline p \end{array}

\begin{array}{r} p \\ q \\ \hline p \land q \end{array}

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

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

\begin{array}{r} P(c) \text{ for an arbitrary c} \\ \hline \therefore \forall x P(x) \end{array}

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

\begin{array}{r} P(c) \text{ for an arbitrary c} \\ \hline \therefore \exists x P(x) \end{array}

\begin{align} (p \lor q) \to (r \land s) & \quad \text{Premise} \\ r \to t & \quad \text{Premise} \\ \neg t & \quad \text{Premise} \\ \neg r & \quad \text{Modus Tollens from 2 and 3} \\ (\neg p \land \neg q) & \quad \text{Modus Tollens from 4 and 1} \\ \neg p & \quad \text{Simplification of 5} \end{align}

Theorem

A statement we can prove using some axioms

Proof

A valid argument/set of arguments that demonstrate a theorem/proposition

Axioms

Statements which are assumed to be true, they are in the most basic form

Lemma

A small proof that is an element of another larger proof

We want to prove "If p, then q". This is done by assuming that the premise is true and then proving that the consequence is also true.

1. We assume \(p\) to be true.
2. By applying the laws of inference, we deduce \(q\) from \(p\).

If we cannot arrive to the consequence using just the premise, we can use contraposition, which states that \((p \to q) \equiv (\neg q \to \neg p)\).

1. We assume that \(\neg q\) is true
2. We find a way to infer that \(\neg p\) is true
3. Since this verifies the contrapositive, we have proved that \(p \to q\)

If we are saying that \(p \to q\) is True, we can assume that:

1. \(p\) is False (Vacuous proof)
2. \(q\) is True (Trivial proof)

It is enough to prove just one of these (as long as we do not accept the premise being True) we can prove the condition to be True.

This can be used to demonstrate any statement \(p\). We say that \(\neg p\) implies a contradiction. A nicer way to think about this is by the following:

\[ \neg p \to \bot \equiv \neg (\neg p) \lor \bot \equiv p \lor \bot \equiv p \]

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.

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)\).

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.

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.

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.

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

\[ \forall x ((x \in A) \Leftrightarrow P(x)) \]

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.

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

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

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

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)\} \]

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