Teoria Abstracta a Automatelor

TEORIA ABSTRACTA A AUTOMATELOR

AUTOMATE

Despre o mașină sau instalație care realizează o serie de sarcini fără intervenție umană se spune ca este automatizată .

Automatizarea unei mașini , instalații sau proces presupune realizarea unui bloc de comandă numit automat , care , în urma prelucrării unor semnale ce i se aplică pe intrări , emite la ieșirile sale semnale de comandă prin care determină realizarea unor sarcini . Semnalele de la intrările si ieșirile unui automat reprezintă informații , dar care sunt prezentate într-o formă accesibilă automatului , ca de exemplu reprezentarea prin numere binare .

Orice mărime de intrare poate fi codificată în binar și de aceea , în ceea ce urmează , ne vom referi doar la prezentarea binară a informației .

Din cele prezentate rezultă următoarea :

Definiție

Un dispozitiv de prelucrare a informației se numește automat .

Fiecare semnal binar de informație poate avea doar două valori logice notate si .

Controlul unei activități automatizate , impune ca automatul , în funcție de valorile logice a semnalelor aplicate pe intrări la un moment , să emită la momentul , anumite valori logice pe ieșirile sale .

Funcționarea unui automat este deci descrisă în timp printr-o succesiune de etape distincte numite secvențe , in care se efectueaza anumite sarcini , spunându-se că automatul are o funcționare secvențială .

Fiecare sarcină dintr-o secvență va fi comandata de automat printr-o anumită combinație a semnalelor logice de la ieșiri , sub acțiunea unei anumite combinații a semnalelor logice de la intrări.

Definiții

a) Mulțimea combinațiilor între semnalele de intrare admise de automat se numește alfabet de intrare .

b) Mulțimea a combinațiilor între semnalele de ieșire pe care le poate asigura automatul se numește alfabet de ieșire .

Ca dispozitiv de prelucrare a informației , automatul este o grupare de circuite logice interconectate , care la un moment dat se afla in stări logice precise determinând o stare internă a automatului . Un automat se caracterizează prin mulțimea a stărilor sale interne , în care se poate afla .

Definiție

Mulțimea a stărilor interne ale unui automat se numește mulțime de stare .

Rezultă că o combinație logică a semnalelor de ieșire la un moment este determinată atât de combinația logică a semnalelor de intrare , cât si de starea internă a automatului de la momentul t. De asemenea , sub acțiunea combinației logice de intrare de la momentul t , circuitele automatului își vor modifica nivelele logice , determinând la momentul altă stare internă pentru automat .

Circuitele automatului realizând prelucrări logice , rezultă că ieșirea este rezultatul unei funcții logice g , iar starea interna este rezultatul unei funcții logice f .

Pe baza considerațiilor de mai sus se poate scrie :

Cunoscând funcțiilesi se poate prevedea funcționarea automatului .

Un automat realizează deci funcția de memorare a stării interne in care a ajuns (capacitatea sa de memorare fiind limitata datorita numărului finit de circuite componente) .

Rezultă că pentru un automat , din punct de vedere matematic , se poate da următoarea :

Definiție

Se numește automat în sens Mealy , gruparea ordonată , în care este mulțimea combinațiilor semnalelor de intrare , numită alfabet de intrare , este mulțimea combinațiilor semnalelor de ieșire , numită alfabet de ieșire , este mulțimea stărilor interne , este funcția de tranziție prin care se determină starea interna în care va trece automatul după aplicarea unei intrări , iar este funcția de ieșire ce indică ieșirea pe care o generează automatul sub acțiunea unei intrări .

Un automat Mealy se reprezintă ca în fig.1 unde prin s-au notat circuitele logice combinaționale ce materializează funcțiile de tranziție f și de ieșire g .

Fig. 1 Automat Mealy

Fig. 2 Automat Moore

Un caz particular de automat Mealy este automatul Moore , care diferă de un automat Mealy prin funcția de ieșire Reprezentarea unui automat Moore este dată în fig.2 .

Definiții

a) Numărul de elemente al mulțimii se numește cardinal și se notează Card , iar pentru , Card .

b) Automatul se numește automat inițial dacă există o singură stare de la care se pune in funcțiune automatul , adică dacă Card , unde este mulțimea stărilor din care poate porni automatul .

c) Un automat se numește automat slab inițial dacă există cel puțin două stări din care poate porni , adică Card .

d) Un automat se numește automat neinițial , dacă poate porni din orice stare a sa , adică Card = Card .

e) Un automat se numește automat autonom sau orologiu daca evoluția lui este independentă de intrare , adică Card .

Observație

Denumirea de orologiu dată unui automat autonom se datorește faptului că , indiferent din care stare pornește , secvența de ieșire este periodică .

f) Un automat se numește -determinist dacă prin tranziție trece într-o singură stare , adică :

, : Card

g) Un automat se numește-determinist dacă , în urma unei tranziții , trece într-o singură ieșire , adică :

, : Card

h) Un automat care este -determinist si -determinist se numește automat determinist .

i) Se numește evoluție a unui automat un șir de stări în care este starea de început a evoluției .

j) Se numește semiautomat atașat automatului gruparea , semiautomatele servind la analiza separată a tranziției stărilor .

Observație

Fiecărui automat i se atașează un semiautomat unic notat , în timp ce un semiautomat poate fi atașat mai multor automate ce diferă prin ele prin si .

k) Un automat se numește subautomat al automatului dacă :

si si .

l) Se numește macroautomat atașat automatului , automatul notat

, în care :

și = ,

Pe durata funcționării sale , unui automat i se aplică un șir de simboluri ale alfabetului de intrare , fiecare găsind automatul în starea lăsată de simbolul precedent , iar sub acțiunea șirului de simboluri de intrare, automatul generează la ieșirea sa un șir de simboluri din alfabetul său de ieșire.

Apare astfel util ca , știind șirul simbolurilor ce se vor aplica la intrarea unui automat , precum și starea în care se află automatul , să se determine șirul stărilor și al simbolurilor de ieșire prin care va trece automatul .

Dacă automatul e în starea , cu ieșirea in , și la intrarea sa se aplică șirul de simboluri :

atunci automatul va trece prin stările :

iar la ieșirea sa se vor genera simbolurile :

.

Funcțiile f și g pot fi deci extinse pe șiruri de intrări astfel :

,

relatii in care :

,

unde = elementul vid , iar = .

Această definire reprezintă o extensie a funcțiilor f și g deoarece , avand in vedere că :

