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ą;

Zaprzeczenie (negacja)

[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:

Koniunkcja

[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:

Alternatywa

[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]".

Implikacja

[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:

Równoważność

[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:

Alternatywa wykluczająca

[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ń

1. Prawo podwójnego przeczenia: [math]\sim(\sim p) \Longleftrightarrow p[/math].
2. 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.
3. Prawa de Morgana:
   1. 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.)
   2. Prawo zaprzeczenia alternatywy: [math]\sim(p \vee q) \Longleftrightarrow (\sim p) \wedge (\sim q)[/math].
4. Prawo zaprzeczenia implikacji: [math]\sim(p\Longrightarrow q) \Longleftrightarrow (p \wedge \sim q)[/math].
5. Prawo transpozycji: [math](p\Longrightarrow q) \Longleftrightarrow (\sim q \Longrightarrow \sim p)[/math].
6. Prawa łączności:
   1. Łączność koniunkcji: [math][(p \wedge q) \wedge r] \Longleftrightarrow [p \wedge (q \wedge r)][/math]
   2. Łączność alternatywy: [math][(p \vee q) \vee r] \Longleftrightarrow [p \vee (q \vee r)][/math]
7. Prawa rozdzielności:
   1. koniunkcji względem alternatywy: [math](p \wedge q) \vee r \Longleftrightarrow (p \vee r) \wedge (q \vee r)[/math]
   2. 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:

[math] A=B \Longleftrightarrow \forall_x (x\in A \Longleftrightarrow x\in B). [/math]

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].

A jest podzbiorem B

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:

Suma A i B, oznaczana A ∪ B

[math] A\cup B = \{x: x\in A \vee x\in B\}. [/math]

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:

[math] A\cap B = \{x: x\in A \wedge x\in B\}. [/math]

Przecięcie A i B, oznaczane A ∩ B.

Różnia zbiorów

Różnicę zbiorów [math]A[/math] i [math]B[/math] zapiszemy już tylko wzorem i zilustrujemy:

[math] A\setminus B = \{x: x\in A \wedge x\not\in B\}. [/math]

Różnica
A\B

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]:

[math] A \times B := \{(a,b): 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:

[math] A_1 \times A_2 \times \dots \times A_n:= \{(a_1, a_2,\dots, a_n): a_1\in A_1, \dots, a_n\in A_n\} [/math]

Przykład

Nasza przestrzeń, w której żyjemy, to [math]R^3[/math].

Podstawowe zbiory liczbowe i ich oznaczenia

1. [math]\mathbb N = \{1,2,\dots\}[/math] — zbiór liczb naturalnych ("natural"),
2. [math]\mathbb Z = \{\dots, -2,-1,0,1,2,\dots\}[/math] — zbiór liczb całkowitych ("Zahlen"),
3. [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"),
4. [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].

1. [math]]a,b[=\{x\in\mathbb R: a\lt x\lt b\}[/math] (przedział obustronnie otwarty)
2. [math][a,b[=\{x\in\mathbb R: a\leq x\lt b\}[/math]
3. [math]]a,b]=\{x\in\mathbb R: a\lt x\leq b\}[/math]
4. [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].

1. [math]]a,\infty[=\{x\in\mathbb R: a\lt x\}[/math]
2. [math][a,\infty[=\{x\in\mathbb R: a\leq x \}[/math]
3. [math]]-\infty,a]=\{x\in\mathbb R: x\lt a\}[/math]
4. [math]]-\infty,a]=\{x\in\mathbb R: x \leq a\}[/math]