Logika i zbiory
Logika
Jest to zasadniczo powtórka ze szkoły średniej, być może z niektórymi rzeczami nowymi.
Często słowu "logika" nadaje się szersze znaczenie niż temu o czym będzie poniżej: np. mówi się "logiczne myślenie" w sensie wyciągania wniosków itp. Tu "logika" oznacza "formalne reguły dotyczące prawdziwości zdań".
Zdanie
Zdaniem w sensie logiki (zdaniem logicznym) nazywamy wyrażenie, któremu możemy jednoznacznie przyporządkować jedną z dwóch wartości logicznych: prawdę (1) lub fałsz (0).
Uwaga
W sensie logiki zdaniami nie są zdania pytające i rozkazujące.
Przykład
"Warszawa jest stolicą Polski" jest zdaniem (prawdziwym), "Pcim jest stolicą Polski" jest zdaniem (fałszywym), "najładniejsze kwiaty to malwy" nie jest zdaniem.
Zdania złożone
Z jednego (lub kilku) zdań możemy utworzyć nowe zdania — zdania złożone— przy pomocy operatorów logicznych (zw. czasem też spójnikami zdaniowymi, funktorami zdaniotwórczymi).
Podstawowe operatory
- Zaprzeczenie (negacja) zdania: "[math]\sim\;[/math]". Dla zdania [math]p[/math] czytamy: "nieprawda, że [math]p[/math]". Zaprzeczenie jest operacją jednoargumentową;
[math]p[/math] | [math]\sim p\;[/math] |
---|---|
1 | 0 |
0 | 1 |
- Koniunkcja zdań [math]p,\ q[/math]: "[math] \wedge [/math]". ("Mnożenie" logiczne). Operacja dwuargumentowa: czytamy "[math]p[/math] i [math]q[/math]". Koniunkcja dwóch zdań jest prawdziwa wtedy i tylko wtedy, gdy oba są prawdziwe, co ilustrujemy przy pomocy tabelki logicznej:
[math]p[/math] | [math]q[/math] | [math]p \wedge q [/math] |
---|---|---|
1 | 1 | 1 |
1 | 0 | 0 |
0 | 1 | 0 |
0 | 0 | 0 |
- Alternatywa zdań [math]p,\ q[/math]: "[math] \vee [/math]". ("Dodawanie" logiczne). Operacja dwuargumentowa: czytamy "[math]p[/math] lub [math]q[/math]". Koniunkcja dwóch zdań jest prawdziwa wtedy i tylko wtedy, gdy co najmniej jedno z nich jest prawdziwe. Zapisujemy to przy użyciu tabelki:
[math]p[/math] | [math]q[/math] | [math]p \vee q[/math] |
---|---|---|
1 | 1 | 1 |
1 | 0 | 1 |
0 | 1 | 1 |
0 | 0 | 0 |
- Implikacja zdań [math]p,\ q[/math]: "[math] \Longrightarrow [/math]". Operacja dwuargumentowa: czytamy "jeżeli [math]p[/math] to [math]q[/math]".
[math]p[/math] | [math]q[/math] | [math]p \Longrightarrow q[/math] |
---|---|---|
1 | 1 | 1 |
1 | 0 | 0 |
0 | 1 | 1 |
0 | 0 | 1 |
- Równoważność zdań: [math]p,\ q[/math]: "[math] \Longleftrightarrow [/math]". Operacja dwuargumentowa: czytamy "[math]p[/math] wtedy i tylko wtedy gdy [math]q[/math]". Dwa zdania są równoważne, gdy są oba jednocześnie prawdziwe lub jednocześnie fałszywe:
[math]p[/math] | [math]q[/math] | [math]p \Longleftrightarrow q[/math] |
---|---|---|
1 | 1 | 1 |
1 | 0 | 0 |
0 | 1 | 0 |
0 | 0 | 1 |
- Alternatywa wykluczająca zdań: [math]p,\ q[/math]: "[math] \underline{\vee}[/math]". Operacja dwuargumentowa. Jest to operacja działająca odwrotnie niż równoważność: Wynik zadziałania alternatywy wykluczającej jest prawdziwy wtedy i tylko wtedy gdy jedno ze zdań jest fałszywe, a drugie prawdziwe:
[math]p[/math] | [math]q[/math] | [math]p \underline{\vee} q[/math] |
---|---|---|
1 | 1 | 0 |
1 | 0 | 1 |
0 | 1 | 1 |
0 | 0 | 0 |
Tautologia
Tautologią nazywamy zdanie złożone, które jest prawdziwe niezależnie od wartości logicznych zdań, z których jest złożone. (W językoznawstwie "tautologią" nazywa się wyrażenie w stylu "masło maślane", czyli powtórzenie tego samego, może innymi nieco słowami; tu definicja jest nieco szersza, gdyż dotyczy zdań złożonych.)
Niektóre prawa rachunku zdań
- Prawo podwójnego przeczenia: [math]\sim(\sim p) \Longleftrightarrow p[/math].
- Prawo wyłączonego środka: Przykł: Niech [math]p[/math] będzie zdaniem: "Legia wygrała"; wtedy [math]\sim p \;[/math] to "Legia przegrała lub zremisowała". Zdanie: [math]p \vee \sim p[/math] jest zawsze prawdziwe.
- Prawa de Morgana:
- Prawo zaprzeczenia koniunkcji: [math]\sim(p \wedge q) \Longleftrightarrow (\sim p) \vee (\sim q)[/math]. (o tym można się przekonać bezpośrednim rachunkiem, wstawiając możliwe wartości logiczne zdań i patrząc czy po lewej i prawej stronie dostanie się to samo. Jest to uniwersalna metoda sprawdzania, czy dwa zdania złożone są równoważne.)
- Prawo zaprzeczenia alternatywy: [math]\sim(p \vee q) \Longleftrightarrow (\sim p) \wedge (\sim q)[/math].
- Prawo zaprzeczenia implikacji: [math]\sim(p\Longrightarrow q) \Longleftrightarrow (p \wedge \sim q)[/math].
- Prawo transpozycji: [math](p\Longrightarrow q) \Longleftrightarrow (\sim q \Longrightarrow \sim p)[/math].
- Prawa łączności:
- Łączność koniunkcji: [math][(p \wedge q) \wedge r] \Longleftrightarrow [p \wedge (q \wedge r)][/math]
- Łączność alternatywy: [math][(p \vee q) \vee r] \Longleftrightarrow [p \vee (q \vee r)][/math]
- Prawa rozdzielności:
- koniunkcji względem alternatywy: [math](p \wedge q) \vee r \Longleftrightarrow (p \vee r) \wedge (q \vee r)[/math]
- alternatywy względem koniunkcji: [math](p \vee q) \wedge r \Longleftrightarrow (p \wedge r) \vee (q \wedge r)[/math]
Kwantyfikatory
Dotyczą form zdaniowych.
- Dla każdego [math]x[/math] zachodzi [math]\phi(x)\ :\ \mathop{\forall}_x[/math] [math]\phi(x)\;[/math]
- Istnieje taki [math]x[/math], że zachodzi [math]\psi(x)\ : \ \mathop{\exists}_x[/math] [math]\psi(x)\;[/math]
Prawa de Morgana dla kwantyfikatorów
- [math]\sim ( \mathop{\exists}_x \psi(x)) \Longleftrightarrow \mathop{\forall}_{x\in X} (\sim \psi(x))[/math]
- [math]\sim ( \mathop{\forall}_{x\in X}\phi(x)) \Longleftrightarrow \mathop{\exists}_{x\in X} (\sim \phi(x))[/math]
Przykład
Powiedzieć, że "nieprawda, że wszystkie liczby naturalne są parzyste" jest tym samym, co powiedzieć, że "istnieje taka liczba naturalna, która jest nieparzysta".
Zbiory
Zbiór
Zbiór jest pojęciem pierwotnym, niedefiniowalnym. Aby jednak na tym nie poprzestać i powiedzieć o co tu chodzi, to taką pseudodefinicją mogłoby być: "coś, co zawiera elementy".
Zbiór pusty
Zbiorem pustym nazywamy zbiór, który nie zawiera żadnego elementu. Oznacza się go [math]\emptyset[/math].
Zbiór skończony
Zbiorem skończonym nazywamy zbiór posiadający skończoną ilość elementów. Ilość elementów zbioru skończonego [math]A[/math] oznaczamy jako [math]|A|[/math], czasem też [math]\# A[/math].
Równość zbiorów
Mówimy, że zbiory [math]A[/math] i [math]B[/math] są równe wtedy i tylko wtedy, gdy każdy element zbioru [math]A[/math] należy do zbioru [math]B[/math] i każdy element zbioru [math]B[/math] należy do zbioru [math]A[/math]. Zapisujemy to tak:
Zawieranie się zbiorów
Zbiór [math]A[/math] zawiera się w zbiorze [math]B[/math] wtedy i tylko wtedy, gdy każdy element zbioru [math]A[/math] jest jednocześnie elementem zbioru [math]B[/math]. Sytuację taką oznaczamy [math]A\subset B[/math], a o zbiorze [math]A[/math] mówimy, że jest podzbiorem zbioru [math]B[/math]. Zapisujemy to tak: [math]A\subset B \Longleftrightarrow (a\in A \Longrightarrow a\in B)[/math].
Przykład
Zbiór liczb parzystych jest podzbiorem zbioru liczb naturalnych.
Niektóre proste własności inkluzji (zawierania się ) zbiorów
- [math]\forall_A : \emptyset \subset A[/math] (zbiór pusty jest podzbiorem dowolnego zbioru [math]A[/math])
- [math]\forall_A : A \subset A[/math] (każdy zbiór jest swoim podzbiorem).
Podzbiór właściwy
Jeśli [math]A\subset B[/math] i [math]A\ne B[/math], to mówimy, że [math]A[/math] jest podzbiorem właściwym zbioru [math]B[/math].
Pytanie
Ile podzbiorów ma zbiór skończony zawierający [math]n[/math] elementów?
Odp. [math]2^n[/math].
Suma zbiorów
Sumą zbiorów [math]A[/math] i [math]B[/math] nazywamy zbiór tych elementów, które należą do co najmniej jednego z tych zbiorów. Zapisujemy to jako:
Przecięcie zbiorów
Przecięciem (iloczynem) zbiorów [math]A[/math] i [math]B[/math] nazywamy zbiór tych elementów, które należą do obu zbiorów. (Przecięcie nazywamy też częścią wspólną). Zapisujemy to jako:
Różnia zbiorów
Różnicę zbiorów [math]A[/math] i [math]B[/math] zapiszemy już tylko wzorem i zilustrujemy:
Rozłączność zbiorów
Mówimy, że zbiory [math]A[/math] i [math]B[/math] są rozłączne wtedy i tylko wtedy, gdy nie mają wspólnych elementów, tzn. gdy [math]A\cap B=\emptyset[/math].
Dopełnienie zbioru
Każdy zbiór [math]A[/math] możemy uważać za podzbiór jakiegoś większego zbioru [math]\Omega[/math] (wtedy [math]\Omega[/math] nazywamy nadzbiorem zbioru [math]A[/math]).
Def. Dopełnieniem zbioru [math]A[/math] do zbioru [math]\Omega[/math] nazywamy zbiór [math]A'=\Omega\setminus A[/math]. (Czasem dopełnienie [math]A[/math] oznacza się też [math]A^C[/math] od "complement").
Iloczyn kartezjański zbiorów
Iloczynem kartezjańskim zbiorów [math]A[/math] i [math]B[/math] nazywamy zbiór par uporządkowanych [math](a,b)[/math], gdzie [math]a\in A, b\in B[/math]:
Przykład
Niech [math]x,y\in A=\mathbb R[/math]. Wtedy [math](x,y)[/math] — parę liczb rzeczywistych można interpretować jako współrzędne punktu na płaszczyŹnie. Tak więc [math]\mathbb R \times \mathbb R[/math] to płaszczyzna.
Przykład
Niech [math]A[/math] — zbiór dat, [math]B[/math] — zbiór miejsc na Ziemi; wtedy [math]A\times B [/math]= [math](data,\ miejsce)[/math] — zbiór zdarzeń historycznych.
Iloczyn kartezjański [math]n[/math] zbiorów
Analogicznie definiujemy iloczyn kartezjański [math]n[/math] zbiorów [math]A_1, A_2, \dots, A_n[/math] jako zbiór [math]n[/math]-ek uporządkowanych:
Przykład
Nasza przestrzeń, w której żyjemy, to [math]R^3[/math].
Podstawowe zbiory liczbowe i ich oznaczenia
- [math]\mathbb N = \{1,2,\dots\}[/math] — zbiór liczb naturalnych ("natural"),
- [math]\mathbb Z = \{\dots, -2,-1,0,1,2,\dots\}[/math] — zbiór liczb całkowitych ("Zahlen"),
- [math]\mathbb Q = \{x: x=\frac{p}{q}, p\in \mathbb Z, q\in \mathbb Z\setminus \{0\}, p,q[/math] — względnie pierwsze [math]\}[/math] — zbiór liczb wymiernych ("quotient"),
- [math]\mathbb R[/math] — zbiór liczb rzeczywistych ("real").
Przedziały liczbowe i ich oznaczenia
Przedziały ograniczone
Niech [math]a,b\in \mathbb R[/math] i [math]a\lt b[/math].
- [math]]a,b[=\{x\in\mathbb R: a\lt x\lt b\}[/math] (przedział obustronnie otwarty)
- [math][a,b[=\{x\in\mathbb R: a\leq x\lt b\}[/math]
- [math]]a,b]=\{x\in\mathbb R: a\lt x\leq b\}[/math]
- [math][a,b]=\{x\in\mathbb R: a\leq x \leq b\}[/math] (przedział obustronnie domknięty)
Przedziały nieograniczone
Niech [math]a\in \mathbb R\,[/math].
- [math]]a,\infty[=\{x\in\mathbb R: a\lt x\}[/math]
- [math][a,\infty[=\{x\in\mathbb R: a\leq x \}[/math]
- [math]]-\infty,a]=\{x\in\mathbb R: x\lt a\}[/math]
- [math]]-\infty,a]=\{x\in\mathbb R: x \leq a\}[/math]