armstrong公理系统证明_armstrong公理系统

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（传递律）