\input /home/pasky/school/fastex/lib.tex

\subchapter{V�rokov� logika}{


\definition{
	\shortdef{Logika}{v�da o spr�vnosti v�rok�.}
	\shortdef{V�rok}{tvrzen�, o kter�m m� smysl ��ci, zda je pravdiv� nebo ne.
		Obvykle ve form� ``premisa $\Rightarrow$ d�sledek''.
		Tarskiho definice: ``V�rok $A$ je pravdiv�, jestli�e $A$.''}

	\example{
		$$ \eqalign{(A \Rightarrow B) &\Longleftrightarrow (\neg B \Rightarrow \neg A)\cr
					      &\Longleftrightarrow \neg (A \et \neg B)} $$
	}

	\shortdef{V�rokov� funkce}{v�raz, z n�j� obdr��me v�rok po dosazen� prvk� za prom�nn�.
		Zapisujeme $V(x_1,\ldots,x_n)$, $x_n \in M_n$.}
	\shortdef{Kvantifik�tory}{v�eobecn� ($\forall$) a existen�n� ($\exists$).
		Plat� {\bf princip stejnom�rnosti}:}
	$$ \forall x\ \existss y: V(x,y) \Longleftarrow \existss y\ \forall x: V(x,y) $$
}


\scpart{Z�kladn� metody d�kaz�}{
	Pou��v�me zejm�na d�kazy sporem, indukc�, p��mo a nep��mo.
	Je z�hodno se vyhnout d�kazu kruhem.

	P�i dokazov�n� je vhodn� si uv�domit form�ln� definici dokazovan�ho
	v�roku a aplikovat ji na n� konkr�tn� p��pad (nap�. dokazujeme-li
	existenci limity, m��e pomoci vyj�t z dosazen� do jej� definice).

	\shortdef{Tvrzen�}{Pro $\forall n \in \nat: n^2$ lich� $\Rightarrow$ $n$ lich�.}
	{\bf D�kazy:}
	\list{
	\listItem{{\bf P��mo:}
		$$ n^2 = p_1^2 \cdots p_k^2 \textnote{prvo��seln� rozklad} $$
		$$ n = p_1 \cdots p_k $$
		$$ j = 1,\ldots,k: p_j \ne 2 \Rightarrow n \textbox{lich�} $$
	}
	\listItem{{\bf Nep��mo:}
		$$ n \textbox{sud�} \Rightarrow n = 2m \Rightarrow n^2 = 4m^2 \Rightarrow n^2 \textbox{sud�} $$
	}
	\listItem{{\bf Sporem:}
		$$ n^2 \textbox{lich�} \et n \textbox{sud�} $$
		$$ \Longrightarrow n^2 + n \textbox{lich�} \Longrightarrow n(n+1) \textbox{lich�} $$

		\XXX
	}
	\listItem{{\bf Indukc�:}

		$n = 1$: $1^2$ lich�, $1$ lich�.

		$n \Rightarrow n + 2$: $n^2$ lich� $\Rightarrow$ $(n+2)^2$ lich�
		(nebo� $(n+2)^2 = n^2 + 2n + 4 = 2n + 5$ je lich�).

		\qed
	}
	}

}

\penalty-100

\scpart{Dal�� p��klady:}{
	\list{
	\olistItem{{\bf P��mo:} $A \Rightarrow C_1 \Rightarrow C_2 \Rightarrow \cdots \Rightarrow C_n \Rightarrow B$

		{\bf Cauchyho nerovnost:}{
			$$ \left(\sum_{i=1}^n a_ib_i\right)^2
				\le \left(\sum_{i=1}^n a_i^2\right)\left(\sum_{i=1}^n b_i^2\right) $$
			$$ \forall m \in \nat,\ a_1, \ldots, a_n, b_1, \ldots, b_n \in \real $$

			\list{
			\listItem{$a_1 = a_2 = \cdots = a_n = 0$, tedy plat�.}
			\listItem{$\existss i \in \{1,\ldots,n\}: a_i \ne 0$.

				\shortdef{Trik}{Definujme si:}
				$$f(x) := \sum_{i=1}^n \left(a_ix + b_i\right)^2$$
				
				Pak plat�:
				$$f(x) = \left(\sum_{i=1}^n a_i^2\right)x^2 + \left(\sum_{i=1}^n 2a_ib_i\right)x
					+ \left(\sum_{i=1}^n b_i^2\right) = \alpha x^2 + \beta x + \gamma$$
				$$ \alpha > 0,\ f(x) > 0 \becauseof{z grafu}{\Longrightarrow} D \le 0
					\Leftrightarrow \beta^2 - 4\alpha\gamma \le 0 $$
				$$ \beta^2 - 4\alpha\gamma \le 0 \Longrightarrow
					\beta^2 \le 4\alpha\gamma = 4\left(\sum_{i=1}^n a_ib_i\right)^2
					\le 4\left(\sum_{i=1}^n a_i^2\right)\left(\sum_{i=1}^n b_i^2\right) $$
			}
			}

			\qed
		}
	}

		\medskip

	\olistItem{{\bf Sporem:} P�edpokl�d�me opak a dok�eme jeho neplatnost.

		{\bf Iracionalita $\sqrt{2}$:}{
			$$ x > 0: x^2 = 2 \Rightarrow x \notin \rat $$

			Nech� $x = p/q$, kde $p$, $q$ jsou nesoud�ln�:
			$$ x^2 = 2 \Longrightarrow p^2/q^2 = 2 \Longrightarrow p^2 = 2q^2 $$
			$$ p^2 = 4m \Longrightarrow q^2 = 2m $$

			To je ale spor s nesoud�lnost� $p$, $q$.
			\qed
		}

% TODO
%		{\bf Troj�heln�kov� nerovnost:}{
%		}
	}

		\medskip

	\olistItem{{\bf Indukc�:} Dokazujeme, �e pro $\forall n \in \nat: V(n)$.
		Sta�� dok�zat:
		\list{
		\rlistItem{$V(1)$}
		\rlistItem{$V(n) \Rightarrow V(n+1)$}
		}

		{\bf Bernoulliho nerovnost:}{
			$$ (1+x)^n \ge 1+nx\qquad \forall n \in \nat, x \ge -1 $$

			\list{
			\nlistItem{$n = 1$:

				$1 + x \ge 1 + x$
			}
			\nlistItem{$V(n) \Rightarrow V(n+1)$:

				$(1+x)^n(1+x) \ge (1+nx)(1+x) = 1 + (n+1)x + nx^2 \ge 1 + (n+1)x$
			}
			}

			\qed
		}

		\smallskip

		{\bf A-G nerovnost:}{
			$$ {a_1 + a_2 + \cdots + a_n \over n} \ge \broot{n}\of{\strut a_1a_2\cdots a_n} $$
			$$ \forall n \in \nat,\ a_1,a_2,\ldots,a_n > 0 $$

			$V(1)$ je trivi�ln�.

			$V(2)$: $(a_1 + a_2)/2 \ge \broot{2}\of{a_1a_2}$. Nech� $a = A^2$ a $b = B^2$:
				$$ (A - B)^2 = A^2 + B^2 - 2AB \ge 0 $$

			\penalty-100

			$V(n) \Rightarrow V(2n)$:
				$$ {a_1 + \cdots + a_n + a_{n+1} + \cdots + a_{2n} \over 2n} = $$
				$$ = {a_1 + \cdots + a_n \over n} + {a_{n+1} + \cdots + a_{2n} \over n} \ge $$
				$$ \becauseof{$V(2)$}{\ge} \broot{2}\of{\strut {a_1 + \cdots + a_n \over n}
						\cdot{a_{n+1} + \cdots + a_{2n} \over n}} \ge $$
				$$ \becauseof{$V(n)$}{\ge} \broot{2}\of{\broot{n}\of{\strut a_1\cdots a_n}
				   		\cdot\broot{n}\of{\strut a_{n+1}\cdots a_{2n}}} = $$
				$$ = \broot{2n}\of{\strut a_1\cdots a_{2n}} \Longrightarrow V(2n) $$

			$V(n+1) \Rightarrow V(n)$: M�jme $a_1,\ldots,a_n$.

				{\bf Trik:} Definujme:
				$$ \eqalign{b_1 &:= {a_1 \over \broot{n}\of{a_1\cdots a_n}}\cr
				            b_2 &:= {a_2 \over \broot{n}\of{a_1\cdots a_n}}\cr
				            b_n &:= {a_n \over \broot{n}\of{a_1\cdots a_n}}\cr
				            b_{n+1} &:= 1} $$

				$$ \eqalign{V(n+1)\Longrightarrow {b_1 + b_2 + \cdots + b_{n+1} \over n+1}
						&\ge \broot{n+1}\of{\strut b_1b_2\cdots b_{n+1}} = 1\cr
						b_1 + b_2 + \cdots + b_{n+1} &\ge n+1\cr
						{a_1 + a_2 + \cdots + a_{n} \over \broot{n}\of{a_1\cdots a_n}} &\ge n\cr
						{a_1 + a_2 + \cdots + a_{n} \over n} &\ge \broot{n}\of{\strut a_1\cdots a_n}
							\Longrightarrow V(n)} $$

			\qed
		}
	}
	}
}



}

\bend
