Prawa De Morgana

Prawa De Morgana
Polecane artykuły

Prawa de Morgana - rodzina praw logiki – zawsze prawdziwych zdań w logice - noszących nazwę pochodzącą od nazwiska jego odkrywcy, jakim jest August de Morgan. Oryginalne hasła należą do rachunku klas, jednak ich rodzina odnajduje swoje miejsce także w prawach dotyczących zdań oraz predykantów (występują zmienne w zdaniu przyjmujące wartości zarówno prawdziwe jak i fałszywe oraz posiadają formę złożoną)

Prawa logiki

Prawa logiki nazywane także tautologią, są to zdania logiczne, które zawsze będą prawdziwe, bez względu na wartość logiczną, z której są zbudowane. Na ich podstawie szacuje się wynikanie logiczne jednych zdań z drugich. Stanowią podstawę operacji w logice.

August de Morgan

August de Morgan- angielski matematyk i logik. Urodzony 27 czerwca 1806 roku w Maduraju (Indie). Od 1828 roku do 1866 roku, z pięcioletnią przerwą w 1831 r. wykładał matematykę w londyńskim University College. Po wielu latach badań nad sylogistyką opracował prawa, nazwane w późniejszym czasie jego nazwiskiem. Był jedynym z przyczyniających się do powstania logiki matematycznej, rozszerzając logikę arystotelesowską. Wprowadził termin „indukcja matematyczna”. Zajmował się także innymi dziedzinami matematyki. Były to: algebra, prawdopodobieństwo, historia matematyki. Zmarł 18 marca 1871 roku w Londynie.

I Prawo de Morgana

I prawo De Morgana jest prawem zaprzeczenia koniunkcji. Określa się je wzorem: ~(p ∧ q) ↔ (~p ∨ ~q). Dowiadujemy się z niego, że zaprzeczenie koniunkcji dwóch zdań (∼(p ∧ q)) jest równoważne alternatywie zaprzeczeń tych zdań ((∼p) ∨ (∼q)) (Lapis W. 2014 s. 19).

Tabela poniżej przedstawia zestaw wartości logicznych w I Prawie de Morgana:

p q p ∧ q ~(p ∧ q) ~p ~q (∼p) ∨ (∼q) ~(p ∧ q) ↔ (~p ∨ ~q)
1 1 1 0 0 0 0 1
1 0 0 1 0 1 1 1
0 1 0 1 1 0 1 1
0 0 0 1 1 1 1 1

II Prawo de Morgana

II prawo de Morgana jest prawem zaprzeczenia alternatywy. Określa się je wzorem: ~(p ∨ q) ↔ (~p ∧ ~q) . Dowiadujemy się z niego, że zaprzeczenie alternatywy dwóch zdań (∼(p ∨ q)) jest równoważne koniunkcji zaprzeczeń tych zdań ((∼p) ∧ (∼q)) (Lapis W. 2014 s. 19).

Tabela poniżej prezentuje zestaw wartości logicznych w II Prawie de Morgana

p q p ∨ q ~(p ∨ q) ~p ~q (∼p) ∧ (∼q) ~(p ∨ q) ↔ (~p ∧ ~q)
1 1 1 0 0 0 0 1
1 0 1 0 0 1 0 1
0 1 1 0 1 0 0 1
0 0 0 1 1 1 1 1

Rachunek kwantyfikatorów

Prawa de Morgana także odnajdują swoje miejsce w rachunku kwantyfikatorów. Prawo rachunku kwantyfikatorów mówi o zdaniach zawierających kwantyfikatory oraz jest prawdziwe niezależnie od formy. Opisują one reguły zaprzeczania kwantyfikatorom. Określa się to wzorem: ~(∀x p(x)) ↔ ~(∃x ~p(x)) oraz ~(∃x p(x)) ↔ (∀x ~p(x)). Kwantyfikatory są symbolami służące do formułowania zdań takich jak: „dla każdego...” oraz „dla pewnego…” itp. w logice matematycznej (Trzęsicki K. 2008, s. 304).

Teoria Mnogości

Prawa de Morgana w teorii mnogości odnajdują swoje miejsce w opisie działania dopełnienia. Prawa de Morgana dla nieskończonych rodzin zbiorów zapisuje się analogicznie jak w teorii mnogości.

Inne ważne wzory z zakresu logiki

Z zakresu logiki poza prawami odkrytymi przez Augusta de Morgana, spotkać możemy się także z prawami takimi jak:

  • prawo podwójnej negacji: ~(~p) ) ↔ p
  • przemienność alternatywy: p ∨ q ↔ q ∨ p
  • przemienność koniunkcji: p ∧ q ↔ q ∧ p
  • łączność alternatywy: (p ∨ q) ∨ r ↔ ∨ (q ∨ r)
  • łączność koniunkcji: (p ∧ q) ∧ r ↔ p ∧ (q ∧ r)
  • rozdzielność koniunkcji względem alternatywy: p ∧ (q ∨ r) ↔ (p ∧ q) ∨ (p ∧ r)
  • rozdzielność alternatywy względem koniunkcji: p ∨ (q ∧ r) ↔ (p ∨ q) ∧ (p ∨ r)
  • prawo wyłączonego środka: p v p~
  • prawo zaprzeczenia implikacji: ~(p → q) ↔ p ∧ ~q
  • prawo zastąpienia równoważności implikacją: (p ↔ q) ↔ [(p → q) ∧ (q → p)]
  • prawo kontrapozycji: (p → q) ↔ (~q → ~p)
  • prawo odrywania: [(p → q) ∧ p] → q
  • prawo eliminacji implikacji: (p → q) ↔ (~p) ∨ q (Lapis W. 2014, s. 17).

Bibliografia

Autor: Tomasz Mirocha

.