0

In my discrete math course we learned that when f is a finite function then there is a formula F in propositional logic such that:

F(x,y) is true iff f(x)=y

My question is, how do I construct such formula, other than some heuristic methods? In particular I'm asked to construct a formula for : $$f: \mathbb{Z}_{8} \rightarrow \mathbb{Z}_{8} $$ $$ f(x)=x^2$$ where the numbers are encoded in 3 bits binary number, so the formula contains 6 variables, 3 for input and 3 for output.

Tung Nguyen
  • 507

1 Answers1

1

There is always the brute force way. You can list all your results $f(x_1x_2x_3)=y_1y_2y_3$:

\begin{align} &f(\color{red}{000})=\color{blue}{000},\qquad f(001)=001,\qquad f(010)=100,\\ &f(011)=001,\qquad f(100)=000,\qquad f(101)=001,\\ &f(110)=100,\qquad f(111)=001. \end{align}

Then your $F(x_1,x_2,x_3,y_1,y_2,y_3)$ can be given by connecting all valid combinations with disjunction:

\begin{align} &(x_1=\color{red}0\land x_2=\color{red}0\land x_3=\color{red}0\land y_1=\color{blue}0\land y_2=\color{blue}0\land y_3=\color{blue}0)\\ \lor\; &(x_1=0\land x_2=0\land x_3=1\land y_1=0\land y_2=0\land y_3=1)\\ \lor\; &(x_1=0\land x_2=1\land x_3=0\land y_1=1\land y_2=0\land y_3=0)\\ &\qquad\qquad\vdots\\ \lor\; &(x_1=1\land x_2=1\land x_3=1\land y_1=0\land y_2=0\land y_3=1).\\ \end{align}

Now you have at least a formula $-$ a very long one though. You can try to simplify. In this example you can reach at something like this:

$$y_2=0\land y_3=x_3\land(y_1=1\leftrightarrow(x_2=1\land x_3=0)).$$

But I admit I found it by looking closely at the table of values instead of the long formula.

M. Winter
  • 29,928
  • That is what’s I’m looking for. Actually I knew this answer yesterday, after reading the lecture note more carefully, didn’t have time to write an answer though. Thanks ! – Tung Nguyen Dec 20 '17 at 14:24
  • Actually you can write x=0 as (not x) and x=1 as x, because I think “=“ is not a valid symbol in propositional logic. – Tung Nguyen Dec 20 '17 at 14:28
  • @TungNguyen Yes, rigorously speaking these are no propositional formulas. But you can easily translate them as you explained. And $x=y$ is the same as $(x\land y)\lor (\neg x\land \neg y)$ or short $\neg(x\oplus y)$ where $\oplus$ is XOR. And of course I wanted to highlight the binary digits colorful ;). – M. Winter Dec 20 '17 at 14:29