( ) P, P P, P (negation, NOT) P ( ) P, Q, P Q, P Q 3, P Q (logical product, AND) P Q ( ) P, Q, P Q, P Q, P Q (logical sum, OR) P Q ( ) P, Q, P Q, ( P

Size: px

Start display at page:

Download "( ) P, P P, P (negation, NOT) P ( ) P, Q, P Q, P Q 3, P Q (logical product, AND) P Q ( ) P, Q, P Q, P Q, P Q (logical sum, OR) P Q ( ) P, Q, P Q, ( P"

みさえねごろ
5 years ago
Views:

1 Advent Calendar Sutaro,,, ( ) Davidson, 5, 1 (quantification) (open sentence) 1,,,,,, 1 1 (propositional logic) (truth value) (proposition) (sentence) 2 (2-valued logic) 2, true false (truth assignment) (valuation) Definition 11 ( ) ( ) (3-valued logic) (many-valued logic) (fuzzy logic) 0 1 1

2 ( ) P, P P, P (negation, NOT) P ( ) P, Q, P Q, P Q 3, P Q (logical product, AND) P Q ( ) P, Q, P Q, P Q, P Q (logical sum, OR) P Q ( ) P, Q, P Q, ( P Q ) P Q P Q, P Q (P implies Q) P Q 4 ( ) P, Q, P Q, P Q, P Q (equivalence, XNOR) P Q (equivalent) true, (top) false, (bottom) (atomic proposition) (positive literal) 5, (molecular proposition) (formula) (wellformed formula),, P (P Q) R (P Q) (P R), P (Q R) (subformula) 6 (theory) M, M (interpretation) M 3 P Q, P Q, P Q, P Q, P Q, P Q 4, P Q P Q (vacuously truth) 5 P P (negative literal),, 1 (clause), 0 1 (Horn clause), 1 (definite clause), 0 (goal clause) 1 (conjunctive normal form), 1 1 (disjunctive normal form) 6 P (Q R) P, Q, R, R, Q R, P (R Q) φ Sub(φ) 2

3 φ true, M = φ true (satisfiable) false (unsatisfiable) T true M T T (model) 7 T true ( T ) φ, (tautology) (valid), T φ T =, φ, 2 8 Problem 12 P, Q, (1) (P Q) ( P Q) (2) (P Q) ( P Q) (3) (P Q) ( P Q) (4) (P Q) (P Q) (Q P ), Problem 13 (P Q) ( Q P ) 2 (reasoning) Gentzen (natural deduction) NK Definition 21 ( NK) φ, ψ, χ [φ] φ 9 NK (axiom) (inference rule) 10 7, true,, {φ, φ} 8, (Sheffer s stroke) 1 P Q P Q, (not and, NAND), 9 10 (intuitionistic logic) NJ 3

4 [ ] φ φ [ ] φ ψ φ ψ [ ] φ ψ φ [ ] φ φ ψ [ ] φ ψ [φ] χ χ [ψ] χ φ ψ ψ ψ φ ψ [ ] [φ] ψ φ ψ [ ] φ φ ψ ψ [ ] [φ] φ [ ] φ φ [ ] φ [ ] φ φ (modus ponens) 4

5 (proof figure) (end sequent) (conclusion) φ 1,, φ n, ψ, φ 1,, φ n ψ, (provable) φ 1,, φ n ψ T φ 1,, φ n T φ 1,, φ n 3, (semantics), (syntax), (completeness) (soundness), NK Theorem 31 ( ) NK, T φ, T = φ T φ Theorem 32 ( ) NK, T φ, T φ T = φ 4 4 (first-order predicate logic) (predicate symbol) (term), x y 5

6 Definition 41 ( ) (1) (2) (3) n f t 1,, t n, f(t 1,, t n ) 11 (atomic formula) (1) t, s, t = s (2) n P t 1,, t n, P (t 1,, t n ) (1) (2) (3) φ x xφ xφ (universal quantifier) (existential quantifier) x, x x (binding) (bound variable), (free variable) (closed fomula), (open formula), qf (quantifier-free formula) (bound occurrence), (free occurrence) φ BVar(φ), F Var(φ), φ Var(φ) Definition 42 ( ) x t (substitutable) (1) x t (2) φ x t def φ x t 11 6

7 (3) φ ψ x t def φ x t ψ x t (4) φ ψ x t def φ x t ψ x t (5) φ ψ x t def φ x t ψ x t (6) φ ψ x t def φ x t ψ x t (7) yφ x t def x y x / F Var(φ) φ x t ( y / Var(t)) (8) yφ x t def x y x / F Var(φ) φ x t ( y / Var(t)) φ[t/x] φ x t Definition 43 ( ) [ ] t = t [ ] φ[t/x] t = s φ[s/x], t, s φ x [ ] φ[y/x] xφ, y φ[y/x] xφ, φ x 7

8 [ ] xφ φ[t/x], t φ x [ ] φ[t/x] xφ, t φ x [ ] xφ ψ ψ ψ φ[y/x], y ψ φ[y/x] xφ ψ, φ x 5 Problem 51 (1) = P (Q P ) (2) = P P (3) = (P P ) Problem 52 (1) P (Q P ) (2) P P (3) (P P ) Problem 53 (1) xφ yφ (2) ( xφ ψ) ( yφ ψ) (3) x(φ ψ) ( yφ) ( zψ) 8

9 6 (classical logic), (non-classical logic) (intuitionistic logic) NJ, NJ NK, (law of de Morgan) (P Q) ( P Q) NJ, 12, (Kripke semantics) Definition 61 ( ) W 13 (W, ) (Kripke frame), W (possible world), (accesibility relation) I true false (W, ) I(φ, w) = true w w I(φ, w ) = true M = (W,, I) (Kripke model) 14 M, = w (1) M = w P def I(P, w) = true (2) M = w φ def I(φ, w) = false (3) M = w φ ψ def M = w φ M = w ψ (4) M = w φ ψ def M = w φ M = w ψ (5) M = w φ ψ def w w M = w φ w W M = w ψ M w M = w φ, = φ NJ 12 NJ NK, 13 ( x)[x x] ( ) ( x, y, z)[x y y z x z] ( ), (preorder), ( x, y)[x y y x x = y] ( ) (partial order), ( x, y)[x y y x] ( ) (total order) (linear order), 14 W, (W, ) (finite frame), (W,, I) (finite Kripke model) 9

10 Theorem 62 (NJ ) T φ, T = φ T φ 7 (modal logic) 15, φ φ, φ φ φ φ φ φ Definition 71 ( ) (1) (2) φ φ, φ, Definition 72 ( ) Definition 61 = w (1) M = w P def I(P, w) = true (2) M = w φ def I(φ, w) = false (3) M = w φ ψ def M = w φ M = w ψ (4) M = w φ ψ def M = w φ M = w ψ (5) M = w φ ψ def M = w φ M = w ψ (6) M = w φ def w w w W M = w φ, M w M = w φ, = φ S4, S5 GL Definition 73 ( ) 15, 10

11 [K] (φ ψ) ( φ ψ) 4 [T], [4], [5], [L] [T] [4] S4, [T] [5] S5, [4] [L] GL [T] φ φ [4] [5] [L] φ φ φ φ ( φ φ) φ [ ] φ φ 8 (paraconsistent logic) 16, {φ, φ} ψ,, φ, ( ), (logic of paradox) LP Definition 81 ( ) LP true, both, false 3 V ( 1) V( φ) = true def V(φ) = false 16 (dialetheism) 11

12 ( 2) V( φ) = false def V(φ) = true ( 3) V( φ) = both def V(φ) = both ( 1) V(φ ψ) = true def V(φ) = false V(ψ) = true ( 2) V(φ ψ) = false def V(φ) false V(ψ) = false ( 3) V(φ ψ) = both def V(φ) false V(ψ) = both φ true both = φ, (1) φ φ (2) φ (ψ ψ) φ (3) φ ψ φ 9 (temporal logic), (model checking) (branching time temporal logic) (linear time temporal logic) (tree), (computation tree logic) CTL, (linear temporal logic) LTL LTL (temporal operator),,, U Definition 91 (LTL ) LTL (1) LTL (2) φ, ψ LTL φ, φ, φ, φ U ψ LTL 12

13 Definition 92 (LTL ) ( ) = φ def φ ( ) = φ def φ ( ) = φ def φ ( U ) = φ U ψ def φ ψ φ 2 φ, k 1 φ k φ CTL LTL (path quantifier) E, A Definition 93 (CTL ) CTL (1) CTL (2) φ, ψ CTL E φ, A φ, E φ, A φ, E φ, A φ, E(φU ψ), A(φU ψ) CTL Definition 94 (CTL ) F LTL ( E ) = EF def F ( A ) = AF def F [1] Theodore Sider, Logic for Philosophy, Oxford University Press, 2010 [2] G Priest, R Routley and J Norman (eds), Paraconsistent Logics Philosophia Verlag, 1988 [3],,,

handout.dvi

handout.dvi http://www.kurims.kyoto-u.ac.jp/ ichiro 1 1.1 (formal verification, formal methods) [3] 2 theorem prover proof assistant PVSIsabell/HOLCoq Kripke M ϕ M ϕ M = ϕ model checker M ϕ M ϕ M M ϕ state explosion