Logic for Computer Science/Logic for Computer Technology Chapter 8 Summary of the book Modelling Computing Systems written by Faron Moller and Georg Struth. Summary written in English. Using examples and pictures, the substance and theory are clarified. Given at Utrecht University.
We can define a finite set by enumerating all its elements: People = {Alice, Bob, Carroll } We can
define a function on such a finite set by listing all possible cases: age(Alice) = 23 age(Bob) = 21
age(Carroll) = 19 We can define a relation by listing all the relevant pairs: Likes = { (Alice, IceCream),
(Alice, Toffee), (Carroll, Toffee) }
But for infinite set we can define for example the natural numbers as: N = {0, 1, 2, …}. We (as
humans) can understand this definition perfectly well - but it relies on ‘guessing’ how to fill in the
dots. Because we as human scan guess that after the 2, probably stands a 3, but we do not know this
for sure. Criticism on these notations:
− How could we expect a computer to understand such a definition?
− How can we be sure that the reader ‘guesses’ the right definition? Maybe I meant to define
the set of solutions to the equation x × (x − 1) × (x − 2) = 0.
− The order of elements in a set is not important. Yet this definition implies that the elements
should be listed in some particular order.
− How can we determine whether a particular number is in the set or not? The definition
doesn’t give us an effective check.
− What about sets where the ‘next’ element is difficult to describe, like the set of all real
numbers or the set of all valid C# programs.
Many infinite sets are described using induction, the idea behind induction is to easily describe
infinite sets. Each inductive definition consists of three parts:
− The base case that establishes some objects are in the set. Says these are some elements of
the set
− The inductive case that determines the ways in which elements of the set can be assembled
to create new elements that are also in the set. Describe how to build up bigger elements
from existing elements.
− The extremal clause that asserts that no other elements are in the set unless its
membership can be established from the first two clauses. This is all there is, there are no
other things living in the set.
We can give an inductive definition of the natural numbers (N) as follows:
− 0∈N
− for any n ∈ N, the number (n + 1) ∈ N.
− there are no other elements of N.
Using these clauses, we can show that 3 ∈ N but 4.5 ∈/ N. This inductive definition lets give a finite
description of an infinite set.
, Example of a power set:
Given a set A we can define the powerset of A, written P(A) as follows:
− ∅ ∈ P(A)
− if a ∈ A and X ∈ P(A) then {a} ∪ X ∈ P(A)
− there are no other elements of P(A)
Let B = {1, 2, 3} then from these rules we can conclude that:
− ∅ ∈ P(B)
− {1} ∪ ∅ ∈ P(B) – or more simply {1} ∈ P(B). Similarly, {2} ∈ P(B), {3} ∈ P(B)
− Repeating the second rule also gives us that, {1, 2} ∈ P(B), {1, 3} ∈ P(B), {2, 3} ∈ P(B)
− Finally, {1, 2, 3} ∈ P(B).
− 0∈N
− for any n ∈ N, the number (s(n)) ∈ N. Here we thing of s as being a unary function symbol
that stands for ‘successor’.
− there are no other elements of N.
We consider the digit 4 to be a shorthand for s(s(s(s(0)))). The Arabic numerals are simply a
shorthand for repeatedly adding one using the successor operation.
Example of a string instead of int:
Induction definition:
− the empty string, which we’ll denote using the symbol ε, is a string;
− if c is one of the 256 ASCII characters and s is a string, we can construct a longer string by
writing cs (that is, the character c followed by the string s).
There is very little that is specific to ASCII in this definition! Given any set A, we can construct the
words of characters over some set A, often written A ⋆ as follows:
− ε∈A⋆
− for all a ∈ A an w ∈ A ⋆ , aw ∈ A ⋆
A⋆ To denote the set of all words over A
A+ To denote the set of non-empty words over A.
That is, the only word of length 0.
Let’s try to construct some example inhabitants of the set {0, 1} ⋆:
− ε ∈ {0, 1} ⋆
− 0 ∈ {0, 1} ⋆ and 1 ∈ {0, 1} ⋆
− 00, 01, 10, 11 are all also in {0, 1} ⋆ .
− As are 000, 001, 010, 100, …
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller luukvaa. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $3.21. You're not tied to anything after your purchase.
