Which of the following is valid first order formula?

Question

Which of the following is a valid first order formula ?

(Here $α$ and $β$ are first order formula with $x$ as their only free variable)

$[((∀x)[α] ⇒ (∀x)[β])] ⇒ [(∀x)[α ⇒ β]]$
$[(∀x)[α]] ⇒ [(∃x)[α ∧ β]]$
$[((∀x)[α ∨ β] ⇒ (∃x)[α])] ⇒ [(∀x)[α]]$
$[(∀x)[α ⇒ β]] ⇒ [((∀x)[α]) ⇒ (∀x)[β])]$

I tried by taking $α$ as $0=0$ and $β$ as $0=1$, but still not getting.

Is there something that I am missing ?

Not every valid FOL formula is a tautology of prop calculus (consider e.g. $\forall x (x=x)$. Thus, the truth-table method does not work (in general) to show validity. — Mauro ALLEGRANZA, Apr 12 '17 at 10:10
@MauroALLEGRANZA Any proof, as we just have to check the validity. Can you explain the 2nd line of thee question ? — Jon Garrick, Apr 12 '17 at 10:13
For the second one, try with $(x \ge 0)$ for $\alpha$ and $(x < 0)$ as $\beta$ in the domain $\mathbb N$. — Mauro ALLEGRANZA, Apr 12 '17 at 10:13
@MauroALLEGRANZA Yes, from your example, 2nd one is not valid . — Jon Garrick, Apr 12 '17 at 10:15
@MauroALLEGRANZA what I used as $α$ and $β$. Is that wrong ? — Jon Garrick, Apr 12 '17 at 10:18
For 1st and 4th, see the post which-of-the-following-is-a-valid-first-order-formula. — Mauro ALLEGRANZA, Apr 12 '17 at 10:23
@MauroALLEGRANZA Just a doubt. Here I have $α$ and $β$ and in that example, it is using $p(x)$ and $g(x)$ . Will there be any difference ?As I think $α$ and $β$ don't depend on $x$ but other one depends on $x$ . — Jon Garrick, Apr 12 '17 at 10:58
You have written "Here $α$ and $β$ are first order formula with $x$ as their only free variable". Thus thei are $α(x)$ and $β(x)$... — Mauro ALLEGRANZA, Apr 12 '17 at 11:48

mandy8055 · Answer 1 · 2019-09-09T14:58:26.477

In the given question the last point is the valid first order formula:

We can prove this by using law of contradiction and Rule of Inference (Modus Ponens specifically). The TT or boolean alzebra methods will be a bit difficult to apply in case of Predicate Logic, therefore your method of taking α as 0 = 0, β as 0 = 1 would be a little herculean.

Proof:

Let the consider the LHS to be true i.e. [(∀x)[α⇒β]] is true

which means

α1 => β1, α2 => β2, α3=> β3, ..., αn => βn are true. Now we have to prove the RHS to be false

Also, in implication we can write A => (B => C) as (A ^ B) => C

Therefore we can write, [(∀x)[α⇒β]]⇒[((∀x)[α]) as [(∀x)[α⇒β]] ^ [((∀x)[α]).

Now using Rule of detachment (Modus Ponens) i.e. If (p => q and p) => q we can prove that [(∀x)[α⇒β]] ^ [((∀x)[α]) => (∀x)[β]).

Note, here if we want to make RHS false by any means; we will not be able to. Therefore; ~F = T (Proof by contradiction)

Also, notice the first Option is the converse of the 4th option and is not valid. And other two options are vaguely out of order.

Which of the following is valid first order formula?

1 Answers1