0
$\begingroup$

I have a midterm exam today but still can't get a grasp on how to decide if given expressions are formulae or not. The three tasks are: $$1. \quad\forall y \forall x \forall yPxy $$ $$2. \quad\forall y(P \to \forall yQxy))$$ $$3. \quad\forall x(Qx)(Px \to Lx)$$

I understand the rules that atomic formulae are formulae and if A and B are formulae then $A \land B, A \lor B, \lnot A, A \to B$ are formulae and if x is a variable then $(\forall xA)$ and $(\exists xA)$ are formulae too and also if $t_1$ and $t_2$ are terms then $t_1 = t_2$ is a formula too.

Based on these rules how to I decide that given three mathematical expressions are formulae or not?

$\endgroup$
2
  • 1
    $\begingroup$ I think you might be missing at least one rule, in the sense that there's no way that formulae like "Qx" or "Pxy" can be introduced with your rules. But logic's not my area, so maybe I'm missing something. $\endgroup$ Nov 13 '19 at 12:05
  • $\begingroup$ The first two options fail to be formulae because they use the same variable on multiple quantifiers (in fact, they each use $\forall y$ twice) - is that repetition intentional? I don't even know what the third one is meant to say. Is it that for all $x$ such that $Q(x)$, $Px\to Lx$? Because that's just a clunky way to write $\forall x(Qx\land Px\to Lx)$. $\endgroup$
    – J.G.
    Nov 13 '19 at 12:45
1
$\begingroup$

You have to follow the syntactical specification of the language.

Your examples are about first-order logic and not propositional calculus.

Thus, you have to consider atomic formulas, like :

$Pxy, t_1=t_2$, etc.

If $P$ is a binary predicate symbol, then $Pxy$ is an atomic formula, and thus a formula, and also $∀x∀yPxy$ is.

What about $∀y∀x∀yPxy$ ? It depends on the details of the syntactical rules...

If the rule for quantifiers is :

if $\varphi$ is a formula and $x$ is a variable, then $\forall x\varphi$ and $\exists x\varphi$ are formulas,

then the expression above is a correctly written formula (well-formed formula).

Regarding $∀y(P→∀yQxy)$, it depends if $P$ is a $0$-ary predicate symbol.

The third formula is not well written; thus, it is not a formula.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.