Test GR2: Różnice pomiędzy wersjami

Aktualna wersja na dzień 22:16, 11 wrz 2023

$ϕ$	$ψ$	$ψ \Rightarrow ϕ$	$(ϕ \Rightarrow (ψ \Rightarrow ϕ))$
0	0	1	1
0	1	0	1
1	0	1	1
1	1	1	1

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left| x \right|\ = \left\{ \begin{array}{rll} x & \text{ gdy }, x\geq 0 \\ -x & \text{ w przeciwnym przypadku}. \end{array}}

Parser nie mógł rozpoznać (błąd składni): {\displaystyle w_3 &\rightarrow bv_3v_2w_3v_1v_3v_3v_2\ |\ aw_3v_1v_3v_3v_2\ |\ bv_3v_2v_1v_3v_3v_2 \\ \begin{array}{lll} & & |\ av_1v_3v_3v_2\ |\ bv_3v_3v_2 \end{array}}

oraz

Parser nie mógł rozpoznać (błąd składni): {\displaystyle w_3 &\rightarrow bv_3v_2w_3v_1v_3v_3v_2w_3\ |\ aw_3v_1v_3v_3v_2w_3\ |\ bv_3v_2v_1v_3v_3v_2w_3 \\ \begin{array}{lll} & & |\ av_1v_3v_3v_2w_3\ |\ bv_3v_3v_2w_3 \end{array}}

Ostatecznie, gramatyka w postaci Greibach ma postać:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle v_1 &\rightarrow bv_3v_2w_3v_1v_3\ |\ aw_3v_1v_3\ |\ bv_3v_2v_1v_3\ |\ av_1v_3\ |\ bv_3 \\ v_2 &\rightarrow bv_3v_2w_3v_1\ |\ aw_3v_1\ |\ bv_3v_2v_1\ |\ av_1\ |\ b \\ v_3 &\rightarrow bv_3v_2w_3\ |\ aw_3\ |\ bv_3v_2\ |\ a \\ w_3 &\rightarrow bv_3v_2w_3v_1v_3v_3v_2\ |\ aw_3v_1v_3v_3v_2\ |\ bv_3v_2v_1v_3v_3v_2 \\ \begin{array}{lll} & & |\ av_1v_3v_3v_2\ |\ bv_3v_3v_2 bv_3v_2w_3v_1v_3v_3v_2w_3 \\ & & |\ aw_3v_1v_3v_3v_2w_3\ |\ bv_3v_2v_1v_3v_3v_2w_3\ \\ & & |\ av_1v_3v_3v_2w_3\ |\ bv_3v_3v_2w_3 \end{array}}

