Foundationপ্রথম নীতি থেকে
LEVEL 2লেসন ৩/১৬মাঝারি৫০ মিনিট

NAND-এর সর্বজনীনতা — একটা মাত্র gate দিয়ে সবকিছু

Gate Universality and NAND Completeness

NAND দিয়েই NOT, AND, OR — এমনকি XOR — বানানো যায়; যেহেতু {AND, OR, NOT} ইতিমধ্যে functionally complete (Level 0), তাই NAND একাই যেকোনো Boolean function বাস্তবায়নের জন্য যথেষ্ট।

এই লেসন শেষে আপনি পারবেন

  • শুধু NAND gate ব্যবহার করে NOT, AND, OR বানাতে পারবেন
  • ৪টা NAND gate দিয়ে XOR তৈরি করে ধাপে ধাপে তার সঠিকতা যাচাই করতে পারবেন
  • NAND-এর functional completeness-এর যুক্তি (Level 0-এর {AND,OR,NOT}-সম্পূর্ণতার উপর ভিত্তি করে) পুনর্গঠন করতে পারবেন
  • একটা truth table থেকে সরাসরি NAND-only circuit ডিজাইন করতে পারবেন
  • কেন তাত্ত্বিক ন্যূনতমতা (NAND-only) সবসময় ব্যবহারিক সর্বোত্তমতা নয় তা যুক্তি দিতে পারবেন

আগে যা বোঝা থাকা দরকার

আগে এটা বুঝি

গত লেসনে দেখলাম CMOS-এ NAND আর NOR “স্বাভাবিক” — সরাসরি transistor network থেকে আসে, সবচেয়ে সস্তা। কিন্তু বাস্তব circuit-এ তো শুধু AND/OR/NOT দিয়ে না, XOR, XNOR — অনেক ধরনের function দরকার হয়।

প্রশ্ন: আমরা কি শুধু NAND (আর তার copy) দিয়ে সবকিছু বানাতে পারি? উত্তরটা “হ্যাঁ” — আর এই একটা তথ্যই ব্যাখ্যা করে কেন বাস্তব ASIC ডিজাইন এত গভীরভাবে NAND/NOR-নির্ভর।

মূল ধারণা

NAND দিয়ে NOT, AND, OR

NOT: দুইটা input-কে একই signal দিন।

NAND(A,A)=A⋅A‾=A‾=NOT(A)\text{NAND}(A, A) = \overline{A \cdot A} = \overline{A} = \text{NOT}(A)

      ┌──────┐
  A ──┤      │
      │ NAND ├──── A'
  A ──┤      │
      └──────┘
NAND-এর দুই input শর্ট করলেই NOT পাওয়া যায়।

AND: NAND-এর পর একটা NOT (যা আমরা এইমাত্র NAND দিয়েই বানালাম)।

AND(A,B)=NOT(NAND(A,B))=NAND(NAND(A,B),NAND(A,B))\text{AND}(A,B) = \text{NOT}(\text{NAND}(A,B)) = \text{NAND}(\text{NAND}(A,B), \text{NAND}(A,B))

OR: এখানে Level 0-এর [[de-morgans-law]] সরাসরি কাজে লাগে।

A+B=A‾⋅B‾‾A + B = \overline{\overline{A} \cdot \overline{B}}

De Morgan-এর সূত্র অনুযায়ী, A OR B মানে “A-ও না, B-ও না” -এর বিপরীত। তাই: প্রথমে A আর B-কে আলাদাভাবে invert করুন (NAND(A,A) আর NAND(B,B)), তারপর সেই invert করা মানদুটোকে NAND করুন:

OR(A,B)=NAND(NAND(A,A),NAND(B,B))\text{OR}(A,B) = \text{NAND}(\text{NAND}(A,A), \text{NAND}(B,B))

যাচাই — A=0, B=1:

  • NAND(A,A) = NAND(0,0) = 1
  • NAND(B,B) = NAND(1,1) = 0
  • NAND(1, 0) = 1
  • প্রত্যাশিত: OR(0,1) = 1 ✓

এই তিনটাই — {NOT, AND, OR} — Level 0-এর boolean-algebra লেসনে প্রমাণিত হয়েছিল functionally complete: যেকোনো Boolean function এদের দিয়ে (একটা DNF/[[dnf]] expression হিসেবে) লেখা যায়। যেহেতু NAND একাই এই তিনটা বানাতে পারে, NAND নিজেই functionally complete।

XOR from NAND — চারটা NAND-এর কৌশল

