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: @@
 {| border="1" cellspacing="0"
-! !! Złożoność czasowa !! Złożoność pamięciowa
+! <math>\phi</math>!! <math>\psi</math>!! <math>\psi \Rightarrow \phi</math>!! <math>(\phi \Rightarrow (\psi \Rightarrow \phi))</math>!!
- |-
- ! 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>
-|}
-{| border="1"
-! <math>\Rightarrow</math>!! 0!! 1!! ...!! ...
-|-
-| Cell1|| Cell2
-|}
-{| 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;
-|}
-{| border="1" cellspacing="0"
-! <math>p</math>!! <math>\neg p</math>
-|-
-| &nbsp;0&nbsp;|| &nbsp;1&nbsp;||
-|-
-| &nbsp;1&nbsp;|| &nbsp;0&nbsp;||
-|}
-{| border="1" cellspacing="0"
-! <math>\wedge</math>!! 0!! 1!!
 |-
-| &nbsp;0&nbsp;|| &nbsp;0&nbsp;|| &nbsp;o&nbsp;
+| &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;1&nbsp;|| &nbsp;0&nbsp;|| &nbsp;1&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;
-|}
-{| border="1" cellspacing="0"
-! <math>\vee</math>!! 0!! 1!!
 |-
-| &nbsp;0&nbsp;|| &nbsp;0&nbsp;|| &nbsp;1&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;1&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;
 |}
