Algebra booleană. Partea 2. Legile și funcțiile de bază

Continuarea poveștii despre algebra booleană, convenții, reguli, operații. Tranziția la elementele de bază ale circuitelor de contact.

primul articol George Bull a fost descris ca fiind creatorul algebrei logicii. Al doilea articol va descrie operațiile de bază ale algebrei booleane și metodele de simplificare a expresiilor booleane. Deci, algebra booleană folosește enunțurile ca argumente și nu sensul lor, ci adevărul sau falsitatea afirmației.

Forma pentru scrierea expresiilor în algebră booleană.

Dacă afirmația este adevărată, atunci se scrie astfel: A = 1, dacă este falsă, atunci A = 0 (până la urmă, nu este adevărat că cartoful este un fruct). Pentru orice afirmație, A este fie adevărat (A = 1), fie fals (A = 0). Nu poate exista niciun mijloc aici. Am vorbit deja despre acest lucru.

Dacă conectați două declarații simple cu uniunea Și, obțineți o declarație complexă, care se numește produs logic. Să luăm două afirmații simple: „Trei este mai mult de două” pe care le vom desemna prin litera A, „Trei mai puțin de cinci” - cu litera B.

Prin urmare, afirmația complexă „Trei este mai mult de doi Și mai puțin de cinci” este una logică (în acest caz, majusculă Și, spune că aceasta este o operațiune „ȘI” logică, precum și mai târziu în textele „OR” și „NU”.) și B. Este desemnat după cum urmează: A ^ B sau A * B.

Înmulțirea logică (operația „ȘI”).

În algebra elementară A * A = A2. Dar în algebra lui Buhl A * A = A2 = A, A * A = A, deoarece semnul de înmulțire (*) înseamnă acum ... Și ... în sensul lui And ... Și. Toată experiența noastră confirmă faptul că A&A este aceeași cu A. singură. Nu putem fi de acord cu acest lucru. Adevărul afirmației nu se schimbă dacă este repetat de mai multe ori de factor.

Produsul a două afirmații este considerat adevărat (egal cu 1), atunci și numai dacă ambii factori sunt adevărați, și fals (egal cu 0) dacă cel puțin unul dintre factori este fals. Sunt de acord că aceste reguli nu contravin bunului simț și, în plus, respectă pe deplin regulile algebrei elementare:

1*1 = 1, 1*0 = 0 = 0*1 = 0, 0*0 = 0.

Prima egalitate are următorul conținut: dacă ambele A și B sunt adevărate, atunci produsul A * B este adevărat. În algebra Buhl, semnul de înmulțire (*) înlocuiește uniunea I.

Produsele logice pot include nu doi, ci un număr mai mare de enunțuri - factori. Și în acest caz, produsul este adevărat numai atunci când, în același timp, toți afirmațiile-factori sunt adevărați.

Adăugare logică (operație OR)

Dacă două declarații sunt conectate de către o uniune OR. acea propoziție compusă formată se numește sumă logică.

Luați în considerare un exemplu de sumă logică. Spunând A: „Astăzi voi merge la cinema”.

Declarația B: „Astăzi voi merge la discotecă.” Adăugăm ambele afirmații și obținem: „Astăzi voi merge la filme SAU la o discotecă”.

Această afirmație complexă se notează după cum urmează: A + B = C sau (A V B) = C.

Prin C am notat o enunțare complexă a unei sume logice.

În exemplul analizat, uniunea OR nu poate fi utilizată în sens exclusiv. Într-adevăr, în aceeași zi puteți ajunge la cinema și la discotecă. Și aici este vorba:

„Președintele parteneriatului de grădinărit va fi Petrov sau Ivanov”, nu este o sumă logică, deoarece o singură persoană va fi președintele, iar cealaltă va fi un grădinar obișnuit amator.

Semnul V pentru suma logică este ales pentru că este litera inițială a cuvântului latin „vel”, care înseamnă „sau”, în contrast cu cuvântul latin „aut>, care înseamnă„ și ”. Acum ar trebui să fie clar pentru toată lumea de ce produsul logic este indicat prin semn ^.

În algebra elementară există o regulă A + A = 2A. Această regulă este adevărată, indiferent de numărul care este reprezentat de litera A. În algebra booleană, regula A + A = A. îi corespunde. Întreaga noastră experiență de viață spune că a spune A sau A sau ambele A este doar un alt mod și mai lung de a spune doar A.

Ca orice afirmație compusă, suma celor două enunțuri A și B pot fi adevărate sau false. Suma este considerată adevărată, adică egală cu unitatea, dacă cel puțin unul dintre termeni este adevărat:

