Home / predicate logic proof calculator / Predicate logic - University of Pittsburgh

# Predicate logic - University of Pittsburgh - predicate logic proof calculator

CS 441 Discrete Mathematics for CS
Lecture 5
Predicate logic
Milos Hauskrecht
milos@cs.pitt.edu
5329 Sennott Square
CS 441 Discrete mathematics for CS M. Hauskrecht
Negation of quantifiers
English statement:
? Nothing is perfect.
? Translation: ? x Perfect(x)
Another way to express the same meaning:
? Everything ...
M. Hauskrecht
1
Negation of quantifiers
English statement:
? Nothing is perfect.
? Translation: ? x Perfect(x)
Another way to express the same meaning:
? Everything is imperfect.
? Translation: x ? Perfect(x)
Conclusion: ? x P (x) is equivalent to x ? P(x)
M. Hauskrecht
Negation of quantifiers
English statement:
? It is not the case that all dogs are fleabags.
? Translation: ? x Dog(x) Fleabag(x)
Another way to express the same meaning:
? There is a dog that ...
M. Hauskrecht
2
Negation of quantifiers
English statement:
? It is not the case that all dogs are fleabags.
? Translation: ? x Dog(x) Fleabag(x)
Another way to express the same meaning:
? There is a dog that is not a fleabag.
? Translation: x Dog(x) ? Fleabag(x)
? Logically equivalent to:
- x ? ( Dog(x) Fleabag(x) )
Conclusion: ? x P (x) is equivalent to x ? P(x)
M. Hauskrecht
Negation of quantified statements
(aka DeMorgan Laws for quantifiers)
Negation Equivalent
?x P(x) x ?P(x)
?x P(x) x ?P(x)
M. Hauskrecht
3

#### Pdf INFO

Title: Microsoft PowerPoint - Class5-new-out.ppt [Compatibility Mode]
Author: milos
Creator: PScript5.dll Version 5.2.2
Producer: Acrobat Distiller 10.1.5 (Windows)
CreationDate: Tue Jan 21 16:33:22 2014
ModDate: Tue Jan 21 16:33:22 2014
Tagged: no
Form: none
Pages: 16
Encrypted: no
Page size: 612 x 792 pts (letter) (rotated 0 degrees)
File size: 52794 bytes
Optimized: yes