1

How can I prove that the following two statements are equivalent, using Formula Equivalence laws?

f(x) and (g(x) and h(x)) 
(f(x) and g(x)) and (f(x) and h(x))

I know that by associativity, f(x) and (g(x) and h(x)) is equal to (f(x) and g(x)) and h(x). I am also thinking to use distributive laws to prove this, but they state that A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) or A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) (the law uses a union and intersection, rather than two intersections).

Any help to get me in the right direction would be greatly appreciated.

Git Gud
  • 31,356
Charles
  • 315
  • You have two intersections ("and's") and no unions which are expressed with "or". So the equivalence is actually straightforward – Jimmy R. Oct 18 '14 at 23:53
  • I am looking at a list of set identities, and I do not see anything that can help me prove this. What identify should I be looking to use? – Charles Oct 19 '14 at 00:01
  • You can use the fact that $f\wedge f = f$ (I don't know the name for this property) as well as the commutative property that $f\wedge g = g\wedge f$. – JMoravitz Oct 19 '14 at 00:11
  • @JMoravitz The fact $f\land f=f$ is called idempotent law. – Hanul Jeon Oct 19 '14 at 01:37
  • @JMoravitz Can you prove it using just commutativity and idempotence? – Doug Spoonwood Oct 19 '14 at 02:54

1 Answers1

1

For X(x), I just write X.

Axiom 1: ∧(X, Y)=∧(Y, X). (commutativity)

Axiom 2: ∧(X, ∧(Y, Z))=∧(∧(X, Y), Z). (associativity)

Axiom 3: ∧(X, X)=X. (idempotence).

A set with a binary operation "∧" with the above axioms as axioms or theorems forms an idempotent commutative semigroup. I'll drop parentheses in the following:

  1. ∧F∧GH=∧F∧GH (axiom of "x=x" for equality).

  2. ∧F∧GH=∧∧FF∧GH idempotence on 1.

  3. ∧F∧GH=∧F∧F∧GH associativity on 2.

  4. ∧F∧GH=∧F∧∧FGH associativity on 3.

  5. ∧F∧GH=∧F∧∧GFH commutativity on 4.

  6. ∧F∧GH=∧F∧G∧FH associativity on 5.

  7. ∧F∧GH=∧∧FG∧FH associativity on 6.

Therefore, ∧ distributes over itself. Since $\lor$ satisfies commutation and association and idempotence also, $\lor$ distributes over itself.

Doug Spoonwood
  • 11,211