XOR-কে NAND দিয়ে বানানো সবচেয়ে চতুর অংশ — সরল “NAND + NOT” প্যাটার্নে হয় না, একটু ভিন্ন গঠন লাগে।

XOR(A,B)=A‾B+AB‾\text{XOR}(A,B) = \overline{A}B + A\overline{B}

চার-NAND গঠন:

n1 = NAND(A, B)
n2 = NAND(A, n1)
n3 = NAND(B, n1)
Y  = NAND(n2, n3)
A ──┬──────────┐
    │      ┌───┴───┐
    ├──────┤ NAND  ├── n1 ──┬──────┐
    │      └───────┘        │      │
    │   ┌────────────────┐  │  ┌───┴───┐
    └───┤ NAND (A, n1)   ├──┼──┤       │
        └────────────────┘  │  │ NAND  ├── Y
B ──┬───┤ NAND (B, n1)   ├──┴──┤       │
    │   └────────────────┘     └───────┘
    └──────────┘ (n1-এর ইনপুট হিসেবেও)
৪-NAND XOR — n1 একটা 'partial NAND' হিসেবে কাজ করে, n2/n3 প্রতিটা input-কে n1-এর সাথে মিশিয়ে দেয়।

সম্পূর্ণ truth table verify করে দেখি:

ABn1=NAND(A,B)n2=NAND(A,n1)n3=NAND(B,n1)Y=NAND(n2,n3)প্রত্যাশিত XOR
001NAND(0,1)=1NAND(0,1)=1NAND(1,1)=00 ✓
011NAND(0,1)=1NAND(1,1)=0NAND(1,0)=11 ✓
101NAND(1,1)=0NAND(0,1)=1NAND(0,1)=11 ✓
110NAND(1,0)=1NAND(1,0)=1NAND(1,1)=00 ✓

চারটা row-ই মিলে যায়। এই বিশ্লেষণটা নিজে হাতে verify করা মূল্যবান — এটা exactly সেই দক্ষতা যা পরের লেসনগুলোয় (adder, ALU) বারবার লাগবে।

ভেতরে কী ঘটছে

Functional Completeness-এর প্রমাণের কাঠামো

কেন “NAND দিয়ে AND, OR, NOT বানানো যায়” থেকে “NAND দিয়ে যেকোনো Boolean function বানানো যায়” পর্যন্ত লাফ দেওয়া বৈধ?

Level 0-এর boolean-algebra লেসনে দেখানো হয়েছিল যেকোনো truth table [[dnf]] (sum-of-products) আকারে লেখা যায় — প্রতিটা row যেখানে output 1, সেই row-এর একটা [[minterm]] (variable-দের AND, কিছু invert করা) তৈরি করে, আর সব minterm-কে OR করে দেওয়া হয়। এই গঠনে লাগে শুধু: AND (minterm বানাতে), NOT (variable invert করতে), আর OR (minterm-গুলো একসাথে করতে)।

যেহেতু আমরা এই তিনটাই NAND দিয়ে বানিয়েছি (উপরের সরল প্রতিস্থাপন), যেকোনো DNF expression — মানে যেকোনো Boolean function — NAND দিয়ে বানানো সম্ভব। এটাই formal proof-এর কাঠামো:

সব Boolean function = কোনো DNF expression   (truth table থেকে সবসময় সম্ভব)
DNF = শুধু AND, OR, NOT ব্যবহার করে         (definition অনুযায়ী)
AND, OR, NOT = শুধু NAND দিয়ে বানানো যায়    (এই লেসনে দেখানো হলো)
─────────────────────────────────────────
∴ সব Boolean function = শুধু NAND দিয়ে বানানো যায়

উদাহরণ

একটা truth table থেকে NAND-only circuit

ধরুন আমাদের একটা 3-variable function F(A,B,C) লাগবে যা 1 দেয় শুধু A=1,B=0,C=1 অথবা A=0,B=1,C=0-এ।

DNF: F = A·B'·C + A'·B·C'

NAND রূপান্তর (De Morgan প্রয়োগ করে):

F=A⋅B‾⋅C‾⋅A‾⋅B⋅C‾‾‾F = \overline{\overline{A \cdot \overline{B} \cdot C} \cdot \overline{\overline{A} \cdot B \cdot \overline{C}}}

এটা দেখতে জটিল লাগলেও, প্রতিটা অংশ সরাসরি একটা NAND gate:

  • ভিতরের দুইটা 3-input AND — প্রতিটা “NAND + NOT” (বা সরাসরি 3-input NAND-এর পর inverter)
  • বাইরের OR — De Morgan অনুযায়ী সরাসরি একটা NAND

