Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm asked to prove by induction that a certain set of 4 function is complete on a 3-valued logic (Kleene). However, I'm having difficulty figuring out the induction step. More specifically, I'm not sure how to express multi-variate functions in terms of the bivariate and univariate functions I have.

I'd be grateful for any hints or examples of technique.

(following suggestions from the comments, I provide some more detail)

In detail: The logic is Kleene's $K_3$ with the operations $\neg, \wedge, \vee$ and a fourth univariate operation $*$ defined as $*T = F, *N = T, *F = N$. The question asks to prove expressional completeness: any function $f:\{T, F, N\}^n \to \{T, F, N\}$ can be expressed as a composition of the above four functions.

share|improve this question
    
You haven't gotten any answers yet, so your question may be too sketchy. One sort of inductive proof for propositional logic proceeds by induction on the construction of formulas. This is outlined for example on page 8 of R.M. Smullyan's text "First Order Logic." But your mentioning functions and your use of the computer-science tag suggests your context is different. Maybe you need to expand a bit on the details of your question. –  MikeC Feb 18 '12 at 4:46
    
What's the logic you're talking about? –  Doug Spoonwood Feb 18 '12 at 5:18

1 Answer 1

up vote 1 down vote accepted

I'll assume that you don't mean "a composition" literally and that any function that composes any number of those operations is allowed.

To solve this by induction, note that if you treat, say, the first argument separately, then for each possible value of the first argument you can treat the result as a function of the remaining arguments. In two-valued logic, this is already enough to solve the problem, since you can use it to write

$$f(a_1,\dotsc,a_n)=(a_1\land f_T(a_2,\dotsc,a_n))\lor((\neg a_1)\land f_F(a_2,\dotsc,a_n))\;.$$

In three-valued logic, it's not quite as simple, since you need to prevent the three terms you get from changing each other's results. Since $\land$ and $\lor$ still have the property that $\land$ passes $F$ through regardless of the other argument whereas $T$ lets the other argument pass through, and vice versa for $\lor$, you can analogously write

$$f(a_1,\dotsc,a_n)=(\overline{a_1}\land f_T(a_2,\dotsc,a_n))\lor(\overline{*a_1}\land f_N(a_2,\dotsc,a_n))\lor(\overline{*{*}a_1}\land f_F(a_2,\dotsc,a_n))$$

if you can find a unary operation $\overline x$ that's $T$ for $x=T$ and $F$ otherwise. To make that easier, note that $*$ and $\neg$ together generate the group of all permutations of $\{T,N,F\}$, so all you need to find is some unary operation that maps two values to the same value and the third to another, and then you can get the required operation $\overline x$ by applying permutations to the arguments and/or the output.

I'll leave it at that since you asked for hints; feel free to ask again if you have trouble constructing such a unary operation.

share|improve this answer
    
That was a very clear answer. The interplay between the three arguments was exactly the point I found confusing. I understand it now. Thank you! –  GLG Feb 18 '12 at 8:44
    
In the last part of the second equation, can we have $\overline{\neg a_1}$ instead of $\overline{**a_1}$? –  GLG Feb 18 '12 at 8:54
    
@Gal: Yes, that's a good idea. By the way, the extra spacing you got around the asterisks is because $\TeX$ thinks these are binary operators -- you can avoid that like this: *{*}a_1. –  joriki Feb 18 '12 at 12:34

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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