A + B = 1 dacă OR A = 1 SAU B = 1, care este în concordanță cu aritmetica convențională:

1+0 = 0+1 = 1.

Dacă ambele afirmații însumate sunt adevărate, atunci suma este considerată adevărată, prin urmare, în algebra booleană avem: (1) + (1) = 1.

Parantezele sunt setate aici pentru a evidenția condiționalul, sensul acestei adăugări și nu aritmetica.

Suma a două afirmații este considerată falsă și egală cu zero dacă și numai dacă ambii termeni sunt false. De aici:

0 + 0=0.

Deci, suma celor două enunțuri A + B este considerată adevărată dacă este adevărat, OR A, OR B, OR ambii termeni împreună. Astfel, cuvântul OR este notat cu +.

Amintind că afirmațiile A și B pot fi adevărate sau false și, prin urmare, au o măsură a adevărului 1 sau 0, rezultatele operațiunilor AND și OR considerate pot fi rezumate în tabelele 1 și 2.

A treia operație, utilizată pe scară largă de algebra booleană, este operația de negație - NU. Vă reamintim că algebra elementară folosește operațiunile ADD, D Subract, Multiplică prin, Împărțit prin și altele.

Pentru fiecare afirmație A, există negația sa NU A, pe care o vom denota prin simbol / A. Acest lucru nu ar trebui să fie în îndoială.

Dăm exemple: „Vom merge în pădure” A, „Nu vom merge în pădure” / A.

Dacă afirmația A este adevărată, adică A = 1, atunci negația / A trebuie să fie falsă / A = 0. Și invers, dacă orice afirmație este falsă, atunci negația ei este adevărată. De exemplu: „Un cal nu mănâncă fân” / A = 0, „Un cal nu mănâncă fân” (A = 1). Acest lucru poate fi exprimat în tabelul 3.

Determinarea sensului acțiunii de negație și presupunerea că a celor două enunțuri A și / A este întotdeauna una adevărată, urmează două noi formule ale algebrei booleane:

A + (/ A) = 1 și A * (/ A) = 0.

Există și alte formule care simplifică procesarea logică a enunțurilor. De exemplu, 1 + A = 1, deoarece, conform definiției adăugării, în cazul în care un termen este egal cu unitatea, suma este întotdeauna egală cu unitatea. Rezultatul obținut nu depinde dacă A = 0 sau A = 1.

Fiecare dintre cele trei operații logice examinate (AND, SAU NU) are anumite proprietăți care sunt apropiate de regulile algebrei elementare. Dacă toate sunt formulate, atunci obținem 25 de reguli de algebră booleană. Sunt destul de suficiente pentru a rezolva aproape orice problemă logică. Fără aceste reguli, devine destul de dificil de rezolvat probleme logice din cauza complexității aparente a acestora. Încercarea de a găsi răspunsul corect fără a folosi regulile înseamnă înlocuirea lor cu ingeniozitate și raționament general. Regulile facilitează foarte mult această muncă și economisesc timp.

În cadrul articolului, este imposibil de luat în considerare toate aceste 25 de reguli, dar cei care doresc le pot găsi întotdeauna în literatura de specialitate relevantă.

Așa cum am menționat deja în primul articol din 1938, tânărul om de știință american, Claude Shannon, în articolul său „Analiza simbolică a releului și a comutării circuitelor”, folosește pentru prima dată algebra booleană pentru problemele tehnologiei releului. Descoperirea lui Shannon a fost că a realizat că metoda de proiectare a mașinilor cu releu și a calculatoarelor electronice este de fapt o ramură a logicii matematice.

Se întâmplă adesea. De mai mulți ani, savantul lucrează la o problemă care pare complet inutilă compatrioților săi - doar distracție. Dar decenii trec și, uneori, secole, iar o teorie de care nimeni nu are nevoie nu dobândește doar dreptul de a exista, dar fără ea, progresul devine de neconceput.

Ce a ajutat-o ​​pe Shannon a doua oară să „descopere” algebra booleană? Cazul? Nimic de acest fel.

Dragostea mașinilor de releu, construite pe întrerupătoare și relee convenționale, l-a ajutat pe tânărul om de știință să conecteze o teorie uitată cu sarcinile centralelor telefonice automate, la care lucra la acea vreme. Ulterior, Shannon a introdus aceeași idee de „da sau nu” în mesajele discrete și a pus bazele unei întregi secțiuni de cibernetică - teoria informației.

Algebra lui Buhl a fost foarte potrivită pentru analiza și sinteza circuitelor releului. A fost suficient să acceptăm ca o afirmație adevărată: „Există un semnal în circuit”, și ca unul fals - „Nu există semnal în circuit”, pe măsură ce a apărut o nouă algebră - algebra semnalului, algebra circuitului releului.

Noua algebră este valabilă numai pentru luarea în considerare a circuitelor releului și comutării. La urma urmei, numai în astfel de scheme este îndeplinită condiția „există un semnal” și „niciun semnal”. În cazul în care semnalul se schimbă continuu, obținând un număr arbitrar de mare de condiții intermediare (un astfel de semnal se numește analog), algebra releului nu este aplicabilă. Acest lucru trebuie să fie mereu amintit. Dar doar majoritatea calculatoarelor electronice și a mașinilor cibernetice folosesc principiul discret al procesării semnalelor, care se bazează pe elementele „da - nu”.

Expresia „Contact închis” a fost acceptată de Shannon ca fiind adevărată (1), iar „Contact deschis” ca falsă (0). Restul „algebrei”, inclusiv operațiunile AND, OR și NU și 25 de reguli, Shannon a împrumutat de la Boole.

Algebra circuitului releului s-a dovedit a fi mai simplă decât algebra booleană, deoarece se ocupă doar de elemente de tipul „da - nu”. În plus, noua algebră este mai vizuală.

Elementele din această algebră sunt contactele, pe care le vom nota prin literele A, B, C ... Contactul este închis - A, contactul este deschis - / A (literă cu liniuță).

Notarea, după cum vedeți, este complet preluată din algebra booleană. Un contact deschis este o negație a unui contact închis. Același contact nu poate fi închis și deschis.

Să fim de acord că, dacă în orice circuit, două contacte sunt notate prin aceeași literă, aceasta înseamnă că acestea iau mereu aceleași valori.

În orice moment, ambele sunt deschise în același timp, sau ambele sunt închise. Cel mai simplu mod de a le imagina conectate mecanic între ele, astfel încât ambele să se deschidă sau să se închidă simultan.

Dacă într-un anumit lanț un contact este o negație a unui alt contact, atunci semnificațiile lor sunt întotdeauna opuse. De exemplu, contactele C și / C nu pot fi niciodată deschise sau închise simultan. Și în diagrama pot fi reprezentate ca conectate mecanic: dacă unul dintre ele se deschide, atunci celălalt se închide.

Începem cunoașterea noastră cu algebra releului analizând cele mai simple circuite corespunzătoare operațiilor AND, SAU NU.

Produsul a două contacte (funcționare AND) este circuitul obținut ca urmare a conectării lor în serie: este închis (egal cu 1) numai atunci când ambele contacte sunt închise (egal cu 1).

Suma a două contacte (operație OR) va fi circuitul format atunci când sunt conectate în paralel: este închis (egal cu 1) când cel puțin unul dintre contactele care formează circuitul este închis (egal cu 1).

Opusul acestui contact (operația NU) este un contact egal cu 0 (deschis) dacă acest contact este 1 (închis) și invers.

Ca și în algebra booleană, dacă contactele sunt notate cu literele A și B, atunci vom indica produsul a două contacte cu A * B, suma cu A + B, iar contactul opus A, cu / A. Cele de mai sus sunt explicate în figurile 1, 2 și 3.

Valabilitatea tabelelor corespunzătoare operațiunilor AND, OR și NU. acum nimeni nu ar trebui să aibă îndoieli.

Să punem la punct două exemple: 1 * 0 = 0 și 1 + 0 = 1.

Din figura se poate observa că un contact închis permanent conectat în serie cu un contact deschis permanent este echivalent cu un contact permanent deschis (1 * 0 = 0) Un contact închis permanent conectat în paralel cu un contact permanent deschis este echivalent cu un contact închis permanent.

După ce ați făcut cunoștință cu aritmetica circuitelor de contact, puteți descrie orice circuit releu cu o formulă folosind convențiile acceptate. În cibernetică, astfel de formule sunt numite structurale.

Dacă formula structurală a oricărui circuit releu este 1, atunci poate trece un semnal prin acesta - circuitul este închis. Și invers, dacă formula structurală a circuitului este 0, semnalul nu va trece prin el - circuitul este spart.Concluzie: două circuite relee sunt echivalente între ele atunci când formulele lor structurale sunt egale.

În continuarea articolului, vom lua în considerare exemple de circuite de contact, circuite tipice de contact și echivalente ale acestora, precum și întocmirea diagramelor conform formulelor structurale. De asemenea, avem în vedere principalele circuite logice care îndeplinesc funcțiile algebrei booleane.

Continuarea articolului: Algebra booleană. Partea 3. Scheme de contact

Boris Aladyshkin