0
$\begingroup$

Let $f:$ {T,F}$^n \rightarrow$ {T,F}, i.e a function of n boolean variables.

Show that each $f$ can be expressed as a formula of only conjunctions and negations, and give an upper bound for the number of conjunctions aswell as a lower bound.

For example n=2 has 2^4=16 different functions and I can express them all using only conjunctions and negations. But, for the general case I'm really lost on how to proceed.

$\endgroup$
4
  • $\begingroup$ Can you show how you express all $16$? I can show you how to generalize once you do so. $\endgroup$
    – Rushabh Mehta
    Commented Feb 18, 2021 at 22:08
  • $\begingroup$ I don't have any method for doing it really, just brute forcing, for example f defined as f(T,T)=T, f(T,F)=F, f(F,T)=F, f(F,F)=T can be expressed as f($x_1,x_2$)=~(~($x_1$^$x_2$) ^ ~(~$x_1$^~$x_2$)) $\endgroup$
    – napadia
    Commented Feb 18, 2021 at 22:20
  • $\begingroup$ Do you know any related theorems? For example, do you know the theorem that any function can be expressed with only conjunctions, disjuntions, and negations? Or the theorem that any function can be expressed with just the Sheffer stroke operator? $\endgroup$
    – MJD
    Commented Feb 18, 2021 at 23:05
  • $\begingroup$ See math.stackexchange.com/questions/2646024/… $\endgroup$
    – Bram28
    Commented Feb 25, 2021 at 18:35

1 Answer 1

Reset to default
1
$\begingroup$

Welcome to MSE!

Hint:

You mention in the comments that you're proceeding by brute force for the $16$ functions when $n=2$... What's preventing you from doing this in the general case?

Given $n$ variables you have a (big) truth table with $2^n$ rows.

  • Can you find a way to implement any particular row? That is, can you find a combination of $\land$s and $\lnot$s which gets a fixed row correct?
  • Can you then modify each row function to be $0$ if you plug in a different row of the truth table, but still give the correct answer on your row of interest?
  • Once you have these, can you show that "or-ing" all of the rows together will give you the function you want?

You might take inspiration from the Lagrange Interpolation Formula. In fact, the problem you're describing is exactly showing that every boolean function is a polynomial over $\mathbb{Z}/2$!

I hope this helps ^_^

$\endgroup$
3
  • $\begingroup$ Thank you so much for your answer, I will try applying it. I was also thinking, is induction of any use here? $\endgroup$
    – napadia
    Commented Feb 18, 2021 at 23:06
  • $\begingroup$ Induction on $n$ is a great idea! Notice the first column of your truth table is half $0$s and half $1$s. So we get two functions $f_0$ and $f_1$ by "hard coding" the first input to $f$ to be $0$ or $1$ respectively. Each of these functions has $n-1$ variables, so (by induction) we know how to write them with $\land$s and $\lnot$s. Can you then find a way to combine $f_0$ and $f_1$ together to recover all of $f$? $\endgroup$
    – Chris Grossack
    Commented Feb 18, 2021 at 23:11
  • $\begingroup$ Hmm, so say I prove it for the base case, $n=1$, that all the functions can be written as conjunctions and negations. Then, assuming it holds for $n$, f($x_1,...,x_{n+1}$) can be written as $\lnot$(($x_1 \land $f$_1$($x_2$,...,$x_{n+1}$))$\land$($\lnot$x$_1$$\land$f$_2$(x$_2$,...,x$_{n+1}$))), is this what you mean? $\endgroup$
    – napadia
    Commented Feb 18, 2021 at 23:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .