Metamath Proof Explorer |
< Previous
Next >
Nearby theorems |
||
Mirrors > Home > MPE Home > Th. List > sadadd | Structured version Visualization version GIF version |
Description: For sequences that
correspond to valid integers, the adder sequence
function produces the sequence for the sum. This is effectively a proof
of the correctness of the ripple carry adder, implemented with logic
gates corresponding to df-had 1585 and df-cad 1599.
It is interesting to consider in what sense the sadd function can be said to be "adding" things outside the range of the bits function, that is, when adding sequences that are not eventually constant and so do not denote any integer. The correct interpretation is that the sequences are representations of 2-adic integers, which have a natural ring structure. (Contributed by Mario Carneiro, 9-Sep-2016.) |
Ref | Expression |
---|---|
sadadd | ⊢ ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) → ((bits‘𝐴) sadd (bits‘𝐵)) = (bits‘(𝐴 + 𝐵))) |
Step | Hyp | Ref | Expression |
---|---|---|---|
1 | bitsss 15765 | . . . . . 6 ⊢ (bits‘𝐴) ⊆ ℕ0 | |
2 | bitsss 15765 | . . . . . 6 ⊢ (bits‘𝐵) ⊆ ℕ0 | |
3 | sadcl 15801 | . . . . . 6 ⊢ (((bits‘𝐴) ⊆ ℕ0 ∧ (bits‘𝐵) ⊆ ℕ0) → ((bits‘𝐴) sadd (bits‘𝐵)) ⊆ ℕ0) | |
4 | 1, 2, 3 | mp2an 688 | . . . . 5 ⊢ ((bits‘𝐴) sadd (bits‘𝐵)) ⊆ ℕ0 |
5 | 4 | sseli 3962 | . . . 4 ⊢ (𝑘 ∈ ((bits‘𝐴) sadd (bits‘𝐵)) → 𝑘 ∈ ℕ0) |
6 | 5 | a1i 11 | . . 3 ⊢ ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) → (𝑘 ∈ ((bits‘𝐴) sadd (bits‘𝐵)) → 𝑘 ∈ ℕ0)) |
7 | bitsss 15765 | . . . . 5 ⊢ (bits‘(𝐴 + 𝐵)) ⊆ ℕ0 | |
8 | 7 | sseli 3962 | . . . 4 ⊢ (𝑘 ∈ (bits‘(𝐴 + 𝐵)) → 𝑘 ∈ ℕ0) |
9 | 8 | a1i 11 | . . 3 ⊢ ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) → (𝑘 ∈ (bits‘(𝐴 + 𝐵)) → 𝑘 ∈ ℕ0)) |
10 | eqid 2821 | . . . . . . . . 9 ⊢ seq0((𝑐 ∈ 2o, 𝑚 ∈ ℕ0 ↦ if(cadd(𝑚 ∈ (bits‘𝐴), 𝑚 ∈ (bits‘𝐵), ∅ ∈ 𝑐), 1o, ∅)), (𝑛 ∈ ℕ0 ↦ if(𝑛 = 0, ∅, (𝑛 − 1)))) = seq0((𝑐 ∈ 2o, 𝑚 ∈ ℕ0 ↦ if(cadd(𝑚 ∈ (bits‘𝐴), 𝑚 ∈ (bits‘𝐵), ∅ ∈ 𝑐), 1o, ∅)), (𝑛 ∈ ℕ0 ↦ if(𝑛 = 0, ∅, (𝑛 − 1)))) | |
11 | eqid 2821 | . . . . . . . . 9 ⊢ ◡(bits ↾ ℕ0) = ◡(bits ↾ ℕ0) | |
12 | simpll 763 | . . . . . . . . 9 ⊢ (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) ∧ 𝑘 ∈ ℕ0) → 𝐴 ∈ ℤ) | |
13 | simplr 765 | . . . . . . . . 9 ⊢ (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) ∧ 𝑘 ∈ ℕ0) → 𝐵 ∈ ℤ) | |
14 | simpr 485 | . . . . . . . . . 10 ⊢ (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) ∧ 𝑘 ∈ ℕ0) → 𝑘 ∈ ℕ0) | |
15 | 1nn0 11902 | . . . . . . . . . . 11 ⊢ 1 ∈ ℕ0 | |
16 | 15 | a1i 11 | . . . . . . . . . 10 ⊢ (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) ∧ 𝑘 ∈ ℕ0) → 1 ∈ ℕ0) |
17 | 14, 16 | nn0addcld 11948 | . . . . . . . . 9 ⊢ (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) ∧ 𝑘 ∈ ℕ0) → (𝑘 + 1) ∈ ℕ0) |
18 | 10, 11, 12, 13, 17 | sadaddlem 15805 | . . . . . . . 8 ⊢ (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) ∧ 𝑘 ∈ ℕ0) → (((bits‘𝐴) sadd (bits‘𝐵)) ∩ (0..^(𝑘 + 1))) = (bits‘((𝐴 + 𝐵) mod (2↑(𝑘 + 1))))) |
19 | 12, 13 | zaddcld 12080 | . . . . . . . . 9 ⊢ (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) ∧ 𝑘 ∈ ℕ0) → (𝐴 + 𝐵) ∈ ℤ) |
20 | bitsmod 15775 | . . . . . . . . 9 ⊢ (((𝐴 + 𝐵) ∈ ℤ ∧ (𝑘 + 1) ∈ ℕ0) → (bits‘((𝐴 + 𝐵) mod (2↑(𝑘 + 1)))) = ((bits‘(𝐴 + 𝐵)) ∩ (0..^(𝑘 + 1)))) | |
21 | 19, 17, 20 | syl2anc 584 | . . . . . . . 8 ⊢ (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) ∧ 𝑘 ∈ ℕ0) → (bits‘((𝐴 + 𝐵) mod (2↑(𝑘 + 1)))) = ((bits‘(𝐴 + 𝐵)) ∩ (0..^(𝑘 + 1)))) |
22 | 18, 21 | eqtrd 2856 | . . . . . . 7 ⊢ (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) ∧ 𝑘 ∈ ℕ0) → (((bits‘𝐴) sadd (bits‘𝐵)) ∩ (0..^(𝑘 + 1))) = ((bits‘(𝐴 + 𝐵)) ∩ (0..^(𝑘 + 1)))) |
23 | 22 | eleq2d 2898 | . . . . . 6 ⊢ (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) ∧ 𝑘 ∈ ℕ0) → (𝑘 ∈ (((bits‘𝐴) sadd (bits‘𝐵)) ∩ (0..^(𝑘 + 1))) ↔ 𝑘 ∈ ((bits‘(𝐴 + 𝐵)) ∩ (0..^(𝑘 + 1))))) |
24 | elin 4168 | . . . . . 6 ⊢ (𝑘 ∈ (((bits‘𝐴) sadd (bits‘𝐵)) ∩ (0..^(𝑘 + 1))) ↔ (𝑘 ∈ ((bits‘𝐴) sadd (bits‘𝐵)) ∧ 𝑘 ∈ (0..^(𝑘 + 1)))) | |
25 | elin 4168 | . . . . . 6 ⊢ (𝑘 ∈ ((bits‘(𝐴 + 𝐵)) ∩ (0..^(𝑘 + 1))) ↔ (𝑘 ∈ (bits‘(𝐴 + 𝐵)) ∧ 𝑘 ∈ (0..^(𝑘 + 1)))) | |
26 | 23, 24, 25 | 3bitr3g 314 | . . . . 5 ⊢ (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) ∧ 𝑘 ∈ ℕ0) → ((𝑘 ∈ ((bits‘𝐴) sadd (bits‘𝐵)) ∧ 𝑘 ∈ (0..^(𝑘 + 1))) ↔ (𝑘 ∈ (bits‘(𝐴 + 𝐵)) ∧ 𝑘 ∈ (0..^(𝑘 + 1))))) |
27 | nn0uz 12269 | . . . . . . . . 9 ⊢ ℕ0 = (ℤ≥‘0) | |
28 | 14, 27 | eleqtrdi 2923 | . . . . . . . 8 ⊢ (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) ∧ 𝑘 ∈ ℕ0) → 𝑘 ∈ (ℤ≥‘0)) |
29 | eluzfz2 12905 | . . . . . . . 8 ⊢ (𝑘 ∈ (ℤ≥‘0) → 𝑘 ∈ (0...𝑘)) | |
30 | 28, 29 | syl 17 | . . . . . . 7 ⊢ (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) ∧ 𝑘 ∈ ℕ0) → 𝑘 ∈ (0...𝑘)) |
31 | 14 | nn0zd 12074 | . . . . . . . 8 ⊢ (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) ∧ 𝑘 ∈ ℕ0) → 𝑘 ∈ ℤ) |
32 | fzval3 13096 | . . . . . . . 8 ⊢ (𝑘 ∈ ℤ → (0...𝑘) = (0..^(𝑘 + 1))) | |
33 | 31, 32 | syl 17 | . . . . . . 7 ⊢ (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) ∧ 𝑘 ∈ ℕ0) → (0...𝑘) = (0..^(𝑘 + 1))) |
34 | 30, 33 | eleqtrd 2915 | . . . . . 6 ⊢ (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) ∧ 𝑘 ∈ ℕ0) → 𝑘 ∈ (0..^(𝑘 + 1))) |
35 | 34 | biantrud 532 | . . . . 5 ⊢ (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) ∧ 𝑘 ∈ ℕ0) → (𝑘 ∈ ((bits‘𝐴) sadd (bits‘𝐵)) ↔ (𝑘 ∈ ((bits‘𝐴) sadd (bits‘𝐵)) ∧ 𝑘 ∈ (0..^(𝑘 + 1))))) |
36 | 34 | biantrud 532 | . . . . 5 ⊢ (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) ∧ 𝑘 ∈ ℕ0) → (𝑘 ∈ (bits‘(𝐴 + 𝐵)) ↔ (𝑘 ∈ (bits‘(𝐴 + 𝐵)) ∧ 𝑘 ∈ (0..^(𝑘 + 1))))) |
37 | 26, 35, 36 | 3bitr4d 312 | . . . 4 ⊢ (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) ∧ 𝑘 ∈ ℕ0) → (𝑘 ∈ ((bits‘𝐴) sadd (bits‘𝐵)) ↔ 𝑘 ∈ (bits‘(𝐴 + 𝐵)))) |
38 | 37 | ex 413 | . . 3 ⊢ ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) → (𝑘 ∈ ℕ0 → (𝑘 ∈ ((bits‘𝐴) sadd (bits‘𝐵)) ↔ 𝑘 ∈ (bits‘(𝐴 + 𝐵))))) |
39 | 6, 9, 38 | pm5.21ndd 381 | . 2 ⊢ ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) → (𝑘 ∈ ((bits‘𝐴) sadd (bits‘𝐵)) ↔ 𝑘 ∈ (bits‘(𝐴 + 𝐵)))) |
40 | 39 | eqrdv 2819 | 1 ⊢ ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) → ((bits‘𝐴) sadd (bits‘𝐵)) = (bits‘(𝐴 + 𝐵))) |
Colors of variables: wff setvar class |
Syntax hints: → wi 4 ↔ wb 207 ∧ wa 396 = wceq 1528 caddwcad 1598 ∈ wcel 2105 ∩ cin 3934 ⊆ wss 3935 ∅c0 4290 ifcif 4465 ↦ cmpt 5138 ◡ccnv 5548 ↾ cres 5551 ‘cfv 6349 (class class class)co 7145 ∈ cmpo 7147 1oc1o 8086 2oc2o 8087 0cc0 10526 1c1 10527 + caddc 10529 − cmin 10859 2c2 11681 ℕ0cn0 11886 ℤcz 11970 ℤ≥cuz 12232 ...cfz 12882 ..^cfzo 13023 mod cmo 13227 seqcseq 13359 ↑cexp 13419 bitscbits 15758 sadd csad 15759 |
This theorem was proved from axioms: ax-mp 5 ax-1 6 ax-2 7 ax-3 8 ax-gen 1787 ax-4 1801 ax-5 1902 ax-6 1961 ax-7 2006 ax-8 2107 ax-9 2115 ax-10 2136 ax-11 2151 ax-12 2167 ax-ext 2793 ax-rep 5182 ax-sep 5195 ax-nul 5202 ax-pow 5258 ax-pr 5321 ax-un 7450 ax-inf2 9093 ax-cnex 10582 ax-resscn 10583 ax-1cn 10584 ax-icn 10585 ax-addcl 10586 ax-addrcl 10587 ax-mulcl 10588 ax-mulrcl 10589 ax-mulcom 10590 ax-addass 10591 ax-mulass 10592 ax-distr 10593 ax-i2m1 10594 ax-1ne0 10595 ax-1rid 10596 ax-rnegex 10597 ax-rrecex 10598 ax-cnre 10599 ax-pre-lttri 10600 ax-pre-lttrn 10601 ax-pre-ltadd 10602 ax-pre-mulgt0 10603 ax-pre-sup 10604 |
This theorem depends on definitions: df-bi 208 df-an 397 df-or 842 df-3or 1080 df-3an 1081 df-xor 1496 df-tru 1531 df-fal 1541 df-had 1585 df-cad 1599 df-ex 1772 df-nf 1776 df-sb 2061 df-mo 2618 df-eu 2650 df-clab 2800 df-cleq 2814 df-clel 2893 df-nfc 2963 df-ne 3017 df-nel 3124 df-ral 3143 df-rex 3144 df-reu 3145 df-rmo 3146 df-rab 3147 df-v 3497 df-sbc 3772 df-csb 3883 df-dif 3938 df-un 3940 df-in 3942 df-ss 3951 df-pss 3953 df-nul 4291 df-if 4466 df-pw 4539 df-sn 4560 df-pr 4562 df-tp 4564 df-op 4566 df-uni 4833 df-int 4870 df-iun 4914 df-disj 5024 df-br 5059 df-opab 5121 df-mpt 5139 df-tr 5165 df-id 5454 df-eprel 5459 df-po 5468 df-so 5469 df-fr 5508 df-se 5509 df-we 5510 df-xp 5555 df-rel 5556 df-cnv 5557 df-co 5558 df-dm 5559 df-rn 5560 df-res 5561 df-ima 5562 df-pred 6142 df-ord 6188 df-on 6189 df-lim 6190 df-suc 6191 df-iota 6308 df-fun 6351 df-fn 6352 df-f 6353 df-f1 6354 df-fo 6355 df-f1o 6356 df-fv 6357 df-isom 6358 df-riota 7103 df-ov 7148 df-oprab 7149 df-mpo 7150 df-om 7569 df-1st 7680 df-2nd 7681 df-wrecs 7938 df-recs 7999 df-rdg 8037 df-1o 8093 df-2o 8094 df-oadd 8097 df-er 8279 df-map 8398 df-pm 8399 df-en 8499 df-dom 8500 df-sdom 8501 df-fin 8502 df-sup 8895 df-inf 8896 df-oi 8963 df-dju 9319 df-card 9357 df-pnf 10666 df-mnf 10667 df-xr 10668 df-ltxr 10669 df-le 10670 df-sub 10861 df-neg 10862 df-div 11287 df-nn 11628 df-2 11689 df-3 11690 df-n0 11887 df-xnn0 11957 df-z 11971 df-uz 12233 df-rp 12380 df-fz 12883 df-fzo 13024 df-fl 13152 df-mod 13228 df-seq 13360 df-exp 13420 df-hash 13681 df-cj 14448 df-re 14449 df-im 14450 df-sqrt 14584 df-abs 14585 df-clim 14835 df-sum 15033 df-dvds 15598 df-bits 15761 df-sad 15790 |
This theorem is referenced by: bitsres 15812 smumullem 15831 |
Copyright terms: Public domain | W3C validator |