Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Swift Programming and Logic

Swift Programming and Logic

Yasuhiro Inami

September 20, 2019
Tweet

More Decks by Yasuhiro Inami

Other Decks in Programming

Transcript

  1. Patterns of Formula If A then B A and B

    A or B not A A → B A ∧ B A ∨ B ¬A
  2. Examples of Formula A ∧ (B → C) (A ∨

    B) ∧ (C → D) (¬A → ⊥ ) ∨ (¬B ∧ ⊤ )
  3. Example of Inference Rule: Modus Ponens A → B A

    B Inference Rules as a part of axiomatic system Premise 1: If A then B Premise 2: A Conclusion: B
  4. Truth Table (Interpretation of the formula) A B ¬A A∧B

    A∨B A→B 1 1 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 1 0 0 1 0 0 1 Valuation A → B A ∧ B A ∨ B ¬A
  5. Example of Truth Table A B ¬A ¬A∨B A→B (¬A∨B)

    → (A→B) (A→B) → (¬A∨B) 1 1 0 1 1 1 1 1 0 0 0 0 1 1 0 1 1 1 1 1 1 0 0 1 1 1 1 1 Some formulas are always 1 (true)
  6. (A → B) ↔ (¬A ∨ B) Tautology: Formulas that

    are always true in every possible interpretation P ↔ Q := (P → Q) ∧ (Q → P)
  7. Examples of Tautology A → A Law of Identity A

    ∨ ¬A Law of Excluded Middle
  8. Examples of Tautology (A → B) → ((B → C)

    → (A → C)) ((((A → B) → (¬C → ¬D)) → C) → E) → ((E → A) → (D → A)) ¬(A ∧ ¬A) (A ∧ ¬A) → B ((A → B) → A) → A ¬¬A → A (A → B) ↔ (¬B → ¬A) ¬(A ∧ B) ↔ (¬A ∨ ¬B) ¬(A ∨ B) ↔ (¬A ∧ ¬B)
  9. (A → B) → ((B → C) → (A →

    C)) ((((A → B) → (¬C → ¬D)) → C) → E) → ((E → A) → (D → A)) ¬(A ∧ ¬A) (A ∧ ¬A) → B ((A → B) → A) → A ¬¬A → A (A → B) ↔ (¬B → ¬A) ¬(A ∧ B) ↔ (¬A ∨ ¬B) ¬(A ∨ B) ↔ (¬A ∧ ¬B) Examples of Tautology Law of 
 Contradiction Principle of
 Explosion Double Negation
 Elimination Peirce’s Law Law of
 Contraposition De Morgan’s Laws Transitive Law Meredith’s Axiom
  10. Examples of Tautology There are infinite number of tautologies… Can

    we abstract into a finite subset as a basis? A → ¬¬A A → ¬¬¬¬A A → ¬¬¬¬¬¬A ⋯
  11. Formal System Axiom l Base premises (part of tautologies) Inference

    Rules l Deduces new formula from existing ones Using Axioms and Inference Rules to deduce Theorem (all possible tautologiesʣ
  12. Styles of Formal System •Gentzen Style l Many inference rules

    •Natural Deduction l + No axioms •Sequent Calculus l + 1 axiom (identity) •Hilbert Style •Many axioms + 1 inference rule (modus ponens)
  13. Gentzen Natural Deduction A B A ∧ B A ∧

    B A A ∧ B B A A ∨ B B A ∨ B A ∨ B C C C A → B A B B A → B ⊥ ¬A A ¬A ⊥ ⊥ A ⋮ [A] ¬¬A A ⋮ [A] ⋮ [B] ⋮ [A]
  14. Hilbert Style A → B A B B → (A

    → B) (A → (B → C)) → ((A → B) → (A → C)) ¬¬A → A A → A ∨ B ⊥ → A B → A ∨ B (A → C) → ((B → C) → ((A ∨ B) → C)) A ∧ B → A A ∧ B → B A → (B → (A ∧ B)) (A → ¬A) → ¬A ¬A → (A → B) Modus ponens is the only available
 inference rule
  15. Logic 㱻 Swift Programming A → B A ∧ B

    A ∨ B ¬A := A → ⊥ 㱻 Function Tuple Either ⊥ Either<A, B> Never typealias Not<A> = (A) -> Never (A, B) (A) -> B Bottom
  16. Gentzen Natural Deduction A B A ∧ B A ∧

    B A A ∧ B B A A ∨ B B A ∨ B A ∨ B C C C A → B A B B A → B ⊥ ¬A A ¬A ⊥ ⊥ A ⋮ [A] ¬¬A A ⋮ [A] ⋮ [B] ⋮ [A]
  17. /// `B ===> A → B` /// - Note: More

    formally, A ⊢ B ===> ⊢ A → B. func implyIntro<A, B>(_ b: B) -> ((A) -> B) { { _ in b } } /// `A, A → B ===> B` (Modus ponens) func implyElim<A, B>(_ f: (A) -> B, _ a: A) -> B { f(a) } A → B A B B A → B ⋮ [A]
  18. /// `A, B ===> A ∧ B` func andIntro<A, B>(_

    a: A, _ b: B) -> (A, B) { (a, b) } /// `A ∧ B ===> A` func andElim1<A, B>(_ ab: (A, B)) -> A { ab.0 } /// `A ∧ B ===> B` func andElim2<A, B>(_ ab: (A, B)) -> B { ab.1 } A B A ∧ B A ∧ B A A ∧ B B
  19. /// `A ===> A ∨ B` func orIntro1<A, B>(_ a:

    A) -> Either<A, B> { .left(a) } /// `B ===> A ∨ B` func orIntro2<A, B>(_ b: B) -> Either<A, B> { .right(b) } /// `A ∨ B, A → C, B → C ===> C` func orElim<A, B, C>( _ e: Either<A, B>, _ ac: (A) -> C, _ bc: (B) -> C ) -> C { switch e { case let .left(a): return ac(a) case let .right(b): return bc(b) } } A A ∨ B B A ∨ B A ∨ B C C C ⋮ [A] ⋮ [B]
  20. struct Not<A> { let f: (A) -> Never } ///

    `A ⊢ ⊥ ===> ⊢ ¬A` func notIntro<A>(_ x: Never) -> Not<A> { Not { _ in x } } /// `A, ¬A ===> ⊥` (NOTE: not using `fatalError`) func notElim<A>(_ a: A, _ notA: Not<A>) -> Never { notA.f(a) } ⊥ ¬A A ¬A ⊥ ⋮ [A]
  21. /// `⊥ ===> A` func absurd<A>(_ x: Never) -> A

    { // Do nothing, but it compiles. } ⊥ A
  22. Hilbert Style B → (A → B) (A → (B

    → C)) → ((A → B) → (A → C)) A → A ∨ B B → A ∨ B (A → C) → ((B → C) → ((A ∨ B) → C)) A ∧ B → A A ∧ B → B A → (B → (A ∧ B)) A → B A B Modus ponens is the only available
 inference rule ¬¬A → A ⊥ → A (A → ¬A) → ¬A ¬A → (A → B)
  23. (A → C) → ((B → C) → ((A ∨

    B) → C)) A → A ∨ B B → A ∨ B A ∧ B → A A ∧ B → B A → (B → (A ∧ B)) ¬¬A → A ⊥ → A (A → ¬A) → ¬A ¬A → (A → B) Hilbert Style A → B A B Modus ponens is the only available
 inference rule (A → (B → C)) → ((A → B) → (A → C)) A ∨ B := ¬A → B := ¬B → A A ∧ B := ¬(A → ¬B) := ¬(B → ¬A) ¬A := A → ⊥ NOTE: ∨, ∧, ¬ can be rewritten using → and ⊥ only B → (A → B)
  24. Combinatory Logic Kxy = x Sxyz = xz(yz) I =

    SKK K : X → Y → X S : (Z → Y → X) → (Z → Y) → Z → X I : X → X
  25. /// `K = A → (B → A)` func k<A,

    B>(_ a: A) -> (B) -> A { { _ in a } } /// `S = (A → (B → C)) → ((A → B) → (A → C))` func s<A, B, C>(_ a: @escaping (C) -> (A) -> B) -> (_ b: @escaping (C) -> A) -> (C) -> B { { b in { c in a(c)(b(c)) } } }
  26. /// `I = SKK: A → A` func i<A>(_ a:

    A) -> A { let k_: (A) -> (A) -> A = k let skk: (A) -> A = s(k)(k_) return skk(a) } i("hello") // "hello" i(123) // 123
  27. ((A → B) → A) → A A ∨ ¬A

    ¬¬A → A ¬(A ∧ B) → (¬A ∨ ¬B) (A → B) → (¬A ∨ B) (¬B → ¬A) → (A → B) Law of Excluded Middle Double Negation Elimination (One of)
 Law of Contraposition (One of) De Morgan’s Law Material Implication Peirce’s Law NOTE: Converse
 is tautology Tautologies that can’t be implemented in Swift
  28. /// `A ∨ ¬A` (Law of excluded middle) func excludedMiddle<A>()

    -> Either<A, Not<A>> { fatalError("Can't impl in Swift”) }
  29. /// `A ∨ ¬A` (Law of excluded middle) func excludedMiddle<A>()

    -> Either<A, Not<A>> { fatalError("Can't impl in Swift”) } ANY LANGUAGES! (No Premises) A ∨ ¬A
  30. /// `((A → B) → A) → A` func peirceLaw<A,

    B>() -> (((A) -> B) -> A) -> A { { (aba: ((A) -> B) -> A) in let ab: (A) -> B = { fatalError("Can't impl ") }() let a = aba(ab) return a } }
  31. “→” in Swift Programming Types Int Bool (A) -> B

    (Int)->Bool New type is constructed
  32. Curry-Howard Correspondence Intuitionistic Logic Swift Programming Proposition Type Proof Program

    → Introduction Function / Closure Modus Ponens Function Application Axiom Global Variable Assumption Free Variable Discharged Assumption Bound Variable
  33. Inheritance of truth value A 0 B 0 A 1

    B 0 A 1 B 0 A = 1 will be 
 inherited to future (Never becomes A = 0) New Theorem
  34. Inheritance of truth value A 0 ¬A 0 A 0

    ¬A 1 A 0 ¬A 1 If ¬A = 1, A = 0 from now & future (Never becomes A = 1) inherit
  35. Inheritance of truth value A 0 ¬A 0 A 0

    ¬A 1 A 0 ¬A 1 If ¬A = 1, A = 0 from now & future (Never becomes A = 1) JOIFSJU A 0 ¬A 0 A ∨ ¬A
  36. Inheritance of truth value A → B 1 A 0

    B 0 A → B 1 A 1 B 1 A → B 1 A 1 B 1 inherit If A = 1, B = 1 
 can also be obtained Never becomes
 A = 1, B = 0
  37. Kripke Semantics • Kripke Frame l Ordered set of possible

    world 
 e.g. → → • Kripke Model l Assigning inheriting truth value 
 for every possible world on the Frame • Tautology in Intuitionistic Logic
 … For any frame and for any valuation (= for any model), 
 formula is always true "͕ಘΒΕΔͱɺ
 #΋ࣗಈతʹಘΒΕΔ
  38. Classical Logic ⊂ Intuitionistic Logic Minimal Intuitionistic Classical A ∨

    ¬A ⊥ → A → , ∧ , ∨ , ¬, ⊥ Formulas using A → A ∨ B A ∧ B → A Law of
 Contradiction Law of 
 Excluded Middle ⋮ NOTE: Doesn’t mean Intuitionistic Logic owns Law of Excluded Middle ”directly” (See next slide)
  39. Glivenko’s Theorem: Classical to Intuitionistic Embedding Intuitionistic Classical A ∨

    ¬A ¬¬(A ∨ ¬A) ¬¬ Double
 Negation
 Translation Law of
 Excluded Middle Double-negated
 Excluded Middle
  40. ((A → B) → A) → A A ∨ ¬A

    ¬¬A → A ¬(A ∧ B) → (¬A ∨ ¬B) (A → B) → (¬A ∨ B) (¬B → ¬A) → (A → B) Law of Excluded Middle Double Negation Elimination (One of)
 Law of Contraposition (One of) De Morgan’s Law Material Implication Peirce’s Law NOTE: Converse
 is tautology Tautologies that can’t be implemented in Swift
  41. ¬¬(((A → B) → A) → A) ¬¬(A ∨ ¬A)

    ¬¬(¬¬A → A) ¬¬(¬(A ∧ B) → (¬A ∨ ¬B)) ¬¬((A → B) → (¬A ∨ B)) ¬¬((¬B → ¬A) → (A → B)) Tautologies in Intuitionistic Logic Adding double-negation will hold in 
 Intuitionistic Logic!
  42. ¬¬((A → B) → A) → ¬¬A ¬¬(A ∨ ¬A)

    ¬¬¬¬A → ¬¬A ¬¬¬(A ∧ B) → ¬¬(¬A ∨ ¬B) ¬¬(A → B) → ¬¬(¬A ∨ B) ¬¬(¬B → ¬A) → ¬¬(A → B) Tautologies in Intuitionistic Logic Using helper rule ¬¬(A → B) ¬¬A → ¬¬B
  43. /// `¬¬(A ∨ ¬A)` (Law of excluded middle in Intuitionistic

    Logic) func excludedMiddle_IL<A>() -> Not<Not<Either<A, Not<A>>>> { Not<Not<Either<A, Not<A>>>> { notEither in let notA: Not<A> = Not { a in notEither.f(.left(a)) } let either: Either<A, Not<A>> = .right(notA) return notEither.f(either) } }
  44. /// `¬¬¬¬A ===> ¬¬A` (Double negation elimination in IL) func

    doubleNegationElim_IL<A>( _ notNotNotNotA: Not<Not<Not<Not<A>>>> ) -> Not<Not<A>> { Not<Not<A>> { notA in notNotNotNotA.f( Not<Not<Not<A>>> { notNotA in notNotA.f(notA) } ) } }
  45. /// `¬¬¬(A ∧ B) ===> ¬¬(¬A ∨ ¬B)` (De-Morgan's Law

    in IL) func deMorgan4_IL<A, B>(_ notNotNotAB: Not<Not<Not<(A, B)>>>) -> Not<Not<Either<Not<A>, Not<B>>>> { Not<Not<Either<Not<A>, Not<B>>>> { (notEither: Not<Either<Not<A>, Not<B>>>) in let notNotAB = Not<Not<(A, B)>> { notAB in let notB = Not<B> { b in let notA = Not<A> { a in notAB.f((a, b)) } let either: Either<Not<A>, Not<B>> = .left(notA) return notEither.f(either) } let either: Either<Not<A>, Not<B>> = .right(notB) return notEither.f(either) } return notNotNotAB.f(notNotAB) } }
  46. /// `¬¬((A → B) → A) → ¬¬A` (Peirce's Law

    in IL) func peirceLaw_IL<A, B>() -> (Not<Not<((A) -> B) -> A>>) -> Not<Not<A>> { { notNotF in Not<Not<A>> { notA in let notABA = Not<((A) -> B) -> A> { aba in let ab: (A) -> B = { a in absurd(notElim(a, notA)) } let a = aba(ab) return notA.f(a) } return notNotF.f(notABA) } } }
  47. Peirce’s Law → Call with Current Continuation ¬¬(A → B)

    ¬¬A → ¬¬B ((A → ¬¬B) → ¬¬A) → ¬¬A Here, are used to gain ¬¬(A → B) A → ¬¬B ¬¬(((A → B) → A) → A) Peirce’s Law
  48. /// Continuation. typealias Cont<R, A> = (@escaping (A) -> R)

    -> R /// /// Call with Current Continuation. /// - Peirce (classical): `((A → B) → A) → A` /// - CallCC (intuitionistic): `((A → M<B>) → M<A>) → M<A>` /// /// - Note: `callCC` is like control operators e.g. `goto`, `return`, `throw`. /// func callCC<A, B, R>( _ f: @escaping (_ exit: @escaping (A) -> Cont<R, B>) -> Cont<R, A> ) -> Cont<R, A> { { outer in f { a in { _ in outer(a) } }(outer) } }
  49. /// - DoubleNegationElim (classical): `((A → ⊥) → ⊥) ===>

    A` /// - DoubleNegationElim (intuitionistic): `((A → M<⊥>) → M<⊥>) ===> M<A>` func doubleNegationElim_callCC<R, A>( _ doubleNegation: @escaping ( _ neg: @escaping (A) -> Cont<R, Never> ) -> Cont<R, Never> ) -> Cont<R, A> { callCC { exit -> Cont<R, A> in flatMap(doubleNegation(exit), absurd) } }
  50. Recap •Syntax and Semantics •Tautology as “always true” formula •Formal

    System: Axioms and Inference Rules •Intuitionistic Logic 㱻 Swift Programming (Curry-Howard) •Writing Law of Excluded Middle in Swift (Glivenko) •Learning Logic will help understand Swift’s type (system)