جبر بول و مدارهای منطقی

■ سرآغاز

جبر بول^⮫، که به افتخار ریاضیدان جرج بول نام‌گذاری شده، شاخه‌ای از ریاضیات است که با دو مقدار اصلی «درست» (1) و «نادرست» (0) کار می‌کند. جبر بول بنیاد طراحی منطقی↝ کامپیوتر‌ها و تقریباً همه‌ی سیستم‌های رایانشی مدرن است. درواقع، این جبر پلی است که منطق انتزاعی را به دنیای فیزیک می‌پیونداند.

در این بخش، مرور مختصر و ضروری از جبر بول ارائه می‌شود که نه تنها پیش‌نیاز درک مدارهای منطقی کلاسیک، بلکه پایه‌ای برای آشنایی با اصول گسترش‌یافته در حوزه کوانتوم خواهد بود. در همین راستا، به مفاهیم پایه‌ای مانند کیوبیت‌ها و ویژگی‌هایی چون برهم‌نهی و درهم‌تنیدگی نیز پرداخته خواهد شد.

■ جبر بول (Boolean algebra)

`<L^C, I>` را، که در یادداشت پیشین↝ تعریف شد، به صورت زیر بازآرایی می‌کنیم:

حاصل آ تا د را <L_B, |B| ,J> می‌نامیم. در این صورت عبارت‌های زیر نمونه‌هایی از فرمول‌های L_B هستند.

a , a+b , a+b×c , ~(a+a×c) ≡ a , (a+c)+~d

`<L_B, |B|,J>`

`<L^C, I>` و `<L_B, |B|,J>` هم ریخت هستند. یعنی، می‌توان نظیر هر عنصر یکی را در دیگری یافت (برای مثال، برای هر تعریف، قضیه یا مانند آن‌ها در یکی معادلی در دیگری وجود دارد).

بعلاوه در `<L_B, |B|,J>` به خاطر آسان نویسی قرارداد می‌کنیم:

با توجه به این قراردادها‌ به هر فرمول ‌`<L_B, |B|,J>` یک عبارت بولی و به `<L_B, |B|,J>` یک جبر بول می‌گوییم.

■ هم‌ارزی‌های بولی پرکاربرد

اثبات هم‌ارزی‌های بولی که در زیر آمده و در جبر بول مورد توجه ابتدایی هستند با جدول ارزش به راحتی میسر است:

■ ساده گردانی عبارات بولی

عبارت بولی زیر را در نظر بگیرید،

f: abc+abc+abc+abc.

ساده شده این عبارت بولی ab+bc+ac است. هزینه محاسبه این فرمول سه × و دو + است، حال آنکه هزینه محاسبه f سه متمم‌ (نقیض) گیری، هشت × و سه + است و هر دو نیز مقدار یکسان دارند. برخی روندهای الگوریتمیک برای ساده کردن عبارت‌های بولی [از جمله جدول کارنو /Karnaugh map] برای عبارت‌های شامل تا ۴ متغیر و الگوریتم کواین-مگ کلاسکی /Quine–McCluskey algorithm برای متغیرهای بیشتر] وجود دارد. اما الگوریتمی که هر عبارت بولی را به گونه بهینه ساده کند از جمله مسئله‌های موسوم به NP (Nondeterministic Polynomial) است. مسئله‌های NP را در یادداشت‌های نظریه رایانش توضیح خواهیم داد. اینجا و به عنوان پاسخ کوتاه، مسئله‌های NP مسئله‌هایی هستند که گرچه درستی پاسخ آن‌ها را می‌توان بطور کارساز سنجید، اما روند حل آن‌ها می‌تواند کارساز نباشد. بنابراین، گرچه هر مسئله کارساز یک NP است ولی ورارون آن برقرار نیست.

■ مثال ۱.

■ گذرگاه ‌منطقی  (Logic Gate)

در بند زندگی‌نامه چارلز ساندرس پیرس یادآوری شد که وی فیزیکی سازی عبارت‌های بولی را پیشنهاد کرده بود. این منجر به آنچه شد که امروزه (طراحی) مدارهای منطقی نامیده می‌شود. قصد ما در اینجا شرح کوتاه و البته بنیادین طراحی مدارهای منطقی است. برای این کار می‌باید از گذرگاه‌های منطقی و سپس مدارهای منطقی که از اتصال گذر‌گاه‌ها به دست می‌آید شروع کنیم. مبنای نظری ما صورت‌های نرمال و تمامیت کارکردی <L_B,|B|,J> هستند.

