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
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
