Unformatted text preview:

Lecture Notes for CS 388L, Part 1Propositional Formulas: SyntaxThe alphabet of propositional logic includes the propositional connectives> ⊥ ¬ ∧ ∨ →parentheses( )and other symbols, called atoms. We assume that atoms are different fromthe propositional connectives and parentheses, and that there are finitelymany of them. In examples, we will assume that p, q, r are atoms.By a string we understand a finite string of symbols in this alphabet.We define when a string is a (propositional) formula recursively, as follows:• every atom is a formula,• > and ⊥ are formulas,• if F is a formula then ¬F is a formula,• if F and G are formulas and  is one of the binary connectives ∧, ∨,→ then (F  G) is a formula.Properties of formulas can often be proved by structural induction. Insuch a proof, we check that all atoms and the 0-place connectives >, ⊥ havethe property P that we would like to establish, and that this property ispreserved when a new formula is formed using a unary or binary connective.More precisely, we show that• every atom has property P ,• > and ⊥ have property P ,• if a formula F has property P then so does ¬F ,• for any binary connective , if formulas F and G have property Pthen so does (F  G).Then we can conclude that property P holds for all formulas.For instance, we can use structural induction to prove that a binaryconnective never occurs at the very end of a formula, as follows. Atoms,> and ⊥ don’t contain binary connectives at all. If the last character ofF is not a binary connective then the last character of ¬F is not a binaryconnective. The last character (F  G) is not a binary connective.1Problem 1 A formula cannot contain two binary connectives next to eachother. True or false?Problem 2 If a formula contains more than one character then its lastcharacter is not an atom. True or false?We will abbreviate formulas of the form (F  G) by dropping the outer-most parentheses in them. For any formulas F1, F2, . . . , Fn(n > 2),F1∧ F2∧ · · · ∧ Fnwill stand for(· · · (F1∧ F2) ∧ · · · ∧ Fn).The abbreviation F1∨ F2∨ · · · ∨ Fnwill be understood in a similar way. Theexpression F ↔ G will be used as shorthand for(F → G) ∧ (G → F ).Propositional Formulas: SemanticsThe symbols f and t are called truth values. A (propositional) interpretation,or a truth assignment, is a function that maps atoms to truth values. Forinstance, if the atoms are p, q, r then an interpretation I can be defined bythe formulasI(p) = f, I(q) = f, I(r) = t. (1)An interpretation can be represented by the table of its values:p q rf f tThe semantics of propositional formulas introduced below defines whichtruth value is assigned to a formula F by an interpretation I. As a pre-liminary step, we need to associate functions with all unary and binaryconnectives: a function from {f, t} into {f, t} with the unary connective ¬,and a function from {f, t} × {f, t} into {f, t} with each of the binary connec-tives. These functions are denoted by the same symbols as the correspondingconnectives, and defined by the following tables:x ¬(x)f tt f2x y ∧(x, y) ∨(x, y) → (x, y)f f f f tf t f t tt f f t ft t t t tFor any formula F and any interpretation I, the truth value FIthat isassigned to F by I is defined recursively, as follows:• for any atom F , FI= I(F ),• >I= t, ⊥I= f,• (¬F )I= ¬(FI),• (F  G)I= (FI, GI) for every binary connective .If FI= t then we say that the interpretation I satisfies F and write I |= F .The truth table for a formula F shows the truth values assigned to Fby all interpretations. For instance, here is the truth table for the formula¬p ∨ ¬q:p q ¬p ∨ ¬qf f tf t tt f tt t f(We assume that there are no atoms other than p and q).Problem 3 For any formulas F1, . . . , Fn(n ≥ 1) and any interpretation I,(F1∧ · · · ∧ Fn)I= t iff FI1= · · · = FIn= t,(F1∨ · · · ∨ Fn)I= f iff FI1= · · · = FIn= f.Problem 4 (a) Assuming that the atoms are p, q, r, find a formula F suchthat (1) is the only interpretation satisfying F . (b) For any interpretation Ithere exists a formula F such that I is the only interpretation satisfying F .Problem 5 (a) Assuming that the atoms are p, q, r, find a formula F thatis satisfied by two interpretations: the interpretation defined by (1) and theinterpretation defined byI(p) = t, I(q) = t, I(r) = t.(b) For any set S of interpretations there exists a formula F such that forall interpretations I, I |= F iff I ∈ S.3Tautologies and EquivalenceA propositional formula F is a tautology if every interpretation satisfies F .Problem 6 Determine which of the formulas(p → q) ∨ (q → p),((p → q) → p) → p,(p → (q → r)) → ((p → q) → (p → r))are tautologies.A formula F is equivalent to a formula G (symbolically, F ∼ G) if, forevery interpretation I, FI= GI.Problem 7 (a) We know that conjunction and disjunction are associative:(F ∧ G) ∧ H ∼ F ∧ (G ∧ H),(F ∨ G) ∨ H ∼ F ∨ (G ∨ H).Determine whether equivalence has a similar property:(F ↔ G) ↔ H ∼ F ↔ (G ↔ H).(b) We know that implication distributes over conjunction:F → (G ∧ H) ∼ (F → G) ∧ (F → H).Find a similar transformation for (F ∨ G) → H.Problem 8 We know that conjunction distributes over disjunction andthat disjunction distributes over conjunction:F ∧ (G ∨ H) ∼ (F ∧ G) ∨ (F ∧ H),F ∨ (G ∧ H) ∼ (F ∨ G) ∧ (F ∨ H).Do these connectives distribute over equivalence?Problem 9 (a) De Morgan’s laws¬(F ∧ G) ∼ ¬F ∨ ¬G,¬(F ∨ G) ∼ ¬F ∧ ¬Gshow how to transform a formula of the form ¬(F  G) when  is ∧ or ∨.Find similar transformations for the cases when  is → or ↔.Problem 10 To simplify a formula means to find an equivalent formulathat is shorter. Simplify the formulasF ∨ (F ∧ G), F ∧ (F ∨ G), F ∨ (¬F ∧


View Full Document

UT CS 388 - Lecture Notes

Download Lecture Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture Notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture Notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?