如何在 Coq 中将命题公式转换为 DNF

Question

我已经定义了我的命题公式如下：

Inductive propForm : Set :=
| top : propForm
| bot : propForm
| var : propVar -> propForm
| orp : propForm -> propForm -> propForm
| andp : propForm -> propForm -> propForm.

我正在尝试定义一个函数，用于将命题公式转换为 DNF 中的命题公式。为此，我定义了一个使用分配律分布项的函数：

Fixpoint distribute (f:propForm) : propForm -> propForm :=
fix distribute1 (g:propForm) : propForm :=
match f with
| f1 \/p f2 => match g with
            | g1 \/p g2 => distribute1 g1 \/p distribute1 g2
            | _ => distribute f1 g \/p distribute f2 g
            end
| _ => match g with
       | g1 \/p g2 => distribute1 g1 \/p distribute1 g2
       | _ => f /\p g
       end
end.

这个功能很好用。但是，我仍然需要定义一个将命题公式转换为 DNF 的函数。下面的函数可以做我想做的事，但它不被 Coq 接受，因为对于最后一种情况，函数在 f' 中没有结构递减。任何提示和技巧将不胜感激。

Fixpoint toDNF (f':propForm):propForm :=
match f' with
| top => f'
| bot => f'
| var _ => f'
| f1 \/p f2 => toDNF f1 \/p toDNF f2
| f1 /\p f2 => toDNF (distribute f1 f2)
end.

Answer 1

您的函数是对半环表达式进行归一化的特例。我写了一个 post 解释了如何使用 Ssreflect 和 MathComp 库在算术表达式的情况下做到这一点，但我将在此处包含一个更直接的答案。

一个想法是使用列表的列表来表示DNF中的公式：毕竟，它们只是析取列表的合取，而析取列表只是文字列表。然后您可以重用列表库来编写您的函数：

Module Sol1.

Require Import Coq.Lists.List.
Import ListNotations.

Notation propVar := nat.

Inductive propAtom :=
| top | bot | var :> propVar -> propAtom.

Inductive propForm : Set :=
| atom :> propAtom -> propForm
| orp : propForm -> propForm -> propForm
| andp : propForm -> propForm -> propForm.

Definition dnfForm := list (list propAtom).

Fixpoint andd (f1 f2 : dnfForm) : dnfForm :=
  match f1 with
  | [] =>
    (* false && f2 = false *)
    []
  | cf :: f1 =>
    (* (cf || f1) && f2 = cf && f2 || f1 && f2 *)
    map (app cf) f2 ++ andd f1 f2
  end.

Fixpoint toDNF (f : propForm) : dnfForm :=
  match f with
  | atom a => [[a]]
  | orp f1 f2 => toDNF f1 ++ toDNF f2
  | andp f1 f2 => andd (toDNF f1) (toDNF f2)
  end.

Compute (toDNF (andp (orp 3 4) (orp 1 2))).

End Sol1.

这里有两点需要注意。首先，我将变量和常量分解为单独的 propAtom 类型，并调用了 distribute andd，因为你可以将其视为计算 DNF 中两个表达式的 AND。

这是另一个基于您的原始代码的解决方案。看来你的distribute函数保留了DNF中的不变性；也就是说，如果f1和f2在DNF中，那么distribute f1 f2也是。因此，您可以翻转调用顺序：

Module Sol2.

Notation propVar := nat.

Inductive propForm : Set :=
| top : propForm
| bot : propForm
| var :> propVar -> propForm
| orp : propForm -> propForm -> propForm
| andp : propForm -> propForm -> propForm.

Fixpoint distribute (f:propForm) : propForm -> propForm :=
fix distribute1 (g:propForm) : propForm :=
match f with
| orp f1 f2 => match g with
            | orp g1 g2 => orp (distribute1 g1) (distribute1 g2)
            | _ => orp (distribute f1 g) (distribute f2 g)
            end
| _ => match g with
       | orp g1 g2 => orp (distribute1 g1) (distribute1 g2)
       | _ => andp f g
       end
end.

Fixpoint toDNF (f':propForm):propForm :=
match f' with
| top => f'
| bot => f'
| var _ => f'
| orp f1 f2 => orp (toDNF f1) (toDNF f2)
| andp f1 f2 => distribute (toDNF f1) (toDNF f2)
end.

Compute (toDNF (andp (orp 3 4) (orp 1 2))).

End Sol2.

如何在 Coq 中将命题公式转换为 DNF

How to convert propositional formula to DNF in Coq

normalization

coq