Mathematical Logic
TeachersKAMIDE, NorihiroStaffInfo
Grade, SemesterYear 1 1st semest [Department of Information and Electronic Engineering, Faculty of Science and Engineering]
CategoryBasic Major Subjects
Elective, CreditsRequisites 2credit
 Syllabus Number3A111

Course Description

 The contents of the lectures are summarized as follows:
(1) proof system and semantics for propositional classical logic (formulas, tautology, sequent calculus, valuation semantics, soundness theorem, completeness theorem, etc.),
(2) proof system and semantics for first-order classical logic (quantifiers, valid formulas, soundness theorem, completeness theorem, etc.),
(3) how to construct normal forms of formulas in propositional and first-order classical logics (conjunction normal form, disjunction normal form, prenex normal form, etc.),
(4) sets and functions (set, function, injection, surjection, bijection, etc.),
(5) ordered sets and lattices (pre-ordered set, linearly ordered set, lattices, etc.), and
(6) Boolean algebras (Boolean algebra, relationship between Boolean algebras and propositional classical logic, etc.).

Course Objectives

 The aim of this course is to understand the following items:
(1) proof system and semantics for propositional classical logic,
(2) proof system and semantics for first-order classical logic,
(3) normal forms of formulas in propositional and first-order classical logics,
(4) sets and functions,
(5) ordered sets and lattices, and
(6) Boolean algebras.

Grading Policy

 Students are evaluated by a term examination, some midterm examinations, and some quizzes.

Textbook and Reference

KindTitleAuthorPublisher
TextbookNo textbook. The original slides and video contents are used.
ReferencesNo reference. The original slides and video contents are used.

Requirements(Assignments)

 The slides of the lecture should be read. The video contents of the lecture should be viewed.

Note

 LMS is used in this course.

Schedule

1Introduction: Outline of this course. Basic concepts of logic.
2Propositional classical logic (1): Propositions. Formulas. Truth table. Valuation semantics. Tautology.
3Propositional classical logic (2): Equivalent formulas. Conjunction normal form. Disjunction normal form.
4Propositional classical logic (3): Sequent calculus. Proofs by sequent calculus.
5Propositional classical logic (4): Soundness theorem. Completeness theorem. Cut-elimination theorem.
6First-order classical logic (1): Quantifiers. Formulas of first-order classical logic.
7First-order classical logic (2): Semantics. Valid formulas. Prenex normal form. Sequent calculus.
8First-order classical logic (3): Godel's completeness theorem. Compactness theorem. Midterm examination.
9Sets and functions (1): Sets. Cardinality. Operations on sets.
10Sets and functions (2): Functions. Surjection. Injection. Bijection.
11Sets and functions (3): Infinite sets. Countable sets. Uncountable sets. Diagonalisation argument.
12Relations: Relation. Equivalence relation. Order.
13Ordered sets and latices: Partially ordered sets. Totally ordered sets. Lattices. Boolean algebras.
14History of logic and the origin of computer: Godel's incompleteness theorem. Church-Turing thesis.
15Advanced topics: Non-classical logics and their applications to computer science. Term examination.