Summary Modelling Computing Systems Chapter 4 Faron Moller & Georg Struth
19 views 0 purchase
Course
Logic for Computer Science
Institution
Universiteit Utrecht (UU)
Book
Modelling Computing Systems
Logic for Computer Science/Logic for Computer Technology Chapter 4 Summary of the book Modelling Computing Systems written by Faron Moller Georg Struth. Summary written in English. Using examples and pictures, the substance and theory are clarified. Given at Utrecht University.
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 ∧ …
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.
