No comments posted yet


Slide 1

Predicate Logic, II Mathematics for Computer Science MIT 6.042J/18.062J Validity & Satisfiability

Slide 2

Propositional Validity True for all truth-values. Example:

Slide 3

Predicate Calculus Validity True for all domains and predicates. Example:

Slide 4

Proof strategy: assume left side is T, then prove right side is T Proving Validity

Slide 5

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

Slide 6

providing c does not occur in P Universal Generalization (UG)

Slide 7

Proof: Give counter-model, 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

Slide 8

DeMorgan’s Law for Quantifiers NOT(∀x. P(x)) IFF ∃y. NOT(P(y)) Another valid formula:

More by this User
Most Viewed