Mijn geheim

De meest gebruikte bewerking bij het minimaliseren van functies is de lijmbewerking.

AB+ ВB=B (A+ В)=B.

Laten we eens kijken naar de drie meest voorkomende minimalisatiemethoden.

1. Geef de aantallen sets van vier variabelen, waarop de logische functie een eenheidswaarde aanneemt: f (2,5,6,7,10,12,13,14)=1.

Laten we deze logische functie in SDNF uitdrukken (we zullen het conjunctiesymbool niet schrijven):(0010,0101, 0110, 0111, 1010, 1100, 1101, 1110) =

F

In de eerste fase van minimalisatie kan de oorspronkelijke SDNF worden vereenvoudigd door de wet van lijmen te gebruiken, waarna we het volgende verkrijgen:

We vestigen de aandacht op het feit dat hetzelfde bestanddeel (implicant) vele malen aan elkaar kan worden gelijmd met andere bestanddelen (implicanten), aangezien in de logica van Boole de wet van idempotentie van toepassing is:

daarom kan elk bestanddeel worden vermenigvuldigd. In de tweede fase zullen we de tabel van Quine gebruiken (Tabel 8), volgens welke deze methode

minimalisatie kreeg zijn naam: de methode van Quine. De tabel vermeldt verticaal alle implicanten die in de eerste fase van de vereenvoudiging zijn verkregen, en horizontaal de initiële bestanddelen. Eenheid in tabel 8 staat waar de implicant de constituant ‘bedekt’. Feit is dat het bestanddeel altijd kan worden vervangen door een impliciete of zelfs een afzonderlijke term volgens de wet van absorptie:

Tabel 8

Na het invullen van Quine's tabel kwamen we uit op twee eenheden in bijna elke kolom; Ondertussen is het voldoende om één eenheid in de grafiek te hebben. Daarom moeten overtollige eenheden waar mogelijk worden geëlimineerd. De keuze van eenheden wordt gemaakt op basis van het minimum aantal termen (geselecteerde eenheden zijn gearceerd). Het resultaat is dat we met slechts drie implicanten kunnen rondkomen in plaats van zes: Met behulp van waarheidstabellen is het eenvoudig om te controleren of de in MNF verkregen functie alle waarden reproduceert originele functie

. Merk op dat er in het algemeen verschillende oplossingen kunnen zijn voor het criterium van minimumvoorwaarden. 2. Niet minder op een efficiënte manier minimalisering is een methode om indexen te combineren. Om het te presenteren, laten we een tafel maken. 9, in de kolommen waarvan mogelijke combinaties van indices zijn geschreven. De laatste kolom bevat de functiewaarden. De analyse van de tabel begint links langs de kolommen. Het principe van het uitsluiten van i, j_code is als volgt. Op het snijpunt van de i_kolom, bijvoorbeeld, met een combinatie van indices 23, en de j_row, bijvoorbeeld 3_th, bevindt zich code 10, die overeenkomt met de implicant. Daarom worden deze codes in deze kolom, waar code 10 voorkomt, dat wil zeggen in de regels 2, 3, 10 en 11, uitgesloten, omdat de waarde van de functie op de derde regel nul is. Laten we nu een kolom nemen met een combinatie van indexen 124. Hier blijft code 010 op de tweede en zesde regel staan, en code 011 op de tiende en veertiende regel. Dit wordt gedaan omdat deze codes alleen voorkomen op regels met een functiewaarde gelijk aan één. Integendeel, code 110 van dezelfde kolom komt zowel voor bij enkele functiewaarden als bij nulwaarden.

Tabel 9

Alle codes staan ​​dus op het einde van de regels nul waarden functies worden automatisch uitgesloten. Als deze codes op regels vallen die eindigen op een enkele functiewaarde, wordt er ook geen rekening mee gehouden. Alleen de codes die zich op lijnen met een enkele functiewaarde bevinden, blijven behouden (deze codes zijn donker gemaakt).

Volg dan de volgende regel. Om een ​​functie een waarde gelijk aan één te laten aannemen, is het voldoende dat slechts één implicant op de lijn de waarde één aanneemt. Allereerst laten we de minimale implicant achter, die de regels in de regels 2, 6, 10 en 14 overlapt. Vervolgens gaan we natuurlijk naar de 12e regel. Hier laten we de enige code op de regel staan, 011, die overeenkomt met de implicant. Dezelfde implicant is verantwoordelijk voor de 13e regel, die ook eindigt met een eenheid. Het blijft de 5e en 7e regel overwegen. Wat ze gemeen hebben is het impliciete: . Met drie implicanten hebben we dus alle afzonderlijke waarden van de functie gedekt, wat samenvalt met het resultaat dat is verkregen op basis van de tabellen van Quine.

3. Bestaat grafische methode lijmen, wat de Karnaugh-kaartmethode wordt genoemd (gepresenteerd in Tabel 10). We selecteren aangrenzende eenheden, dit zijn de voorwaarden van onze functie.

Tabel 10

We hebben twee termijnen

Hoewel tafel 9 is omslachtiger dan tabel. 8 wordt de methode voor het combineren van indexen niet als complexer beschouwd dan de methode van Quine, als we bedenken dat het vóór het samenstellen van Quine's tabellen noodzakelijk is om talloze aaneenschakelingen van bestanddelen en implicanten te maken. Het implementeren van het indexcombinatiemethode-algoritme op een computer blijkt relatief eenvoudig. En integendeel, de externe eenvoud en helderheid van de derde methode om logische functies te minimaliseren met behulp van Karnaugh-kaarten blijkt te zijn complex programma bij het implementeren van het algoritme op een computer.

Tabel 11

Tabel 12

De Karnaugh-kaart voor vier variabelen wordt gepresenteerd in de vorm van een tabel. 11. Elke cel van de kaart komt overeen met een bestanddeel. De voltooide kaart wordt weergegeven in Tabel. 12 (de functie is dezelfde als bij de eerste twee methoden). Volgens de wet van het lijmen kunnen twee aangrenzende bestanddelen met eenheidswaarden altijd worden gecombineerd om de overeenkomstige implicant te verkrijgen. Bovendien worden degenen die op de grenzen van de kaart liggen ook als aangrenzend beschouwd. Welke eenheden moeten worden gecombineerd om een ​​geschikte implicant te verkrijgen, kan eenvoudig visueel worden bepaald. Er moet ook aan worden herinnerd dat, in overeenstemming met de wet van idempotentie, dezelfde eenheid van de tafel is. 12 kan op twee of drie aangrenzende eenheden worden gelijmd.

