با n ورودی باینری، چند تابع منطقی می‌توان ساخت؟

بعضی از دریچه‌های منطقی (logic gate) یک ورودی می‌گیرند؛ مثل NOT

ما در کل چهار دریچه/گیت داریم که تک‌ورودی باشد؛ این یک محاسبه دستی، براساس جداول درستی هست:

1. دریچه/گیت منطقیِ هیچ‌کاری نکن
2. نه/NOT
3. بدون توجه به ورودی، خروجی همیشه یک باشد
4. بدون توجه به ورودی، خروجی همیشه صفر باشد

جدول درستی این چهار تابع را مشاهده کنید:

اما از کجا بدانیم که برای یک خروجی با یک ورودی n = 1، فقط چهار تابع وجود دارد؟

ما فرض می‌کنیم که ورودی یا ۱ هست و یا ۰ (همانطور که در جدول می‌بینید). بعد می‌گوییم که خروجیِ ورودی ۰، می‌تواند ۲حالت ۱ و ۰ را داشته باشد و به همین ترتیب خروجی ورودی ۱ یعنی در مجموع چهار حالت.

همانطور که دیدید، ما به تعداد ورودی کاری نداشتیم و به‌جای آن، با تعداد حالت‌های که ورودی می‌تواند داشته باشد کار کردیم. مثلا اگر ورودی ۱۶ حالت داشته باشد، خروجی ورودی اول می‌تواند ۲ حالت ۱ و ۰ و.... را داشته باشد که یعنی در مجموع 2 به توان ۱۶ حالت.

بگذارید فرض کنیم تعداد حالات ورودی، xتا هست. پس ما می‌توانیم ۲ به توان x تابع بسازیم.

تعداد حالات ورودی برای تعداد n ورودی

اما از کجا بدانیم که تعداد ورودی، چند حالت می‌تواند بسازد؟ همانطور که تعداد حالت‌هایی که یک بایت می‌تواند داشته باشد، از رابطه ۲ به توان ۸ به دست می‌آید، این بار نیز از راه مشابهی، این کار را می‌کنیم:

تعداد حالات ورودی برای تعداد ورودی n مساوی هست با «دو به توان n »

‍‍‍جواب نهایی

دقت کنید که این مقدار با ۴ به توان n متفاوت هست. مثلا n را ۳ در نظر بگیرید.