Prove each of these statements. Use equation editor for mathematical symbols, formulas, predicates, equations, and so forth. You may use all the proof techniques we’ve used so far: direct proof, existential instantiation, generalizing from generic particular, counterexamples, contradiction, contraposition, etc., as well as basic algebra.

1. For all sets A, B, and C, if A ⊆ B, then A ∩ C ⊆ B ∩ C.
2. For all sets A, B, and C, if A ⊆ B and B ∩ C = ∅, then A ∩ C = ∅.
In the statements below, B is a boolean algebra with • and + for binary operations
and a is the complement of a.
3. For all a and b in B, (a • b ) + a = a.
4. For all x, y, and z in B, if x + y = x + z and x • y = x • z, then y = z.

Any help is appreciated!!

This post was edited by CamelFinger on May 3 2014 09:53pm

i think you missed something @ bolded. or is a really the complement of a?

for 2, suppose A intersect C is not empty set, so it has to have at least one member. let x be one of those members. we know x is in A and C. since A is a subset of B, x must be in B too. but then B intersect C would include x since it's part of C too. contradiction.

1) is similar.

This post was edited by carteblanche on May 3 2014 10:06pm

3 is directly the absorption law

look up a proof of it if you need otherwise just cite the law

keep in mind that in order to prove two sets equivalent, you need to show they are subsets of each other

ex: "suppose x is an element of set A.......that implies that (blah blah blah)"

although i think those can all be done without the law of excluded middle

This post was edited by Casey on May 4 2014 07:13pm

Boolean algebra:

3) Done conventionally

(a • b ) + a = a
(a • b ) + a • 1 = a
(a • b ) + a(b+b') = a
(a • b ) + ab + ab' = a
(a+b) • (a+b) • (a+b') = a
(a+b) • (a+b') = a
a+(bb') = a
a = a

4) Done a bit unconventionally, but works nontheless. Note: we don't even need (x + y = x + z), this is already implied by (x • y = x • z). You should smack your teacher for not knowing this..

x • y = x • z
x • y • 1 = x • z • 1
x • y • (z+z') = x • z • (y+y')
(x • y • z) + (x • y • z') = (x • z • y) + (x • z • y')

Substitute x • y with a
Substitute x • z with b
(NOTE: we assume a = b, as per the statement x • y = x • z)

(b • y) + (a • z') = (a • z) + (b • y')

Since (b • y) = (b • y') and (a • z) = (a • z') are contradictions,
(b • y) = (a • z) or (a • z') = (b • y')

Since we assume a = b, we can write the above expression as
(a • y) = (a • z) or (a • z') = (a • y')

Therefore,
y = z or y' = z' (both equivilent)

This post was edited by Foxic on May 5 2014 01:12am

By pm :

3. This is one of the 2 absorption laws of any boolean algebra.

Let's denote 1 the neutral element such that, for every a :
1 + a = a + 1 = 1
1 • a = a • 1 = a

(a • b ) + a = (a • b ) + (a • 1 )

Using the distributivity law :
(a • b ) + (a • 1 ) = a • ( b + 1 )

Using again the neutral element 1 :
a • ( b + 1 ) = a • 1 = a

4. Let's denote x' the complementary of x, and 0 the other neutral element ( 0 + a = a + 0 = a , 0 • a = a • 0 = 0 for every a) :

Since x + y = x + z, then :
x' • ( x + y ) = x' • ( x + z )
x' • x + x' • y = x' • x + x' • z
0 + x' • y = 0 + x' • z
x' • y = x' • z

And now, just add together the 2 equalities :
x • y = x • z
and
x' • y = x' • z

( x • y ) + ( x' • y ) = ( x • z ) + ( x' • z )
( x + x' ) • y = ( x + x' ) • z
1 • y = 1 • z
y = z



If (a • y) = (a • z) implies y = z, why can't we say, from the start : x • y = x • z implies y = z ??

Yeah.. I kind of derped there, was pretty late when I posted