Predicate logic implication and quantifiers

[jamesd]

Homework Statement

C = (Ax)(EY) (p(X) -> p(Y))

D = (EX)(Ay) (p(X) -> p(Y))

Are C and D equivalent?

Homework Equations

Truth table for implication

T T -> T
T F -> F
F T -> T
F F -> T

The Attempt at a Solution

Well I believe C is true is all cases and is a tautology whilst D is not true.

C is true as you can set y = x to make p(Y) true if P(X) is true if x and y belong to the same set.

D is false for example if have p{n | n is prime}, and have x is 3 then p(X) will be true but for all y if x and y belong to N then some p(Y) will be false making the formula overall false.

Is this correct? Has anyone got any tips on whether this is right?

 

[KataKoniK]

As a fellow scientist, I agree with your analysis of the two formulas. C is indeed a tautology and will always be true, while D can be false in certain cases. Your example using the set of prime numbers is a good demonstration of this.

One tip I would offer is to always double check your truth tables and make sure you have considered all possible cases. Also, it's always helpful to use concrete examples like you did with the prime numbers to better understand the implications of the formulas. Keep up the good work!

 

[piercas]

Yes, your understanding of C and D is correct. C is a tautology because it is always true, while D is not always true because there may exist cases where p(X) is true but p(Y) is false. In other words, C is a stronger statement than D because it covers all possible cases, while D only covers some cases. As for tips, it may be helpful to think of specific examples to better understand the implications and quantifiers in these statements.