0
$\begingroup$

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!

$\endgroup$
0

2 Answers 2

1
$\begingroup$

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).

$\endgroup$
0
$\begingroup$

To say $A\vee B\vee B'\vee C$ is invalid, is to claim that we are able to evaluate it as false for some interpretation. Thus you need to construct a counterexample where $\neg A\wedge\neg B\wedge\neg B'\wedge\neg C$ holds.

But I can't understand how to implement '∀' Universal notation into formula.

The negation of a universal is an existential. So $\neg A\equiv \exists a~P(a,a)$. Thus your counterexample needs a witness to this (and likewise to the other statements' negations).

And what happened when we use $P(a,b)$ instead of just $a$ or $b$.

So, rather than evaluating propositions, we are evaluating predicates.

The bivalent predicate $P$ is a relation between terms in the domain . Your interpretation then must consist of some set of values and some relation over them which makes $\neg A\wedge\neg B\wedge\neg B'\wedge\neg C$ true.

Can you build it?

The natural numbers, or a subset, often may serve as a domain. Now, to have $\neg A$ hold true, we need a witness to $\exists a~P(a,a)$. So we declare $P(0,0)$ to be a fact.

  • If we evaluate $P(0,0)$ to be true, then $\neg A$ holds in this interpretation of $(\Bbb N,P)$.

And so forth...

$\endgroup$
7
  • $\begingroup$ Could you use predicate formula such as ∀a(¬P(a,a)) instead of A. $\endgroup$
    – Hume
    Sep 13, 2019 at 12:04
  • $\begingroup$ That is what A is. $\endgroup$ Sep 13, 2019 at 23:57
  • $\begingroup$ To make the "¬A ∧ ¬B ∧ ¬B ′ ∧ ¬C" true, we should prove ¬B, ¬B' and ¬C true. Right? $\endgroup$
    – Hume
    Sep 15, 2019 at 5:45
  • $\begingroup$ Yes, indeed. Do the "And so forth..." $\endgroup$ Sep 15, 2019 at 6:16
  • $\begingroup$ But we don't know what the P is. It can be smaller than or square and so on. How to prove A and other things are true? $\endgroup$
    – Hume
    Sep 15, 2019 at 6:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.