Block 1

Kursusgang 1:

1:
Proposition: is a declarative sentence (that is, a sentence that declares a fact) that is either true or false,
but not both.

Example of proposition:

1+1=2 , true
2+2=3 , false

Propositional variables (or sentential variables): is variables that represent propositions.

Atomic propositions: is propositions that cannot be expressed in terms of simpler propositions.

The area of logic which deals with propositions are called propositional calculus or propositional logic.

New propositions, called compound propositions, are formed from existing propositions using logical
operators.

Definition 1: Let p be a proposition. The negation of p, denoted by ¬ p (also denoted by p), is the
statement

“It is not the case that p”

The proposition ¬ p is read “not p.” The truth value of the negation p, ¬ p , is the opposite of the truth
value of p.

Simplified - Negation: not the case (negative)

p ¬p
T F
F T

Connectives: are logical operators that are used to form new propositions from two or more existing
operators.
Definition 2: Let p and q be propositions. The conjunction of p and q, denoted by p ∧q , is the proposition
“p and q.” The conjunction p ∧q is true when both p and q are true and is false otherwise

Simplified - Conjunction: and ( p ∧q)

p q p ∧q
T T T
T F F
F T F
F F F

Definition 3: Let p and q be propositions. The disjunction of p and q, denoted by p ∨q , is the proposition “p
or q.” The disjunction p ∨q is false when both p and q are false and is true otherwise.

Simplified - Disjunction: or ( p ∨q)

p q p ∨q
T T T
T F T
F T T
F F F

Definition 4: Let p and q be propositions. The exclusive or of p and q, denoted by p q (or p XOR q), is the
proposition that is true when exactly one of the p and q is true and is false otherwise.

Simplified - Exclusive or: p or q is T, but not both ( p ⊕ q)

p q p⨁q
T T F
T F T
F T T
F F F

Definition 5: Let p and q be propositions. The conditional statement p →q is the proposition “if p, then q
.” The conditional statement p →q is false when p is true and q is false, and true otherwise. In the
conditional statement p →q , pis called the hypothesis (or antecedent or premise) and q is called the
conclusion (or consequence).
Simplified - Conditional statement (or implication): if p, then q . ( p → q)

p q p →q
 T T T
T F F
F T T
F F T

Three types of conditional statements:

Converse: p →q

Contrapositive: ¬ q →¬ p

Inverse: ¬ p → ¬q

Equivalent: When two compound propositions always have the same truth value, regardless of the truth
values of its propositional variables.

Biconditional: Let p and q be propositions. The Biconditional statement p ↔q is the proposition “ p if and
only if q .” The biconditional statement p ↔q is true when p and q have the same truth values and is false
otherwise. Biconditional statements are also balled bi-implications.

Simplified - Biconditional statements: p if and only if q ( p ↔q ).

p q p ↔q
T T T
T F F
F T F
F F T

1.3.1-1.3.3

Definition 1: A compound proposition that is always true, no matter what truth values of the propositional
variables that occur in it, is called tautology. A compound proposition that is always false is called
contradiction. A compound proposition that is neither a tautology nor a contradiction is called contingency.

Definition 2: The compound proposition p and q are called logically equivalent if p ↔q is a tautology. The
notation p ≡q denotes that p and q are logically equivalent.

Simplified - Logically equivalent: if two compound propositions p and q have the same truth
values for all possible cases.
De Morgans laws:

¬ ( p ∧q )=¬ p ∨ ¬q
¬ ( p ∨q )=¬ p ∧ ¬q

Proof of De Morgans law:

p q p ∨q ¬( p ∨q) ¬p ¬q ¬ p ∧¬ q
T T F F F F F
T F F F F T F
F T F F T F F
F F T T T T T

More Logical Equivalences on page 29

1.4.1-1.4.3
Predicate:

Statements involving variables such as x >3, x= y +3 , don’t tell us anything about true or false.

x >3 can be split up in different parts

x is the first part that has a variable.
is greater than3 is the last part, the predicate.