De methode is toepasbaar voor functies van een willekeurig aantal variabelen, maar we zullen deze overwegen voor functies van drie variabelen.

Laten we het voorstellen als een DNF met onbepaalde coëfficiëntsk:

(**)

Deze DNF presenteert alle mogelijke elementaire conjuncties die in de functie kunnen worden opgenomen, en de coëfficiënten k kunnen waarden 0 of 1 aannemen. De waarden van de coëfficiënten moeten zo worden gekozen dat deze DNF minimaal is.

We zullen de functie bekijken die ons op alle sets wordt gegeven en de uitdrukking (**) op elk van de sets (zonder nulconjuncties) gelijkstellen aan de overeenkomstige waarde van de functie. We verkrijgen een stelsel vergelijkingen van de vorm:

Als in een van deze vergelijkingen de rechterkant gelijk is aan 0, dan zijn alle termen aan de linkerkant ook gelijk aan 0. Deze coëfficiënten kunnen worden geëlimineerd uit alle vergelijkingen waarvan de rechterkant gelijk is aan 1. In deze vergelijkingen moet de waarde 1 worden toegewezen aan de coëfficiënt die overeenkomt met de conjunctie van de kleinste rang. Deze coëfficiënten bepalen de MDNF.

Voorbeeld

We stellen het systeem samen met behulp van de uitdrukking (**).

Na het elimineren van de nultermen krijgen we

We nemen aan dat de overige coëfficiënten als nul worden beschouwd. We krijgen MDNF:

2.2. Quine-Mack-Clasky-methode

De beschouwde methode van onbepaalde coëfficiënten is effectief als het aantal functieargumenten niet meer is dan 5 - 6. Dit komt door het feit dat het aantal vergelijkingen 2n is. Het is efficiënter om niet alle mogelijke voegwoorden voor een functie op te schrijven, maar alleen diegene die aanwezig kunnen zijn in de DNF van deze functie. Hierop is de werkwijze van Quine gebaseerd. Er wordt aangenomen dat de functie is gespecificeerd in de vorm van SDNF. Bij deze methode worden elementaire conjuncties van rang n die in de DNF zijn opgenomen, minitermen van rang n genoemd. De methode van Quine bestaat uit het achtereenvolgens uitvoeren van de volgende stappen.

1. Het vinden van primaire implicaties

We bekijken elke miniterm van de functie opeenvolgend en voegen deze samen met alle minitermen waarmee dit mogelijk is. Als resultaat van het aan elkaar lijmen van n-rang minitermen, verkrijgen we (n-1)-rang minitermen. We markeren de n-rang minitermen die hebben deelgenomen aan de lijmoperatie. Vervolgens beschouwen we minitermen van rang (n-1) en passen we de lijmbewerking daarop toe. We markeren de gelijmde minitermen van (n-1) rang en noteren de resulterende minitermen van (n-2) rang, enz. De fase eindigt als de nieuw verkregen minitermen l-de rang blijft niet langer bij elkaar. Alle ongemarkeerde minitermen worden priemimplicanten genoemd. Hun disjunctie is Abbr. DNF-functies.

We lijmen minitermen van de 4e rang aan elkaar en markeren de gelijmde minitermen met asterisken

We vormen miniterms van de 2e rang:

De primaire (eenvoudige) implicaties zijn:

2. Plaatsing van markeringen

Voor deze functie Afk. DNF heeft de vorm:

Om doodlopende DNF's en Abbr. DNF moet de extra intervallen weggooien. We bouwen een tabel waarvan de rijen overeenkomen met de primaire implicaties, en de kolommen overeenkomen met de SDNF-minitermen. Als een van de minitermen een van de implicanten bevat, wordt een markering geplaatst op het snijpunt van de overeenkomstige rij en kolom, bijvoorbeeld 1.

Vervolg van het voorbeeld

3. Het vinden van essentiële implicaties

Als een kolom slechts één 1 bevat, wordt de primaire implicant die die rij definieert essentieel genoemd. De essentiële implicant is bijvoorbeeld . De essentiële implicant kan niet uit de Afkorting worden verwijderd. DNF, omdat alleen het enkele minitermen van SDNF kan bestrijken. Daarom sluiten we de rijen die overeenkomen met deze implicanten uit de tabel uit, evenals de kolommen die rijen in deze rijen hebben.

In dit voorbeeld sluiten we de rij en kolommen uit.

Als resultaat krijgen we de tafel

4. Extra kolommen en rijen doorstrepen

Als de resulterende tabel identieke kolommen heeft, streep ze dan allemaal door, op één na. Als hierna de tabel verschijnt lege regels, dan schrappen we ze.

5. Minimale dekking met maximale intervallen selecteren

Selecteer in de resulterende tabel een reeks rijen die rijen in alle kolommen bevat. Gegeven meerdere mogelijke opties voor een dergelijke keuze, wordt de voorkeur gegeven aan de optie met het minimale aantal letters in de lijnen die de dekking vormen.

Vervolg van het voorbeeld

De minimale tafeldekking wordt gevormd door de rijen die overeenkomen met de implicanten. Dan heeft MDNF de vorm:

De methode van Quine heeft één aanzienlijk ongemak dat verband houdt met de noodzaak van een volledige paarsgewijze vergelijking van minitermen in de fase van het construeren van Abbr. Niet gevonden. In 1956 stelde McCluskey een modernisering voor van de eerste fase van Quine's methode, resulterend in een aanzienlijke vermindering van het aantal minitermvergelijkingen.

Het idee van de McCluskey-methode is als volgt. Alle minitermen worden geschreven in de vorm van binaire getallen, bijvoorbeeld als 1010. Deze getallen zijn verdeeld in groepen op basis van het aantal eenheden in het getal, dat wil zeggen dat de i-de groep getallen bevat die i eenheden in hun notatie hebben. Er wordt alleen een paarsgewijze vergelijking gemaakt tussen groepen die qua aantal aan elkaar grenzen, omdat de minitermen die geschikt zijn voor lijmen slechts in één cijfer van elkaar verschillen. Wanneer minitermen met een hogere rang dan nul worden gevormd, wordt een streepje geplaatst in de cijfers die overeenkomen met de uitgesloten variabelen.

