谓词、变量与论域

从一个可判真的问题开始

离散数学不是公式目录。先把“命题逻辑与谓词逻辑”中的本讲问题写成对象、假设与结论：为谓词、变量与论域手推最小正常例、边界例和反例，再用有限枚举或结构验证器核对中间状态。第一步固定定义和论域，第二步列出最小实例，第三步尝试构造证明或反例，最后才推广到任意规模。若连输入对象属于集合、函数、关系、图、序列还是随机变量都没写清，后面的符号运算没有稳定含义。
（本段唯一反查锚：cs-22-discrete-mathematics/01/04/谓词、变量与论域。）

定义、量词与不变量

本节核心为：谓词、变量与论域的核心是：谓词在给定论域和变量赋值下成为命题，自由变量与约束变量必须区分；必须把对象类型、量词、构造或算法不变量和结论同时写清。把定义拆成对象类型、量词顺序、允许操作和判定条件。全称命题要求覆盖任意合法对象，存在命题要求给出见证并验证，唯一性还需证明任意两个见证相等。算法型命题要写循环或递归不变量、终止度量和输出条件。
（本段唯一反查锚：cs-22-discrete-mathematics/01/04/谓词、变量与论域。）

遇到“显然”时停下来问：这一步用了定义、已知定理还是直觉图形？集合图、真值表、小图和数值序列能帮助发现结构，但证明必须说明为什么任意对象都被覆盖。对于谓词、变量与论域，请在纸边标出每个变量的论域和依赖，防止量词交换、代表元偷换或下标越界。
（本段唯一反查锚：cs-22-discrete-mathematics/01/04/谓词、变量与论域。）

跟老师手推一个实例

选择不大于10个元素的实例。先列全集或输入编码，再按规则推进至少8步，每一步记录当前集合、真值赋值、关系矩阵、递推项、图的队列/栈、模余数或计数部分和。结束时用另一种表示复核，例如关系矩阵对照有向图、图遍历对照父指针、闭式对照递推前几项。
（本段唯一反查锚：cs-22-discrete-mathematics/01/04/谓词、变量与论域。）

然后主动改动一个条件：去掉非空、互素、连通、非负权、独立或有限性假设中的一个，寻找最短失败例。反例不只是宣布命题错，要逐项证明它满足原假设却违反结论；若命题需修订，就写出最弱的补充条件而不是把结论改成琐碎真话。
（本段唯一反查锚：cs-22-discrete-mathematics/01/04/谓词、变量与论域。）

严格证明的选择

直接证明适合从定义连续推演；逆否适合结论否定给出结构信息；反证适合否定后产生不可能对象；归纳适合自然数或递归生成结构；双计数与双射适合等式；极值和最小反例适合下降论证；概率方法通过坏事件概率小于1证明存在。选择方法后仍须完成每一条推理。
（本段唯一反查锚：cs-22-discrete-mathematics/01/04/谓词、变量与论域。）

证明双条件时分成两个方向。证明构造正确时分成“输出一定合法”和“每个目标对象都能得到”或“算法返回是正确答案”和“算法不会遗漏更优答案”。证明归纳时写基例、归纳假设适用范围、从k到k+1的桥；强归纳中引用更小情形前要证明对象确实变小。
（本段唯一反查锚：cs-22-discrete-mathematics/01/04/谓词、变量与论域。）

可运行实验与有限证据

课程中的Python实验从标准输入读取并输出稳定结果，至少四组不同测试覆盖正常、空/最小、失败和组合情形。实验对象包括真值赋值、集合关系、计数组合、递推序列、图遍历、树、同余、布尔式和编码。先让清晰参考实现通过，再讨论优化；遍历顺序和并列选择必须在题面声明。
（本段唯一反查锚：cs-22-discrete-mathematics/01/04/谓词、变量与论域。）

程序枚举到某个规模没有找到反例，只能成为发现证据，不能冒充无限命题证明。反过来，找到一个合法反例足以推翻全称命题。代码结果要与数学对象一一对应：顶点编号、是否允许重边、模余数约定、空积、0的阶乘、图是否有向都必须一致。
（本段唯一反查锚：cs-22-discrete-mathematics/01/04/谓词、变量与论域。）

计数与复杂度检查

若有n个布尔变量，真值赋值有2^n个；n元素集合有2^n个子集；简单无向图潜在边有n(n−1)/2条。指数出现时指出每一位独立选择来自哪里，不要只背公式。算法复杂度写输入长度与表示：邻接矩阵和邻接表对同一图会给不同空间和遍历代价。
（本段唯一反查锚：cs-22-discrete-mathematics/01/04/谓词、变量与论域。）

本讲简化核对任务有8组对象，每组检查6个局部条件，共48次局部检查。这个数字只解释当前小实例，不能替代一般复杂度。换成规模n后重写求和或递推，做n=0、1、2和翻倍时的极端值检查。
（本段唯一反查锚：cs-22-discrete-mathematics/01/04/谓词、变量与论域。）

易错边界

最危险的误解是：省略论域会改变量词命题真值，变量捕获会悄悄改义。把它改写成一个错误命题，给出最短反例，再说明正确版本增加了什么假设。若边界涉及术语对，例如属于/包含、逆/逆否、独立/互斥、路径/迹、MST/最短路，必须分别写定义并指出决定性差异。
（本段唯一反查锚：cs-22-discrete-mathematics/01/04/谓词、变量与论域。）

答案数值正确也可能推理错误。检查是否除以零、是否遗漏空集、是否重复计数、是否把有序当无序、是否在模运算中非法约分、是否把平均情形当最坏情形。每一步写理由能让这些错误在中间暴露，而不是只在最后对答案。
（本段唯一反查锚：cs-22-discrete-mathematics/01/04/谓词、变量与论域。）

前后连接

逻辑为证明提供语法，集合函数关系定义离散结构，归纳处理递归对象，计数与生成函数计算规模，递推描述增长，图树建模连接，数论支撑模算法，布尔代数连接电路，概率方法证明存在，组合设计与编码把结构转成可靠性。为谓词、变量与论域画一条向前依赖和一条向后应用。
（本段唯一反查锚：cs-22-discrete-mathematics/01/04/谓词、变量与论域。）

练习与闭卷自检

完成单选、多选、计算和本节可用的代码题；章末严格证明题按公开rubric提交。闭卷回答：对象和论域是什么，量词顺序怎样，核心构造或不变量是什么，最短反例是什么，代码能验证到什么范围，怎样把小实例提升为一般证明。只会复述定理名不合格。
（本段唯一反查锚：cs-22-discrete-mathematics/01/04/谓词、变量与论域。）