Linear Boolean Function | Functional Completeness | Digital Logic | GO Classes
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 linear.
¬ is linear.
Neither ∧ nor ∨ is linear. ∧ is not linear because on 0 outputs, the number of 1’s in the corresponding inputs is sometimes even and sometimes odd.
The mentioned theorem is called Post’s completeness criterion and is due to Emil Post. What this criterion says is that in order for a system of boolean functions to be functionally complete, this system should have
• at least one function that does not preserve zero (i.e. it is not in T0), and
• at least one function that does not preserve one (i.e. it is not in T1), and
• at least one function that is not linear (i.e. it is not in L), and
• at least one function that is not monotone (i.e. it is not in M), and
• at least one function that is not self-dual (i.e. it is not in S).
Visit GO Classes Website :
Website Link : https://www.goclasses.in/
Join GO Classes Telegram channel for Resources :
Telegram Link : https://t.me/Goclasses_for_GATECSE
Complete Discrete Mathematics Course(FREE) Link : https://www.goclasses.in/s/store/cour...
Complete C-Programming Course(FREE) Link :
https://www.goclasses.in/s/store/cour...
Crack GATE Computer science exam with the best.
Join "GO Classes Complete GATE CSE Course"
Feel free to contact us for any query.