Voorbeeld

Laten we de MDNF voor de functie vinden:

Miniterms van de 4e rang per groep

Minitermen 3e rang

Minitermen 2e rang

Niet-gelabelde minitermen of primaire implicanten

Een tabel met labels maken

Beide primaire implicanten zijn essentieel en bepalen de minimale dekking, d.w.z. MDNF heeft de vorm.

Algebra's van de logica

3.3.1. Minimaliseren van FAL met behulp van de Carnot-matrix

De Carnot-matrix is ​​een soort FAL-waarheidstabel, die is opgedeeld in cellen. Het aantal matrixcellen is 2 N, Waar N– aantal FAL-argumenten. De kolommen en rijen van een matrix worden aangeduid met sets argumenten. Elke cel van de matrix komt overeen met een bestanddeel van de FAL-eenheid (binair getal). Het binaire getal van een cel bestaat uit een reeks rij- en kolomargumenten. De Carnot-matrix voor FAL wordt, afhankelijk van twee argumenten, gepresenteerd in de vorm van tabel 3.3, op basis van drie argumenten in tabel 3.4. en uit vier argumenten tabel 3.5.

Tabel 3.3.

Tabel 3.5.

X 3 X 4 X 1 X 2
	0 0 0 0	0 0 0 1	0 0 1 1	0 0 1 0
	0 1 0 0	0 1 0 1	0 1 1 1	0 1 1 0
	1 1 0 0	1 1 0 1	1 1 1 1	1 1 1 0
	1 0 0 0	1 0 0 1	1 0 1 1	1 0 1 0

De cellen van de matrices (tabellen 3.3., 3.4. en 3.5.) zijn genummerd met decimale equivalenten binaire getallen cellen. Aangrenzende matrixcellen, zowel horizontaal als verticaal, bevatten aangrenzende binaire getallen. Bovendien worden aangrenzende binaire getallen aangetroffen in alle kolommen van de bovenste en onderste rij, evenals in alle rijen van de buitenste kolommen.

Het proces van het minimaliseren van FAL met behulp van de Carnot-matrix is ​​gebaseerd op de wet van het lijmen van aangrenzende binaire getallen. U kunt binaire getallen van aangrenzende cellen aan elkaar lijmen, maar het wordt aanbevolen om sets argumenten te lijmen die de rijen en kolommen van matrices aangeven. Laten we eens kijken naar het lijmen van de binaire getallen van de cellen van de eerste kolom van de matrix (Tabel 3.5).

Cellen 0 en 4, binaire getallen 0000 en 0100, respectievelijk, het resultaat van lijmen is 0-00.

Cellen 8 en 12, binaire getallen 1000 en 1100, resultaat 1-00. De resulterende implicanten zijn aan elkaar gelijmd, omdat Het streepje bevindt zich op dezelfde plaats en de impliciete binaire getallen liggen naast elkaar, het eindresultaat is - 00.

Cellen 8 en 12

Als dus alle binaire getallen van één kolom aan elkaar worden gelijmd, verdwijnen de bits die de rijen aangeven. Op dezelfde manier, als alle binaire getallen van één rij aan elkaar zijn gelijmd, bijvoorbeeld 4, 5, 7, 6, verdwijnen alle cijfers die de kolommen aangeven, d.w.z. het resultaat is de volgende 01- -.

Als de binaire getallen van slechts twee willekeurige cellen aan elkaar zijn gelijmd, wordt er een streepje geplaatst in plaats van dat cijfer van de binaire getallen van een rij of kolom dat zal veranderen wanneer cellen van de ene regel naar de andere gaan (of van de ene kolom naar de andere). . Als u bijvoorbeeld de getallen van cellen 5 en 13 aan elkaar plakt, krijgen we het resultaat -101, of van cellen 7 en 6 is het resultaat 011-.

Bij het lijmen van binaire getallen van acht aangrenzende cellen verdwijnen drie variabelen, bijvoorbeeld voor cellen 3, 7, 15, 11, 2, 6, 14, 10 verdwijnen variabelen X 1 , X 2 , X 3. Variabelen X 1 , X 2 verdwijnen omdat alle cellen van de kolommen aan elkaar zijn gelijmd, en X 3 omdat de laatste twee kolommen aan elkaar zijn gelijmd.

Voordat we voorbeelden bekijken van het minimaliseren van FAL met behulp van de Carnot-matrix, is het noodzakelijk om de sets argumenten te classificeren met behulp waarvan de functies van de algebra van de logica worden bepaald.

Het is bekend dat er voor elke FAL 2 sets argumenten zijn N, Waar N– het aantal argumenten waarvan een functie of logische expressie afhankelijk is.

Argumentensets zijn onderverdeeld in drie typen

1. De sets argumenten waarvoor de functie gelijk is aan één, worden werken genoemd.

2. Reeksen argumenten waarvan de functie gelijk is aan nul worden verboden genoemd.

3. Reeksen argumenten waarvoor een functie gelijk kan zijn aan één of nul, worden indifferent genoemd.

Als een gegeven FAL geen indifferente sets heeft, kan deze worden weergegeven in letterlijke uitdrukking in de vorm van SDNF. Als er indifferente sets zijn in een gegeven FAL, kan de representatie ervan de volgende vorm hebben.

waar zijn decimale equivalenten werk sets,

– decimale equivalenten van verboden sets.

Reeksen argumenten die niet tot de werkende en verboden behoren, zullen onverschillig zijn.

Voorbeeld 3.3. Minimaliseer de gegeven FAL in de vorm van SDNF met behulp van de Carnot-matrix.

Daarom wordt de functie alleen door werksets gespecificeerd. De rest zal verboden worden. De functie is afhankelijk van slechts drie argumenten. We bouwen een Carnot-matrix en plaatsen enen in de cellen die overeenkomen met de werksets, en plaatsen nullen in de overige cellen.

Tabel 3.5.

X 2 X 3 X 1
	0

Om te minimaliseren worden matrixcellen die cellen bevatten, gecombineerd tot contouren. Het circuit kan twee cellen bevatten, vier of alle acht. IN in dit voorbeeld de omtrek omvat vier aangrenzende cellen van dezelfde rij. De implicant van de gegeven contour is 1 - -. Het resultaat van de minimalisatie is als volgt, d.w.z. er vond een reductie plaats gegeven functie in SDNF met 11 letters.

