armstrong公理系统证明由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“armstrong公理系统”。
Armstrong公理系统的证明
① A1自反律：若Y X U，则X→Y为F所蕴含
证明1
设Y X U。
对R的任一关系r中的任意两个元组t,s：
若t[X]=s[X]，由于Y X，则有t[Y]=s[Y]，所以X→Y成立，自反律得证。
② A2增广律：若X→Y为F所蕴含，且Z U，则XZ→YZ为F所蕴含
证明2
设X→Y为F所蕴含，且Z U。
对R的任一关系r中的任意两个元组t,s：
若t[XZ]=s[XZ]，由于X XZ，Z XZ，根据自反律，则有t[X]=s[X]和t[Z]=s[Z]；
由于X→Y，于是t[Y]=s[Y]，所以t[YZ]=s[YZ]；所以XZ→YZ成立，增广律得证。
③ A3传递律：若X→Y，Y→Z为F所蕴含，则X→Z为F所蕴含
证明3
设X→Y及Y→Z为F所蕴含。
对R的任一关系r中的任意两个元组t,s：
若t[X]=s[X]，由于X→Y，有t[Y]=s[Y]；
再由于Y→Z，有t[Z]=s[Z]，所以X→Z为F所蕴含，传递律得证。
④ 合并规则：若X→Y，X→Z，则X→YZ为F所蕴含
证明4
因X→Y（已知）
故X→XY（增广律），XX→XY即X→XY
因X→Z（已知）
故XY→YZ（增广律）
因X→XY，XY→YZ（从上面得知）
故X→YZ（传递律）
⑤ 伪传递规则：若X→Y，WY→Z，则XW→Z为F所蕴含
证明5
因X→Y（已知）
故WX→WY（增广律）
因WY→Z（已知）
故XW→Z（传递律）
⑥ 分解规则：若X→Y，Z Y，则X→Z为F所蕴含
证明6
因Z Y（已知）
故Y→Z（自反律）
因X→Y（已知）
故X→Z（传递律）
