Fragen zur Logik

[Senior Sanchez]

Hi,

Ich lerne gerade für die Logik-Klausur am Freitag und da ist mir gerade etwas Seltsames aufgefallen. Wir befinden uns in der Aussagenlogik. Dort gibt es ja zwei Substitutionen.
Zum einen hätten wir die parallele die _alle_ Vorkommen einer Variable in einem aussagenlogischen Ausdruck durch einen anderen aussagenlogischen Ausdruck ersetzt.
Der andere Fall ist die sequentielle Substitution, die nur _einen_ Teilausdruck in einem aussagenlogischen Ausdruck durch einen anderen aussagenlogischen Ausdruck ersetzt.

Meine Frage ist jetzt: Warum wird bei der sequentiellen Substitution ein Teilausdruck ersetzt während bei der parallelen Substitution nur Variablen ersetzt werden dürfen? Warum dort nicht auch Ausdrücke?

Hat es vielleicht damit zu tun, dass man sonst einen Fall erzeugen könnte, sodass die parallele Substitution nicht terminiert?
Beispielsweise könnte man im Ausdruck (A UND (B ODER C)) alle Ausdrücke von B durch (B UND D) ersetzen. Das hätte aber zur Folge, dass in der Ersetzung wieder B ersetzt werden müsste, sodass es nicht terminiert.
Andererseits besteht dieses Problem ja auch bei Ersetzung der Variablen, da könnte das auch passieren.

Oder woran liegt das sonst? Ich habe leider bisher keine Erklärung gefunden.

[Expandable]

Bei uns war parallele Substitution so definiert, dass alle Formeln gleichzeitig ersetzt werden (aber nur genau einmal, d.h. nicht rekursiv), bei der seq. Sub. eine Formel nach der anderen.

D.h.:

(a und (b oder c)){b -> {b und a}, a -> q} ergibt parallel (q und ((b und a) oder c)) und seq. (q und ((b und q) oder c))

Ist aber vermutlich bloß eine Definitionssache.

[Senior Sanchez]

Okay, gut, aber bei euch durften komplette Ausdrücke in der parallelen Substitution ersetzt werden oder auch nur Variablen?

EDIT: Ah, sehe es am Beispiel.
Ich frage mich dann, warum das bei uns anders behandelt wurde, denn die Logiker sind ja immer _sehr_ genau und dann muss es dafür einen Grund geben.

[Senior Sanchez]

Soar, ich weiß jetzt wieso das so ist.

Der Grund, wieso bei der parallelen Substitution nur Variablen ersetzt werden dürfen ist folgender. Angenommen wir haben diesen Ausdruck

A = (p OR p OR p)

Würde man jetzt darin den Teilausdruck p OR p ersetzen wollen, so ist die Frage, welchen Teil des Ausdrucks wir hier ersetzen. Semantisch macht das keinen Unterschied, syntaktisch aber schon, denn es entstehen unterschiedliche Ausdrücke.
Ersetze ich nun A = (_p OR p_ OR p) oder A = (p OR _p OR p_)?
Bei einer sequentiellen Substitution ist das egal, denn beide Varianten wären danach in der Menge die durch die sequentielle Substitution entstehen. Bei der parallelen Substitution geht das aber nicht, denn hier müssen _alle_ Vorkommen gleichzeitig ersetzt werden. Um genau das Problem zu vermeiden, also welchen Ausdruck man hier ersetzt, wird dort definiert das nur Variablen ersetzt werden dürfen und will man nun die Variable p durch einen Ausdruck ersetzen, ist das überhaupt kein Problem.


Das war mal ein kleiner Ausflug in die Aussagenlogik. :D

[MadCat]

Hi,

boah... so einen großen Bahnhof hab ich schon ewig nicht mehr gesehen! ;D

Hab halt nur Realschulabschluss - und das lange her... ;D

[WarSlash]

Hi,

boah... so einen großen Bahnhof hab ich schon ewig nicht mehr gesehen! ;D

Hab halt nur Realschulabschluss - und das lange her... ;D

Wenn man Informatik oder Mathematik studiert, dann ist das ganz normal :)
Btw: Ebenfalls Info-Student :)

[Senior Sanchez]

Hi,

boah... so einen großen Bahnhof hab ich schon ewig nicht mehr gesehen! ;D

Hab halt nur Realschulabschluss - und das lange her... ;D

Ich sage dir eins: das ist noch gar nichts! *g*

Sobald es in die Prädikatenlogik geht und man den Wert eines prädikatenlogischen Ausdrucks streng formal bestimmen will, wirste wahnsinnig.
Ich habe persönlich noch nie ein Fach erlebt, dass so abhängig von exakten Definitionen ist wie Logik. Alles baut da wirklich komplett logisch (daher auch der Name *g*) aufeinander auf und vieles ist zwar für das fachkundige Auge sofort offensichtlich, aber wenn du etwas zeigen musst, kannst du das nur auf Basis der bekannten Definitionen und das will dann auch haarklein gezeigt werden.

Mir ist übrigens bei der obigen Ausführung eine Schwäche aufgefallen. Der Einsatz von Funktionssymbolen wie dem logischen Oder erzwingt die Klammerung. Insofern müsste der Ausdruck A eigentlich ((p OR p) OR p) heißen bzw. (p OR (p OR p)). In so einem Fall würde aber die Ersetzung von Ausdrücken mittels paralleler Substitution wieder funktionieren. :D Wir gehen aber mal davon aus, dass es wahrscheinlich irgendeinen Fall gibt, wo es deshalb wirklich mal hakt, auch wenn uns keiner eingefallen ist.

Hoffen wir mal, dass das heute net dran kommt. Also drückt mir fleißig die Daumen ab 13.30. *g*