Prawa De Morgana

Prawa De Morgana
Polecane artykuły
Nominalizm Efekt domina Brzytwa Ockhama Złoty podział Kodeks Wartość bezwzględna Pascal (język programowania) Kodeks Hammurabiego Geocentryzm

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

• Lapis W. (2014) Matematyka dla laika „Matematyka dla laika”, s. 1-132
• Marciszewski W. (2003) Prawa de Morgana i ich zastosowania, „Logika”, s. 1-4
• Trzęsicki K. (2008) Logika Nauka i sztuka, s. 4-439

Autor: Tomasz Mirocha

.