Boolean functions

Question

Boolean function f(x1,x2,x3):

If

f(x1,x2,x3)= TRUE

then

f(TRUE,x2,x3)= TRUE

f(x1,TRUE,x3)= TRUE

f(TRUE,TRUE,x3)= TRUE

f(x1,x2,TRUE)= TRUE

f(TRUE,x2,TRUE)= TRUE

f(x1,TRUE,TRUE)= TRUE

f(TRUE,TRUE,TRUE)= TRUE

For 2 arguments there is 6 such functions. How many such functions for N arguments?

What is the class of these function called?

Edit: For N=2 variables, these are the functions:

A   B|  F1  F2  F3  F4  F5  F6
0   0|  0   0   0   0   0   1
0   1|  0   0   0   1   1   1
1   0|  0   0   1   0   1   1
1   1|  0   1   1   1   1   1

F1(a,b) = False

F2(a,b) = A & B

F3(a,b) = A

F4(a,b) = B

F5(a,b) = A or B

F6(a,b) = True

Really $6$? You wrote down $7$ (or $8$ with initial). There is $2^N$ rows in truth table; but I'm not sure I understand you correctly. — Michael Galuza, Jul 19 '15 at 10:42
see edit. It is functions where if the result is true, then changing arbitrary false variables to true, the result must stay true. — Anlhord Smithson, Jul 19 '15 at 10:52
It's completely unclear. What is $F1$? If $f(x, y)$ is a function, and $f(x,, false) = f(x,, true)$, then $f(x, y)$ actually doesn't depend on $y$. Since you want to demand it for any variable, your functions are constant. Anyway, clarify your question. — Michael Galuza, Jul 19 '15 at 10:56
see edit. Please also note that XOR function doesn't belong to this class. — Anlhord Smithson, Jul 19 '15 at 11:06
In your question you neglect to state what condition "such" functions are supposed to satisfy. However, from a comment of yours, I guess you are asking about monotone Boolean functions. Is that right? — bof, Jul 19 '15 at 11:32

rudr · Answer 1 · 2022-07-12T11:29:59.680

Firstly some background issues, Boolean function is same just like other mathematical function f: (B^n)--->B , provided B={0,1} is a boolean domain and n is non-negative # . Boolean function of 1 variable can have 2 values 0 and 1. and with 0 var either it'll be 0 or 1, completely constant with no logical operations.

Similarly a boolean function of n var can have 2^n combinations of values. eg:- 3 var boolean functions can have 2^3 elements (all from 0 to 7 in binary.... 000,001,010,011,100,101,110,111)

now monotone boolean function . First understand the word monotone, which means either it is going up (increasing) or down (decreasing).

(1) shows increasing ; 2 shows decreasing; 3 is a constant y(that line is parallel to x axis) ; 4th shows increment and decrement both

Now coming to MBF (Monotone Boolean Function) : Function in which the value of the function follows the value of arguments. Consider a monotonic function fm and <x1 , x2 , ....., xn> as well as <y1, y2, .... , yn> as the sequence of the truth values :

if <x1 , x2 , ....., xn> <= <y1, y2, .... , yn> then fm(x1 , x2 , ....., xn) <= fm(y1, y2, .... , yn) .

To make this more sensible , consider F <T .

distributive lattice is a lattice which follows the distributive property

   1. (x+(y.z))=((x.y)+(x.z))
   2. (x.(y+z))=((x.y)+(x.z))

Now look at the boolean lattice below in the image . Boolean lattice is nothing but a distributive lattice with 0 and 1 in which every node / element has a complement (000 and 111 belongs to same lattice ). (0 is not equal to 1).

3-tuple boolean lattice

Now answer to your question

There's no function from F1 to F6 which satisfies this , except for F5 only. but if you consider 4- var function (input of values from the combination of A and B ) then from F1 to F6 they all are a part of MBFunction.

Furthermore , MBFs can't be concluded without looking at the logical expressions . Therefore for the n-arguments you'll have to state the logical expression for it. Although i must tell you , the # of MBFs in an n var is called nth Dedekind # . Its' calculation is still a challenge for all of us. For upto 8 variables only this is known. for upto n=6 , we know the in-equivalent MBFs.

forgive me for the handmade images,in Img 1 , 3rd graph looks more of a non-constant but consider that line as parallel to x-axis # means number

(edit-reference)

    for reference, visit:
 https://www.sfu.ca/~tstephen/Papers/r7.pdf

Thanks.

Boolean functions

1 Answers1