how to solve (d), (e),(f),(g),(h) Here is a more or less typical set of axioms o
ID: 3823373 • Letter: H
Question
how to solve (d), (e),(f),(g),(h)
Here is a more or less typical set of axioms of a Boolean Algebra, a kind of structure we can investigate much like we have done with linear orders, number systems, etc. A Boolean algebra B = (B, +, ., -, 0, 1) is a non-empty set B together with (i) A binary operation on B, denoted ., called meet. (ii) A binary operation on B, denoted +, called join. (iii) A unary operation on B, denoted -, called complement and (iv) Two distinguished elements in B, denoted by constant symbols 0 and 1 These operations satisfy the following properties for any elements a, b, c elementof B: (a) a + (b+ c) = (a + b) + c and a middot (b middot c) = (a middot b) middot c (Associative Laws) (b) a +b = b + a and a middot b = b middot a (Commutative Laws) (c) a + (b middot c) = (a + b) middot (a + c) and a middot (b + c) = (a middot b) + (a middot c) (Distributive Laws) (d) a + a = a and a middot a = a (Idempotent Laws) (e) a + -a = 1 and a middot -a = 0 (Complement Laws) (f) a + (a middot b) = a and a middot (a + b) = a (Absorption Laws) (g) a + 1 = 1 and a middot 0 = 0 (Zero-One Laws) (h) -(a + b) = (-a middot -b) and -(a middot b) = (-a + -b) (DeMorgan's Laws) (i) -(-a) = a (Double Negation Law) This is not the smallest possible list of laws for Boolean algebras but should look familiar as these are exactly the laws of sentential logic we have been using all semester. a) Define the relation lessthanorequalto on the elements of a Boolean Algebra B as follows a lessthanorequalto b iff a middot b = a. Show this relation lessthanorequalto is a partial order on B. b) Show that 1 is a maximal element and 0 is a minimal element in this partial order on B. c) Let S be the set {1, 2, 3, 4, ..., 10}. Consider the power set of S, denoted P(S), that is the set of all subsets of S. How many elements are there in P(S). Show P(S) is a Boolean algebra under the operations set intersection, union, and complement. Draw a partial diagram of the Boolean Algebra of this collection of sets. Definition: A structure composed of sets closed under union, intersection, and complement is often called a field of sets. d) Improve the previous exercise and show the same result follows for any set S whatsoever. That is, P(S) is a B.A. What does the diagram of P(N) look like where N = {0, 1, 2, ...}? e) An clement a notequalto 0 in a B.A. is called an atom if there is no clement b such that 0Explanation / Answer
Answer
D. a + a = a and a.a = a (indemptent laws)
First Explain the laws
B.I. commutative law,
a + b = b + a
a.b = b.a
B II. Distributive law,
a.(b + c) =a.b + a.c
a+(b.c) = (a + b).(a + c)
B III. Existence of identity elements,
There exist elements, 0
a + 0 = a
a.1 =a
B IV. Existence of complements,
a + a’ = 1
a.a’ = 1
a.a’ = 0
Proof :-
a + a = a and a.a = a (indemptent laws)
a = a + 0 = a+ (a. a’) (B IV)
= (a + a). (a +a’) (B II)
= (a + a).1
= a +a
Also a = a.1
= a.(a +a’)
= a.(a + a.a’
= a.a + 0 = a.a
Answer f:-
A + (a.b) = a and a.(a + b) = a. (Absorption Law)
proof:-
a = a.1
= a.(1 + b)
= (a.1) + (a.b) (B II)
= a + a.b
Also
a. (a + b) a.a + a.b
= a + a.b
= a
Answer g
A + 1 = 1, a.0 = 0.
Proof :-
1 = a + a’
= a + (a’.1) = (a + 1).(a + a’)
= (a + 1).1 = a+ 1
Also
0 = a.a’ (B IV)
= a.(a’ + 0) (B III)
= a.a’ + a.0 (B II)
= 0 + A.0 (B IV)
= a.0
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.