Legile lui De Morgan

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare

Legile lui De Morgan sau teoremele lui De Morgan sunt legate de logica booleană și stabilesc relații de echivalență între conjuncția logică și operatorii de disjuncție .

Acestea sunt utilizate pentru analiza circuitelor logice (electrice, electronice, pneumatice, oricum binare, adică ON-OFF) și pentru demonstrarea teoremelor bazate pe reguli logice.

Teoreme

Cele două teoreme sunt duale :

Referindu-ne la termenii stabiliți, primul este declarat prin faptul că dacă un element nu aparține pentru , atunci sau nu aparține sau nu aparține sau nu le aparține amândurora. A doua teoremă este afirmată afirmând că dacă un element nu aparține , atunci nu aparține și nu aparține .

Generalizarea la un număr este imediată de variabile:

În logica propozițională, ele pot fi formulate în diferite moduri:

sau

sau

și în teoria mulțimilor:

sau

Și

sau

În practică, aceștia descriu comportamentul conectivelor logice (ȘI ȘI SAU) atunci când o negație este eliminată sau inserată într-o formulă între paranteze. Dacă colectați negația în afara parantezelor sau o distribuiți între termenii din paranteze, conectivul se transformă în opusul său.

Exprimat sub formă de tabel:

¬ (W + Y) = (¬W) * (¬Y)
¬ (W * Y) = (¬W) + (¬Y)
1 + W = 1
0 * W = 0
0 + W = W
1 * W = W

Demonstrație

Pictogramă lupă mgx2.svg Același subiect în detaliu: Tabelul adevărului .

Teoremele pot fi dovedite atât algebric, cât și cu ajutorul tabelului adevărului, deoarece cazurile care trebuie dovedite sunt finite:

Prima teoremă

Dovadă tabelară

V. V. F. F. V. F. F.
V. F. F. V. V. F. F.
F. V. V. F. V. F. F.
F. F. V. V. F. V. V.

Dovadă algebrică

Înainte de a trece la dovadă este util să notăm câteva proprietăți și definiții ale algebrei booleene; se consideră , Și trei variabile booleene:

  1. si invers,
  2. este negatia logica a
  3. (două negații logice se anulează reciproc, astfel încât o variabilă dublă negată să fie echivalentă cu variabila non negată în sine)
  4. (rețineți cum această proprietate este valabilă numai în algebra booleană și nu în algebra comună)

D IMOSTRARE :

THE)

(Se aplică proprietatea 11 )

(Proprietatea 8 se aplică)

(Se aplică proprietatea 6 )

(Se aplică proprietatea 4 )

II)

(Se aplică proprietatea 10 )

(Se aplică proprietatea 9 )

(Proprietatea 7 se aplică)

(Se aplică proprietatea 5 )

Să fie acum ; obținem de la I) și respectiv II) ecuațiile:

Ibis)

II-bis)

Combinând proprietățile 6) și respectiv 7) cu ecuațiile I-bis) și II-bis) , se pot seta cele două sisteme echivalente:

s1)

s2)

Folosind din nou înlocuitorul și, ulterior, proprietatea 3), obținem în cele din urmă:

cvd

A doua teoremă

Dovadă tabelară

V. V. F. F. V. F. F.
V. F. F. V. F. V. V.
F. V. V. F. F. V. V.
F. F. V. V. F. V. V.

Dovadă algebrică

Elemente conexe

linkuri externe

Matematica Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică