De Morgan törvényei
A Morgan törvényei vannak azonosságok között javaslatok logika. Augustus De Morgan (1806-1871) brit matematikus fogalmazta meg őket .
Beszélt francia nyelven
A klasszikus logika szerint két állítás diszjunkciójának tagadása egyenértékű a két állítás tagadásának együttesével , ami azt jelenti, hogy a „nem (A vagy B)” azonos a „(nem A) és (nem B)” kifejezéssel .
A klasszikus logikában még mindig két állítás együttesének tagadása egyenértékű a két állítás tagadásának disszjunkciójával, ami azt jelenti, hogy a „nem (A és B)” azonos a (z) (nem A) vagy (nem B) ”.
Matematikai megállapítás
Tudva, hogy a kötőszót a jel : fejezi ki , a diszjunkciót a jel fejezi ki: és egy képlet tagadását írják .
∧{\ displaystyle \ land}∨{\ displaystyle \ lor}F{\ displaystyle F}F¯{\ displaystyle {\ overline {F}}}
- (NÁL NÉL∧B)¯↔(NÁL NÉL¯)∨(B¯){\ displaystyle {\ overline {(A \ land B)}} \ leftrightarrow ({\ overline {A}}) \ lor ({\ overline {B}})}
- (NÁL NÉL∨B)¯↔(NÁL NÉL¯)∧(B¯){\ displaystyle {\ overline {(A \ lor B)}} \ leftrightarrow ({\ overline {A}}) \ land ({\ overline {B}})}
A klasszikus logikában érvényes négy implikáció közül három az intuitionista logikában érvényes , de nem:
(NÁL NÉL∧B)¯→(NÁL NÉL¯)∨(B¯){\ displaystyle {\ overline {(A \ land B)}} \ rightarrow ({\ overline {A}}) \ lor ({\ overline {B}})}
Indokolás
Ezeknek a képleteknek az igazolásához használja például az igazságtáblák módszer- szemantikáját . Felidézzük, hogy két képlet akkor és akkor egyenértékű, ha ugyanaz az igazságtáblázatuk.
(NÁL NÉL∧B)¯↔(NÁL NÉL¯)∨(B¯){\ displaystyle {\ overline {(A \ land B)}} \ leftrightarrow ({\ overline {A}}) \ lor ({\ overline {B}})}
|
NÁL NÉL{\ displaystyle A} |
B{\ displaystyle B} |
NÁL NÉL∧B{\ displaystyle A \ land B} |
(NÁL NÉL∧B)¯{\ displaystyle {\ overline {(A \ land B)}}} |
NÁL NÉL¯{\ displaystyle {\ overline {A}}} |
B¯{\ displaystyle {\ overline {B}}} |
(NÁL NÉL¯)∨(B¯){\ displaystyle ({\ overline {A}}) \ lor ({\ overline {B}})}
|
0 |
0 |
0 |
1 |
1 |
1 |
1
|
0 |
1 |
0 |
1 |
1 |
0 |
1
|
1 |
0 |
0 |
1 |
0 |
1 |
1
|
1 |
1 |
1 |
0 |
0 |
0 |
0
|
(NÁL NÉL∨B)¯↔(NÁL NÉL¯)∧(B¯){\ displaystyle {\ overline {(A \ lor B)}} \ leftrightarrow ({\ overline {A}}) \ land ({\ overline {B}})}
|
NÁL NÉL{\ displaystyle A} |
B{\ displaystyle B} |
NÁL NÉL∨B{\ displaystyle A \ lor B} |
(NÁL NÉL∨B)¯{\ displaystyle {\ overline {(A \ lor B)}}} |
NÁL NÉL¯{\ displaystyle {\ overline {A}}} |
B¯{\ displaystyle {\ overline {B}}} |
(NÁL NÉL¯)∧(B¯){\ displaystyle ({\ overline {A}}) \ land ({\ overline {B}})}
|
0 |
0 |
0 |
1 |
1 |
1 |
1
|
0 |
1 |
1 |
0 |
1 |
0 |
0
|
1 |
0 |
1 |
0 |
0 |
1 |
0
|
1 |
1 |
1 |
0 |
0 |
0 |
0
|
Általánosítás
De Morgan állításait indukcióval általánosítják a propozíciókra, felhasználva a törvények asszociativitását és kettős eloszlását . Mivel a két bizonyítás szimmetrikus (elegendő az egyik törvény helyébe lépni a másikkal), itt csak ezt adjuk meg az első törvénynél.
nem{\ displaystyle n}∧{\ displaystyle \ land}∨{\ displaystyle \ lor}
- Igaz a ranghoz nem=2{\ displaystyle n = 2}
- Olyan igaz a sorhoz nem{\ displaystyle n}
(NÁL NÉL1∧NÁL NÉL2∧...∧NÁL NÉLnem∧NÁL NÉLnem+1)¯{\ displaystyle {\ overline {(A_ {1} \ land A_ {2} \ land ... \ land A_ {n} \ land A_ {n + 1})}}}
↔((NÁL NÉL1∧NÁL NÉL2∧...∧NÁL NÉLnem)∧NÁL NÉLnem+1)¯{\ displaystyle \ leftrightarrow {\ overline {((A_ {1} \ land A_ {2} \ land ... \ land A_ {n}) \ land A_ {n + 1})}}}
↔((NÁL NÉL1∧NÁL NÉL2∧...∧NÁL NÉLnem)¯)∨(NÁL NÉLnem+1¯){\ displaystyle \ leftrightarrow ({\ overline {(A_ {1} \ land A_ {2} \ land ... \ land A_ {n})}}) \ lor ({\ overline {A_ {n + 1}} })}
↔((NÁL NÉL1¯)∨(NÁL NÉL2¯)∨...∨(NÁL NÉLnem¯))∨(NÁL NÉLnem+1¯){\ displaystyle \ leftrightarrow (({\ overline {A_ {1}}}) \ lor ({\ overline {A_ {2}}}) \ lor ... \ lor ({\ overline {A_ {n}}} )) \ lor ({\ overline {A_ {n + 1}}})}
- Ezeknek a szabályoknak a végesen túl történő általánosítása megadja a klasszikus predikátumszámítás univerzális és egzisztenciális kvantorainak meghatározhatatlanságát . Az univerzális kvantor a konjunkció általánosításaként, az egzisztenciális kvantor pedig a (nem kizárólagos) diszjunkció általánosításaként tekinthető.
∀x(NÁL NÉLx¯)↔∃x(NÁL NÉLx)¯{\ displaystyle \ forall x ({\ overline {Ax}}) \ leftrightarrow {\ overline {\ pastāv x (Ax)}}}
∃x(NÁL NÉLx¯)↔∀x(NÁL NÉLx)¯{\ displaystyle \ pastāv x ({\ overline {Ax}}) \ leftrightarrow {\ overline {\ forall x (Ax)}}}
E négy klasszikus implikáció közül pedig csak az egyik nem érvényes az intuíciós logikában .
∀x(NÁL NÉLx)¯→∃x(NÁL NÉLx¯){\ displaystyle {\ overline {\ forall x (Ax)}} \ rightarrow \ pastāv x ({\ overline {Ax}})}
Intuitionista logikában
Az intuitionista logika szerint De Morgan törvényeinek csak egy legyengült formája van. Csak a következményei vannak
- ¬(NÁL NÉL∨B)→(¬NÁL NÉL∧¬B){\ displaystyle \ lnot (A \ lor B) \ to (\ lnot A \ land \ lnot B)}
- (¬NÁL NÉL∧¬B)→¬(NÁL NÉL∨B){\ displaystyle (\ lnot A \ land \ lnot B) \ to \ lnot (A \ lor B)}
- (¬NÁL NÉL∨¬B)→¬(NÁL NÉL∧B){\ displaystyle (\ lnot A \ lor \ lnot B) \ to \ lnot (A \ land B)}
Bemutassuk az első implikációt. Ehhez be kell mutatnunk , hogy beismerjük . Ezért meg kell mutatnunk, hogy lövünk és lövünk . Bizonyítsuk be az elsőt. Ez azt jelenti, hogy megmutatjuk, hogy mi és mi van . Arany . Ezért elegendő kétszer alkalmazni a modus ponenseket (az implikáció kiküszöbölése).
¬(NÁL NÉL∨B){\ displaystyle \ lnot (A \ lor B)}¬NÁL NÉL∧¬B{\ displaystyle \ lnot A \ land \ lnot B}¬(NÁL NÉL∨B){\ displaystyle \ lnot (A \ lor B)}NÁL NÉL→⊥{\ displaystyle A \ to \ bot}¬(NÁL NÉL∨B){\ displaystyle \ lnot (A \ lor B)}B→⊥{\ displaystyle B \ to \ bot}(NÁL NÉL∨B)→⊥{\ displaystyle (A \ l vagy B) \ to \ bot}NÁL NÉL{\ displaystyle A}⊥{\ displaystyle \ bot}NÁL NÉL→(NÁL NÉL∨B){\ displaystyle A \ to (A \ lor B)}
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">