,

există egalitatile :

.

Teoremă

Pentru un automat , și :

Demonstrație

Demonstrațiile se fac prin inducție matematică după lungimea șirurilor (x), notată lg(x) .

(a) Fie , unde , adică () = .

Deoarece = () , rezultă :

,

adică = adevărată .

Să arătăm că daca = adevărată , rezultă = adevărată , unde :

, cu () =

= adevărată .

Deci :

este adevărată n 1 .

(b) Fie , cu lg() = 1 , adică () = .

Deoarece :

,

rezultă că :

adică P(1) = adevărată .

Să arătăm că P(i) = adevărată P(i+1) = adevărată .

, unde :

.

Deci :

este adevărată i 1 .

(c) Fie = adevărată prin definire extindere f .

Să arătăm că :

.

Avand in vedere ca :

,

se poate scrie :

adevărată.

Deci :

este adevărată .

(d) Fie = adevărată prin extindere a functiei g.

Să arătăm că = adevărată P(j+1) = adevărată .

.

Avand in vedere ca :

,

se poate scrie :

adevărată .

Deci :

este adevărată .

AUTOMATE CONEXE

Funcționarea unui automat este o secvență de stări parcursă prin tranziție de la o stare de început către starea finală . În stabilirea funcționării unui automat apare necesitatea cunoașterii posibilității de a ajunge într-o stare pornind dintr-o stare , cu alte cuvinte dacă starea este accesibilă din starea prin parcurgerea unor stări intermediare .

Definitii

a) Se spune că o stare este accesibilă dintr-o stare dacă există o secvență de intrare () ce descrie o funcționare posibilă a automatului A = (X,Z,Y,f,g), încât = .

b) Se spune că o stare este k-accesibilă dintr-o stare , dacă , unde notatia lg() reprezintă lungimea secvenței de intrare .

c) Se numește subautomat conex de stare al automatului , automatul A()= (X,Z(),Y,f,g) în care Z() = { , , Z și accesibilă din }

d) Se spune că un automat este conex de stare dacă

e) Se spune că un automat este tare conex dacă orice stare a sa este accesibilă din oricare altă stare .

Teoremă

Într-un automat cu Card , o stare accesibilă dintr-una , este cel mult accesibilă , adică :

Demonstrație

Fie și .

Presupunem că pentru orice secvență de intrare , prin care se accede din în , . Deoarece , rezultă ca în secvența de stări , un număr de stări se vor repeta. Secvența de stări obținută va fi :

, cu ,

iar cea de intrare este :

.

Rezultă că există și secvența de stări :

obținută din secvența de intrare :

, cu ,

adică o secvență mai scurtă cu pași . Cel mai defavorabil caz este când .

Secvența de intrare () poate fi scurtată , în acest mod , până la eliminarea tuturor stărilor ce se repetă , adică până când în secvența de stări rămân doar stări distincte .

În cel mai defavorabil caz secvența de stări () include toate stările automatului în număr de , prima stare fiind starea de plecare . Deci lungimea secvenței de intrare este mai scurtă cu un pas decât cea a stărilor .

Deoarece :

,

rezultă că :

,

si deci :

.

Consecință

Dacă un automat este tare conex , atunci :

.

Demonstrație

Într-un automat tare conex orice stare Z este accesibilă din orice altă stare Z . Conform teoremei anterioare rezultă că :

ECHIVALENTA DE STARI

Din punctul de vedere al funcționării automatului intereseză doar acele stări interne care asigură automatului funcții diferite de ieșire . Între stările interne ale unui automat există și stări din care pornind automatul genereză funcții identice pe ieșire , adică există stări ce determină o aceiași funcționare a automatului .

O mulțime de astfel de stări , asigurând aceiași comportare pe ieșire a automatului , va fi inlocuită printr-o singură stare . Astfel , mulțimea stărilor interne pa care trebuie să le asigure un automat fiind mai mică și stuctura automatului va rezulta mai simplă .

Din această cauză , în faza de proiectare , se impune eliminarea stărilor ce determină aceeași funcționare pe ieșirea automatului de realizat. Aceste stări redundante se numesc stări echivalente deoarece se află într-o relație de echivalență .

Noțiunea de relație de echivalență se introduce în teoria mulțimilor prin următoarele :

Definiții

a) Se numește relație binară pe mulțimile de elemente și , o submulțime a produsului cartezian x astfel că dacă atunci si se notează .

b) Se numește relație binară pe mulțimea de elemente o submulțimea produsului cartezian .

c) O relație binară definită pe mulțimea se numește relație de echivalență dacă are următoarele proprietăți :

– este reflexivă :

– este simetrică :

– este tranzitivă :

O relație de echivalență pe o mulțime determină împărțirea mulțimii în submulțimi nevide disjuncte ce epuizează mulțimea , toate elementele unei submulțimi fiind in relație de echivalență . Aceste submulțimi , induse de o relație de echivalență , se numesc clase de echivalență și constituie o partiție a mulțimii . Partiția unei mulțimi în clase de echivalență are la bază următoarea :

Teoremă

Două clase de echivalență dintr-o partiție indusă de o relație de echivalență pe o mulțime sunt , sau disjuncte , sau identice .

Demonstrație

Fie două clase de echivalență din partiția indusă pe mulțimea M de relația de echivalență R .

(a) Fie x R yase de echivalență are la bază următoarea :

Teoremă

Două clase de echivalență dintr-o partiție indusă de o relație de echivalență pe o mulțime sunt , sau disjuncte , sau identice .

Demonstrație

Fie două clase de echivalență din partiția indusă pe mulțimea M de relația de echivalență R .

(a) Fie x R y .

(b) Fie .

Pentru demonstratie se foloseste metoda reducerii la absurd .

se contrazice ipoteza

Deci : .

Din cele prezentate mai sus rezultă că două stări ale unui automat sunt redundante , dacă se află în relația R definită astfel :

R 

Această relație R este de echivalență deoarece are următoarele proprietăți :

– este reflexivă :

– este simetrică :

– este tranzitivă :

.

Echivalența a două stări ale unui automat se poate defini astfel :

Definitii

a) Două stări interne , Z ale unui automat se numesc stări echivalente dacă :

b) Două stări interne din care pornind un automat generează secvențe identice pe ieșire , se numesc stări echivalente .

Se pot introduce relații de echivalență pentru secvențe de intrare de diferite lungimi astfel :

Definiție

Două stări z1 , z2 ale unui automat se numesc k-echivalente dacă

,

