Need an example for Normal Form

27 Views Asked by At

We define Normal Form as:

Given a proposition $φ$ of $FOL$ (in some fixed language $L$), $φ$ is logically equivalent to a formula of the following form (called normal form):

$(Q_1x_1)$...$(Q_{​n}x_{​n})ψ$

Where,

ψ is a formula with no quantifiers occurring in it (called quantifier-free), and

$Q_i$ ​​ " is one or the other quantifier ($∀$ or $∃$).

We know a proposition is a statement like "For any ..., there exists ... such that..." Here is $ψ$ represent the statement "such that..."?

I want a concrete example.

1

There are 1 best solutions below

1
On BEST ANSWER

No, the "such that" is implied in the notation; $\psi$ is the statement following the "such that".

Here's an example: $$\forall x\exists y(x<y).$$ "For all $x$, there is some $y$ such that $x<y$." Does this make things clearer?


Actually, "such that" is tied to the existential quantifier $\exists$: we wouldn't translate "$\forall x(x+1\not=x)$" as "For all $x$ such that $x+1\not=x$", but rather "For all $x$, it is the case that $x+1\not=x$."

Basically, translate "$\forall x$" as "For all $x$, it is the case that" and "$\exists x$" as "There exists an $x$ such that". This will lead to lengthy translations - e.g. "$\forall x\exists y(x<y)$" translates to $$\mbox{"For all $x$, it is the case that there exists a $y$ such that $x<y$"},$$ which is a bit more complicated than "For all $x$ there is a $y$ such that $x<y$". However, it will also accurately translate the meaning of the sentence.