Summary Modelling Computing Systems Hoofdstuk 4 Faron Moller & Georg Struth
19 vistas 0 compra
Grado
Logic for Computer Science
Institución
Universiteit Utrecht (UU)
Book
Modelling Computing Systems
Logic for Computer Science / Logica voor computertechnolgie hoofdstuk 4. 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...
Predicates: properties which may be true or false of particular elements in a given universe.
Quantifiers: the means by which we refer to elements which satisfy such properties.
We sometimes defined sets by stating using the following notation:
- { x : x > 17}
- { p : p is a prime number}
Or more generally, we write {x : x has the property P}. Such a set consists of all elements that satisfy
the predicate P. In general, we will write P(x) when ‘x has the property P’, or when ‘P holds for x’.
A predicate is not the same as a proposition:
- P(x) = x > 17 ∧ x > 5 defines a predicate on x
- x < 12 defines a proposition.
Predicates differ from propositions in that they do not have a fixed truth value, since we do not
know the value of the object to which it refers.
Example: Let the universe of discourse be the Duck family: DUCKS = {Quackmore, Hortense, Scrooge,
Donald, Della, Huey, Louis, Dewey}, and define the following predicate:
Female(x) = “x is a female”.
Then:
- Female(Hortense) and Female(Della) are both true;
- Female(Quackmore), Female(Scrooge), Female(Donald), Female(Huey), Female( Louis),
Female(Dewey) are all false;
- The truth set of the predicate Female(x) is {Hortense, Della}
Predicates can have more than one argument. In that case, they are typically called a relation. We
have already encountered several different relations when studying sets:
- SubsetOf(A,B) holds if for all x, x ∈ A ⇒ x ∈ B
- EqualSet(A,B) holds if both A ⊆ B and B ⊆ A
- ProperSubset(A,B) holds if A ⊆ B and A ≠ B
Many familiar relations are written using infix operators, such as ⊆ or =, rather than a function
name, such as SubsetOf.
We can ‘define’ a predicate Divides(x, y) to hold when x and y are natural numbers and x divides
evenly y (that is, there is no remainder after performing the division):
- For example, Divides(3, 15) holds.
- But Divides(3, 17) does not.
We can construct a truth-set: {(x, y) : Divides(x, y)} To be the set of all pairs (x, y) such that x divides
evenly into y. Traditionally, mathematicians write x | y when Divides(x, y) holds.
, When defining a predicate of the form: P(x) = ...x... The occurrences of x on the right hand side of the
equality all refer to the x bound by the declaration P(x). If we write: P(x) = ...y... It is not clear what y
is – where it is not bound - we say that the variable y is free. Example: ∀y P (x, y): x is free and y is
bound by the universal quantifier.
We can turn any predicate into a proposition by substituting a value for variable bound in the
predicate’s definition. For example, we can define the following predicate: P(x) = x > 1337
- P(10.000) is the proposition 10.000 > 1337 (which happens to be true)
- P(5) is the proposition 5 > 1337 (which happens to be false).
Example:
How many elements are there in the set { x : x < 17}? It depends! Is it a set of natural numbers,
integers, real numbers, … I prefer to be explicit: { x ∈ N : x < 17 }. This avoids confusion and makes it
clear what the universe of discourse is that I’m assuming. These examples all show that – even in the
study of formal logic – there can be information left implicit in the context, naming conventions,
universe of discourse, etc.
We cannot express infinite conjunctions and disjunctions in propositional logic. Example: The
universe of discourse is the set consisting of the four children: Children = {Joel, Felix, Oskar,
Amanda}. They get into the car and head off to school. One of the children has to sit in the front
passenger’s seat, as there is only room for three
passengers in the back seat. Thus, the predicate:
Front(x) which denotes that child x sits in the front
seat, must be true of some one of them. As there is
only room for one child in the front seat, the
predicate front(x) must be true of exactly one child
that is, it must be true of one and false of all of the
others. This means that the following proposition
must be true:
These propositions are lengthy already when there are only four elements in the universe of
discourse.
Let A be the set {0,1,2,3}. We say A is the subset of some other set B, written A ⊆ B, when all the
elements of A also occur in the set B. Or more precisely: 0 ∈ B ∧ 1 ∈ B ∧ 2 ∈ B ∧ 3 ∈ B.
This may work for a finite set, but what if we want to show that all the even numbers are also
natural numbers? 0 ∈ N ∧ 2 ∈ N ∧ 4 ∈ N ∧ 6 ∈ N ∧ …
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.
