HomeplJakie są prawa De Morgana?

Jakie są prawa De Morgana?

Logika jest gałęzią matematyki, a jej częścią jest teoria mnogości. Prawa De Morgana to dwa postulaty dotyczące interakcji między zbiorami. Prawa te odnotowują poprzedników u Arystotelesa i Wilhelma Ockhama. Augustus De Morgan żył w latach 1806-1871 i jako pierwszy włączył postulowane przez siebie prawa do formalnej struktury logiki matematycznej.

Operatory w teorii mnogości

Zanim przejdziemy do postulatów De Morgana, przyjrzyjmy się kilku definicjom teorii mnogości.

Jeśli istnieją dwa zbiory elementów, które nazwiemy A i B, to przecięcie tych dwóch zbiorów jest zbiorem elementów wspólnych dla obu zbiorów. Przecięcie dwóch zbiorów jest oznaczone symbolem ∩ i jest kolejnym zbiorem, który możemy nazwać C; C = A∩B, a C to zbiór elementów, które pojawiają się zarówno w grupie A, jak iw grupie B. Podobnie suma dwóch zbiorów A i B jest nowym zbiorem zawierającym wszystkie elementy A i B i jest odnotowywana za pomocą symbol U. Zbiór C, suma A i B, C = AUB, jest zbiorem zintegrowanym ze wszystkimi elementami A i B. Trzecią definicją, o której musimy pamiętać, jest dopełnienie zbioru: jeśli mamy pewien wszechświat elementów i zbiór A tego wszechświata, dopełnienie A jest zbiorem elementów tego wszechświata, które nie należą do zbioru A. Zbiór dopełnień A jest oznaczony jako AC .

Te trzy operatory między zbiorami można uogólnić na operację między kilkoma zbiorami, to znaczy na przecięcie, sumę i dopełnienie kilku zbiorów. Spójrzmy na prosty przykład. Poniższy rysunek przedstawia diagram Venna trzech zestawów: ptaki reprezentowane przez papugę, strusia, kaczkę i pingwina; żywe istoty, które latają, reprezentowane przez papugę, kaczkę, motyla i latającą rybę, oraz żywe istoty, które pływają, reprezentowane przez kaczkę, pingwina, latającą rybę i wieloryba. Kaczka jest zbiorem przecinającym się trzech zestawów: zbiór łączący ptaki i żywe istoty, które latają, składa się ze strusia, papugi, motyla, kaczki, pingwina i latającej ryby. A dopełnieniem żywych istot, które latają i tych, które pływają, jest zestaw zawierający strusia.

Diagram Venna trzech zestawów. Diagram Venna trzech zestawów.

Prawa De Morgana

Teraz możemy zobaczyć postulaty praw De Morgana. Pierwszy postulat mówi, że dopełnienie zbioru przecięcia dwóch zbiorów A i B jest równe iloczynowi zbioru dopełnienia A i dopełnienia B. Korzystając z operatorów zdefiniowanych w poprzednim akapicie, można zapisać pierwsze prawo De Morgana jako następujący sposób:

(A∩B) do = A do UB do

Drugie prawo De Morgana postuluje, że dopełnienie zbioru unii A i B jest równe przecięciu zbioru dopełnień A ze zbiorem dopełnień B, i należy zauważyć, co następuje:

(AUB) do = ZA do ∩ B do

Zobaczmy przykład. Rozważmy zbiór liczb całkowitych od 0 do 5. Jest on oznaczony jako [0,1,2,3,4,5]. W tym wszechświecie definiujemy dwa zbiory A i B. A to zbiór liczb 1, 2 i 3; A = [1,2,3]. YB to zbiór liczb 2, 3 i 4; B = [2,3,4]. Pierwsze prawo De Morgana miałoby zastosowanie w następujący sposób.

A = [1,2,3]; B = [2,3,4]

Pierwsze prawo De Morgana: (A∩B) C = A C UB C

(A∩B) C

A∩B = [1,2,3]∩[2,3,4] = [2,3]

(A∩B) do = [2,3] do = [ 0,1,4,5 ]

A C UB C

ZA C = [ 1,2,3] C = [0,4,5]

B C = [2,3,4] C = [0,1,5]

ZA CUB C = [ 0,4,5 ]U[0,1,5] = [ 0,1,4,5]

Wynik zastosowania operatorów po obu stronach równości pokazuje, że pierwsze prawo De Morgana jest zweryfikowane. Zobaczmy zastosowanie przykładu do drugiego postulatu.

Drugie prawo De Morgana: (AUB) C = A C ∩ B C

(AUB) C

AUB = [1,2,3]U[2,3,4] = [1,2,3,4]

(AUB) do = [1,2,3,4] do = [ 0,5 ]

ZA C ∩ B C

ZA C = [ 1,2,3] C = [0,4,5]

B C = [2,3,4] C = [0,1,5]

ZA C ∩ B C = [0,4,5]∩[0,1,5] = [0,5]

Podobnie jak w przypadku pierwszego postulatu, w podanym przykładzie obowiązuje również drugie prawo De Morgana.

Źródła

AG Hamilton. Logika dla matematyków. Redakcja Paraninfo, Madryt, 1981.

Carlosa Ivorry Castillo. Logika i teoria mnogości . Dostęp w listopadzie 2021 r