altfel , fiind numite k-separabile .

Pe baza k-echivalenței , echivalența a două stări interne ale unui automat se defineste astfel :

Definiție

Două stări interne ale unui automat sunt echivalente dacă sunt k-echivalente pentru orice valoare a lui k .

Definiție

Se numește automat redus , un automat care nu are stări interne echivalente , adică :

Pentru un automat finit determinist , stările echivalente pot fi identificate prin determinarea unor partiții pe mulțimea Z a stărilor interne :

,

fiecare submulțime din partiția fiind formată din stări k-echivalente .

Teoremă

Într-un automat două stări k-echivalente sunt și m-echivalente , unde 1 mk.

Demonstrație

Fie .

Dar : .

Consecință

Orice submulțime este conținută într-o submulțime și :

Card Card .

Demonstrație

Toate elementele unei submulțimi sunt k+1-echivalente . Fiind și k-echivalente vor fi situate într-o aceeași submulțime . Submulțimile oricărei partiții fiind disjuncte rezultă că elementele unei partiții se obțin prin divizarea elementelor partiției precedente și deci :

Card Card .

Teoremă

Dacă pe mulțimea Z de stări interne din automatul există două partiții succesive și încât Card = Card , atunci fiecare submulțime este formată din elemente echivalente .

Demonstrație

si:

și .

Din aproape în aproape rezultă că :

.

Deci fiecare submulțime e formată din elemente echivalente .

Observații

a) Rezultă că dacă o submulțimenu se divide la trecerea la , atunci ea conține elemente echivalente .

b) La trecerea de la la rămân în analiză doar submulțimile ce s-au divizat .

Teoremă

Într-un automat stări echivalente trec în stări echivalente .

Demonstrație

Fie , cu

Avand in vedere ca : cu

deoarece

este un șir oarecare

Teoremă

Pentru un automat cu , determinarea stărilor echivalente prin partiții are loc în cel mult pași .

Demonstrație

Cel mai mare șir de partiții este când mulțimea Z nu are elemente echivalente , procedeul încheindu-se cu partiția P pentru care, partiție formată din submulțimi cu un singur element (i = 1 , 2 , … , n) .

Dacă partiția are j elemente , , … , unde, , … , , iar Z nu are elemente echivalente , atunci numărul maxim de etape va fi :

,

numai dacă într-o etapă fiecare submulțime se divide în două submulțimi dintre care una are doar un element .

În aceste condiții pentru N se obține valoarea maximă dacă are doar două submulțimi și , încât :

si ,

rezultând :

.

AUTOMATE ECHIVALENTE

Definiții

a) Gruparea , unde M este o mulțime , iar „ ” este o operație binară definită pe M, numită și lege de compoziție , ce are proprietățile :

– M este închisă față de legea de compoziție (sau că legea de compoziție este internă) :

– asociativitate :

,

se numește semigrup .

b) Un semigrup se numește grup dacă legea de compoziție „” mai satisface și proprietățile :

– există element neutru față de legea de compoziție , notat „1” :

– fiecare element din M are un invers :

c) Un grup în care legea de compoziție „” are și proprietatea de comutativitate :

–

se numește grup comutativ (sau grup abelian).

d) Se numește subgrup al unui grup o grupare , unde , care are structură de grup .

e) Fiind date două grupuri și , o aplicație cu proprietatea :

se numește homomorfism al lui în .

f) Un homomorfism bijectiv între două grupuri și se numește izomorfism .

Corespondența între elementele a două mulțimi A și B are la bază următoarele :

Definiții

a) Fiind date două mulțimi A și B , o corespondență prin care unui element i se atribuie un element se numește funcție de la A la B și se notează :

.

b) O funcție se numește funcție surjectivă , dacă :

c) O funcție se numește funcție injectivă , dacă :

și

d) O funcție ce este atât injectivă , cât și surjectivă se numește funcție bijectivă .

e) Fie două funcții și , unde . Dacă , atunci funcția g se numește restricția lui f pe .

f) Fie două funcții și cu și .Dacă , atunci funcția g se numește extensia funcției f .

Observație

O funcție realizează o indexare a mulțimii A cu mulțimea de indici M , elementul notându-se .

Din cele prezentate mai sus rezultă următoarea :

Definiție

O funcție binară f peste o mulțime M realizeză o corespondență între o parte a mulțimii și mulțimea M :

,

adică f , ce reprezintă o relație binară „” pe mulțimea M , are proprietatea ca dacă este punct de definiție , atunci .

Pe baza ultimei definiții se pot reformula definițiile anterioare , astfel :

b) Un semigrup se numește grup dacă are proprietățile :

– sau , adică există element neutru ;

– , adică , adică fiecare element din mulțimea M are un invers .

c) Un grup se numește grup comutativ dacă are și proprietatea de comutativitate :

– sau

d) O grupare se numește subgrup al unui grup dacă este grup și dacă .

e) Fiind date două grupuri :

cu , și

cu , , o aplicație h : cu proprietatea :

,

proprietate ce poate fi pusa sub forma :

se numește homomorfism al lui în .

f) Un homomorfism bijectiv între două grupuri și se numește izomorfism .

Observație

Din cele de mai sus rezultă că un homomorfism al unui grup într-un grup , realizează o corespondență de la la cu păstrarea relațiilor binare , adică trecerea de la funcționarea grupului , la funcționarea grupului .

În studiul automatelor apare necesitatea reproducerii pe un automat

a funcționării altui automat , fapt ce implică existența a trei funcții :

, , ,

cu păstrarea relațiilor binare , , , , adică existența unui homomorfism al automatului în automatul .

Definiție

Dacă între două automate și există un homomorfism bijectiv se spune că automatele sunt automate izomorfe .

Rezultă că pentru două automate izomorfe și există egalitățile :

, și ,

adică cele două automate diferă doar prin notația intrărilor , stărilor și ieșirilor , și că există un homomorfism bijectiv :

de la automatul la automatul .

Deci , dacă între două automate și există un izomorfism :

,

atunci sunt valabile următoarele reprezentări ale automatelor date în fig.3 .

Observație

Homomorfismul , dintre automatele și , poate fi extins pe șiruri de simboluri :

, , .

În majoritatea cazurilor și , adică un homomorfism h se reduce la un homomorfism de stări :

.

Definiții

a) Fiind date două automate și , două stări și sunt echivalente și se notează R dacă : .

b) Două automate și sunt echivalente dacă orice stare a unui automat are o stare echivalentă în celălalt automat .

Stările echivalente ale unui automat fiind redundante , vom considera , în cele ce urmează , doar automatul redus care păstrează aceeași funcționare și nu prezintă stări interne echivalente .

Fig.3 Reprezentarea a două automate izomorfe și

Teoremă

Dacă în automatele și stările și sunt echivalente , R , atunci :

(x) : R ,

adică în două automate stări echivalente trec tot în stări echivalente .

Demonstrație

R .

Teoremă

Dacă există un homomorfism de stare al automatului pe automatul cele două automate sunt echivalente .

Demonstrație

Fie homomorfismul : ,

si fiind funcții identice .

Fie , () și = .

Sub acțiunea lui , va trece prin stările interne :

, = , … , = ,

si prin ieșirile :

, = , … , = ,

iar automatul va trece prin stările interne :

() , = = = () , … , = ()

si prin ieșirile :

==, = = , … , = .

Deoarece k este oarecare , rezultă că și () sunt echivalente :

R () ,

iar fiind arbitrar ales , rezultă că fiecare stare din are o stare echivalentă în .

Homomorfismul fiind surjectiv , iar și fiind automate reduse , rezultă că homomorfismul este bijectiv , adică este un izomorfism si ca urmare :

Card = Card .

Conform definiției rezultă că și sunt echivalente .

Teorema precedentă se poate enunța și astfel :

Teoremă

Dacă între automatele și există un izomorfism de stare , atunci cele două automate sunt echivalente .

Echivalența a două automate poate fi determinată și folosind noțiunea de acoperire .

Definiție

Se spune că automatul acoperă automatul , dacă fiecare stare din automatul are o stare echivalentă în automatul adică :

: : (): R () .

Teoremă

Două automate și ce se acoperă reciproc sunt echivalente .

Demonstrație

Fie și două automate reduse .

Dacă acoperă , atunci fiecare stare din are o stare echivalentă în și deci :

.

Când acoperă , fiecare stare din are o stare echivalentă în și deci :

.

Rezultă astfel :

Card = Card ,

fiecare stare dintr-un automat având una echivalentă în celălalt automat .

Conform definiției echivalenței automatelor , rezultă că automatele sunt echivalente .

Teorema

Orice automat Moore are un echivalent Mealy .

Demonstrație

Fie un automat Moore . Pentru orice stare internă a automatului există relația :

z Z : ( )

Rezultă că există un automat Mealy , din care , intarziind ieșirea cu o tranziție se obține automatul Moore .

Trecerea de la automatul Moore la automatul Mealy se face cu o aplicație :

,

în care :

() = ;

() = ;

( ()) = .

Deoarece :

( ()) = = ,

rezultă că este un homomorfism de ieșire , care , din modul de constructie al automatului Mealy , este și surjectiv .

Deci , cele două automate sunt izomorfe si implicit echivalente .

Observație

Automatul Mealy are proprietatea că tranzițiile de intrare într-o stare internă , determină aceeași ieșire pentru automat . Orice automat Mealy poate avea această proprietate dacă fiecare stare internă z , în care se intră prin tranziții ce determină ieșiri diferite pentru automat , este divizată în atâtea stări interne câte ieșiri diferite apar în tranzițiile sale de intrare , fiecare dintre noile stări interne păstrând din starea internă din care provine aceleași tranziții de ieșire și doar tranzițiile de intrare ce determină o aceeași ieșire a automatului . Pentru un automat Mealy reprezentat sub formă de graf , această transformare se realizează astfel :

Teoremă

Orice automat Mealy are un automat echivalent Moore .

Demonstrație

Fie un automat Mealy , pentru care se poate scrie relația:

, : = .

Rezultă că există un automat Moore la care se ajunge prin întârzierea cu o tranziție pe ieșirea automatului Mealy , fiind necesar ca automatul Mealy să aibă proprietatea că în fiecare stare internă a sa se intră prin tranziții ce determină aceeași ieșire pentru automat , deoarece în caz contrar funcția f(z) ar introduce nedeterminare pe ieșirea automatului .

Trecerea de la automatul Mealy la automatul Moore se face cu aplicația :

,

în care :

() = ;

() = ;

Deoarece :

() = = ,

rezultă că este un homomorfism de ieșire care , din modul de construcție al automatului Moore , este și surjectiv .

Deci , cele două automate sunt izomorfe și implicit echivalente .

AUTOMATE INCOMPLET DEFINITE

În practica automatizărilor industriale , există multe cazuri în care anumite combinații ale semnalelor de intrare nu interesează în procesul comandat . În aceste condiții o serie de tranziții nu vor fi utilizate , neinteresând ce va genera automatul pe ieșirile sale în aceste cazuri .

Definiții

a) Se numește automat incomplet definit , automatul în care unele tranziții nu-s definite , adică automatul ale cărui combinații de intrare reprezintă o submulțime a tuturor secvențelor de intrare posibile .

b) Două stări ,Z ale unui automat incomplet definit se numesc stări compatibile , și se notează dacă : = când ) și sunt specificate , adică , dacă , pornind din aceste stări , ieșirile generate sunt identice când sunt specificate .

Noțiunea de compatibilitate este o generalizare a noțiunii de echivalență , deoarece , pentru combinațiile de intrare în care nu-i definit , un automat poate fi redefinit oricum , fără a se afecta funcționarea sa .

Noțiunea de compatibilitate este însă mai slabă decât cea de echivalență , deoarece îi lipsește proprietatea de tranzitivitate .

Astfel , pentru trei stări ,, ale unui automat incomplet definit in care :

și : = = și (,) (,) , iar g(,) = nedefinit , se observă că :

, , dar

Definiții

a) Două stări , ale unui automat incomplet definit , se numesc compatibil determinate , sau direct compatibile , dacă :

: , când sunt definite , și fie / si = /, , fie ;

b) Două stări , ale unui automat se numesc compatibil nederminate, dacă :

: = cand sunt definite , dar : (,) (,)

Observație

Din cele prezentate rezultă că într-un automat complet definit relația de compatibilitate reprezintă o relație de echivalență .

REPREZENTAREA AUTOMATELOR

În reprezentarea unui automat trebuie să se evidențieze elementele mulțimilor și funcțiile de tranziție și de ieșire . Cele mai uzuale reprezentări pentru un automat sunt : graful , tabelul , matricea și organigrama funcțională .

Graful

Graful , ca reprezentare a unui automat Mealy , conține câte un nod pentru fiecare stare internă a automatului , iar o tranziție de la starea către starea se reprezintă printr-un arc orientat de la nodul spre nodul și pe care se indică intrarea care generează tranziția și ieșirea emisă de automat .

Pentru un automat Moore ieșirea fiind univoc asociată unei stări interne , va fi specificată în nod , pe arcele tranziției indicându-se doar intrarea ce determină tranziția .

a) Automat Mealy b) Automat Moore

Fig. 4 Reprezentarea prin graf a unui automat

Tabelul

Un automat Mealy va fi reprezentat prin două tabele fiecare având câte o coloană pentru fiecare combinație de intrare și câte o linie pentru fiecare stare internă . Un tabel e destinat valorilor funcției de tranziție, iar celălalt valorilor funcției de ieșire .

Un automat Moore se reprezintă cu un singur tabel , cel al funcției de tranziție,în care la coloanele combinațiilor de intrare se adaugă o coloană pentru ieșirile generate de automat în fiecare stare internă .

Cele două tabele de reprezentare a unui automat Mealy ,din fig.5 , pot fi condensate într-un singur tabel , așa cum se arată in fig.6

.

a)Automat Mealy

b)Automat Moore

Fig. 5 Reprezentarea tabelară a automatelor

Fig. 6 Reprezentare automat Mealy cu tabel condensat

Matrice de conexiuni

Un automat mai poate fi reprezentat și printr-o matrice pătrată având atâtea linii câte stări interne are automatul :

=|||| cu și = reuniunea perechilor prin care se tranzitează de la starea la starea . Matricea de conexiuni se obține din graful automatului , ca în fig.7a,b .

Fig.7a Reprezentarea unui automat Mealy prin matrice de conexiuni

≡

+

Fig. 7b Reprezentarea unui automat Moore prin matrice de conexiuni

Organigrama functională

Această metodă de reprezentare este legată de tehnica microprogramării în care un automat secvențial numit mașină algoritmică de stare și notat (Algorithmic State Machine) este reprezentat printr-o organigramă compusă din blocuri distincte numite blocuri . Un bloc ce descrie funcționarea automatului pe durata unei singure stări indică starea prezentă , comenzile date pe ieșirea automatului și starea în care se trece sub acțiunea semnalelor de intrare . Într-o organigramă funcțională , orice cale ce leagă o stare de una următoare se numește conexiune de stare .

Fiind vorba de automate deterministe , dintr-o stare curentă , un automat va tranzita către o singură stare următoare , dar care va fi determinată de combinația de intrare aplicată . Cele trei elemente ale unui bloc sunt : starea curentă (reprezentată prin cerc) , comanda dată pe ieșire (reprezentată prin dreptunghi) și combinația aplicată la intrare ca element de decizie pentru tranziție (reprezentată prin triunghi) .

Organigrama funcțională , numită și organigramă va avea atâtea blocuri distincte, câte combinații distincte există în reprezentarea tabelară a automatului .

Modul de reprezentare a unui automat (Mealy sau Moore) prin organigramă functională este ilustrat in fig.8 .

Bloc ASM

a) Automat Mealy b) Automat Moore

Fig.8 Reprezentare automate prin organigramă funcțională

COMPATIBILITATE

Compatibilitățile între stările unui automat pot fi indicate matriceal prin matricea de compatibilitate având alocată pentru fiecare stare internă câte o linie și o coloană în care compatibilitatea între stările interne și este marcată prin punerea în 1 logic a elementelor din matrice aflate la intersecția liniilor și coloanelor aferente acestor stări interne . Relația de compatibilitate fiind simetrică , determină ca matricea de compatibilitate să fie simetrică față de de diagonala principală , iar toate elementele diagonalei principale sunt în 1 logic pentru că fiecare stare internă este compatibilă cu ea însăși .

Un grup de stări fiind compatibile dacă oricare două stări ale grupului sunt compatibile între ele , rezultă că matricea de compatibilitate asociată acestui grup e o matrice unitate conținută în matricea de compatibilitate a automatului .

Incompatibilitatea a două stări interne este indicată în matricea de compatibilitate prin 0 logic .

Exemplu

Automatul având matricea de compatibilitate :

… … .. …

:

=

are stările și compatibile între ele , dar incompatibile cu starea . Matricea de compatibilitate asociată stărilor și este matricea unitate :

Pentru simplificarea determinării compatibilităților între stările unui automat se evidențiază doar compatibilitațile nedeterminate între două stări și prin analiza în tabelul de adevăr al automatului doar a tranzițiilor imediate din aceste stări , compatibilitatea nedeterminată fiind indicată prin variabila , iar incompatibilitatea prin .

Relația de comapatibilitate fiind simetrică :

,

se convine a se folosi doar variabila pentru care .

Astfel , compatibilitatea între două stări și poate fi exprimată analitic cu funcția logică :

,

care arată că stările și sunt compatibil nederminate dacă stările și în care se tranzitează pentru fiecare sunt compatibil nederminate , sau stările și sunt incompatibile dacă există cel puțin un pentru care stările și în care se tranzitează sunt incompatibile .

Rezultă că mulțimea compatibilităților peste mulțimea Z a stărilor interne ale automatului poate fi exprimată cu următoarea funcție de compatibilitate :

,

în a cărei expresie termenii conținând variabilele și sunt eliminați intrucât două stări interne și nu pot fi simultan compatibile și incompatibile .

Fiecare termen al funcției evidențiază o posibilitate de compatibilitate pe mulțimea stărilor interne . Din mulțimea compatibilităților evidențiate prin funcția se alege cea mai avantajoasă .

Observație

Analiza compatibilităților pe baza tabelei de adevăr a automatului este mult simplificată dacă automatul este de tip Moore . De aceea se recomandă transformarea Mealy – Moore urmată de identificarea compatibilităților în automatul Moore echivalent rezultat .

Exemplu

Pentru automatul , de tip Mealy , avand tabela de adevăr :

să se determine automatul echivalent Moore în formă redusă .

Rezolvare

Automatul fiind de tip Mealy , automatul echivalent de tip Moore se determină astfel :

– Automatul dat are următoarea matrice de conexiuni :

/ / /- -/-

/- / / -/- =

/ / / /

/ / / /

– Pentru a obține automatul Moore echivalent , starea se divide în stările și astfel :

/ -/- /- -/- /

/- / / -/- -/- =

/ / / / -/-

/ / / / -/-

/ / -/- -/- -/-

– Prin întârzierea ieșirilor automatului cu o tranziție , se obține automatul Moore cu următoarea matrice de conexiuni :

