Oblig 1 - Q & A

• Q: Oppgave 1:
  Det st?r at man skal gi bevis for sekventen eller konstruere en?motmodell. Jeg forst?r det slik at man skal lage en LK-utledning for?hver sekvent (noe jeg dessverre har f?tt null ?velse i!). Sp?rsm?let?mitt er: n?r er man "i m?l" med beviset sitt, og hvordan ser man at man?ikke klarer ? finne et bevis? I foilene fra 6. februar st?r det at en?utledning med l?vnoder som har "noe likt p? begge sider av |-" kalles et?bevis (s. 7). Holder det ? utlede til man finner en eller annen atom?r?formel p? begge sider av dette tegnet, for hver gren i treet?
  
  Ja.
  
  > Og er det dette som kalles en "lukking" av grenen (s. 20)?
  
  Ja.
  
  > Videre: hva er fortolkningen av et LK-bevis? At formelen ikke lar seg falsifisere?
  
  Ja, indirekte. Direkte s? er det at *sekventen* ikke lar seg falsifisere.
  
  > Og hvordan finner man ut at man ikke kan finne et bevis?
  
  1. Du holder p? i all uendelighet og fors?ker alle muligheter ;-) eller
  2. Bruker sunnhetsteoremet. Det sier at hvis du har et bevis, s? er sekventen gyldig. Eller (kontrapositivt) at hvis en sekvent ikke er gyldig, dvs. er falsifiserbar, s? fins ikke et bevis. Dermed kan du vise at en sekvent ikke lar seg bevise ved ? gi en motmodell.
  
  > Er det kort og godt at man ikke "finner noe likt p? begge sider"?
  
  Ja.
  
  > Hvordan g?r man evt fra innsikten om at det ikke finnes noe bevis til ? danne en motmodell?
  
  Det er en fin ?velse ? finne ut av dette selv, s? jeg skal ikke r?pe noen systematisk m?te ? gj?re det p?. Hint: tenk semantisk! (Dette blir for?vrig temaet for forelesningen - om kompletthet - neste uke.
  
  > M? man pr?ve og feile vha boolske valuasjoner til man finner en som falsifiserer uttrykket?
  
  Ja. Men, du trenger ? ikke ? pr?ve og feile helt blindt. Hvis du ikke finner noe bevis ganske kjapt, s? kan det l?nne seg ? se om du p? en grei m?te kan falsifisere sekventen (og formelen).
  
  
• > Oppgave 3:
  > Hva vil det si ? argumentere semantisk i denne sammenhengen? Holder det?? vise at det stemmer for alle boolske valuasjoner, dvs for b?de v(A) =?0 og v(A) = 1?
  
  ? argumentere semantisk betyr her ? ikke argumentere syntaktisk, f.eks. ved ? gi LK-bevis. S? ja, du skal henvise til valuasjoner og denslags. For ? ikke ? "gi bort" l?sningen: gir det mening ? "vise p?standen" for v(A)=1?
  
  
• Q: Oppgave 4b. Dersom vi skal vise det oppgaven ber oss om, skal vi vise det for alle alfa og beta regler, eller kun den som er gitt i deloppgave a? Dersom det er slik at vi skal vise det for alle, er det s?nn at man m? ta for seg en og en? Eller er det annen fremgangsm?te det er tenkt at man skal bruke?
  
  A: Man skal ikke vise det for en bestemt mengde regler. Bruk "definisjonene" av falsifikasjonsbevarende og gyldighetsbevarende regler i oppgaveteksten. Hint: Er det mulig ? falsifisere en gyldig sekvent?
  
  
• Q: Oppgave 5. Her sliter jeg litt med ? tolke hva jeg skal gj?re. Det g?r egentlig p? det at jeg ikke forst?r hvordan man kan snakke om at en valuvasjon feks ikke oppfyller (gamma) union (delta falsum)..hva vil det si?
  
  A: En mengde formler A er ikke oppfyllbar dersom det ikke finnes en valuasjon som oppfyller A. En valuasjon v oppfyller en mengde formler A, dersom v(a) = 1 for alle formler a i A.
  Tips: Pr?v kontrapositivt bevis. Anta at Gamma |- Delta ikke er gyldig og vis at Gamma union Delta^falsum er oppfyllbar. (NB! Dette er kun den ene "retningen", <=, av bi-implikasjonen "hvis og bare hvis".)