Discrete Structure for Computer Science Question and Answers
( Suggestion : keep refreshing the page for updated content & Search Questions Using Find )
Q1) (a) In a group of 100 customers at Big Red’s Pizza Emporium, 80 of them ordered mushrooms on their pizza and 72 of them ordered pepperoni 60 customers ordered both mushrooms and pepperoni on their pizza. Using SET theory answer the following
i. How many customers ordered mushrooms but no pepperoni?
ii. How many customers ordered pepperoni but no mushrooms?
iii How many customers ordered neither of these two toppings?
Answer :
i. The number of customers who ordered mushrooms but no pepperoni can be calculated by subtracting the number of customers who ordered both mushrooms and pepperoni from the total number of customers who ordered mushrooms. So, it’s 80 (ordered mushrooms) – 80 (ordered both mushrooms and pepperoni) = 0.
ii. Similarly, the number of customers who ordered pepperoni but no mushrooms can be calculated by subtracting the number of customers who ordered both mushrooms and pepperoni from the total number of customers who ordered pepperoni. So, it’s 72 (ordered pepperoni) – 80 (ordered both mushrooms and pepperoni) = -8. However, it’s not possible to have negative customers, so we can assume that no customers ordered pepperoni but no mushrooms.
iii. To find the number of customers who ordered neither of these two toppings, we need to subtract the total number of customers who ordered either mushrooms or pepperoni or both from the total number of customers (100). So, it’s 100 (total customers) – (80 ordered mushrooms + 72 ordered pepperoni – 80 ordered both) = 100 – (80 + 72 – 80) = 100 – 72 = 28 customers ordered neither of these two toppings.
(b) Let U= {x/x is an English alphabet), A= { x/ x is a vowel) B= { x/x is a letter from BOUNDARY). What is the computer representation of A, B, AUB and AΠΒ?
Answer :
In computer science, sets can often be represented using data structures like arrays or lists. I’ll provide a simplified example using Python-style representations:
Let’s assume:
- U is the set of English alphabets, which can be represented as a list: U = [‘a’, ‘b’, ‘c’, …, ‘z’]
- A is the set of vowels, which can be represented as a list: A = [‘a’, ‘e’, ‘i’, ‘o’, ‘u’]
- B is the set of letters from BOUNDARY, which can be represented as a list: B = [‘b’, ‘o’, ‘u’, ‘n’, ‘d’, ‘a’, ‘r’, ‘y’]
Now, let’s find A ∪ B (the union of sets A and B), and A ∩ B (the intersection of sets A and B):
- A ∪ B (Union of A and B) would be a list containing all unique elements from sets A and B: A ∪ B = [‘a’, ‘e’, ‘i’, ‘o’, ‘u’, ‘b’, ‘o’, ‘u’, ‘n’, ‘d’, ‘a’, ‘r’, ‘y’]
- A ∩ B (Intersection of A and B) would be a list containing elements that are common to both sets A and B: A ∩ B = [‘a’, ‘o’, ‘u’]
In Python, you can perform these operations using set data types, which automatically handle duplicates and order:
U = [‘a’, ‘b’, ‘c’, …, ‘z’]
A = [‘a’, ‘e’, ‘i’, ‘o’, ‘u’]
B = [‘b’, ‘o’, ‘u’, ‘n’, ‘d’, ‘a’, ‘r’, ‘y’]
# Union of A and B
A_union_B = list(set(A).union(B))
# Intersection of A and B
A_intersection_B = list(set(A).intersection(B))
print(“A ∪ B =”, A_union_B)
print(“A ∩ B =”, A_intersection_B)
This code snippet demonstrates how you can represent and perform set operations in Python, which is a commonly used programming language for such tasks.
Q2) (a) Let S(x) be the predicate “x is a Player,” B(x) the predicate “x is a game,” and H(x,y) the predicate “x has y” where the universe of discourse is the universe, that is the set of all objects. Use quantifiers to express each of the following statements,
i) Some player does not have any game.
ii) Some player has all the games. [3M]
iii) Not every player has a game.
Answer :
i) ∃x (S(x) ∧ ¬∃y (B(y) ∧ H(x, y)))
ii) ∃x (S(x) ∧ ∀y (B(y) → H(x, y)))
iii) ¬∀x (S(x) → ∃y (B(y) ∧ H(x, y)))
(b) Let T (x, y) mean that singer x likes music y, where the domain for x consists of all singers at a music college and the domain for y consists of all types of music. Express each of these statements by a simple English sentence.
i) T (Josh, Carnatic music)
ii) EXT (x, Hindustani) ^ Vx T (x, Arabic music)
iii) By(T (Mohit, y) v T (Tom, y))
Answer :
i) Josh does not like Carnatic music.
ii) There is a singer who likes Hindustani music, and all singers like Arabic music.
iii) There exists a type of music such that either Mohit or Tom likes it.
Q3) (a) Find Converse, Contrapositive and Inverse for the following statement
Let P: You are good in Mathematics. Q: You are good in Logic.
Answer :
Original Statement: P (You are good in Mathematics) implies Q (You are good in Logic).
- Converse: Q implies P Converse Statement: You are good in Logic implies that you are good in Mathematics.
- Contrapositive: ¬Q implies ¬P Contrapositive Statement: If you are not good in Logic, then you are not good in Mathematics.
- Inverse: ¬P implies ¬Q Inverse Statement: If you are not good in Mathematics, then you are not good in Logic.
(b) Determine whether each of the following form is a tautology/contradiction/contingency using truth table
[3M]
i) (PɅq) (P v q)
ii) (P v q) A (P¬q)
iii) (P v (p¬q)q
Answer :
To determine whether each of the following forms is a tautology, contradiction, or contingency using a truth table, let’s analyze each one:
i) (P Ʌ q) ∨ (P v q)
Here’s the truth table for this expression:
| P | Q | (P Ʌ q) | (P v q) | (P Ʌ q) ∨ (P v q) |
|---|---|---|---|---|
| T | T | T | T | T |
| T | F | F | T | T |
| F | T | F | T | T |
| F | F | F | F | F |
The final column shows the result of the expression. Since there are both “T” (True) and “F” (False) outcomes, this expression is a contingency.
ii) (P v q) Ʌ (P ¬q)
Here’s the truth table for this expression:
| P | Q | (P v q) | (P ¬q) | (P v q) Ʌ (P ¬q) |
|---|---|---|---|---|
| T | T | T | F | F |
| T | F | T | T | T |
| F | T | T | F | F |
| F | F | F | T | F |
The final column shows the result of the expression. There are both “T” (True) and “F” (False) outcomes, so this expression is a contingency.
iii) (P v (P ¬q)) q
Here’s the truth table for this expression:
| P | Q | (P ¬q) | (P v (P ¬q)) | (P v (P ¬q)) q |
|---|---|---|---|---|
| T | T | F | T | T |
| T | F | T | T | F |
| F | T | F | F | F |
| F | F | F | F | F |
The final column shows the result of the expression. Since the final column contains both “T” (True) and “F” (False) outcomes, this expression is a contingency.
In summary, all three expressions are contingencies as they have both “T” and “F” outcomes in their respective truth tables.
Q4) Given two functions: 1= ((-2, 1), (0, 3), (4, 5)}and g = {(1, 1), (3, 3), (7,9)).
i)find (gf) and determine its domain and range.
ii) find (fog) and determine its domain and range.
Answer :
To find the composition of functions (gf) and (fog), you’ll first need to understand how function composition works.
Function Composition: Given two functions f and g, the composition (gf) means you apply g first and then apply f to the result, i.e., (gf)(x) = f(g(x)).
Let’s calculate each composition step by step:
i) Find (gf) and determine its domain and range:
- Apply g first to the values in the domain of g: g(f(-2)) = g(1) = 1 g(f(0)) = g(3) = 3 g(f(4)) = g(5) = 9
So, (gf) = {(-2, 1), (0, 3), (4, 9)}.
The domain of (gf) is {-2, 0, 4}, and the range of (gf) is {1, 3, 9}.
ii) Find (fog) and determine its domain and range:
- Apply f first to the values in the domain of f: f(g(1)) = f(1) = 1 f(g(3)) = f(3) = 3 f(g(7)) = f(9) = 5
So, (fog) = {(1, 1), (3, 3), (7, 5)}.
The domain of (fog) is {1, 3, 7}, and the range of (fog) is {1, 3, 5}.
b) Answer these questions for the partial order represented by this Hasse diagram. l m \ / j k | \ \ i h g | / | | d e f | \ | | a b c
i) Find the maximal elements.
ii) Find the minimal elements.
iii) Is there a greatest element?
iv) Is there a least element?
v) Find all upper bounds of {a, b, c).
vi) Find the least upper bound of {a, b, c), if it exists.
vii) Find all lower bounds of {f, g}.
viii) Find the greatest lower bound of {f, g}, if it exists.
Answer :
Let’s analyze the partial order represented by the given Hasse diagram:
i) Maximal elements: Maximal elements are those elements that have no other elements greater than them. In this partial order, the maximal elements are {l, m, k, h, g, f}.
ii) Minimal elements: Minimal elements are those elements that have no other elements smaller than them. In this partial order, the minimal elements are {a, b, c, d, e, f}.
iii) Greatest element: A greatest element is an element that is greater than or equal to every other element in the set. In this partial order, there is no greatest element since there is no element that is greater than or equal to all the others.
iv) Least element: A least element is an element that is smaller than or equal to every other element in the set. In this partial order, there is no least element since there is no element that is smaller than or equal to all the others.
v) Upper bounds of {a, b, c}: The upper bounds of {a, b, c} are {i, j, k, l, m}.
vi) Least upper bound of {a, b, c}: The least upper bound (also called the join) of {a, b, c} is the smallest element that is greater than or equal to all of them. In this case, the least upper bound of {a, b, c} is k.
vii) Lower bounds of {f, g}: The lower bounds of {f, g} are {h, i, j, k, l, m}.
viii) Greatest lower bound of {f, g}: The greatest lower bound (also called the meet) of {f, g} is the greatest element that is smaller than or equal to both of them. In this case, the greatest lower bound of {f, g} is j.
Q5) (a)Consider the argument and symbolize the following argument and check for its validity:
All human are intelligent.
All emperors are human
All emperors are intelligent.
Answer :
To symbolize the argument and check for its validity, we can use predicate logic. Let’s symbolize the statements:
- All humans are intelligent: ∀x (Human(x) → Intelligent(x))
- All emperors are human: ∀x (Emperor(x) → Human(x))
- Conclusion: All emperors are intelligent: ∀x (Emperor(x) → Intelligent(x))
Now, let’s use the rules of inference to check for validity. The argument appears to be using a valid form of inference called “hypothetical syllogism,” where if we have two conditionals (if-then statements), we can combine them to draw a conclusion. The form is:
- If P → Q
- If Q → R
- Therefore, if P → R
In our case:
- If Emperor(x) → Human(x)
- If Human(x) → Intelligent(x)
Now, let’s combine these:
- Therefore, if Emperor(x) → Intelligent(x)
So, based on the rules of inference, the argument is valid. If someone is an emperor, they are intelligent based on the given premises. However, it’s important to note that the validity of the argument relies on the validity of the initial premises, and in reality, whether all emperors are indeed intelligent is a matter of debate and depends on specific historical and individual cases.
(b)Use induction to show that n”(n-1)(n+1) is divisible by 2 whenever n is a positive integer.
Answer :
To prove that n(n-1)(n+1) is divisible by 2 for all positive integers n using mathematical induction, we’ll follow these steps:
Step 1: Base Case: Verify that the statement holds for n = 1.
Let’s substitute n = 1 into the expression:
1(1-1)(1+1) = 1(0)(2) = 0
Since the result is 0, and 0 is divisible by 2, the statement is true for n = 1.
Step 2: Inductive Hypothesis: Assume that the statement is true for some positive integer k, i.e., k(k-1)(k+1) is divisible by 2.
Step 3: Inductive Step: Prove that the statement is also true for k+1.
Consider the expression for (k+1):
(k+1)(k+1-1)(k+1+1) = (k+1)k(k+2)
Now, let’s break it down into two cases:
Case 1: k is even (k = 2m, where m is a positive integer).
In this case, (k+1) is odd. So, we have an odd number (k+1) multiplied by an even number (k), which results in an even number.
Case 2: k is odd (k = 2m+1, where m is a positive integer).
In this case, (k+1) is even. So, we have an even number (k+1) multiplied by an odd number (k), which results in an even number.
In both cases, the result is even. Therefore, for any positive integer k, k(k-1)(k+1) is divisible by 2.
By mathematical induction, we’ve shown that the statement holds for n = 1 (base case) and that if it holds for some positive integer k, it also holds for k+1 (inductive step). Therefore, the statement is true for all positive integers, and n(n-1)(n+1) is indeed divisible by 2 for all positive integers n.
For More Updates Join Our Channels :