/ -/ / -/ x1/

/ / / -/ -/

/ / / / -/ =

/ / / / -/

/ / / -/ -/

Pentru automatul Moore echivalent se obține din matricea de conexiuni următoarea tabelă de adevăr :

– Din tabela de adevăr obținută , rezultă următoarele funcții de compatibilitate :

Functia de compatibilitate a automatului Moore este :

S-a obținut astfel că doar stările și sunt compatibile , matricea de compatibilitate a automatului Moore fiind :

1 0 0 0 1

0 1 0 0 0

0 0 1 0 0 =

0 0 0 1 0

1 0 0 0 1

Automatul Moore – redus are următoarea tabelă de adevăr :

PARTITII

Definiție

O mulțime , notată P, de submulțimi ale mulțimii Z , submulțimi care sunt nevide , disjuncte și a căror reuniune este chiar mulțimea Z , se numește partiție peste mulțimea Z :

și SjP = Z} si .

Totalitatea partițiilor peste mulțimea Z se notează .

Pe mulțimea PZ se pot defini operațiile binare de reuniune , notată „ + ” , și de intersecție , notată „ . ”

Definiții

1) Fiind dată mulțimea Z și partițiile , , , se spune că partiția este intersecția partițiilor și , dacă oricare submulțime din este inclusă atât într-o submulțime a partiție P1 , cât și într-o submulțime a partiției :

si .

2) Fiind dată mulțimea Z și spațiile , , , se spune că partiția este reuniunea partițiilor și dacă orice submulțime a partițiilor și este inclusă într-o submulțime a partiție :

=+ = si

Pentru un automat determinist , determinarea formei sale reduse , impune identificarea mulțimilor de stări interne echivalente care , fiind redundante , să fie substituite prin câte o singură stare . Acest fapt a condus la noțiunea de partiție cu proprietatea substituției peste mulțimea Z , partitie notata SP .

Definiție

Fiind dat automatul , se spune că este o partiție cu proprietatea substituției , sau că este o partiție SP , dacă funcția de tranziție f duce submulțimi din P în submulțimi din P :

= { , pentru fiecare, : } .

Mulțimea partițiilor SP peste o mulțime Z se notează , iar o partiție se notează .

Într-un automat, cu o partiție se poate construi semiautomatul : = unde (, ) = dacă , .

Semiautomatul astfel construit reproduce funcționarea automatului A numai la nivelul submulțimilor , astfel că sub acțiunea unei intrări dintr-o tranziție , subautomatul SAP indică doar submulțimea din P ce conține starea internă în care va trece automatul A .

Fiecare partiție SP este asociată unui homomorfism de stare așa cum se arată în următoarea :

Teoremă

Într-un automat , dacă și numai dacă între automatul A și semiautomatul = , cu = : , , există un homomorfism de stare cu = dacă .

Demonstrație

(a) Fie . Să arătăm că cu = P dacă reprezintă un homomorfism de stare între automatele A și .

= cu fP (x, ) = SiP dacă , f(x, z) și cu = P dacă atunci că= cu , dar =

Deci :

cu = , dacă , este un homomorfism de stare .

(b) Fie PZ și cu = dacă un homomorfism de stare între automatul și semiautomatul = cu = dacă și

Să arătăm că .

cu = dacă este homomorfism de stare între și = astfel ca :

Deci:

Determinarea de noi spații SP peste o mulțime Z se poate realiza prin operații de reuniune și intersecție între partiții SP deja cunoscute , așa cum rezultă din următoarea :

Teoremă

Fiind dat automatul , mulțimea (a partițiilor SP peste Z) este închisă față de operațiile de reuniune și intersecție .

Demonstrație

