matematikk.net

Trenger hjelp til denne oppgaven, har prøvd men klarer ikke å løse denne

La S være et bevissystem (for eksempel naturlig deduksjon). En formel A er S-konsistent dersom S ̸⊢ ¬A, alts ̊a dersom ¬A ikke er bevisbar i S. Hvilke, om noen, av de følgende p ̊astandene er ekvivalente?
a. S er sunn.
b. S er komplett.
c. S er usunn.
d. S er ukomplett.
e. Det finnes en formel F slik at b ̊ade S ⊢ F og S ⊢ ¬F. f. Enhver S-konsistent formel er oppfyllbar.
g. Det finnes en S-konsistent formel som ikke er oppfyllbar. h. Enhver oppfyllbar formel er S-konsistent.
Du kan ikke anta at S er naturlig deduksjon, s ̊a du kan ikke gjøre noen antakelser om reglene i S. Bevis svarene dine.

Jeg er i tvil om noen er både sunnt og usunnt samtidig

anonim12 wrote:Jeg er i tvil om noen er både sunnt og usunnt samtidig

Alt er vel både sunt og usunt. Sunt i rimelige mengder, usunt i for store mengder.

Kunne du utdype din besvarelsen? hvordan ville du ha løst denne oppgaven?

Hei!

Nøyaktig hvor er det du har problemer? Du må først vite hva de forskjellige begrepene betyr. Gjør du det? Og uansett, har du skrevet dem opp?

Det er vanskelig for meg å vite nøyaktig hvordan dere har definert "sunt" og "usunt" osv, men jeg vil tro det ligner på:

a. [tex]S[/tex] er sunn: For alle [tex]A[/tex], hvis [tex]S \vdash A[/tex], så [tex]\models A[/tex].
b. [tex]S[/tex] er komplett: For alle [tex]A[/tex], hvis [tex]\models A[/tex], så [tex]S \vdash A[/tex].
c. [tex]S[/tex] er usunn: Det eksisterer en [tex]A[/tex] slik at [tex]S \vdash A[/tex] og [tex]\not\models A[/tex].
d. [tex]S[/tex] er ukomplett: Det eksisterer en [tex]A[/tex] slik at [tex]\models A[/tex] og [tex]S \not\vdash A[/tex].
osv...

Har du greid å vise at noen punkter ikke er ekvivalente? Eller at noen er ekvivalente? Kan du tenke deg et system som er sunt men ikke komplett? Hva med bevis-systemet som kan bevise alt? Eller bevissystemet som beviser ingen ting.

Hilsen,
Peter

Hei Peter,

Formler for sunn,kompletthet/usunn, ukompletthet osv. kjenner jeg til, men problemet er å finne bevissytemer som kan påvise de.

Foreløpig har jeg greid oppgaven : b) S er komplett, som var greit å bevise.

Hilsen
-Odda Sofie

peterbb wrote:Hei!

Nøyaktig hvor er det du har problemer? Du må først vite hva de forskjellige begrepene betyr. Gjør du det? Og uansett, har du skrevet dem opp?

Det er vanskelig for meg å vite nøyaktig hvordan dere har definert "sunt" og "usunt" osv, men jeg vil tro det ligner på:

a. [tex]S[/tex] er sunn: For alle [tex]A[/tex], hvis [tex]S \vdash A[/tex], så [tex]\models A[/tex].
b. [tex]S[/tex] er komplett: For alle [tex]A[/tex], hvis [tex]\models A[/tex], så [tex]S \vdash A[/tex].
c. [tex]S[/tex] er usunn: Det eksisterer en [tex]A[/tex] slik at [tex]S \vdash A[/tex] og [tex]\not\models A[/tex].
d. [tex]S[/tex] er ukomplett: Det eksisterer en [tex]A[/tex] slik at [tex]\models A[/tex] og [tex]S \not\vdash A[/tex].
osv...

Har du greid å vise at noen punkter ikke er ekvivalente? Eller at noen er ekvivalente? Kan du tenke deg et system som er sunt men ikke komplett? Hva med bevis-systemet som kan bevise alt? Eller bevissystemet som beviser ingen ting.

Hilsen,
Peter

I denne oppgaven, så går det ikke an å vise at "S er komplett", siden du ikke vet hva S er. S er et vilkårlig bevissystem, m.a.o, du vet i praksis ingen ting om S.

Når du sier at du har "løst B", så virker det som du har missforstått oppgaven; det er ikke deloppgaver a) ... h), men påstander a) ... h). Oppgaven er ikke å finne ut hvilke påstander som er sanne/usann, men å finne ut hvilke påstander som er ekvivalente eller forskjellige.

Ta f.eks. påstand a) og e). Du må svare på om følgende to påstander er ekvivalente eller ei:

a) For alle [tex]A[/tex], hvis [tex]S \vdash A[/tex], så [tex]\models A[/tex].
e) Det finnes en formel [tex]A[/tex], slik at både [tex]S \vdash A[/tex] og [tex]S \vdash \neg A[/tex].

Hvis du tror de er ekvivalente, så må du komme med et bevis for det.

Hvis du tror påstandene er forskjellige, så kan du komme med et moteksempel: et konkret bevissystem S som gjør den ene påstanden sann (f.eks. a), og den andre påstanden usann (i såfall b)).

For å komme med moteksempler, så kan det være lurt å teste med "dumme" bevissystemer: f.eks. et system som beviser alle formler, eller et system som beviser ingen formler, eller et system som beviser nøyaktig en formel, osv.

Så egentlig er det kjempemange deloppgaver! En for hvert par av påstander a) ... h). Heldig vis så trenger du ikke å sjekke alle kombinasjoner (du får spørre etter at du har bevist/motbevist noen ekvivalenser, hvis du lurer på hvorfor).

- Peter

Så kompletthet er relatert til sunnhet. Altså sunnhet er => mens kompletthet er <=>. Så hvis noe er kompletthet, så må det være sunnt. Derfor kan man anta at noe er sunnt og kun bevise <=, er motsatte.


tar et eksempel med S er komplett og enhver S-konsistent formel er oppfyllbar om de er ekvivalente

S er komplett
<=>
∀ A(valid(A) -> Provable(A))
<=>
∀ A( ¬ Provable(A) -> ¬ Valid (A)) her har vi kontrapositiv
<=>
∀ B (¬ Provable (¬B) -> ¬ valid (¬B))
<=>
∀ B(¬ Provable (¬B) -> false (¬ B))
<=>
∀ B (¬ Provable(¬B) -> sat(B))

Hver S-konsistent formel er oppfyllbar ved bruk av logisk eliminasjon.

Er det riktig tankegang? Kan du komme med eksempel på a og e?

Oda Sofie wrote:Så kompletthet er relatert til sunnhet. Altså sunnhet er => mens kompletthet er <=>.

Aha, jeg er kjent med at noen definerer kompletthet slik. Den er grei.

Oda Sofie wrote:Så hvis noe er kompletthet, så må det være sunnt. Derfor kan man anta at noe er sunnt og kun bevise <=, er motsatte.

Ja, hvis du prøver å bevise at a og b er ekvivalente, så kan du gjøre det.

Oda Sofie wrote: tar et eksempel med S er komplett og enhver S-konsistent formel er oppfyllbar om de er ekvivalente

S er komplett
<=>
∀ A(valid(A) -> Provable(A))
<=>
∀ A( ¬ Provable(A) -> ¬ Valid (A)) her har vi kontrapositiv
<=>
∀ B (¬ Provable (¬B) -> ¬ valid (¬B))

Hvordan begrunner du steget over? Jeg ser at du har =>, men lurer på hvordan du får <=.

Oda Sofie wrote: <=>
∀ B(¬ Provable (¬B) -> false (¬ B))
<=>
∀ B (¬ Provable(¬B) -> sat(B))

Hver S-konsistent formel er oppfyllbar ved bruk av logisk eliminasjon.

Er det riktig tankegang?

Ja, dette er måten du beviser at to påstander er ekvivalente. Jeg er dog usikker på om disse to påstandene faktisk er ekvivalente.

Oda Sofie wrote: Kan du komme med eksempel på a og e?

Påstandene a og e er forskjellige. Hvis du tar bevissystemet som ikke kan bevise noe som helst, så får du at det er sunt, men det beviser ingen formel og dens negasjon. Etter å ha tittet på flere av påstandene, så har jeg foreløpig kun sett forskjellige påstander, men det kan jo være at dere har noen egenskaper som jeg ikke kjenner til. Har dere f.eks. definert at bevissystemer må ha visse egenskaper?

oppgaven er litt modifisert nå:

La S være et bevissystem (for eksempel naturlig deduksjon). En formel A er S-konsistent dersom S ̸⊢ ¬A, alts ̊a dersom ¬A ikke er bevisbar i S. Hvil- ke, om noen, av de følgende p ̊astandene er ekvivalente? Der du ikke finner ekvivalenser, kan du finne logisk konsekvens ́en vei?
a. S er sunn.
b. S er komplett.
c. S er usunn.
d. S er ukomplett.
e. Det finnes en formel F slik at b ̊ade S ⊢ F og S ⊢ ¬F. f. Enhver S-konsistent formel er oppfyllbar.
g. Det finnes en S-konsistent formel som ikke er oppfyllbar.
h. Enhver oppfyllbar formel er S-konsistent.
Du kan ikke anta at S er naturlig deduksjon, s ̊a du kan ikke gjøre noen antakelser om reglene i S, men du kan argumentere klassisk i disse bevisene, uavhengig av om S er et bevissystem for klassisk eller intuisjonistisk logikk. Bevis svarene dine.

Så det er bare snak om et bevissystem for klassisk eller intuisjonistisk logikk.