INFO102

Home > Preview

The flashcards below were created by user burntoutmatch on FreezingBlue Flashcards.


  1. Tautologi
    utsagn som alltid er sant
  2. Matematisk induksjon
    Prinsipp for å bevise predikater som er avhengig av et naturlig tall:

    Matematisk induksjon er et logisk prinsipp i matematikk som kan brukes for å bevise påstander indeksert av naturlige tall. It is useful for proving propositions that are true for all natural numbers.

    If P(1) = true, and for all values of k that are greater than or equal to 1, P(k) implies P(k+1) is true, ∀k ≥ 1 (P(k) ⇒ P(k + 1))

    • Then P(n) is true for all n ≥ 1.
    • Basically the function called is true if it implies the next number will be that number plus 1.
  3. Potensmengde
    • ρ(M) = {X| X⊆M}
    • everything in the set, plus the empty set, and the set itself
  4. Bijektiv funksjon
    både injektiv og surjektiv. den er også invertevbar.

    • a - 1
    • b - 3
    • c - 2

    {(a,b,c),(1,2,3)}
  5. injektiv
    • for alle x i domene (venstre) har bare tilknytting til en y i ko-domene (høyre)
    • altså
    • funksjon på formen f:A→B 
    • dvs f(x)=f(y) ⇒x=y, for alle x,y∊A
    • (x,y som er element i mengen A)

    • a - 3
    • b - 1

    {(a,b),(1,2,3)}
  6. surjektiv
    • For A→B
    • Hver "B" har minst en tilsvarende "A"
    • dvs f(A)=B

    • a - 1
    • b -1
    • c - 2

    {(a,b,c),(1,2)}
  7. Hamilton-graf, Hamilton-vei
    Graf der det finnes en sykel som besøker alle nodene èn gang. Den går tilbake til første node. En vei som besøker alle nodene èn gang og ikke gå tilbake.
  8. Refleksiv
    • en relasjon R på en mengde A
    • when x R x for all x ∊ A

    R er refleksiv siden x vil alltid være relatert til x. Noen som helt by “x” vil alltid ligger i samme verdensdelen “z” som seg selv. Altså hvis x er New York City kan vi si at New York City skal alltid være New York City derfor skal den alltid ligger i samme verdensdelen z som er Amerika.
  9. Symmetrisk
    • en relasjon R på en mengde A
    • when x R y ⇒ y R x for all x and y in A

    En relasjon er symmetrisk når x R y => y R x for alle x og y i A. R er symmetrisk fordi en by x er en relasjon til en annen by y fordi begge ligger i samme verdensdel z. Altså hvis x er New York City og y er Los Angeles kan vi si at New York City er relatert til Los Angeles i det samme måte som Los Angeles er relatert til New York i at de ligger i samme verdensdel z som er Amerika.
  10. ekvivalensrelasjon
    En ekvivalensrelasjon er en relasjon R på en mengde A som er refleksiv, symmetrisk og transitiv
  11. irrefleksiv
    • La R ⊆ A x A
    • (not xRx) for alle x∈A
  12. asymmetrisk
    • La R ⊆ A x A
    • xRy ⇒ (not yRx) for alle x,y∈A

    • f.eks
    • ForelderTil ⊆ (Kvinner U Menn) x (Kvinner U Menn)
    • Hvis Per er forelder til Kari så kan ikke Kari være forelder til Per.
  13. antisymmetrisk
    • en relasjon R på en mengde A
    • Hvis både x≤y og y≤x så må nødvendigvis x=y
    • when (x R y and y R x ⇒ x=y) for all x and y in A
  14. transitive
    • en relasjon R på en mengde A
    • En relasjon er transitiv når (x R y og y R z => x R z) for alle x, y og z i A. For den til å holde må x være relatert til y, y være relatert til z. Om det er sant skal x være relatert til z også.

    R er transitive siden hvis New York er relatert til Los Angeles og Los Angeles er relatert til Amerika er New York også relatert til Amerika.
  15. Topologisk sortering
    La R ⊆ A × A være en partiell ordning. Topologisk sortering mht R gir en total ordning R’ som respekterer ordningen i R: x R y ⇒ x R ’y, for alle x,y ∈ A. Topologisk sortering er arbeidet med å sortere nodene i en graf slik at naboer listes i rett innebyrdes orden. Det forutsettes at to noder bare har en rettet kant seg imellom, og at grafen er asyklisk. nodene som har kant med pil fra seg skal være sortert før de som kommer etter.
  16. sannhetstabell. For 2, 3, og 4 variabler - hvor mange rad trenger man? Hvordan setter man opp disse radene?
    • A | B - 4 rad
    • T | T
    • T | F
    • F | T
    • F | F

    • A,B,C - 8 rad
    • A har TTTTFFFF
    • B har TTFFTTFF
    • C har TFTFTFTF

    • A,B,C,D - 16 rad
    • A har TTTTTTTTFFFFFFFF
    • B har TTTTFFFFTTTTFFFF
    • C har TTFFTTFFTTFFTTFF
    • D har TFTFTFTFTFTFTFTF
  17. if P then Q (P⇒Q)
    false whenever the premise P is true and the condition Q is false. Otherwise it is true.

    • P - TTFF
    • Q - TFTF
    • (P⇒Q) - TFTT
  18. ((not Q) ⇒ (not P)) er det samme som...
    • contrapositive of (P⇒Q)
    • It is logically equivalent to (P⇒Q)
    • TFTT
  19. hva betyr ∀
    for all (some property holds for all objects concerned)
  20. hva betyr ∃
    there exists (that there exsists at least one object for which the given property holds)
  21. P(x) = x is an integer and x² = 16. Express the proposition ∃x (P(x)) in words and determine it's truth value.
    There exists at least one interger x where x² = 16. This holds true when x=4 and when x=-4. However it is the equation only needs one value in order to be true.
  22. What is the logical equivalent to not(∃x (P(x)))?
    • for x, there is not at least one x that fufills the criteria for P(x). That means that for all values of x, P(x) is never true.
    • So: ∀x (not(P(x)))
  23. not(∀x (P(x)))
    • NOT (P(x) is true for every value of x)
    • which means that x is always false.
    • logically equivalent to
    • ∃x (not(P(x))) - there exists at least one x where P(x) is false
  24. x and y are real numbers. let P(x, y) denote the predicate x+y =0. Express in words:
    (a) ∀x (∃y (P(x,y)))
    (b) ∃y (∀x (P(x,y)))
    (a) For all x, there exists at least one y for the predicate x+y=0. That is true, since for each x, the real number y=-x in order to equal 0, f.eks 4 + -4 =0, where 4=x and -4=y.

    (b) There exists at least one y, for all values of x. Meaning that the same value of y must hold true if f.eks x=1, x=2, or x=3 ect. There is not a single y value that can do this. If y = -1, it will hold true when x = 1, but not if x = 2.
  25. direct argument, contrapositive argument, and proof by contradiction
    direct argument - P is true, show Q is also true

    contrapositive argument - P is false, show Q is also false. This demonstrates that ((not Q) ⇒ (not P)) is true, which is the same as (P ⇒ Q) is true.

    proof by contradiction - P is true and Q is false, derive a contradiction.
  26. Hva betyr disse set operasjoner?
    ~, ∪, ∩, og ⊆
    • ~ betyr not
    • ∪ betyr or
    • The union of two sets A and B is the set A ∪ B = {x : x ∈ A or x ∈ B}. This consists of those objects which lie in the set A or in the set B, or possibly in both. In a venn diagram both entire circles that intersect one another are grayed out.

    • ∩ betyr and
    • The intersection of two sets A and B is the set A ∩ B = { x : x ∈ A and x ∈ B}. All objects that are in both sets.


    • ⊆ betyr ⇒
    • altså A ⊆ S, A is a subset of a set S where every element of A is also an element of S. Eks. A is a circle within circle S.
  27. The complement of a set B relative to a set A
    The complement of a set B relative to a set A is the set A - B {x : x ∈ A and x ∉ B}. This consists of those objects which lie in the set A but not in the set B (so this does not include where they overlap either).
  28. The symmetric difference of two sets A and B
    The symmetric difference of two sets A and B is the set A Δ B = { x : (x ∈ A and x ∉ B) or (x ∈ B and x ∉ A)}. This consists of those objects which lie either in the set A but not in the set B, or which lie in set B but not in set A. In a venn diagram, objects that lie in both A and B, but not where they overlap.
  29. The Cartesian product of sets A and B
    The Cartesian product of sets A and B is the set A x B = {(a,b) : a ∈ A and b ∈ B}. Elements of A x B are called ordered pairs.
  30. Let A = {x,y} and B = {1,2,3}, find the Cartesian products A x B, B x A, and B x B.
    • A x B = {(x, 1),(x,2),(x,3),(y,1),(y,2),(y,3)}
    • B x A = {(1, x),(2,x),(3,x),(1,y),(2,y),(3,y)}
    • B x B = {(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1)(3,2)(3,3)}
  31. Translating English to FOL
    Every gardener likes the sun.
    (Ax) gardener(x) => likes(x,Sun)
  32. Translating English to FOL
    You can fool some of the people all of the time.
    (Ex)(At) (person(x) ∩ time(t)) => can-fool(x,t)
  33. Translating English to FOL
    You can fool all of the people some of the time.
    (Ax)(Et) (person(x) ∩ time(t) => can-fool(x,t)

    • Venn Diagram
    • A = All people
    • B = Some of the time
    • Can be fooled is the intersection of both, since ∩ refers to and, meaning everything that fits both categories.
  34. Translating English to FOL
    All purple mushrooms are poisonous.
    (Ax) (mushroom(x) ∩ purple(x)) => poisonous(x)

    Universal quantification corresponds to conjunction ("and") in that (Ax)P(x) means that P holds for all values of x in the domain associated with that variable. Meaning that the intersection of all mushrooms and the color purple, only the intersection, purple mushrooms, applies.
  35. (Ax) INFO102student(x) => smart(x)
    –"All INFO102 students are smart."
  36. (Ax)INFO102student(x) ∩ smart(x)
    –that everyone in the world is a INFO102 student and is smart.
  37. Everyone likes someone vs Someone is liked by everyone
    • –Everyone likes someone: (Ax)(Ey)likes(x,y)
    • –Someone is liked by everyone: (Ey)(Ax)likes(x,y)
  38. There are exactly two purple mushrooms.
    (Ex)(Ey) mushroom(x) ^ purple(x) ^ mushroom(y) ^ purple(y) ^ ~(x=y) ^ (Az) (mushroom(z) ^ purple(z)) => ((x=z) v (y=z))

    there exists x, a purple mushroom, and there exists y, a purple mushroom, and they are not the same, and for all z, all purple mushrooms (in this set), we infer that if z is equal to x or z is equal to y, that z contains only x and y, so there are only two purple mushrooms.
  39. Ta utgangspunkt i følgende mengder:
    X = {1,2,3}
    Y = {2,3,4}

    Hva er
    1. X ∪ Y
    2. X ∩ Y
    3. X - Y
    4. X x Y
    5. X x (Y-X)
    • 1. X ∪ Y = {1,2,3,4}
    • 2. X ∩ Y = {2,3}
    • 3. X - Y = {1}
    • 4. X x Y = {(1,2), (1,3), (1,4), (2,2), (2,3), (2,4), (3,2), (3,3), (3,4)}
    • 5. X x (Y-X) = {(1,4), (2,4), (3,4)}
  40. Ta utgangspunkt i følgende mengder:
    X = {1,2,3}
    Y = {2,3,4}

    Sant eller galt?
    1. X⊆Y
    2. YxY ⊆ ρ(Y)
    3. Ø∈ X∩Y
    4. Ø⊆ X∩Y
    5. Xx(Y-X)
    • 1. galt
    • 2. galt siden YxY inkludere ikke {Ø, {2}, {3}, {4}, {2,3,4}} som er inkluderte i power set.
    • 3. galt siden set Ø finnes ikke i interseksjon
    • 4. sant siden interseksjonen finnes i set Ø
    • 5. galt
  41. p(AxA) = p(A) x p(A)
    • moteksempel A= Ø:
    • p(ØxØ) = p(Ø) = {Ø}
    • p(Ø)xp(Ø) = {Ø}x{Ø} = {(Ø,Ø)}
    • {Ø} ≠ {(Ø,Ø)}
  42. Eulerian path and Eulerian cycle
    In graph theory, an Eulerian trail (or Eulerian path) is a trail in a graph which visits every edge exactly once. Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail which starts and ends on the same vertex.
  43. i. Partiell ordning
    • i. Partiell ordning
    • svar:Relasjon på formen R⊆ AxA som er refleksiv, transitiv og antisymmetrisk.
  44. Total ordning
    Partiell ordning som i tillegg oppfyller at alle par av verdier er sammenliknbare,dvs at enten xRy eller yRx for alle x,y∊A.
  45. a function
    a function from set a to set b is where every element of A is associated with a uniquely specified element of B. a cannot be repeated, but b can.

    • is a function
    • a-1
    • b-1
    • c-2

    • is not a function
    • a-1
    • a-2
    • b-3
    • c-2
  46. Spesifikt lar vi
    gift= {(Per, Kari), (Kari, Per),(Ola, Liv),(Liv, Ola)}
    liker = {(Per, Kari), (Per, Jens),(Ola, Liv), (Liv, Ola), (Jens, Per)}
    Hva er gift° liker?
    gift° liker(x,y) gjelder hviss y er gift med noen som x liker. spesifikt{(Per, Per), (Ola, Ola), (Liv, Liv), (Jens, Kari) }

    R°S = (trasitivitet) a->x, a->y, b->x
  47. Graden til en node. (Degree)
    Svar: antallet kanter som har forbindelse til noden.
  48. Graf-isomorfi
    Bijeksjon i mellom nodemengdene til to grafer G1 og G2 slik at det går en kantmellom noder u og v i G1 hviss det går en kant mellom i (u) og i (v) i G2. Detteinnebærer at grafene har samme struktur og vi sier at G1 og G2 er isomorfe.

    If both graphs have the same structure, even if the letters or numbers dont match.
  49. Binært søketre
    Binært tre der alle noder er assosiert med en verdi og at rot-verdien er større ennalle verdiene i det venstre subtreet og mindre enn alle verdiene i det høyre subtreet.Subtrærne er også søketrær.

    root value is greater than all values in the left subtree and smaller than all values in the right subtree.
  50. in a tree what does preorder, inorder, and postorder mean?
    • preorder is the original order of the nodes like abcdefgh
    • inorder is the order of all nodes starting on the left hand side, continuing from left to right.
    • postorder is the order of all nodes starting on the left hand side, continuing from right to left.
  51. utsagn
    statement
  52. Hva er en enkel graf.
    Graf der to noder har max en kant mellom seg og der ingen node har kant til seg selv.
  53. Hva vil det si at to utsagn er ekvivalente?
    De har alltid samme sannhetsverdi.
  54. Per liker ikke noen som Pål liker.
    ∀x(Liker(pal,x) ⇒ not liker(per,x))
  55. Ingen liker de som bare liker seg selv.
    • ∀x((liker(x,x) and ∀y(liker(x,y) ⇒
    •  x=y))
  56. bevis ved selvmotsigelse
    • Strategi for å bevise en implikasjon P ⇒
    • Q, hvor P er sann og Q er usann og derfra derfra utleder en selvmotsigelse.
  57. relasjon
    • Et predikat som gjenspeiler en sammenheng mellom elementer som er slik at den enten gjelder eller ikke gjelder.
    • A predicate that reflects a relationship between elements so as to either apply or not apply.
  58. Forklar forskjellen mellom partielle funksjoner og totale funksjoner.
    En total funksjon er veldefinert for all input. Dvs den returnerer alltid en funksjonsverdi, mens en partiell funksjon kan være udefinert for noen input-verdier.

Card Set Information

Author:
burntoutmatch
ID:
320319
Filename:
INFO102
Updated:
2016-05-26 21:38:01
Tags:
INFO102
Folders:

Description:
Eksamen
Show Answers:

Home > Flashcards > Print Preview