1. Find the Cartesian product A × A if A = {0, 1, 3}. 2. Construct the truth table of the compound proposition (p ∨ ¬q) → (p ∧ q). 3. Define contrapositive of a conditional stateme... 1. Find the Cartesian product A × A if A = {0, 1, 3}. 2. Construct the truth table of the compound proposition (p ∨ ¬q) → (p ∧ q). 3. Define contrapositive of a conditional statement and find the same for the following statement: 'If you do your homework, you will not be punished.' 4. What is the power set of the empty set? What is the power set of the set {φ}? Here φ is an empty set. 5. State pigeonhole principle. 6. Find the greatest common divisor of 414 and 662 using the Euclidean algorithm. 7. Draw a complete graph with 5 vertices. 8. Does there exist a simple graph with six vertices of degrees 1,1,3,4,6,7? Justify. 9. Define a permutation group. 10. For any a,b in a Boolean algebra prove that (a+b)' = a' + b'. 11. Show that ¬(p ∨ (¬p ∧ q)) and ¬p ∧ ¬q are logically equivalent by developing a series of logical equivalences. 12. In a survey it was found that 21 people liked product A, 26 liked product B, and 29 liked product C. If 14 people liked products A and B, 12 liked products C and A, 14 people liked products B and C, and 8 liked all three products. Find how many liked product C only? 13. Let A be the set of integers and R be the relation defined on A × A by (a,b)R (c,d) if ad = bc. Prove that R is an equivalence relation. 14. Explain the following with suitable examples: a) Connected graph, b) Planar graph, c) Vertex colouring of a graph, d) Rooted tree. 15. Show that the set G = {1, 2, 3, 4, 5, 6} is a finite abelian group of order 6 with respect to multiplication modulo 7. 16. a) Prove that √2 is irrational by giving a proof by contradiction. b) Find the number of arrangements of the letters of the word INDEPENDENCE. In how many of these arrangements: i) All the vowels always occur together. ii) Vowels never occur together. 17. a) Prove that a finite integral domain is a field. b) Using Boolean algebra, show that abc + ab'c + abc' + a'b + bc = ab + bca.

Question image

Understand the Problem

The question comprises a series of mathematical problems covering various topics such as set theory, graph theory, logic, algebra, and basic number theory. Each question asks for specific operations, proofs, or explanations related to these topics.

Answer

1. \( A \times A = \{(0,0),(0,1),(0,3),(1,0),(1,1),(1,3),(3,0),(3,1),(3,3)\} \)
Answer for screen readers
  1. ( A \times A = {(0,0),(0,1),(0,3),(1,0),(1,1),(1,3),(3,0),(3,1),(3,3)} )

  2. Truth table constructed for ( (p \lor \neg q) \to (p \land q) ).

  3. Contrapositive: "If you are punished, then you did not do your homework."

  4. ( P(\emptyset) = { \emptyset } )

  5. If ( n > m ) then at least one container has more than one.

  6. GCD of ( 414 ) and ( 662 ) found using steps in the Euclidean algorithm.

  7. Draw ( K_5 ) with vertices connected.

  8. No simple graph exists with given degrees.

  9. A permutation group: set of permutations closed under operation and inverse.

  10. Proved ( (a + b)' = a' + b' ).

Steps to Solve

  1. Finding the Cartesian Product
    Given the set ( A = {0, 1, 3} ), the Cartesian product ( A \times A ) consists of all ordered pairs where the first and second elements are from set ( A ).
    This can be defined as:
    $$ A \times A = {(a, b) | a \in A, b \in A} $$

  2. Construction of the Truth Table
    For the expression ( (p \lor \neg q) \to (p \land q) ), create a truth table.
    List all possible truth values for ( p ) and ( q ), calculate ( \neg q ), then evaluate ( (p \lor \neg q) ) and ( (p \land q) ), and finally the implication:
    | p | q | ¬q | p ∨ ¬q | p ∧ q | (p ∨ ¬q) → (p ∧ q) | |---|---|----|--------|--------|--------------------| | T | T | F | T | T | T | | T | F | T | T | F | F | | F | T | F | F | F | T | | F | F | T | T | F | F |

  3. Defining the Contrapositive
    The contrapositive of a statement ( p \to q ) is ( \neg q \to \neg p ).
    For the given statement: "If you do your homework, you will not be punished."
    Define:

  • ( p ): You do your homework.
  • ( q ): You will not be punished.
    So, contrapositive is: "If you are punished, then you did not do your homework."
  1. Power Set of the Empty Set
    The power set ( P(X) ) of a set ( X ) is the set of all subsets of ( X ).
    For the empty set ( \emptyset ), the power set ( P(\emptyset) = { \emptyset } ).

  2. State the Pigeonhole Principle
    The pigeonhole principle states that if ( n ) items are put into ( m ) containers and if ( n > m ), then at least one container must contain more than one item.

  3. Finding GCD Using Euclidean Algorithm
    To find the GCD of ( 414 ) and ( 662 ):

  • Use the Euclidean algorithm:
    $$ \text{GCD}(a, b) = \text{GCD}(b, a \mod b) $$
    Continue until ( b = 0 ).
  1. Drawing a Complete Graph
    A complete graph with ( n ) vertices, denoted as ( K_n ), has edges between every pair of vertices.
    For ( K_5 ), draw ( 5 ) vertices with edges connecting every pair.

  2. Existence of Simple Graph
    A simple graph with vertex degrees ( 1, 1, 3, 4, 6, 7 ) does not exist since the sum of degrees must be even. Apply the handshake theorem:
    $$ \sum \text{degrees} = 2 \cdot \text{edges} $$

  3. Define a Permutation Group
    A permutation group is a set of permutations of a given set, closed under composition and inverses. The symmetric group ( S_n ) is an example.

  4. Boolean Algebra Proof
    Using Boolean algebra, prove that ( (a + b)' = a' + b' ) by applying De Morgan's laws:
    $$ (a + b)' = a' \cdot b' $$

  1. ( A \times A = {(0,0),(0,1),(0,3),(1,0),(1,1),(1,3),(3,0),(3,1),(3,3)} )

  2. Truth table constructed for ( (p \lor \neg q) \to (p \land q) ).

  3. Contrapositive: "If you are punished, then you did not do your homework."

  4. ( P(\emptyset) = { \emptyset } )

  5. If ( n > m ) then at least one container has more than one.

  6. GCD of ( 414 ) and ( 662 ) found using steps in the Euclidean algorithm.

  7. Draw ( K_5 ) with vertices connected.

  8. No simple graph exists with given degrees.

  9. A permutation group: set of permutations closed under operation and inverse.

  10. Proved ( (a + b)' = a' + b' ).

More Information

The Cartesian product allows for pairing elements from two sets, while power sets involve all possible subsets. Boolean algebra is fundamental in logic and set theory.

Tips

  • Neglecting Order of Operations in Truth Tables: Always evaluate inner expressions first.
  • Forgetting Closure in Groups: Remember that operations in a group must return elements in the same set.
  • Misunderstanding Degrees in Graphs: Ensure that the sum of the vertex degrees is even.

AI-generated content may contain errors. Please verify critical information

Thank you for voting!
Use Quizgecko on...
Browser
Browser