We find establishing assertions of the form ‘Γ ψ’ ( ψ is not a semantic entailment of all formulas in Γ) easier than establishing ‘Γ ψ’ ( ψ is a semantic entailment of Γ), for in the former case we need only talk about one model, whereas in the latter we potentially have to talk about infinitely many.Īll this goes to show that it is important to study both proof theory and semantics. Thus, in semantics we have a ‘negative’ characterisation of the logic. However, when we look at predicate logic, we will find that there are infinitely many valuations, called models from hereon, to consider. If there is a small number of valuations, this is not so bad. For propositional logic, you need to show that every valuation (an assignment of truth values to all atoms involved) that makes all φ i true also makes ψ true. Showing that ψ is a consequence of Γ, on the other hand, is harder in principle. To show that ψ is not a consequence of Γ is the ‘easy’ bit: find a model in which all φ i are true, but ψ isn’t. Semantics, on the other hand, works in the opposite way. Thus, proof theory gives a ‘positive’ characterisation of the logic it provides convincing evidence for assertions like ‘Γ ψ is valid,’ but it is not very useful for establishing evidence for assertions of the form ‘Γ φ is not valid.’ Yet, how can we show that ψ is not a consequence of Γ? Intuitively, this is harder how can you possibly show that there is no proof of something? You would have to consider every ‘candidate’ proof and show it is not one. Thus, to show that Γ ψ is valid, we need to provide a proof of ψ from Γ. Let us write Γ as a shorthand for lists of formulas φ 1, φ 2. In proof theory, the basic object which is constructed is a proof. By ‘equivalent,’ we mean that we should be able to prove soundness and completeness, as we did for propositional logic – although a fully fledged proof of soundness and completeness for predicate logic is beyond the scope of this book.īefore we begin describing the semantics of predicate logic, let us look more closely at the real di erence between a semantic and a proof-theoretic account. In semantics, we expect something like truth tables. By ‘separate,’ we mean that the meaning of the connectives is defined in a di erent way in proof theory, they were defined by proof rules providing an operative explanation. Just like in the propositional case, the semantics should provide a separate, but ultimately equivalent, characterisation of the logic. Having seen how natural deduction of propositional logic can be extended to predicate logic, let’s now look at how the semantics of predicate logic works. The validity of the converse sequent is proved in the same way by swapping Identical, since x, y, x 0, y 0 di erent variables 6.3.2 Representing the transition relation.6.3.1 Representing subsets of the set of states.6.1.1 Propositional formulas and truth tables.5.5 Reasoning about knowledge in a multi-agent system.5.3.2 Important properties of the accessibility relation.4.4 Proof calculus for total correctness.4.3.3 A case study: minimal-sum section.4.3 Proof calculus for partial correctness.4.2.4 Program variables and logical variables.
#PROPOSITIONAL LOGIC SYMBOLS SHORTCUTS ON A MAC VERIFICATION#
4.2 A framework for software verification.4.1 Why should we specify and verify code?.3.7 The fixed-point characterisation of CTL.3.5.1 Boolean combinations of temporal formulas in CTL.3.4.4 Important equivalences between CTL formulas.3.4.3 Practical patterns of specifications.3.4.2 Semantics of computation tree logic.3.3 Model checking: systems, tools, properties.3.2.5 Adequate sets of connectives for LTL.3.2.4 Important equivalences between LTL formulas.3.2.3 Practical patterns of specifications.2.2 Predicate logic as a formal language.1.5.2 Conjunctive normal forms and validity.1.5.1 Semantic equivalence, satisfiability and validity.1.4.4 Completeness of propositional logic.1.4.1 The meaning of logical connectives.1.3 Propositional logic as a formal language.The interdependence of chapters and prerequisites.Our motivation for (re)writing this book.
0 kommentar(er)
