MPE Home Metamath Proof Explorer < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  MPE Home  >  Th. List  >  sadval Structured version   Unicode version

Theorem sadval 13956
Description: The full adder sequence is the half adder function applied to the inputs and the carry sequence. (Contributed by Mario Carneiro, 5-Sep-2016.)
Hypotheses
Ref Expression
sadval.a  |-  ( ph  ->  A  C_  NN0 )
sadval.b  |-  ( ph  ->  B  C_  NN0 )
sadval.c  |-  C  =  seq 0 ( ( c  e.  2o ,  m  e.  NN0  |->  if (cadd ( m  e.  A ,  m  e.  B ,  (/)  e.  c ) ,  1o ,  (/) ) ) ,  ( n  e.  NN0  |->  if ( n  =  0 ,  (/) ,  ( n  - 
1 ) ) ) )
sadcp1.n  |-  ( ph  ->  N  e.  NN0 )
Assertion
Ref Expression
sadval  |-  ( ph  ->  ( N  e.  ( A sadd  B )  <-> hadd ( N  e.  A ,  N  e.  B ,  (/)  e.  ( C `  N ) ) ) )
Distinct variable groups:    m, c, n    A, c, m    B, c, m    n, N
Allowed substitution hints:    ph( m, n, c)    A( n)    B( n)    C( m, n, c)    N( m, c)

Proof of Theorem sadval
Dummy variable  k is distinct from all other variables.
StepHypRef Expression
1 sadval.a . . . 4  |-  ( ph  ->  A  C_  NN0 )
2 sadval.b . . . 4  |-  ( ph  ->  B  C_  NN0 )
3 sadval.c . . . 4  |-  C  =  seq 0 ( ( c  e.  2o ,  m  e.  NN0  |->  if (cadd ( m  e.  A ,  m  e.  B ,  (/)  e.  c ) ,  1o ,  (/) ) ) ,  ( n  e.  NN0  |->  if ( n  =  0 ,  (/) ,  ( n  - 
1 ) ) ) )
41, 2, 3sadfval 13952 . . 3  |-  ( ph  ->  ( A sadd  B )  =  { k  e. 
NN0  | hadd ( k  e.  A ,  k  e.  B ,  (/)  e.  ( C `  k ) ) } )
54eleq2d 2532 . 2  |-  ( ph  ->  ( N  e.  ( A sadd  B )  <->  N  e.  { k  e.  NN0  | hadd ( k  e.  A ,  k  e.  B ,  (/)  e.  ( C `
 k ) ) } ) )
6 sadcp1.n . . 3  |-  ( ph  ->  N  e.  NN0 )
7 eleq1 2534 . . . . 5  |-  ( k  =  N  ->  (
k  e.  A  <->  N  e.  A ) )
8 eleq1 2534 . . . . 5  |-  ( k  =  N  ->  (
k  e.  B  <->  N  e.  B ) )
9 fveq2 5859 . . . . . 6  |-  ( k  =  N  ->  ( C `  k )  =  ( C `  N ) )
109eleq2d 2532 . . . . 5  |-  ( k  =  N  ->  ( (/) 
e.  ( C `  k )  <->  (/)  e.  ( C `  N ) ) )
117, 8, 10hadbi123d 1428 . . . 4  |-  ( k  =  N  ->  (hadd ( k  e.  A ,  k  e.  B ,  (/)  e.  ( C `
 k ) )  <-> hadd ( N  e.  A ,  N  e.  B ,  (/)  e.  ( C `
 N ) ) ) )
1211elrab3 3257 . . 3  |-  ( N  e.  NN0  ->  ( N  e.  { k  e. 
NN0  | hadd ( k  e.  A ,  k  e.  B ,  (/)  e.  ( C `  k ) ) }  <-> hadd ( N  e.  A ,  N  e.  B ,  (/)  e.  ( C `  N ) ) ) )
136, 12syl 16 . 2  |-  ( ph  ->  ( N  e.  {
k  e.  NN0  | hadd ( k  e.  A ,  k  e.  B ,  (/)  e.  ( C `
 k ) ) }  <-> hadd ( N  e.  A ,  N  e.  B ,  (/)  e.  ( C `
 N ) ) ) )
145, 13bitrd 253 1  |-  ( ph  ->  ( N  e.  ( A sadd  B )  <-> hadd ( N  e.  A ,  N  e.  B ,  (/)  e.  ( C `  N ) ) ) )
Colors of variables: wff setvar class
Syntax hints:    -> wi 4    <-> wb 184    = wceq 1374  haddwhad 1424  caddwcad 1425    e. wcel 1762   {crab 2813    C_ wss 3471   (/)c0 3780   ifcif 3934    |-> cmpt 4500   ` cfv 5581  (class class class)co 6277    |-> cmpt2 6279   1oc1o 7115   2oc2o 7116   0cc0 9483   1c1 9484    - cmin 9796   NN0cn0 10786    seqcseq 12065   sadd csad 13920
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1596  ax-4 1607  ax-5 1675  ax-6 1714  ax-7 1734  ax-8 1764  ax-9 1766  ax-10 1781  ax-11 1786  ax-12 1798  ax-13 1963  ax-ext 2440  ax-sep 4563  ax-nul 4571  ax-pow 4620  ax-pr 4681  ax-un 6569  ax-cnex 9539  ax-resscn 9540  ax-1cn 9541  ax-icn 9542  ax-addcl 9543  ax-addrcl 9544  ax-mulcl 9545  ax-mulrcl 9546  ax-i2m1 9551  ax-1ne0 9552  ax-rrecex 9555  ax-cnre 9556
This theorem depends on definitions:  df-bi 185  df-or 370  df-an 371  df-3or 969  df-3an 970  df-xor 1356  df-tru 1377  df-had 1426  df-cad 1427  df-ex 1592  df-nf 1595  df-sb 1707  df-eu 2274  df-mo 2275  df-clab 2448  df-cleq 2454  df-clel 2457  df-nfc 2612  df-ne 2659  df-ral 2814  df-rex 2815  df-reu 2816  df-rab 2818  df-v 3110  df-sbc 3327  df-csb 3431  df-dif 3474  df-un 3476  df-in 3478  df-ss 3485  df-pss 3487  df-nul 3781  df-if 3935  df-pw 4007  df-sn 4023  df-pr 4025  df-tp 4027  df-op 4029  df-uni 4241  df-iun 4322  df-br 4443  df-opab 4501  df-mpt 4502  df-tr 4536  df-eprel 4786  df-id 4790  df-po 4795  df-so 4796  df-fr 4833  df-we 4835  df-ord 4876  df-on 4877  df-lim 4878  df-suc 4879  df-xp 5000  df-rel 5001  df-cnv 5002  df-co 5003  df-dm 5004  df-rn 5005  df-res 5006  df-ima 5007  df-iota 5544  df-fun 5583  df-fn 5584  df-f 5585  df-f1 5586  df-fo 5587  df-f1o 5588  df-fv 5589  df-ov 6280  df-oprab 6281  df-mpt2 6282  df-om 6674  df-recs 7034  df-rdg 7068  df-nn 10528  df-n0 10787  df-seq 12066  df-sad 13951
This theorem is referenced by:  sadadd2lem  13959  saddisjlem  13964
  Copyright terms: Public domain W3C validator