33:
385:
251:
485:
560:
Verifying the
Robbins conjecture required proving Huntington's equation, or some other axiomatization of a Boolean algebra, as theorems of a Robbins algebra. Huntington, Robbins,
557:
and the constants 0 and 1 are easily defined from the
Robbins algebra primitives. Pending verification of the conjecture, the system of Robbins was called "Robbins algebra."
294:
577:. For a complete proof of the Robbins conjecture in one consistent notation and following McCune closely, see Mann (2003). Dahn (1998) simplified McCune's machine proof.
304:
547:
523:
155:
131:
62:
186:
416:
501:, namely that the Huntington equation could be replaced with what came to be called the Robbins equation, and the result would still be
591:
17:
651:
84:
554:
550:
526:
55:
502:
394:. This was proved in 1996, so the term "Robbins algebra" is now simply a synonym for "Boolean algebra".
391:
604:
571:
261:
45:
641:
605:
Robbins
Algebras Are Boolean: A Revision of McCune's Computer-Generated Solution of Robbins Problem
49:
41:
646:
380:{\displaystyle \neg \left(\neg \left(a\lor b\right)\lor \neg \left(a\lor \neg b\right)\right)=a}
106:
158:
66:
532:
508:
406:
proposed a new set of axioms for
Boolean algebras, consisting of (1) and (2) above, plus:
140:
116:
8:
615:
586:
625:
574:
403:
110:
98:
564:, and others worked on the problem, but failed to find a proof or counterexample.
494:
134:
390:
For many years, it was conjectured, but unproven, that all
Robbins algebras are
621:
567:
635:
561:
255:
180:
490:
From these axioms, Huntington derived the usual axioms of
Boolean algebra.
246:{\displaystyle a\lor \left(b\lor c\right)=\left(a\lor b\right)\lor c}
480:{\displaystyle \neg (\neg a\lor b)\lor \neg (\neg a\lor \neg b)=a.}
535:
511:
419:
307:
264:
189:
143:
119:
541:
517:
479:
379:
288:
245:
149:
125:
633:
54:but its sources remain unclear because it lacks
616:A Complete Proof of the Robbins Conjecture.
628:," With links to proofs and other papers.
570:proved the conjecture in 1996, using the
85:Learn how and when to remove this message
14:
634:
26:
24:
592:Minimal axioms for Boolean algebra
536:
459:
450:
444:
426:
420:
355:
341:
316:
308:
144:
25:
663:
603:Dahn, B. I. (1998) Abstract to "
31:
289:{\displaystyle a\lor b=b\lor a}
465:
447:
438:
423:
13:
1:
597:
626:Robbins Algebras Are Boolean
7:
580:
10:
668:
397:
157:satisfying the following
652:Computer-assisted proofs
572:automated theorem prover
525:would interpret Boolean
40:This article includes a
69:more precise citations.
543:
519:
493:Very soon thereafter,
481:
381:
290:
247:
151:
127:
544:
542:{\displaystyle \neg }
520:
518:{\displaystyle \lor }
482:
411:Huntington's equation
382:
291:
248:
152:
150:{\displaystyle \neg }
128:
126:{\displaystyle \lor }
113:, usually denoted by
614:Mann, Allen (2003) "
533:
509:
417:
305:
262:
187:
141:
117:
109:containing a single
587:Algebraic structure
137:usually denoted by
609:Journal of Algebra
539:
515:
499:Robbins conjecture
477:
377:
286:
243:
147:
123:
42:list of references
18:Robbins conjecture
404:Edward Huntington
164:For all elements
95:
94:
87:
16:(Redirected from
659:
548:
546:
545:
540:
524:
522:
521:
516:
486:
484:
483:
478:
392:Boolean algebras
386:
384:
383:
378:
370:
366:
365:
361:
337:
333:
299:Robbins equation
295:
293:
292:
287:
252:
250:
249:
244:
236:
232:
214:
210:
156:
154:
153:
148:
132:
130:
129:
124:
111:binary operation
99:abstract algebra
90:
83:
79:
76:
70:
65:this article by
56:inline citations
35:
34:
27:
21:
667:
666:
662:
661:
660:
658:
657:
656:
642:Boolean algebra
632:
631:
611:208(2): 526–32.
600:
583:
534:
531:
530:
510:
507:
506:
503:Boolean algebra
495:Herbert Robbins
418:
415:
414:
400:
348:
344:
323:
319:
315:
311:
306:
303:
302:
263:
260:
259:
222:
218:
200:
196:
188:
185:
184:
142:
139:
138:
135:unary operation
133:, and a single
118:
115:
114:
103:Robbins algebra
91:
80:
74:
71:
60:
46:related reading
36:
32:
23:
22:
15:
12:
11:
5:
665:
655:
654:
649:
647:Formal methods
644:
630:
629:
622:William McCune
619:
612:
599:
596:
595:
594:
589:
582:
579:
568:William McCune
538:
514:
488:
487:
476:
473:
470:
467:
464:
461:
458:
455:
452:
449:
446:
443:
440:
437:
434:
431:
428:
425:
422:
399:
396:
388:
387:
376:
373:
369:
364:
360:
357:
354:
351:
347:
343:
340:
336:
332:
329:
326:
322:
318:
314:
310:
296:
285:
282:
279:
276:
273:
270:
267:
253:
242:
239:
235:
231:
228:
225:
221:
217:
213:
209:
206:
203:
199:
195:
192:
146:
122:
93:
92:
50:external links
39:
37:
30:
9:
6:
4:
3:
2:
664:
653:
650:
648:
645:
643:
640:
639:
637:
627:
623:
620:
617:
613:
610:
606:
602:
601:
593:
590:
588:
585:
584:
578:
576:
573:
569:
565:
563:
562:Alfred Tarski
558:
556:
552:
528:
512:
504:
500:
496:
491:
474:
471:
468:
462:
456:
453:
441:
435:
432:
429:
412:
409:
408:
407:
405:
395:
393:
374:
371:
367:
362:
358:
352:
349:
345:
338:
334:
330:
327:
324:
320:
312:
300:
297:
283:
280:
277:
274:
271:
268:
265:
257:
256:Commutativity
254:
240:
237:
233:
229:
226:
223:
219:
215:
211:
207:
204:
201:
197:
193:
190:
182:
181:Associativity
179:
178:
177:
175:
171:
167:
162:
160:
136:
120:
112:
108:
104:
100:
89:
86:
78:
68:
64:
58:
57:
51:
47:
43:
38:
29:
28:
19:
608:
566:
559:
498:
492:
489:
410:
401:
389:
298:
173:
169:
165:
163:
102:
96:
81:
72:
61:Please help
53:
67:introducing
636:Categories
598:References
553:. Boolean
551:complement
497:posed the
537:¬
513:∨
460:¬
457:∨
451:¬
445:¬
442:∨
433:∨
427:¬
421:¬
402:In 1933,
356:¬
353:∨
342:¬
339:∨
328:∨
317:¬
309:¬
281:∨
269:∨
238:∨
227:∨
205:∨
194:∨
145:¬
121:∨
75:June 2015
581:See also
549:Boolean
398:History
107:algebra
63:improve
172:, and
159:axioms
105:is an
48:, or
555:meet
529:and
527:join
101:, a
624:, "
607:,"
575:EQP
97:In
638::
505:.
413::
301::
258::
183::
176::
168:,
161::
52:,
44:,
618:"
475:.
472:a
469:=
466:)
463:b
454:a
448:(
439:)
436:b
430:a
424:(
375:a
372:=
368:)
363:)
359:b
350:a
346:(
335:)
331:b
325:a
321:(
313:(
284:a
278:b
275:=
272:b
266:a
241:c
234:)
230:b
224:a
220:(
216:=
212:)
208:c
202:b
198:(
191:a
174:c
170:b
166:a
88:)
82:(
77:)
73:(
59:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.