Tekst źródłowy strony Logika i zbiory

__NOTOC__


==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 &mdash; '''zdania złożone'''&mdash; 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ą;
{| class="wikitable" border="1" style="margin:1em auto;text-align:center;"
|+ '''Zaprzeczenie (negacja)'''
|-
! style="width:20%" | <math>p</math>
! style="width:20%" | <math>\sim p\;</math>
|-
| 1 || style="background:papayawhip" | 0
|-
| style="background:papayawhip" | 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:
{| class="wikitable" border="1" style="margin:1em auto;text-align:center;"
|+ '''Koniunkcja'''
|-
! style="width:15%" | <math>p</math>
! style="width:15%" | <math>q</math>
! style="width:15%" | <math>p \wedge q  </math>
|-
| 1 || 1 || 1
|-
| 1 || style="background:papayawhip" | 0 || style="background:papayawhip" | 0
|-
| style="background:papayawhip" | 0 || 1 || style="background:papayawhip" | 0
|-
| style="background:papayawhip" | 0 || style="background:papayawhip" | 0 || style="background:papayawhip" | 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:
{| class="wikitable" border="1" style="margin:1em auto;text-align:center;"
|+ '''Alternatywa'''
|-
! style="width:15%" | <math>p</math>
! style="width:15%" | <math>q</math>
! style="width:15%" | <math>p \vee q</math>
|-
| 1 || 1 || 1
|-
| 1 || style="background:papayawhip" | 0 || 1
|-
| style="background:papayawhip" | 0 || 1 || 1
|-
| style="background:papayawhip" | 0 || style="background:papayawhip" | 0 || style="background:papayawhip" | 0
|}
*'''Implikacja''' zdań <math>p,\ q</math>: "<math> \Longrightarrow  </math>". Operacja dwuargumentowa: czytamy "jeżeli <math>p</math> to <math>q</math>".
{| class="wikitable" border="1" style="margin:1em auto;text-align:center;"
|+ '''Implikacja'''
|-
! style="width:15%" | <math>p</math>
! style="width:15%" | <math>q</math>
! style="width:15%" | <math>p \Longrightarrow q</math>
|-
| 1 || 1 || 1
|-
| 1 || style="background:papayawhip" | 0 || style="background:papayawhip" | 0
|-
| style="background:papayawhip" | 0 || 1 || 1
|-
| style="background:papayawhip" | 0 || style="background:papayawhip" | 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:
{| class="wikitable" border="1" style="margin:1em auto;text-align:center;"
|+ '''Równoważność'''
|-
! style="width:15%" | <math>p</math>
! style="width:15%" | <math>q</math>
! style="width:15%" | <math>p \Longleftrightarrow q</math>
|-
| 1 || 1 || 1
|-
| 1 || style="background:papayawhip" | 0 || style="background:papayawhip" | 0
|-
| style="background:papayawhip" | 0 || 1 || style="background:papayawhip" | 0
|-
| style="background:papayawhip" | 0 || style="background:papayawhip" | 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:
{| class="wikitable" border="1" style="margin:1em auto;text-align:center;"
|+ '''Alternatywa wykluczająca'''
|-
! style="width:15%" | <math>p</math>
! style="width:15%" | <math>q</math>
! style="width:15%" | <math>p \underline{\vee} q</math>
|-
| 1 || 1 || style="background:papayawhip" | 0
|-
| 1 || style="background:papayawhip" | 0 || 1
|-
| style="background:papayawhip" | 0 || 1 ||1
|-
| style="background:papayawhip" | 0 || style="background:papayawhip" | 0 || style="background:papayawhip" | 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:
<center><math>
A=B \Longleftrightarrow \forall_x (x\in A \Longleftrightarrow x\in B).
</math></center>

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

<div style="float:right;margin:1em;">[[Image:Venn A subset B.svg|150px|center|A jest podzbiorem B]]<div class="center"><small> ''A'' jest '''podzbiorem''' ''B''</small></div></div>

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

[[Image:Venn0111.svg|thumb|<div class="center">'''Suma''' ''A'' i ''B'', oznaczana ''A'' ∪ ''B''</div>]]
<center><math>
A\cup B = \{x: x\in A \vee x\in B\}.
</math></center>

===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:
<center><math>
A\cap B = \{x: x\in A \wedge x\in B\}.
</math></center>

[[Image:Venn0001.svg|thumb|<div class="center">'''Przecięcie''' ''A'' i ''B'', oznaczane ''A'' ∩ ''B''.</div>]]

===Różnia zbiorów===

'''Różnicę''' zbiorów <math>A</math> i <math>B</math> zapiszemy już tylko wzorem i zilustrujemy:

<center><math>
A\setminus B = \{x: x\in A \wedge x\not\in B\}.
</math></center>

[[Image:AVenn0100.png|thumb|<div class="center">'''Różnica'''<br /> A\B </div>]]

===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>:
<center><math>
A \times B := \{(a,b): a\in A, b\in B\}
</math></center>

====Przykład====

Niech <math>x,y\in A=\mathbb R</math>. Wtedy <math>(x,y)</math> &mdash; 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> &mdash; zbiór dat, <math>B</math> &mdash; zbiór miejsc na Ziemi; wtedy <math>A\times B </math>= <math>(data,\ miejsce)</math> &mdash; 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:
<center><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></center>

====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> &mdash; zbiór liczb ''naturalnych'' ("natural"),
#<math>\mathbb Z = \{\dots, -2,-1,0,1,2,\dots\}</math> &mdash; 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> &mdash; względnie pierwsze <math>\}</math> &mdash; zbiór liczb ''wymiernych'' ("quotient"),
#<math>\mathbb R</math> &mdash; 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<b</math>.

#<math>]a,b[=\{x\in\mathbb R: a<x<b\}</math> (przedział obustronnie otwarty)
#<math>[a,b[=\{x\in\mathbb R: a\leq x<b\}</math>
#<math>]a,b]=\{x\in\mathbb R: a<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<x\}</math> 
#<math>[a,\infty[=\{x\in\mathbb R: a\leq x \}</math>
#<math>]-\infty,a]=\{x\in\mathbb R: x<a\}</math>
#<math>]-\infty,a]=\{x\in\mathbb R:  x \leq a\}</math>