Voorbeeld 3.4. Minimaliseer de Booleaanse expressie gegeven door de werkende en verboden sets met behulp van de Carnot-matrix.

We bouwen een Carnot-matrix voor vier variabelen en vullen de cellen met respectievelijk enen en nullen voor werkende en verboden sets.

Tabel 3.6.

X 3 X 4 X 1 X 2	00
			(1)
	(1)		(1)

Bij het combineren van cellen met eenheden tot contouren is het wenselijk dat elke contour het grootst mogelijke aantal cellen omvat. Om dit te doen, gebruiken we de cellen van een aantal indifferente sets als cellen van werksets, waarbij we de cellen tussen haakjes vervangen. Als resultaat krijgen we drie contouren met elk 4 cellen. In de gegeneraliseerde circuitcode, die alle cellen van één regel omvat, verdwijnen variabelen X 2 X 3 (10 - -). In de gegeneraliseerde circuitcode, die alle cellen van één kolom omvat, verdwijnen variabelen X 1 X 2 (- - 11) en voor een contour die twee cellen van twee lijnen bevat, verdwijnen de variabelen X 2 (bij het verplaatsen van de ene lijn naar de andere in een contour) en X 3 (bij het verplaatsen van de ene kolom naar de andere). Als gevolg hiervan verkrijgen we de minimale DNF in het volgende formulier

Mogelijke opties de combinatie van Carnot-matrixcellen tot contouren wordt weergegeven in Figuur 3.4.

X 3 X 4 X 1 X 2

EEN = 0 - 0 -

Z = - 0 - 0

N

B = 1 - 1 -

K = - - - 1

B = - - 0 0

L = - 1 - -

Г = 1 0 - -

M = - - - 0

D = - 0 0 1

H = - 0 - -

E = - 0 1 -

F = - 1 - 1

Rijst. 3.1. Mogelijke opties voor het combineren van Carnot-matrixcellen tot contouren

3.3.2. Minimaliseren van logische algebrafuncties met behulp van een matrix van vijf variabelen

De minimalisatiematrix voor vijf variabelen is op dezelfde manier opgebouwd als de Carnot-matrix, d.w.z. in deze matrix moeten aangrenzende kolommen en rijen worden aangegeven door aangrenzende binaire aantallen sets variabelen

In een matrix met vijf variabelen (tabel 3.7) corresponderen de rijen met sets variabelen X 1 X 2 X 3, en de kolommen zijn sets variabelen X 4 X 5. Elke cel van de matrix komt overeen met een binair getal van vijf bits. De cellen van de matrix (Tabel 3.7.) bevatten de decimale equivalenten van de overeenkomstige binaire getallen.

Tabel 3.7.

X 4 X 5 X 1 X 2 X 3

Het minimaliseren van FAL met behulp van een matrix van vijf variabelen bestaat uit het combineren van cellen met werksets (inclusief, indien nodig, cellen met onverschillige sets) tot contouren en het verkrijgen van gegeneraliseerde codes die overeenkomen met deze contouren.

De eigenaardigheid hier is dat je in de kolommen van een matrix van vijf variabelen vier cellen kunt combineren tot alleen contouren, of vier cellen bovenaan, of vier cellen onderaan, of vier cellen in het midden. Voor de laatste kolom van de matrix kunnen de contouren bijvoorbeeld bestaan ​​uit de cellen 2, 6, 14, 10 of 26, 30, 22, 18 of 14, 10, 26, 30.

Voorbeeld 3.6. Gebruik een matrix met vijf variabelen om de volgende logische expressie te minimaliseren

We bouwen een matrix van vijf variabelen en vullen de cellen van de werksets met enen, en de cellen van de verboden sets met nullen.

We combineren cellen met werksets tot contouren, inclusief de noodzakelijke cellen van indifferente sets. Voor elk circuit definiëren we een gegeneraliseerde code.

Tabel 3.8.

X 4 X 5 X 1 X 2 X 3
	(1)	(1)	(1)
	(1)
	(1)	(1)
		(1)	(1)
	(1)		(1)
			(1)
	(1)		(1)

We krijgen de minimale DNF

Beveiligingsvragen

1. Definieer de afgekorte DNF.

2. Wat is een doodlopende DNF?

3. Hoe wordt de minimale DNF geselecteerd uit doodlopende DNF's?

4. Waar wordt de implicante tabel voor gebruikt en hoe is deze opgebouwd?

5. Leg de analysemethode uit voor het minimaliseren van de Quine-McClassky FAL.

6. Hoe wordt de Carnot-matrix opgebouwd voor drie en vier variabelen?

7. Minimaliseer analytisch het volgende logische uitdrukkingen, alleen gedefinieerd door werksets

8. Minimaliseer met behulp van de Carnaugh-matrix de logische expressies die zijn gespecificeerd door de werkende en verboden sets

Gerelateerde informatie.

Er zijn combinatorische en sequentiële logische apparaten.

Combinatielogische apparaten- dit zijn apparaten waarbij de waarden van de uitgangssignalen alleen afhankelijk zijn van de combinatie ingangssignalen V op dit moment tijd.

Sequentiële logische apparaten - Dit zijn apparaten waarvan de uitgangssignalen niet alleen afhankelijk zijn van de waarden van de ingangssignalen op een bepaald moment, maar ook van eerdere tijdstippen. Deze apparaten bevatten noodzakelijkerwijs geheugenelementen - triggers. Er zijn verschillende soorten triggers, afhankelijk van welke elementaire geheugenfunctie ze implementeren.

Bij het ontwikkelen van een logisch apparaat wordt eerst een verbale beschrijving van het actie-algoritme geformuleerd. Vervolgens stellen ze een logische functie samen die aan deze beschrijving voldoet (abstracte synthese) en het structureel verder ontwikkelen logisch circuit apparaten (structurele synthese).

In het proces van abstracte synthese er wordt een overgang gemaakt van een verbale beschrijving van de TP (het normale beloop en noodsituaties) naar de compilatie van een functionerend algoritme in de vorm van een tabel, cyclogram, grafiek, enz. Cyclogram vertegenwoordigt een reeks horizontale lijnen die gelijk zijn aan het aantal in- en uitgangen van een logisch apparaat. Om een ​​logisch algoritme op te stellen voor het besturen van technologische apparatuur, moet u dit hebben volledige informatie over de technische specificaties van elke technologische operatie en de gebruikte apparatuur. In dit stadium worden de volgorde van bewerkingen en de noodzakelijke tijdsvertragingen voor alle werkingsmodi van het besturingsobject verduidelijkt, worden de parameters bepaald die moeten worden bewaakt en waarmee tijdens het proces rekening moet worden gehouden; formuleer de vereisten van het beheerde object voor het logische apparaat. Deze vereisten worden weergegeven in termen van binaire signaalwaarden waarop moet worden toegepast actuatoren besturingssystemen afhankelijk van de toestand van het bestuurde object.