-=="Naiwna" indukcja==
-Zasada indukcji matematycznej jest o prawie trzysta lat starsza
-niż teoria mnogości. Pierwszy dowód indukcyjny pojawił się w pracy
-<u>'''Francesco Maurolico'''</u> 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>.
+<center><math>\left| x \right|\ = \left\{ \begin{array}{rll} x & \text{ gdy }, x\geq 0 \\ -x & \text{ w przeciwnym przypadku}.
+\end{array}</math></center>
-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:
-:1. hipoteza jest prawdziwa dla <math>n=1</math> na podstawie podstawy indukcji,
-:2. hipoteza jest prawdziwa dla <math>n=2</math>, ponieważ jest prawdziwa dla '''1''' i po zastosowaniu kroku &nbsp;&nbsp;&nbsp;&nbsp;indukcyjnego również dla '''2''',
+<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>
-:3. hipoteza jest prawdziwa dla <math>n=3</math>; w poprzednim punkcie pokazaliśmy, że jest prawdziwa dla &nbsp;&nbsp;&nbsp;&nbsp;'''2''' i na podstawie kroku indukcyjnego jest również prawdziwa '''3'''
+oraz
-:4. i tak dalej.
+<center><math>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}</math></center>
-Zasadę indukcji matematycznej można porównać do domina. Aby mieć
+Ostatecznie, gramatyka w postaci Greibach ma postać:
-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.
-Obrazek 2.1 nieskończone domino ponumerowanych liczbami naturalnymi klocków w trakcie przewracania
+<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 \\
+ 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}</math></center>
-Dowód indukcyjny przedstawiony przez <u>'''Francesco Maurolico'''</u> 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>\begin{array} {c|c|c|c|c|} Krok & dodane\quad do\quad S' & okreslenie\quad f' & dodane\quad do\quad T'\\
+\hline 0 & \{q_0\} &  & \emptyset\\
+\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>
-<center><math>
-+3+\dotsb+(2n-1) = n^2.
-</math></center>
-tak więc suma pierwszych <math>n+1</math> liczb nieparzystych
+<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)\\
-<math>1+3+\dotsb+(2n-1)+(2(n+1)-1)</math>, przy użyciu założenia powyżej może być zapisana jako
+\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>
-<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.
-{{cwiczenie|2.1||
-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>\begin{array} {c|c|c|c|c|} (s_0,\sharp)\mapsto (s_R,\sharp,0) & (s_1,\diamondsuit)\mapsto(s1,\diamondsuit,1)\\
+\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>
-<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 2.1
+<center><math>\begin{array} {c|c|c|c|c|}  & s_0 & s_1 & s_2\\
-}}
+\hline \tau _{\mathcal{A}}(1) & s_0 & s_1 & s_2\\
+\hline \tau _{\mathcal{A}}(a) & s_1 & s_2 & s_2\\
-{{cwiczenie|2.2||
+\hline \tau _{\mathcal{A}}(b) & s_0 & s_0 & s_0\\
-Wykaż, że suma kwadratów pierwszych <math>n</math> liczb
+\hline \tau _{\mathcal{A}}(a^{2}) & s_2 & s_2 & s_2\\
-naturalnych jest równa <math>\frac{1}{6}n(n+1)(2n+1)</math>.
+\hline \tau _{\mathcal{A}}(ab) & s_0 & s_0 & s_2\\
-'''Solution.''' Aby wykazać prawdziwość wzoru powyżej postępujemy jak
+\hline \tau _{\mathcal{A}}(ba) & s_1 & s_1 & s_1\\
-w poprzednim zadaniu.
+\hline \tau _{\mathcal{A}}(b^{2}) & s_0 & s_0 & s_0\\
+\hline \tau _{\mathcal{A}}(aba) & s_1 & s_1 & s_2\\
-:* Dla <math>n=1</math> mamy <math>\frac{1}{6}\cdot 1\cdot 2\cdot 3 = 1</math> co dowodzi podstawy indukcji.
+\hline ... & ... & ... & ...\\
+\hline \end{array} </math></center>
-:* Zakładamy że wzór jest prawdziwy dla <math>n</math> to jest, że
+<center><math>\begin{array} {c|c|c|c|c|} f & s_0 & s_1 & s_2 & s_3\\
+\hline a & s_1 & s_2 & s_0 & s_2\\
+\hline b & s_3 & s_2 & s_2 & s_2\\
+\hline \end{array} </math></center>
-<center><math>
-^2+2^2+\dotsb+n^2 = \frac{1}{6}n(n+1)(2n+1).
-</math></center>
+{{algorytm|Minimalizuj2 - algorytm minimalizacji automatu
+wykorzystujący stabilizujący się ciąg relacji|algorytm minimalizacji automatu wykorzystujący stabilizujący się ciąg relacji|
-:Korzystając z tego faktu przekształcamy
+  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>;
-<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 2.2
 }}
-{{cwiczenie|2.3||
-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 '''4'''.
-:* Zakładamy że podzielność zachodzi dla <math>n</math>. Pokażemy że <math>3^{2(n+1)-1}+1</math> jest podzielne przez '''4'''. Przekształcamy
+{| border=1
+|+ <span style="font-variant:small-caps">Uzupelnij tytul</span>
+|-
+|
+||
+<math>s_{0} </math>  ||
+<math>s_{1} </math>  ||
+<math>s_{2} </math>
+|-
+|
-<center><math>
+<math>\tau _{\mathcal{A}}(1) </math>  ||
-^{2(n+1)-1}+1 = 3^{2n-1+2} + 1 = 9\cdot 3^{2n-1} + 1=
+<math>s_{0} </math>  ||
-</math></center>
+<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>
+|-
+|
+... ||
+... ||
+... ||
+...
+|-
+|
+|}
-:wprowadzamy sztuczny czynnik
+<math>
+\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>
-=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 '''8''' są podzielne przez '''4''', a wiec ich różnica również. W ten sposób udowodniliśmy krok indukcyjny.
+  alalalalaa
-Koniec ćwiczenia 2.3
+ alala
-Często bardzo niepraktyczne jest używanie indukcji w jej
+{| border="1" cellspacing="0"
-podstawowej formie. Używa się wtedy indukcji, która w pierwszym
+! !! Złożoność czasowa !! Złożoność pamięciowa
-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
+ ! 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>
-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
+ ! 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>
-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>.
+{| border="1"
+! <math>\Rightarrow</math>!! 0!! 1!! ...!! ...
+|-
+| Cell1|| Cell2
+|}
-* Jeśli hipoteza jest prawdą dla <math>n</math> i jeśli <math>n\geq 4</math> to
-<center><math>
+{| border="1" cellspacing="0"
-(n+1)!= n!\cdot (n+1)>2^n\cdot(n+1)>2^{n+1}
+! <math>\Rightarrow</math>!! 0!! 1!!
-</math></center>
+|-
+| &nbsp;0&nbsp;|| &nbsp;1&nbsp;|| &nbsp;1&nbsp;
+|-
+| &nbsp;1&nbsp;|| &nbsp;0&nbsp;|| &nbsp;1&nbsp;
+|}
-:gdzie pierwsza nierówność pochodzi z założenia indukcyjnego, a
-druga z faktu, że dowodzimy krok indukcyjny dla liczb większych
-niż '''4'''.
-}}
-{{cwiczenie|2.4||
+{| border="1" cellspacing="0"
+! <math>p</math>!! <math>\neg p</math>
+|-
+| &nbsp;0&nbsp;|| &nbsp;1&nbsp;||
+|-
+| &nbsp;1&nbsp;|| &nbsp;0&nbsp;||
+|}
-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:
+{| border="1" cellspacing="0"
+! <math>\wedge</math>!! 0!! 1!!
+|-
+| &nbsp;0&nbsp;|| &nbsp;0&nbsp;|| &nbsp;0&nbsp;
+|-
+| &nbsp;1&nbsp;|| &nbsp;0&nbsp;|| &nbsp;1&nbsp;
+|}
-:* Nierówność ostra nie jest prawdą dla <math>n=0</math>, ani dla <math>n=1</math>. Krok indukcyjny zaczniemy od '''2'''. Wtedy
+{| border="1" cellspacing="0"
-<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>.
+! <math>\vee</math>!! 0!! 1!!
+|-
+| &nbsp;0&nbsp;|| &nbsp;0&nbsp;|| &nbsp;1&nbsp;
+|-
+| &nbsp;1&nbsp;|| &nbsp;1&nbsp;|| &nbsp;1&nbsp;
+|}
-:* 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
+{| border="1"
+! <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>
+|-
+| &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>
+{| border="1"
-{(1+x)}^n> 1+nx.
+! <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>
-</math></center>
+|-
+| 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
+|}
-:Przekształcając nierówność dla <math>n+1</math> otrzymujemy
+{| border="1"
+! 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;
+|-
+| 0|| 0|| 0|| 0|| 0|| &nbsp;|| <math>F</math>
+|-
+| 1|| 0|| 0|| 0|| 1|| &nbsp;|| <math>\wedge</math>
+|-
+| 2|| 0|| 0|| 1|| 0|| &nbsp;|| <math>\neg (p \Rightarrow q)</math>
+|-
+| 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>
+{| border="1"
-{(1+x)}^{(n+1)}={(1+x)}^n(1+x)>(1+nx)(1+x)=1+(n+1)x +x^2\geq
+! <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>
-+(n+1)x,
+|-
-</math></center>
+| 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
+|}
-: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.
+{| border="1"
+! <math>\text{p}</math>!! <math>\text{q}</math>!! <math>\text{r}</math>!!<math>\circ (p, q, r)</math>
-Koniec ćwiczenia 2.4
+|-
-}}
+| 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
+|}
-{{cwiczenie|2.5||
-Liczby Fibonacciego zdefiniowane są następująco
+{| border="1"
+! <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>
+{| border="1" cellspacing="0"
-f_1=1, f_2=1 </math>  oraz  <math>  f_i=f_{i-2}+f_{i-1}  </math>  dla  <math>  i>3.</math></center>
+! <math>\Rightarrow</math>!! 0!! 1!! 2!!
+|-
+| &nbsp;0&nbsp;|| &nbsp;2&nbsp;|| &nbsp;2&nbsp;|| &nbsp;2&nbsp;
-Udowodnij, że dla dowolnego <math>n\geq 2</math> liczby <math>f_n</math> i <math>f_{n-1}</math> są względnie pierwsze.
+|-
+| &nbsp;1&nbsp;|| &nbsp;0&nbsp;|| &nbsp;2&nbsp;|| &nbsp;2&nbsp;
+|-
-'''Solution.''' Dowód przez indukcję matematyczną
+| &nbsp;2&nbsp;|| &nbsp;0&nbsp;|| &nbsp;1&nbsp;|| &nbsp;2&nbsp;
+|}
-:* 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 '''1'''. Pokazaliśmy, że każdy wspólny dzielnik <math>f_{n+1}</math> i <math>f_n</math> jest równy '''1''', a więc liczby te są względnie pierwsze. Krok indukcyjny został pokazany.
-Koniec ćwiczenia 2.5
-}}
-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ż '''2''' jest liczbą pierwszą.
-* Zakładamy że hipoteza jest prawdziwa dla liczb od '''2''' 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.
-{{cwiczenie|2.6||
-Udowodnij, że każda liczba naturalna większa niż
-'''1''' może być przedstawiona jako suma liczb Fibonacciego tak, że
-żadna liczba nie występuje w tej sumie więcej niż raz.
-'''Solution.''' Przedstawimy dowód przez indukcję.
-:* Dla <math>n=1</math> mamy <math>f_2=1</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 raz. Oczywiście
-<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 <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 2.6
-}}
-{{cwiczenie|2.7||
-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ą.
-* 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.
-'''Solution.''' Dowód indukcyjny jest niepoprawny. Krok indukcyjny nie działa dla wszystkich <math>n</math> większych lub równych od '''0''' - 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 '''1''' na sumę dwóch liczb istotnie mniejszych od niej samej.
-Koniec ćwiczenia 2.7
-}}
-{{cwiczenie|2.8||
-W trójwymiarowej przestrzeni znajduje się <math>n</math> punktów. Ilość
-punktów w rzutowaniu na płaszczyznę <math>O_x, O_y</math> oznaczamy przez
-<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
-<math>n_{yz}</math>. Wykaż, że dla dowolnego rozkładu punktów w przestrzeni
-zachodzi nierówność
-<center><math>
-n^2\leq n_{xy}n_{xz}n_{yz}.
-</math></center>
-'''Hint 1.''' Użyj nierówności pomiędzy średnią geometryczną, a średnią arytmetyczną
-<center><math>
-\frac{1}{2}(a+b)\geq \sqrt{ab}.
-</math></center>
-'''Hint 2.''' Podziel punkty na dwie grupy płaszczyzną równoległą do
-którejś z płaszczyzn<br/> &nbsp;&nbsp;&nbsp;&nbsp;<math>O_x, O_y</math>, <math>O_x, O_z</math> lub <math>O_y, O_z</math>.
-'''Solution.''' Dowiedziemy nierówność przy użyciu indukcji.
-:* 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 naturalnych&nbsp;(dla dowolnego układu punktów) mniejszych niż <math>n+1</math>. 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 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 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 płaszczyzny <math>O_x, O_y</math>. Stosując założenie indukcyjne do każdej z części otrzymujemy
-<center><math>
-{n'}^2\leq  n'_{xy}n'_{xz}n'_{yz}
-</math></center>
-:oraz
-<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
+<math>\hat{\sigma}(f(t_0,..,t_n))= I(f)(\hat{\sigma}(t_0),..,\hat{\sigma}(t_n))</math>
-<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 należących do <math>n'</math> i <math>n''</math> i możemy jedynie wnioskować, że
+<center><math>X^*= \{1\}\cup X\cup X^2\cup ...\cup X^n \cup \ldots = \bigcup_{i=0}^\infty X^i</math></center>
-<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ść
+-----------------------------------------------------------
-<center><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ą
+Nagroda Goedla<br>[[Nagroda Goedla|Zobacz Nagroda Goedla]]]]
-<center><math>
+Nagroda Turinga<br>[[Nagroda Turinga|Zobacz Nagroda Turinga]]
-\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>
+Nagroda Knutha<br>[[Nagroda Knutha|Zobacz Nagroda Knutha]]
-:W ostatnim kroku wystarczy wykorzystać zależności pomiędzy projekcjami na pozostałe dwie współrzędne i
+<center><math>g(C)=\begin{cases} C\cup \{f(C')\} C \end{cases}
-<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.
+<math>g(C)=\left\{\begin{align} C\cup \{f(C')\}\\C\end{align} \right</math>
-Na podstawie zasady indukcji matematycznej twierdzenie jest
+<math>c\forall d\; c\in C \land d\in C \land c\sqsubseteq d\implies c\sqsubseteq' d,
-prawdziwe.
+(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>
-Koniec ćwiczenia 2.8
-}}
-Obrazek 2.2 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
+<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>
-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 <u>'''Euclid of Alexandria'''</u> a my prezentujemy go w wersji podanej
-przez Ernst'a Kummera.
-{{twierdzenie|[Istnieje nieskończenie wiele liczb pierwszych]||
+<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>
-}}
-{{dowod|||
-Załóżmy że istnieje jedynie skończenie wiele liczb pierwszych
-<math>p_0,\dotsc,p_n</math>. Zdefiniujmy liczbę
-<center><math>
-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ą.
-}}
-{{cwiczenie|3.1||
-Wykaż, że nie istnieje największa liczba naturalna.
-'''Solution.''' 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 3.1
-}}
-{{cwiczenie|3.2||
-Wykaż, że <math>\sqrt{2}</math> jest liczbą niewymierną.
-'''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 3.1
-Ścisłe uzasadnienie poprawności dowodów niewprost leży na gruncie
-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