#LyX 2.3 created this file. For more info see http://www.lyx.org/ \lyxformat 544 \begin_document \begin_header \save_transient_properties true \origin unavailable \textclass article \begin_preamble \usepackage{siunitx} \usepackage{pgfplots} \usepackage{listings} \usepackage{multicol} \sisetup{output-decimal-marker = {,}, quotient-mode=fraction, output-exponent-marker=\ensuremath{\mathrm{3}}} \end_preamble \use_default_options true \begin_modules enumitem \end_modules \maintain_unincluded_children false \language slovene \language_package default \inputencoding auto \fontencoding global \font_roman "default" "default" \font_sans "default" "default" \font_typewriter "default" "default" \font_math "auto" "auto" \font_default_family default \use_non_tex_fonts false \font_sc false \font_osf false \font_sf_scale 100 100 \font_tt_scale 100 100 \use_microtype false \use_dash_ligatures true \graphics default \default_output_format default \output_sync 0 \bibtex_command default \index_command default \paperfontsize default \spacing single \use_hyperref false \papersize default \use_geometry true \use_package amsmath 1 \use_package amssymb 1 \use_package cancel 1 \use_package esint 1 \use_package mathdots 1 \use_package mathtools 1 \use_package mhchem 1 \use_package stackrel 1 \use_package stmaryrd 1 \use_package undertilde 1 \cite_engine basic \cite_engine_type default \biblio_style plain \use_bibtopic false \use_indices false \paperorientation portrait \suppress_date false \justification false \use_refstyle 1 \use_minted 0 \index Index \shortcut idx \color #008000 \end_index \leftmargin 1cm \topmargin 1cm \rightmargin 1cm \bottommargin 2cm \headheight 1cm \headsep 1cm \footskip 1cm \secnumdepth 3 \tocdepth 3 \paragraph_separation indent \paragraph_indentation default \is_math_indent 0 \math_numbering_side default \quotes_style german \dynamic_quotes 0 \papercolumns 1 \papersides 1 \paperpagestyle default \tracking_changes false \output_changes false \html_math_output 0 \html_css_as_file 0 \html_be_strict false \end_header \begin_body \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \backslash newcommand \backslash euler{e} \end_layout \end_inset \end_layout \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \backslash setlength{ \backslash columnseprule}{0.2pt} \backslash begin{multicols}{2} \end_layout \end_inset \end_layout \begin_layout Paragraph Izjavni račun \end_layout \begin_layout Standard \begin_inset Formula $\forall\exists$ \end_inset , \begin_inset Formula $\neg$ \end_inset , \begin_inset Formula $\wedge\uparrow\downarrow$ \end_inset , \begin_inset Formula $\vee\oplus$ \end_inset , \begin_inset Formula $\Rightarrow$ \end_inset (left to right), \begin_inset Formula $\Leftrightarrow$ \end_inset \end_layout \begin_layout Standard absorbcija: \begin_inset Formula $a\wedge\left(b\vee a\right)\sim a,\quad a\vee\left(b\wedge a\right)\sim a$ \end_inset \end_layout \begin_layout Standard kontrapozicija: \begin_inset Formula $a\Rightarrow b\quad\sim\quad\neg a\vee b$ \end_inset \end_layout \begin_layout Standard osnovna konjunkcija \begin_inset Formula $\coloneqq$ \end_inset minterm \end_layout \begin_layout Standard globina \begin_inset Formula $\coloneqq$ \end_inset \begin_inset Formula $\begin{cases} 1 & \text{izraz nima veznikov}\\ 1+\max\left\{ A_{1}\dots A_{n}\right\} & A_{i}\text{ param. zun. vezn.} \end{cases}$ \end_inset \end_layout \begin_layout Standard \begin_inset Formula $A_{1},\dots,A_{n},B$ \end_inset je pravilen sklep, če \begin_inset Formula $\vDash\bigwedge_{k=1}^{n}A_{k}\Rightarrow B$ \end_inset . \begin_inset Note Note status open \begin_layout Plain Layout zaključek \begin_inset Formula $B$ \end_inset drži pri vseh tistih naborih vrednostih spremenljivk, pri katerih hkrati držijo vse predpostavke \begin_inset Formula $A_{i}$ \end_inset . \end_layout \end_inset \end_layout \begin_layout Paragraph \series bold Pravila sklepanja \end_layout \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \backslash begin{align*} \end_layout \begin_layout Plain Layout && A, A \backslash Rightarrow B & \backslash vDash B && \backslash text{ \backslash emph{modus ponens}} && \backslash text{M. P.} \backslash \backslash \end_layout \begin_layout Plain Layout && A \backslash Rightarrow B, \backslash neg B & \backslash vDash \backslash neg A && \backslash text{ \backslash emph{modus tollens}} && \backslash text{M. T.} \backslash \backslash \end_layout \begin_layout Plain Layout && A \backslash wedge B, \backslash neg B & \backslash vDash A && \backslash text{ \backslash emph{disjunktivni silogizem}} && \backslash text{D. S.} \backslash \backslash \end_layout \begin_layout Plain Layout && A \backslash Rightarrow B, B \backslash Rightarrow C & \backslash vDash A \backslash Rightarrow C && \backslash text{ \backslash emph{hipotetični silogizem}} && \backslash text{H. S} \backslash \backslash \end_layout \begin_layout Plain Layout && A, B & \backslash vDash A \backslash wedge B && \backslash text{ \backslash emph{združitev}} && \backslash text{Zd.} \backslash \backslash \end_layout \begin_layout Plain Layout && A \backslash wedge B & \backslash vDash A && \backslash text{ \backslash emph{poenostavitev}} && \backslash text{Po.} \backslash \backslash \end_layout \begin_layout Plain Layout \backslash end{align*} \end_layout \end_inset \end_layout \begin_layout Standard Protiprimer \begin_inset Formula $1,\dots,1\vDash0$ \end_inset dokaže nepravilnost sklepa. \end_layout \begin_layout Paragraph \series bold Pomožni sklepi \series default : \end_layout \begin_layout Itemize Pogojni sklep (P.S.): \begin_inset ERT status open \begin_layout Plain Layout \backslash newline \end_layout \end_inset \begin_inset Formula $A_{1},\dots,A_{n}\vDash B\Rightarrow C\quad\sim\quad A_{1},\dots,A_{n},B\vDash C$ \end_inset \end_layout \begin_layout Itemize S protislovjem (R.A. – \emph on reduction ad absurdum \emph default ): \begin_inset Formula $A_{1},\dots,A_{n}\vDash B\quad\sim\quad A_{1},\dots,A_{n},\neg B\vDash0$ \end_inset \end_layout \begin_layout Itemize Analiza primerov (A. P.): \begin_inset Formula $A_{1},\dots,A_{n},B_{1}\vee B_{2}\vDash C\sim\left(A_{1},\dots,A_{n},B_{1}\vDash C\right)\wedge\left(A_{1},\dots,A_{n},B_{2}\vDash C\right)$ \end_inset \end_layout \begin_layout Itemize \begin_inset Formula $A_{1},\dots,A_{n},B_{1}\wedge B_{2}\vDash C\quad\sim\quad A_{1},\dots,A_{n},B_{1},B_{2}\vDash C$ \end_inset \end_layout \begin_layout Paragraph Predikatni račun \end_layout \begin_layout Standard \begin_inset Formula $P:D^{n}\longrightarrow\left\{ 0,1\right\} $ \end_inset \end_layout \begin_layout Standard De Morganov zakon negacije: \end_layout \begin_layout Itemize \begin_inset Formula $\forall x:\neg P\left(x\right)\quad\sim\quad\neg\exists x:P\left(x\right)$ \end_inset \end_layout \begin_layout Itemize \begin_inset Formula $\exists x:\neg P\left(x\right)\quad\sim\quad\neg\forall x:P\left(x\right)$ \end_inset \end_layout \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \end_layout \end_inset \end_layout \begin_layout Standard Izjava je zaprta izjavna formula, torej taka, ki ne vsebuje prostih ( \begin_inset Formula $=$ \end_inset nevezanih) nastopov spremenljivk. \end_layout \begin_layout Paragraph Množice \end_layout \begin_layout Standard \begin_inset Formula $^{\mathcal{C}},\cap\backslash,\cup\oplus$ \end_inset (left to right) \end_layout \begin_layout Standard Distributivnost: \begin_inset Formula $\cup\cap$ \end_inset , \begin_inset Formula $\cap\cup$ \end_inset , \begin_inset Formula $\left(\mathcal{A}\oplus\mathcal{B}\right)\cap\mathcal{C}=\left(\mathcal{A\cap\mathcal{C}}\right)\oplus\left(\mathcal{B}\cap\mathcal{C}\right)$ \end_inset \end_layout \begin_layout Standard Asociativnost: \begin_inset Formula $\oplus\cup\cap$ \end_inset . Distributivnost: \begin_inset Formula $\oplus\cup\cap$ \end_inset \end_layout \begin_layout Standard Absorbcija: \begin_inset Formula $\mathcal{A}\cup\left(\mathcal{A}\cap\mathcal{B}\right)=\mathcal{A}=A\cap\left(\mathcal{A}\cup\mathcal{B}\right)$ \end_inset \end_layout \begin_layout Standard \begin_inset Formula $\mathcal{A}\subseteq\mathcal{B}\Leftrightarrow\mathcal{A}\cup\mathcal{B}=\mathcal{B}\Leftrightarrow\mathcal{A}\cup\mathcal{B}=\mathcal{A}\Leftrightarrow\mathcal{A}\backslash\mathcal{B}=\emptyset\Leftrightarrow\mathcal{B}^{\mathcal{C}}\subseteq\mathcal{A^{\mathcal{C}}}$ \end_inset \end_layout \begin_layout Standard \begin_inset Formula $\mathcal{A}=\mathcal{B}\Longleftrightarrow\mathcal{A\oplus\mathcal{B}}=\emptyset$ \end_inset \end_layout \begin_layout Standard \begin_inset Formula $\mathcal{A}=\emptyset\wedge\mathcal{B}=\emptyset\Longleftrightarrow\mathcal{A}\cup\mathcal{B}=\emptyset$ \end_inset \end_layout \begin_layout Standard \begin_inset Formula $\left(\mathcal{X}\cap\mathcal{P}\right)\cup\left(\mathcal{X^{C}}\cap\mathcal{Q}\right)=\emptyset\Longleftrightarrow\text{\ensuremath{\mathcal{Q\subseteq X}\subseteq\mathcal{P^{C}}}}$ \end_inset \end_layout \begin_layout Standard \begin_inset Formula $\mathcal{A}\backslash\mathcal{B}\sim\mathcal{A}\cap\mathcal{B}^{C}$ \end_inset \end_layout \begin_layout Standard \begin_inset Formula $\mathcal{X}\cup\mathcal{X^{C}}=\emptyset$ \end_inset \end_layout \begin_layout Standard \begin_inset Formula $\mathcal{W}=\mathcal{W}\cap\mathcal{U}=\mathcal{W\cap}\left(\mathcal{X}\cup\mathcal{X^{C}}\right)=\left(\mathcal{W}\cap\mathcal{X}\right)\cup\left(\mathcal{W}\cap\mathcal{X^{C}}\right)$ \end_inset \end_layout \begin_layout Standard \begin_inset Formula $\mathcal{A}\oplus\mathcal{B}=\left(\mathcal{A}\backslash\mathcal{B}\right)\cup\left(\mathcal{B\backslash\mathcal{A}}\right)$ \end_inset \end_layout \begin_layout Paragraph \series bold Lastnosti binarnih relacij \end_layout \begin_layout Paragraph \begin_inset ERT status open \begin_layout Plain Layout \backslash begin{align*} \end_layout \begin_layout Plain Layout && \backslash forall a \backslash in A : & \backslash left(a R a \backslash right) && \backslash text{refleksivnost} \backslash \backslash \end_layout \begin_layout Plain Layout && \backslash forall a,b \backslash in A : & \backslash left(a R b \backslash Rightarrow b R a \backslash right)&& \backslash text{simetričnost} \backslash \backslash \end_layout \begin_layout Plain Layout && \backslash forall a,b \backslash in A : & \backslash left(a R b \backslash wedge b R a \backslash Rightarrow a=b \backslash right) && \backslash text{antisimetričnost} \backslash \backslash \end_layout \begin_layout Plain Layout && \backslash forall a,b,c \backslash in A : & \backslash left(a R b \backslash wedge b R c \backslash Rightarrow a R c \backslash right) && \backslash text{tranzitivnost} \backslash \backslash \end_layout \begin_layout Plain Layout && \backslash forall a \backslash in A : & \backslash neg \backslash left(a R a \backslash right) && \backslash text{irefleksivnost} \backslash \backslash \end_layout \begin_layout Plain Layout && \backslash forall a,b \backslash in A: & \backslash left(a R b \backslash Rightarrow \backslash neg \backslash left(b R a \backslash right) \backslash right) && \backslash text{asimetričnost} \backslash \backslash \end_layout \begin_layout Plain Layout && \backslash forall a,b,c \backslash in A:& \backslash left(a R b \backslash wedge b R c \backslash Rightarrow \backslash neg \backslash left(a R c \backslash right) \backslash right) && \backslash text{itranzitivnost} \backslash \backslash \end_layout \begin_layout Plain Layout && \backslash forall a,b \backslash in A:& \backslash left(a \backslash not=b \backslash Rightarrow \backslash left(a R b \backslash vee b R a \backslash right) \backslash right) && \backslash text{sovisnost} \backslash \backslash \end_layout \begin_layout Plain Layout && \backslash forall a,b \backslash in A:& \backslash left(a R b \backslash vee b R a \backslash right)&& \backslash text{stroga sovisnost} \backslash \backslash \end_layout \begin_layout Plain Layout && \backslash forall a,b,c \backslash in A:& \backslash left(aRb \backslash wedge aRc \backslash Rightarrow b=c \backslash right)&& \backslash text{enoličnost} \end_layout \begin_layout Plain Layout \backslash end{align*} \end_layout \end_inset Sklepanje s kvantifikatorji \end_layout \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \backslash begin{align*} \end_layout \begin_layout Plain Layout && \backslash exists x:P \backslash left(x \backslash right) \backslash longrightarrow& x_0 \backslash coloneqq x, P \backslash left(x \backslash right) && \backslash text{eksistenčna specifikacija} \backslash \backslash \end_layout \begin_layout Plain Layout && P \backslash left(x_0 \backslash right) \backslash longrightarrow& \backslash exists x:P \backslash left(x \backslash right)&& \backslash text{eksistenčna generalizacija} \backslash \backslash \end_layout \begin_layout Plain Layout && \backslash forall x:P \backslash left(x \backslash right) \backslash longrightarrow& x_0 \backslash coloneqq x, P \backslash left(x \backslash right)&& \backslash text{univerzalna specifikacija} \backslash \backslash \end_layout \begin_layout Plain Layout && \backslash text{poljub. } x_0, P \backslash left(x_0 \backslash right) \backslash longrightarrow& \backslash forall x:P \backslash left(x \backslash right)&& \backslash text{univerzalna generalizacija} \end_layout \begin_layout Plain Layout \backslash end{align*} \end_layout \end_inset \begin_inset Formula $R\subseteq A\times B:aR\oplus Sb\sim\left(a,b\right)\in R\backslash S\vee\left(a,b\right)\in S\backslash R\sim aRb\oplus aSb$ \end_inset \begin_inset Newline newline \end_inset \begin_inset Formula $R^{-1}\coloneqq\left\{ \left(b,a\right);\left(a,b\right)\in R\right\} :\quad aRb\sim bR^{-1}a$ \end_inset \begin_inset Newline newline \end_inset \begin_inset Formula $R*S\coloneqq\left\{ \left(a,c\right);\exists b:\left(aRb\wedge bSc\right)\right\} :R^{2}\coloneqq R*R,R^{n+1}\coloneqq R^{n}*R$ \end_inset \begin_inset Newline newline \end_inset \begin_inset Formula $\left(R^{-1}\right)^{-1}=R,\left(R\cup S\right)^{-1}=R^{-1}\cup S^{-1},\left(R\cap S\right)^{-1}=R^{-1}\cap S^{-1}$ \end_inset \begin_inset Newline newline \end_inset \begin_inset Formula $\left(R*S\right)=R^{-1}*S^{-1}$ \end_inset . \begin_inset Formula $*\cup$ \end_inset in \begin_inset Formula $\cup*$ \end_inset sta distributivni. \end_layout \begin_layout Standard \begin_inset Formula $R^{+}=R\cup R^{2}\cup R^{3}\cup\dots,\quad R^{*}=I\cup R^{+}$ \end_inset \begin_inset Newline newline \end_inset Ovojnica \begin_inset Formula $R^{L}\supseteq R$ \end_inset je najmanjša razširitev \begin_inset Formula $R$ \end_inset , ki ima lastnost \begin_inset Formula $L$ \end_inset . \end_layout \begin_layout Standard \begin_inset Formula $R^{\text{ref}}\coloneqq I\cup R,R^{\text{sim}}\coloneqq R\cup R^{-1},R^{\text{tranz}}=R^{+},R^{\text{tranz+ref}}=R^{*}$ \end_inset \end_layout \begin_layout Standard Ekvivalenčna rel. je simetrična, tranzitivna in refleksivna. \end_layout \begin_layout Standard Ekvivalenčni razred: \begin_inset Formula $R\left[x\right]\coloneqq\left\{ y;xRy\right\} $ \end_inset \end_layout \begin_layout Standard Faktorska množica: \begin_inset Formula $A/R\coloneqq\left\{ R\left[x\right];x\in A\right\} $ \end_inset \end_layout \begin_layout Standard \begin_inset Formula $\vec{\mathcal{B}}\text{ razbitje}A\Longleftrightarrow\bigcup_{i}\mathcal{B}_{i}=A\wedge\forall i\mathcal{B}_{i}\not=\emptyset\wedge\mathcal{B}_{i}\cap\mathcal{B}_{j}=\emptyset,i\not=j$ \end_inset \end_layout \begin_layout Paragraph Urejenosti \end_layout \begin_layout Standard \begin_inset Formula $\left(M,\preccurlyeq\right)$ \end_inset \end_layout \begin_layout Standard Delna: refl., antisim. in tranz. Linearna: delna, sovisna \end_layout \begin_layout Standard def.: \begin_inset Formula $x\prec y\Longleftrightarrow x\preccurlyeq y\wedge x\not=y$ \end_inset \end_layout \begin_layout Standard \begin_inset Formula $x\text{ je nepo. predh. }y\Longleftrightarrow x\prec y\wedge\neg\exists z\in M:\left(x\prec z\wedge z\prec y\right)$ \end_inset \end_layout \begin_layout Standard \begin_inset Formula $a\in M\text{ je minimalen}\Longleftrightarrow\forall x\in M\left(x\preccurlyeq a\Rightarrow x=a\right)$ \end_inset \end_layout \begin_layout Standard \begin_inset Formula $a\in M\text{ je maksimalen}\Longleftrightarrow\forall x\in M\left(a\preccurlyeq x\Rightarrow x=a\right)$ \end_inset \end_layout \begin_layout Standard \begin_inset Formula $a\in M\text{ je prvi}\Longleftrightarrow\forall x\in M:\left(a\preccurlyeq x\right)$ \end_inset \end_layout \begin_layout Standard \begin_inset Formula $a\in M\text{ je zadnji}\Longleftrightarrow\forall x\in M:\left(x\preccurlyeq a\right)$ \end_inset \end_layout \begin_layout Standard \begin_inset Formula $M_{1}\times M_{2}$ \end_inset : \begin_inset Formula $\left(a_{1},b_{1}\right)\preccurlyeq\left(a_{2},b_{2}\right)\coloneqq a_{1}\preccurlyeq a_{2}\wedge b_{1}\preccurlyeq b_{2}$ \end_inset \end_layout \begin_layout Standard Srečno! \end_layout \begin_layout Paragraph Funkcijska polnost \end_layout \begin_layout Standard \begin_inset Formula $T_{0},$ \end_inset \begin_inset Formula $T_{1}$ \end_inset , \begin_inset Formula $S$ \end_inset – \begin_inset Formula $f\left(\vec{x}\right)=\neg f\left(\vec{x}\oplus\vec{1}\right)$ \end_inset , \begin_inset Formula $L$ \end_inset , \begin_inset Formula $M$ \end_inset \end_layout \begin_layout Standard \begin_inset Formula $L$ \end_inset – \begin_inset Formula $f\left(\vec{x}\right)=\left[\begin{array}{ccc} a_{0} & \dots & a_{n}\end{array}\right]^{T}\oplus\wedge\left[\begin{array}{cccc} 1 & x_{1} & \dots & x_{n}\end{array}\right]$ \end_inset \end_layout \begin_layout Standard \begin_inset Formula $M$ \end_inset – \begin_inset Formula $\forall i,j:\vec{w_{i}}<\vec{w_{j}}\Rightarrow f\left(\vec{w_{i}}\right)\leq f\left(\vec{w_{j}}\right)$ \end_inset \end_layout \begin_layout Standard \begin_inset Newpage pagebreak \end_inset \end_layout \begin_layout Paragraph Supermum in infimum \end_layout \begin_layout Standard \begin_inset Formula $\sup\left(a,b\right)$ \end_inset in \begin_inset Formula $\inf\left(a,b\right)$ \end_inset v \begin_inset Formula $\left(M,\preceq\right)$ \end_inset \end_layout \begin_layout Standard \begin_inset Formula $\sup\left(a,b\right)\coloneqq j\ni:a\preceq j\wedge b\preceq j\wedge\forall x:a\preceq x\wedge b\preceq x\Rightarrow j\preceq x$ \end_inset \end_layout \begin_layout Standard \begin_inset Formula $\inf\left(a,b\right)\coloneqq j\ni:j\preceq a\wedge j\preceq b\wedge\forall x:x\preceq a\wedge x\preceq b\Rightarrow x\preceq j$ \end_inset \end_layout \begin_layout Standard Relacijska \series bold def. mreže \series default : Delna urejenost je mreža \begin_inset Formula $\Leftrightarrow\forall a,b\in M:\exists\sup\left(a,b\right)\wedge\exists\inf\left(a,b\right)$ \end_inset \end_layout \begin_layout Standard Algebrajska \series bold def. mreže \series default : \begin_inset Formula $\left(M,\wedge,\vee\right)$ \end_inset je mreža, če veljata idempotentnosti \begin_inset Formula $a\vee a=a\wedge a=a$ \end_inset , komutativnosti, asociativnosti in absorpciji. \end_layout \begin_layout Standard Mreža je \series bold omejena \series default \begin_inset Formula $\Leftrightarrow\exists0,1\in M\ni:\forall x\in M:0\preceq x\preceq1$ \end_inset \end_layout \begin_layout Standard Mreža je \series bold komplementarna \series default \begin_inset Formula $\Leftrightarrow\forall a\in M\exists a^{-1}\in M\ni:a\wedge a^{-1}\sim0\text{ in }a\vee a^{-1}\sim1$ \end_inset \end_layout \begin_layout Standard V \series bold distributivni mreži \series default veljata obe distributivnosti. \end_layout \begin_layout Standard \begin_inset Formula $\sup\left(a,b\right)\sim a\wedge b,\quad\inf\left(a,b\right)\sim a\vee b$ \end_inset \end_layout \begin_layout Standard V delni urejenosti velja: \begin_inset Formula $a\preceq b\Leftrightarrow a=\inf\left(a,b\right)\Leftrightarrow b=\sup\left(a,b\right)$ \end_inset \end_layout \begin_layout Standard \begin_inset Formula $M_{5},N_{5}$ \end_inset nista distributivni. \end_layout \begin_layout Standard \series bold \begin_inset Formula $\left(N,\wedge,\vee\right)$ \end_inset \series default je \series bold podmreža \series default \begin_inset Formula $\left(M,\wedge,\vee\right)\Leftrightarrow\emptyset\not=N\subseteq M,\forall a,b\in N:a\vee b\in N\text{ in }a\wedge b\in N$ \end_inset \end_layout \begin_layout Standard \series bold Boolova algebra \series default je komplementarna distributivna mreža. Tedaj ima vsak element natanko en komplement in velja dualnost ter De Morganova zakona. \end_layout \begin_layout Paragraph Funkcije \end_layout \begin_layout Standard Funkcija \begin_inset Formula $f$ \end_inset je preslikava, če je \begin_inset Formula $D_{f}$ \end_inset domena. \end_layout \begin_layout Itemize \begin_inset Formula $f,g\text{ injekciji }\Rightarrow g\circ f\text{ injekcija}$ \end_inset \end_layout \begin_layout Itemize \begin_inset Formula $f,g\text{ surjekciji }\Rightarrow g\circ f\text{ surjekcija}$ \end_inset \end_layout \begin_layout Itemize \begin_inset Formula $g\circ f\text{ injekcija }\Rightarrow f\text{ injekcija}$ \end_inset \end_layout \begin_layout Itemize \begin_inset Formula $g\circ f\text{ surjekcija }\Rightarrow g\text{ surjekcija}$ \end_inset \end_layout \begin_layout Standard Slika množice \begin_inset Formula $A_{1}\subseteq A$ \end_inset : \begin_inset Formula $f\left(A_{1}\right)\coloneqq\left\{ y\in B;\exists x\in A_{1}\ni:f\left(x\right)=y\right\} $ \end_inset . Praslika \begin_inset Formula $B_{1}\subseteq B$ \end_inset : \begin_inset Formula $f^{-1}\left(B_{1}\right)=\left\{ x\in A:\exists y\in B_{1}\ni:f\left(x\right)=y\right\} $ \end_inset . \end_layout \begin_layout Paragraph Permutacije \end_layout \begin_layout Standard \begin_inset Formula $\pi=\pi^{-1}\Leftrightarrow\pi$ \end_inset je konvolucija. \end_layout \begin_layout Standard V disjunktnih ciklih velja: \begin_inset Formula $C_{1}C_{2}=C_{2}C_{1}$ \end_inset . \end_layout \begin_layout Standard V ciklih velja: \begin_inset Formula $C_{2}^{-1}C_{1}^{-1}=\left(C_{1}C_{2}\right)^{-1}$ \end_inset \end_layout \begin_layout Standard Razcep na disjunktne cikle je enoličen. \end_layout \begin_layout Standard Neenolično razbitje cikla dolžine \begin_inset Formula $n$ \end_inset na produkt \begin_inset Formula $n-1$ \end_inset transpozicij: \begin_inset Formula $\left(a_{1}a_{2}a_{3}a_{4}a_{5}\right)=\left(a_{1}a_{2}\right)\left(a_{1}a_{3}\right)\left(a_{1}a_{4}\right)\left(a_{1}a_{5}\right)$ \end_inset . Parnost števila transpozicij je enolična. \begin_inset ERT status open \begin_layout Plain Layout \backslash newcommand \backslash red{ \backslash text{red}} \backslash newcommand \backslash sgn{ \backslash text{sgn}} \backslash newcommand \backslash lcm{ \backslash text{lcm}} \end_layout \end_inset \begin_inset Formula $\sgn\pi=\sgn\pi^{-1}$ \end_inset . \end_layout \begin_layout Standard \begin_inset Formula $\red\pi$ \end_inset je najmanjše \begin_inset Formula $k\ni:\pi^{k}=id$ \end_inset \end_layout \begin_layout Standard Za cikel \begin_inset Formula $C$ \end_inset dolžine \begin_inset Formula $n$ \end_inset velja: \begin_inset Formula $C^{n}=id$ \end_inset — \begin_inset Formula $\red C=n$ \end_inset \end_layout \begin_layout Standard Red produkta disjunktnih ciklov dolžin \begin_inset Formula $\vec{n}$ \end_inset je \begin_inset Formula $\lcm\left(\vec{n}\right)$ \end_inset . \end_layout \begin_layout Paragraph Moči končnih množic \end_layout \begin_layout Standard \begin_inset Formula $\left|A\times B\right|=\left|A\right|\left|B\right|$ \end_inset , \begin_inset Formula $\left|\mathcal{P}\left(A\right)\right|=2^{\left|A\right|}$ \end_inset , \begin_inset Formula $\left|B^{A}\right|=\left|B\right|^{\left|A\right|}$ \end_inset , \begin_inset Formula $\left|B\backslash A\right|=\left|B\right|-\left|A\cap B\right|$ \end_inset \end_layout \begin_layout Standard Princip vključitve in izključitve: \begin_inset Formula $\left|A_{1}\cup A_{2}\cup\cdots\cup A_{n}\right|=\sum_{i=1}^{n}\left(-1\right)^{i+1}S_{i}$ \end_inset , kjer \begin_inset Formula $S_{k}\coloneqq\sum_{I\subseteq\left\{ 1,\dots,n\right\} ,\left|I\right|=k}\bigcap_{i\in I}A_{i}$ \end_inset \end_layout \begin_layout Paragraph Neskončne množice \end_layout \begin_layout Standard \begin_inset Formula $A$ \end_inset in \begin_inset Formula $B$ \end_inset sta enakomočni: \begin_inset Formula $A\sim B\Leftrightarrow\exists\text{bijekcija }f:A\to B$ \end_inset . \begin_inset Formula $\sim$ \end_inset je ekvivalenčna relacija. \end_layout \begin_layout Standard Ekvivalenčni razredi: \begin_inset Formula $0,1,2,\dots,\aleph_{0},c$ \end_inset . \end_layout \begin_layout Standard \begin_inset Formula $A$ \end_inset je neskončna \begin_inset Formula $\Leftrightarrow\exists B\subset A\ni:A\sim B$ \end_inset , drugače je končna. \end_layout \begin_layout Standard \begin_inset Formula $A$ \end_inset ima manjšo ali enako moč kot \begin_inset Formula $B$ \end_inset zapišemo: \begin_inset Formula $A\leq B\Leftrightarrow\exists\text{injekcija }f:A\to B$ \end_inset . Označimo \begin_inset Formula $A