Question

In each part below, give a formal proof that the sentence given is valid or else provided an interpretation in which the sentence is false.

(a) ∀xA(x) → ∃x[B(x) → A(x)].

(b) ∃x[B(x) → A(x)] → ∃xA(x).

Answer 1

Question : To prove the following sentences are valid or not.

Solution : A senetence is said to be valid if it is a Tautology ( Always True in all cases )

Truth table for conditional operator :

p	q	p   q
T	T	T
T	F	F
F	T	T
F	F	T

(a)  

Assuming the domain of and   contains only one element " x₁ " .

Transforming the sentence:

    

Now element x₁ can take values " True " and " False " .

(i) = True ;    = True , then the sentence becomes :

True [ True True ] , which results in True as per the truth table of conditional operator.

(ii) = True ;    = False , then ;

True [ False True ] which also results in True.

(iii) = False ;    = False , then ;

False [ False False ] which also results in True.

(iv) = False ;    = True , then ;

False [ True False ] which also results in True.

So for all cases the sentence results True value which makes it a Tautology and hence Valid.

(b)

Here also we are assuming the same condition as above. Only one element exists in the domain say " x₁ " .

Transforming the sentence:

Now element x₁ can take values " True " and " False " .

(i)   = True ;    = True , then the sentence becomes :

[ True True ] True , which results in True as per the truth table of conditional operator.

(ii)   = True ;    = False , then ;

[ False True ] True , which also results in True .

(iii) = False ;    = False , then ;

[ False False ]   False , which results in False which does not satisfy the requirement of a Tautology.

Hence the sentence is not valid.