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.
In this class we use the book “Discrete Math” by Kenneth Rosen, 7th Edition. We cover chapters, 1, 2, 5, 9, and 13.
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.
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.
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 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. , would have to be true, and would have to be false for the entire statement to be false.
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,
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 where is the number of propositions we have.
A Tautology is a propositional statement (compound or not) which will always evaluate to true.
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
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 and or even statements like: “computer is under attach by an intruder”.
The statements all have two different parts:
In a statement like “ is greater than 4”, the subject is , and the predicate is “greater than 4”
We can call this statement a propositional function, which we can replace by . Here denotes the predicate “x is greater than 4”.
A statement of the form is the value of the propositional function P at the n-tuple, 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.
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
|Statement||When True||When False|
|is true for every||There is an for which is false|
|There is an x for which is true||is false for every .|
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 for the existential quantification of P(x). Here is called the existential quantifier.
The Uniqueness Quantifier
The uniqueness quantifier, denoted by in , 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 of all real numbers, then we can restrict our statement to certain quantities or portions of such.
This statement restricts the domain of all real numbers by specifying “for all x that are less than 0”
Precedence of Quantifiers
The quantifiers and have higher precedence than all logical operators from the propostional logic that were covered before.
That is given the statement
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 , we say that x is bound and y is free
Negating Quantified Expressions
|Negation||Equivalent Statement||When negation is true?||When false?|
|For every x, P(x) is false.||There is an x for which P(x) is true|
|There is an x for which P(x) is false||P(x) is true for every x|
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”
Section 1.5 - Nested Quantifiers
Nested Quantifiers are where one quantifier is within the scope of another quanitifier.
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:
“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:
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
|Statement||When True||When False|
|P(x, y) is true for every pair x, y.||There is a pair x, y for which P(x, y) is false|
|For every x there is a y for which P(x, y) is true||There is an x such that P(x, y) is false for every y|
|There is an x for which P(x, y) is true for every y||For every x there is a y for which P(x, y) is false.|
|There is a pair x, y for which P(x, y) is true||P(x, y) is false for every pair x, y|
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”
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.
Given sets and each with a finite number of elements.
A binary relation from A to B is always a subset of .
is the set which contains all unique combinations of pairs of elements from and
An example of a relation:
Given a set of all students in a school. and 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, which represents the students currently enrolled in calculus 1.
Functions as Relations
Recall that a function defined as on a set to a set assigns one element from to each element of
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 , is a relation from to .
In other words the relation on a set is a subset of
Properties of Relations on Sets
A relation, R, on a set is called reflexive if for every element
A relation on a set is called symmetric if whenever there is a pair for all a and b in
A relation is antisymmetric if for where implies that
Using quantifiers, the formal definitions:
- Symmetric is:
- Antisymmetric is:
A relation on a set is called transitive if whenever and , then for all
Because relations of two sets (A and B, or A, A) are simply subsets of the cross product of the two sets ( or ). Any two relations can be combined to form another relation.
Let be a relation from a set to a set and is a relation from to a set . The composite of and is the relation consisting of ordered pairs where and , and for which there exists an element such that and . We denote the composite of and by
If and then
Powers With Relations
Given is a relation on a set . The powers of , are defied recursively by and that
The relation on a set is transitive if and only if for
One way to represent a relation is with an matrix.
The matrix simply has the following properties for each entry :
Directed Graphs (Digraphs)
A directed graph, or digraph consists of a set of vertices together with a set of ordered pairs of elements of called edges. The vertex is called the initial vertex of the edge . The vertex is called the terminal vertex of the edge.
The closure of a relation 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
- 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.
The power set is an interesting concept.
The power set is a set of all subsets from a specific set, say, .
The cardinality of the power set is where is the number of elements within the set.