#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 Standard
\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 ERT
status open
\begin_layout Plain Layout
\backslash
end{multicols}
\end_layout
\end_inset
\end_layout
\end_body
\end_document