P( x ) is a propositional function, P at x . Once a value has been assigned to the variable x, the statement
P( x ) becomes a proposition and has a truth value. Does also count if you had more variables ( Q(x , y ) and
x and y were assigned variables).

Propositional function: P( x 1 , x 2 ,… , n n)

Preconditions: The statements that describe valid input

Postconditions: The conditions that the output should satisfy when the program has run

Quantification: expresses the extent to which a predicate is true over a range of elements.
Universal quantification: tells us that a predicate is true for every element under consideration

Definition 1: The universal quantification of P( x ) is the statement

“ P( x ) for all values of x in the domain.”

The notation ∀ xP(x) denotes the universal quantification for P( x ). Here ∀ is called the universal
quantifier. We read ∀ xP( x) as “for all ∀ xP( x) ” or “for every xP( x ).” An element for which P( x ) is false
is called a counterexample to ∀ xP(x) .

Existential quantification: tells us that there is one or more element under consideration for which a
predicate is true.

Definition 2: 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 ∃ xP (x) for the existential quantification of P( x ). Here ∃ is called the existential
quantifier. “For some”

Uniqueness quantifier: “There exists a unique x such that P( x ) is true” (∃! Or ∃1)

2.1.1-2.1.4
Sets:

Definition 1: a set is an unordered collection of distinct objects, called elements or members of the set. A
set is said to contain its elements. We write a ∈ A to denote that a is an element of the set A . The notation
a ∉ A denotes that a is not an element of the set A .
Elements are usually denoted with lowercase letters, whilst sets are denoted with uppercase letters.

Example of a set: {a , b , c , d }, a, b, c and d are the 4 elements in an unnamed set. Roster method.

These sets, each denoted using a boldface letter, play an important role in discrete mathematics:

N = { 0 , 1 ,2 , 3 , … }, the sets of all natural numbers

Z = { … ,−2 ,−1 , 0 ,1 , 2 ,… }, the set of all integers

Z+¿ ¿= { 1 , 2, 3 , … }, the set of all positive integers

Q = { p/q∨ p ∈ Z , q ∈ Z∧q ≠0 }, the set of all rational numbers
R , the set of all real numbers
+¿ ¿
R , the set of all positive real numbers
 C, the set of all complex numbers

An element in a set is separated a comma ({ N , Z ,Q , R } , the following set has 4 elements, each of which is
a set).

Datatype or type is the name of a set, together with a set of operations that can be preformedon objects
from that set.

Definition 2: Two sets are equal if and only if they have the same elements. Therefore, if A and B are sets,
then A and B are equal if and only if ∀ x ( x ∈ A ↔ x ∈ B ). We write A=B if A and B are equal sets.

Furthermore, it does not matter if an element is listed more than once, because they have the same
elements.

The Empty Set: There is a special set that contains no elements. This set is called the empty set or null set,
which is denoted by Ø or {} .

Singleton set: a singleton set is a set with one element, like {Ø } (this is a common confusion, but it is a
singleton set and not an empty set)

Venn Diagrams:

Sets can be represented graphically using Venn Diagrams. In Venn diagrams the universal set, U , which
contains all objects under consideration, is represented by a rectangle. Inside the rectangle, circles or other
geometrical objects are used to represent elements of the sets. Sometimes points are used to represent
the elements of the set.

Subsets:

Definition 3: The set A is a subset of B, and B is a superset of A , if and only if every element of A is also an
element of B. We use the notation A ⊆B to indicate that A is a subset of B. If, instead, we want to stress
that B is a superset of A , we use the equivalence notation B⊇ A . (So, A ⊆ B and B⊇ A are equivalent
statements.)

Rule 1: To show that A ⊆B , show that if x belongs to A then x also belongs to B.

Rule 2: To show that A ⊈ B , find a single x ∈ A such that x ∉ B

Theorem 1: For every set, S, ( i ) , Ø ⊆S and ( ii ) S ⊆ S .

Simplified: Theorem 1 shows that every nonempty set S is guaranteed to have at least two
subsets, the empty and the set S itself, that is, Ø ⊆ S and S ⊆S .

