Recently i was thinking about reprecentation of ternary conditional operator in programming:

"a ? b : c" means "if (a) then b else c".

Obviously it's equivalent to $(a \land b) \lor (\lnot a \land c)$.

Can we go more and represent any boolen f(x,y,z) as follows?

let $f(x,y,0) = g(x,y)$; and $f(x,y,1) = h(x,y)$;

$f(x,y,z) = z?f(x,y,1):f(x,y,0) = (g(x,y) \land \lnot z)) \lor (h(x,y) \land z) $

Can we go slightly more and get this representaion?

$f(x_1,...,x_n) = \bigvee \limits _{a_1,...a_n = \{0,1\}} {(f(a_1,...a_n) \land (x_1 \leftrightarrow a_1) \land ... \land (x_n \leftrightarrow a_n))} $

So, since $x \leftrightarrow y = (x \land y) \lor (\lnot x \land \lnot y)$, we can representi any *-ary function, given by it's truth table $f(a_1,...a_n)$, as the composition of classical binary functions.

Where i went wrong?

  • $\begingroup$ I think this is correct, except that you are ignoring that $\lnot$ is a unary function, not a binary function. You might like to look up the $\text{nand}$ function: it is a binary function which can be used to represent any boolean function regardless of arity. $\endgroup$ – DanielV Sep 7 '16 at 7:33
  • $\begingroup$ Suppose $b,c \in S$. Usually, in programming, when people write "a ? b : c", then they mean the function $f: \{T,F\} \to S$ where $f(T) = b$ and $f(F) = c$. Or are you also supposing that $b,c \in \{T,F\}$? $\endgroup$ – benguin Sep 7 '16 at 7:42
  • $\begingroup$ Yes, i wasn't correct. I had to write "... as the composition of classical logic function" (that is $\lnot, \lor, \land$). $\endgroup$ – Пегасище Sep 7 '16 at 8:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.