এই প্যাটার্নটাই (“NAND-of-NANDs”) বাস্তবে standard: যেকোনো 2-level AND-OR (sum-of-products) circuit-কে NAND-only-তে রূপান্তর করতে, প্রতিটা AND আর প্রতিটা OR gate-কেই সরাসরি একটা NAND দিয়ে প্রতিস্থাপন করা যায় (একটা ছোট bubble-pushing কৌশল, যা De Morgan-এর সরাসরি প্রয়োগ) — কোনো বাড়তি inverter স্তর ছাড়াই।

নিজে চালিয়ে দেখুন

EXPERIMENT

Logisim-এ XOR-শুধু-NAND circuit যাচাই করুন

Logisim Evolution বা Digital· ১৫ মিনিট

১. চারটা NAND gate primitive রাখুন, উপরের diagram অনুযায়ী জুড়ুন ২. A, B input toggle, Y-তে output probe ৩. চারটা combination চালিয়ে উপরের truth table-এর সাথে মেলান ৪. এবার built-in XOR primitive দিয়ে পাশাপাশি একই input দিয়ে চালান — দুইটা output সবসময় মেলে কি না নিশ্চিত করুন

এটা কী প্রমাণ করে

৪টা NAND gate সত্যিই একটা সঠিক XOR truth table দেয় — কোনো XOR primitive না ব্যবহার করেই।

নিজে বানান

BUILD IT

একটা 3-variable Majority Function শুধু NAND দিয়ে

Logisim / Digital · ●●●○○
  1. একটা majority function সংজ্ঞায়িত করুন: F=1 যদি A,B,C-এর মধ্যে অন্তত দুইটা 1 হয়
  2. পূর্ণ truth table বানান (৮টা row)
  3. DNF expression বের করুন
  4. De Morgan প্রয়োগ করে পুরো expression-কে শুধু NAND-এর টার্মে লিখুন
  5. Logisim-এ শুধু NAND primitive ব্যবহার করে circuit বানান, সব ৮টা combination-এ verify করুন

Majority function বাস্তবে গুরুত্বপূর্ণ — এটাই ভিত্তি voting circuit, error-correcting memory (triple modular redundancy — তিনটা copy চালিয়ে majority vote নেওয়া, মহাকাশযান আর নিরাপত্তা-জটিল সিস্টেমে ব্যবহৃত), আর carry-lookahead adder-এর কিছু অংশে (পরের লেসনে দেখবেন)।

বাস্তব সিস্টেমে

Universality যেখানে কাজে লাগে

  • ASIC standard-cell library — বাস্তব chip design-এ synthesis tool প্রায়ই একটা high-level বর্ণনাকে NAND/NOR-ভিত্তিক gate network-এ রূপান্তর করে, কারণ এই gate-গুলো CMOS-এ সবচেয়ে সস্তা (গত লেসন) আর তাত্ত্বিকভাবে যথেষ্ট (এই লেসন)।

  • Triple Modular Redundancy (TMR) — মহাকাশযান/বিমান নিয়ন্ত্রণ সিস্টেমে একই সার্কিট তিনবার চালিয়ে একটা majority-vote circuit (যা এইমাত্র NAND দিয়ে বানানো শিখলেন) দিয়ে ফলাফল বাছাই করা হয় — একটা কপি radiation-এ ভুল দিলেও বাকি দুইটা সঠিক থাকলে সিস্টেম সঠিক থাকে।

  • FPGA-র LUT — Field-Programmable Gate Array-তে NAND-based universality-র বদলে একটা ভিন্ন mechanism ব্যবহার হয়: Look-Up Table (LUT) — একটা ছোট memory যা যেকোনো truth table সংরক্ষণ করতে পারে। এটাও “যেকোনো function বানানো”-র একটা ভিন্ন পথ, memory-ভিত্তিক না গেট-ভিত্তিক — একটা আকর্ষণীয় বিকল্প approach যা Level 12-এর কাছাকাছি টপিক।

  • Historical relay computer-এও universality — Zuse-এর Z3-তেও একটা “সার্বজনীন” building block দিয়ে সব logic composed হতো, ধারণাটা transistor-নির্দিষ্ট না, generic switch theory-র অংশ।

যে ভুলগুলো সবাই করে

“যেহেতু NAND দিয়ে সবকিছু বানানো যায়, real chip সবসময় শুধু NAND ব্যবহার করে।”

