Summary everything from the course 'logic for computing science
54 views 1 purchase
Course
Logic For Computer Science (INFOB1LI)
Institution
Universiteit Utrecht (UU)
Book
Modelling Computing Systems
This summary contains all the substance for the course of logic for computer science (informatica), from both the lectures and the book. The summary contains useful tables, for example, summarizing all the laws and all proofing strategies.
Modelling Computing Systems Hoofdstuk 11 Faron Moller & Georg Struth
All for this textbook (14)
Written for
Universiteit Utrecht (UU)
Informatica
Logic For Computer Science (INFOB1LI)
All documents for this subject (12)
Seller
Follow
mmwaasdorp
Reviews received
Content preview
Summary “Logica voor Informatica”
Summary of the lectures and the book “Modelling Computing Systems”
Contents
0. Introduction ........................................................................................................................................ 2
1. Propositions (H1) ................................................................................................................................ 3
1.2 The language of Propositional Logic ............................................................................................. 3
2. Sets (H2) .............................................................................................................................................. 7
Operations on sets .............................................................................................................................. 8
3. Boolean algebra (H3) ........................................................................................................................ 12
Logic gates and Digital Circuits ......................................................................................................... 14
4. Predicate Logic (H4) .......................................................................................................................... 16
5. Proof strategies (H5) ......................................................................................................................... 17
6. Functions (H6) ................................................................................................................................... 19
,0. Introduction
Logic studies the rules of deduction – given certain assumptions, what conclusions can we draw from
them?
Safety critical applications: Applications with which system failures cannot be tolerated.
Safe design
Why designing a system that is both safe, user friendly and dependable in any context is so hard:
• Systems can be extremely complex. Existing of a large number of heterogeneous
components that can change over time and interact in intricate and sophisticated ways.
• Knowledge is still at its infancy as compared to, for instance, building bridges.
• Rigorous mathematical tools and methods are much less employed in software engineering
than in other engineering disciplines.
System: An assemblage of objects arranged in a regular subordination, or after some distinct
method, usually logical or scientific; a complete whole of objects related by some common law,
principle, or end; a complete exhibition of essential principles or facts, arranged in a rational
dependence or connection; a regular union of principles or parts forming one entire thing.
Systems can be described in terms of their:
• Structure
• Behavior
• Functionality
Model: definition from lecture: some abstraction of reality that makes it tractable to study.
Definition from book: (1) A miniature representation of a thing, with the several parts in due
proportion; sometimes, a facsimile of the same size. (2) Something intended to serve, or that may
serve, as a pattern of something to be made; a material representation of or embodiment of an
ideal; sometimes a drawing or a plan; a description of observed behavior, simplified by ignoring
certain details.
Abstraction: The act or process of leaving out of consideration one or more properties of a complex
object so as to attend to others.
Example: A map (can be in the form of google maps/earth or even a subway map but they are all an
abstraction or reality)
Notation: Any particular system of characters, symbols, or abbreviate expressions used in art, or in
science, to express briefly technical facts, quantities, etc. Especially the system of figures, letter, and
signs used in arithmetic and algebra to express number, quantity, or operations.
A good notation provides the shortest distance between the idea in your head and a piece of paper.
Three tasks that are central to software development and its formalization trough computational
modelling:
• Specification: refers to the task of modelling a computing system together with its
functionality and behavior. This can be understood as a formal description of a problem to
be solved.
, • Implementation: refers to the task of programming the specification so that it can be
executed on a computer. This can be understood as an effective solution to the problem
posed by the specification.
• Verification: refers to the task of rigorously demonstrating that the implementation does
indeed respect the specification. This can be understood as a proof that the implementation
doe indeed solve the problem specified.
Invariant: A logical notation that some property will always hold
Example: When something is True it will stay true.
1. Propositions (H1)
Statements/propositions: declarations which are either true or false (but not both).
Premises: Arguments from which possibly a conclusion can be drawn.
Conclusion: The conclusion which can be inferred or deducted from the premises.
Example:
Either this man is dead or my watch has Premises
stopped
My watch is still ticking Premises
Deduction / inference
↓
This man is dead Conclusion
Syntax: The syntax (structure) of propositional logic provides a language for modelling systems,
situations and arguments.
Semantics: The semantics (meaning) of propositional logic gives an interpretation to the symbols of
the language.
Atomic propositions: The language of propositional logic starts with atomic propositions such as
“this man is dead”.
1.2 The language of Propositional Logic
Propositional variable: Variables that represent unknown propositions. Can be P, Q, R, … or whole
words.
Example: Let ‘Dead’ represent the statement: this man is dead
Propositional connectives: Something that connects to atomic propositions such as ‘or’. Each
connective is given a precise prescribed meaning which aims to reflect its everyday use in natural
language. The propositional connectives are:
Symbol Name Natural language
T, 1, Truth
true
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 mmwaasdorp. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $9.01. You're not tied to anything after your purchase.
