Logika

Logika

Spis treści

[edytuj] Wstęp

[edytuj] Co to jest zdanie?

[edytuj] Kwantyfikatory i spójniki logiczne

[edytuj] Tautologie

[edytuj] Funkcje Boolowskie

[edytuj] Relacje logiczne a zbiory

[edytuj] Relacje logiczne w języku Pascal

[edytuj] Zadania

[edytuj] Notacja beznawiasowa

Spis treści

[edytuj] Wstęp

[edytuj] Co to jest zdanie?

[edytuj] Kwantyfikatory i spójniki logiczne

[edytuj] Tautologie

[edytuj] Funkcje Boolowskie

[edytuj] Relacje logiczne a zbiory

[edytuj] Relacje logiczne w języku Pascal

[edytuj] Zadania

[edytuj] Notacja beznawiasowa

Z Wikibooks, biblioteki wolnych podręczników.

Z Wikibooks, biblioteki wolnych podręczników.

Widok

Osobiste

Nawigacja

Drukuj lub eksportuj

Szukaj

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.

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óznia się zdania proste (nie zawierające żadnych spójników logicznych) oraz zdania złożone (zawierające przynajmniej jeden spójnik logiczny).

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

Tautologie są to wyrażenie 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 Pierce'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 sytacji 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.

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ą Bool'a odsyłam właśnie do tych podręczników (kiedy powstaną)

Relacje logiczne używa się jako warunki oraz jako warunki pętli.
przykładowy warunek if x>0 or y>0znaczy tyle co jeżeli x>0 lub y>0
Inny przykład if x>0 or x<0czyli 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 {istrukcja}. Jednakże w tym przypadku należy zrócić uwagę że fałsz implikuje zarówno prawdę jaki i fałsz natomiast w instrukcji warunkowej tego nie ma.

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". Przyczym 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 (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$

$p\Rightarrow q$

$p\Leftrightarrow q$

$p \land q$

$p\oplus q$