তাত্ত্বিক ন্যূনতমতা আর ব্যবহারিক সর্বোত্তমতা এক জিনিস না। বাস্তব standard-cell library-তে AND, OR, XOR, MUX — বিভিন্ন আকারের অনেক gate সরাসরি পাওয়া যায় (transistor-দক্ষভাবে ডিজাইন করা), কারণ প্রতিটা জায়গায় সবচেয়ে ভালো fit করা gate ব্যবহার করলে সামগ্রিক circuit ছোট, দ্রুত, কম বিদ্যুৎ-ক্ষুধার্ত হয়। “NAND-only” একটা তাত্ত্বিক সম্ভাব্যতার প্রমাণ, একটা ডিজাইন নির্দেশিকা না। আধুনিক synthesis tool জটিল অপ্টিমাইজেশন (area, timing, power-এর মধ্যে trade-off) করে সিদ্ধান্ত নেয় কোন gate কোথায় ব্যবহার করবে।

“XOR NAND-এর মতোই একটা 'মৌলিক' গেট, তাই একইভাবে সস্তা।”

CMOS-এ XOR সরাসরি একটা simple series/parallel transistor network দিয়ে তৈরি হয় না (NAND/NOR-এর মতো) — সাধারণত ৮-১২টা transistor লাগে (এই লেসনের ৪-NAND গঠনে 4 × 4 = 16 transistor, যদিও optimized XOR-নির্দিষ্ট transistor layout কম, প্রায় ৮-১০টায় করা যায়)। এই কারণেই XOR-heavy circuit (যেমন পরের লেসনের adder, যেখানে প্রতিটা bit-এ একটা XOR লাগে) NAND/AND/OR-heavy circuit-এর চেয়ে তুলনামূলক বেশি এলাকা নেয় — এটা একটা বাস্তব ডিজাইন consideration, শুধু তাত্ত্বিক curiosity না।

বুঝেছেন কি না দেখুন

1

NAND(A, NAND(A,B)) কোন Boolean function গণনা করে? সরল করে দেখান।

প্রয়োগ

NAND(A,NAND(A,B))=A⋅A⋅B‾‾\text{NAND}(A, \text{NAND}(A,B)) = \overline{A \cdot \overline{A \cdot B}}

De Morgan প্রয়োগ করে:

=A‾+A⋅B‾‾=A‾+(A⋅B)= \overline{A} + \overline{\overline{A \cdot B}} = \overline{A} + (A \cdot B)

Distribution/absorption দিয়ে সরল করি (Level 0-এর boolean-algebra লেসনের identity ব্যবহার করে):

A‾+AB=A‾+B\overline{A} + AB = \overline{A} + B

(কারণ \overline{A} + AB = (\overline{A}+A)(\overline{A}+B) = 1 \cdot (\overline{A}+B) = \overline{A}+B, distribution আর complement law প্রয়োগ করে)

A‾+B=A→B(logical implication!)\overline{A} + B = A \to B \quad \text{(logical implication!)}

এটাই Level 0-এর propositional-logic লেসনের [[logical-connective]] IMPLIES (→)। চমৎকার উদাহরণ — মাত্র দুইটা NAND দিয়ে একটা সম্পূর্ণ ভিন্ন, অ-স্বজ্ঞাত connective (IMPLIES) সরাসরি বানানো যায়।

2

প্রমাণ করুন {NOR} (শুধু NOR) একাই functionally complete — সংক্ষিপ্ত যুক্তি দিন (সম্পূর্ণ derivation দরকার নেই, কাঠামোটা দেখান)।

যুক্তি

একই কাঠামো, dual ভাবে:

NOT(A)=NOR(A,A)\text{NOT}(A) = \text{NOR}(A,A) OR(A,B)=NOT(NOR(A,B))=NOR(NOR(A,B),NOR(A,B))\text{OR}(A,B) = \text{NOT}(\text{NOR}(A,B)) = \text{NOR}(\text{NOR}(A,B),\text{NOR}(A,B)) AND(A,B)=A‾+B‾‾ (De Morgan)=NOR(NOR(A,A),NOR(B,B))\text{AND}(A,B) = \overline{\overline{A}+\overline{B}} \text{ (De Morgan)} = \text{NOR}(\text{NOR}(A,A), \text{NOR}(B,B))

যেহেতু NOR দিয়ে {NOT, OR, AND} সবগুলোই বানানো যায়, আর সেই সেট functionally complete (Level 0), NOR-ও functionally complete।

গঠনগত মিল লক্ষ্য করুন: NAND-এর প্রমাণে যেখানে “দুই input শর্ট করে NOT” আর তারপর “De Morgan দিয়ে বাকিটা” ব্যবহার হয়েছিল, NOR-এর প্রমাণেও একই দুই কৌশল ব্যবহৃত হচ্ছে — শুধু De Morgan-এর কোন রূপ (AND-এর জন্য না OR-এর জন্য) প্রয়োগ হচ্ছে সেটাই পাল্টাচ্ছে।

