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 :
LA ⋅ B. ¯ = LA ¯ + B. ¯ {\ displaystyle {\ overline {A \ cdot B}} = {\ overline {A}} + {\ overline {B}}} LA + B. ¯ = LA ¯ ⋅ B. ¯ {\ displaystyle {\ overline {A + B}} = {\ overline {A}} \ cdot {\ overline {B}}} Referindu-ne la termenii stabiliți, primul este declarat prin faptul că dacă un element nu aparține LA {\ displaystyle A} pentru B. {\ displaystyle B} , atunci sau nu aparține LA {\ displaystyle A} sau nu aparține B. {\ displaystyle B} sau nu le aparține amândurora. A doua teoremă este afirmată afirmând că dacă un element nu aparține LA + B. {\ displaystyle A + B} , atunci nu aparține LA {\ displaystyle A} și nu aparține B. {\ displaystyle B} .
Generalizarea la un număr este imediată n {\ displaystyle n} de variabile:
LA ⋅ B. ⋅ C. ⋯ ¯ = LA ¯ + B. ¯ + C. ¯ + ... {\ displaystyle {\ overline {A \ cdot B \ cdot C \ cdots}} = {\ overline {A}} + {\ overline {B}} + {\ overline {C}} + \ dots} LA + B. + C. + ... ¯ = LA ¯ ⋅ B. ¯ ⋅ C. ¯ ... {\ displaystyle {\ overline {A + B + C + \ dots}} = {\ overline {A}} \ cdot {\ overline {B}} \ cdot {\ overline {C}} \ dots} În logica propozițională, ele pot fi formulate în diferite moduri:
¬ ( la ∧ b ) = ¬ la ∨ ¬ b ¬ ( la ∨ b ) = ¬ la ∧ ¬ b {\ displaystyle {\ begin {matrix} \ neg {(a \ wedge b)} = \ neg {a} \ vee \ neg {b} \\\ neg {(a \ vee b)} = \ neg {a} \ wedge \ neg {b} \ end {matrix}} \ quad} sau
( la ∧ b ) ¯ = la ¯ ∨ b ¯ ( la ∨ b ) ¯ = la ¯ ∧ b ¯ {\ displaystyle \ quad {\ begin {matrix} {\ overline {(a \ wedge b)}} = {\ overline {a}} \ vee {\ overline {b}} \\ {\ overline {(a \ vee b)}} = {\ overline {a}} \ wedge {\ overline {b}} \ end {matrix}}} sau
¬ ( P. ∧ Î ) = ( ¬ P. ) ∨ ( ¬ Î ) ¬ ( P. ∨ Î ) = ( ¬ P. ) ∧ ( ¬ Î ) {\ displaystyle {\ begin {matrix} \ neg (P \ wedge Q) = (\ neg P) \ vee (\ neg Q) \\\ neg (P \ vee Q) = (\ neg P) \ wedge (\ neg Q) \ end {matrix}}} și în teoria mulțimilor:
( LA ∩ B. ) C. = LA C. ∪ B. C. {\ displaystyle (A \ cap B) ^ {C} = A ^ {C} \ cup B ^ {C}} sau
( LA ∩ B. ) ¯ = LA ¯ ∪ B. ¯ {\ displaystyle {\ overline {(A \ cap B)}} = {\ overline {A}} \ cup {\ overline {B}}} Și
( LA ∪ B. ) C. = LA C. ∩ B. C. {\ displaystyle (A \ cup B) ^ {C} = A ^ {C} \ cap B ^ {C}} sau
( LA ∪ B. ) ¯ = LA ¯ ∩ B. ¯ {\ displaystyle {\ overline {(A \ cup B)}} = {\ overline {A}} \ cap {\ overline {B}}} Î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 Teoremele pot fi dovedite atât algebric, cât și cu ajutorul tabelului adevărului, deoarece cazurile de dovedit sunt finite:
Prima teoremă Dovadă tabelară p {\ displaystyle p} q {\ displaystyle q} p ¯ {\ displaystyle {\ overline {p}}} q ¯ {\ displaystyle {\ overline {q}}} p ∨ q {\ displaystyle p \ vee q} p ∨ q ¯ {\ displaystyle {\ overline {p \ vee q}}} p ¯ ∧ q ¯ {\ displaystyle {\ overline {p}} \ wedge {\ overline {q}}} 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ă la {\ displaystyle \ mathbf {a}} , b {\ displaystyle \ mathbf {b}} Și c {\ displaystyle \ mathbf {c}} trei variabile booleene:
0 ¯ = 1 {\ displaystyle {\ overline {0}} = 1} si invers, 1 ¯ = 0 {\ displaystyle {\ overline {1}} = 0} la ¯ {\ displaystyle \ mathbf {\ overline {a}}} este negatia logica a la {\ displaystyle \ mathbf {a}} la = la ¯ ¯ {\ displaystyle \ mathbf {a} = {\ overline {\ overline {\ mathbf {a}}}}} (două negații logice se anulează reciproc, astfel încât o variabilă dublă negată este echivalentă cu variabila non negată în sine) la + 1 = 1 {\ displaystyle \ mathbf {a} + 1 = 1} la ⋅ 0 = 0 {\ displaystyle \ mathbf {a} \ cdot 0 = 0} la + la ¯ = 1 {\ displaystyle \ mathbf {a} + \ mathbf {\ overline {a}} = 1} la ⋅ la ¯ = 0 {\ displaystyle \ mathbf {a} \ cdot \ mathbf {\ overline {a}} = 0} ( la + b ) + c = la + ( b + c ) {\ displaystyle \ left (\ mathbf {a} + \ mathbf {b} \ right) + \ mathbf {c} = \ mathbf {a} + \ left (\ mathbf {b} + \ mathbf {c} \ right) } ( la ⋅ b ) ⋅ c = la ⋅ ( b ⋅ c ) {\ displaystyle \ left (\ mathbf {a} \ cdot \ mathbf {b} \ right) \ cdot \ mathbf {c} = \ mathbf {a} \ cdot \ left (\ mathbf {b} \ cdot \ mathbf {c } \ dreapta)} ( la + b ) ⋅ c = ( la ⋅ c ) + ( b ⋅ c ) {\ displaystyle \ left (\ mathbf {a} + \ mathbf {b} \ right) \ cdot \ mathbf {c} = \ left (\ mathbf {a} \ cdot \ mathbf {c} \ right) + \ left ( \ mathbf {b} \ cdot \ mathbf {c} \ right)} la + ( b ⋅ c ) = ( la + b ) ⋅ ( la + c ) {\ displaystyle \ mathbf {a} + \ left (\ mathbf {b} \ cdot \ mathbf {c} \ right) = \ left (\ mathbf {a} + \ mathbf {b} \ right) \ cdot \ left ( \ mathbf {a} + \ mathbf {c} \ right)} (rețineți cum această proprietate este valabilă numai în algebra booleană și nu în algebra comună) D IMOSTRARE :
THE) ( la + b ) + la ¯ ⋅ b ¯ = {\ displaystyle \ left (\ mathbf {a} + \ mathbf {b} \ right) + {\ overline {\ mathbf {a}}} \ cdot {\ overline {\ mathbf {b}}} =}
(Se aplică proprietatea 11 )
= [ ( la + b ) + la ¯ ] ⋅ [ ( la + b ) + b ¯ ] = {\ displaystyle = \ left [\ left (\ mathbf {a} + \ mathbf {b} \ right) + {\ overline {\ mathbf {a}}} \ right] \ cdot \ left [\ left (\ mathbf { a} + \ mathbf {b} \ right) + \ mathbf {\ overline {b}} \ right] =}
(Se aplică proprietatea 8 )
= [ ( la + la ¯ ) + b ] ⋅ [ ( b + b ¯ ) + la ] = {\ displaystyle = \ left [\ left (\ mathbf {a} + {\ overline {\ mathbf {a}}} \ right) + \ mathbf {b} \ right] \ cdot \ left [\ left (\ mathbf { b} + {\ overline {\ mathbf {b}}} \ right) + \ mathbf {a} \ right] =}
(Se aplică proprietatea 6 )
= [ ( 1 ) + b ] ⋅ [ ( 1 ) + la ] = {\ displaystyle = \ left [\ left (1 \ right) + \ mathbf {b} \ right] \ cdot \ left [\ left (1 \ right) + \ mathbf {a} \ right] =}
(Se aplică proprietatea 4 )
= 1 + 1 = 1 {\ displaystyle = 1 + 1 = 1}
II) ( la + b ) ⋅ ( la ¯ ⋅ b ¯ ) = {\ displaystyle \ left (\ mathbf {a} + \ mathbf {b} \ right) \ cdot \ left ({\ overline {\ mathbf {a}}} \ cdot {\ overline {\ mathbf {b}}} \ dreapta) =}
(Se aplică proprietatea 10 )
= la ⋅ ( la ¯ ⋅ b ¯ ) + b ⋅ ( la ¯ ⋅ b ¯ ) = {\ displaystyle = \ mathbf {a} \ cdot \ left ({\ overline {\ mathbf {a}}} \ cdot {\ overline {\ mathbf {b}}} \ right) + \ mathbf {b} \ cdot \ left ({\ overline {\ mathbf {a}}} \ cdot {\ overline {\ mathbf {b}}} \ right) =}
(Se aplică proprietatea 9 )
= b ¯ ⋅ ( la ⋅ la ¯ ) + la ¯ ⋅ ( b ⋅ b ¯ ) = {\ displaystyle = {\ overline {\ mathbf {b}}} \ cdot \ left (\ mathbf {a} \ cdot {\ overline {\ mathbf {a}}} \ right) + {\ overline {\ mathbf {a }}} \ cdot \ left (\ mathbf {b} \ cdot {\ overline {\ mathbf {b}}} \ right) =}
(Se aplică proprietatea 7 )
= b ¯ ⋅ ( 0 ) + la ¯ ⋅ ( 0 ) = {\ displaystyle = {\ overline {\ mathbf {b}}} \ cdot \ left (0 \ right) + {\ overline {\ mathbf {a}}} \ cdot \ left (0 \ right) =}
(Se aplică proprietatea 5 )
= 0 + 0 = 0 {\ displaystyle = 0 + 0 = 0}
Să fie acum c = la ¯ ⋅ b ¯ {\ displaystyle \ mathbf {c} = {\ overline {\ mathbf {a}}} \ cdot {\ overline {\ mathbf {b}}}} ; obținem de la I) și respectiv II) ecuațiile:
Ibis) ( la + b ) + c = 1 {\ displaystyle \ left (\ mathbf {a} + \ mathbf {b} \ right) + \ mathbf {c} = 1}
II-bis) ( la + b ) ⋅ c = 0 {\ displaystyle \ left (\ mathbf {a} + \ mathbf {b} \ right) \ cdot \ mathbf {c} = 0}
Combinând proprietățile 6) și respectiv 7) cu ecuațiile I-bis) și II-bis) , se pot seta cele două sisteme echivalente:
s1) { ( la + b ) + ( la + b ) ¯ = 1 ( la + b ) + c = 1 ⟹ c = ( la + b ) ¯ ⟹ c ¯ = ( la + b ) {\ displaystyle {\ begin {cases} \ left (\ mathbf {a} + \ mathbf {b} \ right) + {\ overline {\ left (\ mathbf {a} + \ mathbf {b} \ right)}} = 1 \\\ left (\ mathbf {a} + \ mathbf {b} \ right) + \ mathbf {c} = 1 \ end {cases}} \ implica \ mathbf {c} = {\ overline {\ left ( \ mathbf {a} + \ mathbf {b} \ right)}} \ implică {\ overline {\ mathbf {c}}} = \ left (\ mathbf {a} + \ mathbf {b} \ right)}
s2) { ( la + b ) ⋅ ( la + b ) ¯ = 0 ( la + b ) ⋅ c = 0 ⟹ c = ( la + b ) ¯ ⟹ c ¯ = ( la + b ) {\ displaystyle {\ begin {cases} \ left (\ mathbf {a} + \ mathbf {b} \ right) \ cdot {\ overline {\ left (\ mathbf {a} + \ mathbf {b} \ right)} } = 0 \\\ left (\ mathbf {a} + \ mathbf {b} \ right) \ cdot \ mathbf {c} = 0 \ end {cases}} \ implica \ mathbf {c} = {\ overline {\ left (\ mathbf {a} + \ mathbf {b} \ right)}} \ implică {\ overline {\ mathbf {c}}} = \ left (\ mathbf {a} + \ mathbf {b} \ right)}
Folosind din nou înlocuitorul c = la ¯ ⋅ b ¯ {\ displaystyle \ mathbf {c} = {\ overline {\ mathbf {a}}} \ cdot {\ overline {\ mathbf {b}}}} și, ulterior, proprietatea 3), obținem în cele din urmă:
c ¯ = ( la + b ) ⟹ la ¯ ⋅ b ¯ ¯ = ( la + b ) ⟹ la ¯ ⋅ b ¯ = ( la + b ) ¯ {\ displaystyle {\ overline {\ mathbf {c}}} = \ left (\ mathbf {a} + \ mathbf {b} \ right) \ implică {\ overline {{\ overline {\ mathbf {a}}} \ cdot {\ overline {\ mathbf {b}}}}} = \ left (\ mathbf {a} + \ mathbf {b} \ right) \ implică {\ overline {\ mathbf {a}}} \ cdot {\ overline {\ mathbf {b}}} = {\ overline {\ left (\ mathbf {a} + \ mathbf {b} \ right)}}}
cvd
A doua teoremă Dovadă tabelară p {\ displaystyle p} q {\ displaystyle q} p ¯ {\ displaystyle {\ overline {p}}} q ¯ {\ displaystyle {\ overline {q}}} p ∧ q {\ displaystyle p \ wedge q} p ∧ q ¯ {\ displaystyle {\ overline {p \ wedge q}}} p ¯ ∨ q ¯ {\ displaystyle {\ overline {p}} \ vee {\ overline {q}}} 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