Matematika pro Informatiky (4MM106)

• Katedra matematiky – Vysoká škola ekonomická v Praze
• 10. tyden test

Matematicka logika

• Vyrokovy pocet
  • Klicove slovo vyrok, primitivni pojem (nedefinujeme ho)
    • Ma pravdivost (v informatice binarni jednobitova hodnota)
    • Oznamovaci gramaticka veta, majici jednoznacne urcenou pravdivostni hodnotu
    • Vsechna auta jsou cervena
      • “Vsechna” je obecny kvantifikator ($\forall$), rika se vetsinou “kazde”
        • Dukaz muze byt protiprikladem
      • Vyrok ma pravdivostni hodnotu 0 / nil
    • V ucebne je prave jedna tabule
      • “Prave jedna” je kvantifikator existencni ($\exists$), v tomto pripade $\exists!$
    • Dnes je patek
      • Je to vyrok, ale zalezi na case
    • Zelezo je kov
      • Je to z realneho sveta, ale je to definovano vedni disciplinou chemii, takze se to da exaktne urcit
    • Pes je cerny
      • Neni to vyrok, ale je to vyrokova forma (predikat)
      • Pes je volna promenna $\therefore$ je to veta s jednou volnou promennou
        • Muzeme z toho udelat vyrok tim, ze do vety strcime nejaky konkretni priklad psa (dosazeni)
        • Muzeme z toho taky udelat vyrok tim, ze vetu kvantifikujeme (alespon jeden pes, prave jeden pes, vsichni psi)
  • Definice vs veta
    • Definice vymezuje pojem starsimi pojmy / konvence, jak se neco bude jmenovat
    • Recyklace starych definic pro vysloveni zakonitosti
    • Vety se dokazuji Logicke operace
• Atomarni vyroky (oznacujeme $\alpha \beta \gamma, ...$)

Symbol	Operace	Cteni	Co se dela
$\neg$	negace		opak
$\alpha \land \beta$	konjunkce	a zaroven	oba == 1
$\alpha \lor \beta$	disjunkce	nebo	>=jeden == 1
$\alpha \implies \beta$	implikace	beta vyplyva z alfy / $\alpha$ je dostacujici podminka pro $\beta$
$\alpha \iff \beta$	ekvivalence	prave tehdy, kdyz	a == b
$\alpha \oplus \beta$	XOR / X-OR (exkluzivni disjunkce)	bud $\alpha$, nebo $\beta$ (bez carky by to bylo normalni or)	jeden == 1
$\alpha \textbar \beta$	NAND (Sheffruv operator)		!oba = 1
$\alpha \downarrow \beta$	NOR (Peirceova sipka)	ani $\alpha$, ani $\beta$	oba != 1

$(\alpha \implies \beta) \iff (\beta \implies \alpha)$

$\alpha$	$\beta$	$\alpha \implies \beta$	$\beta \implies \alpha$	$\Phi$
1	1	1	1	1
1	0	0	1	0
0	1	1	0	0
0	0	1	1	1
Tautologie —> ve vysledkovem sloupci same jednicky
Kontradikce —> ve vyslednem sloupci same nuly
Splnitelna formule —> neni kontradikce

Ucebnice str. 17/1

Prvni hodina s prof. Klufou

• Matematika je deduktivni disciplina (z obecne pravdy dela dilci zavery)
  • Statistika je induktivni disciplina (z dilcich zaveru dela obecne pravdy)

Hodnost matice

