Beweis: Deduktionstheorem Beweisen Sie: Für aussagenlogische Formeln F, F1, …, Fn gilt: {F1, …, Fn} |= F gdw. |= ((...(F1 UND F2)...) UND Fn) → F). → : Wir nehmen an, dass {F1, …, Fn} |= F gilt. Dann soll |= ((...(F1 UND F2)...) UND Fn) → F) gelten. Das bedeutet, ((...(F1 UND F2)...) UND Fn) → F)I = WAHR bzw. ((...(F1 UND F2)...) UND Fn)I →* FI ) = WAHR für alle Interpretationen I. Sei I eine beliebig gewählte Interpretation. (1) Wenn (...(F1 UND F2)...) UND Fn)I = FALSCH, dann gilt ((...(F1 UND F2)...) UND Fn) → F)I = WAHR, weil die Bedingung der Implikation FALSCH ist, und somit die Implikation immer WAHR. (2) Wenn (...(F1 UND F2)...) UND Fn)I = WAHR, dann erhalten wir ((...(F1I UND* F2I)...) UND* FnI) = WAHR, d.h. FiI = WAHR für alle i = 1,...,n. Das bedeutet aber, dass unter I die Formelmenge {F1, …, Fn} WAHR ist. Da wir annehmen, dass {F1, …, Fn} |= F gilt, muss also FI = WAHR gelten. Zusammen erhalten wir ((...(F1 UND F2)...) UND Fn)I → FI = WAHR, also auch ((...(F1 UND F2)...) UND Fn) → F)I = WAHR wie gewünscht. ← : Wir nehmen an, dass |= ((...(F1 UND F2)...) UND Fn) → F) gilt, d.h. dass für jede Interpretation I gilt ((...(F1 UND F2)...) UND Fn) → F)I = WAHR, was gleichbedeutend ist mit ((...(F1 UND F2)...) UND Fn)I →* FI) = WAHR. Wenn {F1, …, Fn} keine Modelle hat, dann gilt {F1, …, Fn} |= F. Andernfalls sei I eine beliebiges Modell von {F1, …, Fn}, also eine Interpretation, die jede Formel in {F1, …, Fn} auf WAHR abbildet. Es genügt zu zeigen, dass I auch Modell von F ist, also FI = WAHR gilt. Da wir annehmen, dass jede der Formeln in {F1, …, Fn} WAHR ist unter I, gilt FiI = WAHR für alle i = 1, …, n. Dann ist auch ((...(F1I UND* F2I)...) UND* FnI) = WAHR und damit auch ((...(F1 UND F2)...) UND Fn) → F)I = WAHR. Da wir annehmen, dass ((...(F1 UND F2)...) UND Fn) → F)I WAHR ist, erhalten wir aus der Wahrheitswerttetabelle für →*, dass FI = WAHR gelten muss. Dies war zu zeigen.