law word_adc_overflow_sym

bend-mathlib@0.8.1.0 · u32.bend:1016

import Base
import bend-mathlib@0.8.1.0/nat.bend as MNat

1016# The adder drops exactly one 2^n on overflow: 2^n <= a + b + carry-in implies to_nat (adc a b False c) + 2^n = a + b + carry-in, reversed to rewrite toward the simple side.
1017law word_adc_overflow_sym:
1018  for n: Nat
1019  for a: Word(n)
1020  for b: Word(n)
1021  for c: Bool
1022  for h: MNat.le(Nat.pow(2n, n), Nat.add(Nat.add(Word.to_nat(n, a), Word.to_nat(n, b)), Bool.pick(Nat, c, 1n, 0n)))
1023  {Nat.add(Nat.add(Word.to_nat(n, a), Word.to_nat(n, b)), Bool.pick(Nat, c, 1n, 0n)) == Nat.add(Word.to_nat(n, Word.adc(n, a, b, False{}, c)), Nat.pow(2n, n)) : Nat}