0

I have an formula , and i am to find if it is logically true.

((∃x)A ∧ (∃x)B) ⇒ (∃x)(A ∧ B)

By definition , to check if it is true , i should neg it and create a semantic tree. But with that it results in this formula to be true , while it isnt , what is the right way to do it then?

trolkura
  • 407
  • This is false. For example, take $A$ to be the statement that $x=0$ for $x\in\Bbb R$ and $B$ the statement that $x=1$. – Spenser Jan 05 '16 at 10:19
  • Counterexample: Let $A(x)$ denote true if and only if $x$ is even. Let $B(x)$ denote true if and only if $x$ is odd. – barak manos Jan 05 '16 at 10:33
  • The $x$ in $\exists x B$ is deceptive as it is not related to the $x$ in $\exists x A$. Consider that if you substitute $y$ for each free occurrence of $x$ (that is any occurrence not in the scope of any $\forall$ or $\exists$ occurring in $B$) then you get a formula $ B' $, with $ \exists x B\iff \exists y B'.$ So your original formula is equivalent to $(\exists x A) \land \exists y B'.$ – DanielWainfleet Jan 05 '16 at 23:56

2 Answers2

0

One way to show a statement isn't logically true is to exhibit a a model in which the statement is false.

A simple example here would be: interpret $A(x)$ as the predicate "$x$ is a square" and $B(x)$ as "$x$ is a circle." Then $$\exists xA(x)\land\exists xB(x)$$ is true, but $$\exists x (A(x)\land B(x))$$ is false, so your implication is false.

You can also use a tree to show the sentence is invalid. But trees are sometimes tedious. Before you work through a semantic tree to test validity, it's often helpful to interpret the statement in a few simple models to see whether it's plausible. If it's not plausible, you're likely to find a countermodel.

symplectomorphic
  • 18,604
  • but what about ((∀x)A ∨ (∀x)B) ⇒ (∀x)(A ∨ B) ? all x are square or all x are circle , that doesnt impliceate that all x are square or cicle , yet it is logically true – trolkura Jan 05 '16 at 10:31
  • @trolkura: yes, it does. if everything is a square, then, trivially, everything is a square or a circle; similarly if everything is a circle. – symplectomorphic Jan 05 '16 at 10:51
  • ((∃x)A ⇒ (∃x)B) ⇒ (∃x)(A ⇒ B) , one last question, what about this formula? i cant figure it out and semantic tree throws wrong result – trolkura Jan 06 '16 at 18:43
0

YES, we can show that a formula $\varphi$ is not valid through a semantic tree, considering its negation $\lnot \varphi$.

If the tree does not close, then $\lnot \varphi$ is satisfiable and thus $\varphi$ is not valid.

1) $(∃x)A ∧ (∃x)B$

2) $\lnot (∃x)(A ∧ B)$ --- 1) and 2) using the rule for $\lnot (\to)$

3) $(∃x)A$

4) $(∃x)B$ --- from 1) using the rule for $(\land)$

5) $Aa$ --- from 3) using the rule for $\exists$ : $a$ new

6) $Bb$ --- from 4) using the rule for $\exists$ : $b$ new

Now we have to apply the rule for $\lnot (\exists)$ to 2) for all the parameters already used in the tree : $a$ and $b$ :

7) $\lnot (Aa ∧ Ba)$

8) $\lnot (Ab ∧ Bb)$

Now we have to apply the rule for $\lnot (\land)$ to both 7) and 8), producing three branches, from left to right :

$9_L$) $\lnot Aa$ --- from 7) : this branch closes with 5)

$9_R$) $\lnot Ba$ --- from 7)

$10_L$) $\lnot Ab$ --- from 8)

$10_R$) $\lnot Bb$ --- from 8) : this branch closes with 6).

We have finished and we are left with an open path : 5), 6), $9_R$) and $10_L$).

This path defines an interpretation satisfying the formula $\lnot \varphi$ :

$Aa, \lnot Ab, \lnot Ba, Bb$

and thus providing a counter-example showing that $\varphi$ is not valid.

To verify it, consider that $Aa \land Bb$ sohws that $(∃x)A ∧ (∃x)B$ is true in this interpretation, while $Aa \land \lnot Ab$ and $\lnot Ba \land Bb$ show that $(∃x)(A ∧ B)$ is false in it.

Mauro ALLEGRANZA
  • 94,169