# functionally complete set of connectives

• April 15th 2010, 07:29 AM
Jagger
functionally complete set of connectives
I have to proof that the connective ${|}$ is functionally complete.
According to the definition :

A set of connectives C is complete if whatever valuation function is definable in terms of the conectives of C

I have that $v(\phi | \psi) = 0$ iff $v(\phi) = v(\psi) = 1$

As a suggestion I have : Proof that $(NOT \phi)eq(\phi|\phi)$

Can someone guide me?

Thank's
• April 15th 2010, 07:48 AM
Failure
Quote:

Originally Posted by Jagger
I have to proof that the connective ${|}$ is functionally complete.
According to the definition :

A set of connectives C is complete if whatever valuation function is definable in terms of the conectives of C

I have that $v(\phi | \psi) = 0$ iff $v(\phi) = v(\psi) = 1$

As a suggestion I have : Proof that $(NOT \phi)eq(\phi|\phi)$

Can someone guide me?

Thank's

Well, I think it is obvious, that the system of connectives $\wedge, \vee, \neg$, that is "and", "or" and "not", is complete (proof: think of the distributive normal form of a propositional function, aka. valuation function).
If that's agreed, I would just try to show that these three basic connectives can be defined in terms of |. I assume that | stands for the "Sheffer stroke", i.e. for $a|b :\Leftrightarrow \neg(a\vee b)$.

If so, negation of $a$ can be expressed as $a|a$.

$a\vee b$ is $\neg (a|b)$, in other words, $(a|b)|(a|b)$.

Similarly for $a\wedge b$, since $a\wedge b$ is equivalent to $\neg (\neg a \vee \neg b)$, you get that $a\wedge b$ is equivalent to $(a|a)|(b|b)$
• April 15th 2010, 10:58 AM
Jagger
Ok thanks for your answer but I can't understand the meaning of functionally complete set of connectives.
As you said one connective y functionally complete when you can found a propositional formula formed in terms of NOT OR AND conectives equivalent to the other one...Is this true? or how can I know exactly when a connective or a set of connectives are functionally complete?

From the book of Dirk Van Dalen says "For each n-ary connective $defined by its valuation function, there is a proposition τ, containing only p1, . . . , pn, ∨ and ¬, such that |= τ ↔$(p1, . . . , pn). " but I don't understand the meaning of this Theorem
• April 15th 2010, 12:29 PM
Failure
Quote:

Originally Posted by Jagger
Ok thanks for your answer but I can't understand the meaning of functionally complete set of connectives.
As you said one connective y functionally complete when you can found a propositional formula formed in terms of NOT OR AND conectives equivalent to the other one...Is this true? or how can I know exactly when a connective or a set of connectives are functionally complete?

From the book of Dirk Van Dalen says "For each n-ary connective $defined by its valuation function, there is a proposition τ, containing only p1, . . . , pn, ∨ and ¬, such that |= τ ↔$(p1, . . . , pn). " but I don't understand the meaning of this Theorem

Well an "n-ary connective" is, basically, acting like a function (aka. its valuation function) that maps n-tupes of truth values (T or F) to a single truth value. In other words, the valuation function of an n-ary connective is a function $v:\{T,F\}^n\to \{T,F\}$.
Take a similar situation from a domain with which you are probably better acquainted: real numbers. To the "2-ary connective" that we call multiplication, and symbolize by $\times$, for example, there corresponds a 2-ary function $v:\mathbb{R}^2\to \mathbb{R}$ defined by $v(a,b) := a\times b$.
So, basically, the distinction between "n-ary connective" and "n-ary valuation function" is mainly one of notation, not substance.

The question that you are asked to answer is whether it is possible with a certain limited set of connectives to express any such valuation function (from n-tuples of truth values to a truth value, for any natural number n) with the help of a term consisting of connectives from that set exclusively. In other words, whether it is possible to write the definition of any n-ary valuation function in terms of connectives from that set exclusively.
So, for example, if the set of connectives is $\{\wedge, \neg\}$, then you have to figure out a way to express the valuation function $v(a,b) := a\vee b$ in terms of $\wedge$ and $\neg$. This works, because we know that $a\vee b\Leftrightarrow\neg \neg (a\vee b)\Leftrightarrow\neg (\neg a\wedge \neg b)$. And thus we have shown, that this particular valuation can indeed be expressed with the help of connectives from the set $\{\wedge,\neg\}$, namely by defining it like this: $v(a,b) := \neg (\neg a\wedge \neg b)$.
Now it might be surprising, and I suppose it was indeed surprising to some people, that it is in fact possible represent any valuation function that can be defined in terms of $\{\wedge,\vee,\neg\}$ with a connective like the Sheffer stroke $|$ alone.
• April 15th 2010, 12:50 PM
Failure
Quote:

Originally Posted by Jagger
Ok thanks for your answer but I can't understand the meaning of functionally complete set of connectives.
As you said one connective y functionally complete when you can found a propositional formula formed in terms of NOT OR AND conectives equivalent to the other one...Is this true? or how can I know exactly when a connective or a set of connectives are functionally complete?

I forgot to answer directly this particular question: If you are asked to show that a limited set of connectives is functionally complete, it suffices to show that every connective from some other set of connectives, that is already known to be functionally complete, can be expressed with a term consisting entirely of connectives from that limited set (and parentheses, and variables of course).

Now, I suspect that your teacher / your book has already shown that the set $\{\wedge,\vee,\neg\}$ of connectives is, indeed, functionally complete.
This is because every n-ary valuation function can be (uniquely) defined by its so called disjunctive normal form. This is simply a disjunction of conjunctions where each of the conjunctions specifies a pattern of T/F arguments for which the n-ary valuation function assumes the value T.
For example, $v(a,b,c) := (a\wedge \neg b\wedge c)\vee (\neg a\wedge b\wedge \neg c)$ is the disjunctive normal form of a valuation function v, which is T if and only if a=T, b=F and c=T, or if a=F, b=T, and c=F.
v(a,b,c) is F, according to its above disjunctive normal form, for all other patterns of arguments a,b, and c.