Istinitosne tablice

Konjukcija

\(p\) \(q\) \(p\wedge q\)
\(\top \) \(\top \) \(\top \)
\(\top \) \(\perp\) \(\perp\)
\(\perp\) \(\top \)\(\perp\)
\(\perp\) \(\perp\) \(\perp\)

Disjunkcija

\(p\) \(q\) \(p\vee q\)
\(\top \) \(\top \) \(\top \)
\(\top \) \(\perp\) \(\top \)
\(\perp\) \(\top \) \(\top \)
\(\perp\) \(\perp\) \(\perp\)

Implikacija

\(p\) \(q\) \(p \Rightarrow q\)
\(\top \) \(\top \) \(\top \)
\(\top \) \(\perp\) \(\perp\)
\(\perp\) \(\top \) \(\top \)
\(\perp\) \(\perp\) \(\top \)

Ekvivalencija

\(p\) \(q\) \(p \Leftrightarrow q\)
\(\top \) \(\top \) \(\top \)
\(\top \) \(\perp\) \(\perp\)
\(\perp\) \(\top \) \(\perp\)
\(\perp\) \(\perp\) \(\top \)

Negacija

\(p\) \(\neg p\)
\(\top \) \(\perp \)
\(\perp\) \(\top \)

Skupovi i skupovne operacije

Presek skupova $$A\cap B=\left \{ x|x\in A\wedge x\in B \right \}$$

Unija skupova $$A\cup B=\left \{ x|x\in A\vee x\in B \right \}$$

Razlika skupova $$A\setminus B=\left \{ x|x\in A\wedge x\notin B \right \}$$

Komplement skupa $$A'=\left \{ x|x\notin A \right \}$$

Partitivni skup \(P(A)\) skupa \(A\) je skup svih podskupova skupa \(A\).

Dekartov proizvod $$A\times B=\left \{ (a,b)|a\in A\wedge b\in B \right \}$$

Relacije

Binarna relacija skupa \(A\) je svaki podskup \(\rho\) skupa \(A\). Relacija je...

  • refleksivna (R), ako je \((\forall x\in A)(x\rho x)\);
  • simetrična (S), ako je \((\forall x,y\in A)(x\rho y\Rightarrow y\rho x)\);
  • antisimetrična (A), ako je \((\forall x,y\in A)(x\rho y\wedge y\rho x\Rightarrow x=y)\);
  • tranzitivna (T), ako je \((\forall x,y,z\in A)(x\rho y\wedge y\rho z\Rightarrow x\rho z)\).

Relaciju koja je R, S, T nazivamo relacija ekvivalencije.

Relaciju koja je R, A, T nazivamo relacija poretka.

Ako je \(\sim \) relacija ekvivalencije na skupu \(A\), tada skup \(C_a=\left \{ x|x\in A,a\sim x \right \}\), gde je \(a\in A\) nazivamo klasom ekvivalencije elementa \(a\). Osobine:

  • \((\forall a\in A)C_a\neq \varnothing \);
  • ako je \(a \sim b\), onda je \(C_a=C_b\);
  • ako nije \(a \sim b\), onda je \(C_a\cap C_b=\varnothing \).

Funkcije

Preslikavanje \(f:A\rightarrow B\) je relacija \(f\subset A\times B\) koja ima svojstvo da je svaki element skupa \(A\) u relaciji \(f\) sa tačno jednim elementom skupa \(B\).

Funkcija je "1-1" ako $$(\forall x_1,x_2\in A)(x_1\neq x_2\Rightarrow f(x_1)\neq f(x_2))$$ ili $$(\forall x_1,x_2\in A)(f(x_1)= f(x_2)\Rightarrow x_1=x_2)$$

Funkcija je "na" ako $$(\forall y\in B)(\exists x\in A)(y=f(x))$$

Ako su \(f:A\rightarrow B\) i \(g:B\rightarrow C\) preslikavanja, tada je \(g\circ f:A\rightarrow C\) proizvod (kompozicija, slaganje) preslikavanja \(f\) i \(g\) i definisan je sa $$(\forall x\in A)((g \circ f)(x)=g(f(x)))$$

Ako je \(f:A\rightarrow B\) "1-1" i "na" preslikavanje, tada postoji inverzna funkcija \(f^{-1}:B\rightarrow A\), takva da je $$(f^{-1}\circ f)(x)=x$$