Logic for Computer Science / Logica voor computertechnolgie hoofdstuk 8. Samenvatting van het boek Modelling Computing Systems geschreven door Faron Moller en Georg Struth. Samenvatting geschreven in het Engels. Aan de hand van voorbeelden en plaatjes wordt de stof en theorie verduidelijkt. Gegeven...
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, …
Los beneficios de comprar resúmenes en Stuvia estan en línea:
Garantiza la calidad de los comentarios
Compradores de Stuvia evaluaron más de 700.000 resúmenes. Así estas seguro que compras los mejores documentos!
Compra fácil y rápido
Puedes pagar rápidamente y en una vez con iDeal, tarjeta de crédito o con tu crédito de Stuvia. Sin tener que hacerte miembro.
Enfócate en lo más importante
Tus compañeros escriben los resúmenes. Por eso tienes la seguridad que tienes un resumen actual y confiable.
Así llegas a la conclusión rapidamente!
Preguntas frecuentes
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.
100% de satisfacción garantizada: ¿Cómo funciona?
Nuestra garantía de satisfacción le asegura que siempre encontrará un documento de estudio a tu medida. Tu rellenas un formulario y nuestro equipo de atención al cliente se encarga del resto.
Who am I buying this summary 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 this summary for $3.44. You're not tied to anything after your purchase.
