Slides

Page 1

1 Propositional logic Propositional logic 2 Language Language Propositional logic 3 Language Definition 1. A propositional alphabet is assigned by: 1. A set 𝑋 = {𝑥0, 𝑥1, …}of variables. 2. The symbols ⊤ (true) and ⊥ (false). 3. The propositional connectives Connective Name Pronunciation ¬ negation not ∧ conjunction and ∨ disjunction or → implication implies ↔ biimplication if and only if 4. The auxiliary simbols ( and ). Remark 2. The only freedom in the choice of the alphabet is the set of variables, which can be infinite . Propositional logic 4 Language Definition 3. The language generated by a propositional alphabet is the smallest set 𝐿 containing all formulas, which are recursively defined by a finite application of the following formation rules: 1. all variables are formulas, 2. ⊤ and ⊥ are formulas, 3. if 𝜑 is a formula, then (¬𝜑)is a formula, 4. if 𝜑 and 𝜓 are formulas, so are (𝜑 ∧ 𝜓), (𝜑 ∨ 𝜓), (𝜑 → 𝜓)and (𝜑 ↔ 𝜓). Remark 4. • The symbols 𝜑 and 𝜓 are metalinguistic variables representing finite strings of symbols from the alphabet. • Formulas generated by rules 1 and 2 are called atomic. • Formulas are strings of finite length. In particular, each of them has finitely many variables. • Parentheses can not be omitted: without them we can not tell how 𝑥 ∧ 𝑦 ∨ 𝑧 was formed. • We will use □ as a metalinguistic variable ranging over ∧, ∨, → or ↔. • The formation rules can be succintly described by the context-free grammar 𝜑 :≔ 𝑥 | ⊤ | ⊥ | (¬𝜑) | (𝜑 ∧ 𝜓) | (𝜑 ∨ 𝜓) | (𝜑 → 𝜓) | (𝜑 ↔ 𝜓) Propositional logic 5 Language Remark 5. The language 𝐿 generated by a propositional alphabet exists and is a set because 1. Finite sequences of symbols from the alphabet form a set 𝑆 which satisfies conditions 1–4. 2. Subsets of 𝑆 which satisfy conditions 1–4 are closed under…