
Predicate Logic, II Mathematics for Computer Science MIT 6.042J/18.062J Validity & Satisfiability
Propositional Validity True for all truthvalues. Example:
Predicate Calculus Validity True for all domains and predicates. Example:
Proof strategy: assume left side is T, then prove right side is T Proving Validity
Proof: Assume left hand side.That is, for all values of z in the domain, Q(z) AND P(z) is true. Suppose val(z) = c, an element in the domain. Then Q(c) AND P(c) holds, and so Q(c) by itself holds. But c could have been any element of the domain. So we conclude ∀x.Q(x). Similarly conclude ∀y.P(y). Therefore, ∀x.Q(x) AND ∀y.P(y) QED ∀z[Q(z)∧P(z)] → [∀x.Q(x)∧∀y.P(y)] (by UG) Proving Validity
providing c does not occur in P Universal Generalization (UG)
Proof: Give countermodel, where left side of IMPLIES is T, but right side is F. Namely, let domain ::= {1, 2}, Q(z) ::= [z = 1], P(z) ::= [z = 2]. Similar Example is Not Valid
DeMorgan’s Law for Quantifiers NOT(∀x. P(x)) IFF ∃y. NOT(P(y)) Another valid formula:
URL: 
No comments posted yet
Comments