Discrete Mathematics (CS 205)

These are notes for the version of the class which is being taught by professor Minsky in the Spring of 2016.

Class Information

In this class we use the book “Discrete Math” by Kenneth Rosen, 7th Edition. We cover chapters, 1, 2, 5, 9, and 13.

Propositional Logic

At first we’re going to study propositional logic. This is a type of logic which uses statements called propositions to convey truth (or falsity).

Examples of propositions:

The sky is blue

The internet connection is poor.

In these two statements we can clearly determine whether they are true or false. This is the key to propositions. They are only true or false.

Typically we map True/False values to 1/0 respectively.

We can also create compound propositions! These are propositions which are made of two (or more) propositions by utilizing binary logical operators. There is also a unary operator which we will cover as well.

Below is a table of the basic binary operators which shows their basic meanings. We will go into more deatil shortly.

AND: \(\land\)

This operator tells us that the entire should only be true if and only if the statements which are being operated on are both true. That is it can only be true if both propositions are true as well.

OR: \(\lor\)

This operator will convey truth if either one or both propositions are true. That is it can only be false if both of is propositions which it is comprised of are false.

Implication

Implication is a bit trickier, but what it tells us is that If one statement is true, then the next statement should be true as well. The order in implication matters, whereas in the AND and OR operators it does not.

So then for an implication statement to be false, the statements which comes first i.e. \(p \implies q\), \(p\) would have to be true, and \(q\) would have to be false for the entire statement \(p \implies q\) to be false.

Exclusive Or: \(\oplus\)

Exclusive Or is similar to the regular Or, but in this case, we exclude the case which both statements are true. This means that in this statement, if both statements are true, then the result is false.

Unary Operator: NOT, \(\neg\)

This operator only requires a single proposition and will return the opposite value of a proposition. That is if we have a true statements, negated would be false. And then a false statemented negated would be true.

Sample Truth Table

The above truth table showcases the possible combinations of truth values for two different propositions whether they are true are false.

Now applying the same logic (ha, get it??) we can compound even more propositions together using these operators

One thing that might be interesting to note, is that if we want to create truth tables for multiple propositions (2, 3, 4, etc… different propositions) That the number of possible rows in our table increases exponentially as the number of propositions increases.

This occurs because for every new proposition we add another possible combination of 0 or 1 to every already present combination

Simply put we’ll call this the counting principle. In terms of truth tables:

The total number of rows in a truth table is equal to \(2^n\) where \(n\) is the number of propositions we have.

Definition: Tautology

A Tautology is a propositional statement (compound or not) which will always evaluate to true.

Propositional Equivalencies

In propositional logic we find that it is actually possible to change the form of some propositions to equivalents which might make it easier to evaluate statements.

Below is a table which highlights these equivalencies. Note that T and F represent True and False. They are not propositions

DeMorgan’s Laws

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

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

Propositional Satisfiability

A compound proposition is satisfiable if there is an assignment of truth values to its variables that makes it true.

In other words, if we can assign values to the variables which cause the statement to be true, then it is satisfiable.

Predicates and Quantifiers

Predicates are statements which involve variable such as \(x > 3\) and \(x = 3 + y\) or even statements like: “computer \(x\) is under attach by an intruder”.

The statements all have two different parts:

• Subject
• Predicate

In a statement like “\(x\) is greater than 4”, the subject is \(x\), and the predicate is “greater than 4”

We can call this statement a propositional function, which we can replace by \(P(x)\). Here \(P\) denotes the predicate “x is greater than 4”.

A statement of the form \(P(x_1 ,x_2 ,...,x_n )\) is the value of the propositional function P at the n-tuple\((x_1 ,x_2 ,...,x_n )\), and P is also called an n-place predicate or a n-ary predicate.

Preconditions and Postconditions

Predicates are also used to establish the correctness of computer programs, that is, to show that computer programs always produce the desired output when given valid input.

The statements that describe valid input are known as preconditions. The condititions of that the output should satisfy when the program has run are known as postconditions.

Quantifiers

Quantification is a way to create a proposition from a propositional function. Quantification expresses the extent to which a predicate is true over a range of elements.

In english, the words all, some, many, none, and few are used in quantifications.

There are two types of quantifications which we will cover

• Universal quantification
• Existential quantification

The domain of discourse often just referred to as the domain, is what we call all of the values in a specified domain.

Below is a table describing the two basic quantifiers

The existential quantification of P(x) is the proposition

There exists an element x in the domain such that P(x).

We use the notation \(\exists\ x\ P(x)\) for the existential quantification of P(x). Here \(\exists\) is called the existential quantifier.

The Uniqueness Quantifier

The uniqueness quantifier, denoted by \(\exists!\) in \(\exists!\ x \ P(x)\), states that “there exists a unique x, such that P(x) is true”

Quantifiers with Restricted Domains

Sometimes it occurs that we’ll want to restrict which numbers can be valid for a quantifier. In this regard we can say that if we give our quantifier the domain \(D\) of all real numbers, then we can restrict our statement to certain quantities or portions of such.

Example:

\[\forall x < 0\ (x^2 > 0)\]

This statement restricts the domain \(D\) of all real numbers by specifying “for all x that are less than 0”

Precedence of Quantifiers

The quantifiers \(\forall\) and \(\exists\) have higher precedence than all logical operators from the propostional logic that were covered before.

That is given the statement \(\forall x P(x) \lor Q(x) \equiv (\forall x P(x)) \lor Q(x)\)

Binding Variables

When a quantifier is used on a variable, we call that variable then bound. If a variable is not bound we tend to call it free.

Example in the statement \(\exists x (x + y = 1)\), we say that x is bound and y is free

Negating Quantified Expressions

