Monotonic Boolean Function | Post's Functional Completeness Theorem | Boolean Functions

Functional Completeness Complete Playlist: https://youtube.com/playlist?list=PLIPZ2_p3RNHh7tLVtGdh2mIRXJv8_Udnl&feature=shared Monotonic Function: 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. Yet the given definition looks slightly intimidating, it is actually very easy to check monotonicity by looking at the following Hasse diagrams. We have discussed Checking monotonicity with Hasse diagrams in this lecture. Emil Post's Functional Completeness Theorem: A set X of truth functions (of 2-valued logic) is functionally complete if and only if for each of the five defined classes, there is a member of X which does not belong to that class. To state the criterion of functional completeness of a system of Boolean functions. Theorem. A system of Boolean functions is functionally complete if and only if this system does not entirely belong to any of T0, T1, L, M, S. 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). Crack GATE Computer Science Exam with the Best Course. ➤ Join "GO Classes #GateCSE Complete Course": https://www.goclasses.in/s/pages/gatecompletecourse Join GO Classes #Gate2024 Complete Course here: https://www.goclasses.in/courses/GATE-2024-Complete-Course-CS---IT-62c2b94c0cf2912f669c08af ➤ Download GO Classes Android APP: https://play.google.com/store/apps/details?id=com.goclasses.courses ---------------------------------------------------- #GoClasses Website : https://www.goclasses.in/ #GOClasses ALL Links : https://linktr.ee/goclasses ➤ Join GATEOverflow + GoClasses Combined TEST SERIES for Best Quality questions for GATE CSE Preparation, Here: https://gateoverflow.in/blog/14987/gate-overflow-and-go-classes-test-series-gate-cse-2024 ---------------------------------------------------- ➤Join GATE Overflow & GO Classes #Telegram Groups for GATE CSE Doubt Discussions: 1. https://t.me/GATECSE_Goclasses 2. https://t.me/gateoverflow_cse 3. https://t.me/goclasses_cse ---------------------------------------------------- ➤ Watch Complete Discrete Mathematics and Complete Engineering Mathematics Courses on GO Classes( FREE for ALL learners) : https://www.goclasses.in/s/store/ Complete #Discrete_Mathematics Course(FREE) Link : https://www.goclasses.in/courses/Discrete-Mathematics-Course Complete #Engineering_Mathematics Course(FREE) Link : https://www.goclasses.in/courses/Engineering-Mathematics Know ALL about GO Classes GATE 2024 Course: https://www.youtube.com/live/47_lF9_NaxI?feature=share Download GATEOverflow GATE Previous Years Questions(GATE CSE PYQs) Books here: https://github.com/GATEOverflow/GO-PDFs/releases/tag/gatecse-2022-vol1%2C2 ---------------------------------------------------- Feel free to Contact Us for any query. ➤ GO Classes Contact : (+91)63025 36274 (+91)9468930964 GO Classes Mail ID : [email protected] [email protected] #gatecse #gate2024 #goclasses #computerscience #computer_science