Consider
“Every student in your class has taken a course in Java.”
Here is “x has taken a course in Java” and
the domain is students in your class.
Negating the original statement gives “It is not the case that
every student in your class has taken Java.” This implies that
“There is a student in your class who has not taken Java.”
Now Consider
“There is a student in this class who has taken a course in Java.”
Where is “x has taken a course in Java.”
Negating the original statement gives “It is not the case that
there is a student in this class who has taken Java.” This implies
that “Every student in this class has not taken Java”
The rules for negating quantifiers are (proof will be done later):
The reasoning in the table shows that:
These are important. You will use these.
Equivalence Formula of Predicate Calculus:
2.(
3.(
4.(
5.(
6.(
7.
8.
Implications of Predicate Calculus
2.(
NESTED (MORE THAN ONE) QUANTIFIERS
Definition: Two quantifiers are said to be nested if one is within
the scope of other.
Note: Anything within the scope of the quantifier can be
thought as propositional function
( )(ꓱ )Q(x,y) ( )P(x)
P(x)
Note: In the nested case, if both the quantifiers are same, then
ordering does not matter.
•Determine the truth value if ={ , , ,……, , }
( )( )(ꓱ )( + <14) Ans: True
(b) ( )( )( + <14) Ans: False
Example:
Let x and y are real numbers and P(x,y) denotes ‘x+y=0’. Find the
truth values of
a. P(x,y)
b. ꓱ P(x,y)
c. ꓱ P(x,y)
d. ꓱ ꓱ P(x,y)
Ans: a. False, b. True, c. False, d. True
Example: Translate the statement
x (C(x ) y (C(y ) F(x, y)))
where C(x) is “x has a computer,” and F(x,y) is “x and y are
friends,” and the domain for both x and y consists of all
students in your school.
Solution: Every student in your school has a computer or
has a friend who has a computer.
Choose the obvious predicates and express in predicate logic.
Example 1: “Brothers are siblings.”
Solution: x y (B(x,y) → S(x,y))
Example 2: “Everybody loves somebody.”
Solution: x y L(x,y)
Example 3: “There is someone who is loved by everyone.”
Solution: y x L(x,y)
Example 4: “There is someone who loves someone.”
Solution: x y L(x,y)
Example 5: “Everyone loves himself”
Solution: x L(x,x)
Example:
Our domain consists of all dogs and Fido is a dog.
“All dogs are cuddly.”
“Therefore, Fido is cuddly.”
Used often implicitly in Mathematical Proofs.
Example:
“There is someone who got an A in the course.”
“Let’s call her a and say that a got an A”
Example:
“Michelle got an A in the class.”
“Therefore, someone got an A in the class.”
Example : Using the rules of inference, construct a valid argument
to show that
“John Smith has two legs”
is a consequence of the premises:
“Every man has two legs.” “John Smith is a man.”
Solution: Let M(x) denote “x is a man” and L(x) “ x has two legs” and
let John Smith be a member of the domain.
Valid Argument:
Example : Use the rules of inference to construct a valid
argument showing that the conclusion
“Someone who passed the first exam has not read the book.”
follows from the premises
“A student in this class has not read the book.”
“Everyone in this class passed the first exam.”
Solution: Let C(x) denote “x is in this class,” B(x) denote “ x has
read the book,” and P(x) denote “x passed the first exam.”
First we translate the
premises and conclusion
into symbolic form.
Continued on next slide
Valid Argument:
Ex: All men are mortal. Socrates is a man. Therefore
Socrates is mortal.
Solution:
Introduce the propositional functions Man(x) denoting “x is a man”
and Mortal(x) denoting “x is mortal.” Specify the domain as all
people.
The two premises are:
The conclusion is:
Valid Argument