In a 4-valued logic with values 0, 1/2, 2/3 and 1, three connectives are defined:

$V(\varphi \wedge \psi)$ = min $V((\varphi), V(\psi))$
$V(\varphi \vee \psi)$ = max $V((\varphi), V(\psi))$
$V(\diamond \varphi) = 1$ if $V(\varphi) \geq 2/3$, else 0

On formulas in the language composed of proposition letters and these three connectives we define a function $C$ that places the connective $\diamond$ in front of every proposition letter in the formula.

E.g.: $C((p \vee \diamond q) \vee q) = ((\diamond p \vee \diamond \diamond q)\vee \diamond q)$

The question:

Give an inductive definition of $C$

Inductive definitions have always given me troubles! I have the following versions of this inductive definition, and I just can't decide which version is better.:

Version 1:

base case:

$C(p) = \diamond p$

I never know what to write here, I got a plethora of possibilities and I never know which one I should take:

  • If $\varphi$ is an atomic formula, then $C(\varphi) = \diamond \varphi$
  • for all atomic formulas $\varphi$, $C(\varphi) = \diamond \varphi$
  • for all atoms $\varphi$, $C(\varphi) = \diamond \varphi$
  • If $p$ is an atomic formula, then $C(p) = \diamond p$
  • For all atomic formulas $p$, $C(p) = \diamond p$
  • For all atoms $p$, $C(p) = \diamond p$

Inductive step:

$C(\varphi \wedge \psi) = (C(\varphi) \wedge C(\psi))$
$C(\varphi \vee \psi) = (C(\varphi) \vee C(\psi))$
$C(\diamond \varphi) = \diamond (C(\varphi))$

Version 2:

With this one, I moved a step in the base case.

base case:

$C(p) = \diamond p$ and $C(\diamond p) = \diamond \diamond C(p)$

And the same trouble of which version to write like in version one

Inductive step:

$C(\varphi \wedge \psi) = (C(\varphi) \wedge C(\psi))$
$C(\varphi \vee \psi) = (C(\varphi) \vee C(\psi))$

  • $\begingroup$ What is $V$? is it a function? 1-arity? 2-arity? $\endgroup$ – DanielV May 3 '14 at 10:23
  • $\begingroup$ Yes. It's just a unary valuation function. $\endgroup$ – Hunan Rostomyan May 3 '14 at 10:30
  • 1
    $\begingroup$ Must be my years in front of a compiler, the parenthesis in the first two equations set my internal signals off. V is used as both unary and binary. I guess it is something like "the value of the expression". I'm guessing they were supposed to be $V(\varphi \land \psi) = \min\{V(\varphi), V(\psi)\}$. $\endgroup$ – DanielV May 3 '14 at 10:34
  • $\begingroup$ Exactly. Forget about what I said about min. $\endgroup$ – Hunan Rostomyan May 3 '14 at 10:39
  • $\begingroup$ @DanielV, HunanRostomyan The V is used in the other questions, but I needed that part to tell about the connectives that were used. $\endgroup$ – Garth Marenghi May 3 '14 at 13:41

I also think your first version is perfectly fine. Note that as a definition by recursion on the complexity of $\phi$ (which is the more appropriate term) your second candidate is ill-defined.

The base clause of a recursive definition of some function $f: \mathcal{F} \rightarrow A$ (where $\mathcal{F}$ is the set of formulas and $A$ some set) says that $f(\phi) = f_{At}(\phi)$, where $f_{At}$ is some function from $At$ (the set of atoms from $\mathcal{F}$) to $A$ and $\phi \in At$.

The base clause of your second version, however, uses a function defined on the set $At \cup \lbrace \diamond \phi : \phi \in At \rbrace \not = At$. In other words, the base clause must be specified independently of the values of $f$.

One might try to repair your second version by putting $C(\diamond \phi) = \diamond \diamond C(\phi)$ to the recursive clauses, where $\phi \in \mathcal{F}$. But this repaired version yields wrong results. According to that definition $C((p∨\diamond q)∨q) = ((\diamond p \lor \diamond \diamond C(q)) \lor \diamond p) = ((\diamond p \lor \diamond \diamond \diamond q) \lor \diamond p) \not = ((\diamond p \lor \diamond \diamond q) \lor \diamond p)$.


Your first version looks fine. Here is one, albeit not very explicit (because the language details are implicit) way of presenting the definition. $C(\phi)$ is defined by induction on the structure of $\phi$:

  • If $\phi \in \mathsf{Props}$, then $C(\phi) = \diamond\phi$;

  • If $\phi$ is of form $\psi \circ \chi$ and $\circ \in \mathsf{Cons_2}$, then $C(\phi) = C(\psi) \circ C(\chi)$;

  • If $\phi$ is of form $\diamond \psi$, then $C(\phi) = \diamond C(\psi)$;

where $\mathsf{Prop}$ and $\mathsf{Cons_2}$ are the sets of propositional letters and binary connectives respectively.


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.