北京雁栖湖应用数学研究院 北京雁栖湖应用数学研究院

  • 关于我们
    • 院长致辞
    • 理事会
    • 协作机构
    • 参观来访
  • 人员
    • 管理层
    • 科研人员
    • 博士后
    • 来访学者
    • 行政团队
    • 学术支持
  • 学术研究
    • 研究团队
    • 公开课
    • 讨论班
  • 招生招聘
    • 教研人员
    • 博士后
    • 学生
  • 会议
    • 学术会议
    • 工作坊
    • 论坛
  • 学院生活
    • 住宿
    • 交通
    • 配套设施
    • 周边旅游
  • 新闻
    • 新闻动态
    • 通知公告
    • 资料下载
关于我们
院长致辞
理事会
协作机构
参观来访
人员
管理层
科研人员
博士后
来访学者
行政团队
行政团队
学术支持
学术研究
研究团队
公开课
讨论班
招生招聘
教研人员
博士后
学生
会议
学术会议
工作坊
论坛
学院生活
住宿
交通
配套设施
周边旅游
新闻
新闻动态
通知公告
资料下载
清华大学 "求真书院"
清华大学丘成桐数学科学中心
清华三亚国际数学论坛
上海数学与交叉学科研究院
BIMSA > Introduction to mathematical logic
Introduction to mathematical logic
This course will use a material written by J.Carlström. It can be downloaded by https://bimsa.net/doc/notes/logic2008.pdf
Professor Lars Aake Andersson
讲师
Boris Shapiro
日期
2024年06月03日 至 07月11日
位置
Weekday Time Venue Online ID Password
周一,周四 13:30 - 15:05 A3-2-301 ZOOM 04 482 240 1589 BIMSA
课程大纲
Day 1 Introduction
• History and purpose of logic.
• Boolean algebras.
Inductively defined sets (Ch. 3 of Carlström)
• Motivation: What is formal syntax?  What are formulas?
• The natural numbers; recursion and induction principles
• General inductively defined sets; their recursion and induction principles
• Example: binary trees
Suggested Exercises: Carlström exercises 3.2.28, 3.2.29.

Day 2 Propositional logic (Ch. 4)
• Syntax: the inductively defined set of propositional formulas
• Interpretation of formulas as truth-value
• Semantics: valuations, interpretations, tautologies
• Logical equivalence and entailment.
Suggested exercises: Any from Ch. 4, especially 4.1.6, 4.2.32, 4.2.34, 4.2.37, 4.2.41

Day 3 Natural deduction (Ch. 5)
• Rules of natural deduction
• Notation: φ1, φ2, … φn ⊢ ψ
• Formal definition of derivations, derivability;
Suggested exercises: any from Ch. 5, especially 5.2.4, 5.2.7, 5.3.6–10, 5.4.4, 5.6.1, 5.6.3, and 5.6.6 (this one is a bit more challenging than the rest).

Day 4 Soundness Theorem (Ch. 6)
• Statement of Soundness Theorem (6.1.5): connection between derivability and validity in interpretations
• Proof of soundness
Suggested exercises: any from Ch.6, especially 6.1.22, 6.1.25, 6.1.28, 6.1.34, 6.1.38, 6.3.4

Day 5 Applications of Soundness (Ch. 6)
• Theories and consistency
• Proofs vs countermodels
Suggested exercises: any from Ch.6, especially 6.1.22, 6.1.25, 6.1.28, 6.1.34, 6.1.38, 6.3.4  
NOTE: For now, we’re skipping Ch.7, Normalization.  We may come back to it later in the course, if time allows

Day 6 Completeness (Ch. 8)
• Statement of completeness
• Statement of model existence lemma
• Roadmap to proof of completeness
• Maximal consistency
Suggested exercises: 8.1.3, 8.1.14, 8.1.17, 8.2.1, 8.2.6, 8.2.7

Day 7 Predicate Logic (Ch.9)
• Concept, examples: languages/theories of groups, posets, arithmetic
• Arity types (aka signatures, etc.)
• Terms, Formulas
• Substitution
• Free/bound occurrences of variables
Suggested exercises: 9.1.15, 9.1.17, 9.1.19, 9.2.7.

Day 8 Semantics (Ch. 10)
• Structures for signatures; valuations of variables. 
• NOTE: we define/notate interpretations slightly differently from Carlström — we consider the valuation of variables v as separate from the structure 𝒜, not a part of 𝒜 as in Carlström.
• Interpretation of terms and formulas, 
Suggested exercises: Any from Ch. 10

Day 9 Semantics (Ch. 10), cont’d
• Lemma: interpretation of a term/formula depends only on its free variables 
• Notations, terminology: A,v ⊨ φ, etc.
Simplifications (Ch. 11)
• Definition of “bound for”, “free for” (OBS: confusing terminology — this is completely different from “bound in”, “free in”!)
• Lemmas on interpretation of substitutions

Day 10 Natural deduction for predicate logic (Ch. 12)
• New rules for predicate logic
• Rules for equality
• Rules for quantifiers
• Heuristics for derivations in predicate logic
• Useful building-block derivations
Soundness for predicate logic (Ch. 13)
• Statement + proof outline
Suggested exercises: Any from Ch. 12; especially 12.1.6, 12.1.12, but also all from §12.2 are good.  For finding derivations: practice, practice, practice!

Day 11 Soundness (Ch. 13)
• Proof of soundness for predicate logic
• Adaptation of outline to predicate setting
• Cases for the new rules
Suggested exercises: Any from Ch. 13.

Day 12 Completeness (Ch. 14)
• Outline of proof: model existence lemma, constructing model from suitable theory
• Maximal consistency and the existence property
• Any maximally consistent theory with the existence property has a model
• Any consistent theory has (up to variable-renaming) a maximally consistent extension with the existence property
Suggested exercises: proof of 14.1.3, 14.1.4, 14.1.5, 14.1.15, 14.2.16.
视频公开
公开
笔记公开
公开
北京雁栖湖应用数学研究院
CONTACT

No. 544, Hefangkou Village Huaibei Town, Huairou District Beijing 101408

北京市怀柔区 河防口村544号
北京雁栖湖应用数学研究院 101408

Tel. 010-60661855 Tel. 010-60661855
Email. administration@bimsa.cn

版权所有 © 北京雁栖湖应用数学研究院

京ICP备2022029550号-1

京公网安备11011602001060 京公网安备11011602001060