These rules for negations of quantifiers are called De Morgan’s Laws for Quantifiers

Using Quantifiers in System Specifications

We won’t go into much detail here, but take this example for what it represents.

“Every mail message larger than one megabyte will be compressed”

Equivalent Representation:

\[\forall m (S(m, 1) \implies C(m))\]

Section 1.5 - Nested Quantifiers

Nested Quantifiers are where one quantifier is within the scope of another quanitifier.

Example:

\[\forall x \exists y (x + y = 0)\]

The english equivalent of this statement is: “For every x there is a value of y in our domain where (x + y) is equal to 0.

Another, more complex example. Translating to English:

\[\forall x \forall y ((x > 0) \lor (y < 0) \implies (xy < 0))\]

Translated:

“For real numbers x and y, if x is positive and y is negative, then xy is negative”

Sometimes when evaluating these types of statements it is easy to think in terms of nested loops (programming)

The Order of Quantifiers

The order of the quantifiers in a statement is important unless all of the quantifiers are universal or all existential quantifiers.

Take these two statements:

and

While both very similar they do not translate to the same thing.

The first one translates to:

“There is a real number y such that for every real number x, Q(x, y)”

Whereas the latter is:

“For every real number x there is a real number y such that Q(x, y)”

Quantifications of Two Variables

Translating Mathematical Statements into Statements Involving Nested Quantifiers

Mathematical statements expressed in English can be translated into logical expressions.

Example: “The sum of two positive integers is always positive”

\[\forall x \forall y ((x > 0) \land (y > 0) \implies (x + y > 0))\]

Note that if we could also simply just change the domain to be all positive integers instead of specifying x and y being greater than 0.

Relations

Given sets \(A\) and \(B\) each with a finite number of elements.

A binary relation from A to B is always a subset of \(A\times B\).

\(A\times B\) is the set which contains all unique combinations of pairs of elements from \(A\) and \(B\)

An example of a relation:

Given a set \(A\) of all students in a school. and \(B\) is the set of all courses offered. Then one example of a relation could be the binary relation of all students enrolled in Calculus 1

The above is an example relation, \(R\) which represents the students currently enrolled in calculus 1.

Functions as Relations

Recall that a function defined as \(f\) on a set \(A\) to a set \(B\) assigns one element from \(B\) to each element of \(A\)

However, relations are less rigid than functions and they can define many more relations on two sets than a function can.

Relations on a Set

A relation on a set , say \(A\), is a relation from \(A\) to \(A\).

In other words the relation on a set \(A\) is a subset of \(A\times A\)

Properties of Relations on Sets

Reflexive Relations

A relation, R, on a set \(A\) is called reflexive if \((a, a) \in R\) for every element \(a \in A\)

Symmetric Relations

A relation \(R\) on a set \(A\) is called symmetric if \((b, a) \in R\) whenever there is a pair \((a, b)\in R\) for all a and b in \(A\)

Antisymmetric Relation

A relation is antisymmetric if for \((a, b) \in R\) where \(a\neq b\) implies that \((b, a) \not\in R\)

Using quantifiers, the formal definitions:

• Symmetric is: \(\forall a\forall b ((a, b) \in R \implies (b, a)\in R)\)
• Antisymmetric is: \(\forall a\forall b ((a, b) \in R \land (b, a)\in R \implies (a = b))\)

Transitive Relations

A relation \(R\) on a set \(A\) is called transitive if whenever \((a, b) \in R\) and \((b, c)\in R\), then \((a, c) \in R\) for all \(a, b, c \in A\)

Combining Relations

Because relations of two sets (A and B, or A, A) are simply subsets of the cross product of the two sets (\(A\times B\) or \(A\times B\)). Any two relations can be combined to form another relation.

Composite Relations

Let \(R\) be a relation from a set \(A\) to a set \(B\) and \(S\) is a relation from \(B\) to a set \(C\). The composite of \(R\) and \(S\) is the relation consisting of ordered pairs \((a, c)\) where \(a\in A\) and \(c\in C\), and for which there exists an element \(b\in B\) such that \((a, b) \in R\) and \((b, c)\in S\). We denote the composite of \(R\) and \(S\) by \(S \circ R\)

Example:

If \((1, 0) \in R\) and \((0, 5) \in S\) then \((1, 5) \in S \circ R\)

Powers With Relations

Given \(R\) is a relation on a set \(A\). The powers of \(R^n\), \(n = 1, 2, 3\dots\) are defied recursively by \(R^1 = R\) and that \(R^{n+1} = R^n \circ R\)

Transitivity Theorem

The relation \(R\) on a set \(A\) is transitive if and only if \(R^n \subset R\) for \(n = 1, 2, 3\dots\)

Representing Relations

Zero-One Matrices

One way to represent a relation is with an \(n\times n\) matrix.

The \(n\times n\) matrix simply has the following properties for each \(i, j\) entry \(m_{i,j}\):

Directed Graphs (Digraphs)

A directed graph, or digraph consists of a set of \(V\) vertices together with a set \(E\) of ordered pairs of elements of \(V\) called edges. The vertex \(a\) is called the initial vertex of the edge \((a, b)\). The vertex \(b\) is called the terminal vertex of the edge.

Closures

The closure of a relation \(R\) with respect to a certain property, P, is the relation obtained by adding the minimum number of ordered pairs to R to obtain the property, P.

In terms of a digraph representation of R:

• To find a reflexive closure, add loops for \((a, a) \in R\)
• To find the symmetric closure, add arcs in the opposite direction
• To find the transitive closure, if there is a path from a to b, add an arc from b to c.

Power Set

The power set is an interesting concept.

The power set is a set of all subsets from a specific set, say, \(A\).

The cardinality of the power set is \(2^n\) where \(n\) is the number of elements within the set.