logic quantifiers truth

38 Views Asked by At

$\forall x \forall y \forall z[P(x,y) \land P(y,z) \implies P(x,z)]$

for the domain all people in the world, and
$P(x,y) \iff $ x likes y

how can i know that this is true or false?

i can change the equation to: $\forall x \forall y \forall z[ \neg P(x,y) \lor \neg P(y,z) \lor P(x,z)]$

i tried to draw truth tables

P(x,y) P(y,z) P(x,z) |$\neg P(x,y)$|$\neg P(y,z)$|P(x,z)|result

TTT |F F T T

TTF |F F F F

TFT |F F T T

TFF |F T F T

FTT |T F T T

FTF |T F F T

FFT |T T T T

FFF |T T F T

means is not true for all domain?

is the negation will be $\exists x \exists y \exists z[P(x,y) \land P(y,z) \land \neg P(x,z)]$

1

There are 1 best solutions below

2
On BEST ANSWER

The proposition you gave $$\forall x \forall y \forall z[P(x,y) \land P(y,z) \implies P(x,z)]$$ Is the definition of transitivity. It is true in some context, but not in all context.

E.g. let $x, y, z, \in \Bbb R$ and $P(x, y) \iff x<y$. Then your proposition is true. $x<y$ and $y<z$ implies $x<z$.

The negative of this proposition is $$\exists x \exists y \exists z[P(x,y) \land P(y,z) \land \neg P(x,z)]$$

If the domain is all the people in the world, then we could certainly find three people, Alice, Bob and Charles, such that Alice likes Bob, Bob likes Charles, but Alice doesn't like Charles. In this situation, the proposition is not always true.

Thus the proposition is not a tautology, we found a context where it is not always true. We also knew it was not a tautology by the truth table.