برای ما، گذرگاه‌ منطقی (یا دروازه‌ منطقی  Logic Gate) نام دیگری برای جدول ارزش (تابع ارزش) با حداکثر دو متغیر (دو ستون راهنما) است. وقتی به لایه فیزیک نزدیک می‌شویم، به این متغیر(ها) ورودی می‌گوییم.

در صورت‌های نرمال سه رابط ∨ ،• و ~ را داریم که در اینجا به ترتیب آنها را دروازه‌های AND ،OR و NOT می‌نامیم. با این رابط‌ها می‌توان همه عبارت‌های (بولی) را نوشت. نیز دو رابط ↑ و ↓ را داریم که هر یک به تنهایی تمام هستند. این دو رابط آخری را دروازه‌های NAND و NOR می‌نامیم. در شکل زیر کارکرد (تابع ارزش) و نمای شماتیک این رابط‌ها، که در اینجا گذرگاه‌های منطق نامیده شده‌اند، نشان داده شده است:

■ مدار منطقی (Logic Circuit)

به نگاره شماتیک یک عبارت بولی، مدار منطقی می‌گوییم. بنابراین هر گذرگاه منطق در شکل (۱) خود یک مدار منطقی است. مثال‌هایی که در پی خواهند آمد خود گویای چیستی مدارهای منطق هستند.

مثال: مدار عبارت بولی: f: abc.

مثال: دو مدار زیر، هم‌ارزند. همان‌طور که می‌‌توان دید، در مدار سمت راست دو گذرگاه صرفه جویی شده است.

■ مدار منطقی اکثریت

در زیر مدار مثال نمایشگر اکثریت در یک گروه سه نفری آمده است. با هر بار فشار دکمه بازنشان (ریست کردن / resetting سیستم) تمام ورودی‌ها 0 خواهند شد.

■ مدارهای منطقی ترکیبی (Combinational logic circuits)

مدارهای منطقی که تاکنون مورد بحث بود، مدارهای منطقی ترکیبی نامیده (Combinational logic circuit) می‌شوند. علت این نام‌گذاری در واقع تابع–ارزشی بودن آن‌ها است. به عبارت دیگر، خروجی هر مدار (گذرگاه) منحصراً توسط ورودی‌های آن نعیین می‌گردد و نه چیز دیگری. گونه دیگر از مدار‌های منطقی موسوم به مدارهای ترتیبی را در ادامه خواهیم دید.

■ فیزیک مدار منطقی ( دیجیتال / رقمی)

هدف این بند چگونگی پل‌زدن بین مفاهیم انتزاعی منطقی (صورت و معنی) و فیزیک است. امروزه این اتصال عمدتاً با فناوری نیمه‌هادی‌ها و ترانزیستورها صورت می‌گیرد. ترانزیستور ابزار اصلی الکترونیک و محصول فناوری نیمه رسانا‌ها است. نیمه‌هادی‌ها موادی‌اند که در شرایط خاص رسانای جریان الکتریسیته می‌شوند و در غیر آن شرایط رسانا نیستند.

• ترانزیستور (Transistors)

ترانزیستور انواع گوناگون برای مقاصد گوناگون دارد. یک ترانزیستور برای کارکرد خود باید دارای حداقل یک ورودی و یک خروجی جریان باشد. افزون بر آن باید به یک منبع ولتاژ و نیز زمین (زمین در مدارهای الکتریکی حکم سیاه‌چاله‌ای را دارد که می‌تواند همه جریان یک سیستم را در خود فرو دهد) متصل باشد. در شکل زیر (ش.۵) شمای گونه‌ای ترانزیستور موسوم به ترانزیستور دو قطبی (NPN) آمده است.

کارکرد کلی این ترانزیستور به شرح زیر است:

اگر V_in کمتر از مقدار معینی که به مقدار بحرانی موسوم است باشد (گفته می‌شود در حالت low است، که ما آنرا با 0 نشان می‌دهیم) آنگاه مقدار V_out برابر V_cc (که ما آنرا با 1 نشان می‌دهیم) خواهد بود و می‌گویی ترانزیستور بسته / خاموش است،

