find out if formula is logically true

Question

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?

Answer 1

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.

Answer 2

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.