In het proces van structurele synthese er is een overgang van een logische functie die het functionerende algoritme beschrijft naar een blokdiagram van een logisch apparaat.

Voordat u echter begint met het ontwerpen van het circuit, moet u proberen de oorspronkelijke logische functie maximaal te converteren eenvoudige weergave. Gebaseerd op blokschema logisch apparaat ontwerp het schematisch diagram specifiek gebruiken element basis, bijvoorbeeld op de OR-HE- of NAND-basis. De laatste fase van het creëren van een logisch apparaatcircuit is de ontwikkeling en coördinatie van communicatieknooppunten van het apparaat met de operator en het bestuurde object, bescherming tegen interferentie, enz.

Historisch gezien waren de eerste apparaten die logische functies gebruikten om hun acties te beschrijven, apparaten die waren gemaakt op relaiscontactelementen. Om dergelijke apparaten te ontwerpen, werd de theorie van relaiscontactcircuits (TRC) ontwikkeld. Toen kwam contactloze apparaten, alleen bedoeld voor logische transformaties van signalen en die structureel ontworpen producten vertegenwoordigen.

Automatiseringsapparaten, waarvan de werking wordt beschreven door elementaire logische functies, worden gewoonlijk, in overeenstemming met de logische bewerking die ze implementeren, elementen NOT, AND, OR, AND-NOT, OR-HE genoemd (zie Tabel 4.1).

Hebben noodzakelijke elementen Met behulp van een logische functie kunt u een logisch apparaat van elke complexiteit synthetiseren. Het geconstrueerde circuit kan echter onredelijk complex blijken te zijn, waardoor het gebruik ervan vereist is groot aantal logische elementen, wat van invloed kan zijn op de kosten en betrouwbaarheid van het apparaat. In veel gevallen is het mogelijk een logische functie zo te vereenvoudigen dat het bijbehorende apparaatcircuit aanzienlijk eenvoudiger blijkt te zijn en de taak uitvoert.

Methoden voor het minimaliseren van logische functies. Methoden voor het vereenvoudigen van combinatieapparaten worden methoden voor het minimaliseren van logische functies genoemd. De minimalisatiemethode is gebaseerd op de toepassing van de wetten van de logische algebra, of Booleaanse algebra, die hieronder worden gegeven voor het minimumaantal variabelen. De gelijkwaardigheid van de linker- en rechterkant van de vergelijkingen wordt aangegeven door het gelijkteken. Tegelijkertijd worden relais-equivalenten van de wetten van de logische algebra afgebeeld.

Reiswet. Voor logische som en het product, de volgorde van de variabelen is onverschillig:

Combinatierecht.Het resultaat van het opeenvolgend optellen of vermenigvuldigen van variabelen is niet afhankelijk van de volgorde van deze acties:

Wet van absorptie.Optelling van een variabele met dezelfde variabele, vermenigvuldigd met een andere variabele, of het vermenigvuldigen van een variabele met de som van dezelfde variabele en een andere variabele is gelijk aan de eerste variabele:

Distributief recht.De algemene vermenigvuldiger kan tussen haakjes worden geplaatst, zoals in gewone algebra:

Wet van lijmen.De som van de producten van de eerste en tweede variabele en de tweede variabele en de inverse van de eerste variabele is gelijk aan de tweede variabele. Het product van de som van twee variabelen en de som van de inverse van de eerste variabele met de tweede variabele is gelijk aan de tweede variabele:

Wet van inversie (De wet van Morgan - Shannon).De ontkenning van de logische optelling is gelijk aan het product van de ontkenningen van de termen, En, vice versa, de ontkenning van logische vermenigvuldiging is gelijk aan de som van de ontkenningen van de factoren:

Het omkeren van een willekeurige combinatie van binaire variabelen verbonden door een plus- of vermenigvuldigingsteken staat gelijk aan het vervangen van de waarden van de variabelen erin.

hun inversies terwijl tegelijkertijd het “plus”-teken wordt veranderd in het “vermenigvuldiging”-teken en omgekeerd. Bijvoorbeeld, x t x 2 +x 3 x 4 =(x l x 2)(x 3 x 4) = (x l +x 2)(x 3 +x 4). De wet van inversie wordt alleen gevonden in de algebra van de logica.

De inversiewet maakt het dus mogelijk om de OR-bewerking te vervangen door de AND-bewerking, en, indien nodig, omgekeerd. Dit is vooral belangrijk omdat wanneer wijdverbreid gebruik van integrale logische elementen bij de constructie van logische apparaten, worden de elementen van de AND-NOT, OR-NOT-bases het vaakst gebruikt.

Transformaties van logische functies die worden uitgevoerd met behulp van de distributieve wet zijn de belangrijkste vereenvoudigingsmethode, aangezien het plaatsen van de gemeenschappelijke factor tussen haakjes het totale aantal expressievariabelen vermindert, waardoor het aantal elementen in logische apparaatcircuits kan worden verminderd.

Bij het uitvoeren van minimalisatie gebruiken ze ook de gevolgen van de wetten van de logische algebra, waarvan de belangrijkste de volgende zijn:

De laatste identiteit voor minimalisatie wordt verkregen door dubbele inversie van de vereenvoudigde uitdrukking. De eerste inversie geeft

De tweede inversie geeft

Om van de AND, OR, NOT-basis naar de OR-HE-basis en ook naar de AND-NOT-basis te gaan, wordt ook een logische formuletransformatie uitgevoerd met behulp van dubbele ontkenning. Laten we een voorbeeld bekijken van een overgang voor een relaiscircuit in Fig. 4,5, A, geïmplementeerd in de AND, OR, NOT-basis (Fig. 4.5, b), in de OR-HE-basis (Fig. 4.5, V):

en op de EN-NIET-basis (Fig. 4.5, G):

