AFTD Auto-Formalizing Theoretical Domains

bitword_rotate_three_four

theoremverified

Sanity check: rotating the 3-bit words 100 and 011 gives 001 and 110.

Statement

theorem bitword_rotate_three_four : bitword_rotate 3 4 = 1 ∧ bitword_rotate 3 3 = 6
Source
sanity check for bitword_rotate (OP-392)
Verified
20 Oct 2026
Axioms
propext
Built on 1
  • bitword_rotateCyclic rotation of an n-bit word x (a number below 2^n) by one position: the word is shifted up and its top bit moves to the bottom.

The proof, explained

The theorem asserts that rotating the 3-bit words 4 (binary 100) and 3 (binary 011) yields 1 (binary 001) and 6 (binary 110), respectively. Because both inputs and parameters are concrete natural numbers, the definition of bitword_rotate evaluates directly to numerical values. The proof is completed by the decide tactic, which computes the arithmetic operations.

  1. bitword_rotate 3 4 = 1 ∧ bitword_rotate 3 3 = 6 automation

    Both conjuncts follow by direct arithmetic evaluation of the definition bitword_rotate n x = (2 * x) % 2^n + x / 2^(n - 1). For n = 3 and x = 4, this computes to (8 % 8) + 4 / 4 = 0 + 1 = 1. For n = 3 and x = 3, it computes to (6 % 8) + 3 / 4 = 6 + 0 = 6. The decide tactic completes both numerical checks by decision procedure evaluation.

    line 1

    theorem bitword_rotate_three_four : bitword_rotate 3 4 = 1 ∧ bitword_rotate 3 3 = 6 := by decide

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

theorem bitword_rotate_three_four : bitword_rotate 3 4 = 1 ∧ bitword_rotate 3 3 = 6 := by decide
See it in the graphDiscuss this resultChallenge it