Proving that every boolean function can be represented as a propositional logic formula.

Question

I'm currently struggling a bit on this question. I tried induction on the number of parameters.

Induction.

Start $n=0$:

Let $f$ be a boolean function with $0$ parameters.

2 Cases: $f()=0$ or $f()=1$

For case 1 we have a formula like $a \land \lnot a$

Case 2 formula $a \lor \lnot a$

Now the induction step is where i am struggling:

$f(x_1,x_2,...x_n,x_{n+1})=1$ or

$f(x_1,x_2,...x_n,x_{n+1})=0$

Henno Brandsma · Accepted Answer · 2019-03-05T22:03:12.967

3

Just use the conjunctive normal form, or the disjunctive normal form no induction needed, really. Both obey your requirements, I think.

But if you want induction, try: given $f: \{0,1\}^{n+1} \to \{0,1\}$ define the "sections" $g_0: \{0,1\}^n \to \{0,1\}$ by $g_0(x_1,\ldots,x_n) = f(x_1,\ldots,x_n, 0)$ and $g_1$ similarly with $x_{n+1} = 1$.

By induction represent $g_0(x_1,\ldots, x_n) = \phi_0(x_1, \ldots, x_n)$ using some formula with $\land, \lor$ and $\lnot$ in the terms $x_i$. Ditto with $g_1$ and some $\phi_1$. Then $$f(x_1, \ldots,x_n, x_{n+1}) = (\phi_0(x_0,\ldots,x_n) \land \lnot x_{n+1}) \lor (\phi_1(x_0,\ldots,x_n) \land x_{n+1})$$

which is also of the required form.

edited Mar 05 '19 at 22:03

answered Sep 03 '17 at 11:22

Henno Brandsma

242,131

Well, if one happens to want a formal proof, I don't think we can get around using induction somewhere. But it can probably he hidden away with some appropriate handwaving in an ordinary prose argument. – hmakholm left over Monica Sep 03 '17 at 11:32
@HenningMakholm one way is to use one conjunction for every preimage of $1$. I don't see any induction there ,you can just define it from the truth table. – Henno Brandsma Sep 03 '17 at 11:34
yes i know dnf works, but i wanted to use induction. Thanks – asddf Sep 03 '17 at 11:35
@HennoBrandsma: I think (again, to be completely formal) that one needs induction to prove an arbitrary element of the domain has a conjunction corresponding to it. – hmakholm left over Monica Sep 03 '17 at 11:38
Why can i define $g_0$ as equal to a function $f$ who has one parameter more ? – asddf Sep 03 '17 at 11:55
@asddf $g_0$ has $n$ parameters and we use $f$ with the last variable fixed to $0$ to define its value. – Henno Brandsma Sep 03 '17 at 11:57
ok i got it, thanks – asddf Sep 03 '17 at 12:00

Proving that every boolean function can be represented as a propositional logic formula.

1 Answers1