Logic for Computer Science - Lecture Notes
Alexandru Ioan Cuza University, Ias
,
i
Faculty of Computer Science
University Year 2025-2026
S
,
tefan Ciobˆac˘a
Andrei Arusoaie
Rodica Condurache
Cristian Masalagiu
Logic for Computer Science 2025-2026 Alexandru Ioan Cuza University
Part I - Propositional Logic 2 Lecture notes - to print in color
Contents
1 Introduction 7
2 Informal Propositional Logic 9
2.1 Propositions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Atomic Propositions . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3 Conjunctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.4 Disjunctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.5 Implications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.6 Negations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.7 Equivalences . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.8 Logical Connectives . . . . . . . . . . . . . . . . . . . . . . . . 14
2.9 Ambiguities in Natural Language . . . . . . . . . . . . . . . . . 15
2.10 Exercise Sheet . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3 The Formal Syntax of Propositional Logic 19
3.1 Alphabets in Computer Science . . . . . . . . . . . . . . . . . . 19
3.2 The Alphabet of Propositional Logic . . . . . . . . . . . . . . . 20
3.3 Propositional Formulae . . . . . . . . . . . . . . . . . . . . . . 20
3.4 Showing That a Word Is In PL . . . . . . . . . . . . . . . . . . 21
3.5 The Main Connective of a Formula . . . . . . . . . . . . . . . . 22
3.6 Showing That a Word Is Not in PL . . . . . . . . . . . . . . . . 22
3.7 Unique Readability . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.8 Object-language and meta-language . . . . . . . . . . . . . . . 24
3.9 Exercise Sheet . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4 Functions Defined Recursively on PL 27
4.1 The Abstract Syntax Tree of a Formula . . . . . . . . . . . . . 28
4.2 Other Examples of Recursively Defined Functions . . . . . . . . 30
4.3 Proofs by Structural Induction . . . . . . . . . . . . . . . . . . 31
4.4 Exercise Sheet . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3
End of Document
229
