Predicate Calculus Examples, Help on HW3 Part 1, Questions 3-4, and HW4, Question 12

---

HW3-Part 1, Question 3 examples:

A)	1. - [AxP(x) + AxQ(x)] Given 2. -AxP(x) * -AxQ(x) 1, DeMorgans 3. Ex-P(x) * Ex-Q(x) 2, DeMorgans
B)	1. - [Ax[P(x) * Q(x)]] Given 2. Ex -[P(x) * Q(x)] 1, DeMorgans 3. Ex -P(x) + -Q(x) 2, DeMorgans
C)	1. Ex -P(x) + -Q(x) Given 2. Ex C(x) + B(x) 1, subs C(x)=-P(x), B(x)= -Q(x)
D)	1. [AxP(x) * Ax(P(x)-> Q(x))] => Ax Q(x) Given 2. -[AxP(x) * Ax(P(x)-> Q(x))] <= -[AxQ(x)] 1, Contrapositive 3. [-AxP(x) + -Ax(P(x)-> Q(x))] <= RHS 2, DeMorgans (on the left hand side) 4. [Ex-P(x) + Ex-(P(x)-> Q(x))] <= RHS 3, DeMorgans (on the LHS) 5. [Ex-P(x) + Ex-(-P(x) + Q(x))] <= RHS 4, Implication 6. [Ex-P(x) + Ex(P(x)*-Q(x))] <= RHS 5, DeMorgans on LHS 7. [Ex-P(x) + Ex(P(x)*-Q(x))] <= Ex-Q(x) 6, DeMorgans on RHS 8. [Ex-P(x) + Ex(P(x)*R(x))] <= ExR(x) 7, substitute R(x)=-Q(x)
HW3-Part 1, Question 4 examples:
A)	For ANY quantified statement, if it is negated, then you apply the negation to the quantifiers from left to right, and then apply that negation to the predicates, just as you normally would with propositions. The main point is, work from the OUTSIDE in (outermost parentheses to innermost). So, the only difference is, the quantifiers, and here are the four possibilities: -AxAy P(x,y) = Ex -Ay P(x,y) = Ex Ey -P(x,y) -AxEy P(x,y) = Ex -Ey P(x,y) = Ex Ay -P(x,y) -ExAy P(x,y) = Ax -Ay P(x,y) = Ax Ey -P(x,y) -ExEy P(x,y) = Ax -Ey P(x,y) = Ax Ay -P(x,y) Once you have -P(x,y), whatever P is you apply DeMorgans as usual.
B)	If you have the 5th edition book, the bottom of pg 47 and top of page 48 (NEGATING NESTED QUANTIFIERS) shows an example of negating AxEy(xy=1) and finishes with ExAy(xy!=1). Step by step is shown as: -AxEy(xy=1) Ex-Ey(xy=1) ExAy-(xy=1) ExAy(xy!=1)

"Exactly" example:

Write "There is exactly one dog with no owner" in predicate calculus.

First write "There is at least one dog with no owner":

Ed -Ep D(p,d)

Now, suppose there is another dog (not equal to d) like that:

Ef -Ep D(p,f) * (d!=f)

Does he exist? No! So we write:

Ed -Ep D(p,d) * -[ Ef -Ep D(p,f) * (d!=f)]

"Exactly" example 2:

Write "Each dog has exactly one owner" in predicate calculus.

First write "Each dog has at least one owner":

Ad Ep D(p,d)

Now, suppose dog d has another owner q besides p:

Eq D(q,d) * (q!=p)

Does he exist? No! So we write:

Ad [ Ep D(p,d) * -[ Eq D(q,d) * (q!=p)

] ]

DON'T quantify named objects: (Help on HW4, #12)

Given: L(x,y)=x likes y

a. "Tiffany likes Andy" is L(Tiffany, Andy)

b. "Tiffany doesn't like anyone" is -Ed L(Tiffany,d) or Ad -L(Tiffany,d)

More than one way to say the same thing: (Help on HW4, #12 e-f)

Ex (x > 7) => (x*x > 49) can be converted to an equivalent statement with no implication, and having a - on the front:

--Ex (x > 7) => (x*x > 49)	Double Negation
-Ax -[(x>7) => (x*x > 49)]	DeMorgans
-Ax -[-(x>7) + (x*x > 49)]	Implication
-Ax [--(x>7) * -(x*x > 49)]	DeMorgans
-Ax [(x>7) * (x*x <= 49)]	Double Negation

English translations of quantified statements

Suppose P(x) = x is a panda and the universe of discourse is all animals.

Statement	Intermediate English	What a person would say
Ex P(x)	There exists an x so that x is a panda.	There is a panda.
Ax P(x)	For each x, x is a panda.	All animals are pandas.
-Ex P(x)	There does not exist an x so that x is a panda.	There are no pandas.
Ax -P(x)	For each x, x is not a panda.	No animals are pandas.	Ax-P(x) <=> -Ex P(x)
Ex -P(x)	There exists an x so that x is not a panda.	There is an animal that is not a panda.
-Ax P(x)	It is not true that all animals are pandas.	Not all animals are pandas.	-Ax P(x) <=> Ex -P(x)