ایجاب‌کننده

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

در منطق بولی٬ ایجاب کننده (شامل یا فراگیرنده یا 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 می باشند.[۱]

ایجاب کننده اول (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