Proof of Theorem 1 (i): Let S be a set. To show that Ø ⊆ S , we must show that ∀ x( x ∈ Ø → x ∈ S) is
true. Because the empty set contains no elements, it follows that x ∈ Ø is always false. It follows that the
conditional statement x ∈ Ø → x ∈ S is always true because its hypothesis is always false and a conditional
statement with a false hypothesis is true.

Therefore ∀ x( x ∈ Ø → x ∈ S) is true, which completes the proof of (i)

Note: this is a vacuous proof.

When A is a subset to B but that A ≠ B , we write A ⊂B , to say that A is a proper subset of B.

For A ⊂ B to be true, it must be the case that A ⊆B and there must exist an element x of B that is not an
element of A . That is a proper subset of B if and only if

∀ x( x ∈ A → x ∈ B)∧ ∃ x ( x ∈ B ∧ x ∉ A)
Is true.

Rule 3: to show that two sets A and B are equal, show that A ⊆B and B⊆ A

Definition 4: Let S be a set. If there are exactly n distinct elements in S where n is a nonnegative integer,
we say that S is a finite set and that n is the cardinality of S is denoted by |S|.

Definition 5: A set is said to be infinite if it is not finite

2.2.1-2.2.3

Definition 1: let A and B be sets. The union of the sets A and B, denoted by A ∪ B , is the set that
contains those elements that are either in A or in B, or in both.

Simplified: A ∪ B= { x∨x ∈ A ∨ x ∈ B }

Definition 2: let A and B be sets. The intersection of the sets A and B, denoted by A ∩ B, is the set
containing those elements in both A and B.

Simplified: A ∩ B= { x∨x ∈ A ∧ x ∈ B }

Definition 3: Two sets are called disjoint if their intersection is the empty set.

Cardinality of a union of two finite sets:

| A ∪ B|=| A|+|B|−| A ∩ B|, the principle of inclusion-exclusion.

Definition 4: Let A and B be sets. The difference of A and B, denoted by A−B , is the set containing those
elements that are in A , but not in B. The difference of A and B is also called the complement of B with
respect to A .

Simplified: A−B={ x∨x ∈ A ∧ x ∉ B }

Once the universal set has been specified, the compliment of a set can be defined.

Definition 5: Let U be the universal set. The compliment of the set A , denoted by A , is the compliment of
A with respect to U . Therefore, the complement of the set A is U −A .
Simplified: A={ x ∈U ∨x ∉ A }
A−B= A ∩ B
Set identities

Table 1, page 136

Proof of A ∩ B= A ∪ B , page 137

Proof of A ∩ ( B∪C )=(A ∩B) ∪( A ∩C ), page 138

Methods of proving set identities table 3

Definition 6: The union of a collection of sets is the set that contains those elements that are members of at
least one set in the collection.

Simplified: A1 ∪ A 2 ∪ …∪ A n=¿ i=1 ¿ n A i

Definition 7: The union of a collection of sets is the set that contains those elements that are members of
all the set in the collection.

Simplified: A1 ∩ A 2 ∩ … ∩ A n=¿i=1¿ n Ai

Infinite family of sets

A1 ∪ A 2 ∪ …∪ A n ∪…=¿ i=1 ¿ ∞ Ai

A1 ∩ A 2 ∩ … ∩ A n ∩…=¿i=1¿ ∞ Ai

Kursusgang 2:
2.1.5-2.1.6
Power set:

Definition 6: Given a set S, the power set of S is the set of all subsets of the set S. The power set of S is
denoted by P( S).

Simplified - Power sets: A power set is the set containing all possible subsets.

Example: The power set P( {0 , 1 ,2 }) is the set of all subsets of {0 ,1 , 2} . Hence,

 P ( { 0 , 1,2 } )={ Ø , { 0 } , {1 } , { 2 } , {0 , 1 } , {1 , 2 } , {0,2 } , { 0 , 1 ,2 } }

|P ( n )|=2n

Cartesian Products:

Definition 7: The ordered n-tuple (a 1 , a2 , … , an ) is the ordered collection that a 1 as its first element, a 2 as
its second element, …, and a n as its nth element

Ordered pairs: 2 ordered n-tuples.

