Determine which of the following formulas are wffs, and justify which ones are not. [Verification]

first-order-logiclogicproof-verificationquantifiers

I have the following task:

"In each case, state which of the following formula are well formed formulas. If the formula is not well formed, provide a justification as to why. Else, specify the arity of the predicate symbols as well as the free variables

(Individual constants: a, b, c, … . Variables: u, v, w … .)."

  1. $\forall x \exists x \ (P(x) \to P(y))$
  2. $\forall x \ (P(x) \to \exists y \ Q(x,a,y))$
  3. $\forall a \ P(a) \to P(x)$
  4. $\exists x \ P(x) \to Q(\forall y \ R(y))$
  5. $\exists x \ P(Q(x))$
  6. $\forall x \exists x \ (P(x) \land P(y))$

Proposed solutions:

  1. Since this expression is quantified, it is a wff (despite the fact that y is a free variable). The arity of the predicate symbol P is 1 (unary) and there is the free variable y. (question– is it valid to have a formula such as this with both the univeral and existential quantifier?)
  2. all variables are quantified and this is a wff. The arity of P is 1 (unary). The arity of Q is 3 (ternary). There are no free variables.
  3. not a wff. x is not quantified, and the quantifier that does exist refers to a constant (is that even a thing?).
  4. I'm not sure about this one. My guess is that, since Q is not quantified, this is not a wff.
  5. This is a wff. P and Q have arity of 1/are unary predicate symbols.
  6. (Same answer as part 1).

Note: for part 6, the original question contained a typographical error [missing bracket in $\forall x \exists x \ (P(x) \land P(y)$ ]. I do not think this was intended, but in the case that it was, I think the desired answer would be "not a wff because of invalid syntax").

Definition of wff

Defining wff as it applies to this task is not entirely straightforward. The task was set in a course which did not explicitly provide a definition for wff. The course did however closely follow the text "Language, Proof and Logic" (Barwise, Etchemendy) 1st edition.

Here is the definition of wff from that text:

" Wffs are the “grammatical” expressions of fol. They are defined inductively. First, an atomic wff is any n-ary predicate followed by n terms. Complex wffs are constructed using connectives and quantifiers. The rules for constructing complex wffs are found on page 231. Wffs may have free variables. Sentences of fol are wffs with no free variables."

(page 231)

  1. If P is a wff, so is ¬P.
  2. If P1,…,Pn are wffs, so is (P1 ∧…∧Pn).
  3. If P1,…,Pn are wffs, so is (P1 ∨…∨Pn).
  4. If P and Q are wffs, so is (P→Q).
  5. If P and Q are wffs, so is (P↔Q).
  6. If P is a wff and ν is a variable (i.e., one of t, u, v, w, x, …), then ∀ν P is a wff, and any occurrence of ν in ∀νP is said to be bound.
  7. If P is a wff and ν is a variable, then∃νP is a wff, and any occurrence of ν in ∃ν P is said to be bound.

Best Answer

  1. and 4. are not wffs for the same reason that A $\rightarrow$ B is not a wff. (A$\rightarrow$B) is a wff, but A $\rightarrow$ B is not. The parentheses end up necessary, because otherwise the rule of substitution for wffs ends up failing. I'd have to check your formation rules otherwise, but I don't think there exists any other problems.
Related Question