There is first-order predicate formula
$$A = \forall a (\neg P(a,a))$$
$$B = \forall a \forall b \forall c (P(a,b)\wedge P(b,c)\Rightarrow P(a,c))$$
$$B'= \forall a \forall b \forall c (P(a,b)\wedge P(b,c)\Rightarrow \neg P(a,c))$$
$$C = \forall a \forall b (P(a,b)\Rightarrow \neg P(b,a))$$
Question: Show that $A \vee B \vee B' \vee C$ is not valid.
Valid means there is no truth assignment makes it false.
What I got understood are truth assignment and resolving $A\Rightarrow B$ to $\neg A \vee B$.
But I can't understand how to implement '$\forall $' Universal notation into formula. And what happened when we use $P(a,b)$ instead of just $a$ or $b$.
So, can anyone solve above question with explaination step by step .
Many thanks. You're all legends!
Best Answer
Hint
To show that the formula is not valid, you have to find an interpretation such that the complex formula is False.
Being a disjunction, this means that the sought interpretation must falsifies every disjunct.
We can try with a simple interpretation $\mathcal I$ with domain $I = \{ 0,1,2,3 \}$.
Try with $P^{\mathcal I} = \{ (0,0), (0,1), (0,2), (1,0), (1,2), (1,3) \}$ as interpretation of the predicate symbol $P$.
(A) We have that $(0,0) \in P^{\mathcal I}$ and thus it is not true that $\lnot P(a,a)$ for every $a$.
(C) We have that $(0,1) \in P^{\mathcal I}$ and also $(1,0) \in P^{\mathcal I}$; thus it is not true that $P(a,b) \to \lnot P(b,a)$ for every $a,b$.
(B') We have that $(0,1) \in P^{\mathcal I}$ and $(1,2) \in P^{\mathcal I}$ and also $(0,2) \in P^{\mathcal I}$. Thus, it is not true that $(P(a,b) ∧ P(b,c)) \to ¬P(a,c)$, for every $a,b,c$.
In the same way, you can check (B).