Definition 8: Let A and B be sets. The Cartesian product of A and B, denoted by A × B , is the set of all
ordered pairs (a , b), where a ∈ A and b ∈ B . Hence,

A × B= { ( a , b )∨a ∈ A ∧b ∈ B }

Definition 9: The Cartesian product of the sets A1 , A 2 ,… , An , denoted by A1 × A2 ×… × A n, is the set of

ordered n-tuples (a 1 , a2 , … , an ), where a i belongs to Ai for i=1 , 2 ,… , n. In other words,

A1 × A2 ×… × A n={ ( a1 , a2 , … , an )∨ai ∈ A i for i=1 , 2 ,… , n }

Cardinality of cartesian products: if | A|=m and |B|=n, then

| A × B|=m·n

2
A × A= A

An ={( a1 , a 2 , … , an ) ∨ai ∈ A for i=1 ,2 , … , n }

Relation:

9.1

Definition 1: Let A and B be sets. A binary relation from A to B is a subset of A × B .

 a R b=(a ,b) ∈ R
Definition 2: A relation on a set A is a relation from A to A .

Example: side 602

Reflexive:
Definition 3: A relation R on a set A is called reflexive, if (a , a)∈ R for every element a ∈ A .

Simplified: if it has (a , a) (( 1,1 ) , ( 2,2 ) ,(3 , 3) is reflexive because it’s the same)

Symmetric and antisymmetric:

Definition 4.1: A relation R is called symmetric if (b , a) ∈ R whenever (b , a) ∈ R , for all a , b ∈ A .

Simplified - Symmetric: if (a , b) is also (b , a) (( 1,1 ) , ( 1,2 ) ,(2,1) is symmetric)

Definition 4.2: A relation R on a set A such that for all a , b ∈ A , if ( a , b ) ∈ R and ( b , a ) ∈ R , then a=b is
called antisymmetric.

Simplified - Antisymmetric:

Transitive:
Definition 5: A relation R on a set A is called transitive if whenever (a , b)∈ R and (b , c )∈ R , then
(a , c )∈ R, for all, a , b , c ∈ R

Definition 6: Let R be a relation from a set A to a set B and S a relation from B to a set C . The composite
of R and S is the relation consisting of ordered pairs (a , c )∈ A , c ∈C , and for which there exists and
element b ∈ B such that (a , b) ∈ R and (b , c )∈ S . We denote the composite of R and S by S ° R .

Simplified - Composite: if R ∈(A , B) and S ∈(B , C) then S ° R ∈( A , C).

Definition 7: Let R be a relation on the set A . The powers Rn , n=1 ,2 , 3 , …, are defined recursively by
1 n +1 n
R =R and R =R ° R
Simplified: R2=R ° R
Example 22 - Solution:

Theorem 1: The relation R on a set A is translative if and only if Rn ⊆ R for n=1 ,2 , 3 , … .

Proof: page 608

Kursusgang 3
9.5

Definition 1: A relation on a set A is called an equivalence relation if it is reflexive, symmetric, and

transitive.

Definition 2: Two elements a and b that are related by an equivalence relation are called equivalent. The
notation a b is often used to denote that a and b are equivalent elements with respect to a particular
equivalence relation.

aRb means that a and b are related.

Definition 3: let R be an equivalence relation on a set A . The set of all elements that are related to an
element a of A is called the equivalence class of a . The equivalence class of a with respect to R is denoted
by [ a ] R. When only one relation is under consideration, we can delete the subscript R and write [a] for this
equivalence class.

Simplified - Equivalence class: [ a ] R= { s|( a , s ) ∈ R }

If b ∈ [ a ] R , then b is called a representative of this equivalence class

The equivalence class of the relation congruence modulo m are called congruence classes modulo m .

Theorem 1: Let R be an equivalence relation on a set A . These statements for elements a and b of A are
equivalent:

( i ) aRb ( ii ) [ a ] =[ b ] ( iii ) [ a ] ∩ [ b ] ≠ Ø
Proof: page 643

A Partition of a set S is a collection of disjoint nonempty subsets of S that have S as their union.

