两个二进制数的乘法

Question

我需要执行将两个由布尔值列表表示的二进制数相乘的函数。这是我写的：

Fixpoint brmul_r (x y res: list bool): list bool := 
 match x,y,res with
 |x,y,res-> if value x >0 then res else if (value x) mod 2 = 0 then brmul_r ((value x/2) (value y*2) (badd res y)) 
 else brmul_r (x y*2 res)
end.

但它不起作用..我该怎么办？

提前致谢！

Answer 1

该代码有很多问题：

语法错误：您想在 match.

=>

->

实际上，您没有利用模式匹配，因此您可以完全删除它并从 if ... 开始定义。
然后 Coq 抱怨 _ > _ 的类型是 Prop。您需要使用布尔版本 _ <? _ 来代替，之后的相等性也是如此：_ =? _ 而不是 _ = _.
在brmul_r ((value x/2) (value y*2) (badd res y))中，外括号不应该存在； brmul_r 应该接收三个参数，而不是一个参数，对于 brmul_r (x y*2 res)
value x/2 是什么意思？是 value (x / 2) 还是 (value x) / 2？前者不会 type-check 除非您重新定义 _ / _ 符号来处理布尔列表。但是后者的类型是 nat，而 brmul_r 期望类型是 list bool，所以它也不起作用。类似的观察结果适用于 value y*2.
这不是 Coq 抱怨的事情（必须首先解决 5 中的问题），但 Coq 不清楚你的定义是否终止，因为你正在使用 brmul_r 来定义brmul_r 并喂养它 non-structurally 减少参数。事实上，您甚至可以在最后一个分支中为它提供 increasing 个参数（我说的是 brmul_r x y*2 res）。

那么应该怎么办呢？让 Coq 相信函数终止是这里的真正问题，剩下的只是对语法的混淆。由于这是列表上的函数，它应该在列表结构上递归，因此它应该具有以下基本形状（我假设 Require Import List. Import ListNotations. 的上下文）：

Fixpoint brmul_r (xs ys : list bool) : list bool :=
  match xs with
  | [] => (* TODO *)
  | hd :: tl => (* TODO *)
  end.

假设列表的第一个元素是最低有效位，匹配它也是有用的，所以结构变成：

Fixpoint brmul_r (xs ys : list bool) : list bool :=
  match xs with
  | [] => (* TODO *)
  | false :: tl => (* TODO *)
  | true :: tl => (* TODO *)
  end.

现在的目标是当我们已经知道 tl 与 ys 的乘积时，用 ys 表示 false :: tl 的乘积。转换为数字（出于直觉），我们想在已经知道如何计算 (value tl) * (value ys) 的情况下找到 (2 * (value tl)) * (value ys)。这样说，很明显我们只需要复制后者的结果。回到我们的列表表示，我们观察到复制对应于前置 false，因此我们可以更新我们的定义如下：

Fixpoint brmul_r (xs ys : list bool) : list bool :=
  match xs with
  | [] => (* TODO *)
  | false :: tl => false :: brmul_r tl ys
  | true :: tl => (* TODO *)
  end.

现在您可以使用相同的推理来完成功能。

未来：

请包含必要的上下文。在这种情况下，它将是您导入的模块和自定义函数，例如 value.
遵循 Coq 教程可能有助于解决所有语法问题以及递归和函数式编程背后的直觉。 Software Foundations is very good. There are also others.
现在有 dedicated Stack Exchange site 证明 Assistant-related 问题。

两个二进制数的乘法

multiplication of two binary numbers

implementation

coq