0
$\begingroup$

$\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)]$

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thankyou! Is the question ask whether the proposition is tautology or not? and can i find the answer by construct truth table like above? $\endgroup$
    – vedss
    Jan 13, 2020 at 4:01
  • $\begingroup$ If the question ask whether the proposition is a tautology, then yes, you could find the answer by truth table or by finding a context where it is not true. You did both. $\endgroup$ Jan 13, 2020 at 4:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .