4

Suppose A binary boolean function is showed by a true table. How can I know the (simplest) boolean formula which is interpreted by that function?

zty
  • 43

1 Answers1

3

Answer by an example...

Given the following truth-table:

x | y | z | f
--|---|---|--
0 | 0 | 0 | 0
--|---|---|--
0 | 0 | 1 | 1
--|---|---|--
0 | 1 | 0 | 0
--|---|---|--
0 | 1 | 1 | 0
--|---|---|--
1 | 0 | 0 | 1
--|---|---|--
1 | 0 | 1 | 0
--|---|---|--
1 | 1 | 0 | 1
--|---|---|--
1 | 1 | 1 | 1

Your function is: $f(x,y,z)=(\neg{x}\wedge\neg{y}\wedge{z})\vee({x}\wedge\neg{y}\wedge\neg{z})\vee({x}\wedge{y}\wedge\neg{z})\vee({x}\wedge{y}\wedge{z})$

If the table contains more rows with $f=1$ than rows with $f=0$, then you can apply the above technique for the rows where $f=0$ instead, and then wrap the entire expression with a $\neg(\dots)$.

barak manos
  • 43,109
  • How does this technique work!? – zty Sep 02 '14 at 11:45
  • @zty: I thought that the example clarified it pretty well. For each row with $f=1$, you $\wedge$ the variables in it (using $\neg$ for variables with value $0$). Then, you $\vee$ the expressions that you've created for the rows. If the table contains more rows with $f=1$ than rows with $f=0$, then you can apply this technique for the rows where $f=0$ instead, and then wrap the entire expression with a $\neg(\dots)$. – barak manos Sep 02 '14 at 11:56
  • I get it, can you explain why this technique work? – zty Sep 03 '14 at 02:11
  • @zty: Not really. It simply translates the table into a function. So it's kind of like you're asking me to explain a translation of a word from English to German. It is just a translation, there is nothing to explain about it. – barak manos Sep 03 '14 at 05:23
  • I finally get it. It's like translate boolean formula to english. How to translate the truth table to conjunctive normal form? – zty Sep 03 '14 at 09:14
  • @zty: To a CNF? Hmmmm... that might be a little harder, I'll need to think about it (you might want to publish that as a separate question). – barak manos Sep 03 '14 at 09:22