\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