Het aantal streepjes bovenaan de formules is gelijk aan het aantal negatie-elementen, d.w.z. OR-HE- en NAND-elementen. Er zijn zes negatieven in de eerste formule, en dienovereenkomstig is het diagram in Fig. 4,5, V bevat zes OR-HE-elementen. De tweede formule bevat vijf negatieven, en dienovereenkomstig is het diagram in Fig. 4,5, G bevat vijf NAND-elementen.

Rijst. 45.

A - op relaiselementen; B - op de elementen OR, AND, NOT; V- op de elementen

OF-HIJ; Mr. NAND-elementen

Voorbeeld 4.1

Vereenvoudig de uitdrukking / = (X + y)(x + z) en teken het relaisequivalent voor en na de vereenvoudiging. Hier/ is het uitgangssignaal (status van het sluitcontact) van het relaiselement F.

Oplossing

Laten we het vereenvoudigen uitdrukking gegeven in overeenstemming met de wetten van de algebra van de logica: dat in aanmerking nemend X X = X, laten we opschrijven

Gezien het feit dat 1 + bij + z= 1, we zullen uiteindelijk /= schrijven X + bij z. Na vereenvoudiging ziet het relaisequivalent er als volgt uit:

Vereenvoudig de uitdrukking f = x-y + x y-z +y-z en teken het relaisequivalent voor en na de vereenvoudiging.

Oplossing

Vóór vereenvoudiging ziet het relaisequivalent in overeenstemming met de gegeven uitdrukking er als volgt uit:

Laten we de gegeven uitdrukking vereenvoudigen in overeenstemming met de wetten van de logische algebra, door eruit te halen gemeenschappelijke vermenigvuldiger buiten haakjes:

Het relaisdiagram van deze uitdrukking zal de vorm aannemen

Hier wordt rekening mee gehouden x-z =x + z ia + a = 1, of x+z+x+z= 1, waar a = x + z; a = x+z. Daarom zal de vereenvoudigde uitdrukking na transformatie de vorm aannemen

Na het vereenvoudigen van de uitdrukking ziet het relaisequivalent er als volgt uit:

Laten we de juistheid van de transformatie controleren met behulp van de toestandstabel (Tabel 4.2), die alle mogelijke combinaties van twee variabelen toont X en 2, en zorg ervoor dat de expressie x + g + x-z altijd gelijk aan één.

Tabel 4.2

Statustabel

		X+Z+X-Z

Laten we een voorbeeld bekijken van het gebruik van de algebra van de logica om een ​​systeem te creëren automatische regeling waterniveau in tank P (Fig. 4.6). De IM-actuator levert water aan de tank volledige opening of het sluiten van toevoerklep A. De tank heeft twee waterniveausensoren: sensor hoogste niveau B en sensor lager niveau H. Wanneer het waterniveau de positie van de sensor bereikt of overschrijdt, wordt het signaal gelijk aan één. Als het waterniveau onder het sensorniveau zakt, wordt het signaal aan de uitgang nul.

Rijst. 4.6.

Laten we de arbeidsomstandigheden analyseren automatisch systeem. Als het waterniveau het lagere niveau H bereikt, moet de toevoer worden ingeschakeld. Als het waterniveau het bovenste niveau B bereikt, moet de toevoer worden uitgeschakeld. Als het waterniveau tussen B en H ligt, moet de toevoer ingeschakeld blijven als deze door sensor H is ingeschakeld. Als de toevoer door sensor B is uitgeschakeld, moet deze uitgeschakeld blijven. Timingdiagram van signalen van de uitgang van sensoren en het stuursignaal Q getoond in afb. 4.7.

Rijst. 4.7.

in afb. 4.6

Arbeidsomstandigheden, d.w.z. alle combinaties van ingangssignalen en besturingssignalen worden vertaald in de taal van de logische algebra en gepresenteerd in Fig. 4,7 volt bovenste tafel in de vorm van enen en nullen. De tabel geeft aan bij welke verhoudingen van ingangssignalen er wel of geen signaal is Q aan de uitgang van het relais ACS. Het uitgangssignaal is het resultaat logische bewerkingen over de ingangssignalen.

Als we volgens de gegevens in de tabel proberen de bedrijfsomstandigheden op te schrijven in de vorm van logische functies, zullen we ontdekken dat het ingeschakelde stuursignaal overeenkomt met twee verschillende verhoudingen van ingangssignalen. Hetzelfde geldt voor het uitgeschakelde stuursignaal. Het resultaat is een dubbelzinnigheid in het uitgangssignaal, afhankelijk van de combinatie van ingangssignalen. Bij B = 0 en H = 1 is er sprake van een situatie waarin Q = 0 is de positie wanneer Q=l. Dit betekent dat de schakeling een geheugenelement moet hebben, dat kan worden gebruikt als de al bekende RS-flipflop T. Om de trigger in te schakelen, gebruiken we het verschijnen van een nulsignaal op uitgang 11 (II = 0). Dit signaal wordt omgekeerd en geleverd aan de instelingang S van trigger T. Omdat signaal B niet verandert, zullen we er geen rekening mee houden en de voorwaarde schrijven voor het inschakelen van S = H. We schrijven de voorwaarden voor het resetten van de trigger en het verwijderen het stuursignaal als R = B.

Systemen voor het regelen van de temperatuur tijdens het koelen zijn volgens hetzelfde principe gebouwd. elektrische machines en transformatoren, evenals krachtcentrales van auto's en tractoren die ventilatoren gebruiken. Het circuit kan ook worden gebruikt om de temperatuur automatisch op peil te houden door middel van verwarming in woon- en veehouderijen.

Laten we een ander voorbeeld bekijken van het gebruik van logische algebra om logische relaisbescherming van elektrische objecten te creëren met behulp van het voorbeeld van relaisbescherming transformator getoond in afb. 4.8.

Regels voor elektrische installatie voorzien in primaire en back-upbescherming voor kritieke faciliteiten. De hoofdbescherming moet het object zonder tijdsvertraging uitschakelen, en de back-upbescherming met een tijdsvertraging.

Rijst. 4.8.

A -stroomcircuit;B -bescherming schakelschema

