Summary Foundations of Computing (JBI020) 2020/2021

Lieve Göbbels
Foundations of Computing (JBI020)
Semester 1, 2020-2021

Foundations of Computing
Speaking Mathematically 3
Variables 3
The language of sets 3
The Logic of Compound Statements 5
Logical form and logical equivalence 5
Conditional statements (implication) 6
Valid and invalid arguments (deduction) 7
The Logic of Quanti ed Statements 10
Predicates and quanti ed statements I 10
Predicates of quanti ed statements II 11
Statements with multiple quanti ers 12
Elementary Number Theory and Methods of Proof 13
Direct proof and counterexample I: introduction 13
Direct proof and counterexample II: rational numbers 14
Direct proof and counterexample III: divisibility 14
Direct proof and counterexample IV: Quotient-Remainder Theorem 14
Direct proof and counterexample V: oor and ceiling 15
Proving methods from the lectures 15
Sequences and Mathematical Induction 17
Sequences 17
The Pigeon-Hole Principle 18
Mathematical induction 18
Strong mathematical induction 19
Set Theory 20
Properties of sets 20
Euler diagrams 20
Set operations 21
Sets versus propositional logic 21
Power sets 21
Regular Expressions (RegEx) and Automata 22
RegEx 22
Finite-state automata 23
Turing Machines 25
Algorithms I: Ef ciency and Correctness 28
An algorithm 28
Ef ciency 28
Asymptotic notation 30
Correctness 31
Algorithms II: Recursion 33
Recursion 33
Searching and sorting algorithms 34
Different kinds of sorting algorithms 35

,Graphs and Topological Sorting 39
Graphs 39
Topological sorting 40
Shortest paths 41
Limits of Computation 44
Problems in NP 44
Decision problems and reductions 44
The Mother Problem 45
Undecidable problems 46
An overview of the limits of computation 47
Cheat Sheet 48

, Speaking Mathematically
In short:
• Variables
• The language of sets


Variables
There are di erent types of statements that can de ne a variable:
universal statement = a certain property is true for all elements in a set
conditional statement = if one thing is true, some other thing must also be true
existential statement = given a property that may or may not be true, there is at least one
thing for which the property is true
universal existential statement = the rst part says that a certain property is true for all objects of a
given type; the second part states the existence of something
universal conditional statement = a statement that is both universal and conditional
existential universal statement = the rst part states the existence of a certain object; the second part
states says that the object satis es a certain property for all things
of a certain kind.


Examples:

universal existential statement: every real number has an additive inverse


universal conditional statement: for all animals a, if a is a dog, then a is a mammal

existential universal statement: there is a positive integer that is less than or equal to
every positive integer




The language of sets
x∈S = x is an element of set S
x∉S = x is not an element of set S
{1,2,3} = set-roster notation; the set whose elements are 1, 2, 3
… = ellipsis; means ‘and so forth’

The axiom of extension says that a set is completely determined by what its elements are - not the order in
which they might be listed or the fact that some elements might be used more than once.


ℝ = set of all real numbers (continuous) ℝ+ = set of all positive real numbers
ℤ = set of all integers (discrete) ℕ = set of all natural numbers
ℚ = set of all rational numbers (nonnegative integers)