• Vektory (usporadana n-tice realnych cisel, tzv. n-rozmerny vektor)
• $V_{n}$ je mnozina vsech n-rozmernych vektoru
• $\overline{o} = (0, 0, 0) \in V_n$
• Soucet vektoru $\overline{a}, \overline{b} \in V_n$ je vektor, definovany vztahem $(a_{1}, ..., a_{n}) + (b_{1,}..., b_{n})$
• Realne nasobeni vektoru: $\overline{a} \in V_{n}c(a_{1,}..., a_{n}) := (ca_{1,} ..., ca_n)$
• Skalarni soucin ma za vysledek skalar, ne vektor
• Linearni kombinace vektoru
  • $\overline{x} \in V_{n}$ je linearni kombinaci vektoru $x_{1}, ..., x_n$ jestlize existuji $c_{1},..,c\in R$: $\overline{x} = c_{1}\overline{x_{1}}...?$
  • Pokud jsou vsechny nulove, je to trivialni linearni kombinace
  • Priklad 1:
    • $\overline{x} LK \text{vekt.} \overline{x_{1}}+ \overline{x_2}$
      • $\overline{x_{1}}= (1,2)$
      • $\overline{x_{2}}= (-1,0)$
      • $\overline{x}= (0,4)$
      • $(0, 4) = c_1 (1,2) + c_2 (-1, 0)$
      • $(0, 4) = (c_{1 -}c_{2}, 2c_1)$
      • $c_1 - c_2 = 0$;$2c_{1 = 4}\therefore c_{1,2} =2$
  • Priklad 2:
    • $\gamma_{1}= (1,0,0)$
    • $\gamma_{2}= (0,1,0)$
    • $\gamma_{3}= (0,0,1)$
    • vektor $\gamma_1$ jako LK ostatnich
      • otazka: existuje $c_{1}, c_{2} \in R : \overline{\gamma_{1}}= c_{1}\overline{\gamma_{2}} + c_{2}\overline{\gamma_3}$
      • zaver: vektor $\gamma_1$ nelze vyjadrit jako LK ostatnich
    • Nulovy vektor je LK libovolne skupiny vektoru
• Linearni (ne)zavislost vektoru:
  • $\overline(x_{1)}, ..., \overline(x_{R)} LZ \iff \text{alespon jeden z nich je LK ostatnich}$
  • jeden vektor je LZ jen tehdy, pokud je nulovy ($\overline{x} je LZ \iff \overline{x} = \overline{o}$)
  • $\overline{a} = (1,2,3)$
  • $\overline{b} = (2,4,6)$
  • Dva vektory jsou LZ, jestlize jeden je nasobkem druheho, jinak jsou LNZ (linearne nezavisle)
  • Je casto narocne zjistit LZ u > 2 vektoru
  • Pomoci vypoctu hodnosti matice:
    • Vektory zapiseme do radku matice
    • Zjistime hodnost matice
    • Kdyz hodnost matice je rovna poctu radku, radky jsou linearne nezavisle (LNZ), pokud je hodnost mensi, jsou radky linearne zavisle (LZ) $$$$

\begin{pmatrix} 7 & 2 & 0 \ 3 & -1 & 2 \ 4 & 2 & -2 \end{pmatrix} \sim \begin{pmatrix} 7 & 2 & 0 \ 0 & -13 & 14 \ 0 & 13 & -14 \end{pmatrix} \sim \begin{pmatrix} 7 & 2 & 0 \ 0 & -13 & 14 \ \end{pmatrix} \implies h=2 \implies \overline{a}, \overline{b}, \overline{c} \text{ jsou LZ}

#### Matice - Usporadane schema realnych cisel - Matice typu $m \times n$ - Znaci se velkymi pismeny - Prvky matice - Usporadane m-tice realnych cisel - $$ A = \begin{matrix} a_{11}, a_{12}, a_{13}, ..., a_{1n}\\ a_{21}, a_{22}, a_{23}, ..., a_{2n} \\ ... \\ a_{m1}, a_{m2}, a_{m3}, ..., a_{mn} \end{matrix}

- matice, jejiz vsechny prvky jsou 0 se nazyva nulova
- $$ 0 = \begin{matrix} 0, 0, 0 \\ 0,0, 0 \\ 0,0,0 \end{matrix}$$

Hodnost matice

• maximalni pocet linearne nezavislych radku
• $A_{m \times n} \implies h(A) \leq m \land h(A) \leq n$
• Prevadime matici, ktere hodnost nezname na nejakou, ktere ano
• $\triangle$ matice
  • $A_{m \times n}, \text{kde} m \leq n$ se nazyva trojuhelnikova, jestlize ma na hlavni diagonale nenulove prvky a pod ni same nuly

$$A = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 0 & 1 & 5 & 2 \\ 0 & 0 & 3 & 7 \\ 0 & 0 & 0 & 1 \end{pmatrix}$$

- Pokud A je trojuhelnikova, jeji hodnot je pocet radku ($m$), v pripade above je to 4

• Veta o elementarnich radkovych upravach matice:
  • Hodnost matice se nezmeni, udelame-li v ni nasledujici elementarni radkove upravy:
    1. Zamenime poradi radku
    2. Radek nasobime nenulovym realnym cislem
    3. K radku pricteme nasobek jineho radku (obecne k radku muzeme pricist libovolnou LK ostatnich)
    4. Vynechame radek, ktery je LK ostatnich
• Gausuv algoritmus

$$A = \begin{pmatrix} 1 & 0 & -1 & 2 \\ 2 & 1 & 0 & -1 \\ -3 & 0 & 2 & 0 \\ 1 & 1 & 0 & 3 \end{pmatrix} \text{~} \begin{pmatrix} 1 & 0 & -1 & 2 \\ 0 & 1 & 2 & -5 \\ 0 & 0 & -1 & 6 \\ 0 & 1 & 1 & 1 \end{pmatrix} \text{~} \begin{pmatrix} 1 & 0 & -1 & 2 \\ 0 & 1 & 2 & -5 \\ 0 & 0 & -1 & 6 \\ 0 & 0 & -1 & 6 \end{pmatrix} \text{~} \begin{pmatrix} 1 & 0 & -1 & 2 \\ 0 & 1 & 2 & -5 \\ 0 & 0 & -1 & 6 \end{pmatrix} \implies h(A) = 3$$

1. Pomoci prvniho radku nulujeme prvni sloupec pod hl. diagonalou
	1. Prvni radek nasobim -1 a prictu radek
2. Pomoci druheho radku nulujeme druhy sloupec pod hl. diagonalou
3. Vynechame posledni radek, ktery je LK ostatnich (1x 3. + 0x zbytek)

• Transponovana matice
  • Zamenime-li v matici radky za sloupce, tak, ze zachovame jejich poradi, dostaneme matici, ktere rikame transponovana matice
• Jestlize A, A’ jsou nazvajem transponovane matice pak h(A) = h(A’)
  • Poznamka: pri vypoctu hodnosti matice muzeme udelat stejne sloupcove upravy jako radkove

Cviko 2024-09-20

$$(\alpha \land \beta) \implies \gamma \iff \alpha \land (\beta \implies \gamma)$$

• Protoze mame 2 pravdivostni hodnoty a 3 atomarni prvky, budeme mit $2^3$ radku

$\alpha$	$\beta$	$\gamma$	$\alpha \land \beta$	$(\alpha \land \beta) \implies \gamma (\phi))$	$\beta \implies \gamma$	$\alpha \land (\beta \implies \gamma) (\psi)$	$\phi \iff \psi$	$\delta$ (nas vymysl)
1	1	1	1	1	1	1	1	1
1	1	0	1	0	0	0	1	0
1	0	1	0	1	1	1	1	0
1	0	0	0	1	1	1	1	0
0	1	1	0	1	1	0	0	0
0	0	1	0	1	0	0	0	1
0	1	0	0	1	1	0	0	0
0	0	0	0	1	1	0	0	0

• Kanonicka disjunktivni formule vyroku above 👆 -> pokud plati $\alpha$, neboli $\omega \iff \alpha$

  • Kanonicka disjunktivni pro modelovou $\delta$: $\delta \iff (\alpha \land \beta \land \gamma) \lor (\neg \alpha \land \beta \land \neg \gamma)$

• Pr. $(\alpha \downarrow \beta) \textbar (\alpha \implies \beta) \iff (\neg \alpha \oplus \beta)$

Vysvetlivka: $\omega$ je kanonicka disjunktivni formule

$\alpha$	$\beta$	$(\alpha \downarrow \beta)$	$\alpha \implies \beta$	$\phi$ (prvni zavorka)	$\neg \alpha$	$\neg \alpha \oplus \beta = \psi$	$\phi \iff \psi$
1	1	0	1	1	0	1	1
1	0	0	0	1	0	0	0
0	1	0	1	1	1	0	0
0	0	1	1	0	1	1	0
=> $\omega \iff (\alpha \land \beta)$

