Mathematical Logic
Teachers KAMIDE, Norihiro Year 1　1st semest [Department of Information and Electronic Engineering, Faculty of Science and Engineering] Basic Major Subjects Requisites　2credit 3A111

#### 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.

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.