Импликант

Из Википедије, слободне енциклопедије

У Буловој логици, импликант је „покривач“ (облик збира или производа) једног или више минтерма у суми од производа (или мактерма у производу сума) у Буловој функцији. Минтерм се зове производ зато што представља логично И скупа променљивих, а мактерм се зове сума јер представљај логично ИЛИ скупа променљивих. Формално, облик производа P у суми производа је импликант Булове функције F ако P имплицира F. Прецизније:

P подразумева F (и на тај начин је импликант од F) ако F узима вредност 1, кад год је P једнако 1, где је:
  • F Булова функција са n променљивих.
  • P је облик производа.

То значи да је PF у односу на природни редослед Буловог простора. На пример, функција

се подразумева по , по , по , по и многим другима, то су импликанти од .

Прост импликант[уреди]

Први (прост) импликант функције је импликант који не може бити покривен општијим (више редукованим - што значи са мањим бројем литерала) импликантом. В. В. Квајн је дефинисао први (прост) импликант F као импликант који је минималан - то јест, уклањање било ког литерала из P резултује у не-импликант за F. Суштински први (прост) импликанти су главни импликанти који покривају излаз функције који ни једна комбинација других главних импликанта није је у стању да покрије.

Користећи горњи пример, лако се може видети да, док је (и други) први (прост) импликант, то и то нису. Из другог каснијег примера, више литерала се могу уклонити да би се он начинио првим:

  • , и се могу уклонити, дајући .
  • Алтернативно, и се могу уклонити, дајући .
  • На крају, и се могу уклонитити, дајући .

Процес уклањања литерала из Булових термин се зове проширени облик. Проширење једним литералом удвостручује број улазних комбинација за које је облик тачан (у бинарној Буловој алгебри). Користећи функцију у горњем примеру, може да се прошири до или до без промене покривача .[1]

Збир свих првих (простих) импликаната Булове функције се зове целокупна сума', минимална покривајућа сума или Блаке канонски облик.

Види још[уреди]

Референце[уреди]

  1. De Micheli, Giovanni. Synthesis and Optimization of Digital Circuits. McGraw-Hill, Inc., 1994