Oblig 1, INF2220, høst 2008

Hei.

her kommer Oblig1, INF2220.

Logikk

Definisjon (Utsagn).
Et utsagn (eng: proposition) er noe som enten er sant eller usant.

Definisjon (Utsagnsvariable)
Mengden av utsagnsvariable (eng: propositional variables) er en tellbart uendelig mengde
{P, Q, R} av symboler.


Definisjon (Sannhetsverdi).
La Bool = {0, 1} Dette er mengden av sannhetsverdier (eng: truth values).

Negasjon : Hvis F er et utsagn, s°a er negasjonen (eng: negation) til F utsagnet ikke F.

Definisjon (Konnektiv).
De logiske konnektivene (eng: connective) er ^, OR , -> og NOT

Konjunksjon (og)

• Hvis F og G er utsagn, s°a er konjunksjonen (eng: conjuction) av F og G utsagnet F og G.

Disjunksjon (eller)

• Hvis F og G er utsagn, s°a er disjunksjonen (eng: disjunction) av F og G utsagnet F eller G.

Implikasjon (hvis, så)

• Hvis F og G er utsagn, s°a er implikasjonen (eng: implication) mellom F og G utsagnet hvis F, så G. (F -> G)
  

Vi sier at G er en logisk konsekvens (eng: logical consequence) av (S -> G) og S.

Definisjon (Atomær formel).
Enhver utsagnsvariabel er en atomær formel (eng: atomic formula).

Definisjon (Utsagnslogisk formel).
Mengden av utsagnslogiske formler (eng: propositional formula/well-formed formula) er den
minste mengden Prop slik at:
1. Prop inneholder alle atomære formler.
2. Hvis F er medlem av Prop, så er NOT (F) en medlem av Prop.
3. Hvis F,G er medlem av Prop, så er (F ^ G), (F or G) og (F -> G) med i Prop.

Boka kaller en utsagnslogisk formel for en well-formed formula (wff), en velformet formel.

En sannhetsverditabell (eng: truth table) forteller hva sannhetsverdien til en sammensatt

utsagnslogisk formel er på bakgrunn av hvilke sannhetsverdier som er tilordnet utsagnsvariablene.

En valuasjon (eng: valuation) er en funksjon v fra Prop til Bool
En valuasjon svarer til en rad i en sannhetsverditabell
En sannhetsverditabell kan altså si noe om alle valuasjoner.

Definisjon (Oppfyllbarhet) :

En valuasjon v oppfyller (eng: satisfies) en utsagnslogisk formel A hvis v(A) = 1. Dette

skrives ofte v j= A.

En utsagnslogisk formel er oppfyllbar (eng: satisfiable) hvis det fins en valuasjon som

oppfyller den.

Mengder

Mengde differanse :

A - B
eller
A / B
Multimengder :
En multimengde (eng: bag/multiset) er en endelig eller uendelig samling objekter der
innbyrdes rekkefølge ignoreres, men hvor hvert objekt kan forekomme flere ganger. i andre ord Multimengder er mengder der antall forekomster av hvert element teller
Multimengden med elementene a, b, c og d skrives ofte med firkantklammer, slik: [a; b; c; d].

eksempler :
[a,b,c] = [c,b,a]
[a,b,c,a] != [c,b,a]
[a,a,a,b,c] (snitt) [a,a,d]=[a,a]
*** [a,a,b,c] U [a,c] = [a,a,b,c]
*** [a; a; b; c] + [a; c] = [a; a; a; b; c; c]
[a; a; a; b; c] n [a; a; d] = [a; b; c]

Tuppel
Et tuppel (eng: tuple) med n elementer, et n-tuppel, er en samling med n objekter der
både innbyrdes rekkefølge og antall forekomster av hvert objekt teller.
tø, tuppel : <>
Et 2-tuppel med to elementer x og y kalles også et (ordnet) par (eng: ordered pair)
I tuppel : Båade innbyrdes rekkefølge og antall forekomster er viktig.
To n-tupler er like hvis for enhver i slik at 1 < ai =" bi." sxs =" S^2" s =" S^3">

Hvis S er en mengde, så er potensmengden (eng: power set) til S mengden av alle delmengder

Venn Diagram :
Venn-diagrammer brukes til °a illustrere mengder og operasjoner p°a mengder.


Kardinalitet = “størrelsen på en mengde”

To mengder S og T har lik kardinalitet (eng: cardinality) hvis det fins en en-til-en korrespondanse
mellom elementene i S og T.
Mengden S har kardinalitet mindre eller lik T hvis det fins en en-til-en korrespondanse
mellom S og en delmengde av T.
Hvis S er en endelig mengde, så er kardinaliteten til S lik antall elementer i S.
Vi bruker notasjonen |S| for kardinaliteten til S.

Tellbar :
En uendelig mengde S er tellbar (eng: countable) hvis det fins en en-til-en korrespondanse
mellom elementene i S og de naturlige tallene. Hvis ikke, er S overtellbar (eng: uncountable).
Alle endelige mengder er tellbare.

Eksempel.
Mengden av alle partall er tellbar.
Mengden av binære tall er tallbar.
Mengden av brøktall er tellbar.
Mengden av nålevende mennesker er tellbar.
Mengden av reelle tall er ikke tellbar.

En unær relasjon (eng: unary relation) p°a S er en delmengde av S. Kalles ogs°a ofte for et
predikat (eng: predicate).
En binær relasjon (eng: binary relation) fra S til T er en delmengde av S x T.
En n-ær relasjon (eng: n-ary relation) p°a mengdene S1, S2,..., Sn er en delmengde av kryssproduktet S1 x S2 x ... x Sn.
En n-ær relasjon på en mengde S er en delmengde av Sn.

Definisjon (Refleksiv).
En binær relasjon R på mengden S er refleksiv (eng: reflexive) hvis det for alle x i S er slik at
er medlemer av R.

Definisjon (Symmetrisk).
En binær relasjon R på mengden S er symmetrisk (eng: symmetric) hvis det for alle x, y er slik at hvis er medlemer av R, så er medlemer av R.

Definisjon (Transitiv).
En binær relasjon R på mengden S er transitiv (eng: transitive) hvis det for alle x, y, z er slik at
hvis er medlem av R og er medlem av R, så er medlem av R.

Definisjon (Ekvivalensrelasjon).
En binær relasjon p°a mengden S er en ekvivalensrelasjon (eng: equivalence relation) hvis den er
refleksiv, symmetrisk og transitiv.

Definisjon (Anti-symmetrisk).
En binær relasjon R på mengden S er anti-symmetrisk (eng: anti-symmetric) hvis det for alle x, y er slik at hvis medlem av R og medlem av R, så x = y.

Definisjon (Irrefleksiv).
En binær relasjon R på mengden S er irrefleksiv (eng: irreflexive) hvis det ikke fins noen x er medlem av S slik at er medlem av R.