Импликант

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

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

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

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

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

се подразумева по xy, по xyz, по xyzw, по w и многим другима, то су импликанти од f.

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

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

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

  • x, y и z се могу уклонити, дајући w.
  • Алтернативно, z и w се могу уклонити, дајући xy.
  • На крају, x и w се могу уклонитити, дајући yz.

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

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

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

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

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