Please, Can you show, how to check if a function is * Linear or not (for both f and g)*?

Dark Mode

Samujjal Das 1
asked
in Digital Logic
Apr 12, 2016

13,856 views
11 votes

A set of Boolean functions is

functionally complete, if all other Boolean functions can be constructed from this set and a set of input variables are provided.

A set is said to functionally complete if we can derive a set which is already functionally complete.

Example of functionally complete set {AND ,OR,NOT}, {OR,NOT},{AND,NOT} .

So to prove a boolean functionally complete derive any one of the above functionally complete set.

5 votes

A set of Boolean functions isfunctionally complete, if all other Boolean functions can be constructed from this set and a set of input variables are provided.

You will sometimes see circuits implemented using only NANDs or using only NORs, and the reason for this is because they are functionally complete and minimal. You only have to build the circuit using one kind of gate. Of course, using a single gate is likely to make the circuit "larger", i.e., more gates than using many different kinds of gates, but usually it's worth the tradeoff, i.e., it's better to use more of one kind of gate than fewer of many different gates.

5 votes

A function is considered as functionally complete if it does not belong to T0,T1,L,M,S which are

Property 1: We say that boolean function f preserves zero, if on the 0-input it produces 0. By the 0-input we mean such an input, where every input variable is 0 (this input usually corresponds to the ﬁrst row of the truth table). We denote the class of zero-preserving boolean functions as T0 and write f ∈ T0.

Property 2: Similarly to T0, we say that boolean function f preserves one, if on 1-input, it produces 1. The 1-input is the input where all the input variables are 1 (this input usually corresponds to the last row of the truth table). We denote the class of one-preserving boolean functions as T1 and write f ∈ T1.

Property 3: We say that boolean function f is linear if one of the following two statements holds for f:

For every 1-value of f, the number of 1’s in the corresponding input is odd, and for every 0-value of f, the number of 1’s in the corresponding input is even.

or

For every 1-value of f, the number of 1’s in the corresponding input is even, and for every 0-value of f, the number of 1’s in the corresponding input is odd.

If one of these statements holds for f, we say that f is linear1. We denote the class of linear boolean functions with L and write f ∈ L.

Property 4: We say that boolean function f is monotone if for every input, switching any input variable from 0 to 1 can only result in the function’s switching its value from 0 to 1, and never from 1 to 0. We denote the class of monotone boolean functions with M and write f ∈ M.

Property 5: We say that boolean function f(x1,…,xn) is self-dual if f(x1,…,xn) = ¬f(¬x1,…,¬xn).

The function on the right in the equality above (the one with negations) is called the dual of f. We will call the class of self-dual boolean functions S and write f ∈ S.

Take this example :

Consider the operations

f(X, Y, Z) = X’YZ + XY’ + Y’Z’ and g(X′, Y, Z) = X′YZ + X′YZ′ + XY

Which one of the following is correct?

(A) Both {f} and {g} are functionally complete

(B) Only {f} is functionally complete

(C) Only {g} is functionally complete

(D) Neither {f} nor {g} is functionally complete

Solution : As in our case we can see on giving all i/p to 0 (g )produce 0 so it preserving 0 and can’t be functionally complete.

But f is neither preserving 0 nor 1.

F is not linear(see defn. of linear above)

F is not monotone(see defn. of monotone above)

F is not self dual as f(x,y,z) is not equal to –f(-x,-y,-z)

So f is functionally complete.

Hence ans is (B) part.

Reference :

https://cs.hse.ru/data/2015/05/28/1096847873/Lecture%2013.1.pdf

http://scholar.google.co.in/scholar_url?url=https://www.researchgate.net/profile/Francis_Pelletier2/publication/38355402_Post%2527s_functional_completeness_theorem/links/0c960524f7ef05bab1000000/Posts-functional-completeness-theorem.pdf&hl=en&sa=X&scisig=AAGBfm0I6Zlxuq_IJXiIpTnV6XvSrOUlNw&nossl=1&oi=scholarr

Property 1: We say that boolean function f preserves zero, if on the 0-input it produces 0. By the 0-input we mean such an input, where every input variable is 0 (this input usually corresponds to the ﬁrst row of the truth table). We denote the class of zero-preserving boolean functions as T0 and write f ∈ T0.

Property 2: Similarly to T0, we say that boolean function f preserves one, if on 1-input, it produces 1. The 1-input is the input where all the input variables are 1 (this input usually corresponds to the last row of the truth table). We denote the class of one-preserving boolean functions as T1 and write f ∈ T1.

Property 3: We say that boolean function f is linear if one of the following two statements holds for f:

For every 1-value of f, the number of 1’s in the corresponding input is odd, and for every 0-value of f, the number of 1’s in the corresponding input is even.

or

For every 1-value of f, the number of 1’s in the corresponding input is even, and for every 0-value of f, the number of 1’s in the corresponding input is odd.

If one of these statements holds for f, we say that f is linear1. We denote the class of linear boolean functions with L and write f ∈ L.

Property 4: We say that boolean function f is monotone if for every input, switching any input variable from 0 to 1 can only result in the function’s switching its value from 0 to 1, and never from 1 to 0. We denote the class of monotone boolean functions with M and write f ∈ M.

Property 5: We say that boolean function f(x1,…,xn) is self-dual if f(x1,…,xn) = ¬f(¬x1,…,¬xn).

The function on the right in the equality above (the one with negations) is called the dual of f. We will call the class of self-dual boolean functions S and write f ∈ S.

Take this example :

Consider the operations

f(X, Y, Z) = X’YZ + XY’ + Y’Z’ and g(X′, Y, Z) = X′YZ + X′YZ′ + XY

Which one of the following is correct?

(A) Both {f} and {g} are functionally complete

(B) Only {f} is functionally complete

(C) Only {g} is functionally complete

(D) Neither {f} nor {g} is functionally complete

Solution : As in our case we can see on giving all i/p to 0 (g )produce 0 so it preserving 0 and can’t be functionally complete.

But f is neither preserving 0 nor 1.

F is not linear(see defn. of linear above)

F is not monotone(see defn. of monotone above)

F is not self dual as f(x,y,z) is not equal to –f(-x,-y,-z)

So f is functionally complete.

Hence ans is (B) part.

Reference :

https://cs.hse.ru/data/2015/05/28/1096847873/Lecture%2013.1.pdf

http://scholar.google.co.in/scholar_url?url=https://www.researchgate.net/profile/Francis_Pelletier2/publication/38355402_Post%2527s_functional_completeness_theorem/links/0c960524f7ef05bab1000000/Posts-functional-completeness-theorem.pdf&hl=en&sa=X&scisig=AAGBfm0I6Zlxuq_IJXiIpTnV6XvSrOUlNw&nossl=1&oi=scholarr