求证(a∣b)*与(a*b*)* 的等价性
时间: 2023-10-06 07:14:36 浏览: 105
我们需要证明两个方向:
1. (a∣b)* 可转化为 (a*b*)*:
首先,对于任何一个字符串 s ∈ (a∣b)*,我们可以将 s 拆分成若干个字符,每个字符要么是 a,要么是 b,即 s = c1c2...cn,其中 ci ∈ {a, b}。我们可以将每个 ci 分别替换为 a 或者 ε,然后在每个字符之间添加一个 *,得到一个新的字符串 s' = a*c1*b*c2*...a*cn*b*. 那么 s' 显然属于 (a*b*)*,因为 s' 可以通过重复添加 a* 和 b* 来构造得到。
因此,我们证明了对于任意一个 s ∈ (a∣b)*,都存在一个 s' ∈ (a*b*)*,使得 s 和 s' 等价。
2. (a*b*)* 可转化为 (a∣b)*:
对于任何一个字符串 s ∈ (a*b*)*,我们可以将 s 拆分成若干个由 a 和 b 组成的子串,每个子串要么是 a,要么是 b*,即 s = x1x2...xn,其中 xi ∈ {a, b*}。我们可以将每个 xi 分别替换为 a 或者 b,得到一个新的字符串 s' = y1y2...yn,其中 yi ∈ {a, b}。那么 s' 显然属于 (a∣b)*,因为 s' 可以被看作 s 的一种“缩写”,即将每个 b* 替换为 b。
因此,我们证明了对于任意一个 s ∈ (a*b*)*,都存在一个 s' ∈ (a∣b)*,使得 s 和 s' 等价。
综上所述,我们证明了 (a∣b)* 与 (a*b*)* 的等价性。
相关问题
求证a与b与c的异或结果等于a与b与c的同或结果
首先,我们先来理解一下异或和同或的定义:
异或:对应位相同则为0,不同则为1。
同或:对应位相同则为1,不同则为0。
假设a,b,c三个数的二进制位分别为a0,a1,a2,...,an, b0,b1,b2,...,bn, c0,c1,c2,...,cn,则:
a异或b异或c的结果为:(a0^b0^c0, a1^b1^c1, a2^b2^c2, ..., an^bn^cn)
a同或b同或c的结果为:(a0&b0&c0) | (a0&~b0&~c0) | (~a0&b0&~c0) | (~a0&~b0&c0) | (a1&b1&c1) | (a1&~b1&~c1) | (~a1&b1&~c1) | (~a1&~b1&c1) | ... | (an&bn&cn) | (an&~bn&~cn) | (~an&bn&~cn) | (~an&~bn&cn)
要证明a异或b异或c等于a同或b同或c,我们需要证明它们的每一位都相等。
我们可以通过分类讨论来证明它们的每一位相等:
如果a,b,c的某一位都为0,则此位的结果为0。
如果a,b,c的某一位都为1,则此位的结果为0。
如果a,b,c的某一位有两个为1,则此位的结果为0。
如果a,b,c的某一位有三个为1,则此位的结果为1。
可以发现,以上四种情况,a异或b异或c的结果和a同或b同或c的结果都是相同的。
因此,我们证明了a异或b异或c等于a同或b同或c。
已知A=>B,求证B=>A—>B
根据推理规则中的蕴含规则,A=>B等价于 ~B=>~A。因此,我们可以得到 ~B=>~A和B=>A。接下来考虑证明B=>A—>B:
1. 假设B成立,即假设条件B为真。
2. 根据前提A=>B,我们可以得到A也为真。
3. 再根据A—>B,我们可以得到B为真。
4. 因此,我们可以得出结论B=>A—>B成立。
综上所述,B=>A—>B得证。
相关推荐
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)