Trebuie de arătat că , ` : + , . , , existand urmatoarele doua etape :

Să arătăm că : , : .

Fie

este determinist

și fiecare e distribuită în submulțimi

Deci

(b) Să arătăm că

Fie o partiție , ale cărui submulțimi au proprietatea că pot fi exprimate atât ca reuniune a unor submulțimi , cât și ca reuniune a unor submulțimi , adică :

Cu alte cuvinte , fiecare submulțime este obținută prin înlocuirea submulțimilor de exemplu , prin submulțimile conținute .

formează o partiție pentru că , prin modul de construcție , submulțimile sale sunt disjuncte , iar reuniunea lor este chiar :

Z = SijP3

f

x

Sij = i SiP1 = j SjP2 Smn = m SmP1 = n SnP2

Pentru un, prin tranziție cu funcția , o submulțime trece într-o reuniune de submulțimi de exemplu , înlănțuite prin intersecție cu submulțimi , adică într-o submulțime

Submulțimile fiind disjuncte și puse în corespondență prin funcția , rezultă că partiția este o partiție .

Având în vedere și definiția reuniunii de partiții rezultă :.

Identificarea partițiilor

Modul de identificare a partițiilor peste mulțimea a stărilor interne dintr-un automat , se realizează pe baza următoarelor teoreme :

Teoremă

Într-un automat grupările disjuncte de elemente ale mulțimii care pentru toate valorile tranzitează în submulțimi ale lor sunt submulțimi ale unei partiții peste .

Demonstrație

Dacă grupările de elemente din acoperă mulțimea , conform definiției partiției , ele constituie chiar o partiție peste .

Teoremă

Într-un automat, o grupare din oricare două stări generează prin tranziții repetate o partiție peste .

Demonstrație

(a) Fie două stări ce constituie o grupare sursă , adică o grupare conținută într-o submulțime dintr-o partiție peste . Rezultă că din această grupare sursă pentru toate valorile se tranzitează în grupări destinație . Din ansamblul grupărilor sursă și destinație , cele ce se intersectează , fiind conținute în aceiași submulțime, se vor reuni , obținându-se noi grupări .

Noile grupări astfel rezultate , vor constitui grupări sursă în tranzițiile pentru toate valorile dintr-o nouă etapă , ș. a. m. d.

Procesul încetează în etapa în care grupările rezultate sunt incluse în cele sursă . Când , conform teoremei anterioare , ultimele grupări sursă reprezintă submulțimile unei partiții .

(b) Dacă stările nu constituie o grupare, adică nu există nici o partiție ce să conțină într-o submulțime a sa această grupare , atunci prin procesul de la punctul (a) se vor obține un șir de partiții ce nu sunt partiții peste deoarece cel puțin submulțimea conținând gruparea inițială nu este conținută în nici o submulțime a unei partiții .

În plus , în fiecare nouă etapă se generează submulțimi din ce în ce mai mari . Astfel , procesul încetează când se ajunge la partiția banală P formată din mulțimea ca unic element .

Astfel teorema este demonstrată .

Pentru un automat , din categoria partițiilor peste mulțimea , fac parte și partițiile ale căror submulțimi , ce conțin doar stări echivalente între ele , reprezintă clase de echivalență .

O cale de identificare a stărilor interne echivalente dintr-un automat, constă în determinarea tuturor partițiilor peste mulțimea și apoi identificarea între aceste partiții , pe baza funcției de ieșire , a partițiilor formate din clase de echivalență .

Dacă în automatul , Card, pornind de la cele grupări din două stări , se obțin o parte din partițiile , numite partiții primare . Prin reuniunea și intersecția partițiilor primare , se obțin noi partiții , operațiile de reuniune și intersecție continuând până la obținerea tuturor partițiilor .

Exemple

1. Să se determine stările echivalente din automatul descris de următoarea tabelă de adevăr :

Rezolvare

Fie gruparea sursă, care, pentru și , tranzitează în grupările destinație și respectiv .

Prin reuniune între aceste trei grupări se obține gruparea sursă care , pentru și , tranzitează în grupările destinație și respectiv .

Prin reuniune între aceste ultime trei grupări se obține gruparea sursă , care pentru și tranzitează în submulțimile sale și respectiv . Deci partiția generală este : , . Acest algoritm este descris sintetic astfel :

,,,,

Similar se obțin urătoarele partiții :

,,

,

,

Partițiile , , , sunt partiții primare care , prin reuniune și intersecție nu generează noi partiții .Nici una din aceste partiții nu este formată din clase de echivalență .

Deci automatul nu are stări echivalente .

2. Să se determine stările echivalente din automatul Moore descris prin tabelă de adevăr :

Rezolvare

Se obțin următoarele partiții primare :

,,,, ,,,,,,, , , , , , ,

,,,, ,,,,,, , ,

,,,,,, , , , ,

Prin reuniuni și intersecții se mai obține partiția :

Prin analiza ieșirilor se obține că doar partiția este formată din clase de echivalență . Ca urmare doar stările și sunt echivalente , automatul redus având următoarea tabelă de adevăr :

INTERCONECTAREA AUTOMATELOR

Modurile de reprezentare a unui automat , expuse anterior, sunt utile în cazul automatelor , în care mulțimile , , au un număr redus de elemente . De aceea pentru realizarea unui automat complex apare necesitatea descompunerii sale în subautomate simple , cu funcționare independentă , a căror analiză și sinteză sunt ușor de realizat .

Prin interconectarea a două automate și se obține un automat complex având , în care tranziția sub acțiunea unui simbol de intrare este determinată de tranzițiile din automatele și .

Există următoarele moduri de conectare si descompunere a automatelor :

Conectarea serie

Definiție

Se numește conexiune serie a două automate și , automatul în care :

–

– .

Conectarea serie a două automate ) și de tip Mealy se realizează astfel :

Y2

X

Y

Automatul se caracterizează prin :

Conectarea paralel

Două automate Mealy și se conectează în paralel astfel :

În automatul rezultat A , CA este un circuit de adaptare a semnalelor din automatele A1 și A2 , cum ar fi un circuit logic SAU .

Definiție

Se numește conexiune paralel a două automate și un automat în care :

–

–

Conectarea în cascadă

Definiție

Se numește cascada automatelor și automatul în care :

–

– .

Această conexiune între două automate și este o conexiune generală , din care , prin particularizări , se obțin conexiunile serie și paralel și este realizată astfel :

Observație

Prin eliminarea și cu se obține conexiunea paralel, iar prin cu , cu și cu se obține conexiunea serie.

4) Descompunerea serie

Dacă un automat A poate fi transformat într-o conexiune serie a două automate A1 și A2 , se spune ca automatul A1 A2 este descompunerea serie a automatului A .

Descompunerea serie a unui automat în automate și , A1 A2 , este nebanală dacă :

și

Teoremă

Un automat are o descompunere serie nebanală , dacă și numai dacă există o partiție SP nebanală pe mulțimea stărilor Z .

Demonstrație

(a) Fie A1 A2 cu , și . Rezultă :

.Grupând toate stările automatului A1 A2 cu A1 în aceiași stare , în submulțimile unei partiții P peste care epuizează mulțimea :

și

se observă că pentru o intrare automatul A1 A2 tranzitează din orice stare a unei submulțimi SjP într-o aceiași submulțime SjP , adică (partiția P peste este o partiție SP) .

Deoarece rezultă că există o aplicație injectivă și care induce o partiție P peste mulțimea Z de tip

– Pentru un automat :

fie și ,

să arătăm că există A1 și A2 : .

Luând câte un element din fiecare submulțime se formează submulțimile distincte ale unei noi partiții P2 peste Z :

și

cu proprietatea :

și atunci adică

Deoarece , există o corespondență biunivocă ce permite construirea automatelor :

– in care :

cu dacă când ,

cu

– in care :

cu dacă ,

cu dacă ,

care au proprietatea că : .

5) Descompunerea paralel

Dacă un automat A poate fi transformat într-o conexiune paralel a două automate A1 și A2 , se spune că automatul este descompunerea paralel a automatului A .

Descompunerea paralel a unui automat în automatele componente și , , este nebanală dacă :

și .

Teoremă

Un automat are o descompunere paralel nebanală dacă există două partiții SP nebanale astfel încât : P1 P2 = 0 .

Demonstrație

(a) Fie cu , și . Rezultă:

Grupând toate stările automatului cu A1 în aceiași stare , în submulțimi distincte se obțin submulțimile unei partiții P peste care epuizează mulțimea :

cu

Se observă că pentru o intrare automatul tranzitează din orice stare a unei submulțimi SjP1 într-o aceiași submulțime S’jP1 , adică (partiția P1 peste este o partiție SP) .

Deoarece rezultă că există o aplicație injectivă și care induce o partiție P1 peste mulțimea .

Similar , grupând toate stările automatului cu A2 în aceiași stare se ajunge la o partiție P2 peste mulțimea .

Prin modul de construcție P1 și P2 au proprietatea :

(b) Pentru un automat , fie și .

Să arătăm că există A1 și A2 : .

Pe baza partițiilor se pot construi automatele și unde e este funcția identitate .

dacă

dacă

Deoarece , rezultă :

și ca urmare există un homomorfism surjectiv

, în care :

dacă

.

Deci :

ARII LOGICE PROGRAMABILE

Orice funcție logică poate fi exprimată analitic , fie în forma canonică disjunctivă prin combinațiile de intrare în care ia valoarea logică „1” cu relația:

,

în care se numește termen produs , fie în forma canonică conjunctivă prin combinațiile de intrare în care ia valoarea logică „0” cu relația :

,

în care se numește factor sumă .

Formele canonice disjunctivă și conjuctivă de exprimarea unei funcții logice , conținând doar operațile ȘI logic și SAU logic pot fi materializate cu diode . Astfel , prin folosirea diodelor , un termen produs poate fi materializat ca in fig.1 , în timp ce materializarea formei canonice disjuctive a unei funcții logice este arătată in fig.2 .

Realizarea mai multor funcții logice in formă canonică disjunctivă a condus la o matrice cu diode , a carei structura este data in fig.3 , conținand o matrice ȘI având fiecare linie conectată la o variabilă de intrare si generând pe fiecare coloana câte un termen produs din funcțiile logice de materializat și o matrice SAU având pe fiecare coloană conectată la cate un termen produs furnizat de matricea ȘI și generând pe fiecare linie a sa cate o funcție logică ca sumă a unor termeni produs .

Fig.1 Materializare termen produs Fig.2 Materializare formă canonică disjunctivă

Intr-o materializare cu diode , rezistoarele și se dimensionează pentru a obține tensiunile aferente stărilor logice „0” și „1” pe sarcinile conectate la ieșirile matricei . Pentru ca rezistoarele de sarcina să nu afecteze tensiunile stărilor , conectarea unei matrici cu diode la fiecare sarcină se va face prin câte un etaj adaptor ca de exemplu etajul Trigger Schmidt .

O matrice cu diode conținând si etaje separatoare pe ieșiri , realizată ca circuit integrat se numește arie logică programabilă , fiind notată PLA (= Programmable Logic Array) în care fiecare variabilă de intrare determină in matricea ȘI o linie pentru starea sa normală și o altă linie pentru starea sa comportamentală , iar conexiunile in matricile ȘI și SAU fiind programate prin mască la fabricant .

O matrice cu diode , integrată si permițând programarea conexiunilor prin ardere la utilizator se notează FPLA (= Field PLA) .

Structura unui circuit FPLA programabil prin ardere de fuzibile este exemplificată in fig.4 prin circuitul SIGNETICS 82S100 caracterizat prin 16 intrări , 8 ieșiri , și 48 termeni produs , iar reprezentarea simbolică a structurii acestui circuit este data in fig.5 .

Fiecare ieșire a circuitului are câte o poartă ce prin ardere e transformată in poarta inversoare pentru generarea formei complementare a unei funcții logice . Selecția acestui circuit se realizează prin validarea tampoanelor cu trei stări de pe ieșiri cu semnalul , ieșirile fiind puse în înaltă impedanță cât timp .

Circuitele PLA au o mare flexibilitate putând fi programate să realizeze diferite funcții logice

complexe .

Fig.3 Materializare funcții logice prin matrice cu diode

Pentru generarea cu un circuit a unei funcții logice in formă canonică disjunctivă , numărul termenilor produs se reduce aducând funcția intr-o formă disjunctivă normală prin metode analitice de minimizare folosind absorbția , alipirea si reducerea . Pentru că intr-un să nu se depașeasca numărul de termeni produs admis , funcțiile logice de ieșire vor fi exprimate in forme disjunctive normale și se vor grupa pe un același circuit funcții logice având în comun mai mulți termeni produs .

Fig.4 Structura internă a circuitului

Intr-un automat programabil algoritmic cu structura de automat dată în fig.6 , circuitul materializează funcțiile logice de tranziție f și de ieșire g , registrul de stare memorează starea internă a automatului pe care o menține la intrarea , iar registrul de ieșire memorează comenzile de ieșire ce rămân astfel stabile pe durata unei stari interne a automatului . Registrul de stare îndeplinește astfel funcția de memorie de stare , iar registrul de ieșire pe cea de memorie de ieșire (numită și memorie de comandă) .

In aplicațiile complexe un circuit cu număr mare de intrări, ieșiri și/sau termeni produs necesari , este obtinută cu mai multe circuite in conexiuni de expandare adecvate , asa cum se arata in fig.6 .

Structura de automat din fig.6 s-a realizat ca circuit integrat numit secvențiator logic programabil și notat (= Programmable Logic Sequencer) . Structura interna a unui circuit poate fi exprimată sintetic cu relația :

.

Fig 5 . Simbolizarea structurii interne a circuitului

Fig. 6 Automat sincron cu

a) Expendare termeni produs b) Expandare intrari

c) Expandare intrări d) Expandare intrări

e) Expandare ieșiri f) Expandare ieșiri

Fig. 7 Conexiuni de expandare cu circuite PLA

Fig.8 Structură circuit PLS SIGNETICS 82S104

Arhitectura internă a unui PLS este exemplificată in fig.8 prin circuitul SIGNETICS 82S104. La terminalul al acestui circuit se poate realiza prin două porți logice fie comandate de presetare a registrelor RS si RE cu validarea permanentă a tampoanelor de ieșire cu trei stări , fie prin ardere, comanda de selectare a circiutului prin validarea tampoanelor de ieșire care la comanda trec în înaltă impedanța .

Circuitul este prevăzut cu o linie SAU complementată care , fiind conectată la o linie a matricei ȘI permite realizarea unei reacții asincrone de la matricea SAU la matricea ȘI , cele doua linii constituind o matrice numită complementară .

Matricea complementară permite generarea de termeni produs complecși reprezentând reuniunea mai multor termeni produs și care se regasesc în formele cononice disjunctive a unor funcții de materializat, astfel reducându-se numărul de termeni produs de programat în matricea ȘI a circuitului PLS .

Astfel, în scopul reducerii numărului de termeni produs , o funcție logică f poate fi materializată cu matrice complementară prin termenii produs ai funcției complementare , conform relației :

,

unde sunt combinații de intrare în care = mulțimea combinațiilor de intrare pe care este definită , iar :

Exemplu

Să se materializeze cu un PLS funcțiile logice și cu urmatoarele tabele de adevăr :

=

=

Rezolvare

Funcția complementară , descrisă prin tabela de adevăr :

=

și având forma canonică disjunctivă :

,

permite generarea funcților logice și cu relațiile :

,

programarea PLS realizându-se astfel ca in figura de mai jos :