A公理系统的正确性证明定理6.1 Armstrong推理规则是正确的。按函数依赖定义，假设 r是R<U,F>上的任一关系实例，t、s是r的任意两个元组。(1)证明自反律：若Y二XcU，则X→Y 参见P191.若t[X]=s[X], 由于YX,有t[Y]=s[Y], 所以有X →Y。自反律t[X] = s[X]X→Yt[Y] = s[Y]Ycx11
11 A公理系统的正确性证明 定理6.1 Armstrong推理规则是正确的。 按函数依赖定义，假设 r 是R<U, F>上的任一关系 实例，t、s 是 r 的任意两个元组。 (1)证明自反律: 若Y X U，则 X Y 参见P191. 若t[X]=s[X], 由于YX, 有t[Y]=s[Y], 所以有X Y。 t[X] = s[X] YX t[Y] = s[Y] X Y 自反律
A公理系统：增广律证明证明增广律：若X→Y， 则 XZ→YZ。(2)设 t[XZ]=s[XZ], 则有t[X]=s[X]和t[Z]=s[Z];由于 X→>Y, 对t[X]=s[]，就有t[Y]=s[Y],从而有t[YZ]=s[YZ],所以XZ→YZ成立。参见P191.增广律t[X] = s[X]t[XZ] = s[XZ]t[Y] = s[Y]X-Yt[Z] = s[Z]t[XZ] = s[XZ] XZ->YZt[YZ] = s[YZ]12
12 A公理系统：增广律证明 t[XZ] = s[XZ] t[X] = s[X] XY t[Y] = s[Y] t[XZ] = s[XZ] t[Z] = s[Z] t[YZ] = s[YZ] XZYZ 增广律 (2) 证明增广律: 若 X Y， 则 XZ YZ。 设 t[XZ]=s[XZ], 则有t[X]=s[X]和t[Z]=s[Z], 由于 XY, 对t[X]=s[X]，就有t[Y]=s[Y], 从而有t[YZ]=s[YZ], 所以 XZ YZ成立。参见P191
A公理系统：传递律证明证明传递律：若 X→Y及Y→Z，则X→Z。(3)设 t[X] = s[X], 由于X-→Y, 则有 t[Y] = s[Y],再由 Y→Z,， 对t[Y]= s[Y]，有 t[Z]=s[Z],所以X→Z成立。参见P190传递律X→Yt[Y] = s[Y]t[X] = s[X]t[Z] = s[Z]Y→ZX→zZ13
13 A公理系统：传递律证明 X Y t[X] = s[X] t[Y] = s[Y] Y Z t[Z] = s[Z] X Z 传递律 (3) 证明传递律: 若 X Y 及 YZ，则 X Z。 设 t[X] = s[X], 由于XY, 则有 t[Y] = s[Y], 再由 YZ， 对t[Y] = s[Y]，有 t[Z]=s[Z], 所以 X Z 成立。 参见P190
A公理系统：推论由Armstrong公理导出的推理规则参见P191.■合并律(union rule)若X→Y,X→Z, 则X→YZ。■分解律(decomposition rule)若X→YZ，,则X→Y,X→Z。■伪传递律(pseudotransitivity rule)若X→Y, WY→Z, 则WX→Z。■引理5.1X→AiA2...Ak成立 X→A;成立。(i=1, 2, ... ,k)，证明：用数学归纳法证明。“←”由合并律证明;“一”由分解律证明。14
14 A公理系统：推论 由Armstrong公理导出的推理规则参见P191. 合并律(union rule) 若 X Y，X Z，则 X YZ。 分解律(decomposition rule) 若 X YZ ，则 X Y，X Z。 伪传递律(pseudotransitivity rule) 若 X Y，WY Z，则 WX Z。 引理5.1 X A1 A2 Ak 成立 X Ai 成立。 (i=1, 2, ,k) 证明：用数学归纳法证明。 “ ”由合并律证明； “”由分解律证明
A公理系统：例示例：R<U, F >, U = {A, B, C, G, H, I}F = {A-→B, A-→C, CG-→H, CG→I, B→H}■F逻辑蕴涵以下函数依赖吗？A→H?是,：A→B, B-→HCG →HI?是,：CG→>H,CG→IAG→I?是,： A→C,AG→CG, CG→I15
15 A公理系统: 例 示例： R< U, F >, U = {A, B, C, G, H, I}, F = {AB, AC, CGH, CGI, BH}, F逻辑蕴涵以下函数依赖吗？ A H？ CG HI？ AG I？ 是, ∵AB，BH 是, ∵CGH，CGI 是, ∵ AC, AGCG，CGI