CISC 204 Lecture Notes - Lecture 5: Atomic Formula, Parse Tree, Formal Language
25 Sep 2017
School
Department
Course
Professor
Document Summary
( ) is a well-formed formula. Formulas and are syntactically equivalent if and only if and . Formulas are semantically equivalent if and only if they have the same truth table. Example: is a well-formed formula? (( p) q) (p (q ( r))) Semantics: for us, this is the assignment of t or f to a proposition. The semantics of each operator is de ned by using the semantics of its sub-formulas. The set of truth values contains two elements t and f, denoting true and false. A valuation or model of a formula is an assignment of each propositional atom in to a truth value. A common means of expressing the semantics of propositional logic is a truth table, which is a model written in tabular form. The truth tables for the four basic operators are: T if both are t, or else false. F if t f, or else true.