De belangrijkste bescherming van transformator T1 in geval van kortsluiting in de transformator (kortsluiting op punt K1) is differentiële relaisbeveiliging (deze wordt niet weergegeven in het diagram). Back-upbeveiliging bij kortsluiting op de uitgaande bussen van het onderstation achter de Q2-schakelaar (kortsluiting op punt K2) is de maximale stroombeveiliging die werkt wanneer de stroomrelais KL1-K AZ worden geactiveerd. Kortsluiting in transformator T1 moet zonder tijdsvertraging door schakelaar Q1 worden losgekoppeld van de actie van back-upbeveiliging, d.w.z. "onmiddellijk". Een kortsluiting op punt K2 moet zonder tijdsvertraging worden uitgeschakeld door schakelaar Q2 (de beveiliging van schakelaar Q2 is niet weergegeven in het diagram). Als om de een of andere reden de beveiliging die op schakelaar Q2 of schakelaar Q2 zelf inwerkt, niet werkt, moet de back-upbeveiliging met tijdvertraging schakelaar Q1 uitschakelen.

Laten we eens kijken hoe we de prestaties van de betreffende back-upbeveiliging kunnen verbeteren als er kortsluiting optreedt in de transformator en de hoofdbeveiliging niet werkt. Hiertoe worden meetelementen aan de in- en uitgang van transformator T1 geplaatst. Ze vervullen de functie van het bepalen van de locatie van de fout: op het beschermde object of op de locatie extern netwerk. In het geval van een kortsluiting op het beveiligde object (kortsluiting in de hoofdzone) maken ze de werking van de back-upbeveiliging mogelijk zonder tijdsvertraging, en in het geval van een externe kortsluiting blokkeren ze het circuit onmiddellijke afsluiting, en de beveiliging werkt als back-up met een vertraging.

Het bepalen van de locatie van de kortsluiting gebeurt als volgt. Tijdens een kortsluiting in T1 (punt K1) worden de stroomtransformatoren TA 1-TAZ door de kortsluitstroom rondgevlogen en wordt het stroomrelais KA1-KAZ geactiveerd. Stroomtransformatoren TA4-TA5 aan de uitgang van transformator T1 zijn niet onderhevig aan kortsluitstroom. De huidige relais KA4 en KA5 werken niet, hun openingscontacten zijn gesloten. In een dergelijke situatie moet de bescherming onverwijld in werking treden. Tussenrelais KL stuurt een signaal naar open schakelaar Q1.

De bedrijfsomstandigheden van het tussenrelais KL voor ontkoppeling zonder tijdsvertraging kunnen als volgt mondeling worden geformuleerd: het KL-relais werkt als het KL1-relais werkt, OF het KA2-relais werkt OF het KAZ-relais werkt EN het KA4-relais EN de KA5 relais werkt NIET.

In wiskundige logische symbolen wordt de werkingsvoorwaarde van het KL-relais als volgt geschreven:

Tijdens een kortsluiting in een deel van het externe netwerk (punt K2) worden de stroomtransformatoren TA4 en TA5 rondgevlogen door de kortsluitstroom, wat leidt tot het in werking treden van de stroomrelais KA4 en KA5 en het openen van hun onderbrekers. contacten in het relaisbeveiligingscircuit zonder tijdsvertraging. De werking van de beveiliging wordt dus zonder tijdsvertraging geblokkeerd. Back-upbeveiliging voor kortsluiting op punt K2 werkt met een tijdvertraging.

De voorwaarde voor de werking van het tijdrelais voor back-upbeveiliging is mondeling als volgt geformuleerd: het KT-tijdrelais zal werken als het relais KA1 werkt, OF het relais KA2 werkt, OF het relais KAZ werkt.

In wiskundig-logische symbolen wordt de triggervoorwaarde van een tijdrelais geschreven als

De volledige bedrijfstoestand van het tussenrelais KL, dat de schakelaar Q1 zonder tijdsvertraging en met tijdsvertraging uitschakelt, wordt als volgt geschreven:

Schema in afb. 4.8, B geconstrueerd in overeenstemming met vergelijkingen (4.13) en (4.14). De activering van de beveiliging zonder tijdsvertraging (logische beveiliging) wordt geregistreerd door het indicatierelais KN1. De werking van de tijdvertragingsbeveiliging wordt geregistreerd door het signaalrelais KN2.

Het minimaliseren van logische functies is een van de typische taken tijdens het ontwerp van leercircuits. Daarom denk ik dat een dergelijk artikel een plaats heeft, ik hoop dat je het leuk vindt.

Waarom is dit nodig?

De complexiteit van een logische functie, en daarmee de complexiteit en kosten van het circuit (circuit) dat deze implementeert, is evenredig met het aantal logische bewerkingen en het aantal keren dat variabelen of hun ontkenningen voorkomen. In principe kan elke logische functie direct worden vereenvoudigd met behulp van de axioma's en stellingen van de logica, maar in de regel vereisen dergelijke transformaties omslachtige berekeningen.

Bovendien is het proces van het vereenvoudigen van Booleaanse expressies niet algoritmisch. Daarom is het beter om speciaal te gebruiken algoritmische methoden minimalisaties die het mogelijk maken dat een functie eenvoudiger, sneller en foutloos kan worden uitgevoerd. Dergelijke methoden omvatten bijvoorbeeld de Quine-methode, de Karnaugh-kaartmethode, de implicante testmethode, de implicante matrixmethode, de Quine-McCluskey-methode, enz. Deze methoden zijn het meest geschikt voor de gangbare praktijk, vooral voor het minimaliseren van een logische functie. met behulp van Karnaugh-kaarten. De Karnaugh-kaartmethode behoudt duidelijkheid wanneer het aantal variabelen niet meer dan zes bedraagt. In gevallen waarin het aantal argumenten meer dan zes bedraagt, wordt doorgaans de Quine-McCluskey-methode gebruikt.

Bij het minimaliseren van een bepaalde logische functie wordt er gewoonlijk rekening mee gehouden op welke basis het efficiënter zou zijn om de minimale vorm ervan te implementeren met behulp van elektronische circuits.

Minimaliseren van logische functies met behulp van Karnaugh-kaarten

De Karnaugh-kaart is een grafische manier om schakelfuncties (Boolean) te minimaliseren, waardoor relatief eenvoudig met grote uitdrukkingen kan worden gewerkt en potentiële rassen worden geëlimineerd. Vertegenwoordigt de bewerkingen van paarsgewijze onvolledige lijming en elementaire absorptie. Karnaugh-kaarten worden beschouwd als de waarheidstabel van een functie die dienovereenkomstig is herschikt. Carnaugh-kaarten kunnen worden gezien als een specifieke vlakke ontwikkeling van een n-dimensionale Booleaanse kubus.