$((\alpha \downarrow \beta) \downarrow (\alpha \downarrow \beta)) \iff (\alpha \lor \beta)$

$\alpha$	$\beta$	$(\alpha \downarrow \beta)$	$\alpha \lor \beta$	$\phi$	$\phi \iff \psi$
1	1	0	1	1	1
1	0	0	1	1	1
0	1	0	1	1	1
0	0	1	0	0	1

• Tautologie ✅

Na doma:

$$((\alpha \textbar \beta) \textbar (\alpha \textbar \beta)) \iff (\alpha \land \beta)$$

Dulezite tautologie

• $\alpha \lor \neg \alpha$

• $\neg(\alpha \land \neg \alpha)$

• $\neg(\neg \alpha) \iff \alpha$

• $(\alpha \implies \beta) \iff (\neg \beta \implies \neg \beta)$ (kontrapozice)

• $\neg (\alpha \land \beta) \iff (\neg \alpha \lor \neg \beta)$

• $\neg (\alpha \lor \beta) \iff (\neg \alpha \land \neg \beta)$ 👆 de Morganovy zakony

• $\neg (\alpha \implies \beta) \iff (\alpha \lor \beta)$

Negace tvrzeni:

• Dnes bude prset a zitra bude snezit => dnes nebude prset nebo zitra nebude snezit
• Budu-li se prubezne ucit, zkousku udelam => budu se ucit, zkousku neudelam
• Odpoledne nepujdu na trenink, ani vecer do hospody => pujdu na trenink, nebo vecer do hospody
• Prijmou me na skolu, nebo si najdu praci => neprijmou me na skolu a nenajdu si praci

Def: Necht A je ctvercova matice. Matici X, pro niz plati $A \cdot X = J$ nazveme inverzni matice k matici A. Obvykle ji znacine $A^{-1}$ $\therefore$ nema singularni matice inverzi $\therefore$ pokud neexistuje $\triangle$ tvar, ale pouze odstupnovany, A$^{-1}$ neexistuje

Veta o existenci a jednoznacnosti inverzni matice: A je regularni $\Leftrightarrow$ existuje $A^{-1}$ a je urcena jednoznacne

Veta o navzajem inverznich maticich Je-li matice $A$ regularni, pak $A^{-1}$ je regularni a plati $(A^{-1} = A)$. Dusledek: $A \cdot A^{-1}$ = J

O maticove rovnici, je-li A reg radu n plati: $AX = B$ ma 1 reseni $X = A^{-1} B$ pro B typu nxp $XA = B$ ma 1 reseni $X = B * A^{-1}$ pr oB typu q x n

Pozn:

1. V pripade, ze matice A B3 neni regularni, nelze vyloucit existenci resevni rovnice. Hleda se prevodem na soustavu linearnich rovnic.
2. Naopak kazdou soustavu LR lze reprezentovat

Veta o reseni soustavy LR pomoci inverzni matice Je-li A matice soustavy LR regularni, pak soustava zapsana ve tvaru Ax = b ma jedine reseni, $x = A^{-1} b$

Def Determinantem ctvercove matice A = [aij] radu n rozeznavame realne cislo jednoznacne prirozene teto matici a znacime je det A, resp. |A|. Hodnotu det A definujeme v zavislosti na n takto: n = 1 det $a_{11} = a_{11}$ n = 2 $\begin{vmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{vmatrix}$ = $a_{11} \cdot a_{22} - a_{12} \cdot a_{21}$ n = 3 – Sarusovo pravidlo

Veta: Laplace – o rozvoji determinantu (dle i-teho radku): Je-li $A = [a_{ij}]$ ctvercova matice radu n, pak pro $i = 1,2,...,n$ plati: $|A| = (-1)^{i+1} a_{i1} M_{i1} + (-1)^{i+2} a_{i2} M_{i2} + ... + (-1)^{i+n} a_{in} M_{in}$ kde $M_{ij}$ je determinant matice, ktera vznikne z matice $A$ vynechanim i-teho radku a j-teho sloupce. Pozn. $M_{ij}$ - tzv. subdeterminant – rad o 1 mensi nez $|A|$ Pozn.: $M$ (Minor) je maly determinant