Theorem 2: Let R be an equivalence relation on a set S . The the equivalence classes of R form a partition
of S. Conversely, given a partition { Ai|i ∈ I } of the set S, there is an equivalence relation R that has the
sets Ai , i ∈ I , as its equivalence classes.

9.6.1-9.6.2

Definition 1: A relation R on a set S is called a partial ordering or partial order if it is reflexive,

antisymmetric, and transitive. A set S together with a partial ordering R is called a partially ordered set, or
poset, and is denoted by (S , R). Members of S is called elements of the poset.

Definition 2: The elements a and b of a poset ( S , ≼) are called comparable if either a ≼ b or b ≼ a. When a
and b are elements of S such that neither a ≼ b nor b ≼ a, a and b are called incomparable.

When every two elements in the set are comparable., the relation is called total ordering.

Definition 3: If (S , ≼) is a poset and every two elements of S is camparable, S is called a totally ordered or
linearly ordered set, and ≼ is called a total order or linear order. A totally ordered set is also called a chain.

Definition 4: ( S , ≼) is a well-ordered set if it is a poset such that ≼ is a total ordering and every nonempty
subset of S has a least element.
Theorem 1:

THE PRINCIPLE OF WELL-ORDERED INDUCTION

Suppose that S is a well-ordered set. Then P( x ) is true for all x ∈ S , if

INDUCTIVE STEP:

For every y ∈ S, if P( x ) is true for all x ∈ S with x ≺ y , then P( y ) is true.

Proof: page 652

Kursusgang 4
9.4.1-9.4.4

Definition 1: If R is a relation on a set A , then the closure of R with respect to P, if it exists, is the relation
S on A with property P that contains R and is a subset of every subset of A × A containing R with
property P.

Reflexive Closure:
Reflexive closure is equal to R ∪ Δ, where Δ= {( a , a )|a ∈ A } is the diagonal relation on A .

Symmetric Closure:
The symmetric closure of a relation can be contructed by taking the union of a relation with its inverse
(which is (a , b), where the inverse is (b , a)).
−1
R∪R
Where the inverse is as following:

R ={ ( b , a )|( a , b ) ∈ R }
−1

Definition 2: A path from a to b in the directed graph G is a sequence of edges (x 0 , x 1 ), (x 1 , x 2), ( x 2 , x 3) ,

…, (x n−1 , x n ) in G , where n is a nonnegative integer, and x 0=a and x n=b , that is, a sequence of edges
where the terminal vertex of an edge is the same as the initial vertex in the next path. This path is denoted
by x 0 , x 1 , x 2 , … , x 1−n , x n and has length n . We view the empty set of edges as a path of length zero from a
to a . A path of length n ≥ 1 that begins and ends at the same vertex is called circuit cycle.
Circuit cycle: if the path begins and ends on the same

Path: also applies to relations

Theorem 1: Let R be a relation on a set A . There is a path of length n , where n is a positive integer, from a
to b if and only if ( a , b ) ∈ R n.

Proof: page 630

Transitive Closure:
Definition 3: Let R be a relation on a set A . The connectivity relation R⋆ consists of the pairs (a , b) such
that there is a path of length at least one from a to b in R .
⋆ n
R =¿ n=1¿ ∞ R
Theorem 2: The translative closure of a relation R equals the connectivity relation R⋆ .

Proof: page 632

Lemma: Let A be a set with n elements and let R be a relation on A . If there is a path of length at least one
in R from a to b , then there is such a path with length not exceeding n . Moreover, when a ≠ b, if there is a
path of length at least one in R from a to b , then there is such a path with length not exceeding n−1.

Proof: page 632

⋆ 2 3 n
R =R ∪ R ∪ R ∪… ∪ R

Theorem 3: Let M R be the zero-one matrix of the relation R on a set with n elements. Then the zero-one
matrix of the transitive closure R⋆ is
[ 2] [ 3] [ n]
M R =M R ∨ M R ∨ M R ∨ … ∨ M R
⋆

Zero-one matrix: a matrix containing 0 and 1, which means false for 0 and true for 1.