624:. Considerable effort is spent by proof theorists in showing that cut rules are superfluous in various logics. More precisely, what is shown is that cut is only (in a sense) a tool for abbreviating proofs, and does not add to the theorems that can be proved. The successful 'removal' of cut rules, known as
593:
460:
305:
244:
173:
120:
465:
332:
54:
directly. Structural rules often mimic the intended meta-theoretic properties of the logic. Logics that deny one or more of the structural rules are classified as
823:
249:
188:
73:, where the hypotheses or conclusion of a sequence may be extended with additional members. In symbolic form weakening rules can be written as
185:, where two equal (or unifiable) members on the same side of a sequent may be replaced by a single member (or common instance). Symbolically:
129:
76:
758:
588:{\displaystyle {\frac {\Gamma \vdash \Sigma _{1},A,\Sigma _{2},B,\Sigma _{3}}{\Gamma \vdash \Sigma _{1},B,\Sigma _{2},A,\Sigma _{3}}}}
455:{\displaystyle {\frac {\Gamma _{1},A,\Gamma _{2},B,\Gamma _{3}\vdash \Sigma }{\Gamma _{1},B,\Gamma _{2},A,\Gamma _{3}\vdash \Sigma }}}
816:
638:
642:
809:
673:
1109:
970:
863:
176:
320:
312:
868:
626:
1104:
1073:
853:
20:
1003:
944:
906:
901:
848:
1083:
916:
832:
55:
1078:
993:
858:
603:
A logic without any of the above structural rules would interpret the sides of a sequent as pure
316:
123:
47:
775:
1068:
1033:
1021:
998:
985:
975:
962:
754:
731:
612:
1026:
787:
723:
687:
646:
43:
1013:
929:
886:
678:
661: – substructural logic whose proof theory rejects the structural rule of contraction
618:
These are not the only possible structural rules. A famous structural rule is known as
39:
1098:
791:
934:
840:
667:
658:
31:
27:
681: – mathematical logic system that imposes certain restrictions on implication
952:
878:
632:
329:, where two members on the same side of a sequent may be swapped. Symbolically:
891:
711:
735:
1045:
896:
300:{\displaystyle {\frac {\Gamma \vdash A,A,\Sigma }{\Gamma \vdash A,\Sigma }}}
239:{\displaystyle {\frac {\Gamma ,A,A\vdash \Sigma }{\Gamma ,A\vdash \Sigma }}}
712:"Untersuchungen über das logische Schließen. I, Mathematische Zeitschrift"
620:
608:
604:
168:{\displaystyle {\frac {\Gamma \vdash \Sigma }{\Gamma \vdash \Sigma ,A}}}
115:{\displaystyle {\frac {\Gamma \vdash \Sigma }{\Gamma ,A\vdash \Sigma }}}
1038:
727:
51:
801:
611:; and with both contraction and exchange they can be considered to be
1050:
805:
468:
335:
252:
191:
132:
79:
683:
Pages displaying wikidata descriptions as a fallback
663:
Pages displaying wikidata descriptions as a fallback
1061:
1012:
984:
961:
943:
915:
877:
839:
587:
454:
299:
238:
167:
114:
753:. Place of publication not identified: Elsevier.
607:; with exchange, they can be considered to be
19:For the type of rule used in linguistics, see
817:
8:
641:); it often gives a good indication of the
630:, is directly related to the philosophy of
824:
810:
802:
576:
557:
538:
520:
501:
482:
469:
467:
437:
418:
399:
381:
362:
343:
336:
334:
253:
251:
192:
190:
133:
131:
80:
78:
776:"Semantics of weakening and contraction"
699:
670: – System of resource-aware logic
7:
705:
703:
751:Collected papers of Gerhard Gentzen
66:Three common structural rules are:
573:
554:
535:
528:
517:
498:
479:
472:
446:
434:
415:
396:
390:
378:
359:
340:
291:
279:
274:
256:
230:
218:
213:
195:
153:
147:
142:
136:
106:
94:
89:
83:
14:
780:Annals of Pure and Applied Logic
1:
595:. (This is also known as the
792:10.1016/0168-0072(94)90020-5
674:Ordered logic (linear logic)
50:but instead operates on the
971:Ontology (computer science)
639:Curry–Howard correspondence
46:that does not refer to any
1126:
864:Intuitionistic type theory
177:monotonicity of entailment
18:
16:Rule of mathematical logic
716:Mathematische Zeitschrift
710:Gentzen, Gerhard (1935).
321:idempotency of entailment
313:automated theorem proving
869:Constructive set theory
175:on the right. Known as
62:Common structural rules
589:
456:
301:
240:
169:
116:
854:Constructive analysis
774:Jacobs, Bart (1994).
749:Szabo, M. E. (1969).
590:
457:
302:
241:
170:
117:
21:phrase structure rule
907:Fuzzy set operations
902:Fuzzy finite element
849:Intuitionistic logic
466:
333:
250:
189:
130:
77:
56:substructural logics
1084:Non-monotonic logic
833:Non-classical logic
323:in classical logic.
179:in classical logic.
122:on the left of the
1110:Rules of inference
1079:Intermediate logic
859:Heyting arithmetic
728:10.1007/BF01201353
585:
452:
297:
236:
165:
112:
48:logical connective
1092:
1091:
1074:Inquisitive logic
1069:Dynamic semantics
1022:Three-state logic
976:Ontology language
760:978-0-444-53419-4
583:
450:
295:
234:
163:
110:
1117:
1027:Tri-state buffer
826:
819:
812:
803:
796:
795:
771:
765:
764:
746:
740:
739:
707:
688:Separation logic
684:
664:
635:as normalization
597:permutation rule
594:
592:
591:
586:
584:
582:
581:
580:
562:
561:
543:
542:
526:
525:
524:
506:
505:
487:
486:
470:
461:
459:
458:
453:
451:
449:
442:
441:
423:
422:
404:
403:
393:
386:
385:
367:
366:
348:
347:
337:
307:. Also known as
306:
304:
303:
298:
296:
294:
277:
254:
245:
243:
242:
237:
235:
233:
216:
193:
174:
172:
171:
166:
164:
162:
145:
134:
121:
119:
118:
113:
111:
109:
92:
81:
44:sequent calculus
1125:
1124:
1120:
1119:
1118:
1116:
1115:
1114:
1095:
1094:
1093:
1088:
1057:
1008:
980:
957:
939:
930:Relevance logic
925:Structural rule
911:
887:Degree of truth
873:
835:
830:
800:
799:
773:
772:
768:
761:
748:
747:
743:
709:
708:
701:
696:
682:
679:Relevance logic
662:
655:
649:a given logic.
627:cut elimination
572:
553:
534:
527:
516:
497:
478:
471:
464:
463:
433:
414:
395:
394:
377:
358:
339:
338:
331:
330:
278:
255:
248:
247:
217:
194:
187:
186:
146:
135:
128:
127:
93:
82:
75:
74:
64:
36:structural rule
24:
17:
12:
11:
5:
1123:
1121:
1113:
1112:
1107:
1097:
1096:
1090:
1089:
1087:
1086:
1081:
1076:
1071:
1065:
1063:
1059:
1058:
1056:
1055:
1054:
1053:
1043:
1042:
1041:
1031:
1030:
1029:
1018:
1016:
1010:
1009:
1007:
1006:
1001:
996:
990:
988:
982:
981:
979:
978:
973:
967:
965:
959:
958:
956:
955:
949:
947:
945:Paraconsistent
941:
940:
938:
937:
932:
927:
921:
919:
913:
912:
910:
909:
904:
899:
894:
889:
883:
881:
875:
874:
872:
871:
866:
861:
856:
851:
845:
843:
841:Intuitionistic
837:
836:
831:
829:
828:
821:
814:
806:
798:
797:
766:
759:
741:
722:(1): 176–210.
698:
697:
695:
692:
691:
690:
685:
676:
671:
665:
654:
651:
601:
600:
579:
575:
571:
568:
565:
560:
556:
552:
549:
546:
541:
537:
533:
530:
523:
519:
515:
512:
509:
504:
500:
496:
493:
490:
485:
481:
477:
474:
448:
445:
440:
436:
432:
429:
426:
421:
417:
413:
410:
407:
402:
398:
392:
389:
384:
380:
376:
373:
370:
365:
361:
357:
354:
351:
346:
342:
324:
315:systems using
293:
290:
287:
284:
281:
276:
273:
270:
267:
264:
261:
258:
232:
229:
226:
223:
220:
215:
212:
209:
206:
203:
200:
197:
180:
161:
158:
155:
152:
149:
144:
141:
138:
108:
105:
102:
99:
96:
91:
88:
85:
63:
60:
40:inference rule
30:discipline of
15:
13:
10:
9:
6:
4:
3:
2:
1122:
1111:
1108:
1106:
1103:
1102:
1100:
1085:
1082:
1080:
1077:
1075:
1072:
1070:
1067:
1066:
1064:
1060:
1052:
1049:
1048:
1047:
1044:
1040:
1037:
1036:
1035:
1032:
1028:
1025:
1024:
1023:
1020:
1019:
1017:
1015:
1014:Digital logic
1011:
1005:
1002:
1000:
997:
995:
992:
991:
989:
987:
983:
977:
974:
972:
969:
968:
966:
964:
960:
954:
951:
950:
948:
946:
942:
936:
933:
931:
928:
926:
923:
922:
920:
918:
917:Substructural
914:
908:
905:
903:
900:
898:
895:
893:
890:
888:
885:
884:
882:
880:
876:
870:
867:
865:
862:
860:
857:
855:
852:
850:
847:
846:
844:
842:
838:
834:
827:
822:
820:
815:
813:
808:
807:
804:
793:
789:
786:(1): 73–106.
785:
781:
777:
770:
767:
762:
756:
752:
745:
742:
737:
733:
729:
725:
721:
718:(in German).
717:
713:
706:
704:
700:
693:
689:
686:
680:
677:
675:
672:
669:
666:
660:
657:
656:
652:
650:
648:
644:
640:
636:
634:
629:
628:
623:
622:
616:
614:
610:
606:
598:
577:
569:
566:
563:
558:
550:
547:
544:
539:
531:
521:
513:
510:
507:
502:
494:
491:
488:
483:
475:
443:
438:
430:
427:
424:
419:
411:
408:
405:
400:
387:
382:
374:
371:
368:
363:
355:
352:
349:
344:
328:
325:
322:
318:
314:
310:
288:
285:
282:
271:
268:
265:
262:
259:
227:
224:
221:
210:
207:
204:
201:
198:
184:
181:
178:
159:
156:
150:
139:
125:
103:
100:
97:
86:
72:
69:
68:
67:
61:
59:
57:
53:
49:
45:
41:
37:
33:
29:
22:
1105:Proof theory
994:Three-valued
935:Linear logic
924:
783:
779:
769:
750:
744:
719:
715:
668:Linear logic
659:Affine logic
631:
625:
619:
617:
602:
596:
326:
308:
182:
70:
65:
35:
32:proof theory
25:
1034:Four-valued
1004:Łukasiewicz
999:Four-valued
986:Many-valued
963:Description
953:Dialetheism
633:computation
319:. Known as
183:Contraction
1099:Categories
892:Fuzzy rule
694:References
643:complexity
317:resolution
1046:IEEE 1164
897:Fuzzy set
736:0025-5874
609:multisets
605:sequences
574:Σ
555:Σ
536:Σ
532:⊢
529:Γ
518:Σ
499:Σ
480:Σ
476:⊢
473:Γ
447:Σ
444:⊢
435:Γ
416:Γ
397:Γ
391:Σ
388:⊢
379:Γ
360:Γ
341:Γ
309:factoring
292:Σ
283:⊢
280:Γ
275:Σ
260:⊢
257:Γ
231:Σ
228:⊢
219:Γ
214:Σ
211:⊢
196:Γ
154:Σ
151:⊢
148:Γ
143:Σ
140:⊢
137:Γ
124:turnstile
107:Σ
104:⊢
95:Γ
90:Σ
87:⊢
84:Γ
71:Weakening
653:See also
647:deciding
327:Exchange
52:sequents
1039:Verilog
28:logical
26:In the
1062:Others
757:
734:
126:, and
38:is an
879:Fuzzy
637:(see
42:of a
1051:VHDL
755:ISBN
732:ISSN
613:sets
462:and
246:and
34:, a
788:doi
724:doi
645:of
621:cut
311:in
1101::
784:69
782:.
778:.
730:.
720:39
714:.
702:^
615:.
599:.)
58:.
825:e
818:t
811:v
794:.
790::
763:.
738:.
726::
578:3
570:,
567:A
564:,
559:2
551:,
548:B
545:,
540:1
522:3
514:,
511:B
508:,
503:2
495:,
492:A
489:,
484:1
439:3
431:,
428:A
425:,
420:2
412:,
409:B
406:,
401:1
383:3
375:,
372:B
369:,
364:2
356:,
353:A
350:,
345:1
289:,
286:A
272:,
269:A
266:,
263:A
225:A
222:,
208:A
205:,
202:A
199:,
160:A
157:,
101:A
98:,
23:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.