Schnittregel


Schnittregel

Der Schnitt (engl. cut oder cut-rule) ist eine transitive Regel in der Logik, der linearen Optimierung und der Constraintprogrammierung.

Wird in einer Ableitung oder einem Suchbaum ein vermeidbarer transitiver „Umweg“ vorgenommen, so ist dieser Umweg wegschneidbar.

Schnitt in der Logik

In den Logikkalkülen ist die Schnittregel der modus ponens auf metalogischer Stufe und lautet so:

\qquad\frac{\Gamma\vdash A\qquad A, \Delta\vdash B}{\Gamma, \Delta\vdash B}

Ist A aus Sequenzen herleitbar und mittels A auch B herleitbar, so ist B herleitbar. A wird also weggeschnitten.

Dass die Schnittregel in den Gentzentyp-Kalkülen gültig und eliminierbar ist, besagt der Gentzensche Hauptsatz.

Literatur


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Cut-elimination — Der Gentzensche Hauptsatz oder Schnittsatz ist ein Satz der mathematischen Logik, der besagt, dass die Schnittregel in Gentzentypkalkülen gültig ist. Er ist nach Gerhard Gentzen benannt, der ihn 1934 aufstellte und bewies. Inhaltsverzeichnis 1… …   Deutsch Wikipedia

  • Schnittsatz — Der Gentzensche Hauptsatz oder Schnittsatz ist ein Satz der mathematischen Logik, der besagt, dass die Schnittregel in Gentzentypkalkülen gültig ist. Er ist nach Gerhard Gentzen benannt, der ihn 1934 aufstellte und bewies. Inhaltsverzeichnis 1… …   Deutsch Wikipedia

  • Gentzenscher Hauptsatz — Der Gentzensche Hauptsatz oder Schnittsatz ist ein Satz der mathematischen Logik, der besagt, dass die Schnittregel in Gentzentypkalkülen gültig ist. Er ist nach Gerhard Gentzen benannt, der ihn 1934 aufstellte und bewies. Inhaltsverzeichnis 1… …   Deutsch Wikipedia

  • Abtrennungsregel — Der Modus ponens ist eine schon in der antiken Logik geläufige Schlussfigur, die in vielen logischen Systemen (siehe Logik, Kalkül) als Schlussregel verwendet wird. Der Modus ponens erlaubt es, aus zwei Aussagen der Form Wenn A, dann B und A (den …   Deutsch Wikipedia

  • Modus Ponens — Der Modus ponens ist eine schon in der antiken Logik geläufige Schlussfigur, die in vielen logischen Systemen (siehe Logik, Kalkül) als Schlussregel verwendet wird. Der Modus ponens erlaubt es, aus zwei Aussagen der Form Wenn A, dann B und A (den …   Deutsch Wikipedia

  • Modus ponendo ponens — Der Modus ponens ist eine schon in der antiken Logik geläufige Schlussfigur, die in vielen logischen Systemen (siehe Logik, Kalkül) als Schlussregel verwendet wird. Der Modus ponens erlaubt es, aus zwei Aussagen der Form Wenn A, dann B und A (den …   Deutsch Wikipedia

  • Kalkül des natürlichen Schließens — Systeme (oder Kalküle) natürlichen Schließens sind ein Kalkültyp, der 1934 von Gerhard Gentzen und etwa zeitgleich von Stanisław Jaśkowski, einem Vertreter der Lemberg Warschau Schule, entwickelt wurde. Der Begriff des Kalküls des natürlichen… …   Deutsch Wikipedia

  • Kalküle natürlichen Schließens — Systeme (oder Kalküle) natürlichen Schließens sind ein Kalkültyp, der 1934 von Gerhard Gentzen und etwa zeitgleich von Stanisław Jaśkowski, einem Vertreter der Lemberg Warschau Schule, entwickelt wurde. Der Begriff des Kalküls des natürlichen… …   Deutsch Wikipedia

  • Modus ponens — Der Modus ponens ist eine schon in der antiken Logik geläufige Schlussfigur, die in vielen logischen Systemen (siehe Logik, Kalkül) als Schlussregel verwendet wird. Der Modus ponens erlaubt es, aus zwei Aussagen der Form Wenn A, dann B und A (den …   Deutsch Wikipedia

  • Natürliche Deduktion — Systeme (oder Kalküle) natürlichen Schließens sind ein Kalkültyp, der 1934 von Gerhard Gentzen und etwa zeitgleich von Stanisław Jaśkowski, einem Vertreter der Lemberg Warschau Schule, entwickelt wurde. Der Begriff des Kalküls des natürlichen… …   Deutsch Wikipedia