وگرنه (گفته می‌شود در حالت high است، که ما آنرا با 1 نشان می‌دهیم) آنگاه مقدار V_out برابر V₀ خواهد بود (که ما آنرا با 1 نشان می‌دهیم) و می‌گوییم ترانزیستور در حالت باز / روشن است.

علت این کارکرد نیز به شرح زیر است:

ماده نیمه رسانا در این ترانزیستور (در واقع، دو نوع متفاوت نیمه‌رسانا، N و P، با آرایش N-P-N) گونه‌ای است که اگر ولتاژ ورودی کمتر از مقدار بحرانی باشد آنگاه ترانزیستور (ماده نیمه رسانا) کاملاً نارسانا خواهد شد (به صورت مقاومت بی‌نهایت عمل می‌کند) و در نتیجه اتصال منبع ولتاژ با زمین قطع خواهد بود و V_cc به V_out جریان می‌یابد. در غیر این صورت ماده نیمه رسانا به صورت یک سیم (رسانا) عمل می‌کند و تمام جریان منبع، V_cc، به زمین سرریز خواهد شد که نتیجه آن ولتاژ صفر در خروجی، V_out، خواهد بود. در چنین وضعیت به این ترازیستور، معکوس کننده نیز گفته می‌شود.

• فیزیک گذرگاه‌های منطقی

همانطور که در شکل ۶ در بالا دیده می‌شود بستن سری دو ترانزیستور در (آ) مدل فیزیکی ↑ و بستن موازی دو ترانزیستور در (ب) مدل فیزیکی ↓ را به دست می‌دهند. و قضیه تمامیت گویایی نیز تمامیت کارکردی هر یک از این دو گذرگاه را به تنهایی گواهی می‌کند.

---

■ حافظه

حافظه یک مدار منطقی است به ‌گونه‌ای که بتواند یک بیت اطلاعات با قابلیت بازیابی و بازنویسی را در خود ذخیره (به شرحی که می‌آید) نماید. در شکل زیر، ش.۷، شمای یک حافظه یک بیتی آمده است. پاین‌تر به کارکرد و کارساخت آن می‌پردازیم.

---

■ کارکرد حافظه (مدار پایه‌ای ذخیره‌سازی)

مدار بالا دو ورودی با نام‌های S (نشاندن - Set) و R (بازنشاندن - Reset) و دو خروجی با نام‌های A و B دارد. رفتار مدار به شرح زیر است:

۱. حالت آ. (نشاندن مقدار 1)

اگر ورودی S مقدار 1 را بگیرد (صرف نظر از آنکه در ورودی R چه مقداری است) آنگاه:

• خروجی B برابر 1 می‌شود.

• خروجی A برابر مقدار قبلی خروجی B می‌شود. این حالت پایدار است. یعنی اگر بعداً ورودی S به 0 تغییر کند، مقادیر خروجی‌ها بدون تغییرباقی می‌مانند.

۲. حالت ب. (بازنشاندن مقدار 0)

اگر ورودی R مقدار 0 را بگیرد (صرف نظر از آنکه در ورودی S چه مقداری است) آنگاه:

• خروجی B مقدار 0 می‌شود

• خروجی A برابر مقدار قبلی خروجی B می‌شود. این حالت نیز پایدار است. یعنی حتی اگر پس از آن، ورودی R دوباره به 1 تغییر کند، مقادیر خروجی‌ها حفظ می‌شوند.

۳. شرط پایداری

مدار به جز دو حالت (آ) و (ب) در بالا حالت پایدار دیگری ندارد.

■ تعبیری کارکردی به عنوان حافظه

• در حالت آ (Set)، مقدار 1 در مدار ذخیره شده و از طریق خروجی B قابل بازیابی است. مقدار قبلی آن نیز از خروجی A قابل دسترسی است.

• در حالت ب (Reset)، مقدار 0 در مدار ذخیره شده و از طریق خروجی B قابل بازیابی است. مقدار قبلی آن نیز از خروجی A قابل دسترسی است.

• این حافظه از طریق دو ورودی S و R قابل بازنویسی است.

نکته مهم: این حافظه از نوع فرار (Volatile) است. یعنی با غیرفعال شدن منبع تغذیه مدار، اطلاعات ذخیره‌شده در آن به‌طور غیرقابل بازیابی پاک می‌شود. با این حال، تا زمانی که مدار فعال است، همواره یکی از دو حالت پایدار (0 یا 1) را نگه می‌دارد و هرگز خالی نیست.

---

■ ساخت‌کار حافظه

شکل پایین، سمت راست (۸.پ) یک مدار منطقی غیر فعال (بدون اتصال به محیط عامل) را نشان می‌دهد که دارای دو ورودی، دو خروجی و دو گذرگاه NOR (نفی الزامی / ↓) است. در این مدار شعبه‌ای از خروجی هر یک از دو گذرگاه‌ به عنوان یکی از ورودی‌های گذرگاه دیگر به کار گرفته شده است. در ضمن، جدول ارزش NOR برای آسانی رجوع در زیر آن آمده است.

پس از نصب حافظه در مدار، اگر ورودی‌ها و خروجی‌ها مطابق شکل ۸.آ باشند، مدار در حالتی است که در آن خروجی B برابر با 1 خواهد بود. با بررسی جدول ارزش، این حالت یک وضعیت ممکن و قابل دستیابی است. در چنین شرایطی گفته می‌شود مدار در حالت "یک" (ذخیره مقدار 1) قرار دارد.

نکته مهم این است که این وضعیت نسبت به تغییر ورودی S پایدار است. یعنی اگر مقدار S به 0 تغییر کند، خروجی B همچنان بدون تغییر باقی می‌ماند و مقدار ذخیره شده در حافظه حفظ می‌شود. در شکل ۸.آ.۲ این حالت پس از تغییر S به 0 نمایش داده شده است.

اکنون فرض کنید در این وضع (وضع یک) مقدار R تغییر کند (1 شود)؛ در این صورت مدار به حالت ۸.ب.۱ در خواهد آمد که نسبت به خروجی‌ها در وضعیت جدیدی است. این وضع مدار را وضع صفر می‌نامیم و می‌گوییم 0 در آن ذخیره شده است. این وضع (خروجی 0 برای B) نسبت به تغییر R پایدار است، زیرا اگر R تغییر کند (0 شود) بدون تغییر خواهد ماند (محتوی حافظه تغییر نمی‌کند). شکل ۸.ب.۲ مدار را بعد از تغییر R به 1 نشان می‌دهد.

در هر یک از این دو وضع یک بیت اطلاعات در این مدار (حافظه یک بیتی) ذخیره شده است و مقدار آن از طریق خروجی B قابل بازیابی است و نیز می‌توان توسط ورودی‌ها آن را بازنویسی کرد. یعنی، با ۱ کردن S (نشاندن - Set) فقره 1 را در آن نوشت و با 1 کردن R (بازنشاندن - ReSet) فقره 0 را در آن نوشت).

افزون بر آنچه گفته شد، در هر یک از این دو حالت قابل دستیابی مقدار یکی از دو خروجی متمم (نقیض) دیگری است. بنابراین اگر بجای B متغیر q را قراردهیم آنگاه A را می‌توان q نوشت، یعنی خروجی A مقدار حافظه را قبل از آخرین تغییر نشان می‌دهد.

---

■ کنترل حافظه یک بیتی

برای کنترل ساخت‌کار حافظه، به شرحی که می‌آید، یک الحاقیه مداری مطابق شکل ۹ به آن می‌افزایند:

در این مدار اگر تواناساز غیرفعال باشد (0 باشد) تغییر D موجب تغییر محتوی حافظه نمی‌شود، در غیر این صورت ورودی D هرچه باشد در حافظه ذخیره می‌شود. برای توضیح بیشتر به نمودار ۸.آ.۱ و ۸.ب.۱ توجه نمایید.

---

■ کیوبیت‌ها (Qubit) و گسترش بنیان‌های منطقی

