1 files changed, 1136 insertions, 0 deletions

diff --git a/šola/ds1/kolokvij1.lyx b/šola/ds1/kolokvij1.lyx
new file mode 100644
index 0000000..4cbcea1
--- /dev/null
+++ b/šola/ds1/kolokvij1.lyx
@@ -0,0 +1,1136 @@
+#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 0cm
+\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 Title
+List s formulami za 1.
+ kolokvij Diskretnih struktur 1
+\end_layout
+
+\begin_layout Author
+
+\noun on
+Anton Luka Šijanec
+\end_layout
+
+\begin_layout Date
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+today
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\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 B && 
+\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}},\cup\backslash,\cup\oplus$
+\end_inset
+
+ (left to right)
+\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}=\left\{ \right\} \Leftrightarrow\mathcal{B}^{\mathcal{C}}\subseteq\mathcal{A^{\mathcal{C}}}$
+\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 simetreič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=\left\{ \right\} \wedge\mathcal{B}_{i}\cap\mathcal{B}_{j}=\left\{ \right\} ,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
+TODO
+\end_layout
+
+\begin_layout Standard
+Postovi teoremi za funkcijsko polnost, preglej še zapiske s pisalnega stroja.
+\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