বুলিয়ান এক্সপ্রেশন সিমপ্লিফিকেশন ও De Morgan's Law

১ · কেন সিমপ্লিফিকেশন গুরুত্বপূর্ণ

একটি বুলিয়ান এক্সপ্রেশন যত জটিল, বাস্তবায়ন করতে তত বেশি লজিক গেট লাগে — আর প্রতিটি বাড়তি গেট মানে বাড়তি সিলিকন এরিয়া (খরচ), বাড়তি বিদ্যুৎ খরচ, এবং বাড়তি propagation delayএকটি সিগন্যাল একটি গেটের ইনপুট থেকে আউটপুটে পৌঁছাতে যে সময় লাগে — প্রতিটি অতিরিক্ত গেট এই বিলম্ব যোগ করে। (সিগন্যাল একটি গেট পার হতে যে সময় নেয়)। তাই একই সত্য-টেবিল বজায় রেখে এক্সপ্রেশনকে যতটা সম্ভব সরল রূপে আনা — এটা নিছক গাণিতিক কসরত নয়, বরং একটি সরাসরি, বাস্তব ইঞ্জিনিয়ারিং প্রয়োজন।

২ · De Morgan's Law

De Morgan's LawDe Morgan's Lawসিমপ্লিফিকেশনের সবচেয়ে গুরুত্বপূর্ণ হাতিয়ার — বলে যে NOT-কে একটি AND বা OR জাংশনের ভেতর দিয়ে "ঠেলে দিলে" জাংশনের ধরন উল্টে যায়। হলো সিমপ্লিফিকেশনের সবচেয়ে গুরুত্বপূর্ণ হাতিয়ার — দুটি নির্ভুল রূপ:

$$\overline{A \cdot B} = \bar{A} + \bar{B} \qquad \text{(AND-এর NOT = OR-এর NOT-গুলো)}$$

$$\overline{A + B} = \bar{A} \cdot \bar{B} \qquad \text{(OR-এর NOT = AND-এর NOT-গুলো)}$$

স্বজ্ঞা হিসেবে মনে রাখুন: "জাংশন পার হয়ে NOT ভাঙলে AND↔OR উল্টে যায়।" অর্থাৎ একটি বড় NOT বার যখন একটি বন্ধনী ভেদ করে ভেতরে ঢোকে, তখন ভেতরের প্রতিটি ভ্যারিয়েবল আলাদাভাবে উল্টে যায় (¬), আর মাঝের AND/OR জাংশনটাও তার বিপরীতে বদলে যায়।

৩ · বীজগাণিতিক সিমপ্লিফিকেশন টেকনিক

L04-এর সাতটি নিয়ম (Identity, Null, Idempotent, Complement, Commutative, Associative, Distributive) এবং De Morgan's Law একসাথে বার বার প্রয়োগ করে একটি জটিল এক্সপ্রেশনকে ধাপে ধাপে তার ন্যূনতম সমতুল্য রূপে আনা যায় — প্রতিটি ধাপে একটি নিয়ম প্রয়োগ করে এক্সপ্রেশনের চেহারা বদলায়, কিন্তু তার অন্তর্নিহিত সত্য (ট্রুথ টেবিল) অপরিবর্তিত থাকে।

৪ · Worked example — একটি টটোলজি যাচাই

নিচের এক্সপ্রেশনটি সরল করে দেখা যাক (হাতে-কলমে, তারপর কোড দিয়ে যাচাই): ¬(A·B) + A·B। De Morgan's প্রয়োগ করলে ¬(A·B) = ¬A + ¬B হয়ে যায়, তাই পুরো এক্সপ্রেশনটি দাঁড়ায়:

$$\overline{A \cdot B} + A \cdot B \;=\; (\bar{A} + \bar{B}) + A \cdot B$$

লক্ষ্য করুন মূল এক্সপ্রেশনটির আকার হলো X + X̄ (যেখানে X = A·B) — আর L04-এর Complement নিয়ম বলে A+A'=1। অর্থাৎ এই এক্সপ্রেশনটি A ও B যাই হোক না কেন, সবসময় 1 হবে — একে বলা হয় tautologyTautologyএমন একটি বুলিয়ান এক্সপ্রেশন যা ইনপুটের সব সম্ভাব্য কম্বিনেশনের জন্যই সবসময় 1 (True) হয়। (এমন এক্সপ্রেশন যা সবসময় সত্য)। এই দাবি স্রেফ চোখে "ঠিক মনে হওয়া" দিয়ে বিশ্বাস না করে, নিচের কোডে সম্পূর্ণ ট্রুথ টেবিল তুলনা করে যাচাই করা হলো।

# মূল ও De Morgan's দিয়ে সরলীকৃত এক্সপ্রেশনের সম্পূর্ণ ট্রুথ টেবিল তুলনা করে সমতুল্যতা যাচাই
def NOT(a): return 1 - a
def AND(a, b): return a & b
def OR(a, b): return a | b

# মূল এক্সপ্রেশন: NOT(A AND B) OR (A AND B)
def original_expr(a, b):
    return OR(NOT(AND(a, b)), AND(a, b))

# De Morgan's প্রয়োগ করে দাবিকৃত সরলীকৃত রূপ: (NOT A) OR (NOT B) OR (A AND B)
def claimed_simplified(a, b):
    return OR(OR(NOT(a), NOT(b)), AND(a, b))

def verify_equivalence(expr1, expr2):
    """দুটি ২-ভ্যারিয়েবল এক্সপ্রেশনের সম্পূর্ণ ট্রুথ টেবিল সারি-বাই-সারি তুলনা করে সমতুল্যতা যাচাই করে"""
    identical = True
    print("A B | মূল-এক্সপ্রেশন | সরলীকৃত-এক্সপ্রেশন | মিলেছে?")
    print("-" * 52)
    for a in (0, 1):
        for b in (0, 1):
            v1, v2 = expr1(a, b), expr2(a, b)
            if v1 != v2:
                identical = False
            print(f"{a} {b} |       {v1}         |         {v2}         |  {'হ্যাঁ' if v1 == v2 else 'না!'}")
    print()
    print(f"দুটি ট্রুথ টেবিল সম্পূর্ণ অভিন্ন (সমতুল্যতা প্রমাণিত)? {'হ্যাঁ' if identical else 'না'}")
    print(f"এক্সপ্রেশনটি কি টটোলজি (সবসময় 1)? {'হ্যাঁ' if all(expr1(a, b) == 1 for a in (0,1) for b in (0,1)) else 'না'}")
    return identical

verify_equivalence(original_expr, claimed_simplified)