در بحث کارآمدی سمانتیکی و در بند کامپیوترهای کوانتومی کوتاه درباره این ماشین‌ها از منظر پیچیدگی زمانی صحبت شد. گفته شد که آن‌ها با بهره‌گیری از اصول مکانیک کوانتوم (ر.ج ↢ - ↢) به روشی بنیادی متفاوت برای پردازش اطلاعات عمل می‌کنند و صرفاً نسخه‌ای سریع‌تر از کامپیوترهای کلاسیک نیستند. بالاتر در بحث جبر بولی و مدارهای منطقی دیدیم، محاسبات کلاسیک بر مقادیر ارزش قطعی متکی است. یعنی هر بیت یا ۰ (نادرست) یا ۱ (درست) است و عملیات منطقی مانند AND ،OR و NOT این مقادیر گسسته را به نتایج جدید و یکتای معین می‌نگارند. رایانش کوانتومی با جایگزینی بیت کلاسیک با بیت کوانتومی (کیوبیت - Qubit) این چارچوب را گسترش می‌دهد.

برخلاف بیت کلاسیک که صرفاً ۰ یا ۱ است، یک کیوبیت می‌تواند همزمان در برهم‌نهی↢ (Superposition) از هر دو حالت وجود داشته باشد. به عبارت دیگر، یک کیوبیت می‌تواند در ترکیبی از هر دو حالت، با احتمال‌های مشخص برای هر کدام، به‌صورت هم‌زمان باشد. یک کیوبیت را می‌توان با یک سکه در حال چرخش که همزمان هم رو ۰ و هم پشت ۱ دارد مقایسه کرد. این سکه فقط وقتی مشاهده یا اندازه‌گیری می‌شود، که به یکی از حالت‌ها می‌رسد. به عبارت دیگر، اندازه‌گیری آن باعث «فروپاشی» به سمت ۰ (با احتمال `|α|^۲`) یا ۱ (با احتمال `|β|^۲`)، به قسمی که `|α|^۲+|β|^۲=۱`، می‌شود، که در آن احتمال ۱ برای رخ دادن رو یا پشت وقتی سکه روی میز فرود می‌آید است (به عبارت دیگر وقتی خوانده می‌شود). باید دقت داشت که وضع سکه در حالت چرخش نامعلوم نیست، بلکه تا زمانی که مشاهده نشود در واقع هر دو حالت را دارد.

این ویژگی به رایانه‌های کوانتومی اجازه می‌دهد تا تعداد زیادی از احتمالات را به طور همزمان پردازش کنند و آنها را قادر می‌سازد تا مسائل پیچیده خاصی را بسیار کارآمدتر از رایانه‌های کلاسیک حل کنند.

کیوبیت‌ها همچنین می‌توانند درهم‌تنیده (Entanglement) شوند و حالت‌های خود را به روش‌هایی پیوند دهند که قدرت محاسباتی بیشتری را فراهم می‌کند. وضعیت یک کیوبیت، صرف نظر از فاصله، درآنی با وضعیت کیوبیت دیگر همبسته (Correlation) می‌شود. اندازه‌گیری یکی بی‌درنگ وضعیت کیوبیت دیگر را تعیین می‌کند. به عبارت دیگ، کل سیستم (چندین کیوبیت) دارای ویژگی‌هایی است که به جمع اجزای آن قابل کاهش نیست. (درهم‌تنیدگی باعث می‌شود حالت کل سیستم قابل تفکیک به حالت‌های مستقل زیرسیستم‌ها نباشد). از اینجا هست که یک سیستم از `n` کیوبیت تنها `n` بیت مستقل نیست. به خاطر برنهم‌نهی و درهم‌تنیدگی، این سیستم می‌تواند یک همپوشانی منسجم از `۲^n` وضعیت کلاسیک ممکن را همزمان بنمایاند، که این منبع موازی‌سازی کوانتومی است. این ویژگی‌های منحصر به فرد، کیوبیت‌ها را به بلوک‌های سازنده ضروری تبدیل می‌کنند که به رایانه‌های کوانتومی پتانسیل فوق‌العاده‌ای می‌دهند.

این گسترش از استدلال بولی به استدلال کوانتومی (↥ - ↥) نشان می‌دهد که چگونه مفهوم رایانش و معنای منطقی، زمانی که خود واقعیت فیزیکی به صورت احتمالی و نه مطلق توصیف می‌شود، تکامل می‌یابد. بنابراین، منطق کوانتومی، درک کلاسیک از صدق، تعبیر و استنتاج را به چالش می‌کشد، غنی‌تر می‌کند و پایه‌ای منطقی برای فیزیک اطلاعات در دوران کوانتومی ارائه می‌دهد.