Logika i teoria mnogości/Wstęp do logiki

Wstęp

Logika, mimo, że zaliczana jest do przedmiotów humanistycznych, jest jednym z najważniejszych działów matematyki. Jest ona dodatkowo działem, którego nieznajomość uniemożliwia pełne poznanie matematyki. Znajomość logiki pozwala nam udowadniać twierdzenia, programować warunki itd.

Co to jest zdanie?

Zdanie logiczne to wyrażenie, którego wartość logiczną można jednoznacznie określić - stwierdzić, że jest ono prawdziwe lub fałszywe.

Zdaniami logicznymi nie są:

• pytania
  Zdanie "Czy spadł dzisiaj deszcz?", choć poprawne w języku polskim, nie jest zdaniem logicznym, ponieważ nie można mu przyporządkować wartości prawda lub fałsz; co innego, jeżeli pod uwagę weźmiemy zdanie "Spadł dzisiaj deszcz."
• wyrażenia ze zmienną
  Tego typu wyrażenia mogą być fałszywe lub prawdziwe w zależności od danego parametru oraz wszelakie stwierdzenia w stylu "zimno mi", "ten kwiat jest piękny". Dodatkowo, wśród zdań wyróżnia się zdania proste (nie zawierające żadnych spójników logicznych) oraz zdania złożone (zawierające przynajmniej jeden spójnik logiczny).

Kwantyfikatory i spójniki logiczne

Wyróżnia się trzy kwantyfikatory:

• Dla każdego  $\forall$
• Istnieje  $\exists$
• Istnieje tylko jeden. $\exists$!

Spójniki dla każdego i istnieje są w opozycji wobec siebie. Czyli "Nieprawda, że dla każdego..." znaczy tyle co "Istnieje taki, że..." Natomiast "Nieprawda, że istnieje..." znaczy "Dla każdego..."
Natomiast kwantyfikator Istnieje tylko jeden można zapisać $\exists x\subset X:(\lnot \exists y\rightarrow y\not =x)$:

Uwaga: Kolejność takich samych kwantyfikatorów nie ma znaczenia, natomiast kolejność różnych już ma.
Uwaga 2: Jeżeli przed zmienną nie ma kwantyfikatorów, to domyślnie oznacza "dla każdego".

Spójniki logiczne - podstawowymi spójnikami logicznymi są:

• implikacja ($\Rightarrow$)
• równoważność ($\Leftrightarrow$)
• negacja ($\lnot$) (not)
• alternatywa ($\lor$) (or)
• koniunkcja ($\land$) (and)
• alternatywa wykluczająca ($\oplus$) (xor)

Wartości logiczne zdań złożonych:

p	q	$p\Rightarrow q$	$p\Leftrightarrow q$	$p\lor q$	$p\land q$	$p\oplus q$
1	1	1	1	1	1	0
1	0	0	0	1	0	1
0	1	1	0	1	0	1
0	0	1	1	0	0	0

Tautologie

Tautologie są to wyrażenia zawsze prawdziwe niezależnie od tego jakie zdania podstawimy. Tautologie są często wykorzystywanie w innych działach matematyki, na przykład przy dowodzeniu twierdzeń.
Najczęściej używane tautologie.
$p\Leftrightarrow \lnot (\lnot p)$ Prawo podwójnego zaprzeczenia
$\lnot (p\land q)\Leftrightarrow \lnot p\lor \lnot q$
$\lnot (p\lor q)\Leftrightarrow \lnot p\land \lnot q$ Prawa de Morgana
$(p\Rightarrow q)\Leftrightarrow (\lnot q\Rightarrow p)$
$(p\Rightarrow q\Rightarrow z)\Rightarrow (p\Rightarrow z)$ Prawo przechodności implikacji. Uwaga niektórzy mylą tą tautologie ze zdaniem $(p\Rightarrow q\Rightarrow z)\Leftrightarrow (p\Rightarrow z)$, które tautologią nie jest.
$p\Rightarrow p$
$p\Rightarrow (q\Rightarrow p)$
$p\Rightarrow (q\Rightarrow p\land q)$
$(p\Rightarrow (q\Rightarrow r))\Rightarrow ((p\Rightarrow q)\Rightarrow (p\Rightarrow r))$ Prawo sylogizmu warunkowego
$p\lor \lnot p$ Prawo wyłączonego środka
$\lnot (p\land \lnot p)$ Prawo sprzeczności
$(p\Rightarrow q)\Leftrightarrow (\lnot q\Rightarrow \lnot p)$ Prawo transpozycji
$((p\Rightarrow q)\Rightarrow p)\Rightarrow p$ Prawo Peirce'a
$(p\Rightarrow q)\Leftrightarrow (\lnot p\lor q)$

Jak rozpoznać czy wyrażenie jest tautologią?
Sposób naiwny (totalny)
robimy tabele ze wszystkimi możliwościami wartości logicznych zdań prostych. Następnie dla wszystkich z tych możliwości wykonujemy zdanie które sprawdzamy np. sprawdźmy, czy zdanie $\lnot (p\lor q)\Leftrightarrow (\lnot p\land \lnot q)$

$p$	$q$	$(p\lor q)$	$\lnot (p\lor q)$	$(\lnot p\land \lnot q)$	$\lnot (p\lor q)\Leftrightarrow (\lnot p\land \lnot q)$
$0$	$0$	$0$	$1$	$1$	$1$
$0$	$1$	$1$	$0$	$0$	$1$
$1$	$0$	$1$	$0$	$0$	$1$
$1$	$1$	$1$	$0$	$0$	$1$

