COS3761
Formal Logic III

COS3761 Study Guide

1. Propositional Logic

1.1. Declarative sentences

1.1.1. Understanding declarative sentences

1.1.2. Representing sentences in propositional logic

1.1.3. Examples of propositional formulas

1.2. Natural deduction

1.2.1. Rules for natural deduction

1.2.2. Derived rules

1.2.3. Natural deduction in summary

1.2.4. Provable equivalence

1.2.5. Proof by contradiction

1.3. Propositional logic as a formal language

1.4. Semantics of propositional logic

1.4.1. The meaning of logical connectives

1.4.2. Mathematical induction

1.4.3. Soundness of natural deduction

1.4.4. Completeness of natural deduction

1.5. Normal forms

1.5.1. Semantic equivalence, satisfiability and validity

1.5.2. Conjunctive normal forms and validity

1.5.3. Horn clauses and satisfiability

2. Predicate Logic

2.1. The need for a richer language

2.2. Predicate logic as a formal language

2.2.2. Formulas

2.2.3. Free and bound variables

2.2.4. Substitution

2.3. Proof theory of predicate logic

2.3.1. Natural deduction rules

2.3.2. Quantifier equivalences

2.4. Semantics of predicate logic

2.4.2. Semantic entailment

2.4.3. The semantics of equality

2.5. Undecidability of predicate logic

2.6. Expressiveness of predicate logic

5. Modal Logics and Agents

5.1. Modes of truth

5.2. Basic modal logic

5.2.2. Semantics

5.3. Logic engineering

5.3.1. The stock of valid formulas

5.3.2. Important properties of the accessibility relation

5.3.3. Correspondence theory

5.3.4. Some modal logics

5.4. Natural deduction

5.5. Reasoning about knowledge in a multi-agent system