Theorem consensus 767

Description: The consensus theorem. This theorem and its dual (with \/ and /\ interchanged) are commonly used in computer logic design to eliminate redundant terms from Boolean expressions. Specifically, we prove that the term (ps /\ ch) on the left-hand side is redundant.

Assertion

Ref	Expression
consensus	|- ((((ph /\ ps) \/ (-. ph /\ ch)) \/ (ps /\ ch)) <-> ((ph /\ ps) \/ (-. ph /\ ch)))

Proof of Theorem consensus

Step	Hyp	Ref	Expression
1		id 59	. . 3 |- (((ph /\ ps) \/ (-. ph /\ ch)) -> ((ph /\ ps) \/ (-. ph /\ ch)))
2		dedlema 762	. . . . . . 7 |- (ph -> (ps <-> ((ps /\ ph) \/ (ch /\ -. ph))))
3	2	biimpd 153	. . . . . 6 |- (ph -> (ps -> ((ps /\ ph) \/ (ch /\ -. ph))))
4	3	adantrd 391	. . . . 5 |- (ph -> ((ps /\ ch) -> ((ps /\ ph) \/ (ch /\ -. ph))))
5		dedlemb 763	. . . . . . 7 |- (-. ph -> (ch <-> ((ps /\ ph) \/ (ch /\ -. ph))))
6	5	biimpd 153	. . . . . 6 |- (-. ph -> (ch -> ((ps /\ ph) \/ (ch /\ -. ph))))
7	6	adantld 390	. . . . 5 |- (-. ph -> ((ps /\ ch) -> ((ps /\ ph) \/ (ch /\ -. ph))))
8	4, 7	pm2.61i 126	. . . 4 |- ((ps /\ ch) -> ((ps /\ ph) \/ (ch /\ -. ph)))
9		ancom 435	. . . . 5 |- ((ps /\ ph) <-> (ph /\ ps))
10		ancom 435	. . . . 5 |- ((ch /\ -. ph) <-> (-. ph /\ ch))
11	9, 10	orbi12i 257	. . . 4 |- (((ps /\ ph) \/ (ch /\ -. ph)) <-> ((ph /\ ps) \/ (-. ph /\ ch)))
12	8, 11	sylib 198	. . 3 |- ((ps /\ ch) -> ((ph /\ ps) \/ (-. ph /\ ch)))
13	1, 12	jaoi 341	. 2 |- ((((ph /\ ps) \/ (-. ph /\ ch)) \/ (ps /\ ch)) -> ((ph /\ ps) \/ (-. ph /\ ch)))
14		orc 269	. 2 |- (((ph /\ ps) \/ (-. ph /\ ch)) -> (((ph /\ ps) \/ (-. ph /\ ch)) \/ (ps /\ ch)))
15	13, 14	impbi 157	1 |- ((((ph /\ ps) \/ (-. ph /\ ch)) \/ (ps /\ ch)) <-> ((ph /\ ps) \/ (-. ph /\ ch)))

Syntax hints:  -. wn 2   -> wi 3   <-> wb 146   \/ wo 222   /\ wa 223

This theorem was proved from axioms:  ax-1 4  ax-2 5  ax-3 6  ax-mp 7

This theorem depends on definitions:  df-bi 147  df-or 224  df-an 225

Copyright terms: Public domain