# Re: ?? Functional Dependency Question ??

From: David BL <davidbl_at_iinet.net.au>
Date: Mon, 20 Oct 2008 01:05:03 -0700 (PDT)

On Oct 20, 5:07 am, Keith H Duggar <dug..._at_alum.mit.edu> wrote:
>
>
>
>
>
> > tlbaxte..._at_yahoo.com wrote:
>
> > > "Although X->A and X->B implies X->AB by the union rule stated above,
> > > X->A, and Y->B does *not* imply that XY->AB."
>
> > > I'm not seeing this. It seems to me that X->A, and Y->B *DOES* imply
> > > that XY->AB.
>
> > > I'm sure I'm wrong but I'm not seeing it. Can someone explain?
>
> > > Thanks
>
> > I'm not seeing it either. By these truth tables, it seems to:
>
> > XY AB X->A Y->B (X->A)(Y->B) XY->AB (X->A)(Y->B)->(XY->AB)
> > 00 00 1 1 1 1 1
> > 00 01 1 1 1 1 1
> > 00 11 1 1 1 1 1
> > 00 10 1 1 1 1 1
> > 01 10 1 0 0 1 1
> > 01 11 1 1 1 1 1
> > 01 01 1 1 1 1 1
> > 01 00 1 0 0 1 1
> > 11 00 0 0 0 0 1
> > 11 01 0 1 0 0 1
> > 11 11 1 1 1 1 1
> > 11 10 1 0 0 0 1
> > 10 10 1 1 1 1 1
> > 10 11 1 1 1 1 1
> > 10 01 0 1 0 1 1
> > 10 00 0 1 0 1 1
>
> > (View with a fixed width font)
>
> > Can anyone find a mistake in the above truth tables? Is there a
> > difference between functional dependency and implication that I need to
> > learn?
>
> Your truth table is correct. You can also prove this with
> Boolean algebra (below ~ = not, + = or, * = and):
>
> given :
>
> (1) 1 = ~X + A : X implies A
> (2) 1 = ~Y + B : Y implies B
>
> prove :
>
> (3) 1 = ~(XY) + AB : XY implies AB
>
> proof :
>
> (4) 1 = (~X + A)(~Y + B) : conjuction of (1) and (2)
> (5) 1 = ~X~Y + ~XB + ~YA + AB : distributive and commutative
> (6) 1 = ~X~Y + ~X~Y + ~XB + ~YA + AB : idempotent
> (7) 1 = ~X(~Y + B) + ~Y(~X + A) + AB : distributive and commutative
> (8) 1 = ~X + ~Y + AB : substitute (1) and (2)
> (9) 1 = ~(XY) + AB : De Morgan
>
> QED
It's interesting how people come up with such different ways to prove things. I personally tend to use a conditional proof where possible:

RTP: (X->A)(Y->B) -> XY->AB

```    (X->A)(Y->B)               : premise
X->A, Y->B                 : conjunction elimination
XY                         : premise
X,Y                        : conjunction elimination
A                          : modus ponens on X,X->A
B                          : modus ponens on Y,Y->B
AB                         : conjunction introduction
XY->AB                     : conditional proof
(X->A)(Y->B) -> XY->AB     : conditional proof
```
Received on Mon Oct 20 2008 - 10:05:03 CEST

Original text of this message