math - 证明语言属性

Question

我正在学习关于编程的正式基础的课程，我们所涵盖的一件事是证明语言的某些属性，我已经完成了大部分工作，但是我被这两个问题所困扰，因为我不知道如何证明他们。

它们如下：

A ^ (B ^ C) = (A ^ B) ^ C （我相信这是关联规则）

A ^ (BUC) = (A ^ B) U ( A ^ C) (分配规则)

在这些示例中，我使用 ^ 来表示连接

Answer 1

第一的

A^B 是所有单词 x 使得 A 中有 v 和 B 中有 w 使得 x = vw

让我们证明 A^(B^C) 包含在 (A^B)^C 中

A^(B^C) 是所有单词 x，使得 A 中有 v，B^C 中有 w，使得 x=vw

w = lm 其中 l 在 B 中，m 在 C 中，然后 x=vlm

x=(vl)m =v(lm) 因为 vl 在 A^B qnd m 在 C 中，所以 x 在 (A^B)^C 中。

则 A^(B^C) 包含在 (A^B)^C 中。

逆包含的相同证明

那么 A^(B^C) =(A^B)^C

第二：

x 在 BUC 中当且仅当 x 在 B 中或 x 在 C 中。

第一个包含：

如果x 在 A ^ (BUC)

然后 x = vw 其中 v 在 A 中，w 在 B 或 C 中

那么 x 在 A^B 或 A^C 中

那么x 在 (A ^ B) U ( A ^ C)

第二次包含

如果x 在 (A ^ B) U ( A ^ C)

然后 x = vw 与 A 中的 v 和 B 中的 w 或 x = vw 与 A 中的 v 和 C 中的 w

那么因为 v 总是是 A

然后 x = vw 其中 v 在 A 中，w 在 B 或 C 中

x 在 A ^ (BUC)

所以A ^ (B U C) = (A ^ B) U ( A ^ C)