Diskreettejen rakenteiden termejä

Käsitteitä

• Tautologia
  • Aina tosi riippumatta muuttujien arvoista
• Kontradiktio
  • Aina epätosi riippumatta muuttujien arvoista
• Induktio
  • TODO

Funktio

• F(x) = y
• surjektio
  • many to one, ei yksinäisiä Y, mutta X voi olla
  • y ei voi enemmän kuin x
• injektio
  • one to one, Ei yksinäisiä X, mutta y voi olla
  • y saadaan vain yhdellä tecityllä x:n arvolla
  • x määrä ei voi olla suurempi kuin y
• bijektio
  • surjektio JA injektio
  • one to one, ei yksinäisiä

Relaatio

• Suhde

Kombinatoriikka

Termi	Kaava	Järjestyksellä väliä	Toisto sallittu	Muuta
Otos	n^k	x	x
Permutaatio	n! / (n-k)!	x	-	Joukon permutaatio on itsensä bijektio
Valikoima		-	x
Kombinaatio		-	-

Ongelmatyyppien jaottelu

Matemaattisia merkintöjä

Loogiset konnektiivit

• ¬A
  • ei A
  • Negaatio
• A ∧ B
  • A ja B
  • Konjuktio
• A V B
  • A tai B
  • Disjunktio
• A => B
  • jos A niin B
  • Implikaatio
• A <=> B
  • jos ja vain jos A niin B
  • Ekvivalenssi

Kvanttorit

• ∀ x
  • kaikilla x
  • Universaalikvanttori
• ∀ x ∈ A
  • Kaikilla joukon A alkioilla x
• Ǝ x
  • On olemassa x (ainakin yksi)
  • Olemassaolokvanttori