# Re: ?? Functional Dependency Question ??

Date: Mon, 20 Oct 2008 01:05:03 -0700 (PDT)

Message-ID: <723c14d2-5adf-4cd8-9267-88bb72e10523_at_h2g2000hsg.googlegroups.com>

On Oct 20, 5:07 am, Keith H Duggar <dug..._at_alum.mit.edu> wrote:

> On Oct 18, 11:18 am, Bob Badour <bbad..._at_pei.sympatico.ca> 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 proofReceived on Mon Oct 20 2008 - 10:05:03 CEST