3

{XOR, AND} কি functionally complete? যুক্তি দিন (ইঙ্গিত: NOT বানানো যায় কি না চিন্তা করুন)।

ডিজাইন

হ্যাঁ, complete — কিন্তু এটা প্রমাণ করতে একটা constant 1 বা 0 লাগবে, যা প্রায়ই বাস্তব সার্কিটে সহজলভ্য (একটা তার সরাসরি VDD বা GND-এ জোড়া)।

NOT(A)=XOR(A,1)\text{NOT}(A) = \text{XOR}(A, 1)

(A=0 হলে XOR(0,1)=1; A=1 হলে XOR(1,1)=0 — ঠিক NOT)

যেহেতু {XOR, AND} দিয়ে NOT বানানো গেছে (একটা constant ইনপুটের সাহায্যে), আর AND নিজেই আছে, বাকি লাগে শুধু OR। OR-কে De Morgan দিয়ে AND+NOT থেকে বানানো যায় — যা আমাদের কাছে ইতিমধ্যে আছে।

সতর্কতা: এই প্রমাণটা constant input-এর উপর নির্ভর করে — যদি কোনো constant input পাওয়া না যায় (শুধু বিশুদ্ধ {XOR, AND} gate, কোনো fixed wire ছাড়া), তাহলে সেটা functionally complete না, কারণ XOR আর AND দুইটাই “linear-ish” property রক্ষা করে যা একা দিয়ে সব function reach করতে দেয় না। এই সূক্ষ্মতাই দেখায় কেন functional completeness প্রমাণের সময় শর্তগুলো (constant পাওয়া যাচ্ছে কি না) সাবধানে বলা জরুরি।

4

৪-NAND XOR সার্কিটে যদি n1 = NAND(A,B) গেটটা ভেঙে সবসময় 1 আউটপুট দেয় (stuck-at-1 fault), বাকি সার্কিট কী output দেবে — এখনও XOR-এর মতো আচরণ করবে, নাকি অন্য কোনো function-এ পরিণত হবে?

প্রয়োগ

n1 সবসময় 1 ধরে সার্কিট recompute করি:

n2 = NAND(A, 1) = NOT(A) = A' n3 = NAND(B, 1) = NOT(B) = B' Y = NAND(n2, n3) = NAND(A', B') = \overline{A' \cdot B'}

De Morgan দিয়ে: \overline{A' \cdot B'} = A + B

এই ভাঙা সার্কিট আসলে OR gate-এ পরিণত হয়েছে, XOR না। এই ধরনের বিশ্লেষণ — একটা নির্দিষ্ট internal node “stuck-at” fault হলে পুরো circuit-এর আচরণ কী হয় — বাস্তব chip manufacturing testing-এর (post-fabrication test vector generation) একটা মূল কৌশল, “stuck-at fault model” নামে পরিচিত, যা উৎপাদন-পরবর্তী প্রতিটা চিপ পরীক্ষা করতে ব্যবহৃত হয় লক্ষ লক্ষ চিপের মধ্যে ত্রুটিপূর্ণটা বাদ দিতে।

এরপর কী

আমরা এখন জানি: NAND (বা NOR) দিয়ে যেকোনো Boolean function বানানো সম্ভব। কিন্তু “সম্ভব” আর “দক্ষ” এক জিনিস না — সরাসরি DNF থেকে NAND-of-NANDs বানালে প্রায়ই অপ্রয়োজনীয়ভাবে বেশি গেট লাগে।

পরের লেসনে আমরা ফিরে যাব Level 0-এর Boolean algebra-য়, কিন্তু এবার প্রশ্নটা তাত্ত্বিক না — প্রকৌশলগত: একটা নির্দিষ্ট function-কে সর্বনিম্ন সংখ্যক গেট দিয়ে কীভাবে বাস্তবায়ন করা যায়? Karnaugh map সেই minimization-এর হাতিয়ার — আর আমরা দেখব একটা real circuit-এ minimization কতটা গেট বাঁচাতে পারে, একটা concrete before/after তুলনা দিয়ে।

আরও পড়ুন

  • Introduction to Boolean Algebras, Ch. 2 — Functional Completeness — Steven Givant, Paul Halmos · Functional completeness-এর প্রামাণ্য গাণিতিক ভিত্তি
  • Digital Design and Computer Architecture, §2.6 — Sarah Harris, David Harris · NAND/NOR universality-র প্রকৌশলগত উপস্থাপনা