Carnot-kaarten werden in 1952 uitgevonden door Edward W. Veitch en in 1953 verbeterd door Maurice Carnot, een natuurkundige bij Bell Labs, en waren bedoeld om digitale elektronische circuits te helpen vereenvoudigen.

In een Carnaugh-kaart worden Booleaanse variabelen uit de waarheidstabel overgebracht en geordend met behulp van Gray-code, waarbij elk volgend getal slechts één cijfer verschilt van het vorige.

De belangrijkste methode voor het minimaliseren van logische functies gepresenteerd in de vorm van SDNF of SCNF is de werking van paarsgewijze onvolledige lijming en elementaire absorptie. De werking van het paarsgewijze lijmen wordt uitgevoerd tussen twee termen (leden) die identieke variabelen bevatten, waarvan de voorkomens (direct en invers) samenvallen voor alle variabelen behalve één. In dit geval kunnen alle variabelen behalve één tussen haakjes worden gezet, en kunnen de directe en omgekeerde gebeurtenissen van één variabele die tussen haakjes blijft, aan elkaar worden gelijmd. Bijvoorbeeld:

De mogelijkheid van absorptie volgt uit de voor de hand liggende gelijkheden

Dus, hoofdtaak Bij het minimaliseren van SDNF en SCNF is het noodzakelijk om te zoeken naar termen die geschikt zijn voor lijmen met daaropvolgende absorptie, wat voor grote vormen een behoorlijk moeilijke taak kan zijn. Carnaugh-kaarten bieden een visuele manier om dergelijke termen te vinden.

Zoals bekend kunnen Booleaanse functies van N variabelen, gepresenteerd in de vorm van SDNF of SCNF, 2N verschillende termen bevatten. Al deze termen vormen een bepaalde structuur, topologisch equivalent aan een N-dimensionale kubus, en elke twee termen verbonden door een rand zijn geschikt voor lijmen en absorptie.

De foto laat zien eenvoudige tafel waarheidswaarde voor een functie van twee variabelen, een tweedimensionale kubus (vierkant) die overeenkomt met deze tabel, evenals een tweedimensionale kubus met de aanduiding van SDNF-termen en een equivalente tabel voor het groeperen van termen:

Bij een functie van drie variabelen heb je te maken met een driedimensionale kubus. Dit is ingewikkelder en minder visueel, maar technisch mogelijk. De figuur toont als voorbeeld een waarheidstabel voor een Booleaanse functie van drie variabelen en de bijbehorende kubus.

Zoals uit de figuur blijkt, zijn voor het driedimensionale geval complexere configuraties van termen mogelijk. Vier termen die tot één zijde van een kubus behoren, worden bijvoorbeeld gecombineerd tot één term waarbij twee variabelen worden geabsorbeerd:

Over het algemeen kunnen we zeggen dat 2K-termen die tot één K-dimensionaal vlak van een hyperkubus behoren, aan elkaar worden gelijmd tot één term, en dat K-variabelen worden geabsorbeerd.

Om het werken met Booleaanse functies van een groot aantal variabelen te vereenvoudigen, werd het volgende voorgesteld handige ontvangst. De kubus, die de structuur van termen vertegenwoordigt, wordt uitgevouwen op een vlak zoals weergegeven in de figuur. Dit maakt het mogelijk om Booleaanse functies met meer dan twee variabelen weer te geven in de vorm van een platte tabel. Houd er rekening mee dat de volgorde van de termcodes in de tabel (00 01 11 10) niet overeenkomt met de volgorde van binaire getallen, en dat de cellen in de uiterste kolommen van de tabel naast elkaar liggen.

Op een vergelijkbare manier kun je werken met functies van vier, vijf of meer variabelen. Voorbeelden van tabellen voor N=4 en N=5 worden weergegeven in de figuur. Voor deze tabellen moet er rekening mee worden gehouden dat aangrenzende cellen de cellen zijn die zich bevinden in de overeenkomstige cellen van de buitenste kolommen en de overeenkomstige cellen van de bovenste en onderste kolommen. onderste regel. Voor tabellen met 5 of meer variabelen moet u er ook rekening mee houden dat 4x4 vierkanten virtueel op elkaar liggen in de derde dimensie. Daarom liggen de overeenkomstige cellen van twee aangrenzende 4x4 vierkanten aan elkaar en kunnen de overeenkomstige termen aan elkaar worden gelijmd. .

Een Karnaugh-kaart kan voor een willekeurig aantal variabelen worden samengesteld, maar het is handig om met niet meer dan vijf variabelen te werken. In wezen is een Karnaugh-kaart een waarheidstabel die in tweedimensionale vorm is samengesteld. Dankzij het gebruik van Gray-code erin bovenste regel grenst aan de onderste en de rechterkolom grenst aan de linker, d.w.z. de hele Carnot-kaart is samengevouwen tot een torusfiguur (donut). Op het snijpunt van een rij en een kolom wordt de overeenkomstige waarde uit de waarheidstabel ingevoegd. Zodra de kaart gevuld is, kunt u beginnen met minimaliseren.

Als het nodig is om de minimale DNF te verkrijgen, beschouwen we op de kaart alleen die cellen die enen bevatten; als een CNF nodig is, beschouwen we die cellen die nullen bevatten. De minimalisatie zelf wordt uitgevoerd volgens de volgende regels (aan de hand van het voorbeeld van DNF):

Vervolgens nemen we het eerste gebied en kijken welke variabelen niet veranderen binnen dit gebied, schrijven de conjunctie van deze variabelen op, als de onveranderlijke variabele nul is, plaatsen we er een inversie overheen. Neem het volgende gebied, doe hetzelfde als voor het eerste, enzovoort voor alle gebieden. We combineren conjuncties van regio's door disjunctie.
Bijvoorbeeld (voor kaarten met twee variabelen):

Voor CNF is alles hetzelfde, alleen beschouwen we cellen met nullen, combineren we onveranderlijke variabelen binnen één regio tot disjuncties (we plaatsen inversies boven eenheidsvariabelen), en we combineren de disjuncties van regio's tot een conjunctie. Op dit punt wordt de minimalisatie als voltooid beschouwd. Dus voor de Karnaugh-kaart in figuur 1 zal de uitdrukking in DNF-formaat er als volgt uitzien:

In CNF-formaat: