25:
397:, so that a proof of one conjecture may immediately imply the validity of several others. It can be much easier to show a proposition's truth to follow from another proposition than to prove it independently.
410:), and while it is not known if a polynomial-time solution exists for any of them, it is known that if such a solution exists for some of them, one exists for all of them. Similarly, the
54:
277:
76:
47:
378:). Thus, the goal of a conditional proof is to demonstrate that if the CPA were true, then the desired conclusion
253:
246:
239:
291:
574:
406:
328:
132:
579:
332:
138:
37:
319:
158:
145:
41:
33:
323:
164:
151:
528:
177:
99:
58:
569:
272:
220:
211:
171:
351:
184:
8:
523:
379:
284:
267:
229:
190:
423:
411:
382:. The validity of a conditional proof does not require that the CPA be true, only that
355:
197:
518:
310:
303:
106:
92:
426:, suppose we want to prove A → C (if A, then C) from the first two premises below:
260:
564:
404:
class of complexity theory. There is a large number of interesting tasks (see
558:
203:
492:
477:
347:
191:
121:
401:
390:
394:
359:
185:
165:
393:. Conditional proofs exist linking several otherwise unproven
506:(follows from lines 3–5, conditional proof; "If A, then C")
370:
The assumed antecedent of a conditional proof is called the
254:
212:
178:
133:
204:
172:
285:
240:
146:
122:
465:(conditional proof assumption, "Suppose A is true")
198:
556:
278:
46:but its sources remain unclear because it lacks
247:
139:
400:A famous network of conditional proofs is the
389:Conditional proofs are of great importance in
292:
261:
159:
152:
358:of the conditional necessarily leads to the
77:Learn how and when to remove this message
422:As an example of a conditional proof in
547:Dov M. Gabbay, Franz Guenthner (eds.),
557:
414:has many consequences already proven.
18:
350:that takes the form of asserting a
13:
14:
591:
495:; "If B then C; B, therefore C")
480:; "If A then B; A, therefore B")
417:
386:it would lead to the consequent.
23:
549:Handbook of philosophical logic
1:
534:
491:(follows from lines 2 and 4,
476:(follows from lines 1 and 3,
407:List of NP-complete problems
372:conditional proof assumption
7:
551:, Volume 8, Springer, 2002.
512:
499:
484:
469:
458:
442:
431:
365:
10:
596:
544:, Jones and Barlett, 2006.
542:Logic, sets, and recursion
329:Existential generalization
134:Biconditional introduction
453:
320:Universal generalization
160:Disjunction introduction
147:Conjunction introduction
117:Implication introduction
32:This article includes a
435:A → B
354:, and proving that the
61:more precise citations.
529:Propositional calculus
179:hypothetical syllogism
100:Propositional calculus
221:Negation introduction
214:modus ponendo tollens
279:Material implication
230:Rules of replacement
93:Transformation rules
575:Mathematical proofs
524:Logical consequence
380:necessarily follows
192:destructive dilemma
540:Robert L. Causey,
412:Riemann hypothesis
311:Rules of inference
107:Rules of inference
34:list of references
519:Deduction theorem
510:
509:
449:("If B, then C")
438:("If A, then B")
344:conditional proof
340:
339:
87:
86:
79:
587:
580:Methods of proof
429:
428:
294:
287:
280:
268:De Morgan's laws
263:
256:
249:
242:
216:
208:
200:
193:
187:
180:
174:
167:
161:
154:
148:
141:
135:
128:
118:
89:
88:
82:
75:
71:
68:
62:
57:this article by
48:inline citations
27:
26:
19:
595:
594:
590:
589:
588:
586:
585:
584:
555:
554:
537:
515:
454:
420:
384:if it were true
368:
304:Predicate logic
298:
262:Double negation
116:
83:
72:
66:
63:
52:
38:related reading
28:
24:
17:
12:
11:
5:
593:
583:
582:
577:
572:
567:
553:
552:
545:
536:
533:
532:
531:
526:
521:
514:
511:
508:
507:
504:
501:
497:
496:
489:
486:
482:
481:
474:
471:
467:
466:
463:
460:
456:
455:
451:
450:
447:
444:
440:
439:
436:
433:
424:symbolic logic
419:
418:Symbolic logic
416:
367:
364:
338:
337:
336:
335:
326:
314:
313:
307:
306:
300:
299:
297:
296:
289:
282:
275:
270:
265:
258:
255:Distributivity
251:
244:
236:
233:
232:
226:
225:
224:
223:
218:
195:
182:
169:
156:
143:
130:
110:
109:
103:
102:
96:
95:
85:
84:
42:external links
31:
29:
22:
15:
9:
6:
4:
3:
2:
592:
581:
578:
576:
573:
571:
568:
566:
563:
562:
560:
550:
546:
543:
539:
538:
530:
527:
525:
522:
520:
517:
516:
505:
502:
498:
494:
490:
487:
483:
479:
475:
472:
468:
464:
461:
457:
452:
448:
445:
441:
437:
434:
430:
427:
425:
415:
413:
409:
408:
403:
398:
396:
392:
387:
385:
381:
377:
373:
363:
361:
357:
353:
349:
345:
334:
333:instantiation
330:
327:
325:
324:instantiation
321:
318:
317:
316:
315:
312:
309:
308:
305:
302:
301:
295:
290:
288:
283:
281:
276:
274:
273:Transposition
271:
269:
266:
264:
259:
257:
252:
250:
248:Commutativity
245:
243:
241:Associativity
238:
237:
235:
234:
231:
228:
227:
222:
219:
217:
215:
209:
207:
206:modus tollens
201:
196:
194:
188:
183:
181:
175:
170:
168:
162:
157:
155:
149:
144:
142:
136:
131:
129:
126:
123:elimination (
119:
114:
113:
112:
111:
108:
105:
104:
101:
98:
97:
94:
91:
90:
81:
78:
70:
60:
56:
50:
49:
43:
39:
35:
30:
21:
20:
570:Conditionals
548:
541:
493:modus ponens
478:modus ponens
421:
405:
399:
388:
383:
375:
371:
369:
343:
341:
331: /
322: /
213:
210: /
205:
202: /
189: /
186:Constructive
176: /
163: /
150: /
137: /
125:modus ponens
124:
120: /
115:
73:
64:
53:Please help
45:
16:Formal proof
402:NP-complete
395:conjectures
391:mathematics
352:conditional
286:Exportation
173:Disjunctive
166:elimination
153:elimination
140:elimination
59:introducing
559:Categories
535:References
360:consequent
356:antecedent
199:Absorption
293:Tautology
67:July 2021
513:See also
366:Overview
55:improve
565:Logic
503:A → C
446:B → C
348:proof
346:is a
40:, or
376:CPA
561::
500:6.
485:5.
470:4.
459:3.
443:2.
432:1.
362:.
342:A
44:,
36:,
488:C
473:B
462:A
374:(
127:)
80:)
74:(
69:)
65:(
51:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.