Theory
એ lift જે ચાલવાની ના પાડે છે
એક lift ત્યારે જ ચાલે (એટલે output 1) જ્યારે આ નિયમ પળાય: door બંધ હોય (A) AND કોઈએ floor નું button દબાવ્યું હોય (B).
Door ખુલ્લું છે ને button દબાવ્યું? ઊભી રહેશે. Door બંધ છે પણ button નથી દબાવ્યું? ઊભી રહેશે. Door બંધ છે અને button પણ દબાવ્યું છે? હવે ચાલશે.
આ નિયમ, એટલે inputs અંદર જાય ને એક 0/1 નો નિર્ણય બહાર આવે, એ જ છે Boolean function, અને દરેક digital device માં આવા હજારો functions નો ઢગલો હોય છે.
Theory
એક decision box
એક એવો બંધ box કલ્પો જેમાં n input wires હોય અને બરાબર એક જ output wire, દરેક wire માં 0 કે 1 જતું હોય. કોઈ પણ input pattern આપો, box તમને 0 કે 1 જવાબ આપશે, અને એ જ pattern માટે દર વખતે એ જ જવાબ. આ box નું આખું વ્યક્તિત્વ એટલે એના જવાબોની list, અને એ list મર્યાદિત જ હોય: 2ⁿ rows.
Theory
The definition
A Boolean function of n variables maps every combination in {0,1}ⁿ to a single value in {0,1}. એટલે કે n variables વાળું Boolean function દરેક combination ને એક જ 0 કે 1 output સાથે જોડે છે.
2 inputs હોય તો 2² = 4 combinations. 3 inputs હોય તો 2³ = 8. દરેક combination ને બરાબર એક output મળે, એટલે આખું function એક table માં સમાઈ જાય જેમાં 2ⁿ rows હોય.
પેલી lift નું ઉદાહરણ: f(A, B) = A·B. 4 rows, અને એમાંથી બરાબર એક જ row માં output 1 આવે.
Theory
Expression → truth table
ધારો f(A, B) = A·B + ¬A·B. હવે step by step columns બનાવો:
A B A·B ¬A·B f
0 0 0 0 0
0 1 0 1 1
1 0 0 0 0
1 1 1 0 1
પહેલાં વચ્ચેના columns, અને છેલ્લે final OR. (ધ્યાનમાં આવ્યું? f તો ત્યારે જ 1 છે જ્યારે B એ 1 છે, એટલે આ આખું expression ખરેખર માત્ર B માં simplify થઈ જાય. Simplification એ આપણો પછીનો topic છે.)
Quiz
એક Boolean function ને 4 input variables છે. એની આખી truth table માં કેટલી rows જોઈએ?
- 4
- 8
- 16
- એ તો expression ઉપર આધાર રાખે
Show the answer
16
ચારેય variables અલગ અલગ રીતે 0 કે 1 લે છે, એટલે combinations ગુણાય: 2⁴ = 16. દરેક variable દીઠ બમણું થાય એ pattern છે (2, 4, 8, 16...). Expression ગમે એટલું અઘરું હોય એ વચ્ચેના columns બદલે, પણ rows ની સંખ્યા ક્યારેય નહીં; એ તો ફક્ત variables ની સંખ્યા બદલે.
Theory
Truth table → expression (sum of products)
ઊંધું જવાનું, એટલે table માંથી expression, એની એક recipe છે:
1. જ્યાં જ્યાં output 1 હોય એ બધી rows શોધો
2. દરેક એવી row માટે બધા variables ને AND કરો: variable જો એ row માં 1 હોય તો સીધો લખો, અને જો 0 હોય તો એનું complement લખો
3. પછી એ બધા terms ને OR કરી દો
ઉદાહરણ: output ફક્ત (A=0, B=1) અને (A=1, B=1) rows માં 1 છે → f = ¬A·B + A·B. આ sum-of-products form બરાબર એ જ table આપે છે.
Think first
A અને B નું એક function માત્ર એક જ row માં 1 output આપે છે: A = 1, B = 0.
મનમાં જ એનું sum-of-products expression બનાવો, પછી tap કરો.
Show the answer
f = A·¬B
Output 1 વાળી એક જ row એટલે એક જ term. એ row માં A એ 1 છે તો સીધો રહે; B એ 0 છે તો એનું complement આવે. Term ને પાછો વાંચીને check કરો: A·¬B ત્યારે જ 1 થાય જ્યારે A = 1 અને B = 0. Row પોતે જ term બની જાય છે, બસ આટલી જ આખી ટ્રિક છે.
Theory
જે named functions ઓળખવા જેવા છે
કેટલાક two-variable functions એટલા કામના છે કે એમના નામ પડી ગયા છે: AND, OR, NAND (AND નું NOT), NOR (OR નું NOT), XOR (inputs અલગ હોય ત્યારે 1), XNOR (inputs સરખા હોય ત્યારે 1).
3 variables સાથે, majority function ત્યારે 1 આપે જ્યારે ઓછામાં ઓછા 2 inputs 1 હોય: f = A·B + B·C + A·C. સાચા chips આનાથી voting કરે છે.
Quiz
A અને B નું XOR બરાબર ત્યારે જ 1 આપે જ્યારે inputs અલગ હોય. એનું sum-of-products expression શું છે?
- A·B + ¬A·¬B
- ¬A·B + A·¬B
- A + B
- A·B
Show the answer
¬A·B + A·¬B
"Inputs અલગ છે" એવું 2 rows માં થાય: (0,1) જેમાંથી term ¬A·B, અને (1,0) જેમાંથી A·¬B; એ બંનેને OR કરો. Option A તો XNOR છે, એટલે જ્યાં inputs સરખા હોય એ rows, એ છે classic ઊંધું. A + B ખોટું છે કારણ કે એ ત્યારે પણ 1 થાય જ્યારે બંને 1 હોય, જ્યાં XOR તો 0 હોય.
Watch out
Sum-of-products માં ક્યાં ભૂલ થાય છે
3 ભૂલો પર ધ્યાન રાખો: output-0 વાળી rows માટે term લખી નાખવો (ફક્ત 1-rows ને જ term મળે), row માં જે variables 0 હોય એમનું complement કરવાનું ભૂલી જવું, અને combinations ને વ્યવસ્થિત રીતે ન લખવાથી કોઈ row જ છૂટી જવી (દર વખતે 00, 01, 10, 11 એ order માં જ લખો).
Theory
આ ફરી ક્યાં મળશે
દરેક processor instruction એ silicon માં કોતરેલા Boolean functions જ છે, અને એકલું XOR જ parity checks, RAID storage અને simple encryption ને ચલાવે છે. હવે પછીના જ topics આજના sum-of-products output ને લઈને એને નાનું કરે છે: representation અને minimization, જ્યાં ઓછા terms એટલે સસ્તા circuits.
Summary
Key takeaways
- Boolean function એ 2ⁿ input combinations માંથી દરેકને એક 0/1 output સાથે જોડે છે.
- Expression થી table: row by row evaluate કરો, વચ્ચેના columns સાથે.
- Table થી expression: દરેક output-1 row દીઠ એક AND term (1 હોય તો સીધો, 0 હોય તો complement), પછી terms ને OR: એ જ sum of products.
- Named functions જાણી લો: AND, OR, NAND, NOR, XOR (અલગ), XNOR (સરખા), majority.
- યાદ રાખવાની ટ્રિક: Row પોતે જ term છે.