#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