W ostatniej kolumnie są same jedynki, więc zdanie jest tautologią.
Zalety sposobu naiwnego:
+ zdanie jest dokładnie sprawdzone
+ zadanie jest łatwiejsze dla komputera
+ trudniej się pomylić
Wady sposóbu naiwnego
- duża ilość obliczeń, gdyż ilość możliwości wynosi 2^n (dla 2 zmiennych to tylko 4, ale dla 100 to jest 2^100 czyli 1'267'650'600'228'229'401'496'703'205'376)
Sposób przez zaprzeczenie.
Szukamy sytuacji, w których wyrażenie może być fałszywe. W przypadku kiedy nie ma takich możliwości to orzekamy, że wyrażenie jest tautologią
Zalety sposobu przez zaprzeczenie:
+ szybszy, gdyż nie wymaga tylu obliczeń
Wady sposobu przez zaprzeczanie:
- łatwo można przeoczyć ustawienie, w którym zdanie jest fałszywe
- sposób wymaga wprawy
- komputery nie mogą sprawdzać tym sposobem
Po wyliczeniu wad i zalet obu systemów wydawać się by mogło, że sposób przez zaprzeczenie jest gorszym sposobem niż sposób naiwny, jednakże do sprawdzenia niezbyt skomplikowanych zdań sposób przez zaprzeczenie jest znacznie lepszym sposobem.

Funkcje Boolowskie

W funkcjach Boolowskich fałszowi przyporządkowano 0 a prawdzie - 1, koniunkcji mnożenie, alternatywie dodawanie natomiast równoważność została zastąpiona przez równa się. Z implikacji zrezygnowano. Dodatkowo przyjęto, że 1+1=1 (czyli prawda lub prawda to nadal prawda, a nie dwie prawdy).

Funkcje Boolowskie są szeroko stosowane w matematyce dyskretnej oraz w każdej dziedzinie techniki i fizyki, gdzie mierzy się prawdopodobieństwo awarii w przesyle sygnałów prądu strumienia magnetycznego itd. Osoby zainteresowane Algebrą Boola odsyłam właśnie do tych podręczników (kiedy powstaną).

Relacje logiczne a zbiory

Relacje logiczne w języku Pascal

Relacje logiczne używa się jako warunki oraz jako warunki pętli.
Przykładowy warunek if x>0 or y>0 znaczy tyle co jeżeli x>0 lub y>0
Inny przykład if x>0 or x<0 czyli jeżeli x>0 lub x<0 oczywiście można to zapisać łatwiej jako if not (x=0)

Implikacja w językach programowania jest zastąpiona przez instrukcje warunkową if np. $Warunek\Rightarrow Instrukcja$ w języku pascal zapiszemy if {warunek} do {instrukcja}. Jednakże w tym przypadku należy zrócić uwagę, że fałsz implikuje zarówno prawdę, jak i fałsz ,natomiast w instrukcji warunkowej tego nie ma.

Zadania

Przykład

Czy prawdziwe jest zdanie: Jeżeli liczba x jest pierwsza, to liczba x jest złożona to liczba x jest równa cztery. To pozornie bezsensowne zdanie sporóbujmy rozpisać logicznie. Przymujemy "$p$ liczba x jest pierwsza", "$\lnot p$ liczba x jest złożona", "$q$ liczba x jest równa 4". Przy czym jeśli zdania $p$ i $q$ nie mogą być prawdziwe jednocześnie. Więc nasze zdanie po podstawieniu symboli będzie wyglądać tak $p\Rightarrow \lnot p\Rightarrow q$.

Tabela będzie wyglądać więc tak

$p$	$q$	$p\Rightarrow \lnot p$	$p\Rightarrow \lnot p\Rightarrow q$
$0$	$0$	$1$	$0$
$0$	$1$	$1$	$1$
$1$	$0$	$0$	$1$

Wynika więc, że jeśli x będzie liczbą złożoną różną od 4, to nasze zdanie jest fałszywe.

Zadania.
1. Jeżeli liczba naturalna x dzieli się przez 3, to z faktu, że liczba x nie dzieli się przez 3, wynika, że x dzieli się przez 5.
2. Jakie zdanie jest zaprzeczeniem zdania: Wszyscy Polacy i Niemcy żyją w Europie?

Notacja beznawiasowa

Notacja beznawiasowa (Jana Łukasiewcza nie mylić z Ignacym, wynalazcą lampy naftowej). W notacji beznawiasowej zdania są zapisywane za pomocą małych liter, a sybole logiczne przez pięć dużych liter - C-konukcja, D-alternatywa, E-równoważność, I-implikacja oraz N-negacja.
Jeśli po symbolu N stoi zdanie, to oznacza, że zdanie należy zanegować np. Np znaczy to samo co $\lnot p$
Jeśli po symbolu C, D, E, I. stoją dwie zmienne zdaniowe, to spójnik dotyczy tych dwóch zdań np. Cpq znaczy $p\land q$
Jeśli po symbolu C, D, E, I. stoi inny spójnik, to znaczy, że następne zdanie złożone traktujemy jako zdanie zagnieżdzone np. ICpqr znaczy tyle co $(p\land q)\Rightarrow r$