Not logged in. · Lost password · Register

Smowheer
Member since Dec 2012
17 posts
Subject: Completeness
Hey,

mir ist beim Bearbeiten des aktuellen Aufgabenblatts aufgefallen, dass ich completeness nicht ganz verstanden hab. Und zwar sagt mir https://en.wikipedia.org/wiki/Completeness_%28logic%29, dass es sowohl semantic als auch strong completeness gibt. Fuer die completeness Beweise in der Aufgabenstellung sollen wir hier aber nur semantic completeness zeigen, oder? Zumindest wuerde ich das aus dem Beispielbeweis aus den Folien so folgern. Koennte es auch sein, dass semantic und strong completeness fuer propositional logic aequivalent sind?
Jazzpirate
Member since Oct 2016
803 posts
Koennte es auch sein, dass semantic und strong completeness fuer propositional logic aequivalent sind?
Nicht nur für propositional sondern für alle reasonable logics sind die äquivalent. Dass semantic aus strong folgt ist denke ich klar; die Rückrichtung folgt aus dem Deduktionssatz und Kompaktheit (daher brauchen wir reasonable).

...davon abgesehen dass kompaktheit deutlich über reasonable hinaus geht... ähm, ja. Auf jeden fall gilt es für propositional und first-order logic :D
This post was edited on 2017-01-07, 23:14 by Jazzpirate.
Vvalter
Member since Dec 2012
119 posts
Was ist eine reasonable Logic? Ich dachte reasonable war eine Eigenschaft von Kalkülen und nicht Logiken?
Was genau muss kompakt sein? Das ist doch auch wieder nur eine Eigenschaft von Mengen. Also müssen alle Formelmengen kompakt sein oder was?
Jazzpirate
Member since Oct 2016
803 posts
"Kompaktheit" ist eine Eigenschaft von logiken (eine formelmenge hat ein modell genau dann wenn jede endliche teilmenge ein modell hat. Das ist rein semantisch).

@reasonable - ha, ich hatte die definition falsch im kopf. Nevermind :D

Was ich meinte ist auf jeden fall den deduktionssatz und somit die existenz einer Implikation, die sich "vernünftig" verhält; dann kann ich jede logische folgerung auf eine tautologische Implikation reduzieren:

A |= Phi genau dann, wenn für eine endliche teilmenge A'={A1,A2,...,An} gilt: |= (A1 & A2 & ... & An) -> Phi

Dafür brauch ich natürlich kompaktheit um die endliche Teilmenge zu erhalten und den Deduktionssatz, um Ak |= Phi umzuformen in |= (Ak -> Phi)

Point is: Das gilt auf jeden Fall für Aussagenlogik und Prädikatenlogik und ich würde hoffen/vermuten/behaupten für die meisten "normalen" Logiken genauso...
Close Smaller – Larger + Reply to this post:
Verification code: VeriCode Please enter the word from the image into the text field below. (Type the letters only, lower case is okay.)
Smileys: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Special characters:
Go to forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen