Computer Science 2209A/B Lecture Notes - Lecture 3: Formal Language, Propositional Calculus, Atomic Formula

• School: Western University
• Department: Computer Science
• Course: Computer Science 2209A/B
• Professor: Lila Kari

Document Summary

By using connectives, we can combine propositions, whether they are atomic themselves or compound: to prevent ambiguity, we introduce fully paranthesized expressions that can be parsed in a unique way. When possible, we will omit parantheses and use precedence rules. Note that u = u = u if u = w vw. 2 are expressions, then v is a segment of u. If v = u then v is a proper segment of u. if u = vw, where u, v, w are expressions, then v is an initial segment of u. Similarly, w is a terminal segment of u. An atom (atomic formula) is an expression consisting of a proposition variable or constant only. An expression in l p is called a formula (well-formed formula) iff it can be constructed according to the following formation rules: 1. If a is a formula then so is ( a): ifa,b areformulasthensoare(a b),(a b),(a b) and (a b). 4.