\begin{array}{ccccc} K r o k & d o d a n e d o S^{'} & o k r e s l e n i e f^{'} & d o d a n e d o T^{'} \\ 0 & {q_{0}} & \emptyset \\ 1 & {q_{0}, q_{3}} & f^{'} ({q_{0}}, a) = {q_{0}, q_{3}} & \emptyset \\ {q_{0}, q_{1}} & f^{'} ({q_{0}}, b) = {q_{0}, q_{1}} \\ 2 & {q_{0}, q_{3}, q_{4}} & f^{'} ({q_{0}, q_{3}}, a) = {q_{0}, q_{3}, q_{4}} & {q_{0}, q_{3}, q_{4}} \\ f^{'} ({q_{0}, q_{3}}, b) = {q_{0}, q_{1}} \\ f^{'} ({q_{0}, q_{1}}, a) = {q_{0}, q_{3}} \\ {q_{0}, q_{1}, q_{2}} & f^{'} ({q_{0}, q_{1}}, b) = {q_{0}, q_{1}, q_{2}} & {q_{0}, q_{1}, q_{2}} \\ 3 & f^{'} ({q_{0}, q_{3}, q_{4}}, a) = {q_{0}, q_{3}, q_{4}} \\ {q_{0}, q_{1}, q_{4}} & f^{'} ({q_{0}, q_{3}, q_{4}}, b) = {q_{0}, q_{1}, q_{4}} & {q_{0}, q_{1}, q_{4}} \\ {q_{0}, q_{2}, q_{3}} & f^{'} ({q_{0}, q_{1}, q_{2}}, a) = {q_{0}, q_{2}, q_{3}} & {q_{0}, q_{2}, q_{3}} \\ f^{'} ({q_{0}, q_{1}, q_{2}}, b) = {q_{0}, q_{1}, q_{2}} \\ 4 & f^{'} ({q_{0}, q_{1}, q_{4}}, a) = {q_{0}, q_{3}, q_{4}} \\ {q_{0}, q_{1}, q_{2}, q_{4}}, & f^{'} ({q_{0}, q_{1}, q_{4}}, b) = {q_{0}, q_{1}, q_{2}, q_{4}} & {q_{0}, q_{1}, q_{2}, q_{4}} \\ {q_{0}, q_{2}, q_{3}, q_{4}} & f^{'} ({q_{0}, q_{2}, q_{3}}, a) = {q_{0}, q_{2}, q_{3}, q_{4}} & {q_{0}, q_{2}, q_{3}, q_{4}} \\ f^{'} ({q_{0}, q_{2}, q_{3}}, b) = {q_{0}, q_{1}, q_{2}} \\ 5 & f^{'} ({q_{0}, q_{1}, q_{2}, q_{4}}, a) = {q_{0}, q_{2}, q_{3}, q_{4}} \\ f^{'} ({q_{0}, q_{1}, q_{2}, q_{4}}, b) = {q_{0}, q_{1}, q_{2}, q_{4}} \\ f^{'} ({q_{0}, q_{2}, q_{3}, q_{4}}, a) = {q_{0}, q_{2}, q_{3}, q_{4}} \\ f^{'} ({q_{0}, q_{2}, q_{3}, q_{4}}, b) = {q_{0}, q_{1}, q_{2}, q_{4}} \end{array}

\begin{array}{ccccc} (s_{0}, ♯) \mapsto (s_{A}, ♯, 0) & (s_{0}, 0) \mapsto (r_{0}, ♯, 1) & (s_{0}, 1) \mapsto (r_{1}, ♯, 1) \\ (r_{0}, ♯) \mapsto (s_{R}, ♯, 0) & (r_{0}, 0) \mapsto ({r_{0}}^{'}, 0, 1) & (r_{0}, 1) \mapsto ({r_{0}}^{'}, 1, 1) \\ ({r_{0}}^{'}, ♯) \mapsto (q_{0}, ♯, - 1) & ({r_{0}}^{'}, 0) \mapsto ({r_{0}}^{'}, 0, 1) & ({r_{0}}^{'}, 1) \mapsto ({r_{0}}^{'}, 1, 1) \\ (q_{0}, 0) \mapsto (l, ♯, - 1) & (q_{0}, 1) \mapsto (s_{R}, ♯, - 1) \\ (r_{1}, ♯) \mapsto (s_{R}, ♯, 0) & (r_{1}, 0) \mapsto ({r_{1}}^{'}, 0, 1) & (r_{1}, 1) \mapsto ({r_{1}}^{'}, 1, 1) \\ ({r_{1}}^{'}, ♯) \mapsto (q_{1}, ♯, - 1) & ({r_{1}}^{'}, 0) \mapsto ({r_{1}}^{'}, 0, 1) & ({r_{1}}^{'}, 1) \mapsto ({r_{1}}^{'}, 1, 1) \\ (q_{1}, 0) \mapsto (s_{R}, ♯, 0) & (q_{1}, 1) \mapsto (l, ♯, - 1) \\ (l, ♯) \mapsto (s_{0}, ♯, 1) & (l, 0) \mapsto (l, 0, - 1) & (l, 1) \mapsto (l, 1, - 1) \\ (s_{R}, ♯) \mapsto (s_{R}, ♯, 0) \\ (s_{A}, ♯) \mapsto (s_{A}, ♯, 0) \end{array}

\begin{array}{ccccc} (s_{0}, ♯) \mapsto (s_{R}, ♯, 0) & (s_{1}, ♢) \mapsto (s 1, ♢, 1) \\ (s_{0}, 0) \mapsto (s_{1}, ♣, 1) & (s_{1}, 0) \mapsto (s_{2}, ♢, 1) \\ (s_{1}, ♯) \mapsto (s_{A}, ♯, 0) \\ (s_{2}, ♢) \mapsto (s_{2}, ♢, 1) & (s_{3}, 0) \mapsto (s_{2}, ♢, 1) \\ (s_{2}, ♯) \mapsto (s_{4}, ♯, - 1) & (s_{3}, ♢) \mapsto (s_{3}, ♢, 1) \\ (s_{2}, 0) \mapsto (s_{3}, 0, 1) & (s_{3}, ♯) \mapsto (s_{R}, ♯, 0) \\ (s_{4}, 0) \mapsto (s_{4}, 0, - 1) \\ (s_{4}, ♢) \mapsto (s_{4}, ♢, - 1) \\ (s_{4}, ♣) \mapsto (s_{2}, ♣, 1) \\ (s_{A}, ♯) \mapsto (s_{A}, ♯, 0) & (s_{R}, ♯) \mapsto (s_{R}, ♯, 0) \end{array}

\begin{array}{ccccc} s_{0} & s_{1} & s_{2} \\ τ_{𝒜} (1) & s_{0} & s_{1} & s_{2} \\ τ_{𝒜} (a) & s_{1} & s_{2} & s_{2} \\ τ_{𝒜} (b) & s_{0} & s_{0} & s_{0} \\ τ_{𝒜} (a^{2}) & s_{2} & s_{2} & s_{2} \\ τ_{𝒜} (a b) & s_{0} & s_{0} & s_{2} \\ τ_{𝒜} (b a) & s_{1} & s_{1} & s_{1} \\ τ_{𝒜} (b^{2}) & s_{0} & s_{0} & s_{0} \\ τ_{𝒜} (a b a) & s_{1} & s_{1} & s_{2} \\ . . . & . . . & . . . & . . . \end{array}

\begin{array}{ccccc} f & s_{0} & s_{1} & s_{2} & s_{3} \\ a & s_{1} & s_{2} & s_{0} & s_{2} \\ b & s_{3} & s_{2} & s_{2} & s_{2} \end{array}

Algorytm Minimalizuj2 - algorytm minimalizacji automatu wykorzystujący stabilizujący się ciąg relacji

  1  Wejście:  $𝒜 = (S, A, f, s_{0}, T)$  - automat taki, że  $L = L (𝒜)$ .
  2  Wyjście: automat minimalny  $𝒜^{'} = (S^{'}, A^{'}, f^{'}, {s_{0}}^{'}, T^{'})$  dla  $𝒜$ .
  3   ${\overline{ρ}}_{1} \leftarrow \approx_{𝒜}$ ;
  4   $i \leftarrow 1$ ;
  5  repeat
  6    Parser nie mógł rozpoznać (nieznana funkcja „\slash”): {\displaystyle \slash \slash}
 oblicz  ${\overline{ρ}}_{i}$ :  $s_{1} {\overline{ρ}}_{i} s_{2} \Leftrightarrow (s_{1} {\overline{ρ}}_{i - 1} s_{2}) \land (\forall a \in A f (s_{1}, a) {\overline{ρ}}_{i - 1} f (s_{2}, a))$ ;
  7     $i \leftarrow i + 1$ ;
  8    empty $({\overline{ρ}}_{i})$  
  9    for each  $(s_{1}, s_{2}) \in S \times S$  do
 10      flag $\leftarrow$ true;
 11      for each  $a \in A$  
 12        if not  $f (s_{1}, a) {\overline{ρ}}_{i - 1} f (s_{2}, a)$  then
 13          flag $\leftarrow$ false;
 14        end if
 15      end for
 16      if flag=true and  $s_{1} {\overline{ρ}}_{i - 1} s_{2}$  then
 17         ${\overline{ρ}}_{i} \leftarrow {\overline{ρ}}_{i} \cup {(s_{1}, s_{2})}$ ;
 18      end if
 19    end for
 20  until  ${\overline{ρ}}_{i} = {\overline{ρ}}_{i - 1}$ 
 21  Parser nie mógł rozpoznać (nieznana funkcja „\slash”): {\displaystyle S' \leftarrow S \slash \overline{\rho}_i}
;
 22  for each Parser nie mógł rozpoznać (nieznana funkcja „\slash”): {\displaystyle [s]_{\overline{\rho}_i} \in S \slash \overline{\rho}_i}
 do
 23    for each  $a \in A$  do
 24       $f^{'} ([s]_{{\overline{ρ}}_{i}}, a) \leftarrow [f (s, a)]_{{\overline{ρ}}_{i}}$ ;
 25    end for
 26  end for
 27   ${s_{0}}^{'} \leftarrow [s_{0}]_{{\overline{ρ}}_{i}}$ ;
 28   $T^{'} \leftarrow {[t]_{{\overline{ρ}}_{i}} : t \in T}$ ;
 29  return  $𝒜^{'} = (S^{'}, A, f^{'}, {s_{0}}^{'}, T^{'})$ ;

Uzupelnij tytul
	$s_{0}$ \|\| $s_{1}$ \|\| $s_{2}$
$τ_{𝒜} (1)$ \|\| $s_{0}$ \|\| $s_{1}$ \|\| $s_{2}$
$τ_{𝒜} (a)$ \|\| $s_{1}$ \|\| $s_{2}$ \|\| $s_{2}$
$τ_{𝒜} (b)$ \|\| $s_{0}$ \|\| $s_{0}$ \|\| $s_{0}$
$τ_{𝒜} (a^{2})$ \|\| $s_{2}$ \|\| $s_{2}$ \|\| $s_{2}$
$τ_{𝒜} (a b)$ \|\| $s_{0}$ \|\| $s_{0}$ \|\| $s_{2}$
$τ_{𝒜} (b a)$ \|\| $s_{1}$ \|\| $s_{1}$ \|\| $s_{1}$
$τ_{𝒜} (b^{2})$ \|\| $s_{0}$ \|\| $s_{0}$ \|\| $s_{0}$
$τ_{𝒜} (a b a)$ \|\| $s_{1}$ \|\| $s_{1}$ \|\| $s_{2}$
... \|\| ... \|\| ... \|\| ...

$\begin{array}{lll} b) \lim_{x \to 2^{+}} (x - 2) e^{\frac{1}{x - 2}} & = & \lim_{x \to 2^{+}} \frac{e^{\frac{1}{x - 2}}}{(x - 2)^{- 1}} \begin{array}{c} [\frac{\infty}{\infty}] \\ = \\ H \end{array} \lim_{x \to 2^{+}} \frac{- (x - 2)^{- 2} e^{\frac{1}{x - 2}}}{- (x - 2)^{- 2}} = \\ = & \lim_{x \to 2^{+}} e^{\frac{1}{x - 2}} = + \infty; \end{array}$

 alalalalaa

alala

	Złożoność czasowa	Złożoność pamięciowa
Maszyna dodająca	$f (0) = 1$ $f (1) = 3$ $f (n) = n + 3; n \geq 2$	$f (0) = 2$ $f (1) = 3$ $f (n) = n + 1; n \geq 2$
Maszyna rozpoznająca $w w^{\leftarrow}$	$f (n) = 6 + 8 + \dots + (n + 3) + 2; n = 2 k + 1$ $f (n) = 5 + 7 + \dots + (n + 3) + 1; n = 2 k$	$f (n) = n + 1$

$\Rightarrow$	0	1	...	...
Cell1	Cell2

$\Rightarrow$	0	1
0	1	1
1	0	1

$p$	$\neg p$
0	1
1	0

$\land$	0	1
0	0	0
1	0	1

$\lor$	0	1
0	0	1
1	1	1

$p$	$q$	$p \land q$	$\neg (p \land q)$	$\neg p$	$\neg q$	$\neg p \lor \neg q$
0	0	0	1	1	1	1
0	1	0	1	1	0	1
1	0	0	1	0	1	1
1	1	1	0	0	0	0

$p$	$q$	$r$	$(p \land q)$	$(p \land r)$	$(q \land \neg r)$	$(p \land r) \lor (q \land \neg r)$	$(p \land q) \Rightarrow ((p \land r) \lor (q \land \neg r))$
0	0	0	0	0	0	0	1
0	0	1	0	0	0	0	1
0	1	0	0	0	1	1	1
0	1	1	0	0	0	0	1
1	0	0	0	0	0	0	1
1	0	1	0	1	0	1	1
1	1	0	1	0	1	1	1
1	1	1	1	1	0	1	1

Numer funkcji	$p = 0$ $q = 0$	$p = 0$ $q = 1$	$p = 1$ $q = 0$	$p = 1$ $q = 1$
0	0	0	0	0	$F$
1	0	0	0	1	$\land$
2	0	0	1	0	$\neg (p \Rightarrow q)$
3	0	0	1	1	$p$
4	0	1	0	0	$\neg (q \Rightarrow p)$
5	0	1	0	1	$q$
6	0	1	1	0	$X O R$
7	0	1	1	1	$\lor$
8	1	0	0	0	$N O R$
9	1	0	0	1	$\Leftrightarrow$
10	1	0	1	0	$\neg q$
11	1	0	1	1	$q \Rightarrow p$
12	1	1	0	0	$\neg p$
13	1	1	0	1	$p \Rightarrow q$
14	1	1	1	0	$N A N D$
15	1	1	1	1	$T$

$p$	$q$	$r$	$(p \leftrightarrow q)$	$(p \leftrightarrow q) \leftrightarrow r$	$(q \leftrightarrow r)$	$p \leftrightarrow (q \leftrightarrow r)$
0	0	0	1	0	1	0
0	0	1	1	1	0	1
0	1	0	0	1	0	1
0	1	1	0	0	1	0
1	0	0	0	1	1	1
1	0	1	0	0	0	0
1	1	0	1	0	0	0
1	1	1	1	1	1	1

$p$	$q$	$r$	$\circ (p, q, r)$
0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	0
1	1	1	1

$p$	$q$	$r$	$f_{p \to_{(} q \to r)}$
0	0	0	1
0	0	1	1
0	1	0	1
0	1	1	1
1	0	0	1
1	0	1	1
1	1	0	0
1	1	1	1

$\Rightarrow$	0	1	2
0	2	2	2
1	0	2	2
2	0	1	2

$\hat{σ} (f (t_{0}, . ., t_{n})) = I (f) (\hat{σ} (t_{0}), . ., \hat{σ} (t_{n}))$

X^{*} = {1} \cup X \cup X^{2} \cup . . . \cup X^{n} \cup \dots = ⋃_{i = 0}^{\infty} X^{i}

Nagroda Goedla
Zobacz Nagroda Goedla]]

Nagroda Turinga
Zobacz Nagroda Turinga

Nagroda Knutha
Zobacz Nagroda Knutha

g (C) = {\begin{cases} C \cup {f (C^{'})} C \end{cases}

Parser nie mógł rozpoznać (błąd składni): {\displaystyle g(C)=\left\{\begin{align} C\cup \{f(C')\}\\C\end{align} \right}

Parser nie mógł rozpoznać (błąd składni): {\displaystyle c\forall d\; c\in C \land d\in C \land c\sqsubseteq d\implies c\sqsubseteq' d, (C,\sqsubseteq) \preccurlyeq (C',\sqsubseteq') \iff C\subset C' \land \left\{\begin{align} \forall c \forall d\; &(c\in C\land d\in C) \implies (c\sqsubseteq d \iff c\sqsubseteq' d) \text{ oraz }\\ \forall c \forall d\; &(c\in C\land d\in C'\setminus C) \implies c\sqsubseteq' d \end{align} \right}

$h (0, a) = f (a)$ dla każdego Parser nie mógł rozpoznać (błąd składni): {\displaystyle a \in A \\h(n', a) = g(h(n, a), n, a)} dla każdego $a \in A$ i $n \in ℕ$

$e (0, a) = f (a)$ dla każdego Parser nie mógł rozpoznać (błąd składni): {\displaystyle a \in A \\ e(g(n, a), n, a)} dla każdego $a \in A$ i $n \in m$

	$s_{0}$ \|\| $s_{1}$ \|\| $s_{2}$
$τ_{𝒜} (1)$ \|\| $s_{0}$ \|\| $s_{1}$ \|\| $s_{2}$
$τ_{𝒜} (a)$ \|\| $s_{1}$ \|\| $s_{2}$ \|\| $s_{2}$
$τ_{𝒜} (b)$ \|\| $s_{0}$ \|\| $s_{0}$ \|\| $s_{0}$
$τ_{𝒜} (a^{2})$ \|\| $s_{2}$ \|\| $s_{2}$ \|\| $s_{2}$
$τ_{𝒜} (a b)$ \|\| $s_{0}$ \|\| $s_{0}$ \|\| $s_{2}$
$τ_{𝒜} (b a)$ \|\| $s_{1}$ \|\| $s_{1}$ \|\| $s_{1}$
$τ_{𝒜} (b^{2})$ \|\| $s_{0}$ \|\| $s_{0}$ \|\| $s_{0}$
$τ_{𝒜} (a b a)$ \|\| $s_{1}$ \|\| $s_{1}$ \|\| $s_{2}$
... \|\| ... \|\| ... \|\| ...

Test GR2: Różnice pomiędzy wersjami

Aktualna wersja na dzień 22:16, 11 wrz 2023

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia

@@ Linia 1: / Linia 1: @@
-=="Naiwna" teoria mnogości==
+{| border="1" cellspacing="0"
+! <math>\phi</math>!! <math>\psi</math>!! <math>\psi \Rightarrow \phi</math>!! <math>(\phi \Rightarrow (\psi \Rightarrow \phi))</math>!!
+|-
+| &nbsp;0&nbsp;|| &nbsp;0&nbsp;|| &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;1&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|| &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;1&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
+|-
+| &nbsp;0&nbsp;|| &nbsp;1&nbsp;|| &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;0&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|| &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;1&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
+|-
+| &nbsp;1&nbsp;|| &nbsp;0&nbsp;|| &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;1&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|| &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;1&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
+|-
+| &nbsp;1&nbsp;|| &nbsp;1&nbsp;|| &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;1&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|| &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;1&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
+|}
-wyszczególnionych w preambule
-Teoria zbiorów, zwana również teorią mnogości, została stworzona
-około połowy XIX wieku, przez niemieckiego matematyka <u>'''Georg Cantor'''</u>.
-Teoria  mnogości to gałąź matematyki zajmująca się zbiorami --
-kolekcja obiektów. Skończone zbiory można definiować wypisując
-kolejno wszystkie ich elementy. <u>'''Georg Cantor'''</u> był pierwszą osobą która
-podjęła się przeniesienia na ścisły grunt matematyczny pojęcia
-zbioru nieskończonego. Według <u>'''Georg Cantor'''</u> zbiór może być dowolną
-kolekcją obiektów zwanych elementami. Według tego podejścia zbiór
-jest pojęciem podstawowym i niedefiniowalnym. Niestety podejście
-do teorii zbiorów w ten sposób rodzi paradoksy i dlatego teoria
-mnogości prezentowana w ten sposób jest często nazywana "naiwną"
-teorią mnogości.
-Teoria matematyczna nie może dopuszczać istnienia paradoksów i
-dlatego na początku XX wieku zmieniono podejście do teorii
-mnogości. Zaproponowana przez <u>'''Ernst Zermelo'''</u> i uzupełniony przez <u>'''Adolf Abraham Halevi Fraenkel'''</u> system aksjomatów wyklucza paradoksy które spowodowały
-że naiwna teoria zbiorów musiała zostać porzucona. Aksjomaty te
-nakładają pewne ograniczenia na konstrukcje zaproponowane przez
-<u>'''Georg Cantor'''</u>. W większości przypadków jednak intuicje związanej z
-naiwna teorią mnogości sprawdzają się również w aksjomatycznej
-teorii zbiorów. Zaprezentowane poniżej, skrótowe przedstawienie
-"naiwnej teorii mnogości" ma na celu wyrobienie intuicji
-niezbędnych przy dalszej pracy formalną wersją tych teorii.
-Aksjomatyczna teoria zbiorów zostanie przedstawiona w <u>'''Wykład
-.'''</u>
-W podejściu zaproponowanym przez <u>'''Georg Cantor'''</u> zbiory skończone można łatwo wskazywać poprzez wyliczenie ich elementów. Definiowanie zbiorów nieskończonych wymaga bardziej rozwiniętego języka, niemniej jednak, według <u>'''Georg Cantor'''</u>, każda kolekcja obiektów jest zbiorem. Podstawowym symbolem używanym przy definiowaniu i opisywaniu zbiorów jest
+<center><math>\left| x \right|\ = \left\{ \begin{array}{rll} x & \text{ gdy }, x\geq 0 \\ -x & \text{ w przeciwnym przypadku}.
+\end{array}</math></center>
-<center><math>
-\in
-</math></center>
+<center><math>w_3 &\rightarrow  bv_3v_2w_3v_1v_3v_3v_2\ |\
+aw_3v_1v_3v_3v_2\ |\ bv_3v_2v_1v_3v_3v_2 \\
+\begin{array}{lll} & & |\ av_1v_3v_3v_2\ |\ bv_3v_3v_2
+\end{array}</math></center>
-oznaczający, że dany byt jest "elementem" pewnego zbioru.
+oraz
-Napis
-<center> "Kraków" <math> \in </math> "zbiór wszystkich miast Polski" </center>
-ilustruje zastosowanie tego symbolu.
-Aby zdefiniować zbiór należy określić definitywny sposób na
+<center><math>w_3 &\rightarrow  bv_3v_2w_3v_1v_3v_3v_2w_3\ |\
-rozpoznawania czy dany byt jest elementem zbioru, czy nie.
+aw_3v_1v_3v_3v_2w_3\ |\ bv_3v_2v_1v_3v_3v_2w_3 \\
-Najczęściej używanym symbolem przy definiowaniu zbioru są nawiasy
+\begin{array}{lll} & & |\ av_1v_3v_3v_2w_3\ |\ bv_3v_3v_2w_3
-klamrowe. Definicja skończonego zbioru może być bardzo łatwa.
+\end{array}</math></center>
-Zbiór
+Ostatecznie, gramatyka w postaci Greibach ma postać:
-<center><math>
+<center><math> v_1 &\rightarrow  bv_3v_2w_3v_1v_3\ |\ aw_3v_1v_3\ |\ bv_3v_2v_1v_3\ |\ av_1v_3\ |\ bv_3 \\
-\{2,3, </math> Kraków <math> \}
+ v_2 &\rightarrow  bv_3v_2w_3v_1\ |\ aw_3v_1\ |\ bv_3v_2v_1\ |\ av_1\ |\ b \\
-</math></center>
+ v_3 &\rightarrow  bv_3v_2w_3\ |\ aw_3\ |\ bv_3v_2\ |\ a
+\\
+ w_3 &\rightarrow  bv_3v_2w_3v_1v_3v_3v_2\ |\
+aw_3v_1v_3v_3v_2\ |\ bv_3v_2v_1v_3v_3v_2 \\
+\begin{array}{lll} & & |\ av_1v_3v_3v_2\ |\ bv_3v_3v_2 bv_3v_2w_3v_1v_3v_3v_2w_3 \\
+ & & |\ aw_3v_1v_3v_3v_2w_3\ |\ bv_3v_2v_1v_3v_3v_2w_3\ \\
+ & & |\ av_1v_3v_3v_2w_3\ |\ bv_3v_3v_2w_3
+\end{array}</math></center>
-posiada trzy elementy. Liczba '''2''' jest elementem tego zbioru
-<math>2\in\{2,3, </math> Kraków <math> \}</math>, ale również
- Kraków <math> \in\{2,3, </math> Kraków <math> \}</math>.
-Dwa zbiory są sobie równe&nbsp;(takie same) jeśli posiadają dokładnie
-te same elementy. Jedynymi elementami zbioru <math>\{2,3\}</math> są liczby
-naturalne <math>2</math> i <math>3</math> -- ten sam fakt jest prawdziwy dla zbioru
-<math>\{2,2,3\}</math>, a więc
-<center><math>
-\{2,3\} = \{2,3,3\}.
-</math></center>
-Podobnie <math>\{2,3\}=\{3,2\}</math> i
-<center><math>
-\{2,3\}= </math> "zbiór liczb naturalnych ściśle pomiędzy <math>1</math> a
-<math>4</math>" <math> .
-</math></center>
-W definicji zbioru nie ma znaczenia kolejność w jakiej wymienione
+<center><math>\begin{array} {c|c|c|c|c|} Krok & dodane\quad do\quad S' & okreslenie\quad f' & dodane\quad do\quad T'\\
-są jego elementy, ani krotność w jakiej dany element pojawia się w
+\hline 0 & \{q_0\} &  & \emptyset\\
-zbiorze.
+\hline 1 & \{q_0,q_3\} & f'(\{q_0\},a)=\{q_0,q_3\} & \emptyset\\
+\hline  & \{q_0,q_1\} & f'(\{q_0\},b)=\{q_0,q_1\} & \\
+\hline 2 & \{q_0,q_3,q_4\} & f'(\{q_0,q_3\},a)=\{q_0,q_3,q_4\} & \{q_0,q_3,q_4\}\\
+\hline  &  & f'(\{q_0,q_3\},b)=\{q_0,q_1\} & \\
+\hline  &  & f'(\{q_0,q_1\},a)=\{q_0,q_3\} & \\
+\hline  & \{q_0,q_1,q_2\} & f'(\{q_0,q_1\},b)=\{q_0,q_1,q_2\} & \{q_0,q_1,q_2\}\\
+\hline 3 &  & f'(\{q_0,q_3,q_4\},a)=\{q_0,q_3,q_4\} & \\
+\hline  & \{q_0,q_1,q_4\} & f'(\{q_0,q_3,q_4\},b)=\{q_0,q_1,q_4\} & \{q_0,q_1,q_4\}\\
+\hline  & \{q_0,q_2,q_3\} & f'(\{q_0,q_1,q_2\},a)=\{q_0,q_2,q_3\} & \{q_0,q_2,q_3\}\\
+\hline  &  & f'(\{q_0,q_1,q_2\},b)=\{q_0,q_1,q_2\} & \\
+\hline 4 &  & f'(\{q_0,q_1,q_4\},a)=\{q_0,q_3,q_4\} & \\
+\hline  & \{q_0,q_1,q_2,q_4\}, & f'(\{q_0,q_1,q_4\},b)=\{q_0,q_1,q_2,q_4\} & \{q_0,q_1,q_2,q_4\}\\
+\hline  & \{q_0,q_2,q_3,q_4\} & f'(\{q_0,q_2,q_3\},a)=\{q_0,q_2,q_3,q_4\} & \{q_0,q_2,q_3,q_4\}\\
+\hline  &  & f'(\{q_0,q_2,q_3\},b)=\{q_0,q_1,q_2\} & \\
+\hline 5 &  & f'(\{q_0,q_1,q_2,q_4\},a)=\{q_0,q_2,q_3,q_4\} & \\
+\hline  &  & f'(\{q_0,q_1,q_2,q_4\},b)=\{q_0,q_1,q_2,q_4\} & \\
+\hline  &  & f'(\{q_0,q_2,q_3,q_4\},a)=\{q_0,q_2,q_3,q_4\} & \\
+\hline  &  & f'(\{q_0,q_2,q_3,q_4\},b)=\{q_0,q_1,q_2,q_4\} & \\
+\hline \end{array} </math></center>
-Zbiory można definiować na wiele sposobów. Najprostszym sposobem
-zdefiniowani zbioru jest wyliczenie jego elementów. Strategia ta
-zawodzi jednak w odniesieniu do zbiorów nieskończonych -- nie
-jesteśmy w stanie wypisać wszystkich liczb naturalnych. Zgodnie z
-postulatami Georg Cantor możemy przyjąć że istnieje zbiór wszystkich
-liczb naturalnych. Czasami, na określenie zbiorów nieskończonych
-używamy nieformalnego zapisu -- zbiór wszystkich liczb naturalnych
-może być zapisany jako
-<center><math>
-\{0,1,2,3,4,\ldots\}.
-</math></center>
-W podejściu zaproponowanym przez Georg Cantor równoważna definicja tego
-zbioru brzmi
-<center> "zbiór wszystkich liczb naturalnych" </center>
+<center><math>\begin{array} {c|c|c|c|c|} (s_0,\sharp)\mapsto (s_A,\sharp,0) & (s_0,0)\mapsto (r_0,\sharp,1) & (s_0,1)\mapsto (r_1,\sharp,1)\\
+\hline (r_0,\sharp)\mapsto (s_R,\sharp,0) & (r_0,0)\mapsto (r_0',0,1) & (r_0,1)\mapsto (r_0',1,1)\\
+\hline (r_0',\sharp)\mapsto (q_0,\sharp,-1) & (r_0',0)\mapsto (r_0',0,1) & (r_0',1)\mapsto (r_0',1,1)\\
+\hline  & (q_0,0)\mapsto (l,\sharp,-1) & (q_0,1)\mapsto (s_R,\sharp,-1)\\
+\hline (r_1,\sharp)\mapsto (s_R,\sharp,0) & (r_1,0)\mapsto (r_1',0,1) & (r_1,1)\mapsto (r_1',1,1)\\
+\hline (r_1',\sharp)\mapsto (q_1,\sharp,-1) & (r_1',0)\mapsto (r_1',0,1) & (r_1',1)\mapsto (r_1',1,1)\\
+\hline  & (q_1,0)\mapsto (s_R,\sharp,0) & (q_1,1)\mapsto (l,\sharp,-1)\\
+\hline (l,\sharp)\mapsto (s_0,\sharp,1) & (l,0)\mapsto (l,0,-1) & (l,1)\mapsto (l,1,-1)\\
+\hline (s_R,\sharp)\mapsto (s_R,\sharp,0) &  & \\
+\hline (s_A,\sharp)\mapsto (s_A,\sharp,0) &  & \\
+\hline \end{array} </math></center>
-Bardzo często tworzymy zbiory składające się z obiektów
-spełniających daną własność. Zbiór liczb parzystych możemy
-zdefiniować w sposób następujący
-<center><math>
-\{x\,|\, x</math> jest liczbą parzystą <math> \}.
-</math></center>
-Bardziej ogólnie
-<center><math>
-\{x\,|\, </math> warunek <math> \}
-</math></center>
-W skład powyżej zdefiniowanego zbioru wchodzą te elementy, które
-spełniają warunek występujący po znaku <math>\,|\,</math>. Żeby
-zakwalifikować element do powyższego zbioru wstawiamy go w miejsce
-<math>x</math> w warunku występującym po <math>\,|\,</math> i sprawdzamy czy jest on
-prawdziwy. Żeby pokazać, że
-<center><math>
-\in\{x\,|\, x</math> jest liczbą parzystą <math> \}.
-</math></center>
-musimy dowieść, że warunek "<math>2</math> jest liczbą parzystą" jest
+<center><math>\begin{array} {c|c|c|c|c|} (s_0,\sharp)\mapsto (s_R,\sharp,0) & (s_1,\diamondsuit)\mapsto(s1,\diamondsuit,1)\\
-prawdziwy.
+\hline (s_0,0)\mapsto(s_1,\clubsuit,1) & (s_1,0) \mapsto(s_2,\diamondsuit,1)\\
+\hline  & (s_1,\sharp)\mapsto(s_A,\sharp,0)\\
+\hline (s_2,\diamondsuit)\mapsto(s_2,\diamondsuit,1) & (s_3,0)\mapsto(s_2,\diamondsuit,1)\\
+\hline (s_2,\sharp)\mapsto(s_4,\sharp,-1) & (s_3,\diamondsuit)\mapsto(s_3,\diamondsuit,1)\\
+\hline (s_2,0)\mapsto(s_3,0,1) & (s_3,\sharp)\mapsto(s_R,\sharp,0)\\
+\hline (s_4,0)\mapsto(s_4,0,-1) & \\
+\hline (s_4,\diamondsuit)\mapsto(s_4,\diamondsuit,-1) & \\
+\hline (s_4,\clubsuit)\mapsto(s_2,\clubsuit,1) & \\
+\hline (s_A,\sharp)\mapsto(s_A,\sharp,0) & (s_R,\sharp)\mapsto(s_R,\sharp,0)\\
+\hline \end{array} </math></center>
-Pomiędzy zbiorem liczb parzystych a zbiorem wszystkich liczb
-naturalnych występuje oczywista zależność. Każda liczba parzysta
-jest liczbą naturalną, co, ujęte w języku zbiorów oznacza że każdy
-element zbioru liczb parzystych jest elementem zbioru liczb
-naturalnych. Zbiór liczb parzystych jest "podzbiorem"
-zbioru liczb naturalnych&nbsp;(a zbiór liczb naturalnych
-"nadzbiorem" zbioru liczb parzystych). Zapisujemy to w
-następujący sposób
-<center><math>
-\{x\,|\, x</math> jest liczbą parzystą <math> \}\subseteq </math> "zbiór
-liczb naturalnych" <math> .
-</math></center>
-Ogólniej, jeśli każdy element zbioru <math>A</math> jest elementem zbioru <math>B</math>
-mówimy że zbiór <math>A</math> jest podzbiorem zbioru <math>B</math> i piszemy
-<center><math>
-A\subseteq B.
-</math></center>
-W takim przypadku mówimy, że pomiędzy zbiorami <math>A</math> i <math>B</math> zachodzi
-inkluzja.
-W szczególności, dla dowolnego zbioru <math>A</math> zachodzi <math>A\subseteq A</math>.
-Wspomnieliśmy wcześniej, że dwa zbiory są sobie równe wtedy i
-tylko wtedy kiedy posiadają dokładnie takie same elementy. Fakt
-ten możemy zapisać formalnie w następujący sposób
-<center><math>
-A = B  </math>  wtedy i tylko wtedy, kiedy  <math>  A\subseteq B </math>  i  <math>
-B\subseteq A.
-</math></center>
-Często zależy nam na określeniu znaczącym, że jeden zbiór jest
+<center><math>\begin{array} {c|c|c|c|c|}  & s_0 & s_1 & s_2\\
-podzbiorem drugiego i że zbiory te nie są sobie równe. Używamy
+\hline \tau _{\mathcal{A}}(1) & s_0 & s_1 & s_2\\
-wtedy symbolu <math>\varsubsetneq</math> w następujący sposób
+\hline \tau _{\mathcal{A}}(a) & s_1 & s_2 & s_2\\
+\hline \tau _{\mathcal{A}}(b) & s_0 & s_0 & s_0\\
+\hline \tau _{\mathcal{A}}(a^{2}) & s_2 & s_2 & s_2\\
+\hline \tau _{\mathcal{A}}(ab) & s_0 & s_0 & s_2\\
+\hline \tau _{\mathcal{A}}(ba) & s_1 & s_1 & s_1\\
+\hline \tau _{\mathcal{A}}(b^{2}) & s_0 & s_0 & s_0\\
+\hline \tau _{\mathcal{A}}(aba) & s_1 & s_1 & s_2\\
+\hline ... & ... & ... & ...\\
+\hline \end{array} </math></center>
-<center><math>
-A\varsubsetneq B \textrm{ wtedy i tylko wtedy, kiedy } (
-A\subseteq B\textrm{ i nieprawda, że } A=B).
-</math></center>
-{cwicz}{1}
+<center><math>\begin{array} {c|c|c|c|c|} f & s_0 & s_1 & s_2 & s_3\\
-{hint}{0}
+\hline a & s_1 & s_2 & s_0 & s_2\\
-{Æwiczenie {section}.{cwicz}}
+\hline b & s_3 & s_2 & s_2 & s_2\\
+\hline \end{array} </math></center>
-Dla każdej pary zbiorów poniżej określ czy są sobie równe, oraz
-czy jeden z nich jest nadzbiorem drugiego
-# <math>\{2,3\}</math>, <math>\{x\,|\, x</math> dzieli liczbę <math>6 \}</math>
+{{algorytm|Minimalizuj2 - algorytm minimalizacji automatu
+wykorzystujący stabilizujący się ciąg relacji|algorytm minimalizacji automatu wykorzystujący stabilizujący się ciąg relacji|
-#  "zbiór liczb naturalnych" , <math>\{x\,|\, 2</math> dzieli <math>x^2 \}</math>
+Wejście: <math>\mathcal{A}=(S, A, f, s_0, T)</math> - automat taki, że <math>L=L(\mathcal{A})</math>.
+  Wyjście: automat minimalny <math>\mathcal{A}'=(S',A',f', s_0',
+T')</math> dla <math>\mathcal{A}</math>.
+  <math>\overline{\rho}_1\leftarrow\approx_{\mathcal{A}}</math>;
+  <math>i \leftarrow 1</math>;
+  '''repeat'''
+    <math>\slash \slash</math> oblicz <math>\overline{\rho}_i</math>: <math>s_1
+\overline{\rho}_i s_2 \Leftrightarrow (s_1 \overline{\rho}_{i-1}
+s_2) \wedge (\forall a \in A\ f(s_1, a) \overline{\rho}_{i-1}
+f(s_2,a))</math>;
+    <math>i \leftarrow i+1</math>;
+    '''empty'''<math>(\overline{\rho}_i)</math>
+    '''for''' '''each''' <math>(s_1,s_2)\in S\times S</math> '''do'''
+      flag<math>\leftarrow</math>'''true''';
+      '''for''' '''each''' <math>a\in A</math>
+        '''if''' '''not''' <math>f(s_1, a) \overline{\rho}_{i-1} f(s_2,a)</math> '''then'''
+          flag<math>\leftarrow</math>'''false''';
+        '''end''' '''if'''
+      '''end''' '''for'''
+      '''if''' flag<nowiki>=</nowiki>'''true''' '''and''' <math>s_1 \overline{\rho}_{i-1} s_2</math> '''then'''
+        <math>\overline{\rho}_{i} \leftarrow \overline{\rho}_{i} \cup \{(s_1,s_2)\}</math>;
+      '''end''' '''if'''
+    '''end''' '''for'''
+  '''until''' <math>\overline{\rho}_i = \overline{\rho}_{i-1}</math>
+  <math>S' \leftarrow S \slash \overline{\rho}_i</math>;
+  '''for''' '''each''' <math>[s]_{\overline{\rho}_i} \in S \slash \overline{\rho}_i</math> '''do'''
+    '''for''' '''each''' <math>a \in A</math> '''do'''
+      <math>f'([s]_{\overline{\rho}_i},a) \leftarrow
+[f(s,a)]_{\overline{\rho}_i}</math>;
+    '''end''' '''for'''
+  '''end''' '''for'''
+  <math>s_0' \leftarrow [s_0]_{\overline{\rho}_i}</math>;
+  <math>T' \leftarrow \{[t]_{\overline{\rho}_i}:\ t \in T\}</math>;
+  '''return''' <math>\mathcal{A}'=(S', A, f', s_0', T')</math>;
-# <math>\{x\,|\, x^2 =1\}</math>, <math>\{x\,|\, x^3=1\}</math>
+}}
-; Solution.
-: Rozwiązanie:
-:# Zarówno <math>2</math>, jak i <math>3</math> dzielą <math>6</math>, a więc
-<math>\{2,3\}\subseteq\{x\,|\, x</math> dzieli liczbę <math>6 \}</math>. Liczba <math>6</math>
-jest elementem lewego zbioru, a nie jest elementem prawego i dlatego
-zbiory te są od siebie różne. Odpowiedzią jest
-<math>\{2,3\}\varsubsetneq\{x\,|\, x</math> dzieli liczbę <math>6 \}</math>.
-:# Do zbioru liczb naturalnych należy <math>3</math>, które nie należy do zbioru
-<math>\{x\,|\, 2</math> dzieli <math>x^2 \}</math>&nbsp;(ponieważ <math>2</math> nie dzieli <math>9=3^2</math>).
-Równocześnie do prawego zbioru należy liczba <math>-2</math> która nie jest liczbą
-naturalną. Żaden z wymienionych tu zbiorów nie jest podzbiorem drugiego.
-:# Lewy zbiór to, oczywiście zbiór <math>\{-1,1\}</math>, a prawy to
-jednoelementowy zbiór <math>\{1\}</math>. W tym przypadku odpowiedzią jest
-<math>\{x\,|\, x^2 =1\}\varsupsetneq\{x\,|\, x^3=1\}</math>.
-{Koniec æwiczenia {section}.{cwicz}}
-Najczęstszymi operacjami wykonywanymi na zbiorach są operacje
-"sumy","przecięcia" i "różnicy". Sumą dwóch
-zbiorów <math>A</math> i <math>B</math> jest zbiór oznaczony przez <math>A\cup B</math> w skład
-którego wchodzą wszystkie element zbioru <math>A</math>, wszystkie elementy
-zbioru <math>B</math> i żadne elementy spoza tych zbiorów.
-<center><math>
-A\cup B = \{x\,|\, x\in A  </math>  lub  <math>  x\in B\}
-</math></center>
-{obra}{1}{Obrazek {section}.{obra}}standardowy obrazek ilustrujący unię zbiorów Podobnie
-definiujemy przecięcie zbiorów
-<center><math>
-A\cap B = \{x\,|\, x\in A  </math>  i  <math>  x\in B\}
-</math></center>
-{obra}{1}{Obrazek {section}.{obra}}standardowy obrazek ilustrujący przecięcie zbiorów oraz
-różnicę zbiorów
-<center><math>
-A\setminus B = \{x\,|\, x\in A </math>  i  <math>  x\notin B\}.
-</math></center>
-{obra}{1}{Obrazek {section}.{obra}}standardowy obrazek ilustrujący różnicę zbiorów
-{cwicz}{1}
-{hint}{0}
-{Æwiczenie {section}.{cwicz}}
-Dla następujących par zbiorów ustal zawieranie, lub równość
-# <math>A= </math> "zbiór liczb naturalnych" <math> \setminus\{x\,|\,  </math> liczba nieparzysta, większa niż 2 dzieli <math>x \}</math> i drugi zbiór <math>B=\{2^n\,|\, </math> gdzie <math>n</math> jest liczbą naturalną <math> \}</math>,
-# <math>A=\{x\,|\,  </math> liczba 2 dzieli <math>x \}\cup\{x\,|\,  </math> liczba 3 dzieli <math>x \}</math> i zbiór
-<math>B=\{x\,|\,  </math> liczba 6 dzieli <math>x \}</math>.
-; Solution.
-: Rozwiązanie:
-:# Każda liczba postaci <math>2^n</math> jest liczbą naturalną
-niepodzielną przez żadną liczbę nieparzystą większą niż
-<math>2</math>, a więc <math>B\subseteq A</math>. Każda liczba naturalna, która
-nie dzieli się przez żadną liczbę nieparzystą posiada tylko
-jeden dzielnik pierwszy <math>2</math>. W związku z tym każda z liczb
-w <math>A</math> występuje również w <math>B</math>. W związku z tym <math>A=B</math>.
-:# Każda liczba która jest podzielna przez <math>6</math> dzieli się
-również przez <math>2</math> co dowodzi, że <math>B\subseteq A</math>. Zawieranie w
-drugą stronę nie zachodzi ponieważ liczba <math>9\in A</math> i <math>9\notin
-B</math>.
-{Koniec æwiczenia {section}.{cwicz}}
-Dla dowolnego zbioru <math>A</math> zachodzi <math>A\cup A = A</math> i <math>A\cap A = A</math>.
-Zbiór który otrzymujemy jako wynik operacji <math>A\setminus A</math> jest
-"zbiorem pustym". Na mocy definicji różnicy zbiorów
-elementami zbioru <math>A\setminus A</math> są wyłącznie te elementy <math>A</math>,
-które nie należą do <math>A</math>. Takie elementy nie istnieją -- żaden
-element ze zbioru <math>A</math> nie należy do <math>A\setminus A</math> i żaden element
-spoza <math>A</math> nie należy do tego zbioru. Zbiór pusty jest oznaczany
-przez <math>\emptyset</math>. Odejmowanie zbiorów od samych siebie nie jest
-jedynym sposobem na otrzymanie zbioru pustego.
-<center><math>
-\{1,2,2006\}\setminus </math> "zbiór liczb naturalnych" <math> = </math> "zbiór
-psów" <math> \setminus </math> "zbiór wszystkich zwierząt" </center>
-Zbiór po lewej stronie nierówności jest równy zbiorowi po prawej
-stronie nierówności. Każdy element zbioru po prawej stronie jest
-również elementem zbioru po lewej stronie nierówności i vice versa
-dlatego, że żaden z tych zbiorów nie posiada elementów.
-Niestety, podejście zaproponowane przez Georg Cantor i uściślone przez
-Friedrich Frege posiada błędy. Jedną z pierwszych osób które zwróciły uwagę
-na niedociągnięcia tej teorii jest Bertrandt Russell. Zgodnie z zasadami
-zaproponowanymi przez Georg Cantor można zdefiniować dowolny zbiór.
-Zdefiniujmy więc zbiór
-<center><math>
-Z = \{A\,|\, A\notin A\}.
-</math></center>
-Zbiór <math>Z</math> składa się ze zbiorów, które nie są swoimi własnymi
-elementami. Paradoks zaproponowany przez Bertrandt Russell polega na tym,
-że pytanie czy <math>Z</math> jest swoim własnym elementem prowadzi do
-sprzeczności. Jeśli <math>Z\in Z</math> to, zgodnie z definicją zboru <math>Z</math>
-otrzymujemy <math>Z\notin Z</math> co jest sprzecznością z założeniem. Jeśli
-<math>Z\notin Z</math>, to <math>Z</math> spełnia warunek na przynależność do <math>Z</math> i w
-związku z tym <math>Z\in Z</math> co jest kolejną sprzecznością. Definicja
-zbioru zaproponowana przez Georg Cantor prowadzi do powstania
-logicznych paradoksów. Okazuje się że pytanie co jest zbiorem jest
-trudniejsze niż wydawało się matematykom końca XIX wieku.
-W dalszej części wykładu przedstawimy właściwe podejście do teorii
-mnogości. Podejście to jest oparte o część logiki zwaną rachunkiem
-predykatów. Podejście to zostało zaproponowane przez Ernst Zermelo na
-początku XX wieku i ma na celu dostarczenie spójnej teorii zbiorów
-o mocy podobnej to naiwnej teorii, przy równoczesnym uniknięciu
-paradoksów. Aksjomatyczna teoria mocy definiuje bardzo dokładnie
-które kolekcje obiektów są zbiorami. W szczególności paradoks
-zaproponowany przez Bertrandt Russell nie pojawia się w aksjomatycznej
-teorii zbiorów, ponieważ zbiór zdefiniowany powyżej jako <math>Z</math> w
-niej nie istnieje.
-=="Naiwna" indukcja==
-Zasada indukcji matematycznej jest o prawie trzysta lat starsza
-niż teoria mnogości. Pierwszy dowód indukcyjny pojawił się w pracy
-Francesco Maurolico w 1575 roku. W pracy tej autor wykazał, że suma <math>n</math>
-pierwszych liczb nieparzystych równa się <math>n^2</math>.
-Aby zastosować zasadę indukcji matematycznej należy wykazać dwa
-fakty:
-* hipoteza jest prawdziwa dla <math>n=1</math>;
-* jeśli hipoteza jest prawdziwa dla <math>n</math> to jest również prawdziwa dla
-<math>n+1</math>.
-Drugi z powyższych punktów musi być prawdą dla wszystkich <math>n\geq
-</math>. Jeśli oba fakty są prawdą to hipoteza jest prawdziwa dla
-wszystkich liczb naturalnych większych od <math>1</math>. Rozumowanie które
-stoi za tym wnioskiem wygląda następująco:
-# hipoteza jest prawdziwa dla <math>n=1</math> na podstawie podstawy indukcji,
-# hipoteza jest prawdziwa dla <math>n=2</math>, ponieważ jest prawdziwa dla <math>1</math>
-i po zastosowaniu kroku indukcyjnego również dla <math>2</math>,
-# hipoteza jest prawdziwa dla <math>n=3</math>; w poprzednim punkcie pokazaliśmy,
-że jest prawdziwa dla <math>2</math> i na podstawie kroku indukcyjnego jest również
-prawdziwa <math>3</math>
-# i tak dalej.
-Zasadę indukcji matematycznej można porównać do domina. Aby mieć
-pewność że przewrócone zostaną wszystkie klocki wystarczy wykazać,
-że przewrócony zostanie pierwszy klocek i że każdy klocek pociąga
-za sobą następny. {obra}{1}{Obrazek {section}.{obra}}nieskończone domino ponumerowanych
-liczbami naturalnymi klocków w trakcie przewracania
-Dowód indukcyjny przedstawiony przez Francesco Maurolico pokazuje, że suma
-pierwszych <math>n</math> liczb nieparzystych jest równa <math>n^2</math>.
-* Jeśli <math>n=1</math> to pierwsza liczba nieparzysta <math>1</math> jest równa <math>1^2</math>.
-* Jeśli hipoteza jest prawdą dla <math>n</math>, to znaczy że suma pierwszych <math>n</math>
-liczb nieparzystych równa się <math>n^2</math>. Bardziej formalnie
-<center><math>
-+3+\dotsb+(2n-1) = n^2.
-</math></center>
-tak więc suma pierwszych <math>n+1</math> liczb nieparzystych
-<math>1+3+\dotsb+(2n-1)+(2(n+1)-1)</math>, przy użyciu założenia powyżej może
-być zapisana jako
-<center><math>
-+3+\dotsb+(2n-1)+(2(n+1)-1) = n^2 +(2(n+1)-1)= n^2+2n+1=
-{(n+1)}^2.
-</math></center>
-Krok indukcyjny został dowiedziony.
-{cwicz}{1}
-{hint}{0}
-{Æwiczenie {section}.{cwicz}}
-Wykaż, że suma pierwszych <math>n</math> liczb naturalnych jest równa
-<math>\frac{1}{2}n(n+1)</math>.
-; Solution.
-: Aby udowodnić wzór na sumę <math>n</math>
-pierwszych liczb naturalnych posłużymy się indukcją.
-:* Dla <math>n=1</math> mamy <math>\frac{1}{2}\cdot 1\cdot 2 = 1</math>.
-:* Zakładamy, że wzór jest prawdziwy dla <math>n</math>. W związku z tym do sumy
-<center><math>
-+2+\dotsb+n+(n+1) =
-</math></center>
-stosujemy założenie indukcyjne
-<center><math>
-(1+2+\dotsb+n ) +(n+1) = \frac{1}{2}n(n+1) + (n+1) =
-</math></center>
-i po paru prostych przekształceniach otrzymujemy
-<center><math>
-= \frac{1}{2}n(n+1) +\frac{1}{2}2(n+1) = \frac{1}{2}(n+1)(n+2)
-</math></center>
-co dowodzi kroku indukcyjnego.
-Na zasadzie indukcji matematycznej dowiedliśmy wzór na sumę <math>n</math>
-pierwszych liczb naturalnych.
-{Koniec æwiczenia {section}.{cwicz}}
-{cwicz}{1}
-{hint}{0}
-{Æwiczenie {section}.{cwicz}}
-Wykaż, że suma kwadratów pierwszych <math>n</math> liczb
-naturalnych jest równa <math>\frac{1}{6}n(n+1)(2n+1)</math>.
-; Solution.
-: Aby
-wykazać prawdziwość wzoru powyżej postępujemy jak
-w poprzednim zadaniu.
-:* Dla <math>n=1</math> mamy <math>\frac{1}{6}\cdot 1\cdot 2\cdot 3 = 1</math> co dowodzi
-podstawy indukcji.
-:* Zakładamy że wzór jest prawdziwy dla <math>n</math> to jest, że
-<center><math>
-^2+2^2+\dotsb+n^2 = \frac{1}{6}n(n+1)(2n+1).
-</math></center>
-Korzystając z tego faktu przekształcamy
-<center><math>
-^2+2^2+\dotsb+n^2 + {(n+1)}^2= \frac{1}{6}n(n+1)(2n+1) +
-{(n+1)}^2 =
-</math></center>
-i dalej do
-<center><math>
-\frac{1}{6}(n+1)\left(n(2n+1)+6(n+1)\right)=\frac{1}{6}(n+1)(2n^2+7n+6)=
-\frac{1}{6}(n+1)(n+2)(2(n+1)+1)
-</math></center>
-co dowodzi kroku indukcyjnego.
-Podobnie jak w poprzednim przykładzie zasada indukcji
-matematycznej gwarantuje, że wzór jest prawdziwy dla wszystkich
-liczb naturalnych.
-{Koniec æwiczenia {section}.{cwicz}}
-{cwicz}{1}
-{hint}{0}
-{Æwiczenie {section}.{cwicz}}
-Wykaż, że dla <math>n\geq 1</math> zachodzi <math>4|3^{2n-1}+1</math>.
-; Solution.
-: Jak
-poprzednio stosujemy zasadę indukcji matematycznej.
-:* Dla <math>n=1</math> mamy <math>3^{2n-1} + 1 = 3^1 +1 = 4</math> jest podzielne przez <math>4</math>.
-:* Zakładamy że podzielność zachodzi dla <math>n</math>.
-Pokażemy że <math>3^{2(n+1)-1}+1</math> jest podzielne przez <math>4</math>. Przekształcamy
-<center><math>
-^{2(n+1)-1}+1 = 3^{2n-1+2} + 1 = 9\cdot 3^{2n-1} + 1=
-</math></center>
-wprowadzamy sztuczny czynnik
-<center><math>
-=9\cdot (3^{2n-1} +1 -1) + 1 = 9\cdot (3^{2n-1} +1 -1) + 1 =
-\cdot (3^{2n-1} +1) -9 + 1 = 9\cdot (3^{2n-1} +1) -8.
-</math></center>
-Zarówno <math>(3^{2n+1} +1)</math>&nbsp;(na mocy założenia indukcyjnego) jak i <math>8</math>
-są podzielne przez <math>4</math>, a wiec ich różnica również. W ten sposób
-udowodniliśmy krok indukcyjny.
-{Koniec æwiczenia {section}.{cwicz}}
-Często bardzo niepraktyczne jest używanie indukcji w jej
-podstawowej formie. Używa się wtedy indukcji, która w pierwszym
-kroku nie zaczyna się od <math>n=1</math>, ale <math>n=0</math>, <math>n=2</math> lub dowolnej
-innej liczby naturalnej. W takim przypadku drugi krok indukcyjny
-nie musi działać dla wszystkich <math>n</math> a wystarczy by działał dla <math>n</math>
-większych lub równych od liczby którą wybraliśmy w pierwszym
-kroku. Końcowy dowód indukcyjny pokaże, że dana hipoteza nie jest
-prawdziwa dla wszystkich liczb naturalnych, a jedynie dla liczb
-większych od tej wybranej na pierwszy krok indukcyjny.
-Jako przykład pokażemy, że <math>n!>2^n</math>. Po pierwsze nierówność ta nie
-zachodzi dla <math>1,2,3</math>, więc nie można rozpocząć kroku indukcyjnego
-od <math>n=1</math>. Indukcja będzie wyglądać następująco.
-* Hipoteza jest prawdą dla <math>n=4</math>, ponieważ <math>4!=24>16=2^4</math>.
-* Jeśli hipoteza jest prawdą dla <math>n</math> i jeśli <math>n\geq 4</math> to
-<center><math>
-(n+1)!= n!\cdot (n+1)>2^n\cdot(n+1)>2^{n+1}
-</math></center>
-gdzie pierwsza nierówność pochodzi z założenia indukcyjnego, a
-druga z faktu, że dowodzimy krok indukcyjny dla liczb większych
-niż <math>4</math>.
-{cwicz}{1}
-{hint}{0}
-{Æwiczenie {section}.{cwicz}}
-W tym ćwiczeniu dowodzimy wariant nierówności Bernoulliego. Dla dowolnego <math>x</math> takiego, że <math>x> -1</math> i <math>x\neq 0</math> i dla dowolnego <math>n\geq 2</math> zachodzi <math>{(1+x)}^n> 1+nx</math>.
-; Solution.
-: Rozwiązanie:
-:* Nierówność ostra nie jest prawdą dla <math>n=0</math>, ani dla
-<math>n=1</math>. Krok indukcyjny zaczniemy od <math>2</math>. Wtedy
-<math>{(1+x)}^2=1+2x+x^2>1+2x</math>, gdzie ostatnia nierówność bierze
-się z faktu, że <math>x\neq 0</math>.
-:* Zakładamy teraz, że nierówność jest prawdziwa dla <math>n</math>, czyli, że dla dowolnego <math>x</math> takiego, że <math>0\neq x> -1</math> mamy
-<center><math>
-{(1+x)}^n> 1+nx.
-</math></center>
-Przekształcając nierówność dla <math>n+1</math> otrzymujemy
-<center><math>
-{(1+x)}^{(n+1)}={(1+x)}^n(1+x)>(1+nx)(1+x)=1+(n+1)x +x^2\geq
-+(n+1)x,
-</math></center>
-gdzie otrzymujemy ostrą nierówność dzięki założeniu indukcyjnemu i
-faktowi, że <math>x\neq -1</math>. W ten sposób krok indukcyjny został
-udowodniony.
-{Koniec æwiczenia {section}.{cwicz}}
-{cwicz}{1}
-{hint}{0}
-{Æwiczenie {section}.{cwicz}}
-Liczby Fibonacciego zdefiniowane są następująco
-<center><math>
-f_1=1, f_2=1 </math>  oraz  <math>  f_i=f_{i-2}+f_{i-1}  </math>  dla  <math>  i>3.
-</math></center>
-Udowodnij, że dla dowolnego <math>n\geq 2</math> liczby <math>f_n</math> i <math>f_{n-1}</math> są
-względnie pierwsze.
-; Solution.
-: Dowód przez indukcję matematyczną
-:* Twierdzenie jest prawdą dla <math>n=2</math> ponieważ <math>f_2</math> i <math>f_1</math> są
-względnie pierwsze.
-:* Zakładamy że twierdzenie jest prawdą dla <math>n</math>. Rozpatrzmy wspólny
-dzielnik liczb <math>f_{n+1}</math> i <math>f_n</math> i oznaczmy go przez <math>k</math>. Jeśli <math>k</math>
-dzieli <math>f_{n+1}</math> i równocześnie <math>f_n</math> to <math>k | f_{n+1}-f_n</math>. Korzystając z
-definicji liczb Fibbonaciego otrzymujemy
-<math>f_{n+1}-f_n=f_n+f_{n-1}-f_n=f_{n-1}</math>.
-W związku z czym <math>k</math> jest wspólnym dzielnikiem liczb <math>f_n</math> i <math>f_{n-1}</math>,
-więc na mocy założenia indukcyjnego mówiącego, że liczby te są względnie
-pierwsze, jest równy <math>1</math>. Pokazaliśmy,
-że każdy wspólny dzielnik <math>f_{n+1}</math> i <math>f_n</math> jest równy <math>1</math>, a więc liczby
-te są względnie pierwsze. Krok indukcyjny został pokazany.
-{Koniec æwiczenia {section}.{cwicz}}
-Kolejnym uogólnieniem zasady indukcji matematycznej jest indukcja,
-w której w drugi kroku indukcyjnym zakładamy, że hipoteza jest
-prawdą dla wszystkich liczb mniejszych niż <math>n</math> i dowodzimy, że
-jest również prawdziwa dla <math>n+1</math>.
-Jako przykład udowodnimy, że każda liczba naturalna większa niż
-<math>2</math> jest produktem jednej, lub więcej liczb pierwszych.
-* Hipoteza jest prawdą dla <math>n=2</math> ponieważ <math>2</math> jest liczbą pierwszą.
-* Zakładamy że hipoteza jest prawdziwa dla liczb od <math>2</math> do
-<math>n</math>. Weźmy liczbę <math>n+1</math>, jeśli <math>n+1</math> jest liczbą pierwszą, to
-hipoteza jest udowodniona. Jeśli <math>n+1</math> nie jest liczbą
-pierwszą, to <math>n+1=k\cdot l</math> gdzie <math>2\leq k,l\leq n</math>. Założenie
-indukcyjne gwarantuje, że
-<center><math>
-k=p_1\cdot p_2\cdot\dotsb\cdot p_i </math>  i  <math> l=q_1\cdot
-q_2\cdot\dotsb\cdot q_j
-</math></center>
-gdzie <math>p_1,\dotsc,p_i,q_1,\dotsc,q_j</math> są liczbami pierwszymi. W
-związku z tym
-<center><math>
-n+1=p_1\cdot p_2\cdot\dotsb\cdot p_i\cdot q_1\cdot
-q_2\cdot\dotsb\cdot q_j
-</math></center>
-i krok indukcyjny jest udowodniony.
-{cwicz}{1}
+{| border=1
-{hint}{0}
+|+ <span style="font-variant:small-caps">Uzupelnij tytul</span>
-{Æwiczenie {section}.{cwicz}}
+|-
-Udowodnij, że każda liczba naturalna większa niż
+|
-<math>1</math> może być przedstawiona jako suma liczb Fibonacciego tak, że
+||
-żadna liczba nie występuje w tej sumie więcej niż raz.
+<math>s_{0} </math>  ||
-; Solution.
+<math>s_{1} </math>  ||
-: Przedstawimy dowód przez indukcję.
+<math>s_{2} </math>
+|-
+|
-:* Dla <math>n=1</math> mamy <math>f_2=1</math>.
+<math>\tau _{\mathcal{A}}(1) </math>  ||
+<math>s_{0} </math>  ||
+<math>s_{1} </math>  ||
+<math>s_{2} </math>
+|-
+|
+<math>\tau _{\mathcal{A}}(a) </math>  ||
+<math>s_{1} </math>  ||
+<math>s_{2} </math>  ||
+<math>s_{2} </math>
+|-
+|
+<math>\tau _{\mathcal{A}}(b) </math>  ||
+<math>s_{0} </math>  ||
+<math>s_{0} </math>  ||
+<math>s_{0} </math>
+|-
+|
+<math>\tau _{\mathcal{A}}(a^{2}) </math>  ||
+<math>s_{2} </math>  ||
+<math>s_{2} </math>  ||
+<math>s_{2} </math>
+|-
+|
+<math>\tau _{\mathcal{A}}(ab) </math>  ||
+<math>s_{0} </math>  ||
+<math>s_{0} </math>  ||
+<math>s_{2} </math>
+|-
+|
+<math>\tau _{\mathcal{A}}(ba) </math>  ||
+<math>s_{1} </math>  ||
+<math>s_{1} </math>  ||
+<math>s_{1} </math>
+|-
+|
+<math>\tau _{\mathcal{A}}(b^{2}) </math>  ||
+<math>s_{0} </math>  ||
+<math>s_{0} </math>  ||
+<math>s_{0} </math>
+|-
+|
+<math>\tau _{\mathcal{A}}(aba) </math>  ||
+<math>s_{1} </math>  ||
+<math>s_{1} </math>  ||
+<math>s_{2} </math>
+|-
+|
+... ||
+... ||
+... ||
+...
+|-
+|
-:* Zakładamy że każda liczba mniejsza lub równa <math>n</math> może być
+|}
-przedstawiona w sposób opisany powyżej. Jeśli liczba <math>n+1</math> jest
-liczbą Fibonacciego to krok indukcyjny jest już dowiedziony, jeśli
-nie to znajdujemy największą liczbę Fibonacciego mniejszą od <math>n+1</math>
--- oznaczmy tą liczbę <math>f_k</math>. Liczba <math>n+1-f_k</math> jest mniejsza niż
-<math>n</math> więc, na mocy założenia indukcyjnego, posiada reprezentację
-jako suma liczb Fibonacciego
-<center><math>
-n+1-f_k=f_{l_0}+\dotsb+f_{l_i}
-</math></center>
-tak, że każda z liczb w tej reprezentacji występuje co najwyżej
+<math>
-raz. Oczywiście
+\begin{array}{lll}
+\text{b) } \lim_{x\rightarrow 2^+} (x-2)e^{\frac{1}{x-2}}&=&\lim_{x\rightarrow
+^+} \frac{e^{\frac{1}{x-2}}}{(x-2)^{-1}}\begin{array} {c}\left[\frac{\infty}{\infty}\right]\\=\\H\end{array}
+\lim_{x\rightarrow 2^+}
+\frac{-(x-2)^{-2}e^{\frac{1}{x-2}}}{-(x-2)^{-2}}=\\
+&=&\lim_{x\rightarrow 2^+} e^{\frac{1}{x-2}}=+\infty;
+\end{array}
+</math><br>
-<center><math>
-n+1 = f_k+f_{l_0}+\dotsb+f_{l_i}
-</math></center>
-i pozostaje wykazać, że <math>f_k</math> nie występuje pośród liczb
+  alalalalaa
-<math>f_{l_0},\dotsc,f_{l_i}</math>. Skoro <math>f_k</math> było największą liczbą
-Fibonacciego mniejszą niż <math>n+1</math> to <math>f_{k+1}>n+1</math> a więc
-<math>f_{k-1}=f_{k+1}-f_k>n+1-f_k</math>. W związku z tym liczby
-<math>f_{l_0},\dotsc,f_{l_i}</math> są silnie mniejsze niż <math>f_{k-1}</math> i żadna
-z nich nie może być równa <math>f_k</math>. W ten sposób krok indukcyjny
-został dowiedziony.
-{Koniec æwiczenia {section}.{cwicz}}
+ alala
-{cwicz}{1}
+{| border="1" cellspacing="0"
-{hint}{0}
+! !! Złożoność czasowa !! Złożoność pamięciowa
-{Æwiczenie {section}.{cwicz}}
+ |-
+ ! Maszyna dodająca || <math>f(0) = 1</math><br/><math>f(1) = 3</math><br/><math>f(n) = n+3; n\geq2</math> ||   <math>f(0) = 2</math><br/><math>f(1) = 3</math><br/><math>f(n) = n+1; n\geq2</math>
+ |-
+ ! Maszyna rozpoznająca <math>ww^\leftarrow</math>         || <math>f(n) = 6 + 8 + \ldots + (n+3) + 2 ; n=2k+1</math><br/><math>f(n) = 5 + 7 + \ldots + (n+3) + 1 ; n=2k</math> ||   <math>f(n) = n+1</math>
+|}
-Znajdź błąd w poniższym dowodzie indukcyjnym. Dowodzimy
-indukcyjnie twierdzenia, że wszystkie liczby są parzyste.
-* Twierdzenie jest prawdą dla <math>n=0</math> ponieważ <math>0</math> jest liczbą parzystą.
+{| border="1"
+! <math>\Rightarrow</math>!! 0!! 1!! ...!! ...
+|-
+| Cell1|| Cell2
+|}
-* Zakładamy, że twierdzenie jest prawdą dla wszystkich liczb
-mniejszych lub równych <math>n</math>. Liczba <math>n+1</math> jest niewątpliwie sumą
-dwóch liczb silnie mniejszych od siebie <math>n+1=k+l</math>. Liczby <math>k</math> i
-<math>l</math>, na podstawie założenia indukcyjnego, są parzyste, zatem ich
-suma równa <math>n+1</math> jest parzysta. Krok indukcyjny został
-dowiedziony.
-Na zasadzie indukcji matematycznej wszystkie liczby są parzyste.
+{| border="1" cellspacing="0"
+! <math>\Rightarrow</math>!! 0!! 1!!
+|-
+| &nbsp;0&nbsp;|| &nbsp;1&nbsp;|| &nbsp;1&nbsp;
+|-
+| &nbsp;1&nbsp;|| &nbsp;0&nbsp;|| &nbsp;1&nbsp;
+|}
-; Solution.
-: Dowód indukcyjny jest niepoprawny. Krok indukcyjny nie
-działa dla wszystkich <math>n</math> większych lub równych od <math>0</math> -- które
-jest podstawą indukcji. Jeśli <math>n=0</math>, to <math>n+1=1</math> i nie jesteśmy w
-stanie rozbić liczby <math>1</math> na sumę dwóch liczb istotnie mniejszych
-od niej samej.
-{Koniec æwiczenia {section}.{cwicz}}
+{| border="1" cellspacing="0"
+! <math>p</math>!! <math>\neg p</math>
+|-
+| &nbsp;0&nbsp;|| &nbsp;1&nbsp;||
+|-
+| &nbsp;1&nbsp;|| &nbsp;0&nbsp;||
+|}
-{cwicz}{1}
-{hint}{0}
-{Æwiczenie {section}.{cwicz}}
-W trójwymiarowej przestrzeni znajduje się <math>n</math> punktów. Ilość
+{| border="1" cellspacing="0"
-punktów w rzutowaniu na płaszczyznę <math>O_x, O_y</math> oznaczamy przez
+! <math>\wedge</math>!! 0!! 1!!
-<math>n_{xy}</math>. Podobnie ilość punktów w rzutowaniu na <math>O_x, O_z</math> przez
+|-
-<math>n_{xz}</math> i ilość punktów w rzutowaniu na <math>O_y, O_z</math> przez
+| &nbsp;0&nbsp;|| &nbsp;0&nbsp;|| &nbsp;0&nbsp;
-<math>n_{yz}</math>. Wykaż, że dla dowolnego rozkładu punktów w przestrzeni
+|-
-zachodzi nierówność
+| &nbsp;1&nbsp;|| &nbsp;0&nbsp;|| &nbsp;1&nbsp;
+|}
-<center><math>
+{| border="1" cellspacing="0"
-n^2\leq n_{xy}n_{xz}n_{yz}.
+! <math>\vee</math>!! 0!! 1!!
-</math></center>
+|-
+| &nbsp;0&nbsp;|| &nbsp;0&nbsp;|| &nbsp;1&nbsp;
+|-
+| &nbsp;1&nbsp;|| &nbsp;1&nbsp;|| &nbsp;1&nbsp;
+|}
-{hint}{1}
+{| border="1"
-; Hint .
+! <math>\text{p}</math>!! <math>\text{q}</math>!! <math>\text{p} \wedge \text{q}</math>!! <math>\neg( p \wedge q)</math>!! <math>\neg p</math>!! <math>\neg q</math>!! <math>\neg p \vee \neg q</math>
-: Użyj nierówności pomiędzy średnią geometryczną, a
+|-
-średnią arytmetyczną
+| &nbsp;0&nbsp;|| &nbsp;0&nbsp;|| 0|| 1|| 1|| 1|| 1
+|-
+| &nbsp;0&nbsp;|| &nbsp;1&nbsp;|| 0|| 1|| 1|| 0|| 1
+|-
+| &nbsp;1&nbsp;|| &nbsp;0&nbsp;|| 0|| 1|| 0|| 1|| 1
+|-
+| &nbsp;1&nbsp;|| &nbsp;1&nbsp;|| 1|| 0|| 0|| 0|| 0
+|}
-<center><math>
-\frac{1}{2}(a+b)\geq \sqrt{ab}.
-</math></center>
-{hint}{1}
+{| border="1"
-; Hint .
+! <math>\text{p}</math>!! <math>\text{q}</math>!! <math>\text{r}</math>!!<math>(\text{p} \wedge \text{q})</math>!! <math>( p \wedge r)</math>!! <math>( q \wedge \neg r)</math>!! <math>(p \wedge r) \vee (q \wedge \neg r)</math>!! <math>(p \wedge q) \Rightarrow ((p \wedge r) \vee (q \wedge \neg r))</math>
-: Podziel punkty na dwie grupy płaszczyzną równoległą do
+|-
-którejś z płaszczyzn <math>O_x, O_y</math>, <math>O_x, O_z</math> lub <math>O_y, O_z</math>.
+| 0|| 0|| 0|| 0|| 0|| 0|| 0|| 1
-; Solution.
+|-
-: Dowiedziemy nierówność przy użyciu indukcji.
+| 0|| 0|| 1|| 0|| 0|| 0|| 0|| 1
+|-
+| 0|| 1|| 0|| 0|| 0|| 1|| 1|| 1
+|-
+| 0|| 1|| 1|| 0|| 0|| 0|| 0|| 1
+|-
+| 1|| 0|| 0|| 0|| 0|| 0|| 0|| 1
+|-
+| 1|| 0|| 1|| 0|| 1|| 0|| 1|| 1
+|-
+| 1|| 1|| 0|| 1|| 0|| 1|| 1|| 1
+|-
+| 1|| 1|| 1|| 1|| 1|| 0|| 1|| 1
+|}
-:* Jeśli <math>n=1</math> to <math>n_{xy}=n_{xz}=n_{yz}=1</math> i nierówność jest prawdziwa.
-:* Zakładamy, że nierówność jest prawdziwa dla wszystkich liczb
+{| border="1"
-naturalnych&nbsp;(dla dowolnego układu punktów) mniejszych niż <math>n+1</math>.
+! Numer<br/>funkcji!! <math>p=0</math><br/><math>q=0</math>!! <math>p=0</math><br/><math>{q=1}</math>!!<math>p=1</math><br/><math>q=0</math>!! <math>p=1</math><br/><math>{q=1}</math>!! &nbsp;!! &nbsp;
-Rozpoczynamy z dowolnym układem <math>n+1</math> punktów w przestrzeni.
+|-
-Ponieważ <math>n+1>1</math> wiemy, że istnieje płaszczyzna równoległa do
+| 0|| 0|| 0|| 0|| 0|| &nbsp;|| <math>F</math>
-którejś z płaszczyzn <math>O_x, O_y</math>, <math>O_x, O_z</math> lub <math>O_y, O_z</math> i
+|-
-dzieląca <math>n+1</math> punktów na dwie niepuste części posiadające
+| 1|| 0|| 0|| 0|| 1|| &nbsp;|| <math>\wedge</math>
-odpowiednio <math>n'</math> i <math>n''</math> punktów. Ponieważ nasz układ jest bardzo
+|-
-symetryczny możemy założyć że nasza płaszczyzna jest równoległa do
+| 2|| 0|| 0|| 1|| 0|| &nbsp;|| <math>\neg (p \Rightarrow q)</math>
-płaszczyzny <math>O_x, O_y</math>. Stosując założenie indukcyjne do każdej z
+|-
-części otrzymujemy
+| 3|| 0|| 0|| 1|| 1|| &nbsp;|| <math>\text{p}</math>
+|-
+| 4|| 0|| 1|| 0|| 0|| &nbsp;|| <math>\neg (q \Rightarrow p)</math>
+|-
+| 5|| 0|| 1|| 0|| 1|| &nbsp;|| <math>\text{q}</math>
+|-
+| 6|| 0|| 1|| 1|| 0|| &nbsp;|| <math>XOR</math>
+|-
+| 7|| 0|| 1|| 1|| 1|| &nbsp;|| <math>\vee</math>
+|-
+| 8|| 1|| 0|| 0|| 0|| &nbsp;|| <math>NOR</math>
+|-
+| 9|| 1|| 0|| 0|| 1|| &nbsp;|| <math>\Leftrightarrow</math>
+|-
+| 10|| 1|| 0|| 1|| 0|| &nbsp;|| <math>\neg q</math>
+|-
+| 11|| 1|| 0|| 1|| 1|| &nbsp;|| <math>q \Rightarrow p</math>
+|-
+| 12|| 1|| 1|| 0|| 0|| &nbsp;|| <math>\neg p</math>
+|-
+| 13|| 1|| 1|| 0|| 1|| &nbsp;|| <math>p \Rightarrow q</math>
+|-
+| 14|| 1|| 1|| 1|| 0|| &nbsp;|| <math>NAND</math>
+|-
+| 15|| 1|| 1|| 1|| 1|| &nbsp;|| <math>T</math>
+|}
-<center><math>
-{n'}^2\leq  n'_{xy}n'_{xz}n'_{yz}
-</math></center>
-oraz
+{| border="1"
+! <math>\text{p}</math>!! <math>\text{q}</math>!! <math>\text{r}</math>!!<math>(p \leftrightarrow q)</math>!! <math>(p \leftrightarrow q) \leftrightarrow r</math>!! <math>(q \leftrightarrow r)</math>!! <math>p \leftrightarrow (q \leftrightarrow r)</math>
+|-
+| 0|| 0|| 0|| 1|| 0|| 1|| 0
+|-
+| 0|| 0|| 1|| 1|| 1|| 0|| 1
+|-
+| 0|| 1|| 0|| 0|| 1|| 0|| 1
+|-
+| 0|| 1|| 1|| 0|| 0|| 1|| 0
+|-
+| 1|| 0|| 0|| 0|| 1|| 1|| 1
+|-
+| 1|| 0|| 1|| 0|| 0|| 0|| 0
+|-
+| 1|| 1|| 0|| 1|| 0|| 0|| 0
+|-
+| 1|| 1|| 1|| 1|| 1|| 1|| 1
+|}
-<center><math>
-{n''}^2\leq  n''_{xy}n''_{xz}n''_{yz}.
-</math></center>
-Co więcej, pomiędzy projekcjami zachodzą następujące zależności
+{| border="1"
+! <math>\text{p}</math>!! <math>\text{q}</math>!! <math>\text{r}</math>!!<math>\circ (p, q, r)</math>
+|-
+| 0|| 0|| 0|| 0
+|-
+| 0|| 0|| 1|| 1
+|-
+| 0|| 1|| 0|| 1
+|-
+| 0|| 1|| 1|| 0
+|-
+| 1|| 0|| 0|| 1
+|-
+| 1|| 0|| 1|| 0
+|-
+| 1|| 1|| 0|| 0
+|-
+| 1|| 1|| 1|| 1
+|}
-<center><math>
-n'_{xz}+n''_{xz}=n_{xz} </math>  oraz  <math>  n'_{yz}+n''_{yz}=n_{yz}.
-</math></center>
-Dla płaszczyzny <math>O_x, O_y</math> nie posiadamy podziału na część punktów
+{| border="1"
-należących do <math>n'</math> i <math>n''</math> i możemy jedynie wnioskować, że
+! <math>\text{p}</math>!! <math>\text{q}</math>!! <math>\text{r}</math>!!<math>f_{p \rightarrow _(q \rightarrow r)}</math>
+|-
+| 0|| 0|| 0|| 1
+|-
+| 0|| 0|| 1|| 1
+|-
+| 0|| 1|| 0|| 1
+|-
+| 0|| 1|| 1|| 1
+|-
+| 1|| 0|| 0|| 1
+|-
+| 1|| 0|| 1|| 1
+|-
+| 1|| 1|| 0|| 0
+|-
+| 1|| 1|| 1|| 1
+|}
-<center><math>
-n'_{xy}\leq n_{xy} </math>  oraz  <math>  n''_{xy}\leq n_{xy}.
-</math></center>
-Zaczynamy przekształcenia mające udowodnić pożądaną nierówność
+{| border="1" cellspacing="0"
+! <math>\Rightarrow</math>!! 0!! 1!! 2!!
+|-
+| &nbsp;0&nbsp;|| &nbsp;2&nbsp;|| &nbsp;2&nbsp;|| &nbsp;2&nbsp;
+|-
+| &nbsp;1&nbsp;|| &nbsp;0&nbsp;|| &nbsp;2&nbsp;|| &nbsp;2&nbsp;
+|-
+| &nbsp;2&nbsp;|| &nbsp;0&nbsp;|| &nbsp;1&nbsp;|| &nbsp;2&nbsp;
+|}
-<center><math>
+<math>\hat{\sigma}(f(t_0,..,t_n))= I(f)(\hat{\sigma}(t_0),..,\hat{\sigma}(t_n))</math>
-\beginsplit
-n^2& ={(n'+n'')}^2={(n')}^2+2n'n'' + {(n'')}^2\leq {(n')}^2+2\sqrt{{(n')}^2}\sqrt{{(n'')}^2} + {(n'')}^2\leq \\
-& \leq n'_{xy}n'_{xz}n'_{yz} +2\sqrt{n'_{xy}n'_{xz}n'_{yz}}\sqrt{n''_{xy}n''_{xz}n''_{yz}}+n''_{xy}n''_{xz}n''_{yz} \leq\\
-& \leq n_{xy}n'_{xz}n'_{yz} +2\sqrt{n_{xy}n'_{xz}n'_{yz}n_{xy}n''_{xz}n''_{yz}}+n_{xy}n''_{xz}n''_{yz} \leq \\
-& \leq n_{xy}\left(n'_{xz}n'_{yz}
-+2\sqrt{n'_{xz}n'_{yz}n''_{xz}n''_{yz}}+n''_{xz}n''_{yz}
-\right)\endsplit
-</math></center>
-używając założenia indukcyjnego i nierówności pomiędzy projekcjami
-na płaszczyznę <math>O_x, O_y</math>. Kontynuujemy używając nierówności
-pomiędzy średnią algebraiczną i geometryczną
-<center><math>
-\beginsplit
-n^2 & \leq n_{xy}\left(n'_{xz}n'_{yz} +2\sqrt{n'_{xz}n''_{xz}n'_{yz}n''_{yz}}+n''_{xz}n''_{yz}\right) \leq \\
-& \leq n_{xy}\left(n'_{xz}n'_{yz} +2\frac{1}{2}(n'_{xz}n''_{xz} +n'_{yz}n''_{yz})+n''_{xz}n''_{yz}\right) = \\
-& = n_{xy}\left(n'_{xz}n'_{yz} +n'_{xz}n''_{xz}
-+n'_{yz}n''_{yz}+n''_{xz}n''_{yz}\right) = n_{xy}(n'_{xz} +
-n''_{xz})(n'_{yz}+n''_{yz})
-\endsplit
-</math></center>
-W ostatnim kroku wystarczy wykorzystać zależności pomiędzy
+<center><math>X^*= \{1\}\cup X\cup X^2\cup ...\cup X^n \cup \ldots = \bigcup_{i=0}^\infty X^i</math></center>
-projekcjami na pozostałe dwie współrzędne i
-<center><math>
-n^2\leq n_{xy}(n'_{xz} + n''_{xz})(n'_{yz}+n''_{yz})=
-n_{xy}n_{xz}n_{yz}.
-</math></center>
-Krok indukcyjny został dowiedziony.
-Na podstawie zasady indukcji matematycznej twierdzenie jest
-prawdziwe.
-{Koniec æwiczenia {section}.{cwicz}}
-{obra}{1}{Obrazek {section}.{obra}}Obrazek do powyższego ćwiczenia według załączonego skanu
+-----------------------------------------------------------
-Zasada indukcji matematycznej jest bardzo potężnym narzędziem.
-Intuicyjnie wydaje się jasne, że dowody przeprowadzone przy jej
-pomocy są poprawne. Niemniej jednak, żeby uzasadnić poprawność
-samej zasady należy sięgnąć do teorii mnogości i definicji zbioru
-liczb naturalnych. Wiemy już, że "naiwna teoria mnogości" nie daje
-nam poprawnych zbiorów na których można oprzeć ścisłe rozumowanie.
-W dalszej części wykładu wyprowadzimy zasadę indukcji
-matematycznej w oparciu o aksjomaty i aksjomatycznie zdefiniowany
-zbiór liczb naturalnych. Takie podejście gwarantuje nam poprawność
-rozumowania -- podejście naiwne zapewnia intuicje niezbędne do
-budowania poprawnych teorii.
-=="Naiwne" dowody niewprost==
-Częstą metodą dowodzenia twierdzeń matematycznych jest dowodzenie
-niewprost. Dowód niewprost polega na założeniu zaprzeczenia
-twierdzenia, które chcemy udowodnić i doprowadzeniu do
-sprzeczności. Wykazujemy, że jeśli twierdzenie nasze jest
-nieprawdziwe, jesteśmy w stanie udowodnić jakąś tezę, która jest w
-sposób oczywisty fałszywa.
-Jednym z najbardziej znanych dowodów niewprost jest dowód
-istnienia nieskończenie wielu liczb pierwszych. Dowód ten został
-zaproponowany przez Euclid of Alexandria a my prezentujemy go w wersji podanej
-przez Ernst'a Kummera.
-{{twierdzenie|[Uzupelnij]||
+Nagroda Goedla<br>[[Nagroda Goedla|Zobacz Nagroda Goedla]]]]
-Istnieje nieskończenie wiele liczb pierwszych.
+Nagroda Turinga<br>[[Nagroda Turinga|Zobacz Nagroda Turinga]]
-}}
-{{dowod|[Uzupelnij]||
+Nagroda Knutha<br>[[Nagroda Knutha|Zobacz Nagroda Knutha]]
-Załóżmy że istnieje jedynie skończenie wiele liczb pierwszych
-<math>p_0,\dotsc,p_n</math>. Zdefiniujmy liczbę
-<center><math>
+<center><math>g(C)=\begin{cases} C\cup \{f(C')\} C \end{cases}
-k = p_0\cdot p_1\cdot\dotsb\cdot p_n
 </math></center>
-i rozważmy <math>k+1</math>. Liczba <math>k+1</math> posiada dzielnik pierwszy, a
-ponieważ jedynymi pierwszymi liczbami są liczby <math>p_0,\dotsc,p_n</math>
-wnioskujemy, że <math>p_i</math> dzieli <math>k+1</math> dla pewnego <math>i</math>. Liczba <math>p_i</math>
-dzieli również <math>k</math>, a więc <math>p_i</math> dzieli <math>(k+1)-k=1</math> co jest
-sprzecznością.
-}}
-{cwicz}{1}
-{hint}{0}
-{Æwiczenie {section}.{cwicz}}
-Wykaż, że nie istnieje największa liczba naturalna.
-; Solution.
+<math>g(C)=\left\{\begin{align} C\cup \{f(C')\}\\C\end{align} \right</math>
-: Załóżmy, niewprost, że istnieje największa liczba
-naturalna i oznaczmy ją przez <math>n</math>. Niewątpliwie <math>n+1</math> jest liczbą
-naturalną większą od <math>n</math>, co jest sprzecznością z naszym
-założeniem.
-{Koniec æwiczenia {section}.{cwicz}}
+<math>c\forall d\; c\in C \land d\in C \land c\sqsubseteq d\implies c\sqsubseteq' d,
+(C,\sqsubseteq) \preccurlyeq (C',\sqsubseteq') \iff C\subset C' \land \left\{\begin{align} \forall c \forall d\; &(c\in C\land d\in C) \implies (c\sqsubseteq d \iff c\sqsubseteq' d) \text{ oraz }\\
+\forall c \forall d\; &(c\in C\land d\in C'\setminus C) \implies c\sqsubseteq' d \end{align} \right</math>
-{cwicz}{1}
-{hint}{0}
-{Æwiczenie {section}.{cwicz}}
-Wykaż, że <math>\sqrt{2}</math> jest liczbą niewymierną.
+<math>h(0, a) = f(a)</math> dla każdego <math>a \in A \\h(n', a) = g(h(n, a), n, a)</math> dla każdego <math>a \in A</math> i <math>n \in \mathbb{N}</math>
-; Solution.
-: Załóżmy,
-niewprost, że <math>\sqrt{2}</math> jest liczbą wymierną, czyli, że istnieją
-dwie naturalne, względnie pierwsze liczby <math>k</math> i <math>l</math> takie, że
-<math>\sqrt{2}=k/l</math>. Przekształcając ostatnie wyrażenie otrzymujemy
-<math>k^2=2l^2</math>. Skoro <math>2</math> dzieli lewą stronę równości dzieli też i
-prawą, a ponieważ dwa jest liczbą pierwszą wnioskujemy, że <math>2</math>
-dzieli <math>k</math>. Jeśli <math>2</math> dzieli <math>k</math> to <math>4</math> dzieli <math>k^2</math> i na
-podstawie równości <math>4</math> dzieli <math>2l^2</math>. Wnioskujemy stąd, że <math>2</math>
-dzieli <math>l^2</math> i, na podstawie pierwszości liczby <math>2</math>, że <math>2</math> dzieli
-<math>l</math>. Udowodniliśmy, że <math>2</math> dzieli zarówno <math>k</math> jak i <math>l</math>, co jest
-sprzecznością z założeniem, że liczby te są względnie pierwsze.
-{Koniec æwiczenia {section}.{cwicz}}
-Ścisłe uzasadnienie poprawności dowodów niewprost leży na gruncie
+<math>e(0, a) = f(a)</math> dla każdego <math>a \in A \\ e(g(n, a), n, a)</math> dla każdego <math>a \in A</math> i <math>n \in m</math>
-logiki, której poświęcony jest następny wykład.

$p$	$q$	$r$	$(p \land q)$	$(p \land r)$	$(q \land \neg r)$	$(p \land r) \lor (q \land \neg r)$	$(p \land q) \Rightarrow ((p \land r) \lor (q \land \neg r))$
0	0	0	0	0	0	0	1
0	0	1	0	0	0	0	1
0	1	0	0	0	1	1	1
0	1	1	0	0	0	0	1
1	0	0	0	0	0	0	1
1	0	1	0	1	0	1	1
1	1	0	1	0	1	1	1
1	1	1	1	1	0	1	1

$p$	$q$	$r$	$(p \land q)$	$(p \land r)$	$(q \land \neg r)$	$(p \land r) \lor (q \land \neg r)$	$(p \land q) \Rightarrow ((p \land r) \lor (q \land \neg r))$
0	0	0	0	0	0	0	1
0	0	1	0	0	0	0	1
0	1	0	0	0	1	1	1
0	1	1	0	0	0	0	1
1	0	0	0	0	0	0	1
1	0	1	0	1	0	1	1
1	1	0	1	0	1	1	1
1	1	1	1	1	0	1	1

$p$	$q$	$r$	$(p \land q)$	$(p \land r)$	$(q \land \neg r)$	$(p \land r) \lor (q \land \neg r)$	$(p \land q) \Rightarrow ((p \land r) \lor (q \land \neg r))$
0	0	0	0	0	0	0	1
0	0	1	0	0	0	0	1
0	1	0	0	0	1	1	1
0	1	1	0	0	0	0	1
1	0	0	0	0	0	0	1
1	0	1	0	1	0	1	1
1	1	0	1	0	1	1	1
1	1	1	1	1	0	1	1