ایجاب‌کننده

در منطق بولی٬ ایجاب‌کننده (شامل یا فراگیرنده یا Implicant)، پوششِ (جمله جمعی یا جمله ضربی) یک یا چند مینترم در مجموع حاصلضربها (یا ماکسترم در حاصلضرب مجموع ها)ی یک تابع بولی می‌باشد. به‌طور کلی٬ دریک جمله ضربی مانند P، در مجموع حاصلضربها فراگیرنده (شامل یا Implicant) تابع بولی F است اگر F ،P را نتیجه دهد.

  • F یک تابع بولی از n متغیر می‌باشد(Boolean function).
  • P یک عبارت حاصل ضرب می‌باشد(Product term).
P=>F اگر هر بار P برابر یک باشد، F نیز مقدار یک را بگیرد(P یک ایجاب‌کننده F می‌باشد).

به عنوان مثال تابع زیر را در نظر بگیرید:

f(x,y,z,w) = xy + yz + w

این تابع توسط جمله‌های w، xy، xyz ،xyz و بسیاری جملات دیگر توصیف می‌شود. این جملات، فراگیرنده (Implicant)های تابع f می‌باشند.[1]

ایجاب‌کننده اول (Prime Implicant)

ایجاب‌کننده اول یک تابع، فراگیرنده‌ای است که نمی‌تواند با فراگیرنده عمومی تری (کوتاه تر- با متغیرهای بولی کمتر) پوشش داده شود. ویلارد کواین، فراگیرنده اول تابع F را فراگیرنده حداقل تعریف می‌کند از آنجا که حذف هر متغیر بولی از P، برای تابع F یک غیر ایجاب‌کننده یا نافراگیرنده ('non-implicant ) را نتیجه خواهد داد.

ایجاب‌کننده‌های اول اصلی (فراگیرنده‌های نخست بنیادی یا Essential prime implicants):

<فراگیرنده‌هایی اول> هستند که خروجی ای از تابع را پوشش می‌دهند و ترکیب‌های دیگریی از ایجاب‌کننده‌های اول را پوشش نمی‌دهند.

در مثال بالا، xy و سایر جملات، به غیر از xyz و xyzw ، ایجاب‌کننده‌های اول می‌باشند. با حذف متغیرهای بولی از این دو جمله می‌توان آن‌ها را ایجاب‌کننده اول ساخت :

  • x،y،z را می‌توان حذف کرد تا w را نتیجه دهد.
  • مشابهاً z و w می توانند حذف شوند تا xy را به دست آورد.
  • نهایتاً، x و w را می‌توان حذف کرد تا yz را نتیجه دهد.

پروسه حذف متغیرهای بولی از یک جمله بولی را بسط آن جمله می‌گویند. بسط دادن با یک متغیر بولی،تعداد ترکیبات ورودی ای را که جمله برای آن‌ها ارزش بولی صحیح دارد، دو برابر می‌کند. در مثال بالا، جمله xyz را می‌توان به xy و یا yz بسط داد بدون آنکه نیاز به تغییر دادن پوشش f باشد.

مجموع تمام فراگیرنده‌های اول یک تابع بولی را مجموع کل آن تابع یا مجموع پوشش حداقلی آن تابع می نامند.

مطالعه بیشتر

منابع
  1. De Micheli, Giovanni. Synthesis and Optimization of Digital Circuits. McGraw-Hill, Inc., 1994
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.