{0,1}上不同时含子串101和010的字符串集合形式化表示正确性验证

首先明确目标集合：{0,1}上所有**不同时包含子串"101"和"010"**的字符串，即字符串满足：要么不包含"101"，要么不包含"010"（允许两者都不包含）。

原表示的问题分析 #

给出的表达式：

{w∈{0,1}* | ∀x,y∈{0,1}* s.t w = x101y ⇔ ∀x',y'∈ {0,1}*,w ≠ x'010y'}

其中的双蕴含⇔表示：w包含"101"当且仅当w不包含"010"。这等价于两个逻辑断言的组合：

• 若w包含"101"，则w不包含"010"；
• 若w不包含"010"，则w一定包含"101"。

这和目标集合的定义不符：目标集合允许**既不包含"101"也不包含"010"**的字符串（比如空串、"0"、"1"、"00"、"11"等），但原表达式会将这类字符串排除在外——因为对于这类字符串，左边的∀x,y∈{0,1}* s.t w = x101y是假命题，右边的∀x',y'∈ {0,1}*,w ≠ x'010y'是真命题，假命题与真命题的双蕴含结果为假，因此这类字符串不会被纳入原表达式定义的集合。

正确的形式化表示 #

准确的表示可以有两种等价写法：

1. 直接否定“同时包含两个子串”的情况：

{w∈{0,1}* | ¬(∃x,y∈{0,1}*, w=x101y ∧ ∃x',y'∈{0,1}*, w=x'010y')}

2. 用逻辑或表示“至少不包含其中一个子串”：

{w∈{0,1}* | (∀x,y∈{0,1}*, w≠x101y) ∨ (∀x',y'∈{0,1}*, w≠x'010y')}

内容的提问来源于stack exchange，提问作者user19756157