Zusammenfassung
Samenvatting Logica voor informatica
- Kurs
- Hochschule
- Book
Samenvatting van het vak "Logica voor informatica" aan de Universiteit Utrecht, gebaseerd op colleges en het boek Modelling Computer Systems.
[ Mehr anzeigen ]vorschau 3 aus 17 Seiten
Vorschau 3 aus 17 Seiten
In den Einkaufswagen
In den Einkaufswagen
Verknüpftes buch
Buch Titel:
Autor(en):
- Edition:
- ISBN:
- Ausgabe:
Weitere Zusammenfassungen für
-
Samenvatting alle stof logica voor informatica
-
Samenvatting Logica voor Informatica (INFOB1LI)
-
Modelling Computing Systems Hoofdstuk 11 Faron Moller & Georg Struth
Verkäufer
Folgen
pactasuntservanda
Deine Reviews
Inhaltsvorschau
Logic for CSChapter 0
Logic studies the rules of deduction (=gevolgtrekking).
Speci cation: identifying the task to be solved, as well as what constitutes a solution (abstract
description of what a program must do);
Implementation: devising a solution to the task which respects the speci cation (a program that exhibits
the behavior desired by the speci cation);
Veri cation: a proof that an implementation adheres to its speci cation.
To prove something can be done, it su ces to nd 1 successful solution. To prove something cannot be
done, there are way too many combinations to try.
Chapter 1: Propositions
Proposition is a statement that may be true or false.
A propositional formula that always holds is known as a tautology.
A propositional formula that is false regardless of the truth values of its atomic proposition is known as a
contradiction.
A statement that doesn’t change is called an invariant.
The rst statement expresses an option. → A deduction/inference is made to infer the truth of a third
statement from the rst statement. (These two rst statements are premises). → It’s followed by the
conclusion.
Propositional variables such as P, Q, R,… represent unknown propositions (just like variables such as x, y
and z represent unknown numbers in math).
Propositional connectives
￢ negation not p
∧ conjunction p and p
∨ inclusive sense of p or q
disjunction
⨁ exclusive sense of p xor q
disjunction
implication if p then q / p implies q / p only if q /
q is a necessary condition for p
equivalence p if, and only if, q / p is equivalent to q
Logical implication: think about example : “when the re alarm goes o , we all leave the classroom”. p q
is only false when p is true and q is false.
Page 1 of 17
fifi fi fi fi ffi fi fi fi ff fi
,A statement written in propositional logic is called a propositional formula and is either:
• an atomic formula, typically represented by a variable name such as P, Q, R, …;
• two special atomic propositional formula: true and false.
• a compound formula, in which case it is build up using the above propositional connectives.
Parentheses and Precedences
To reduce the need for parentheses, we will consider ￢ as binding more tightly than ∧, which will bind more
tightly than ∨, which will bind more tightly than , which will bind more tightly than . Apart from this, the
connectives will be applied right-to-left.
Syntax Tree
The syntax tree makes it clear how the expression should be parsed, without the need for parentheses or
precedence rules to tell the reader how to interpret the formula.
(P ∨ Q) ￢(P ∧ Q) corresponds to the following syntax tree:
Truth Tables
One way of de ning the meaning of the connectives, is by using truth tables. An example, with implication:
p q p q
F F T
F T T
T F F
T T T
Chapter 2: Sets
A set is a collection of objects which typically share a property.
The objects of a collection are referred to as its elements or members. The number of objects in a set A
is referred to as cardinality.
Simple sets can be de ned by listing all their elements, for example:
• { 3, 12, 25 }
• { 0,2,4,…,50 } for all even numbers under 50.
Creating a list by describing the property that the elements share (set-builder notation):
{ x : x has property P }
P is called a predicate.
Page 2 of 17
fi fi
, Elements
We write |A| to refer to the number of elements in the set A, the cardinality (sometimes also written as #A).
Membership
If x is an element of the set A, we write x ∈ A
If x is not an element of the set A, we write x ∉ A
Set inclusion
When all elements of a set A are also elements of a set B, we say that A is a subset of B, written as A ⊆ B.
B is a superset of A (B ⊇ A). This is called set inclusion.
If A ≠ B, but A is a subset of B, A is called a strict subset written as A ⊂ B. All elements of A are in B, but B
has got more elements.
The subset relation is re exive, antisymmetric and transitive (see chapter 7).
Equality
Two sets are equal if, and only if, they have the same elements. The order of elements in a set doesn’t
matter.
{ 3, 7, 14 } = { 7, 14, 3, 7, 3 }
{ Joel, Felix, Oskar } ≠ { Joel, Felix, Oskar, Amanda }
A useful graphical way of depicting sets, and in particular the relationship between them, is by so-called
Venn diagrams. The rectangle represents some understood universal set U (universe of discourse). ∅ ⊆ A
(empty list is contained by any other list).
Russell’s Paradox
Normally a set will not be a member of itself, but there is nothing to preclude us considering abnormal sets
that are elements of themselves. Consider the set of normal sets; thus all sets which do not contain itself:
R = { A : A ∉ A }.
Is R a normal set? Thus, do we have R ∈ R?
Suppose R ∈ R; then we need to satisfy the property required of being an element of R, thus R ∉ R.
Support R ∉ R; then we must not satisfy the property required of bering an element of R, thus R ∈ R.
Operations on Sets
A∩B intersection1 consists of elements in both sets A and B
A∪B union consists of elements in either set A or B (or
both)
Ā complement the complement of set A consists all of
those elements of the universe of discourse
which are not in A
A\B di erence consists of those elements which are in A
but are not in B
A▽B symmetric di erence consists of those elements that are not in
both A and B
1Two sets A and B are called disjoint if they do not have any elements in common.
It is also possible to say: A ∪ B = ⋃{A, B} and A ∩ B = ⋂{A, B}.
Page 3 of 17
ff
ff fl
Alle Vorteile der Zusammenfassungen von Stuvia auf einen Blick:
Garantiert gute Qualität durch Reviews
Stuvia Verkäufer haben mehr als 700.000 Zusammenfassungen beurteilt. Deshalb weißt du dass du das beste Dokument kaufst.
Schnell und einfach kaufen
Man bezahlt schnell und einfach mit iDeal, Kreditkarte oder Stuvia-Kredit für die Zusammenfassungen. Man braucht keine Mitgliedschaft.
Konzentration auf den Kern der Sache
Deine Mitstudenten schreiben die Zusammenfassungen. Deshalb enthalten die Zusammenfassungen immer aktuelle, zuverlässige und up-to-date Informationen. Damit kommst du schnell zum Kern der Sache.
Häufig gestellte Fragen
Was bekomme ich, wenn ich dieses Dokument kaufe?
Du erhältst eine PDF-Datei, die sofort nach dem Kauf verfügbar ist. Das gekaufte Dokument ist jederzeit, überall und unbegrenzt über dein Profil zugänglich.
Zufriedenheitsgarantie: Wie funktioniert das?
Unsere Zufriedenheitsgarantie sorgt dafür, dass du immer eine Lernunterlage findest, die zu dir passt. Du füllst ein Formular aus und unser Kundendienstteam kümmert sich um den Rest.
Wem kaufe ich diese Zusammenfassung ab?
Stuvia ist ein Marktplatz, du kaufst dieses Dokument also nicht von uns, sondern vom Verkäufer pactasuntservanda. Stuvia erleichtert die Zahlung an den Verkäufer.
Werde ich an ein Abonnement gebunden sein?
Nein, du kaufst diese Zusammenfassung nur für 4,99 €. Du bist nach deinem Kauf an nichts gebunden.
Kann man Stuvia trauen?
4.6 Sterne auf Google & Trustpilot (+1000 reviews)
45.681 Zusammenfassungen wurden in den letzten 30 Tagen verkauft
Gegründet 2010, seit 14 Jahren die erste Adresse für Zusammenfassungen