summaryrefslogtreecommitdiffstats
path: root/šola/ds1
diff options
context:
space:
mode:
authorAnton Luka Šijanec <anton@sijanec.eu>2024-02-02 12:49:38 +0100
committerAnton Luka Šijanec <anton@sijanec.eu>2024-02-02 12:49:38 +0100
commit53b31c6ea98363871c7c6bdb8e662ad825e3f47a (patch)
treeafb56424b413287bb9189a014475286bf06dc706 /šola/ds1
parentla2kol (diff)
downloadr-53b31c6ea98363871c7c6bdb8e662ad825e3f47a.tar
r-53b31c6ea98363871c7c6bdb8e662ad825e3f47a.tar.gz
r-53b31c6ea98363871c7c6bdb8e662ad825e3f47a.tar.bz2
r-53b31c6ea98363871c7c6bdb8e662ad825e3f47a.tar.lz
r-53b31c6ea98363871c7c6bdb8e662ad825e3f47a.tar.xz
r-53b31c6ea98363871c7c6bdb8e662ad825e3f47a.tar.zst
r-53b31c6ea98363871c7c6bdb8e662ad825e3f47a.zip
Diffstat (limited to 'šola/ds1')
-rw-r--r--šola/ds1/izpit.lyx1911
1 files changed, 1911 insertions, 0 deletions
diff --git a/šola/ds1/izpit.lyx b/šola/ds1/izpit.lyx
new file mode 100644
index 0000000..f442310
--- /dev/null
+++ b/šola/ds1/izpit.lyx
@@ -0,0 +1,1911 @@
+#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<B\Leftrightarrow A\leq B\wedge A\not\sim B$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $A\leq B\wedge B\leq A\Leftrightarrow A\sim B,\quad\forall A,B:A<B\vee B<A\vee A\sim B$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $\forall A\not=\emptyset,B:A\leq B\Leftrightarrow\exists\text{surjekcija }g:B\to A$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $\forall$
+\end_inset
+
+neskončna množica vsebuje števno neskončno podmnožico.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $A<\mathcal{P}\left(A\right)$
+\end_inset
+
+, posledično
+\begin_inset Formula $A<\mathcal{P}\left(A\right)<\mathcal{P}^{2}\left(A\right)<\mathcal{P}^{2}\left(A\right)<\cdots$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $\mathbb{N}<\mathcal{P}\left(\mathbb{N}\right)=c<\mathcal{P}^{2}\left(\mathbb{N}\right)<\cdots$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Za neskončno
+\begin_inset Formula $A$
+\end_inset
+
+ in končno
+\begin_inset Formula $B$
+\end_inset
+
+ velja
+\begin_inset Formula $A\backslash B\sim A$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+Za neskončno
+\begin_inset Formula $A$
+\end_inset
+
+ in števno neskončno
+\begin_inset Formula $B$
+\end_inset
+
+ velja
+\begin_inset Formula $A\sim A\cup B$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Paragraph
+Teorija števil
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $-\lfloor-x\rfloor=\lceil x\rceil,\quad-\lceil-x\rceil=\lfloor x\rfloor$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $\lceil x\rceil=\min\left\{ k\in\mathbb{Z};k\geq x\right\} ,\quad\lfloor x\rfloor=\max\left\{ k\in\mathbb{Z};k\leq x\right\} $
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $m\vert n\Leftrightarrow\exists k\in\mathbb{Z}\ni:n=km$
+\end_inset
+
+.
+
+\begin_inset Formula $\vert$
+\end_inset
+
+ je antisimetrična.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $m\vert a\wedge m\vert b\Rightarrow m\vert\left(a+b\right)$
+\end_inset
+
+,
+\begin_inset Formula $m\vert a\Rightarrow m\vert ak$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $a\bot b\Leftrightarrow\gcd\left(a,b\right)=1\Leftrightarrow m\bot\left(a\mod b\right)$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $ab=\gcd\left(a,b\right)\lcm\left(a,b\right)$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $p\in\mathbb{N}$
+\end_inset
+
+ je praštevilo
+\begin_inset Formula $\Leftrightarrow\left|\text{D}\left(p\right)\right|=2$
+\end_inset
+
+ (število deliteljev):
+\begin_inset Formula $p\in\mathbb{P}$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $a,b\in\mathbb{N},p\in\mathbb{P}$
+\end_inset
+
+:
+\begin_inset Formula $a\bot b\vee a\vert b,\quad p\vert ab\Rightarrow p\vert a\vee p\vert b$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $m\vert a-b$
+\end_inset
+
+ označimo
+\begin_inset Formula $a\equiv b\pmod m$
+\end_inset
+
+,
+\begin_inset Formula $a\mod m=b\mod m$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $a\equiv b\pmod m\Rightarrow\forall k\in\mathbb{Z}:a\overset{+}{\cdot}k\equiv b\overset{+}{\cdot}k\pmod m$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $a\equiv b\pmod m\wedge c\equiv d\pmod m\Rightarrow a\overset{+}{\overset{-}{\cdot}}c\equiv b\overset{+}{\overset{-}{\cdot}}d\pmod m$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Mali fermatov izrek:
+\begin_inset Formula $a\in\mathbb{N},p\in\mathbb{P}$
+\end_inset
+
+ velja
+\begin_inset Formula $a\equiv a^{p}\pmod p$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $p,q\in\mathbb{P}:a\equiv b\pmod p\wedge a\equiv b\pmod p\Rightarrow a\equiv b\pmod{pq}$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Eulerjeva funkcija
+\begin_inset Formula $\varphi\left(n\right)\coloneqq\left|\left\{ k\in n;1\leq k<n\wedge k\bot n\right\} \right|$
+\end_inset
+
+ — število tujih števil, manjših od n.
+
+\begin_inset Formula $p\in\mathbb{P}\Rightarrow\varphi\left(p\right)=p-1$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $p\in\mathbb{P},n\in\mathbb{N}\Rightarrow\varphi\left(p\right)=p^{n}-p^{n-1},\quad\varphi\left(a\right)\varphi\left(b\right)=\varphi\left(ab\right)$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+REA:
+\begin_inset Formula $ax+by=d$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+end{multicols}
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\end_body
+\end_document