Week 1
Rationality Square for system development
Definition of artefact: something man-made fulfilling a certain purpose
- Correctness: prove of the properties it should have
- The proof relates to a description of the structure related to a description of behavior.
Rationality Square:
| Structure | Properties | x |
|---|---|---|
| Structure Description | Property Description | description |
| Object in physical reality | Property in physical reality | Things and phenomena |
Summary:
The aim of this course is to focus on the top half of the rationality square: we validate descriptions. Technically speaking, the square can be extended by a third dimension adding the distinction between the real world and the mathematical world.
Propositional Logic
Precedence of operators
From strong to weak: $\neg$, $\land$, $\lor$, $\rightarrow$, $\leftrightarrow$
In the coq grammar, the weakest operator is parsed first and the strongest last.
Associativity of operators
In this course all operators are right-associative except the equivalence $\leftrightarrow$. Note that the associativity of operators can also be seen in the grammar by checking on which side of the rule the recursive call to the same operator is made.
Week 2
Models for investigating artefacts
Two key concepts: Focus and precision
Focus
- Modeling Goals (for studying the artefact)
- Construction Model (what is needed to build artefact - high detail)
- Verification Model (investigate one specific property of artefact)
- Demonstration Model (how does the artefact show insight in some principle)
- Fragment of Reality (which part of reality do and do not matter in the model)
- Usually the artefact, which is itself often part of a larger system.
- Perspective (what are the essential proporties/artefact goals being studied?)
- Dynamic and constant parts must be identified, but the property has to remain unchanged.
Example of focus:
We study a doorbell, with a verification model, the fragment of reality are the components of the bell (button at door, bell itself, wires), and the perspective is the behaviour of the bell (when does it ring?). We don't care about the aesthetics of the bell, for example.
Precision
- Syntactical correctness / unambiguity
- Completeness
- Conciseness
- Semantically unambiguous
- Readability
Formalized Natural Language
Use clear definitions and use them consistently for the same entities, and different ones for different entities. Write in such a way that the meaning of operators (conjunctions,disjunctions etc.) is clear and almost mappable on a formal language.
Predicate Logic
Most important difference is the introduction of quantifiers. Note: Any quantified formula next to a logical operator must have surrounding parentheses. In other words, any new quantified formula that is introduced needs parentheses. Conversely, an introductory quantifier that has the whole formula as it's scope, does not have parentheses.
Tutorial Week 2
Core skills:
- Recognize faulty production table
- Find mistakes in formulas
Week 3
Terminology
- Scenario
One possible course of actions concerning an artefact (i.e. there is the criterium of relevance!).
- Phenomenon
Of which one can determine with a singular observation or measurement whether it is happening or not.
Guideline: a phenomenon can be described by
- one place
- one moment
- one effect (physical, information, thing)
... and thus follows the format: "At location $l$ at time $t$ effect $e$ appears"
Some notes:
The timing can be implicit. "Button $k$ is being pressed" implies a time and is a phenomenon. Two examples of non-phenomena. "A visitor wants to come in" (wanting is not observable). "Button 1 and button 2 are being pressed" (Usually not a singular observation).
- Specification
Specification of the behavior of the artefact that holds for all scenarios the artefact enables, and does not hold for all the scenarios the artefact excludes.
A good specification is a contract between designer and user, and helps determine what we can do with an artefact.
- Theorem
Assertion that states that conclusion B follows from a set of assumptions A, so of form $A \rightarrow B$. We want to proof this with a closed argumentation.
Proof rules
Types of proof
- in natural language
- by truth tables in propositional logic
- by induction
- by semantic tableaux in propositional logic
- by natural deduction both in prop. and predicate logic
Rules
-
Implication introduction 1) Assume P holds 2) It is shown that if P holds, then Q holds 3) Then it holds: if P then Q
-
Implication elimination (Modus Ponens!) 1) Suppose P holds 2) Suppose it holds that: if P then Q 3) Then Q also holds
-
Equivalence elimination (Biconditional Modus Ponens) 1) Suppose P holds | Suppose Q holds 2) Supppose it holds that: P iff Q 3) then Q also holds | then P also holds
-
Negation elimination (Proof by contradiction) 1) Assume "not P" holds 2) Suppose we can derive a contradiction from this 3) Then assertion P must hold by contradiction
-
Disjunction introduction 1) Suppose "P" holds | Suppose "Q" holds 2) Then "P or Q" also holds
-
Disjunction elimination (case distinction, show that conclusion holds in all cases) 1) Suppose "P or Q" holds 2) Suppose that from P it follows that R 3) Suppose that from Q it follows that R 4) Then assertion R holds
-
Conjunction introduction 1) Suppose "P" holds 2) Suppose "Q" holds 3) Then "P and Q" holds
-
Conjunction elimination 1) Suppose "P and Q" holds 2) Then "P" holds | Then "Q" holds
Example format of proof in natural language
Theorem: Given the components X,Y,Z it follows that: if A is the case, then B. ($X \land Y \land Z \rightarrow A \rightarrow B$)
Specifications are not supplied in this example. Assumse some conditions 'c' and effects 'e'
1) Assume A holds 2) From the specification of X we know that: c1 holds. 3) From the specification of Y we know that if A holds and c1 holds, then it holds that: c2 if and only if B 4) From the specification of Z we know that c2 holds. 5) So from 1 and 2 and 3 it follows that: if c2 then B (implication elimination) 6) From 4 and 5 we know that B holds (equivalence elmination) 7) So from 1 and 6 it follows that: if A then B (implication introduction).
Concrete example: knights and knaves
We know the following:
a) There are only knights and knaves b) Knights always speak the truth c) Knaves never speak the truth
Each husband is asked the following question: to which category does he and his spouse belong to? He gives the following answers:
- "We are both knaves"
- "If my wife is a knight, then so am I"
For the first assertion:
1) Assume the husband is not a knave 2) Because of a, the husband must thus be a knight. 3) Because of 2 and c, he thus speaks the truth (implication elimination) 4) If he speaks the truth, then "We are both knaves" is true. 5) Due to 3 and 4, he must be a knave (implication elimination) 6) 1 and 5 form a contradiction 7) So assumption 1 cannot hold and the man is a knave (negation elimination)
Note: make sure that the contradiction is really a contradiction! A) the husband is a knight and B) the husband is a knave, is not a contradiction yet. Assertion A must still be "unfolded" , i.e. we must make explicit with rule a that being a knight means he is not a knave.
We know at this point: the husband is a knave. We thus already know that he lied about the second assertion. The second assertion is false iff his wife is a knight, but he is not. Thus we know his wife must be a knight, i.e. there must at least be one knight. We still have to prove this. If we prove that either the husband or the wife is a knight, and we know from the first assertion that the husband is a knave, then we have proven that the spouse is a knight.
For the second assertion, we thus basically prove that regardless of whether we assume the man is a knave or knight, that either the wife or husband is a knight. The case where the husband is assumed to be a knight is trival, in the other case we need more steps.
1) From a it follows that the man is either a knight or a knave. 2) Suppose the man is a knight 3) Then it follows in particular that the husband or wife is a knight (disjunction introduction) 4) Suppose the man is a knave 5) Because of c (knaves don't speak the truth) and 4 it follows that his answers are not true. 6) Because of 5, "If my wife is a knight, then so am I" is untrue 7) A few steps at once: due to the truth table of the implication, "If my wife is a knight, then so am I" is untrue iff his wife is a knight and he is not. 8) In particular, it follows then that his wife is a knight (conjunction elimination) 9) So, again: it follows from 8 that his wife or the husband is a knight (disjunction introduction) 10) Both from the assumptions at 2 and 4, it follows that the husband or the wife is a knight. 11) Thus it is proved by 1,2-3 and 4-9 that either the husband or the wife is a knight. QED.
Wrap up:
1) The husband is a knave 2) The husband or the spouse is a knight. 3) For both 1 and 2 to hold, the spouse must be a knight.
Tutorial Week 3
Natural proofs in Coq for a solution to the problem with the river, goat, cabbage and wolf. Define an invariant property that determines whether a transition is safe. Make auxiliary definitions that define the states that are not allowed (wolf_goat_problem) and (goat_cabbage_problem) in this case. For each transition, define a theorem to check if the transition is safe, of the following form: if this state holds, then we do not have the wolf_goat_problem and we also do not have the goat_cabbage_problem.
Week 4
Domain Models and Translations
A Domain Model includes:
- All relevant domains
- Individual constants
- Predicates
- Functions
- Measurements for predicates (do they occur or not?)
Domain model in propositional logic
- Only domain of Booleans
- Atomic propositions (predicates with arity zero)
- Individual constants are contained in the atomic propositions
- No functions
Example:
| Proposition : Type | Meaning | Measurement |
|---|---|---|
| PowA : B | Power is supplied to contact A | Check LED of voltage tester on contact A |
In coq:
(* Proposition *) \ Variable PowA : Prop . \ (* Power is delivered to contact A * ) \ (* Check LED of voltage tester on contact A * )
Variable: used to introduce constants, abstract functions, non-auxiliary predicates and domains if the domain is an non-existing set.
Definition:= if no new elements are introduced, and domains if the domain is an existing set, such as R. E.g. in auxiliary predicates (do also not have a measurement). For concrete functions, where coq knows exactly how to compute the results.
Inductive: for finite enumberable sets, e.g. provinces.\ Inductive Provinces : Set := Gelderland | Utrecht | etc... .
Note: Variables use ' : ' and definition use ' := '
**Abstract vs Concrete Function: **
Variable var = (* x *) : R $\rightarrow$ R \ (* description of function, but coq does not know how to compute *)
Definition (x:R) (y:R) := x - y \ (* outcome is x-y *)
Ad hoc translations
1) 'In none of the provinces adjacent to Utrecht it is snowing'
forall p:P,\ A u p -> $\neg$ S p .\
$\neg$ (exists p:P,\ A u p $\land$ S p ).
2) 'It is snowing in exactly two provinces'
Definition sentence2 :=\ (* There are two provinces in which it snows, and for all provinces it holds that if it snows in them, they are either the one or the other province *) exists x:P,\ exists y:P,\ x<>y $\land$ S x $\land$ S y $\rightarrow$ (forall z:P, S z $\rightarrow$ z=x $\lor$ z=y)
Systematic Translation Procedure
0) Fix Domain Model 1) Delimit Scope (by drawing a box of the (sub)formula under consideration) 2) Reformulate (so that the logical syntax categories become explicit) 3) Determine syntax category and write down the correct structure and mandatory symbols 4) Fill in atomic formulas or go to step 2. 5) Remove unnecessary parentheses and reformat
A sentence within a box can only refer to its exterior through variables and constants that are within the scope of containing boxes.
Stopping condition: when is something considered to be an atomic proposition?
- Cannot contain any quantifiers
- There must be a self-evident correspondence to the formula under consideration (usually
or .
Tutorial Week 4
1) Define domain model using Variables. 2) Use a definition to define the main sentence 3) If necessary, introduce a new definition that reformulates the sentence 4) Write down the correct syntactic structure, and make definitions for what still needs to be filled in. 5) Terminate if only atomic propositions are left
To proof the correctness, define a copy of the whole sentence and proof:
Theorem equal : \ main_sentence = sentence_copy.
Week 5
Functional Networks and Correctness Theorem
Intermezzo on SAT-solvers
For formalizations on propositional logic, coq cannot find solutions. We can let a SAT-solver find a solution for us (existential proof). The correctness of this theorem can be shown in coq with:
Theorem validate: Def1 $\land$ Def2 $\rightarrow$ A $\land$ $\neg$ B
where thus v(A)=1 and v(B)=0
How to verify whether this is the only solution?
In coq, the theorem might hold because there is a contradiction in the premises. If not, then the solution must be the only one. With a SAT-solver, the uniqueness of a solution can be verified by explicitly excluding it and then checking whether another solution will be found.
Functional network and correctness theorem.
For a functional network, make sure that there is a clear separation between the interior and the exterior of the network. Following the functional network, the correctness theorem should have the form:
Theorem correctnesTheorem:\ component1 $\land$ component2 $\and$ etc... $\rightarrow$ specification_of_overall_system
... where all components are listed in the antecedent and the system specification as the consequent.
The specification of the overall system lists all external propositions (I/0) as such: all inputs $\rightarrow$ all outputs.
Week 6
Suspicuous arrows and semantic tableux
General tips for arrows:
Using equivalences is dangerous. Only use it in very simple specifications, otherwise it is likely to have side-effects. Writing a conjunction with two implications just to be sure is a good default method.
Semantic Tableaux: definitions for branches
- Sequent: a series of formulas on the left and right side of an "o" symbol, stating that the formulas on the left sided should be true and on the right side should be false.
- A set of propositions is called consistent or satisfiable if there is a valuation such that all propositions are true.
- A set of propositions is inconsistent or unsatisfiable if there is no such a valuation.
- A valuation is a completion of the sequent if it makes the formulas on the left side true and false on the right side.
- Closed branch: a formula appears both on the left and right side of the branch (contradiction).
- Open branch: Only atomic propositions are left on both sides of the sequent, and the branch is not closed. Give open branches a number to track valuation indices.
Defintions for tableaux as a whole:
- A tableua as a whole is called complete if each branch is either open or closed.
- A tableau is closed if it is complete and every branch is closed.
- A tableau is open if it is complete and there is at least one open branch.
Requirements for tableau reduction rules:
- Correctness: if there exists a completion for a lower sequent, there also exists one for the uppper sequent.
- Completeness: if there exists a completion for the upper sequent, there also exists a completion for one of the lower sequents.
Usage of semantic tableaux
Reminder: the unfold rule always applies to both sides of the sequent.
- Proof satisfiability of set of propositions
Sequent: $\phi_1$,$\phi_2$,...,$\phi_n$ $\circ$ \ Goal: show that there is at least one open branch
- Proof for theorem A $\models$ B, where A and B are sets of propositions:
Sequent: $\circ$ A $\rightarrow$ B, a.k.a. A $\circ$ B after elimination of the implication\ Goal: Find an open brach for which A holds but B does not. If at least one such a branch exists, a counterexample has been given and then it has been shown that the theorem does not hold. Conversely, to prove that the theorem holds, the whole tableau needs to be closed i.e. there can be no open branches.
Proof rules and correctness theorem in predicate logic
Week 7
Note: The remaining proof rules in propositional logic are included above in the section on proof rules.
-
For all elimination 1) Suppose "for all x $\in$ X, P x" holds 2) Suppose t is an arbitrary element of set X 3) Then "P t" also holds
-
For all introduction 1) Suppose y is an arbitrary element in X, of which we know absolutely nothing 2) Suppose "P y" holds 3) Then "for all x $\in$ X, P x" also holds.
This rule only makes sense given that absolutely nothing is known y. If predicate P can be shown to hold on this y of which absolutely nothing is known, it must also generalize to all other members in class X. Rephrasing: if we have shown that P y holds while we know absolutely nothing about y, what must we then know to also meaningfully apply predicate P to any x $\in$ X? Nothing, therefore we can safely introduce the for all.
- Exist elimination 1) Suppose "there exists x $\in$ X such that P x" holds 2) Suppose that y is an arbitrary element in X of which we only know that "P y" holds 3) And suppose that from the assertion "P y" it follows that "Q" 4) Then "Q" holds
Note that step 2 is the crucial difference with respect to the for all introduction: now we have (minimal) knowledge of y. We can "point to" or name y. However, it is important that except from knowing that predicate P applies, no recourse to other properties is made. To be safe, it is therefore wise to choose y such that it is completely unknown. I picked "Harige Harrie".
Example:\ 1) Suppose there exists a student that attends response lectures. (some x) 2) Suppose Harige Harrie attends response lectures. (We have "P y" now) 3) Continue reasoning from there on ...
- Exists introduction 1) Suppose that t $\in$ X 2) Suppose "P t" holds 3) Then "there exists x $\in$ X such that P x" holds
Example:
1) All students that attend response lectures, pass this course. 2) Suppose a student exists that attends response lectures... Suppose Harige Harrie attends response lectures (summarized two steps) 3) From 1 it follows that if Harige Harrie attends response lectures, then Harige Harrie will pass this course. 4) From 2 and 3 it follows that Harige Harrie passes this course (for all elimination) 5) There exists a student that passes this course (because we know Harige Harrie passes). (exists introduction)
General remark:
The order of rules in the last example is interesting. We begin by eliminating the for all from 1 through 4. We do this by supposing a arbitrary student exists that attends the response lectures. Within the scope of this for all elimination, we eliminate the exists by supposing that arbitrary student is "Harige Harrie". For Harige Harrie we can show that he passed the course, given all assumptions, and therefore we can afterwards introduce the exists again to reach our desired conclusion. Usually starting with a for all elimination is a good start (for all introduction is harder).