4
$\begingroup$

If I know that the set of operators {∨, & , ¬} is functionally complete, how do I go about proving/disproving the functional completeness of the following set of operators?

a) $\{\vee,\neg\}$

b) $\{\to,\neg\}$

c) $\{\to\}$

I have looked at the answer here for (b) : Prove that the set {→, ¬} is functionally complete

$\endgroup$

2 Answers 2

5
$\begingroup$

a)

$\{\vee, \neg\}$ is functionally complete. You only have to show that $\wedge$ (alias $\&$) is definable from $\{\vee, \neg\}$, because then you can express all the connectives of the complete set $\{\vee, \wedge, \neg\}$ (and the functions they induce). Like so: $$ p \wedge q \colon = \neg (\neg p \vee \neg q) $$

b)

$\{\to, \neg\}$ is functionally complete. By a), it suffices to show that $\vee$ is definable from $\{\to, \neg\}$. Thus: $$ p \vee q \colon = (\neg p \to q) $$

c)

$\{\to \}$ is not functionally complete. The proof is by induction on the complexity of propositional formulas in two variables. Let $2 = \{0,1\}$ be the set of truth values. We show that the always-false function $$F_{false} \colon (u,v) \mapsto 0 \colon 2 \times 2 \to 2$$ is not definable. Let $$ \begin{align} F_{\to} &\colon (u, v) \mapsto (\text{$1$ if $u\le v$ else $0$}) \colon 2 \times 2 \to 2 \\ \end{align} $$ $F_{\to}$ is just the truth table for implication "$\to$".

For any propositional formula $A = A(p,q)$ in variables $p, q$, we define the function $f_A \colon 2 \times 2 \to 2$ corresponding to A, inductively:

$$ \begin{align} f_p(u, v) &= u \tag{$pr_1$} \\ f_q(u, v) &= v \tag{$pr_1$} \\ f_{B\to C}(u,v) &= F_{\to}(f_B(u,v), f_C(u,v)) \tag{$Rule_{\to}$} \end{align} $$

Induction on formulas

Atomic formulas are $p$ and $q$. Clearly, neither $f_p$ nor $f_q$ is always false ($0$).

Now suppose $A$ is $B \to C$ with $B, C$ of lesser complexity (height, length). By induction hypothesis, neither $f_B$ nor $f_C$ is always false. Suppose $f_{B \to C}$ is always false: $$f_{B \to C}(u,v) = 0 \;\;\text{for all $u, v$.}$$ By ($Rule_{\to}$), this means: $$F_{\to}(f_B(u,v), f_C(u,v)) = 0 \;\;\text{for all $u, v$.}$$ By the definition of $F_{\to}$, this can only be so when $$ \begin{align} f_B(u,v) &= 1 \;\;\text{for all $u, v$, and} \tag{i} \\ f_C(u,v) &= 0 \;\;\text{for all $u, v$.} \tag{ii} \\ \end{align} $$ But by induction hypothesis, (ii) cannot be.

$\endgroup$
14
  • $\begingroup$ Is there any other way to prove the falsity of (iii) that does not involve induction? $\endgroup$
    – user141834
    Oct 16, 2015 at 1:25
  • 1
    $\begingroup$ Hmm good question. I couldn't think of one, anyway, or I would have used it assuming it was simpler. And if there really is no other way to prove it, that's harder still to prove (lol). Whatever the approach, you have to show that some function can't be expressed by any formula built up from 2 variables and implication. Perhaps there's some other theorem we could appeal to that would get rid of the induction -- maybe something involving "parity" of the truth function; but I'd bet that the proof of that theorem would be a much heavier induction. Basically, when you want to prove something.. $\endgroup$
    – BrianO
    Oct 16, 2015 at 1:35
  • 1
    $\begingroup$ (cont) about all formulas built up in a standard way, the standard approach is by induction on the construction of the formulas. I'll search a bit, though, see what I can see. $\endgroup$
    – BrianO
    Oct 16, 2015 at 1:36
  • 1
    $\begingroup$ There is a theorem characterizing the functionally complete sets of connectives, but I doubted you could just cite it in your answer -- it's more high-powered. Here's what Emil Post proved, in the 1940s: en.wikipedia.org/wiki/…. This section (&probably the whole article) is also worth checking out: en.wikipedia.org/wiki/Truth_function#Functional_completeness $\endgroup$
    – BrianO
    Oct 16, 2015 at 1:46
  • $\begingroup$ I have come across this statement: $\endgroup$
    – user141834
    Oct 16, 2015 at 2:42
1
$\begingroup$

Here is a proof that $\{ \rightarrow \}$ is not complete:

We'll show by structural induction that for any expression $\phi(p,q)$ that is composed of any number of instances of variables $p$ and $q$, and any number of $\rightarrow$ connectives: $\phi(T,T)=T$.

Base: $\phi(p,q) = p$ and $\phi(p,q) = q$. In both cases we have $\phi(T,T)=T$

Step: Suppose $\phi(p,q) = \phi_1(p,q) \rightarrow \phi_2(p,q)$ and that (inductive hypothesis) $\phi_1(T,T)=T$ and $\phi_2(T,T)=T$. Then $\phi(T,T) = \phi_1(T,T) \rightarrow \phi_2(T,T) = T \rightarrow T = T$

We have proven that for no such expression $\phi(T,T)=F$, and hence $\{ \rightarrow \}$ is not complete.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .