GATE Overflow Book

This book was created programmatically by GATE Overflow on Jun 24, 2017. If you feel any doubt regarding the answer, click on the question link and give a comment on the site. Studying all these questions might get you 60 marks in GATE but that might not be enough for an IIT. So, read standard books, solve exercise questions and use these questions for cementing the concepts and aim 85+. At least if you are not getting the solution to a given problem first refer standard book. If any error is found on any question it shall be updated at http://gateoverflow.in/corrections.
An updated Aptitude Overflow book, a book for Previous Year Questions including ISRO, UGCNET and a book for Non-previous Year Questions are expected in 1-2 months. You can enroll in this course to get notification for the same. Enrollment is free and account details are of GATE Overflow with a new password which will be sent to your registered email on GATE Overflow.

You can now join our Facebook group for GATE CSE discussions.

This book consists of only previous year GATE and TIFR questions (CS from 1991 and all 5 years of IT) both of which are relevant for GATE. Out of syllabus subjects are removed from this book but some out of syllabus topic questions might still be present. This book is mostly stable and is expected to be updated only yearly when new papers come to site. But for GATE2017 a special update shall be made within 2 months which includes all GO Test series questions and previous GATE questions preceding 1991. Also GATECSE book is coming this month describing the topics to be covered and from where and also includes discussions about confusing topics.

Since GATE Overflow started in August 2014, a lot of people have dedicated their time and effort in bringing this book now. Initiated by Omesh Pandita and Arjun Suresh as a Q/A platform for CSE students, Kathleen was instrumental in getting all previous year GATE questions here. Then experts like Praven Saini, Happy Mittal, Sankaranarayanan, Suraj etc. have contributed a lot to the answers here. Pragy Agarwal even after topping GATE has continuously contributed here with his knowledge as well as in making the contents beautiful with fine latex skills. We also have to thank the work by Jothee, Misbah, Ishrat and Nataliyah who are continuously adding and keeping the contents here neat and clean. There are also many toppers of GATE 2015, 2016, 2017 and probably 2018 who are contributing a lot here. The list of all the contributors can be found here but even that does not include the contributions of some like Arif Ali in helping design this book, Arvind Devaraj and others who have provided guidance and help etc. Last but not the least, we thank all the users of GATE Overflow. We also thank the contributions of Silpa, Rahul Kumar Yadav and others for getting the GATECSE Lastrankpage maintained.

Table of Contents
  1. Discrete Mathematics: Combinatory
    (49)
    1. (1)
    2. (2)
    3. (35)
    4. (3)
    5. (1)
    6. (2)
    7. (2)
    8. (1)
    9. (2)
  2. Discrete Mathematics: Graph Theory
    (61)
    1. (0)
    2. (1)
    3. (2)
    4. (4)
    5. (4)
    6. (1)
    7. (11)
    8. (1)
    9. (7)
    10. (14)
    11. (2)
    12. (1)
    13. (1)
    14. (1)
    15. (2)
    16. (1)
    17. (1)
    18. (1)
    19. (2)
    20. (3)
    21. (1)
  3. Discrete Mathematics: Mathematical Logic
    (79)
    1. (2)
    2. (1)
    3. (1)
    4. (26)
    5. (9)
    6. (13)
    7. (27)
  4. Discrete Mathematics: Set Theory & Algebra
    (170)
    1. (2)
    2. (5)
    3. (1)
    4. (2)
    5. (3)
    6. (3)
    7. (1)
    8. (28)
    9. (3)
    10. (21)
    11. (1)
    12. (9)
    13. (1)
    14. (1)
    15. (2)
    16. (2)
    17. (11)
    18. (1)
    19. (1)
    20. (5)
    21. (1)
    22. (3)
    23. (1)
    24. (27)
    25. (1)
    26. (1)
    27. (30)
    28. (2)
    29. (1)
  5. Engineering Mathematics: Calculus
    (49)
    1. (3)
    2. (4)
    3. (1)
    4. (7)
    5. (10)
    6. (11)
    7. (11)
    8. (1)
    9. (1)
  6. Engineering Mathematics: Linear Algebra
    (68)
    1. (2)
    2. (2)
    3. (4)
    4. (22)
    5. (21)
    6. (1)
    7. (11)
    8. (5)
  7. Engineering Mathematics: Probability
    (99)
    1. (0)
    2. (4)
    3. (5)
    4. (1)
    5. (6)
    6. (1)
    7. (9)
    8. (1)
    9. (1)
    10. (1)
    11. (4)
    12. (54)
    13. (10)
    14. (2)
  8. General Aptitude: Numerical Ability
    (184)
    1. (42)
    2. (1)
    3. (1)
    4. (2)
    5. (3)
    6. (3)
    7. (1)
    8. (3)
    9. (8)
    10. (1)
    11. (1)
    12. (2)
    13. (2)
    14. (15)
    15. (3)
    16. (3)
    17. (3)
    18. (6)
    19. (1)
    20. (13)
    21. (1)
    22. (1)
    23. (1)
    24. (2)
    25. (7)
    26. (2)
    27. (10)
    28. (1)
    29. (4)
    30. (1)
    31. (12)
    32. (1)
    33. (5)
    34. (4)
    35. (2)
    36. (1)
    37. (7)
    38. (1)
    39. (1)
    40. (1)
    41. (1)
    42. (2)
    43. (1)
    44. (1)
  9. General Aptitude: Verbal Ability
    (167)
    1. (46)
    2. (3)
    3. (11)
    4. (2)
    5. (2)
    6. (12)
    7. (16)
    8. (1)
    9. (26)
    10. (3)
    11. (2)
    12. (15)
    13. (1)
    14. (1)
    15. (1)
    16. (1)
    17. (3)
    18. (18)
    19. (3)

Answers:

Selected Answer

Every new set Sn+1 starts after n elements from the starting element of S. This means that we can find the starting number of S21 using Arithmetic progression formula. 

Let Sum(n) denote sum of natural numbers uptil n:

S1 starts with = 1

S2 starts with  = Sum(1) + 1= 2

S3 starts with = Sum(2) + 1 = (1+2) + 1 = 4

Similarly S21 starts with S(20) +1 =  $\frac{20(20+1)}{2}$ + 1 = 211

Now we need to find sum of 21 consecutive natural numbers starting from 211

Using A.P. sum formula Sn = $\frac{n}{2}$ [2a + (n-1)*d ] where a= starting term , d= difference

Sum of elements in S21 =  $\frac{21}{2}$ [2(211) + 20 ] = $\frac{21 * 442}{2}$ = 4641... Option D is correct

2 votes -- Heisenberg ( 1.6k points)

How many distinct binary search trees can be created out of 4 distinct keys?

  1. 5
  2. 14
  3. 24
  4. 42

We are given a set of $n$ distinct elements and an unlabeled binary tree with $n$ nodes. In how many ways can we populate the tree with the given set so that it becomes a binary search tree?

  1. $0$
  2. $1$
  3. $n!$
  4. $\frac{1} {n+1} .^{2n}C_n$

Answers: Binary Tree

Selected Answer

answer - B

number of distinct BSTs = 2nCn/(n + 1)
 

9 votes -- ankitrokdeonsns ( 9.1k points)
Selected Answer
Given binary tree is unlabeled . So as it is given we are not allowed to change the formation of tree. Then To make it BST we can use atmost 1 way . As for particular structure we can not use n! arrangement of nodes (Becasue they are labeled and it is BST not BT)
17 votes -- Palash Nandi ( 1.6k points)

With n nodes there are 2nCn/(n+1) distinct tree structures possible.

Corresponding to each structure only  1 binary search tree can be formed because inorder is fixed.

Here we are already given one such structure therefore only 1 tree possible.

If  Binary trees would be asked n! possible corresponding to each distinct tree structure.

9 votes -- Anurag Semwal ( 7.5k points)

Match the pairs in the following questions by writing the corresponding letters only.

(A). The number distinct binary trees with $n$ nodes. (P). $\frac{n!}{2}$
(B). The number of binary strings of length of $2n$ with an equal number of $0’s$ and $1’s$. (Q). $ \binom{3n}{n}$
(C). The number of even permutation of $n$ objects. (R). $\binom{2n}{n}$
(D). The number of binary strings of length $6n$ which are palindromes with $2n$  $0’s$. (S). $\frac{1}{1+n}\binom{2n}{n}$

It is required to divide the $2n$ members of a club into $n$ disjoint teams of 2 members each. The teams are not labelled. The number of ways in which this can be done is:

  1. $\frac{\left ( 2n \right )!}{2^{n}}$
  2. $\frac{\left ( 2n \right )!}{n!}$
  3. $\frac{\left ( 2n \right )!}{2^n . n!}$
  4. $n! / 2$
  5. None of the above.

In how many different ways can $r$ elements be picked from a set of $n$ elements if

(i) Repetition is not allowed and the order of picking matters?

(ii) Repetition is allowed and the order of picking does not matter?

  1. $\frac{n!}{\left(n - r\right)!}$ and $\frac{\left(n + r - 1\right)!}{r!\left(n - 1\right)!}$, respectively.
  2. $\frac{n!}{\left(n - r\right)!}$ and $\frac{n!}{r!\left(n - 1\right)!}$, respectively.
  3. $\frac{n!}{r!\left(n - r\right)!}$ and $\frac{\left(n - r + 1\right)!}{r!\left(n - 1\right)!}$, respectively.
  4. $\frac{n!}{r!\left(n - r\right)!}$ and $\frac{n!}{\left(n - r\right)!}$, respectively.
  5. $\frac{n!}{r!}$ and $\frac{r!}{n!}$, respectively.

There are $n$ kingdoms and $2n$ champions. Each kingdom gets $2$ champions. The number of ways in which this can be done is:

  1. $\frac{\left ( 2n \right )!}{2^{n}}$
  2. $\frac{\left ( 2n \right )!}{n!}$
  3. $\frac{\left ( 2n \right )!}{2^{n} . n!}$
  4. $n!/2$
  5. None of the above.

A $1 \times 1$ chessboard has one $(1)$ square, a $2 \times 2$ chessboard has $(5)$ squares. Continuing along this fashion, what is the number of squares on the (regular) $8 \times 8$ chessboard?

  1. $64$
  2. $65$
  3. $204$
  4. $144$
  5. $256$

There is a set of $2n$ people: $n$ male and $n$ female. A good party is one with equal number of males and females (including the one where none are invited). The total number of good parties is.

  1. $2^{n}$
  2. $n^{2}$
  3. $\left(\frac{n}{n/2}\right)^{2}$
  4. $\left(\frac{2n}{n}\right)$
  5. None of the above.

Suppose that a robot is placed on the Cartesian plane. At each step it is allowed to move either one unit up or one unit right, i.e., if it is at $(i,j)$ then it can move to either $(i + 1, j)$ or $(i,j + 1)$.

Suppose that the robot is not allowed to traverse the line segment from (4,4) to (5,4). With this constraint, how many distinct paths are there for the robot to reach (10,10) starting from (0,0)?

  1. $2^9$
  2. $2^{19}$
  3. $^{8}\mathrm{C}_{4} \times^{11}\mathrm{C}_{5}$
  4. $^{20}\mathrm{C}_{10} - ^{8}\mathrm{C}_{4}\times ^{11}\mathrm{C}_{5}$

We need to choose a team of 11 from a pool of 15 players and also select a captain. The number of different ways this can be done is

  1. $ \begin{pmatrix} 15 \\ 11 \end{pmatrix}$
  2. 11 . $ \begin{pmatrix} 15 \\ 11 \end{pmatrix}$
  3. 15 . 14 . 13 . 12 . 11 .10 . 9 . 8 . 7 . 6 . 5
  4. (15 . 14 . 13 . 12 . 11 .10 . 9 . 8 . 7 . 6 . 5) . 11

In how many ways can we distribute 5 distinct balls, B1, B2, ..., B5 in 5 distinct cells, C1, C2, ...., C5 such that Ball Bi is not in cell Ci, ∀i = 1, 2, ..., 5 and each cell contains exactly one ball?

  1. 44
  2. 96
  3. 120
  4. 3125

For the inter-hostel six-a-side football tournament, a team of 6 players is to be chosen from 11 players consisting of 5 forwards, 4 defenders and 2 goalkeepers. The team must include at least 2 forwards, at least 2 defenders and at least 1 goalkeeper. Find the number of different ways in which the team can be chosen.

  1. 260
  2. 340
  3. 720
  4. 1440

 

Provide short answers to the following questions:

How many substrings (of all lengths inclusive) can be formed from a character string of length $n$? Assume all characters to be distinct, prove your answer.

How many distinct ways are there to split 50 identical coins among three people so that each person gets at least 5 coins?

  1. $3^{35}$
  2. $3^{50}-2^{50}$
  3. $\begin{pmatrix} 35 \\ 2 \end{pmatrix}$
  4. $\begin{pmatrix} 50 \\ 15 \end{pmatrix}. 3^{35}$
  5. $\begin{pmatrix} 37 \\ 2 \end{pmatrix}$

How many disctict words can be formed by permuting the letters of the word ABRACADABRA?

  1. $\frac{11!}{5! \: 2! \: 2!}$
  2. $\frac{11!}{5! \: 4! }$
  3. $11! \: 5! \: 2! \: 2!\:$
  4. $11! \: 5! \: 4!$
  5. $11! $

In a tournament with 7 teams, each team plays one match with every other team. For each match, the team earns two points if it wins, one point if it ties, and no points if it loses. At the end of all matches, the teams are ordered in the descending order of their total points (the order among the teams with the same total are determined by a whimsical tournament referee). The first three teams in this ordering are then chosen to play in the next round. What is the minimum total number of points a team must earn in order to be guaranteed a place in the next round?

  1. 13
  2. 12
  3. 11
  4. 10
  5. 9
Q.3 A subset S of set of numbers {2,3,4,5,6,7,8,9,10} is said to be good if has exactly 4 elements and their gcd=1, Then number of good subset is

A) 126  B) 125  C)123  D)121
Q 4) In how many ways can three person, each throwing a single die once, make a score of 11

A) 22   B)27  C)24   D)38

A line L in a circuit is said to have a stuck-at-0 fault if the line permanently has a logic value 0. Similarly a line L in a circuit is said to have a stuck-at-1 fault if the line permanently has a logic value 1. A circuit is said to have a multiple stuck-at fault if one or more lines have stuck at faults. The total number of distinct multiple stuck-at faults possible in a circuit with N lines is 

  1. 3N
  2. 3N - 1
  3. 2N - 1
  4. 2

Let $P =\sum_{\substack{1≤i≤2k \\ i\;odd}} i$ and $Q = \sum_{\substack{1≤i≤2k \\ i\;even}} i$, where $k$ is a positive integer. Then

  1. $P = Q - k$
  2. $P = Q + k$
  3. $P = Q$
  4. $P = Q + 2k$

Let A be a sequence of 8 distinct integers sorted in ascending order. How many distinct pairs of sequences, B and C are there such that

  1. each is sorted in ascending order,
  2. B has 5 and C has 3 elements, and
  3. the result of merging B and C gives A
    1. 2
    2. 30
    3. 56
    4. 256
  1. In how many ways can a given positive integer $n \geq 2$ be expressed as the sum of 2 positive integers (which are not necessarily distinct). For example, for $n=3$ the number of ways is 2, i.e., 1+2, 2+1. Give only the answer without any explanation.
  2. In how many ways can a given positive integer $n \geq 3$ be expressed as the sum of 3 positive integers (which are not necessarily distinct). For example, for $n=4$, the number of ways is 3, i.e., 1+2+1, 2+1+1. Give only the answer without explanation.
  3. In how many ways can a given positive integer $n \geq k$ be expressed as the sum of k positive integers (which are not necessarily distinct). Give only the answer without explanation.

$n$ couples are invited to a party with the condition that every husband should be accompanied by his wife. However, a wife need not be accompanied by her husband. The number of different gatherings possible at the party is

  1. \(^{2n}\mathrm{C}_n\times 2^n\)
  2. \(3^n\)
  3. \(\frac{(2n)!}{2^n}\)
  4. \(^{2n}\mathrm{C}_n\)

$m$ identical balls are to be placed in $n$ distinct bags. You are given that $m \geq kn$, where $k$ is a natural number $\geq 1$. In how many ways can the balls be placed in the bags if each bag must contain at least $k$ balls?

  1. \(\left( \begin{array}{c} m - k \\ n - 1 \end{array} \right)\)
  2. \(\left( \begin{array}{c} m - kn + n - 1 \\ n - 1 \end{array} \right)\)
  3. \(\left( \begin{array}{c} m - 1 \\ n - k \end{array} \right)\)
  4. \(\left( \begin{array}{c} m - kn + n + k - 2 \\ n - k \end{array} \right)\)

Mala has the colouring book in which each English letter is drawn two times. She wants to paint each of these 52 prints with one of k colours, such that the colour pairs used to colour any two letters are different. Both prints of a letter can also be coloured with the same colour. What is the minimum value of k that satisfies this requirement?

  1. 9
  2. 8
  3. 7
  4. 6

Suppose that a robot is placed on the Cartesian plane. At each step it is allowed to move either one unit up or one unit right, i.e., if it is at $(i,j)$ then it can move to either $(i + 1, j)$ or $(i,j + 1)$.

How many distinct paths are there for the robot to reach the point (10,10) starting from the initial position (0,0)?

  1. $^{20}\mathrm{C}_{10}$
  2. $2^{20}$
  3. $2^{10}$
  4. None of the above.

In how many ways can b blue balls and r red balls be distributed in n distinct boxes?

  1. $\frac{(n+b-1)!\,(n+r-1)!}{(n-1)!\,b!\,(n-1)!\,r!}$
  2. $\frac{(n+(b+r)-1)!}{(n-1)!\,(n-1)!\,(b+r)!}$
  3. $\frac{n!}{b!\,r!}$
  4. $\frac{(n + (b + r) - 1)!} {n!\,(b + r - 1)}$

The number of binary strings of $n$ zeros and $k$ ones in which no two ones are adjacent is

  1. $^{n-1}C_k$

  2. $^nC_k$

  3. $^nC_{k+1}$

  4. None of the above

 

Two girls have picked 10 roses, 15 sunflowers and 15 daffodils. What is the number of ways they can divide the flowers among themselves?

  1. 1638
  2. 2100
  3. 2640
  4. None of the above

 

How many sub strings of different lengths (non-zero) can be found formed from a character string of length $n$?

  1. $n$
  2. $n^2$
  3. $2^n$
  4. $\frac{n(n+1)}{2}$

 

How many 4-digit even numbers have all 4 digits distinct

  1. 2240
  2. 2296
  3. 2620
  4. 4536
A pennant is a sequence of numbers, each number being 1 or 2. An $n$-pennant is a sequence of numbers with sum equal to $n$. For example, $(1,1,2)$ is a 4-pennant. The set of all possible 1-pennants is ${(1)}$, the set of all possible 2-pennants is ${(2), (1,1)}$ and the set of all 3-pennants is ${(2,1), (1,1,1), (1,2)}$. Note that the pennant $(1,2)$ is not the same as the pennant $(2,1)$. The number of 10-pennants is________

The number of substrings (of all lengths inclusive) that can be formed from a character string of length $n$ is

  1. $n$
  2. $n^2$
  3. $\frac{n(n-1)}{2}$
  4. $\frac{n(n+1)}{2}$

 

Find the number of binary strings $w$ of length $2n$ with an equal number of $1's$ and $0's$ and the property that every prefix of $w$ has at least as many $0's$ as $1's.$

The exponent of 11 in the prime factorization of 300! is

  1. 27
  2. 28
  3. 29
  4. 30

Answers: Combinatory

Selected Answer

(A) - S Catalyn no  http://gatecse.in/wiki/Number_of_Binary_trees_possible_with_n_nodes

(B) - R. Choosing n locations out of 2n to place 0. Remaining automatically become 1.

(C) -P An even permutation is a permutation obtainable from an even number of two-element swaps, For a set of n elements and n>2, there are n!/2 even permutations. Ref -> http://mathworld.wolfram.com/EvenPermutation.html

(D) -> Q 

Length = 6n, as it is palindrome, we need to only consider half part.

Total Length to consider 3n (Remaining 3n will be revese of this 3n)

now Choosing n 0's out of 3n. So Q is correct for D.

10 votes -- Akash ( 41.5k points)
Selected Answer
2n member to be n teams with 2 member each and teams are unordered so we can exchange n team member among them.
 
=$\frac{(2n)!}{\underbrace{2!.2!.2! \dots 2!}_{n \text{ times }} \times n!}$
=$\frac{(2n)!}{2^n \times n!}$

Option c.
5 votes -- Umang Raman ( 14.4k points)
Selected Answer

(i) Repetition is not allowed and the order of picking matters =
      = r arrangement with no repetition = npr = $\frac{n!}{(n-r)!}$

(ii) Repetition is allowed and the order of picking does not matter = 
      = combination with unlimited repetition = n-1+rCr = $\frac{n-1+r!}{(n-1)!r!}$
Option A

6 votes -- Umang Raman ( 14.4k points)
Selected Answer

Option A is correct.

We have n Kingdoms as k1 , k2 , ... , kn.

Firstly we can select 2 champions from 2n champions and assign to k1 = $\binom{2n}{2}$ ways(Say w1)

Then we can select next 2 champions and assign to k2 = $\binom{2n-2}{2}$ ways(Say w2)

and so on..

For last kingdom , we have 2 champions left = $\binom{2}{2}$ ways  (say wn)

Total ways for assigning 2n champions to n kingdoms = w1 * w2 * .... * wn

                                  = $\binom{2n}{2} * \binom{2n - 2}{2} * . . . * \binom{2}{2}$ 

                                  = (2n)! / 2n  So, Option A  (Ans) . 

9 votes -- Himanshu Agarwal ( 15.9k points)
Selected Answer
no of squares on chessboard of n*n is equal to sum of squares of n terms

for 8*8 chessboard

=n(n+1)(2n+1)/6

=8*9*17/6

=204
5 votes -- Pooja Palod ( 31.2k points)
1*1 square possible...........8*8=64

2*2            " ".....................7*7 =49

3*3           " ".......................6*6 =36

4*4            " ".......................5*5=25

5*5          " "......................4*4=16

6*6              " ".......................3*3=9

7*7             " "......................2*2=4

8*8              " "......................1*1=1

------------------------------------------------------

total square                                204
6 votes -- srestha ( 54.8k points)

There are n men and n women

Now we can select 1 woman from n women in nC1

With that 1 man can select  nC1 ways

So, by 1 woman and 1 man we can get   nC1 * nC1 ways...................i

Similarly , Now we can select 2 woman from n women in nC2

With that 2 man can select  nC2 ways

So, by 2 woman and 2 man we can get   nC2 * nC2 ways.........................ii

...........................................................

Now, by n woman and n man we can get   nCn * nCn ways........................iii

So, by adding these equation we get 

nC0.nC0 +nC1 * nC1+  nC2 * nC2 + nCnC3+.......................nCn * nC =(2nCn)

Ans will be (D)

 

 

4 votes -- srestha ( 54.8k points)

Let M:Males F:Females

Suppose n=3, then there are total 2n persons; M=F=3

Case Select no. of M's Out of 3 Select no. of F's out of 3 Total Ways
1 0 0 3C0*3C0=1
2 1 (select 1 M out of 3 so 3C1 ways) 1 3C1*3C1=9
3 2 2 3C2*3C2=9
4 3 3 3C3*3C3=1
    Total 20

 

Which fits none of the above options but this is equals to 2nCn=6C3=20

3 votes -- Rajesh Pradhan ( 16.9k points)
Selected Answer

Say, $r = \text{Move Right}$ and $u = \text{Move Up}$
so using 10 combination of r and 10 combinations of u moves we get a solution.

Convert the graphical moves to text and one such solution we get = $\{u, u, u, u, u, u, u, u, u, u, r, r, r, r, r, r, r, r, r, r\}$ now all possible arrangements of them is given by = $\frac{20!}{10! \times 10!} = {20 \choose 10}$

now we need to discard the segment move from $(4,4)$ to $(5,4)$:
to do that we first calculate how many solutions to our problem to reach $(10, 10)$ involves that segment. We'll then subtract those solutions from the total number of solutions.

Number of solutions to reach from (0,0) to (4,4) = all possible arrangements of {r, r, r, r, u, u, u, u} = $\frac{(4+4)!}{4! \times 4!} = {8 \choose 4}$

definitely we take the segment (4,4) to (5,4) = 1

now, Number of solutions to reach from (5,4) to (10,10) = all possible arrangements of {r, r, r, r, r, r, u, u, u, u, u} = $\frac{(6+5)!}{6! \times 5!} = {11 \choose 5}$

so required number of solutions for Q.85 is given by option D

i.e. $={20 \choose 10} - {8 \choose 4} \times 1 \times {11 \choose 5}$

11 votes -- Amar Vashishth ( 27.9k points)
Let us think this way.

If we can find all the paths through (4,4) and (5,4), then subtracting the result from all the possibilities should give us the answer.

So, moving to finding the paths passing through (4,4) and (5,4)

Starting from (0,0), we need 4 ups and 4 rights to go to (4,4). So we have 8C4 ways of doing that.

Similarly from (5,4) to (10,10) we need 6 ups and 5 rights. So we have 11C6 ways of doing that.

Total number of paths from (0,0) to (10,10) are 20C10.

So our answer will be 20C10 - (8C4)*(11C6) which is option d.
3 votes -- Satyandra ( 305 points)
Selected Answer

Number of ways selecting a captain from 15 players = $ \begin{pmatrix} 15 \\ 1 \end{pmatrix}$

Number of ways selecting remaining team members from remaining 14 players

= $ \begin{pmatrix} 14 \\ 10 \end{pmatrix}$  

The number of different ways to choose a team of 11 from a pool of 15 players and also select a captain

=$ \begin{pmatrix} 15\\ 1 \end{pmatrix}$ *$ \begin{pmatrix} 14 \\ 10 \end{pmatrix}$ =15*13*11*7= 11 *$ \begin{pmatrix} 15 \\ 11 \end{pmatrix}$

 

Hence,Option(B)11 *$ \begin{pmatrix} 15 \\ 11 \end{pmatrix}$ is The correct choice.

2 votes -- Leen Sharma ( 31.3k points)
Selected Answer

Use Derangement concept D5= 44 so answer is A

http://oeis.org/wiki/Number_of_derangements

16 votes -- pratikb ( 369 points)
Answer: A

Number of ways = 5C0*5! - 5C1*4! + 5C2*3! - 5C3*2! + 5C4*1! - 5C5*0! = 44
6 votes -- Rajarshi Sarkar ( 34.3k points)
Selected Answer

There are three ways to choose 6 Players.

  1. 5C3*4C2*2C1=120
  2. 5C2*4C2*2C2=60
  3. 5C2*4C3*2C1=80

So total No of ways is 260.

2 votes -- Manoj Kumar ( 37k points)
Selected Answer
Lets take an example . lets consider the given string is GATE.

so set of string of length 1 ={G,A,T,E} ; cardinality of set = 4

set of string of length 2 ={GA,AT,TE}

set of string of length 3={GAT,ATE}

set of strings of length 4 ={GATE}

and set of string of length 0 ={}

and we cant have any substring of length 5 as given string has only 4 length .

so total no of substrings are possible =0's length substring + 1lengths substrings + 2 length substrings +3 length substrings + 4 length substrings = 1+4+3+2+1

means for 1 length string to n length substrings . it will sum of the n natural no from 1 to n .

so 1+2+3+............... +n = n(n+1)/2
so total no substrings possible = 0 length strings + n(n+1)/2= 1+[n(n+1)/2]

so total no of substrings possible in n length string (All length inclusive )= 1+[n(n+1)/2]
6 votes -- Amit Pal ( 3.5k points)
Selected Answer

Distinct ways are there to split 50 identical coins among three people so that each person gets at least 5 coins

x1+5+x2+5+x3+5 = 50 

x1+x2+x3 = 35

Solving Non integral solution n=35 ,r =3

n+r-1 C r-1 = 35+3-1 C 3-1 = 37 C 2

Hence E is Answer

9 votes -- Prajwal Bhat ( 11.6k points)
Selected Answer

a) option answer .

5 votes -- kunal ( 20.3k points)
The word 'ABRACADABRA' have 11 letters. Therefore total permutations is 11!

However they are not unique 11 letters and have duplicates repeated as follows.

A - 5 times

B- 2 times

R- 2 times

C and D are unique.

Therefore answer will be option A.
2 votes -- junk_mayavi ( 489 points)

Let the $7$ Teams be $A,B,C,D,E,F,G$ and so each team plays total 6 matches.

Suppose, Team $A$ wins over $E,F,G$ and draws with $B,C,D$ hence total points scored by Team A = $9$ points

Now, Team $B$ wins over $E,F,G$ and draws with $A,C,D$ hence total points scored by Team B = $9$ points

Similarly, happens for next two teams $C$ and $D$ .

Hence, Finalized scores are => 

A = 9
B = 9
C = 9
D = 9
E = ? (Less than or equal to 4)
F = ? ("...")
G = ? ("...")

Given that the order among the teams with the same total are determined by a whimsical tournament referee.

So, He/She can order the top $3$ teams like $ABC$,$ABD$,$BCD$,$ACD$ .......

But, Question says " team must earn in order to be guaranteed a place in the next round "

Hence, Not to depend on that whimsical referee, the minimum total number of points a team must earn in order to be guaranteed a place in the next round = $9+1$ = $10$ points

3 votes -- Kapil Phulwani ( 47.4k points)
Selected Answer

B is ans.

2 votes -- 2018 ( 4.8k points)
(D) 121

Selecting 4 numbers from 9 is 9C4 = 126

We have to subtract all the cases where gcd of all numbers is 1 and this can only happen when all number should not be even. Which is 5C4 = 5

So answer will be 126 - 5 = 121
2 votes -- Mandeep Singh ( 1.3k points)

The sum 11 can be broken as 6 + 5

Let us name the players as A, B and C.

Case 1: Fix 6 and break 5

Suppose A throws 6. Players B and C can throw dice in following four ways to make sum 5

(1,4), (2,3), (3,2) and (4,1)

As any of the three players can throw value 6, so there are total $3\times 4=12$

Case 2: Fix 5 and break 6

Suppose A throws 5. Players B and C can throw dice in following five ways to make sum 6

(1,5), (2,4), (3,3), (4,2), (5,1)

As any of the three players can throw value 5, so there are total $3\times 5=15$

Adding case 1 and case 2 there are total $12 + 15 = 27$ ways

2 votes -- neha.i ( 295 points)
Selected Answer
Answer should be 3^N-1.

This is because the total possible combinations (i.e a line may either be at fault (in 2 ways i.e stuck at fault 0 or 1) or it may not be , so there are only 3 possibilities for a line ) is 3^N. In only one combination the circuit will have all lines to be correct (i.e not at fault.) Hence 3^N-1. (as it has been said that circuit is said to have multiple stuck up fault if one or more line is at fault )

Please Comment , if anyone finds it wrong.
23 votes -- Afaque Ahmad ( 931 points)
Substitute k=3 then we get p=9 and q=12  on verifying we get option A.
5 votes -- kireeti ( 1.1k points)

The odd series is 1 3 5 7 ... 2k-1

So, 1+(t1-1)2=2k-1

      or t1=k;

P = (k/2) [2x1+(k-1)2]=k^2

The odd series is 2 4 6 8 10  ... 2k

So, 2+(t2-1)2=2k

      or t2=k;


Q = (k/2) [2x2+(k-1)2]=k^2+k
So P=Q-k  is answer...

2 votes -- Palash Nandi ( 1.6k points)
Selected Answer

answer - C

select any 3 elements from given 8 elements - 8C3

19 votes -- ankitrokdeonsns ( 9.1k points)

If you pick any 3 numbers in the given order from the array(sorted) remaining 5 elements are already sorted. You can not change the relative position of those 5 elements because they are distinct and already sorted. So no of ways = 8C3 

Same argument holds for picking up 5 elements initially. No of ways = 8C5

4 votes -- Debashish Deka ( 48k points)
Selected Answer

a. n= 2 (1+1)  n=3(1+2, 2+1) n=4(1+3,3+1,2+2) n=5(1+4,4+1,2+3,3+2)

so x1+x2=n , x1,x2>0 (no.of integral sol)

This is same as number of ways of putting n-2 (as we can't have 0 for either x1 or x2) identical balls into two distinct bins, which is obtained by putting a divider across n-2 balls and taking all possible permutations with n-2 being identical. i.e., (n-2 + 1)!/(n-2)! = (n-1). We can also use the following formula 

n-2+2-1C2-1 =n-1C1

b. n=3(1+1+1) n=4(1+1+2,1+2+1,2+1+1) n=5(1+1+3,1+3+1,3+1+1,2+2+1,2+1+2.,1+2+2) 

so x1+x2+x3=n , x1,x2,x3>0 (no.of integral sol) 

Here, we can permute n-3 items with 2 dividers which will give (n-3 + 2)!/(n-3)!2!

= (n-1)!/(n-1-2)!2!

=n-1C2

c. n-k+k-1Ck-1 =n-1Ck-1

11 votes -- Supromit Roy ( 689 points)
Selected Answer

Possible outcome for a couple:

  1. only wife comes
  2. both come
  3. none come


Thus 3 possibilities for each couple, so 3 x 3 x 3 x ... n times = $3^n$

26 votes -- Palash Nandi ( 1.6k points)
Selected Answer

As there have to be atleast k balls in each bag, so firstly put k balls in each bag i.e k*n balls.

Then now we have total m-k*n balls remaining.

We can use balls & sticks method now !

n bags= n variables, they need to equal to m-k*n, no restrictions on how many balls in each bag !

x1 + x2 + ... + xn = m- k*n , x1,x2..xn >=0.

So when we solve it

We get

C(m - k*n + n - 1, n-1 ) = C(m - k*n + n - 1, m- k*n )

11 votes -- Akash ( 41.5k points)

As there have to be atleast k balls in each bag, so firstly put k balls in each bag i.e k*n balls. Then after, (m - kn) identical balls are left which we have to put it in n distinct bags, so use this general formula: 

C(n + m - kn - 1, n -1).

So, answer would be b.

5 votes -- Vivek sharma ( 2.2k points)
Selected Answer

This question is slightly ambigous. So first let us understand what question is asking. So in a book, we have letters A-Z and each letter is printed twice, so there are 52 letters. Now we have to color each letter, so we need a pair of colors for that, because each letter is printed twice. Also in a pair, both colors can be same. Now condition is that a pair of colors can't be used more than once.

So suppose Mala has 3 colors : Red, Blue, Green. She can color as follows : 1:(Red,Red),  2:(Blue,Blue), 3:(Green,Green), 4: (Red,Blue), 5: (Red,Green),

6 : (Blue,Green). 
Now we don't have more pairs of colors left, we have used all pairs, but could color only 6 letters out of 26. So question is to find minimum no. of colors, so that we could color all 26 letters.

So if Mala has k colors, she can have k pairs of same colors, thus coloring k letters, then kC2 other pairs of colors, thus coloring kC2 more letters. 
So total no. of letters colored = $k + \binom{k}{2} = k+ k \left( \frac{k−1}{2} \right) = k \left( \frac{k+1}{2} \right)$. 
So we want $k \left( \frac{k+1}{ 2} \right) \geq 26$ i.e. $k \left(k+1\right) \geq 52 \implies k \geq  7$, so option (C) is correct.

Ref: http://www.cse.iitd.ac.in/~mittal/gate/gate_math_2004.html

 

11 votes -- Anu ( 10.2k points)
Selected Answer

Q.84
Say, $r = \text{Move Right}$ and $u = \text{Move Up}$
so using 10 combination of r and 10 combinations of u moves we get a solution.

Convert the graphical moves to text and one such solution we get = $\{u, u, u, u, u, u, u, u, u, u, r, r, r, r, r, r, r, r, r, r\}$ now all possible arrangements of them is given by = $\frac{20!}{10! \times 10!} = {20 \choose 10}$

Hence, option A is true.

 

15 votes -- Amar Vashishth ( 27.9k points)

84 At each move, robot can move either 1 unit right, or 1 unit up, and there will be 20 such moves required to reach (10,10) from (0,0). So we have to divide these 20 moves, numbered from 1 to 20, into 2 groups : right group and up group. Right group contains those moves in which we move right, and up group contains those moves in which we move up. Each group contains 10 elements each. So basically, we have to divide 20 things into 2 groups of 10 10 things each, which can be done in 20!/(10! ☓10!)=20C10 ways. So option (A) is correct.

3 votes -- Anu ( 10.2k points)
Selected Answer

r red balls can be distributed into n distinct boxes in C(n+r-1,r) = .(n+r-1)! / (n-1)! r!

b blue balls can be distributed in C(n+b-1,b) = (n+b-1)! / (n-1)! b!

By product rule total ways are (n+b-1)! (n+r-1)! / (n-1)! b! (n-1)! r!

SO THE ANSWER IS  A.

17 votes -- Madhu Veluguri ( 205 points)
Selected Answer

answer - D

first place n zeroes side by side _ 0 _ 0 _ 0 ... 0 _

k 1's can be placed in any of the (n+1) available gaps hence number of ways  = n+1Ck

11 votes -- ankitrokdeonsns ( 9.1k points)
Selected Answer
answer - D

number of ways roses can be distributed - { (0, 10), (1, 9), (2, 8).....(10, 0) } - 11 ways

similarly sunflowers and daffodils can be distributed in 16 ways each

total number of ways 11 x 16 x 16 = 2816
10 votes -- ankitrokdeonsns ( 9.1k points)
for each flower, say there are $n$ number of flowers, we apply star and bars method for each flower. $n$ flowers of a type will generate $(n+1)$ spaces we just need to place one bar. to do that we need to select a position.

so, for roses : $\binom{10+1}{1}$
for sunflowers : $\binom{15+1}{1}$
for daffodils : $\binom{15+1}{1}$

total number of ways distribution can take place = $11 \times 16 \times 16 = 2816$
6 votes -- Amar Vashishth ( 27.9k points)
Selected Answer
assuming an string of length n provided all alphabets are distinct..

no of strings of length 1 = n

no of strings of length 2 = n-1

no of strings of length 3 = n-2
.
.
.
no of string of length n = 1
total = n + (n -1) + (n - 2) + (n - 2) + ..... + 1
         = n(n+1)/2
7 votes -- Digvijay ( 46k points)
Selected Answer
  • If the number ends with a 0 then there are 9 choices for the first digit, 8 for the second and 7 for the third, which makes 1×9×8×7=504 possibilities.

  • If the number is even ending with something else than 0 then there are 4 choices for the last digit, 8 choices for the first digit (no 0 nor the last digit), 8 for the second digit and 7 for the third digit, which makes 4×8×8×7=1792

Together, this gives 2296 numbers with 4 distinct digits that are even. Note that this does not allow leading 0, as you see to want it based from the question

17 votes -- yallasrikanthreddy ( 309 points)
Available digits are { 0,1 , 2  ... 9}

Even { 0 2 4 6 8}

Odd { 1 3 5 7 9 }

Pos 4 must be one of even number . But Pos 1 can be odd or even but not 0.

(case 1 )

POS 1: ODD { ONE OF 1 3 5 7 9}

POS 2:7C1

POS:3 8C1                                                 SO Total is : 5 X (7x8x5)=1400

POS 4: ONE OF EVEN NO i.e. 5C1

(CASE 2: POS1 IS EVEN INLUDING 0)

POS 1: EVEN { ONE OF 0,2,4,6,8}

POS 2:7C1

POS:3 8C1                                                 SO Total is : 5 X (7x8x4)=1120

POS 4: ONE OF EVEN NO EXCLUDING THE DIGIT OF POS1 i.e. 4C1

(Case 3: POS1 IS 0)

POS 1: 0

POS 2:7C1

POS:3 8C1                                                 SO Total is : 1 X (7x8x4)=224

POS 4: ONE OF EVEN NO EXCLUDING 0  i.e. 4C1

The ans is : case1 + case2 - case3 =(1400+1120-224)=2296
5 votes -- Palash Nandi ( 1.6k points)
Selected Answer
Let we denote number of n-pennants by f(n), so f(10) is number of 10-pennants.

A 10-pennant means sum of numbers in sequence is 10. If we look at any 9-pennent, we can make it a 10-pennant by adding 1 into that sequence. Similarly, we can make any 8-pennant a 10-pennant by adding 2 into that sequence.

So all 10-pennants can be formed by 8-pennants and 9-pennants, and no other pennant (since we can add only 1 or 2 into a sequence)

So f(10) = f(9) + f(8)

This is in fact a fibonacci sequence, in which F(1) = 1, f(2) = 2, so this sequence becomes

1, 2, 3, 5, 8, 13, 21, 34, 55, 89,..

So f(10) = 89.
25 votes -- Happy Mittal ( 10.7k points)
Numbers could be any one of

(1,1,1,1,1,1,1,1,1,1),(1,1,1,1,1,1,1,1,2),(1,1,1,1,1,1,2,2),(1,1,1,1,2,2,2),(1,1,2,2,2,2),(2,2,2,2,2)

So, the number of 10 penants =1+  9!/8! + 8!/6!2!  + 7!/4!3! + 6!/2!4! +1 =89
15 votes -- srestha ( 54.8k points)
Selected Answer

First do prime factorization of 2014 - 21 x 191 x 531

Now to get a factor of 2014, we can choose any combination of the prime factors including 0. i.e; 2and 21 are possible and similarly for other prime factors also, there are 2 possibilities. So, total number of positive integral factors

$= 2 \times 2 \times 2 = 8$

(When all the powers of prime factors are 0, we get 1 and when all the powers are maximum, we get the given number.)

11 votes -- Arjun Suresh ( 286k points)
2014 = 2 x 19 x 53

total  positive integral factor=(2x2x2)=8
3 votes -- Palash Nandi ( 1.6k points)
Selected Answer
no. of substrings of length n is 1

no. of substrings of length n-1 is 2

no. of substrings of length n-2 is 3

so n(n+1)/2
8 votes -- Bhagirathi Nayak ( 13.1k points)
Selected Answer

Answer to a is 2nCn/(n+1) which is the Catalan number. 

This is also equal to the number of possible combinations of balanced parenthesizes. 

See the 5th proof here http://en.wikipedia.org/wiki/Catalan_number

 

7 votes -- Arjun Suresh ( 286k points)
Selected Answer
300! is 1*2*3*...*300

Now there are 27 multiples of 11 from 1 to 300, so they will include 11 as a prime factor atleast once.

121 and 242 will contain an extra 11, all other will contain 11 as a factor only once.

So total number of 11's = 27+2 = 29.

So exponent of 11 is 29 i.e. option C.
15 votes -- Happy Mittal ( 10.7k points)

Simple Method:

Floor[300/11] =27

Floor[27/11] =2

Floor[2/11] =0

Repeat this and when get 0 stop and sum all the results.

Ans: 27 + 2 +0=29 

Note: If Having doubt you can cross check it.

7 votes -- papesh ( 22.8k points)
Consider the following sequence:

$s_1 = s_2 = 1$ and $s_i = 1 + \min  \left({s_{i-1}, s_{i-2}}\right) \text{ for } i > 2$.

Prove by induction on $n$ that $s_n=⌈\frac{n}{2}⌉$.
The number of possible commutative binary operations that can be defined on a set of $n$ elements (for a given n) is ___________.

Answers: Counting

Selected Answer

$s_3 = 1 + \min(s_1, s_2) \\= 1 + \min(1, 1) = 2 = \lceil \frac{3}{2} \rceil$.

So, base condition of induction satisfied. 

Assume, $s_{n-2} =\lceil \frac{n-2}{2} \rceil$ and $s_{n-1} =\lceil \frac{n-1}{2} \rceil$ (Induction hypothesis)

Now, we have to prove,

$s_n = \lceil \frac{n}{2} \rceil$

$s_n = 1 + \min(s_{n-1}, s_{n-2}) \\= 1 +  \lceil \frac{n-2}{2} \rceil \\= 1 +  \lceil \frac{n}{2} \rceil -1 \\=\lceil \frac{n}{2}\rceil$

(Hence, proved)

5 votes -- Arjun Suresh ( 286k points)
Selected Answer

Given , the cardinality of set = n

So consequently ,

No of entries in operation table(Cayley table)  =  n2

And hence if we consider lower triangular or upper triangular half , we have : (n2 + n) / 2

And in an operation table , each entry can be filled in n ways by any one element out of given n elements of the set..

So no of ways we can fill the upper or lower triangular half  =  n(n^2 + n)/2

So each of these is nothing but an instance of operation table of commutative operation as say (i,j) entry is filled in the table so (j,i) entry will also be the same hence the choice for (j,i) entry is constrained to 1 as we are concerned about commutativ operation table here..

Therefore,

No of possible binary operations which are commutative  = n(n^2 + n)/2

3 votes -- HABIB MOHAMMAD KHAN ( 66.5k points)
Selected Answer
Answer: 36

$2100 = 7\times 3\times 2^2 \times 5^2$

Hence, total number of factors will be $= (1+1)\times (1+1)\times (2+1)\times (2+1) \\= 2 \times 2\times 3 \times 3 \\= 36$,

because any factor is obtained by multiplying the prime factors zero or more times. (one extra for zero)
14 votes -- Rajarshi Sarkar ( 34.3k points)
If the ordinary generating function of a sequence $\big \{a_n\big \}_{n=0}^\infty$  is $\large \frac{1+z}{(1-z)^3}$, then $a_3-a_0$ is equal to ___________ .

Answers: Generating Functions

Selected Answer
$\frac{1+z}{(1-z)^3} = (1+z)(1-z)^{-3}$

$(1-z)^{-3} = 1 + \binom{3}{1}z + \binom{4}{2}z^2 + \binom{5}{3}z^3 + \dots \infty$

$\color{navy}{(1+z)(1-z)^{-3} = (1+z)*(1 + \binom{3}{1}z + \binom{4}{2}z^2 + \binom{5}{3}z^3 + \dots \infty)}$

$a_0$ is the first term in the expansion of above series and $a_3$ is the fourth term (or) coefficient of $z^3$

$a_0$ = coefficient of $z^0 = 1$
$a_3$ = coefficient of $z^3 = \binom{5}{3} + \binom{4}{2} = 10 + 6$

$\color{maroon}{\Rightarrow a_3 - a_0 = 16 - 1 = 15}$
14 votes -- Manish Joshi ( 25k points)

yes 15 is correct ans 

3 votes -- 2018 ( 4.8k points)

Find the number of positive integers n for which n2+96 is a perfect square.

A palindrome is a sequence of digits which reads the same backward or forward. For example, 7447, 1001 are palindromes, but 7455, 1201 are not palindromes. How many 8 digit prime palindromes are there?

Answers: Number Series

Selected Answer

n^{2} + 96 = x^{2}
x^{2} - n^{2} = 96
(x-n)(x+n) = 96

Since, x and n both should be positive integer. (x-n) and (x+n) will be divisors of 96.

By observation, (x-n) should be smaller than (x+n) because x and n are positive integers.
(x-n) = k1 $\rightarrow$ x= n+k1

(x+n)= k2 $\rightarrow$ n+k1+n = k2 $\rightarrow$ 2n+k1 = k2 $\rightarrow$ 2n = k2-k1 $\rightarrow$ $n = \left ( \frac{k2-k1}{2} \right )$

As we have seen from above, $n = \left ( \frac{k2-k1}{2} \right )$

Therefore, for n to be a positive integer, k2-k1 should be even. That is, both should be odd or both should be even.

There are 6 pairs of divisors when multiplied becomes 96 = (1,96), (2,48), (3,32), (4,24), (6,16), (8,12) .

Therfore, there are only 4 such possibilties. Phew!

5 votes -- Shyam Singh ( 1.4k points)
Selected Answer
I think the answer should be 0, as any even digit palindrome(other than 11) cannot be prime. Even digit palindromes will always be divisible by 11(you can check the divisibility test by 11).
3 votes -- sourb ( 121 points)
Q 1. The number of permutation of {1,2,3,4,5} that keep at least one integer fixed is.

A) 81  B)76  C)120   D)60

In how many ways can the letters of the word ABACUS be rearranged such that the vowels always appear together?

  1. $\displaystyle\frac{(6+3)!}{2!}$
     
  2. $\displaystyle\frac{6!}{2!}$
     
  3. $\displaystyle\frac{3!3!}{2!}$
     
  4. $\displaystyle\frac{4!3!}{2!}$
     
  5. None of the above.

Answers: Permutation

Answer C

There are five places

                                         __  __  __  __  __ 

And we are given five integers {1, 2, 3, 4, 5}


And we are supposed to fix one integer

  • Let me fix integer $1$ at position 1

                                        1  __  __  __  __ 


Now at other four places I can keep the any integers, other than the one already used i.e. 1

So, at second position {2, 3, 4, 5} any one can be kept. There are total $4$ possible options

  • Let me keep $2$

Now, at third position {3, 4, 5} any one can be kept
There are total $3$ possible options

  • Let me keep $3$

So, at fourth position {4, 5} any one can be kept
There are total $2$ possible options

  • Let me keep $4$

Now can fifth position only {5} can be kept as that is the only one left
There is only $1$ possible option

So, overall, when I keep $1$ fixed on position 1 there are total $4*3*2*1$ which is $24$ possible options

Instead of keeping $1$, I can keep any of {1, 2, 3, 4, 5} integers. So there are total $5$ options when it comes to keeping a number on position 1

And with each number which I keep on position 1, there are $24$ possible options of placing other integers at other places

So, in all, there are $5*24$ which is $120$ possibilities

2 votes -- Arunav Khare ( 3.2k points)
Selected Answer

Take AAU together and treat it like 1 entity. Now arrange $\boxed{\small\text{AAU }}$BCS in $4!$ ways.

Then, the AAU can be arranged in $\dfrac{3!}{2!}$ ways because A has been repeated twice.

 

So, total arrangements $= \dfrac{4!3!}{2!}$

Option d. is the correct answer.

11 votes -- yes ( 1.6k points)

The rules for the University of Bombay five-a-side cricket competition specify that the members of each team must have birthdays in the same month. What is the minimum number of mathematics students needed to be enrolled in the department to guarantee that they can raise a team of students?

  1. 23
  2. 91
  3. 60
  4. 49
  5. None of the above.

Answers: Pigeonhole

Selected Answer
There are 12 months and we have to get 5 people having birthdays in the same month in order to form a team . we can apply the pigeon hole principal :

$\left \lceil N/12 \right \rceil$ = 5

On solving we get N=49 .

Hence answer is D.
9 votes -- Riya Roy(Arayana) ( 7k points)

The Fibonacci sequence is defined as follows: $F_{0} = 0, F_{1} = 1,$ and for all integers $n \geq 2, F_{n} = F_{n−1} + F_{n−2}$. Then which of the following statements is FALSE?

  1. $F_{n+2} = 1 + \sum ^{n}_{i=0} F_{i}$ for any integer $n \geq 0$
  2. $F_{n+2} \geq \emptyset^{n}$ for any integer $n \geq 0$, where $\emptyset=\left(\sqrt{5}+1\right) / 2$ is the positive root of $x^{2} -x - 1= 0$.
  3. $F_{3n}$ is even, for every integer $n \geq 0$.
  4. $F_{4n}$ is a multiple of $3$, for every integer $n \geq 0$.
  5. $F_{5n}$ is a multiple of $4$, for every integer $n \geq 0$.

Let H1, H2, H3, ... be harmonic numbers. Then, for n ∊ Z+,  $\sum_{j=1}^{n} H_j$ can be expressed as

  1. nHn+1 - (n + 1)
  2. (n + 1)Hn - n
  3. nHn - n
  4. (n + 1) Hn+1 - (n + 1)

Answers: Recurrence

Selected Answer
F0 F1 F2 F3 F4 F5 F6 F7
0 1 1 2 3 5 8 13

OPTION E)  F5n is a multiple of 4, for every integer n≥0  False

4 votes -- Umang Raman ( 14.4k points)
Selected Answer

The $n^{th}$ Harmonic Number  is defined as the summation of the reciprocals of all numbers from $1$ to $n$.

$$H_n = \sum_{i = 1}^n \frac1 i = \frac1 1 + \frac1 2 + \frac1 3 + \frac1 4 + \dots + \frac1 n$$

Lets call the value of $\sum_{j = 1}^n H_j$ as $S_n$

Then,

$$\begin{align}
S_n &= H_1 + H_2 + H_3 + \dots + H_n\\[1em]

&= \small \overbrace{\left ( \color{red}{\frac1 1} \right )}^{H_1}
 + \underbrace{\left (\color{red}{\frac1 1} + \color{blue}{\frac1 2} \right )}_{H_2}
 + \overbrace{\left (\color{red}{\frac1 1} + \color{blue}{\frac1 2} + \color{green}{\frac1 3} \right )}^{H_3}
 + \dots
 + \underbrace{\left (\color{red}{\frac1 1} + \color{blue}{\frac1 2} + \color{green}{\frac1 3} + \dots + \frac1 n \right )}_{H_n}\\[1em]

&=\small  \color{red}{n \times\frac1 1}+ \color{blue}{ (n-1) \times\frac1 2} + \color{green}{(n-2) \times \frac1 3} + \dots + 1 \times \frac1 n\\[1em]

&= \sum_{i = 1}^n \Big (n - i + 1 \Big ) \times \frac1 i\\[1em]

&= \sum_{i = 1}^n \left ( \frac{n + 1}{i} - 1 \right )\\[1em]

&= \left ( \sum_{i = 1}^n \frac{\color{red}{n+1}}{i}\right ) - \color{blue}{\left ( \sum_{i = 1}^n 1\right )}\\[1em]

&= \Biggl (\color{red}{(n+1)} \times \underbrace{\sum_{i = 1}^n \frac1 i}_{=H_n}\;\Biggr ) - \color{blue}{n}\\[3em]
\hline
\large S_n &= \large (n+1)\cdot H_n - n
\end{align}$$

Hence, the answer is option B.

22 votes -- Pragy Agarwal ( 19.3k points)

Suppose

$\begin{pmatrix}
0&1 &0&0&0&1 \\
1&0&1&0&0&0  \\
0&1&0&1&0&1  \\
0&0&1&0&1&0  \\
0&0&0&1&0&1  \\
1&0&1&0&1&0
\end{pmatrix}$

is the adjacency matrix of an undirected graph with six vertices: that is, the rows and columns are indexed by vertices of the graph, and an entry is $1$ if the corresponding vertices are connected by an edge and is $0$ otherwise; the same order of vertices is used for the rows and columns. Which of the graphs below has the above adjacency matrix?

  1. Only $(i)$
  2. Only $(ii)$
  3. Only $(iii)$
  4. Only $(iv)$
  5. $(i)$ and $(ii)$

Answers: Adjacency Matrix

Selected Answer

Yes, Option (e) must be the right answer.


Number of edges in the graph:

Since the graphs are undirected, it can be observed that there will be two 1's in the adjacency matrix corresponding to each edge in the graph.

For example, suppose two there is an edge between nodes A & B, then there will be 1 in position [A, B] & there will be a 1 in position [B,A] of the adjacency matrix.

That's why the given adjacency matrix is symmetric.


So the number of edges in the graph must be equal to half the number of 1's in the adjacency matrix.

Hence number of edges will be 7 in the graph.

All the other graphs except (iii), have 7 edges.So it is clear that the adjacency matrix does not represents graph (iii).

Isomorphism:

From the definition of Isomorphic graphs, it can be inferred that,

Isomorphic graphs must have same (adjacency matrix) representation.

Thus after eliminating graph (iii) we have to check for isomorphism among graphs (i), (ii) & (iv).

It can clearly be observed that graphs (ii) & (iv) are not isomorphic to each other.

It can also be observed that graph (i) & (ii) are isomorphic(Rotate graph (i) by 90 degree left/right.

Graph (ii) is looking like a closed envelope in the figure, try to view it like an open envelope, like a trapezium over a rectangle.) 

So now it can be inferred that either the adjacency matrix is representing both graphs (i) & (ii) or it is only representing (iv).


Cycles of length 6 :

Now from the adjacency matrix it can be observed that there should be a cycle of length 6 in the graph, since [1, 2], [2, 3], [3, 4], [4, 5], [5, 6], [6, 1] are all 1's in the matrix.(as 1 at any position [x, y] represents an edge between x & y in the graph).

& both graphs (i) & (ii) have cycles of length 6, but graph (iv) does not has any cycle of length 6, it has cycles of length 4 & 5 only.

Thus graph (iv) can not have the above adjacency matrix.

Hence the adjacency matrix represents graphs (i) & (ii).

7 votes -- Anurag Pandey ( 12.8k points)

What is the chromatic number of an $n$ vertex simple connected graph which does not contain any odd length cycle? Assume $n  > 2$.

  1. 2
  2. 3
  3. n-1   
  4. n

Answers: Chromatic Number

Selected Answer

Lemma 1.- G is bipartite, if and only if it does not contain any cycle of odd length.

Proof. Suppose G has an odd cycle. Then obviously it cannot be bipartite, because no odd cycle is 2-colorable. Conversely, suppose G has no odd cycle. Then we can color the vertices greedily by 2 colors, always choosing a different color for a neighbor of some vertex which has been colored already. Any additional edges are consistent with our coloring, otherwise they would close a cycle of odd length with the edges we considered already. The easiest extremal question is about the maximum possible number of edges in a bipartite graph on n vertices. 1 ref@ http://math.mit.edu/~fox/MAT307-lecture07.pdf

Bipartite Graph: A graph which is 2-colorable is called bipartite. We have already seen several bipartite graphs, including paths, cycles with even length, and the graph of the cube (but not any other regular polyhedra) 

ref@ http://ocw.mit.edu/high-school/mathematics/combinatorics-the-fine-art-of-counting/lecture-notes/MITHFH_lecturenotes_9.pdf

3. Bipartite graphs: By definition, every bipartite graph with at least one edge has chromatic number 2. (otherwise 1 if graph is null graph )

ref@ http://math.ucsb.edu/~padraic/mathcamp_2011/introGT/MC2011_intro_to_GT_wk1_day4.pdf

12 votes -- Mithlesh Upadhyay ( 5.3k points)
2 draw some random graph and you will realise that 2 is the chromatic number
9 votes -- Bhagirathi Nayak ( 13.1k points)
Selected Answer

The chromatic number of a graph  is the smallest number of colors needed to color the vertices so that no two adjacent vertices share the same color.

Hence minimum number of colors needed to color given graph is equal to 3( option 2

For odd length cycles we need minimum 3 colors for vertex coloring and for even length cycles we need just 2. 

12 votes -- vinodmits ( 367 points)

If $G$ is the forest with $n$ vertices and $k$ connected components, how many edges does $G$ have?

  1. $\lfloor n/k \rfloor$
  2. $\lceil n/k \rceil$
  3. $n-k$
  4. $n-k+1$
The $2^n$  vertices of a graph G corresponds to all subsets of a set of size $n$, for $n \geq 6$.  Two vertices of G are adjacent if and only if the corresponding sets intersect in exactly two elements.

The number of connected components in G is:

$n$

$n + 2$

$2^{n/2}$

$\frac{2^{n}}{n}$

Let $G$ be an arbitrary graph with $n$ nodes and $k$ components. If a vertex is removed from $G$, the number of components in the resultant graph must necessarily lie down between

  1. $k$ and $n$
  2. $k-1$ and $k+1$
  3. $k-1$ and $n-1$
  4. $k+1$ and $n-k$

 

The maximum number of possible edges in an undirected graph with n vertices and k components is ______. 

 

Answers: Connected Components

Selected Answer

a forest is a collection of trees. here we are given a forest with n vertices and k components. a component is itself a tree.

since there are k components means that every component has a root(every tree has one), therefore we have k roots.

introduction of each new vertex to the forest introduces a single edge to a forest. so for remaining n-k vertices when introduced, to make up to n vertices, contributes to n-k edges.

Hence, ans = option C = (n-k)

16 votes -- Amar Vashishth ( 27.9k points)

A forest is an acyclic graph(with no cycle) , i.e all these components are a tree. With k components there are k roots. And whenever a new node is added to a tree only a singe edge is introduced.
With k roots , remaining nodes are (n-k) each of which introduces an edge. Hence there are (n-k)*1=(n-k) edges.

16 votes -- Srinath Jayachandran ( 3.7k points)
Selected Answer

B. $n+1$ (subsets of size < 2 are all disconnected) $+ 1$ (subsets of size >= 2 are all connected) $= n+2.$

18 votes -- Vikrant Singh ( 13.4k points)
Selected Answer
If a vertex is removed from the graph $G$,

Lower Bound: number of components decreased by one = $k - 1$ (remove an isolated vertex which was a component)

Upper Bound: number of components = $n-1$ (consider a vertex connected to all other vertices in a component as in a star and all other vertices outside this component being isolated. Now, removing the considered vertex makes all other $n-1$ vertices isolated making $n-1$ components)

Therefore (C).
28 votes -- Danish ( 3.5k points)
Selected Answer

Hopefully it should be clear that in any such graph all components will be complete, i.e., have all possible edges. Thus the only remaining question is how large each component should be?

If there are two components with $a$ and $b$ vertices, $a>1, b> 1$, then together they can have at most


$\binom{a}{2} + \binom{b}{2} = \frac{1}{2} \left(a^2 - a + b^2 - b \right)$ edges.

However, if we place all but one of the vertices in a single component, we could have

$\binom{a+b-1}{2} + \binom{1}{2} = \frac{1}{2} \left(a+b-1\right)\left(a + b - 2\right)$
$=\frac{1}{2} \left(a^2 + 2ab -3a + b^2 - 3b + 2 \right)$ edges.

Subtracting the first quantity from the second gives

$\frac{1}{2}\left(\left(2ab - 3a - 3b +2\right) - \left(-a - b \right)\right) \\=ab-a-b+a \\= (a-1)(b-1) \text{ which is } > 0$

Hence it is better not to have two components with multiple vertices.

This leaves us with the answer that all components should have one vertex except one, which will have
$n-k+1$  vertices, for a total of $\binom{n-k+1}{2}$ edges.

 

in simple connected graph , number of edges , 

$(n-1) \leq e \leq n. \frac{(n-1)}{2}$

in simple unconnected graph with k component , number of edges ,

$(n-k) \leq e \leq (n-k).\frac{(n-k+1)}{2 }$

note :- put k=1 then it will be connected graph .

reference @ http://www.quora.com/What-is-the-maximum-number-of-edges-in-graph-with-n-vertices-and-k-components

another read @ http://stackoverflow.com/questions/24003861/maximum-number-of-edges-in-undirected-graph-with-n-vertices-with-k-connected-com

18 votes -- Mithlesh Upadhyay ( 5.3k points)
easy one.
if u want maximum number of nodes and k vertices then u should have k-1 components. with only one vertices and only one should contain remaining vertex ,

like

if i take 6 vertex and have to make 4 component then i will make the  4 component in this way ,

1 vertex 1 vertex 1 vertex 3 vertex.

and now i will make the last one complete graph . then it will have maximum number if edges.

so if u have n vertices and k component then just give (k-1) component one vertex and the remaining will be (n-(k-1)) now make that bigger one a complete graph . i.e ( n-k-1) ( n-k-1+1)/2 complete graph formula . n(n-1)/2 = (n-k)(n-k+1)/2
7 votes -- No Need ( 13.7k points)
How many graphs on $n$ labeled vertices exist which have at least $\frac{(n^2 - 3n)}{ 2}$ edges ?

${}^{\left(\frac{n^2-n}{2}\right)}C_{\frac{n^2-3n} {2}}$

${\sum_{k=0}^{\left (\frac{n^2-3n}{2} \right )}} .^{\left(n^2-n\right)}C_k$

${}^{\left(\frac{n^2-n}{2}\right)}C_n$

${\sum_{k=0}^n}.^{\left(\frac{n^2-n}{2}\right)}C_k$
How many undirected graphs (not necessarily connected) can be constructed out of a given set $V=\{v_1, v_2, \dots v_n\}$ of $n$ vertices?

$\frac{n(n-1)} {2}$

$2^n$

$n!$

$2^\frac{n(n-1)} {2} $
An undirected graph is complete if there is an edge between every pair of vertices. Given a complete undirected graph on $n$ vertices, in how many ways can you choose a direction for the edges so that there are no directed cycles?

$n$

$\frac{n(n-1)}{2}$

$n!$

$2^n$

$2^m, \: \text{ where } m=\frac{n(n-1)}{2}$

Answers: Counting

Selected Answer
Let $a = \frac{n(n-1)}{2}, b = \frac{n^2 -3n}{2}$

Minimum no of edges has to be $\frac{n^2 -3n}{2} = b$.

Maximum no of edges in simple graph = $\frac{n(n-1)}{2} = a$.

So, no of graph with minimum $b$ edges :

$= C(a,b) + C(a,b+1) +  C(a,b+2) + \dots +C(a,a)$

$= C(a,a-b) + C(a,a-(b+1)) +  C(a,a-(b+2)) + \dots +C(a,0)$

$= C(a,n) + C(a,n-1) +  C(a,n-2) + \dots +C(a,0))\\ \left(\because a-b = n \right)$

$= C\left(\frac{n(n-1)}{2},n\right) + C\left(\frac{n(n-1)}{2}, n-1\right) \\+  C\left(\frac{n(n-1)}{2},n-2\right) + \dots +C\left(\frac{n(n-1)}{2},0\right)$

$ =\sum_{k=0}^{n} {}^{\left(\frac{n^2-n}{2}\right)}C_k$

 

Option D..
23 votes -- Digvijay ( 46k points)
Selected Answer

with n vertices we have nC2 edges and each subset of these edges will form a graph, so total number of undirected  graph possible = 2n(n-1)/2

15 votes -- Vikrant Singh ( 13.4k points)
Selected Answer
Answer: C

The number of max edges a simple graph can have is $\frac{n×(n−1)}{2}$.

So, for a graph with 3 nodes the max number of edges is 3.
Now there can be 0 edges, 1 edge, 2 edges or 3 edges in a 3 node simple graph.
So the total number of unlabled simple graphs on 3 nodes will be  4.
Similarly for two node graph we have option of 0 or 1 edge and for one node graph we have option of 0 edge.
So the total number of simple graphs upto three nodes are: 4+2+1=7.
10 votes -- Rajarshi Sarkar ( 34.3k points)

answer = option C

13 votes -- Amar Vashishth ( 27.9k points)
Selected Answer

Take the example of a triangle (K3) where n = 3.

We can have total of 8 permutations - since each edge can be filled with two options ' > ' or ' < ' => 2 * 2 * 2 = 8.

We can have a cycle only in two permutations  =>  ' > > > ' and ' < < < '.

And hence, it is 8-2 = 6 when there are no directed cycles. This corresponds to only option (c), and no other option. 

2 votes -- tarun_svbk ( 1k points)

Let $G$ be a connected, undirected graph. A cut in $G$ is a set of edges whose removal results in $G$ being broken into two or more components, which are not connected with each other. The size of a cut is called its cardinality. A min-cut of $G$ is a cut in $G$ of minimum cardinality. Consider the following graph.

  1. Which of the following sets of edges is a cut

    1. $\left\{(A, B), (E, F), (B, D), (A, E), (A, D)\right\}$
    2. $\left\{(B, D), (C, F), (A, B)\right\}$
  2. What is cardinality of min-cut in this graph?
  3. Prove that if a connected undirected graph $G$ with $n$ vertices has a min-cut of cardinality $k$, then $G$ has at least $(nk/2)$ edges

 

Answers: Cutvertices&edges

Answer :-

a

(i) Not a cut. We have spanning tree after removing this edges.

(ii) This is cut.we break graph into two pieces.

B) Min cut size -> 2. (BC,CF). Removing this two edges disconnects C from remaining graph.
5 votes -- Akash ( 41.5k points)
The answer for a

1 this will not disconnect the graph. Make and check.

2- it will disconnect the graph. and remember the disconnected graph can have more than one vertices

answer for B,

we can always make a graph disconnected by removing the edges equal to min degree of a node. not believe me . remove the two edges BC and CF . as we can get a islolated vertex. tit will become disconnected .

on the same basis the proof can be done,

if k edges has to be removed , to make a graph disconnected . that means . edge connectivity should be ;less than equal to  min degree edges.

edge connectivity = k (min degree) < = 2e/v

so the number of edges in such graph will be atleast  (n*k)/2.
2 votes -- No Need ( 13.7k points)
In a directed graph, every vertex has exactly seven edges coming in. What can one always say about the number of edges going out of its vertices?

Exactly seven edges leave every vertex.

Exactly seven edges leave some vertex.

Some vertex has at least seven edges leaving it.

The number of edges coming out of vertex is odd.

None of the above.
The $2^n$  vertices of a graph G corresponds to all subsets of a set of size $n$, for $n \geq 6$.  Two vertices of G are adjacent if and only if the corresponding sets intersect in exactly two elements.
The number of vertices of degree zero in G is:

$1$

$n$

$n + 1$

$2^n$
Prove that in finite graph, the number of vertices of odd degree is always even.
Show that all vertices in an undirected finite graph cannot have distinct degrees, if the graph has at least two vertices.

The $2^n$  vertices of a graph G corresponds to all subsets of a set of size $n$, for $n \geq 6$.  Two vertices of G are adjacent if and only if the corresponding sets intersect in exactly two elements.

The maximum degree of a vertex in G is:

  1. $\binom{n/2}{2}2^{n/2}$
  2. $2^{n-2}$
  3. $2^{n-3}\times 3$
  4. $2^{n-1}$

In a graph, the degree of a vertex is the number of edges incident (connected) on it. Which of the following is true for every graph $G$?

  1. There are even number of vertices of even degree.
  2. There are odd number of vertices of even degree.
  3. There are even number of vertices of odd degree.
  4. There are odd number of vertices of odd degree.
  5. All the vertices are of even degree.

An undirected graph has 10 vertices labelled $1, 2, ..... , 10$ and 37 edges. Vertices 1, 3, 5, 7, 9 have degree 8 and vertices 2, 4, 6, 8 have degree 7. What is the degree of vertex 10?

  1. 5
  2. 8

Which one of the following is TRUE for any simple connected undirected graph with more than $2$ vertices?

  1.    No two vertices have the same degree.
  2.    At least two vertices have the same degree.
  3.    At least three vertices have the same degree.
  4.    All vertices have the same degree.
$G$ is an undirected graph with $n$ vertices and $25$ edges such that each vertex of $G$ has degree at least $3$. Then the maximum possible value of $n$ is _________ .

A graph $G=(V,E)$ satisfies $|E| \leq 3 |V| - 6$. The min-degree of $G$ is defined as $\min_{v\in V}\left\{degree (v)\right \}$. Therefore, min-degree of $G$ cannot be

  1. 3
  2. 4
  3. 5
  4. 6
Which of the following statements is/are TRUE for undirected graphs?

P: Number of odd degree vertices is even.

Q: Sum of degrees of all vertices is even.

(A) P only (B) Q only (C) Both P and Q (D) Neither P nor Q

Answers: Degree Of Graph

Selected Answer
Since 7 edges come to every vertex, total no. of edges leaving $n$ vertices must be $7n$. So, option a is a possibility but it needn't be always true. We can have 8 edges leave one vertex and 6 edges leave another (and similarly any other combination of outgoing edges ensuring total no. of outgoing edges remain constant). But option c must always be true as if none of the $n$ vertices have at least 7 edges leaving, sum of outgoing edges can never be $7n$.
8 votes -- Arjun Suresh ( 286k points)
Let $n$ be the number of vertices.

Total number of incoming edges $= 7 \times n$.

This should be equal to the total number of outgoing edges. So, either all vertices must have 7 edges leaving or some should have more than 7 leaving while others could have less than 7 leaving. But, it is guaranteed that some vertex will have at least 7 vertices leaving it.

So, (c) is the correct answer.

Only if we restrict $n$ to 8, exactly seven edges need to leave every vertex.
8 votes -- Arjun Suresh ( 286k points)
Selected Answer
C. no. of vertices with degree zero = no. of subsets with size <= 1  = n+1, as edges are there for every vertex with two or more elements as we have a vertex for all subsets of n.
14 votes -- Vikrant Singh ( 13.4k points)
There is one-one correspondence here.

Given that each vertex in a graph G corresponds to subset of a set S (let) with n elements.
We know there are 2^n subsets, for the set S with size n. right.
So is the graph, ie it contains 2^n vertices.(Obvious)

We also know out of all subsets of set S, there are 'n' subsets with only one elements, right. ------ (note - 1)
And a subset with empty set.(phi) ----- (note - 2)

So they both cannot be adjacent to any other vertex, right.
So their degrees are zero  which means they are isolated vertices.

So there are n + 1 isolated vertices in the Graph with given condition (from note-1 and note-2) , right!
Hence n+1 vertices with degree 0

@arjun sir , is it a correct approach ?
2 votes -- pC ( 20.7k points)
Selected Answer
In any finite graph,

Sum of degree of all the vertices = 2* number of egdes

sum of degree of all the verices with even degree + sum of degree of all the verices with odd degree = 2* number of egdes

even number  + sum of degree of all the verices with odd degree = even number

It is possible iff Numbe of odd degree vertices are even.
7 votes -- suraj ( 5k points)
Selected Answer
Let n >2 and all the vertices have distinct degrees. Now, let the degrees be 0, 1, 2, ...n-1 which are all distinct and possible as a vertex can be connected to n-1 other vertices. But, there is a problem here- if a vertex is connected to n-1 other vertices, it means there cannot be a vertex with 0 degree any more. Thus for n vertices we now have only n-1 possible degrees meaning at least one must repeat- pigeon comes here :)
13 votes -- Arjun Suresh ( 286k points)

Let us assume a graph with $n>2$ vertices exists and it is such that each of its vertex is assigned a distinct degree.

To assign each vertex a distinct degree we need a set of n numbers.

We cannot start count from $1$, coz then it will go up to vertex degree $n$ but the graph is a simple graph and it rules out the possibility to have self loops and parallel edges; Without them a vertex with degree n is not possible.

so we have a n-element set = [0,n-1]

a vertex with a degree $0$ means that one of the vertex is disconnected 
a vertex with a degree $n-1$ means that a vertex is connected to every other n-1 vertices.

Both statements cannot be true simultaneously.

This means that our assumption is Wrong and such a graph cannot exist. 

2 votes -- Amar Vashishth ( 27.9k points)
Selected Answer
C. $\max_k ({}^kC_2.2^{n-k}) = {}^3C_2 . 2^{n-3} = 3.2^{n-3}$.

Let the vertex having the max degree contain k elements. Now, as per the given condition, it can have edges to all vertices having two common elements (exactly 2 common). So, we can choose the 2 common elements in ${}^kC_2$ ways. Now, for each of these 2 pair of elements, it can have an edge to a vertex containing $n-k$ elements + the 2 common elements. This will be equal to $2^{n-k}$ possible subsets as the 2 common elements must always be present and other k elements must always be absent. So, we get the degree as

${}^kC_2 . 2^{n-k}$

Now, our answer will be the maximum value for this. We can differentiate this (w.r.t k) and equate to 0. But in other way we can try different values for $k$ starting with 2. As we see if we increase $k$ from 2 on wards, the $2^{n-k}$ term gets divided by 2. The other term is ${}^kC_2$, which goes like $1, 3, 6, 10 \dots$ for $k = 2, 3, 4, 5, \dots$. So, we get the max. degree for $k = 3$ or $4$ and this will be $3 . 2^{n-3}$.
14 votes -- Vikrant Singh ( 13.4k points)
Selected Answer

As we know that sum of degree of vertex = 2*edges 
let there are u vertex with odd degrees and v vertex with even degrees 

Then ∑(u) + ∑(v) = 2e

now 2e = even 
 ∑(v) = sum of even number will be even 
∑(u) = if you consider odd number of vertices of odd degree then sum will be odd and this will violate 2e
          so there will be always even number of vertices with odd degree 

C)There are even number of vertices of odd degree

 

6 votes -- Umang Raman ( 14.4k points)
Selected Answer

Vertices 1, 3, 5,7, 9 have degree 8 and vertices 2, 4, 6, 8 have degree 7.

We knows Sum of degree= 2 * No of edges
 
Let X = degree of vertex 10

8 + 7 + 8 + 7 + 8 + 7 + 8 + 7 + 8 + X =  2 * 37

68 + X =74

X=6

Hence,Degree of vertex 10 is 6.

Hence,Option (B)6 is the correct choice.

3 votes -- Leen Sharma ( 31.3k points)
Selected Answer

answer = option B

There are n vertices and at least n-1 edges. So, for each vertex, degree should range from 1 (since graph is connected) to n-1 (since graph is simple). But we have n such vertices- filling n things with n-1 numbers. $$\bigg \lceil \frac{n}{n-1} \bigg\rceil = \lceil 1.\sim \rceil = 2$$ So, at least 2 of them must be equal (pigeonhole principle).

16 votes -- gatecse ( 13k points)
Selected Answer
Let $m$ be mindegree and $M$ be maxdegree of a graph, then $\color{navy}{m \le \frac{2E}{V} \le M}$

$m = 3, E = 25, V = ...?$

So, $3 \le \frac{2*25}{V}$

$V\le \frac{50}{3}$

$V \le 16.667 \color{maroon}{\Rightarrow V = 16}$
16 votes -- Manish Joshi ( 25k points)
k.V<=2E

so,3V<=2*25=$\left \lfloor 50/3 \right \rfloor =16$

Ans:16
2 votes -- Arnabi ( 6k points)
Selected Answer

say every vertex has a minimum degree, therefore, least number of edges that will be in the graph is given by the handshaking lemma as = $\frac{min \times |v|}{2}$

but the maximum number of edges for such a graph is defined in the question as $3\times |v| - 6$

putting the minimum number of edges obtained by handshaking lemma in the given inequality, we get:$$\begin{align*} \frac{min \times |v|}{2} &\leq 3\times |v| - 6 \\ \frac{6 \times |v|}{2} &\leq 3\times |v| - 6 \qquad \text{;putting min degree as 6}\\ 3 \times |v| &\leq 3\times |v| - 6 \\ 0 &\leq - 6 \\ \end{align*}$$

which is definitely inconsistent.

Hence, answer = option D

14 votes -- Amar Vashishth ( 27.9k points)
Let the min-degree of G is x. then G has at least |v| *x/2 edges.

|v|*x/2 <= 3* |v| -6

for x=6, we get 0 <= -6, Therefore, min degree of G cannot be 6.

Correct answer is (D).

alternative approach ,
let the min_degree of a graph is 'x' , then

                   x <= (2e / n) ,
given  , e <= (3n - 6)          { it will be planner graph}
put the value of e , then min_degree will be ,

                 x <= (2(3n-6))/n

                 x <= (6n - 12) / n
                x <=( 6n/n - 12/n )

                x <= ( 6 - 12/n) ,
 when number of vertices is more , then value of (12/n) will be less , ( 12/n = 0.000001 assume) , then min_degree will be ,
                        x <= (6 - 0.000001)
                        x <= 5.999999  , max value
                        x < = floor value (5.9999999....)
                        x = 5 , maximum value of min_degree of defined graph (i.e. planner graph)
13 votes -- suraj ( 5k points)
Selected Answer
Both are correct

P:sum of odd degree + sum of even degree=2*no of edges

sum of odd degree=2*no of edges - sum of even degree

The right hand side must be even as the difference of 2 even numbers is always even.

Q:each edge is counted twice so sum of degree is always even
17 votes -- Bhagirathi Nayak ( 13.1k points)

Which of the following graphs has an Eulerian circuit?

  1. Any $k$-regular graph where $k$ is an even number.
  2. A complete graph on 90 vertices.
  3. The complement of a cycle on 25 vertices.
  4. None of the above

Answers: Euler Graph

Selected Answer

A connected Graph has Euler Circuit $\iff$ all of its vertices have even degree
A connected Graph has Euler Path $\iff$ exactly 2 of its vertices have odd degree

(a) k-regular graph where k is even number. 
a k-regular graph need not be connected always. Example : The given below graph is a $2$ regular graph is not a Euler graph. This is so because there is no single walk which covers all edges.

(b) the complete graph of $90$ vertices
In such a graph every vertex will have an odd degree = 89, Hence it cannot have a Euler path/Circuit.

(c) to get degree of all vertices of the complement of cycle on 25 vertices we need to subtract the degree of a complete graph of 25 vertices with degree of vertices in the original given graph i.e. cycle on 25 vertices.

Degree of complement $= 24 - 2 = 22$. Since, every degree is Even, and it is connected also, therefore Graph has a Euler Cycle.

It is connected because, there is a theorem which says, "$G$ be a graph with $n$ vertices and if every vertex has a degree of at least $\frac{n-1}{2}$ then $G$ is connected." [check this]

Here Degree of each vertex is $22$, which is of course greater that $\frac{25-1}{2}\left (=12 \right )$.

answer = Option C

28 votes -- Mithlesh Upadhyay ( 5.3k points)

Option is C

A) does not confirm that regular graph should be connected or not.

B)Degree of the each vertices will be 89 since it is complete graph.

C)The complement of the cycle graph with 25 graph where the degree of each vertex will be 24(even) so according to the theorem for the existence of Euler's circuit all the vertices should be of even degree  

3 votes -- Prajwal Bhat ( 11.6k points)

The minimum number of colours required to colour the vertices of a cycle with $n$ nodes in such a way that no two adjacent nodes have the same colour is

  1. $2$
  2. $3$
  3. $4$
  4. $n-2 \left \lfloor \frac{n}{2} \right \rfloor+2$
The minimum number of colours that is sufficient to vertex-colour any planar graph is ________.

A vertex colouring with three colours of a graph $G=(V, E)$ is a mapping $c: V \rightarrow \{R, G, B\}$ so that adjacent vertices receive distinct colours. Consider the following undirected graph.

How many vertex colouring with three colours does this graph have?

  1. $3^9$
  2. $6^3$
  3. $3 \times 2^8$
  4. $27$
  5. $24$

Let $G= (V, E)$ be a simple undirected graph on $n$ vertices. A colouring of $G$ is an assignment of colours to each vertex such that endpoints of every edge are given different colours. Let $\chi (G)$ denote the chromatic number of $G$, i.e. the minimum numbers of colours needed for a valid colouring of $G$. A set $B\subseteq V$ is an independent set if no pair of vertices in $B$ is connected by an edge. Let $a(G)$ be the number of vertices in a largest possible independent set in $G$. In the absence of any further information about $G$ we can conclude.

  1. $\chi (G)\geq a(G)$
  2. $\chi (G)\leq   a(G)$
  3. $a(G)\geq n/\chi (G)$
  4. $a(G)\leq  n/\chi (G)$
  5. None of the above.

Consider the undirected graph $G$ defined as follows. The vertices of $G$ are bit strings of length $n$. We have an edge between vertex $u$ and vertex $v$ if and only if $u$ and $v$ differ in exactly one bit position (in other words, $v$ can be obtained from $u$ by flipping a single bit). The ratio of the chromatic number of $G$ to the diameter of $G$ is

  1. 1/(2n-1)
  2. 1/n
  3. 2/n
  4. 3/n

A vertex colouring of a graph $G=(V, E)$ with $k$ coulours is a mapping $c: V \rightarrow \{1, \dots , k\}$ such that $c(u) \neq c(v)$ for every $(u, v) \in E$. Consider the following statements:

  1. If every vertex in $G$ has degree at most $d$ then $G$ admits a vertex coulouring using $d+1$ colours.
  2. Every cycle admits a vertex colouring using 2 colours
  3. Every tree admits a vertex colouring using 2 colours

Which of the above statements is/are TRUE? Choose from the following options:

  1. only i
  2. only i and ii
  3. only i and iii
  4. only ii and iii
  5. i, ii, and iii

The minimum number of colours required to colour the following graph, such that no two adjacent vertices are assigned the same color, is

  1. 2
  2. 3
  3. 4
  4. 5

Answers: Graph Coloring

Selected Answer
Chromatic number will be 3 for when n is odd and will be 2 when n is even. Option (d) is a representation for this, hence the correct answer
14 votes -- Madhur Rawat ( 2.6k points)
Selected Answer

Four colour theorem is famous result, it says that any planar graphs can be coloured with only 4 colours !

Ref -> https://en.wikipedia.org/wiki/Four_color_theorem

 

Note for confused people => laugh

 
Here ANY is used in sense of FOR ALL x , so , here ANY means literally any one of graph can be selected !

What are you saying , is something like There exists, but in that case, they will say, That specific graph directly..

Any man alive is gonna die => This means all men are gonna die ! Not specific to anyone !
Hope this clears thing a bit !
18 votes -- Akash ( 41.5k points)
According to four color theorem, Every planar graph can be colored using 4 colors.
4 votes -- Sharathkumar Anbu ( 717 points)
Selected Answer

Start with the Inner one which can be filled in => $3 * 2 * 1 = 6$ ways

Then, middle one can be filled in => $2 * 1 * 1 = 2$ ways

Then, similarly outermost can be filled in => $2 * 1 * 1 = 2$ ways


Hence, Total number of ways to fill this figure => $6 * 2 * 2 = 24$ ways

14 votes -- Kapil Phulwani ( 47.4k points)
Selected Answer

Independence number : Size of largest maximum independent set. a(G) (it covers all adjacent vertices)
Chromatic Number : Minimum No. of color required to properly color the graph .χ(G)

 
The vertices of G can be partitioned into χ(G) monochromatic classes. Each class is an independent set, and hence cannot have size larger than α(G)

α(G) χ(G)  n (its a theorem)
option C

 
5 votes -- Umang Raman ( 14.4k points)
Selected Answer

Answer is (C)

For the given condition we can simply design a K-MAP and mark an edge between every two adjacent cells in K-Map.(adjacency has to seen just as we do for minimization )

That will give us a Bipartite graph. chromatic number for this =2

Also from the same we can conclude that we need ,for a 'n' bit string, to traverse NO MORE than (n-1) edges or 'n' vertices to get a path b/w two arbitrary points.

So ratio is 2/n.

The given graph is actually hypercubegraph. 

https://en.wikipedia.org/wiki/Hypercube_graph

See problem 4 here:
http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-spring-2005/assignments/pset5_soln.pdf

11 votes -- Sandeep_Uniyal ( 7.3k points)
Answer better explained here :http://gateoverflow.in/38185/haming-distance-and-chromatic-number
3 votes -- pC ( 20.7k points)
Selected Answer
i is true, since in worst case the graph can be complete. So, d+1 colours are necessary for graph containing vertices with degree atmost 'd' .

ii is false since cyles with odd no of vertices require 3 colours.

iii is true, since each level of the tree must be coloured in an alternate fashion. We can do this with two colours.

Therefore, option c is correct.
2 votes -- tarun_svbk ( 1k points)
Selected Answer

4 colors are required to color the graph in the prescribed way.

answer = option C

9 votes -- Amar Vashishth ( 27.9k points)

Ans C 

2 votes -- Anu ( 10.2k points)

The maximum number of edges in a n-node undirected graph without self loops is

  1. $n^2$
  2. $\frac{n(n-1)}{2}$
  3. $n-1$
  4. $\frac{(n+1)(n)}{2}$

In a connected graph, a bridge is an edge whose removal disconnects the graph. Which one of the following statements is true?

 

  1. A tree has no bridges
  2. A bridge cannot be part of a simple cycle
  3. Every edge of a clique with size ≥ 3 is a bridge (A clique is any complete subgraph of a graph)
  4. A graph with bridges cannot have cycle

Let G be a directed graph whose vertex set is the set of numbers from 1 to 100. There is an edge from a vertex i to a vertex j iff either j = i + 1 or j = 3i. The minimum number of edges in a path in G from vertex 1 to vertex 100 is

  1. 4
  2. 7
  3. 23
  4. 99

What is the number of vertices in an undirected connected graph with 27 edges, 6 vertices of degree 2, 3 vertices of degree 4 and remaining of degree 3?

  1. 10
  2. 11
  3. 18
  4. 19

What is the maximum number of edges in an acyclic undirected graph with n vertices?

  1. n-1
  2. n
  3. n+1
  4. 2n-1

If all the edge weights of an undirected graph are positive, then any subset of edges that connects all the vertices and has minimum total weight is a

  1. Hamiltonian cycle
  2. grid
  3. hypercube
  4. tree

Let $G=(V, E)$ be a graph. Define $\bar{G}$ to be $(V, \bar{E})$, where for all $u, \: v \: \in V \: , (u, v) \in \bar{E}$ if and only if $(u, v) \notin E$. Then which of the following is true?

  1. $\bar{G}$ is always connected.
  2. $\bar{G}$ is connected if $G$ is not connected.
  3. At least one of $G$ and $\bar{G}$ connected.
  4. $G$ is not connected or $\bar{G}$ is not connected

G is a simple undirected graph. Some vertices of G are of odd degree. Add a node v to G and make it adjacent to each odd degree vertex of G. The resultant graph is sure to be

  1. regular
  2. complete
  3. Hamiltonian
  4. Euler
The minimum number of edges in a connected cyclic graph on $n$ vertices is:

(a) $n-1$
(b) $n$
(c) $n+1$
(d) None of the above

Consider a simple connected graph $G$ with $n$ vertices and $n$ edges $(n > 2)$. Then, which of the following statements are true?

  1. $G$ has no cycles
  2. The graph obtained by removing any edge from $G$ is not connected
  3. $G$ has at least one cycle
  4. The graph obtained by removing any two edges from $G$ is not connected
  5. None of the above 
Consider an undirected graph $G$ where self-loops are not allowed. The vertex set of $G$ is $\{(i,j) \mid1 \leq i \leq 12, 1 \leq j \leq 12\}$. There is an edge between $(a,b)$ and $(c,d)$ if $|a-c| \leq 1$ and $|b-d| \leq 1$. The number of edges in this graph is______.
For a positive integer n, let G = (V, E) be a graph, where V = {0,1}^n, i.e., V is the set of vertices has one to one correspondence with the set of all n-bit binary strings and E = {(u,v) | u, v belongs to V, u and v differ in exactly one bit position}.

i) Determine size of E

ii) Show that G is connected

Answers: Graph Connectivity

Selected Answer
In a graph of n vertices you can draw an edge from a vertex to n-1 vertex we will do it for n vertices so total number of edges is n(n-1) now each edge is counted twice so the required maximum number of edges is n(n-1)/2
17 votes -- Bhagirathi Nayak ( 13.1k points)

For maximum no of edges we must have one edge for each pair of vertices.

We can select a pair out of N nodes in NC2 ways = N(N-1)/2

4 votes -- Debashish Deka ( 48k points)
Selected Answer
Ans B

In a cycle if we remove an edge, it will still be connected. So, bridge cannot be part of a cycle.
20 votes -- Vikrant Singh ( 13.4k points)
Ans B- bridge cannot be part of a simple cycle
2 votes -- Deepak ( 187 points)
Selected Answer

The conditions are given

Edge set consists of edges from i to j using either 
1) j = i+1 OR
2) j=3i

what we think from here 

minimum we take vertex 1 max we take vertex 100 

now one important point is to reach 100 the maximum no. which get   j=3i is i= 33 so j= 3*3= 99

half problem is solved.

we got 1--33--99--100

now see to reach 33 how many minimum edge needed.

max no between which get value j= 3i, i= 11 so j= 3*11= 33

what we get  1--11--33--99--100

so problem solved almost minimum edge need to reach 11 from 1

max no. i which get j= 3i, i= 3 so j= 3*i =9 to reach 11 ..9--10--11

so we got another point

1--9--10--11--33--99--100

now to reach 11 from 1

max value of i = 3 so j= 3*i= 9 so 3--9

1--3--9--10--11--33--99--100

 

 

Solved problem into half give u idea how to get minimum for rest of graph.

 

12 votes -- Prashant Singh ( 47.5k points)

Edge set consists of edges from i to j using either 
1) j = i+1 OR
2) j=3i.
Second option will help us reach from 1 to 100 rapidly. 

The trick to solve this question is to think in reverse way. Instead of finding a path from 1 to 100, try to find a path from 100 to 1.

The edge sequence with minimum number of edges is 1 - 3 - 9 - 10 - 11 - 33 - 99 - 100 which consists of 7 edges. 
The answer is option 2.

23 votes -- Shridhar ( 313 points)
Selected Answer
sum of degree of all the vertices = 2 * number of edges

2*6 + 4*3 + 3*x = 27*2

x=10.

Number of vertices = 6 + 3 +x = 19
The correct answer is (D).
13 votes -- suraj ( 5k points)
Selected Answer

This is possible with spanning tree. 

A spanning tree with n nodes has n-1 edges.

Therefore, Answer is (A)

10 votes -- Dhananjay ( 967 points)
Selected Answer

A) Hamiltonian cycle -> This is cycle guys. Cycle will not only connect all vertices, it will have 1 extra edge than necessary. So I can just remove that edge & get better cost "subset of edges" which connect all vertices. So this is false.

B) grid -> This is unrelated concept. This is false.

ref-> https://en.wikipedia.org/wiki/Electrical_grid

C) Hypercube -> This is also unrelated concept. Also it have cycles too..This is false.

D) Tree -> This is answer. We need to have Minimum spanning Tree to be exact.

Ref -> https://en.wikipedia.org/wiki/Minimum_spanning_tree

"If all the edge weights of an undirected graph are positive, then any subset of edges that connects all the vertices and has minimum total weight is a Minimum Spanning Tree". !

D is true.

12 votes -- Akash ( 41.5k points)

I think it is (D)

5 votes -- Sandeep_Uniyal ( 7.3k points)
Selected Answer

Correct answer would be C) At least one of G and G-bar is connected.

Option A: Its straight forwardly wrong.

Option B: This is a subset of Option C.

Option D: This also implies that G and G-bar is not connected at the same time, which is impossible

Here is the total Possibility

     G                                             G-bar                          Possible/Not-Possible

Connected                                 Connected                             Possible

Connected                               Dis-connected                          Possible

Dis-Connected                            Connected                             Possible

Dis - Connected                       Dis-Connected                         Not-Possible

6 votes -- Muktinath Vishwakarma ( 33.9k points)
Selected Answer
In any simple undirected graph, total degree of all vertices is even (since each edge contributes 2 degrees). So number of vertices having odd degrees must be even, otherwise their sum would have been odd, making total degree also odd.

Now Single vertex v is connected to all these even number of vertices (which have odd degrees). So degree of v is also even. Moreover, now degree of all vertices which are connected to v is increased by 1, hence vertices which had odd degree earlier now have even degree.

So now, all vertices in graph have even degree, which is necessary and sufficient condition for euler graph. So D) is correct.
19 votes -- Happy Mittal ( 10.7k points)
Selected Answer
B.

For making a cyclic graph, the minimum number of edges have to be equal to the number of vertices.
16 votes -- Gate Keeda ( 18.8k points)
Selected Answer

ARTICULATION POINT: are those points whose removal from the graph makes the graph disconnected.!! 

here if we remove the vertex no 2 than we get disconnected graph.

similarly if we remove the vertex no 3 than we get disconnected graph.

similarly if we remove the vertex no 5 than we get disconnected graph.

So, D choice. 

13 votes -- kunal ( 20.3k points)
Answer: D

The articulation points are 2,3,5.
5 votes -- Rajarshi Sarkar ( 34.3k points)
Selected Answer

This seems like multiple answer questions.

Here we have n vertices & n edges. So we must have cycle.

So C) has at least one cycle is True & A) is false.

D) The graph obtained by removing any two edges from G is not connected -> This is true, for graph of n vertices to be connected, we need at least n-1 edges. If we remove 2 out of n, we get n-2 edges, which can connect at max n-1 vertices. 1 Vertex at least will be disconnected. So D is true.

B) B is false as if graph is cyclic graph then removing any edge will not disconnect graph.

ANswer -> C & D.

 

7 votes -- Akash ( 41.5k points)
if there are n vertices if you want to make it as a connected graph , there should be at least n-1 edges. hence if we remove two edges, it wont be a connected graph hence answer :d
3 votes -- Sankaranarayanan P.N ( 11k points)
Selected Answer
Maximum no. of edges occur in a complete bipartite graph i.e. when every vertex has an edge to every opposite vertex.

Number of edges in a complete bipartite graph is mn, where m and n are no. of vertices on each side. This quantity is maximum when m = n i.e. when there are 6 vertices on each side, so answer is 36.
18 votes -- Happy Mittal ( 10.7k points)
in a bipartite graph all the vertices can be distributed in two sets .let the set-1 has M vertices and set-2 has N vertices.

as  M+N=12     

total no of edges =MN =M(12-M)   

take the derivative of this  equation  with respect to M.

d(total no of edges)/d(M)= 12-2M

second order derivative is negative so this function will attain maximum value at 12-2M=0

so M=6

and N=6

total no of edges = MN= 36.
5 votes -- preetam ( 137 points)
Selected Answer
If you think of a 12 * 12 grid (like a chess board of size 12*12), then each each point (i,j), which is in ith row and jth column, is a vertex (i,j).

Now we are allowed to connect only those points which are atmost 1 distance apart (in both horizontal and vertical direction). So we will connect only horizontal neighbours, vertical neighbours, and diagonal neighbours.

So horizontal edges on each row are 11 i.e. 11*12 = 132 horizontal edges. Similarly we have 132 vertical edges.

To count diagonal edges, think of 1*1 square boxes in which diagonals meet each other. There are 11*11 such square boxes, and each box contains 2 diagonals, so total diagonals = 242.

So total edges = 132 + 132 + 242 = 506.
60 votes -- Happy Mittal ( 10.7k points)

Total number of vertices $= 12*12 = 144.$

The graph formed by the description contains $4$ (corner) vertices of degree $3$ and $40$ (external) vertices of degree $5$
and  $100$ (remaining) vertices of degree $8.$

 According to (handshake theorem's) 

$2|E|=$ sum of the degrees

$ 2|E| = 4*3+40*5+100*8= 1012$ 

$|E| = 1012/2 = 506$  edges.

32 votes -- Mithlesh Upadhyay ( 5.3k points)
These types of graphs are also known as hypercube graphs.

Part i:

Consider any vertex $v$. Exactly $n$ vertices have a hamming distance of $1$ from $v$. (Reason: Consider the vertex which is exactly the same bit pattern as $v$ except the first bit as $v_1$.     $v_2$ differs from $v$ in only the 2nd bit and so on till $v_n$ which is different from $v$ in last bit).

Now there are total of $2^n$ vertices (Since each vertex corresponds to a bit string and for n bits there are $2^n$ bit strings.).

Consider the basic theorem for undirected graphs which says that sum of degrees of vertices is equal to twice the no. of edges.

Using that here we get:

$2^n*n = 2*e$ where $e$ is the no. of edges.

Thus no. of edges = $2^{n-1}n$

Part ii)

A graph is called connected if there's a path between any two vertices.

Consider any vertices $v_x$ and $v_y$. Suppose hamming distance between them is $k$. Consider the first different bit $k_1$. You simply reach $v_{k1}$ from $v_x$  which differs from $v_x$ only in that bit. Now $v_{k1}$ and $v_y$ differ from each other by $k-1$ bits. You continue to do this until you reach $v_y$. Thus any two vertices are connected by a path of $k$ where $k$ is the hamming distance between them.
2 votes -- Akshay Arora ( 2.2k points)

Answers: Graph Isomorphism

Selected Answer

for this type of questions find which are not isomorphic

The graph in option A has a 3 length cycle whereas the original graph does not have a 3
length cycle
The graph in option C has vertex with degree 3 whereas the original graph does not have a
vertex with degree 3

The graph in option D has a 4 length cycle whereas the original graph does not have a 4
length cycle

so option B is correct

11 votes -- Bhagirathi Nayak ( 13.1k points)
Selected Answer

its n=5 only.

only C5 is isomorphic to its complement.

16 votes -- jayendra ( 7.7k points)

No of edges in graph + no of edges in complement of graph = n(n-1)/2  // No Of edges in complete graph of N vertices

5 + 5 = n(n-1)/2 // Here in C5 edges are there and in isomorphic graph the no of edges should be equal to no of edges in graph.

so solving it we get n = 5 .

16 votes -- Hardi Shah ( 329 points)

How many perfect matching are there in a complete graph of $6$ vertices?

  1. 15
  2. 24
  3. 30
  4. 60

Answers: Graph Matching

Selected Answer
Perfect matching is a set of edges such that each vertex appears only once and all vertices appear at least once (EXACTLY one appearance). So for $n$ vertices perfect matching will have $n/2$ edges and there won't be any perfect matching if n is odd.

For $n = 6$, we can choose the first edge in ${}^6C_2=15$ ways, second in ${}^4C_2= 6$ ways and third in ${}^2C_2 = 1$ way. So, total number of ways $= 15\times 6=90$. But perfect matching being a set, order of elements is not important. i.e., the $3!$ permutations of the $3$ edges are same only. So, total number of perfect matching $= 90/3!= 90/6 = 15$.

Alternatively we can also say there are 3 identical buckets to be filled from 6 vertices such that 2 should go to each of them. Now the first vertex can combine with any of the other 5 vertices and go to bucket 1- 5 ways. Now only 4 vertices remain and 2 buckets. We can take one vertex and it can choose a companion in 3 ways and go to second bucket- 3 ways. Now only a single bucket and 2 vertices remain- so just 1 way to fill the last one. So total ways=5*3=15.
20 votes -- Arjun Suresh ( 286k points)

Note: To understand the solution please go through the definitions of perfect matching

The complete graph kn have a perfect matching only when n is even.. So let n=2m. 

Let the vertices be V1 , V2 ,......,V2m.    

v1 can be joined to any other 2m-1 vertices

v2 can be joined to any other 2m-3 vertices

Similarly go till V2m which will have only one vertex to be joined with..

No of Perfect matches= (2m-1)(2m-3)(2m-5).....(3)(1)

In the above question 2m=6

So No. of perfect matches=5*3*1=15

14 votes -- Hunaif ( 485 points)

Answer the following:

Which of the following graphs is/are planner? (see Fig. 2)

Answers: Graph Planarity

Selected Answer
graph G2 is planar because we can draw all its edges without crossing each other .
2 votes -- kunal ( 20.3k points)
Let $G$ be a group with $15$ elements. Let $L$ be a subgroup of $G$. It is known that $L \neq\ G$ and that the size of $L$ is at least $4$. The size of $L$ is __________.

Answers: Groups

Selected Answer

Lagranges theorem : For any finite group G, the order (number of elements) of every subgroup L of G divides the order of G.
G has 15 elements.
Factors of 15 are 1,3,5, and 15.
Since given the size of L is atleast 4(1 and 3 eliminated) and not equal to G(15 eliminated) , the only size left is  5.

Size of L is 5.


 

27 votes -- Srinath Jayachandran ( 3.7k points)

The degree sequence of a simple graph is the sequence of the degrees of the nodes in the graph in decreasing order. Which of the following sequences can not be the degree sequence of any graph?

  1. 7, 6, 5, 4, 4, 3, 2, 1
  2. 6, 6, 6, 6, 3, 3, 2, 2
  3. 7, 6, 6, 4, 4, 3, 2, 2
  4. 8, 7, 7, 6, 4, 2, 1, 1
    1. I and II
    2. III and IV
    3. IV only
    4. II and IV

An ordered $n-$tuple $(d_1, d_2,....,d_n)$ with $d_1 \geq d_2 \geq ... \geq d_n$ is called graphic  if there exists a simple undirected graph with $n$ vertices having degrees $d_1,d_2,...,d_n$ respectively. Which one of the following 6-tuples is NOT graphic?

  1. $(1,1,1,1,1,1)$
  2. $(2,2,2,2,2,2)$
  3. $(3,3,3,1,0,0)$
  4. $(3,2,1,1,1,0)$

Answers: Havel Hakimi Theorem

Selected Answer

The answer is clearly D.

You can eliminate the last sequence i.e 4th one as... the total number of vertices is 8 and the maximum degree given is 8 too. which isn't possible at all. The maximum degree you can have out of 8 vertices is 7.

Now coming to the method for solving such questions is through Havel-Hakimi Algorithm.

you can implement it by following one simple video. Here it is. :)

11 votes -- Gate Keeda ( 18.8k points)
A degree sequence d1,d2,d2. . . dn of non negative integer is graphical if it is a degree sequence of a graph. We now introduce a powerful tool to determine whether a particular sequence is graphical due to Havel and Hakimi

Havel–Hakimi Theorem :

→ According to this theorem, Let D be sequence the d1,d2,d2. . . dn with d1 ≥ d2 ≥ d2 ≥ . . . dn for n≥ 2 and di ≥ 0.

→ Then D0 be the sequence obtained by:

→ Discarding d1, and
→ Subtracting 1 from each of the next d1 entries of D.
→ That is Degree sequence D0 would be : d2-1, d2-1, d3-1 . . . , dd1+1 -1 . . . , dn
→ Then, D is graphical if and only if D0 is graphical.

Now, we apply this theorem to given sequences:

option I) 7,6,5,4,4,3,2,1 → 5,4,3,3,2,1,0 → 3,2,2,1,0,0 → 1,1,0,0,0 → 0,0,0,0 so its graphical.

Option II) 6,6,6,6,3,3,2,2 → 5,5,5,2,2,1,2 ( arrange in ascending order) → 5,5,5,2,2,2,1 → 4,4,1,1,1,1 → 3,0,0,0,1 this type of graph can not possible  so its not a graphical.

Option III) 7,6,6,4,4,3,2,2 → 5,5,3,3,2,1,1 → 4,2,2,1,1,0 → 1,1,0,0,0 → 0,0,0,0 so its graphical.

Option IV) 8,7,7,6,4,2,1,1 , here degree of a vertex is 8 and total number of vertices are 8 , so it’s impossible, hence it’s not graphical.

Hence only option I) and III) are graphic sequence and answer is option-D
3 votes -- Madhab Paul Choudhury ( 4.8k points)
Selected Answer
This can be solved using havel-hakimi theorem.

The idea is simple : Remove a vertex, which results into decrease of degree by 1 of each vertex which was connected to it. Keep removing like this, and if we get any negative degree, the degree sequence was not possible.

We need not check (A) and (B) as they are clearly graphs : (A) is 3 disconnected edges, (B) is 2 disconnected triangles.

For (C), we remove first vertex of degree 3, and thus decrease degree by 1 of next 3 vertices, so we get (2,2,0,0,0), then we remove vertex of degree 2, and decrease degree of next 2 vertices to get (1,-1,0,0). Since we get negative degree, original degree sequence is impossible.

For (D) : (3,2,1,1,1,0) -> (1,0,0,1,0). Now since this list is not sorted (which is required to apply further steps of algorithm), we sort it to get (1,1,0,0,0). Then we continue our algorithm on this list to get (0,0,0,0), which is valid (4 isolated vertices).

So (C) is answer.
20 votes -- Happy Mittal ( 10.7k points)
The line graph $L(G)$ of a simple graph $G$ is defined as follows:

There is exactly one vertex $v(e)$ in $L(G)$ for each edge $e$ in $G$.

For any two edges $e$ and $e'$ in $G$, $L(G)$ has an edge between $v(e)$ and $v(e')$, if and only if $e$ and $e'$ are incident with the same vertex in $G$.

Which of the following statements is/are TRUE?
(P) The line graph of a cycle is a cycle.
(Q) The line graph of a clique is a clique.
(R) The line graph of a planar graph is planar.
(S) The line graph of a tree is a tree.

(A) P only

(B) P and R only

(C) R only

(D) P, Q and S only

Answers: Line Graph

Selected Answer

P)True. Because every edge in cycle graph will become a vertex in new graph L(G) and every vertex of cycle graph will become an edge in new graph.

R)False. We can give counter example. Let $G$ has 5 vertices and 9 edges which is a planar graph. Assume degree of one vertex is 2 and of all others are 4. Now,  $L(G)$ has 9 vertices (because $G$ has 9 edges ) and 25 edges. (See below). But for a graph to be planar |E| <= 3|V| - 6.

For 9 vertices |E| <= 3*9 - 6

⇒|E| <= 27 - 6

⇒|E| <= 21. But L(G) has 25 edges and so is not planar.

As R is False option B, C are eliminated.
http://www.personal.kent.edu/~rmuhamma/GraphTheory/MyGraphTheory/planarity.htm

S)False. By counter example. Try drawing a simple tree which has a Root node ,Root node has one child A, node A has two child B and C. Draw its Line graph acc. to given rules in question you will get a cycle graph of 3 vertices.

So D) also not correct.

∴ option A is correct.


For a graph G with n vertices and m edges, the number of vertices of the line graph L(G) is m, and the number of edges of L(G) is half the sum of the squares of the degrees of the vertices in G, minus m.

18 votes -- prashant singh ( 455 points)
Let G be a complete undirected graph on 6 vertices. If vertices of G are labeled, then the number of distinct cycles of length 4 in G is equal to

(A) 15 (B) 30 (C) 90 (D) 360

Answers: Permutation

Selected Answer

From 6 vertices we can select 4 distinct vertices in 6C4 = 15 ways. 
Now, with 4 vertices, we can form only 3 distinct cycles. [See below]
So, total no. of distinct cycles of length 4 = 15 * 3 = 45.

No. of cyclic permutations of n objects = (n-1)! and for n = 4, we get 3! = 6 ways. But number of distict cycles in a graph is exactly half the number of cyclic permutations as there is no left/right ordering in a graph. For example a - b - c - d and a - d - c - b are different permutations but in a graph they form the same cycle. 

Since, 45 was not in the choice, marks were given to all in GATE. 

42 votes -- gatecse ( 13k points)

Answer would be 6C4 * 4! /(4*2) =45

Explanation:

Number of ways to choose 4 vertices = 6C4
Total number of cycles from a particular set of 4 vertices = 4!/(4*2) (sice the same cycle can start from different vertices and go in both directions)

7 votes -- suraj ( 5k points)
The number of edges in a regular graph of degree d and n vertices is ____________

Answers: Regular Graph

Selected Answer
in a complete graph which is (n-1) regular (where n is the no of vertices) has edges n(n-1)/2
n vertices are adjacent to n-1 vertices and an edge contributes two degree so dividing by 2.

so in d regular graph No of edges will be n*d/2
8 votes -- Manu Thakur ( 5.8k points)

Let $K_{n}$ be the complete graph on $n$ vertices labelled $\left\{1, 2,\dots ,n\right\}$ with $m= n (n - 1)/2$ edges. What is the number of spanning trees of $K_{n}$?

  1. $\frac{m}{n - 1}$
  2. $m^{n - 1}$
  3. $n^{n - 2}$
  4. $n^{n - 1}$
  5. None of the above.

What is the largest integer m such that every simple connected graph with n vertices and n edges contains at least m different spanning trees ?

  1. 1
  2. 2
  3. 3
  4. n

Answers: Spanning Tree

Selected Answer

Answer will be (C) 

e.g. for K4 no. of spanning tree will be 16

2 votes -- srestha ( 54.8k points)
Selected Answer

OPTION (C) is Correct , reason is as follows:

Graph is connected and has 'n' edges   means   exactly one cycle is there , if n vertices are there.

Now we can make a different spanning tree by removing one edge from the cycle, one at a time.

Minimum cycle length can be 3 , So, there must be atleast 3 spanning trees in any such Graph. 

1

Consider this Graph ,Here n = 4 and three spanning trees possible at max (removing edges of cycle one at a time, alternatively).

So, any such Graph with minimum cycle length '3' will have atleast 3 spanning trees.

23 votes -- Himanshu Agarwal ( 15.9k points)
ans :D

starting from 3 vertices only we can do 3 edges so atleast 3 spanning trees
6 votes -- rajsh3kar ( 1.2k points)

Which of the following is NOT a sufficient and necessary condition for an undirected graph $G$ to be a tree?

  1. $G$ is connected and has $n -1$ edges.
  2. $G$ is acyclic and connected.
  3. $G$ is acyclic and has $n - 1$ edges.
  4. $G$ is acyclic, connected and has $n - 1$ edges.
  5. $G$ has $n - 1$ edges.

Let $G=(V, E)$ be a graph. Define $\xi(G) = \sum\limits_d i_d*d$, where $i_d$ is the number of vertices of degree $d$ in G. If $S$ and $T$ are two different trees with $\xi(S) = \xi(T)$, then

  1. $\mid S\mid = 2\mid T \mid$
  2. $\mid S \mid = \mid T \mid - 1$
  3. $\mid S\mid = \mid T \mid$
  4. $\mid S \mid = \mid T\mid + 1$
Consider all possible trees with $n$ nodes. Let $k$ be the number of nodes with degree greater than $1$ in a given tree. What is the maximum possible value of $k$?

Answers: Trees

Selected Answer

Option a $\iff$ Option b $\iff$ Option c $\iff$ Option d.

  • You need atleast $n-1$ edges to have a connected graph. This leaves no edges to make any cycles. Thus, Option a $\implies G$ is acyclic.
  • A connected graph with $n-1$ edges is acyclic, as shown above. Now, if we add any more edges to this graph, we will be connecting two vertices that are already connected. Thus, adding any more than edges to a connected graph will cause cycles. So, if a graph is acyclic and connected, it has exactly $(n-1)$ edges.
  • You can't fit $(n-1)$ edges between $(n-1)$ vertices without causing cycles. Thus, if graph with $(n-1)$ edges is acyclic, it must connect $n$ vertices. Hence, an acyclic graph with $(n-1)$ edges is connected.

Thus, all options, a to d are equivalent.

Option b $\iff G$ is a tree.

  • Any acyclic connected graph is a tree by definition.
  • A graph $G$ is a tree if it is both acyclic and connected by definition.

Thus, all option a to d are both necessary and sufficient for an undirected graph $G$ to be a tree.


Option e $\mathrel{\rlap{\hskip .5em/}}\Longrightarrow G$ is a tree.

  • Since $G$ is not constrained to be acyclic, we can create a cyclic graph with $(n-1)$ edges. This graph will be cyclic, and it won't be connected. And thus, it won't be a tree.

 

Hence, option e is the correct answer.

9 votes -- Pragy Agarwal ( 19.3k points)
Selected Answer
Sum of degrees in a graph = 2 |E|, as each edge contributes two to the sum of degrees. So, when sum of degrees are same, number of edges must also be same.

Trees with equal no of edges has to have equal no of vertices as No of Edges = No of vertices - 1, in a tree.

So, should be |S| = |T|
24 votes -- Digvijay ( 46k points)
Maximum value of k is n-2 which is example of line graph because every tree should contain at least 2 pendent vertices (i.e vertex with degree 1). Therefore value of k cannot exceed n-2
3 votes -- Heisenberg ( 1.6k points)

Let $G$ be a simple graph with $20$ vertices and $100$ edges. The size of the minimum vertex cover of G is $8$. Then, the size of the maximum independent set of $G$ is:

  1. 12
  2. 8
  3. less than 8
  4. more than 12

Answers: Vertex Cover

Selected Answer
Vertex cover: A set  of vertices such that each edge of the graph is incident to atleast one vertex of the set.

 

Therefore, removing all the vertices of the vertex cover from the graph results in an isolated graph and the same set of nodes would be the independent set in the original graph.

size of minimum vertex cover = 8

size of maximum independent set = 20 - 8  =12

Therefore, correct answer would be (A).
18 votes -- suraj ( 5k points)

Q12  The maximum possible value of xy2z3 subjected to condition x,y,z$\geq 0$ and x+y+z=3 is

A) 1

B) $\frac{9}{8}$

C) $\frac{9}{4}$

D) $\frac{27}{16}$

Show that the product of the least common multiple and the greatest common divisor of two positive integers $a$ and $b$ is $a\times b$.

       

Answers:

Selected Answer

Given ,

             x + y + z = 3

==>    x + (y/2) + (y/2) + (z/3) + (z/3) + (z/3) = 3

Now using A.M. G.M inequality , we have : 

        [ x + (y/2) + (y/2) + (z/3) + (z/3) + (z/3) ] / 6  >=   (x . (y/2) .(y/2) . (z/3) . (z/3) .(z/3))^(1/6)

==>    (x . (y/2) .(y/2) . (z/3) . (z/3) .(z/3))^(1/6)    <=   1/2

==>    (x . (y/2) .(y/2) . (z/3) . (z/3) .(z/3))     <=  1 / 64

==>     x . y^2 . z^3    <=  108 / 64  =  27 / 16

 

Hence  D) is the correct answer

6 votes -- HABIB MOHAMMAD KHAN ( 66.5k points)
lcm(x,y) : lcm of x and y

gcd(x,y):  gcd of x and y

∀x∀y( x >= 0 ∧ y>=0 ) $\rightarrow$ (LCM(x,y) * GCD(x,y) = x*y )
2 votes -- khush tak ( 5.8k points)

Let  a ( 120 ) = f1 * f2 * f3 * f4 * f5 ....  ( 2 * 2 * 2 * 3 * 5 ).

      b ( 18 )   = F1 * F2 * F3........       ( 2 * 3 * 3 )


LCM of a( 120 )  and b( 18 ) = product of elements of a union b.

                                         = M( {f1, f2, f3, f4, f5 } U { F1, F2, F3 } )    //M- > multiplication.

                                         = M( (f1/F1), f2, f3, (f4/F2), F3, f5 )   ----- (A)      // f1/ F1- > f1 or F1 


HCF of a( 120 )  and b( 18 ) = product of elements of a intersection b.   

                                         = M( {f1, f2, f3, f4, f5 } $\cap$ { F1, F2, F3 } )

                                         = M( (f1/F1), (f4/F2) )      -----------------------(B)

// Remember if a $\cap$ b= ∅, then HCF = 1.


From equation A and B,

Product of LCM and HCF =  M( (f1/F1), f2, f3, (f4/F2), F3, f5 ) M( (f1/F1), (f4/F2) ) 

                                      =  M( f1, f2, f3, f4, F3, f5,  F1, F2 )

                                      = Product of a and b.

2 votes -- Dhananjay Kumar Sharma ( 24.9k points)

Which one of the following Boolean expressions is NOT a tautology?

  1. $((\,a\,\to\,b\,)\,\wedge\,(\,b\,\to\,c))\,\to\,(\,a\,\to\,c)$
  2. $(\,a\,\to\,c\,)\,\to\,(\,\sim b\,\to\,(a\,\wedge\,c))$
  3. $(\,a\,\wedge\,b\,\wedge\,c)\,\to\,(\,c\vee\,a)$
  4. $a\,\to\,(b\,\to\,a)$

Answers: Boolean Expressions

Selected Answer
Another way to solve it...

Implication A->B is not tautology if B is false and A is true

For b option Let RHS ie -b->(a ∧c) be false ie b is false and (a∧ c ) is false

Now a AND c is false if both a and c are false or one of them is true and other is false

Now if a and c both are false then a ->c is true Now LHS is true and RHS is false

So option b is not tautology..
12 votes -- Pooja Palod ( 31.2k points)

option B reduces to A+B rest all reduces to 1

Hence, B is not a tautology.

7 votes -- Amar Vashishth ( 27.9k points)
Obtain the principal (canonical) conjunctive normal form of the propositional formula

$$(p \wedge q) \vee (\neg q \wedge r)$$

where $\wedge$ is logical and, $\vee$ is inclusive or and $\neg$ is negation.

Answers: Canonical Normal Form

Selected Answer
$(p \vee \neg q\vee r)\wedge (p\vee \neg q\vee \neg r)\wedge (p\vee q\vee r)\wedge (\neg p\vee q\vee r)$
6 votes -- Anu ( 10.2k points)
Which of the following predicate calculus statements is/are valid?

(1) $(\forall (x)) P(x) \vee (\forall(x))Q(x) \implies (\forall (x)) (P(x) \vee Q(x))$

(2) $(\exists (x)) P(x) \wedge (\exists (x))Q(x) \implies (\exists (x)) (P(x) \wedge Q(x))$

(3) $(\forall (x)) (P(x) \vee Q(x)) \implies (\forall (x)) P(x) \vee (\forall (x)) Q(x)$

(4) $(\exists (x)) (P(x) \vee Q(x)) \implies \sim (\forall (x)) P(x) \vee (\exists (x)) Q(x)$

Let $\text{fsa}$ and $\text{pda}$ be two predicates such that $\text{fsa}(x)$ means $x$ is a finite state automaton and $\text{pda}(y)$ means that $y$ is a pushdown automaton. Let $\text{equivalent}$ be another predicate such that $\text{equivalent}(a,b)$ means $a$ and $b$ are equivalent. Which of the following first order logic statements represent the following?

Each finite state automaton has an equivalent pushdown automaton

  1. $\left(\forall x \text{ fsa}\left(x\right) \right) \implies \left( \exists y \text{ pda}\left(y\right) \wedge \text{equivalent}\left(x,y\right)\right)$
  2. $\neg \forall y \left(\exists x \text{ fsa}\left(x\right)  \implies \text{pda}\left(y\right) \wedge \text{equivalent}\left(x,y\right)\right)$
  3. $\forall x \exists y \left(\text{fsa}\left(x\right) \wedge \text{pda}\left(y\right) \wedge \text{equivalent}\left(x,y\right)\right)$
  4. $\forall x \exists y \left(\text{fsa}\left(y\right) \wedge \text{pda}\left(x\right) \wedge \text{equivalent}\left(x,y\right)\right)$
Which one of the following options is CORRECT given three positive integers $x, y$ and $z$, and a predicate
$$P\left(x\right) = \neg \left(x=1\right)\wedge \forall y \left(\exists z\left(x=y*z\right) \Rightarrow \left(y=x\right) \vee \left(y=1\right) \right)$$

(A) $P(x)$ being true means that $x$ is a prime number

(B) $P(x)$ being true means that $x$ is a number other than 1

(C) $P(x)$ is always true irrespective of the value of $x$

(D) $P(x)$ being true means that $x$ has exactly two factors other than 1 and $x$

The CORRECT formula for the sentence, "not all Rainy days are Cold" is

  1. $\forall d (\text{Rainy}(d) \wedge \text{~Cold}(d))$
  2. $\forall d ( \text{~Rainy}(d) \to \text{Cold}(d))$
  3. $\exists d(\text{~Rainy}(d) \to \text{Cold}(d))$
  4. $\exists d(\text{Rainy}(d) \wedge \text{~Cold}(d))$

Which of the following first order formulae is logically valid? Here $\alpha(x)$ is a first order formula with $x$ as a free variable, and $\beta$ is a first order formula with no free variable.

  1. $[\beta \rightarrow (\exists x, \alpha(x))] \rightarrow [\forall x, \beta \rightarrow \alpha(x)]$
  2. $[\exists x, \beta \rightarrow \alpha(x)] \rightarrow [\beta \rightarrow (\forall x, \alpha(x))]$
  3. $[(\exists x, \alpha(x)) \rightarrow \beta] \rightarrow [\forall x, \alpha(x) \rightarrow \beta]$
  4. $[(\forall x, \alpha(x)) \rightarrow \beta] \rightarrow [\forall x, \alpha(x) \rightarrow \beta]$

Which one of the following is NOT logically equivalent to $¬∃x(∀ y (α)∧∀z(β ))$?

 

(A) $∀ x(∃ z(¬β )→∀ y(α))$

(B) $∀x(∀ z(β )→∃ y(¬α))$

(C) $∀x(∀ y(α)→∃z(¬β ))$

(D) $∀x(∃ y(¬α)→∃z(¬β ))$

Which of the following is the negation of [∀ x, α → (∃y, β → (∀ u, ∃v, y))]

  1. [∃ x, α → (∀y, β → (∃u, ∀ v, y))]
  2. [∃ x, α → (∀y, β → (∃u, ∀ v, ¬y))]
  3. [∀ x, ¬α → (∃y, ¬β → (∀u, ∃ v, ¬y))]
  4. [∃ x, α ʌ (∀y, β ʌ (∃u, ∀ v, ¬y))]

Which one of these first-order logic formulae is valid?

  1. ∀x(P(x) => Q(x)) => (∀xP(x) => ∀xQ(x))
  2. ∃x(P(x) ∨ Q(x)) => (∃xP(x) => ∃xQ(x))
  3. ∃x(P(x) ∧ Q(x)) <=> (∃xP(x) ∧ ∃xQ(x))
  4. ∀x∃y P(x, y) => ∃y∀x P(x, y)
What is the logical translation of the following statement?

"None of my friends are perfect."

(A) $∃x(F (x)∧ ¬P(x))$

(B) $∃ x(¬ F (x)∧ P(x))$

(C)$ ∃x(¬F (x)∧¬P(x))$

(D)$ ¬∃ x(F (x)∧ P(x))$

Consider the following first order logic formula in which $R$ is a binary relation symbol.

$$∀x∀y (R(x, y)  => R(y, x))$$

The formula is

  1. satisfiable and valid
  2. satisfiable and so is its negation
  3. unsatisfiable but its negation is valid
  4. satisfiable but its negation is unsatisfiable

Let $a(x, y), b(x, y,)$ and $c(x, y)$ be three statements with variables $x$ and $y$ chosen from some universe. Consider the following statement:

$$(\exists x)(\forall y)[(a(x, y) \wedge b(x, y)) \wedge \neg c(x, y)]$$

Which one of the following is its equivalent?

  1. $(\forall x)(\exists y)[(a(x, y) \vee b(x, y)) \to c(x, y)]$
  2. $(\exists x)(\forall y)[(a(x, y) \vee b(x, y)) \wedge\neg c(x, y)]$
  3. $\neg (\forall x)(\exists y)[(a(x, y) \wedge b(x, y)) \to c(x, y)]$
  4. $\neg (\forall x)(\exists y)[(a(x, y) \vee b(x, y)) \to c(x, y)]$

Let $P(x)$ and $Q(x)$ be arbitrary predicates. Which of the following statements is always TRUE?

  1. $\left(\left(\forall x \left(P\left(x\right) \vee Q\left(x\right)\right)\right)\right) \implies \left(\left(\forall x P\left(x\right)\right) \vee \left(\forall xQ\left(x\right)\right)\right)$
  2. $\left(\forall x \left(P\left(x\right) \implies Q\left(x\right)\right)\right) \implies \left(\left(\forall x P\left(x\right)\right) \implies \left(\forall xQ\left(x\right)\right)\right)$
  3. $\left(\forall x\left(P\left(x\right) \right) \implies \forall x \left( Q\left(x\right)\right)\right) \implies \left(\forall x \left( P\left(x\right) \implies Q\left(x\right)\right)\right)$
  4. $\left(\forall x \left( P\left(x\right)\right) \Leftrightarrow \left(\forall x \left( Q\left(x\right)\right)\right) \right) \implies \left(\forall x  \left (P\left(x\right) \Leftrightarrow Q\left(x\right)\right)\right)$

Which one of the following  well-formed formulae is a tautology?
 

  1. $\forall x \, \exists y \, R(x,y) \, \leftrightarrow \, \exists y \, \forall x \, R(x, y)$
  2. $( \forall x \, [\exists y \, R(x,y) \, \rightarrow \, S(x, y)]) \, \rightarrow \, \forall x \, \exists y \, S(x, y)$
  3. $[ \forall x \, \exists y \, \left( P(x,y) \, \rightarrow \, R(x, y) \right)] \, \leftrightarrow [ \forall x \, \exists y \left(\neg P(x, y) \, \lor R(x, y) \right)]$
  4. $\forall x \, \forall y \, P(x,y) \, \rightarrow \, \forall x \, \forall y \, P(y, x)$

Which of the following is NOT necessarily true? { Notation: The symbol ''$\neg$''notes negation; $P (x, y)$ means that for given $x$ and $y$, the property $P(x, y)$ is true }.

  1. $(∀x∀y P(x, y)) \Rightarrow (∀y∀x P(x, y))$
  2. $(∀x∃y \neg P(x, y)) \Rightarrow \neg (∃x∀y P(x, y))$
  3. $(∃x∃y P(x, y)) \Rightarrow  (∃y∃x P(x, y))$
  4. $(∃x∀y P(x, y)) \Rightarrow  (∀y∃x P(x, y))$
  5. $(∀x∃y P(x, y)) \Rightarrow  (∃y∀x P(x, y))$

Consider the following formula and its two interpretations \(I_1\) and \(I_2\).

\(\alpha: (\forall x)\left[P_x \Leftrightarrow (\forall y)\left[Q_{xy} \Leftrightarrow \neg Q_{yy} \right]\right] \Rightarrow (\forall x)\left[\neg P_x\right]\)

\(I_1\) : Domain: the set of natural numbers

\(P_x\) = 'x is a prime number'

\(Q_{xy}\) = 'y divides x'

\(I_2\) : same as \(I_1\) except that \(P_x\) = 'x is a composite number'.

Which of the following statements is true?

  1. \(I_1\) satisfies \(\alpha\), \(I_2\) does not
  2. \(I_2\) satisfies \(\alpha\), \(I_1\) does not
  3. Neither \(I_1\) nor \(I_2\) satisfies \(\alpha\)
  4. Both \(I_1\) and \(I_2\) satisfies \(\alpha\)

Which one of the following is the most appropriate logical formula to represent the statement?

 "Gold and silver ornaments are precious".
The following notations are used:        

  • $G(x): x$ is a gold ornament
  • $S(x): x$ is a silver ornament        
  • $P(x): x$ is precious

 

  1. $\forall x(P(x) \implies (G(x) \wedge S(x)))$
  2. $\forall x((G(x) \wedge S(x)) \implies P(x))$
  3. $\exists x((G(x) \wedge S(x)) \implies P(x))$
  4. $\forall x((G(x) \vee S(x)) \implies P(x))$

Which one of the following well-formed formulae in predicate calculus is NOT valid ?

  1. $(\forall x p(x) \implies \forall x q(x)) \implies (\exists x \neg p(x) \vee \forall x q(x))$
  2. $(\exists x p(x) \vee \exists x q (x)) \implies \exists x (p(x) \vee q (x))$
  3. $\exists x (p(x) \wedge q(x)) \implies (\exists x p(x) \wedge \exists x q(x))$
  4. $\forall x (p(x) \vee q(x)) \implies (\forall x p(x) \vee \forall x q(x))$

 

Which of the following is a valid first order formula? (Here \(\alpha\) and \(\beta\) are first order formulae with $x$ as their only free variable)

  1. ((∀x)[α] ⇒ (∀x)[β]) ⇒ (∀x)[α ⇒ β]
  2. (∀x)[α] ⇒ (∃x)[α ∧ β]
  3. ((∀x)[α ∨ β] ⇒ (∃x)[α]) ⇒ (∀x)[α]
  4. (∀x)[α ⇒ β] ⇒ ((∀x)[α]) ⇒ (∀x)[β])

In the following, $A$ stands for a set of apples, and $S(x, y)$ stands for "$x$ is sweeter than $y$. Let

$$\Psi \equiv \exists x : x \in A$$

$$\Phi \equiv \forall x \in A : \exists y \in A : S(x, y).$$

Which of the following statements implies that there are infinitely many apples (i.e.,, $A$ is an inifinite set)?

  1. $\Psi \wedge \Phi \wedge [\forall x \in A : \neg S(x, x)]$
  2. $\Psi \wedge \Phi \wedge [\forall x \in A : S(x, x)]$
  3. $\Psi \wedge \Phi \wedge [\forall x,y \in A : S(x, x) \wedge S(x, y) \rightarrow S(y,y)]$
  4. $\Psi \wedge \Phi \wedge [\forall x \in A : \neg S(x, x)] \wedge [\forall x, y, z \in A : S(x, y) \wedge S(y, z) \rightarrow s(y, x)]$
  5. $\Psi \wedge \Phi \wedge [\forall x \in A : \neg S(x, x)] \wedge [\forall x, y, z \in A : S(x, y) \wedge S(y, z) \rightarrow s(x, z)]$

Given that

  • B(x) means "x is a bat",
  • F(x) means "x is a fly", and
  • E(x, y) means "x eats y",

what is the best English translation of $$ \forall x(F(x) \rightarrow \forall y (E(y, x) \rightarrow B(y)))?$$

  1. all flies eat bats
  2. every fly is eaten by some bat
  3. bats eat only flies
  4. every bat eats flies
  5. only bats eat flies

For a person $p$, let $w(p)$, $A(p, y)$, $L(p)$ and $J(p)$ denote that $p$ is a woman, $p$ admires $y$, $p$ is a lawyer and $p$ is a judge respectively. Which of the following is the correct translation in first order logic of the sentence: "All woman who are lawyers admire some judge"?

  1. $\forall x: \left[\left(w\left(x\right)\Lambda L \left(x\right)\right)\Rightarrow \left(\exists y:\left(J \left(y\right)\Lambda w\left(y\right) \Lambda A\left(x, y\right)\right)\right)\right]$
  2. $\forall x: \left[\left(w\left(x\right)\Rightarrow L \left(x\right)\right)\Rightarrow \left(\exists y:\left(J \left(y\right) \Lambda A\left(x, y\right)\right)\right)\right]$
  3. $\forall x \forall y: \left[\left(w\left(x\right) \Lambda L\left(x\right)\right) \Rightarrow \left(J\left(y\right) \Lambda A\left(x, y\right)\right)\right]$
  4. $\exists y \forall x: \left[\left(w\left(x\right) \Lambda L\left(x\right)\right) \Rightarrow \left(J\left(y\right) \Lambda A\left(x, y\right)\right)\right]$
  5. $\forall x: \left[\left(w\left(x\right) \Lambda L\left(x\right)\right) \Rightarrow \left(\exists y: \left(J\left(y\right) \Lambda A\left(x, y\right)\right)\right)\right]$

Consider the first-order logic sentence $F:\forall x(\exists yR(x,y))$. Assuming non-empty logical domains, which of the sentences below are implied by $F$?

  1. $\exists y(\exists xR(x,y))$
  2. $\exists y(\forall xR(x,y))$
  3. $\forall y(\exists xR(x,y))$
  4. $¬\exists x(\forall y¬R(x,y))$

 

(A) $IV$ only

(B) $I$ and $IV$ only

(C) $II$ only

(D) $II$ and $III$ only

Consider the following well-formed formulae:
        

  1. $\neg \forall x(P(x))$
  2. $\neg \exists x(P(x))$
  3. $\neg \exists x(\neg P(x))$
  4. $\exists x(\neg P(x))$


Which of the above are equivalent?

  1. I and III
  2. I and IV
  3. II and III
  4. II and IV
What is the correct translation of the following statement into mathematical logic?

“Some real numbers are rational”

(A) $\exists x (real(x) \lor rational(x))$
(B) $\forall x (real(x) \to rational(x))$
(C) $\exists x (real(x) \wedge rational(x))$
(D) $\exists x (rational(x) \to real(x))$

Consider the statement

 "Not all that glitters is gold”

Predicate glitters$(x)$ is true if $x$ glitters and predicate gold$(x)$ is true if x is gold.  Which one of the following logical formulae represents the above statement?

  1. $\forall x: glitters (x)\Rightarrow \neg gold(x)$
  2. $\forall x: gold (x)\Rightarrow glitters(x)$
  3. $\exists x: gold(x)\wedge \neg glitters(x)$
  4. $\exists x: glitters(x)\wedge \neg gold(x)$
(b)

Consider the following first order formula:

$$\left ( \matrix{
    \forall x \exists y : R(x,y)
    \\[1em] \Large \land \\[1em]
    \forall x \forall y : \Bigl ( R(x,y) \implies \lnot R(y,x) \Bigr)
    \\[1em] \Large \land \\[1em]
    \forall x \forall y \forall z : \Bigl ( R(x,y) \land R(y,z) \implies R(x,z) \Bigr )
    \\[1em] \Large \land \\[1em]
    \forall x: \lnot R(x,x)
}\right )$$

Does it have finite models?

Is it satisfiable? If so, give a countable model for it.

Answers: First Order Logic

Selected Answer

(1) The corresponding English meaning: If $P(x)$ is true for all $x$, or if $Q(x)$ is true for all $x$, then for all $x$, either $P(x)$ is true or $Q(x)$ is true. This is always true and hence valid. To understand deeply, consider $X = \{3,6,9,12\}$. For LHS of implication to be true, either $P(x)$ must be true for all elements in $X$ or $Q(x)$ must be true for all elements in $X$. In either case, if we take each element $x$ in $X$, either one of $P(x)$ or $Q(x)$ will be true. Hence, this implication is always valid.

(If still in doubt, let $P(x)$ mean $x$ is a multiple of $3$ and $Q(x)$ means $x$ is a multiple of $2$)

(2) The corresponding English meaning: If $P(x)$ is true for at least one $x$, and if $Q(x)$ is true for at least one $x$, then there is at least one $x$ for which both $P(x)$ and $Q(x)$ are true. This is not always true as $P(x)$ can be true for one $x$ and $Q(x)$ can be true for some other $x$ . To understand deeply, consider $X = \{3,6,9,12\}$. Let $P(x)$ be $x$ is a multiple of $9$ and $Q(x)$ be $x$ is a multiple of $6$. Now, LHS of implication is true, since $P(x)$ is true for $x = 9$, and $Q(x)$ is true for $x = 6$. But RHS of implication is not true as there is no $x$ for which both $P(x)$ and $Q(x)$ holds.  Hence, this implication is not valid.

(3) If for each $x$, either $P(x)$ is true or $Q(x)$ is true then $P(x)$ is true for all $x$ or $Q(x)$ is true for all $x$. Just one read is enough to see this is an invalid implication. Consider set {2,4,5}. Here every element is either a multiple or 2 or 5. But all elements are neither multiple of 2 nor 5.

(4)If there is at least one $x$ for which either $P(x)$ or $Q(x)$ is true then either it is not the case that $P(x)$ is true for all $x$ or $Q(x)$ is true for at least one $x$. This is clearly invalid as  LHS of implication becomes true if $P(x)$ is true for some $x$ and $Q(x)$ is not true for any $x$, but RHS will be false (if $P(x)$ is true for all $x$).

A little modification to the statement is enough to make it valid:
$$\exists (x) (P(x) \vee Q(x)) \implies \sim (\forall (x) \sim  P(x)) \vee \exists (x) Q(x)$$
which means if there is at least one $x$ for which either $P(x)$ or $Q(x)$ is true then
either it is not the case that $\sim P(x)$ is true for all $x$ (which means P(x)  is true for some $x$) or $Q(x)$ is true for some $x$.

Note
De Morgan's law is applicable in first order logic and is quite useful:

$$\forall(x)(P(x)) \equiv \neg \exists (x)(\neg P(x))$$

This is a logical reasoning statement which means if $P(x)$ is true for all $x$, then there can never exist an $x$ for which $P(x)$ is not true. This formula is quite useful in proving validity of many statements as is its converse given below:

$$\exists(x)(P(x)) \equiv \neg \forall (x)(\neg P(x))$$

20 votes -- gatecse ( 13k points)

$A \implies B$ in this implication we can say this is false, if we can show a situation where A is true but at the same time B is false.

In the 4th case : $(\exists (x)) (P(x) \vee Q(x)) \implies \sim (\forall (x)) P(x) \vee (\exists (x)) Q(x)$

To check validity we do the following : 

1st approach:

  • Assume LHS as true or (1) based on some condition.
  • Then try to make RHS false (0) on the same set of conditions as above.

Or,

2nd approach:

  • Assume RHS as false (0) and try to make LHS as true (1) on some common conditions.

if we can show anyone one of the above situation exists. Then implication 4 is false.

Using second approach:

in RHS assume all $Q(x)$ are false (0) and all $P(x)$ are true (1) such that RHS becomes false (0).

Based on these above condition if we look on the left hand side, we find that LHS side is true (1) since all $P(x)$ are true.

6 votes -- Debashish Deka ( 48k points)
Selected Answer
None of these.

A. If everything is a FSA, then there exists an equivalent PDA for everything.
B. It is not the case that for all y if there exist a FSA then it has an equivalent PDA.
C. Everything is a FSA and has an equivalent PDA.
D. Everything is a PDA and has exist an equivalent FSA.

The correct answer would be

$$∀x (\text{fsa}(x)⟹(∃y \text{ pda}(y)∧\text{ equivalent}(x,y)))$$
18 votes -- Arjun Suresh ( 286k points)
Selected Answer

Answer is A.

$P\left(x\right) = (\neg \left(x=1\right)\wedge \forall y \left(\exists z\left(x=y*z\right) \Rightarrow (\left(y=x\right) \vee \left(y=1\right) \right)) \\ \text{Statement:  x is not equal to 1 and if there exists some z for all }\\ \text{ y such that product of y and z is x, then y is either the number itself or 1.}\\ \text{ This is the definition of prime numbers.}$
 

alternative approach ,
 the formula

\exists x \forall y \forall z[\times (y, z, x) \rightarrow ((y = 1) \vee (z = 1))]

expresses the statement "there exists a prime number" (the number 1 also satisfies this statement).

Note here that \times (y, z, x) is equivalent to (x = y \times z).
but ¬(x=1) removes 1 as satisfying given number in question's formula , so the option A is True.
ref@ 
https://en.wikibooks.org/wiki/Logic_for_Computer_Science/First-Order_Logic#Semantics
ref@ http://math.stackexchange.com/questions/1037795/what-is-the-meaning-of-this-predicate-statement

 

18 votes -- Sona Praneeth Akula ( 4k points)
Let's consider here   P= R  AND S ( for simplification)

We know that   T AND T=T

                       F AND F=F

                       F AND T =F

To make P(x) = T ,  need to make both R and S , True.

R is true , i.e. NOT(x=1) is true , so ( x=1) is false

hence x is a number other than 1 . (option B)
2 votes -- Manali ( 2.8k points)
Selected Answer

Not all rainy days are cold.

In other words it says "Some rainy days are cold" or "Some rainy days are not cold"
 

Given statement is
~Vd[R(d)->C(d)]
<=>~Vd[~R(d)VC(d)]

<=> ∃ d[R(d) ^ ~C(d)]
D)

 

10 votes -- Srinath Jayachandran ( 3.7k points)
A) No rainy days are cold

B) All non-rainy days are cold

C)Some non-rainy days are cold.

D) Some rainy days are not cold.

option D
15 votes -- Manali ( 2.8k points)
Selected Answer

A. $[\beta → (\exists x, \alpha(x))] → [\forall x, \beta → \alpha(x)]$

LHS: If $\beta$ (some condition) is true, then there exists an $x$ for which $\alpha(x)$ is true.  
RHS: For all $x$, if $\beta$ is true then $\alpha(x)$ is true. This is same as saying if $\beta$ is true then for all $x$, $\alpha(x)$ is true. $(\beta \implies \forall x, \alpha(x))$.

So, $$\text{RHS} \implies \text {LHS} \\ \text{and} \\ \text{LHS} \not\Longrightarrow  \text{RHS}.$$

B. $[\exists x, \beta → \alpha(x)] → [\beta → (\forall x, \alpha(x))]$

LHS: There exists an $x$ such that if $\beta$ is true then $\alpha(x)$ is true. 
RHS: If $\beta$ is true then for all $x, \alpha(x)$ is true.  

So, $$\text{RHS} \implies \text {LHS} \\ \text{and} \\ \text{LHS} \not\Longrightarrow  \text{RHS}.$$

C. $[(\exists x, \alpha(x)) → \beta] → [\forall x, \alpha(x) → \beta]$

LHS: If there is an $x$ such that $\alpha(x)$ is true, then $\beta$ is true. 
RHS: For all $x$, if $\alpha(x)$ is true, then $\beta$ is true. 

Here, both LHS and RHS are in fact same as $\beta$ is a formula which is independent of $x$. (if $\beta$ is true for one $x$, it is true for every $x$ and vice versa). 

So, $$\text{RHS} \implies \text {LHS} \\ \text{and} \\ \text{LHS} \implies  \text{RHS}.$$

D. $[(\forall x, \alpha(x)) → \beta] → [\forall x, \alpha(x) → \beta]$

LHS: If $\alpha(x)$ is true for every $x$, then $\beta$ is true.
RHS: For every $x$, if $\alpha(x)$ is true then $\beta$ is true. 

So, $$\text{RHS} \implies \text {LHS} \\ \text{and} \\ \text{LHS} \not\Longrightarrow  \text{RHS}.$$

So, answer here is option C. Any of options A, B or D could be valid if their implication is reversed. For option C, LHS and RHS being equivalent, even if the implication is reversed (or changed to double implies) it remains valid. 

16 votes -- Arjun Suresh ( 286k points)

[(∃x,α(x))→β]→[∀x,α(x)→β]

LHS => (∃x,α(x))→β ))

              (~∃x,α(x)) V β -> (∀x, ~α(x)) V β  )  -> (∀x, (~α(x) V β)) (I can change scope of  ∀x as B do not have x as  free variable in it.

(∀x, (α(x) -> β)) Proved !

C is correct

 

17 votes -- Akash ( 41.5k points)
Selected Answer

A useful rule: $$\forall x (\alpha) = \neg \exists (x)  (\neg \alpha) $$

i.e.; If some property $\alpha$ is true for all $x$, then it is equivalent ot say that no $x$ exists such that property $\alpha$ does not hold for it.

Starting with choices:

A: $\forall x (\exists z (\neg \beta) \to \forall y (\alpha)) $

$\implies \forall x (\neg \exists z (\neg \beta) \vee \forall y (\alpha)) $

$\implies \forall x (\forall z ( \beta) \vee \forall y (\alpha)) $

$\implies \neg \exists x \neg (\forall z ( \beta) \vee \forall y (\alpha)) $

$\implies \neg \exists x  (\neg \forall z ( \beta) \wedge \neg \forall y (\alpha)) $

So, A is not matching with the logical statement in question.

B: $\forall x (\forall z (\beta) \to \exists y (\neg \alpha)) $

$\implies \forall x (\neg \forall z (\beta) \vee \exists y (\neg \alpha)) $

$\implies \neg \exists x \neg(\neg \forall z (\beta) \vee \exists y (\neg \alpha)) $

$\implies \neg \exists x (\forall z (\beta) \wedge \neg \exists y (\neg \alpha)) $

$\implies \neg \exists x (\forall z (\beta) \wedge \forall y (\alpha)) $

Hence matches with the given statement.

C.  $\forall x (\forall y (\alpha) \to \exists z (\neg \beta)) $

$\implies \forall x (\neg \forall y (\alpha) \vee \exists z (\neg \beta)) $

$\implies \neg \exists x \neg(\neg \forall y (\alpha) \vee \exists z (\neg \beta)) $

$\implies \neg \exists x (\forall y (\alpha) \wedge \neg \exists z (\neg \beta)) $

$\implies \neg \exists x (\forall y (\alpha) \wedge \forall z (\beta)) $

Hence matches with the given statement.

D: $\forall x (\exists y (\neg \alpha) \to \exists z (\beta)) $

$\implies \forall x (\neg \exists y (\neg \alpha) \vee \exists z (\beta)) $

$\implies \forall x (\forall y ( \alpha) \vee \exists z (\beta)) $

$\implies \neg \exists x \neg (\forall y ( \alpha) \vee \exists z (\beta)) $

$\implies \neg \exists x  (\neg \forall y ( \alpha) \wedge \neg \exists z (\beta)) $

$\implies \neg \exists x  (\neg \forall y ( \alpha) \wedge \forall z (\neg \beta)) $

So, D is not matching with the logical statement in question.

Thus both A and D are not logically equivalent to the given statement.
In GATE 2013 marks were given to all for this question

19 votes -- Arjun Suresh ( 286k points)
Selected Answer

[∀ x, α → (∃y, β → (∀ u, ∃v, y))] = [∀ x, ¬α v  (∃y, ¬β v (∀ u, ∃v, y))]

Now, doing complement gives (complement of ∀ is ∃ and vice versa while propagating negation inwards as ∀x (P) = ¬∃x (¬P) and ∃x (P) = ¬∀x (¬P))

[∃ x, α ʌ (∀y, β ʌ (∃ u, ∀ v, ¬y))]

D choice
 

19 votes -- Arjun Suresh ( 286k points)
Selected Answer
(A) is the answer

(A)
LHS: For every x, if P holds then Q holds
RHS: If P(x) holds for all x, then Q(x) holds for all x.
LHS implies RHS but RHS does not imply LHS.

(B)
LHS: An x exist for which either P(x) is true or Q(x) is true.
RHS: If an x exist for which P(x) is true then another x exist for which Q(x) is true.
LHS does not imply RHS, but on RHS if we change ∃xP(x) to ~∃xP(x), implication becomes TRUE.

(C)
LHS: There exist an x for which both P(x) and Q(x) are true.
RHS: There exist an x for which P(x) is true and there exist an x for which Q(x) is true.
LHS implies RHS but RHS does not imply LHS as the 'x' for P and Q can be different on the RHS

(D)
LHS: For every x, there exist a y such that P(x, y) holds.
RHS: There exist a y such that for all x P(x, y) holds.
Here RHS implies LHS but LHS does not imply RHS as the y on LHS can be different for each x.
21 votes -- Arjun Suresh ( 286k points)

option A

Let P(x)=All are multiple of 4

     Q(X)= All are even numbers

if a ∈ P(X) then a must  ∈ Q(X) 

4 votes -- Manali ( 2.8k points)
Selected Answer

A. some of my friends are not perfect

B. some of those who are not my friends are perfect

C. some of those who are not my friends are not perfect

D. NOT (some of my friends are perfect) / none of my friends are perfect

 

 

 

23 votes -- Bhagirathi Nayak ( 13.1k points)

Best way to answer this kind of question...

F(x)=x is my friend

P(x)=x is perfect

"None of my friends are perfect" it can be written like this

∀x[F(x)--->~P(x)]

=∀x[~F(x)∨~P(x)]

=∀x~[F(x)∧p(x)]

=~∃x[F(x)∧P(x)]

 

so answer is D

11 votes -- vnc ( 6.1k points)
Selected Answer
The given relation is nothing but symmetry. We have both symmetric relations possible as well as anti-symmetric but neither always holds for all sets. So they both are not valid but are satisfiable. B option.
29 votes -- Arjun Suresh ( 286k points)
Selected Answer
$(\exists x)(\forall y)[(a(x, y) \wedge b(x, y)) \wedge ¬c(x, y)]$

$= ¬(\forall x)¬(\forall y)[(a(x, y) \wedge b(x, y)) \wedge ¬c(x, y)]$
$(\because (\exists x) F(x) = \neg \forall x \neg F(x))$

$= ¬(\forall x)(\exists y)¬[(a(x, y) \wedge b(x, y)) \wedge ¬c(x, y)]$
$(\because (\forall x) F(x) = \neg \exists x \neg F(x)), \neg \neg F(x) = F(x))$

$= ¬(\forall x)(\exists y)[¬(a(x, y) \wedge b(x, y)) \vee c(x, y)]$

$= ¬(\forall x)(\exists y)[(a(x, y) \wedge b(x, y)) → c(x, y)]$

(C) choice.
12 votes -- Arjun Suresh ( 286k points)
Selected Answer
Answer: B

Let P: Student is a girl.

and Q: Student is smart.

Option B says: IF for all student x if x is a girl then the student is smart THEN if the whole class comprises of girls then the whole class comprises of smart students.
18 votes -- Rajarshi Sarkar ( 34.3k points)

For these kind of quetion use method.

Put RHS is false then try to make LHS is true . if this happen then statemnt is false otherwise true.

Or 

Put LHS is True then try to make RHS is False . if this happen then statemnt is false otherwise true.

9 votes -- Prashant Singh ( 47.5k points)
Selected Answer

Ans C.

$\left(P \rightarrow Q\right) \leftrightarrow \left(\neg P \vee Q\right)$

 

D is wrong as shown below. 

Let $S = \left\{2, 3, 4, 5\right\}$ and $P(x,y)$ be $x < y$.

Now, P(2,3) is true but P(3,2), P(4,2) etc are false and hence the implication also.

This is because the given formula is evaluated as:

$\forall x \, \forall y \, \left(P(x,y) \, \rightarrow \, \forall x \, \forall y \, P(y, x) \right)$

For every (x,y) if P(x,y) is true then for every (x,y) P(y,x) is true. 

On the RHS, $P(y,x)$ can be replaced with $P(x,y)$ and then also the formula means the same. So, here precedence rule used is $\implies$ having more precedence than quantification which is against the convention used in Wikipedia. I guess all books only talk about conventions and there is no standard here. C option being so straight forward I guess, GATE didnot even consider this as an ambiguity. Also, it works only if $x, y$ belongs to same domain.

The below one is a tautology provided $x,y$ have the same domain.

$\left(\forall x \,\forall y P(x,y) \, \right) \rightarrow \,\left( \forall x \forall y \,P(y, x)\right)$ 

If P(x,y) is true for all (x,y), then P(y,x) is true for all (x,y).

16 votes -- Vikrant Singh ( 13.4k points)
Selected Answer

a is TRUE as both LHS and RHS are equivalent- English would be for every x, and for every y, P(x,y) is TRUE. Changing y and x wouldn't change the meaning.

b is TRUE as both LHS and RHS are equivalent- RHS is obtained by double negation of LHS.

c. Similar to a, both are equivalent.

d.

  • LHS: For some x, for all y, P(x,y) is TRUE.
  • RHS: For all y and for some x, P(x,y) is TRUE.

Both are not equivalent. LHS is stronger and implies RHS. For example, on the natural number set, we have $x = 1$ such that for every $y, P(x \leq y)$ is TRUE. Clearly, this implies for all $y$ there exists some $x$ (here $x$ could be different for different $y$ but on LHS, it must be the same).

e.

  • LHS: For all x and for some y, P(x, y) is TRUE.
  • RHS: For some y and for all x, P(x, y) is TRUE.

As explained in d, these are not equivalent and here RHS is stronger than LHS, making the implication false. For example consider the "<=" relation on the integer set. LHS is true here as for every integer we have another integer which is greater . But RHS is false as there is no single integer (infinity is not an integer) which is greater than all other integers. 

7 votes -- Arjun Suresh ( 286k points)
Selected Answer

 

@Arjun Sir plz verify this method.


$Q_{yy}$ is always True, this makes  $\neg Q_{yy}$ False.

Writing $(\forall y)[Q_{xy} \Leftrightarrow \neg Q_{yy}]$ is same as writing $(\forall y)[Q_{xy} \Leftrightarrow False]]$

This is equivalent to saying that, for all y $Q_{xy}$ is false and finally we can rewrite $(\forall y)[Q_{xy} \Leftrightarrow \neg Q_{yy}]]$ as $(\forall y)[\neg Q_{xy}]$

 

α: (∀x)[Px⇔(∀y)[¬Qxy]]⇒(∀x)[¬Px

LHS:(∀x)[Px⇔(∀y)[¬Qxy]]

consider only (∀y)[¬Qxy] it says all values of y does not divide x, It is true irrespective of x being prime or composite. Even if x is composite then only its factor divides x not all values.

Now LHS becomes (∀x)[Px⇔True], "Px⇔True" this means Pis True, which is same as writing "Px" only.

Finally, we reduced LHS to (∀x)[Px]

α: (∀x)[Px]⇒(∀x)[¬Px

LHS: (∀x)[Px].

LHS is false for I1 bcoz not all x are primes False ⇒ Anything is True. For I1 α is true hence I1 satisfies α.

Similarly, LHS is false for I2 also bcoz not all x are composite. hence I2 satisfies α.

Option D.

19 votes -- Sachin Mittal ( 5.9k points)

$\alpha: (\forall x)\left[P_x \Leftrightarrow (\forall y)\left[Q_{xy} \Leftrightarrow \neg Q_{yy} \right]\right] \Rightarrow (\forall x)\left[\neg P_x\right]$

This is can be interpreted as:

  • $\alpha: \left( (\forall x)\left[P_x \Leftrightarrow (\forall y)\left[Q_{xy} \Leftrightarrow \neg Q_{yy} \right]\right] \right) \Rightarrow \left((\forall x)\left[\neg P_x\right] \right)$

See the RHS. It says $P(x)$ is false for any natural number. But there are natural numbers which are prime and hence this RHS is FALSE. Now, to make $\alpha$ TRUE, LHS must be FALSE for any $x$. Here, LHS is bit complex, so lets consider it separately. 

$ (\forall x)\left[P_x \Leftrightarrow (\forall y)\left[Q_{xy} \Leftrightarrow \neg Q_{yy} \right]\right] $

LHS is TRUE only if the given implication is TRUE for all $x$. Here the rightmost double implication $(\forall y)\left[Q_{xy} \Leftrightarrow \neg Q_{yy} \right]$ is always FALSE, because $x$ can be equal to $y$ and hence forall can never be TRUE. So the LHS reduces to just $(\forall x) \neg P(x)$ and returns FALSE as we have prime as well as non-prime natural numbers. So, FALSE $\Rightarrow$ FALSE returns TRUE making both $I_1$ and $I_2$ satisfy $\alpha$. D choice. 

 

24 votes -- Arjun Suresh ( 286k points)
Selected Answer

Answer is D. \text{ The statement could be translated as, If }x \text{ is either Gold or Silver,}\\ \text{ then it would be precious. Rather than, If }x \text{ is both Gold and Silver, as an item cannot both Gold and silver at the same time.}

25 votes -- Sona Praneeth Akula ( 4k points)
Selected Answer
Here D is not valid

Let me prove by example

What D is saying here is something like this

For all x ( x is even no or x is odd no ) ==> For all x( x is even no ) or For all x ( x is odd no) this is surely wrong. So

Ans => D
22 votes -- Akash ( 41.5k points)
Selected Answer
(D) is the answer.

(A) Let X = {3,6,9,8}. Let α denote multiple of 3 and β denote multiple of 4. (∀x)[α] becomes false as 8 is not a multiple of 3, and so (∀x)[α] ⇒ (∀x)[β] becomes TRUE. Now, this won't imply (∀x)[α ⇒ β] as multiple of 3 doesn't imply multiple of 4 for 3, 6 or 9.

(B) Let X = {3,6,9}. Let α denote multiple of 3 and β denote multiple of 4. Now LHS is TRUE but RHS is false as none of the x in X, is a multiple of 4.

(C)  Let X = {3,6,9,7}.  Let α denote multiple of 3 and β denote multiple of 4. Now  (∀x)[α ∨ β] becomes false and hence LHS = ((∀x)[α ∨ β] ⇒ (∃x)[α]) becomes true. But RHS is false as 7 is not a multiple of 3.

(D) This is valid. LHS is saying that if α is holding for any x, then β also holds for that x. RHS is saying if α is holding for all x, then β also holds for all x. Clearly LHS $\implies$ RHS (but RHS does not imply LHS).
For example, let X = {4, 8, 12}, α denote multiple of 2 and β denote multiple of 4. LHS = (∀x)[α ⇒ β], is TRUE. RHS is also true. If we add '3' to X, then LHS is true, first part of RHS becomes false and thus RHS also becomes TRUE. There is no way we can make LHS true and RHS false here. But if we add 2 and 3 to X, RHS will be true and LHS will be false. So, we can't say RHS implies LHS.
14 votes -- Arjun Suresh ( 286k points)
Selected Answer

Here is my Approach ....i am also getting (E) as the answer 

let A be {1,2}  (say apple 1, apple 2)

there is atleast one element in A : satisfied

for every element x in A there is a y in A such that S(x,y) : Since nothing is told about the symmetry of the relation, we can have S(1,2) and S(2,1)  : so,satisfied

So as of now, A = {1,2} and S={(1,2),(2,1)}

now we can go throught the options :

(A) S(x,x) is not possible ....i dont have that in S ....so satisified .....and still finite A

(B)  S(x,x) should be there......well, i will make S={(1,2)(2,1),(1,1),(2,2)}....satisfied and still finite A

(C) take the same case as above ....satisfied and still finite A

(D) Now i cant have (1,1) and (2,2)

but even with S={(1,2).(2,1)} this condition is satisfied ....still finite A

(E) i cant do this with (1,2) and (2,1) ...because the trasitivity makes it (1,1) which should not be there .....and whatever elements i add the transitivity will lead me to (x,x) .....because any element added to A should occur atleast once in the left side of an ordered pair.......so only solution is infinite A ...

3 votes -- Anand Vijayan ( 727 points)
Selected Answer
If $x$ is a fly, then for all $y$ which eats $x$, $y$ is a bat. This means only bats eat flies. Option E.
9 votes -- Arjun Suresh ( 286k points)
For any/all x if it is a fly and if it gets eaten up by any y than that y must be a bat..

So only bats eat flies.

Option e
6 votes -- ms17436 ( 95 points)
Selected Answer

Just translating to English:

  1. Every women who is a lawyer admires some women judge.
  2. If a person being women implies she is a lawyer then she admires some judge. OR If a person is not women or is a lawyer he/she admires some judge.
  3. Every women who is a lawyer admires every judge.
  4. There is some judge who is admired by every women lawyer.
  5. Every women lawyer admire some judge. 

So, option E is the answer. 

7 votes -- Arjun Suresh ( 286k points)
It will be e
2 votes -- srestha ( 54.8k points)
Selected Answer

Ans is B.

1st Method: $F:\forall x(\exists yR(x,y))$

Take option 4 :$¬\exists x(\forall y¬R(x,y))$

                      $\forall x(\exists yR(x,y))$  ( Since we know  $\sim \forall x = \exists x $ And  $ \sim\exists x =\forall x$ )


F:  For all girls there exist a boyfriend. (Given)
( x for girl & y for boys)

I:   There exists some boys who have girlfriends.  (True)
II:  There exists some boys for which all the girls are girlfriend. (False)
III: For all boys there exists a girlfriend. (False)
IV: For all girls, there exists a boyfriend (True) (Same as given F)

7 votes -- Ahwan Mishra ( 2.5k points)

so B is the ans.

4 votes -- 2018 ( 4.8k points)
Selected Answer

Option B is correct.  I and IV are equivalent. 

¬∀x(P(x)) = ∃x(¬P(x))    [De morgan's Law]

Alternate approach:

Let's take an example.

Let P(x) = Student x is pass.

I→ Not all students are pass. (which means "Some students are fail")

II→There doesn't exist a student who is pass. (which means "Every student is fail")

III→There doesn't exist a student who is not pass  (which means "Every student is pass")

IV→Some students are not pass. (which means "Some students are fail")

I and IV are equivalent.

2 votes -- Soumya Jain ( 565 points)
I and IV are equal
12 votes -- Bhagirathi Nayak ( 13.1k points)
Selected Answer
Meaning of each choices:

(A): There exists a number which is either real or rational

(B): If a number is real it is rational

(C): There exists a number which is real and rational

(D): There exists a number such that if it is rational, it is real

So, (C) is the answer.
17 votes -- Arjun Suresh ( 286k points)
Selected Answer

"Not all that glitters is gold”  can be expressed as : 

                                                           ∼(∀x(glitters(x)gold(x))) 

(as restriction of universal quantification is same as universal quantification of a conditional statement.)

"Not all that glitters is gold" means "some glitters are not gold" which can be expressed as 

                                                             ∃x(glitters(x)¬gold(x))

(as restriction of an existential quantification is same as existential quantification of a conjunction.)

So option D is correct. 

2 votes -- Soumya Jain ( 565 points)

Option D is correct .
              "Not all that glitters is gold
can be expressed as :


⇒∼(∀x(glitters(x)⇒gold(x))

⇒$ ∃x\neg(glitters(x)⇒gold(x))$

⇒$∃x(\neg(\neg glitters(x) \vee gold(x))$

⇒$∃x(glitters(x) \wedge \neg gold(x))$

can be expressed as :

         " some glitters are not gold"

 

8 votes -- Anu ( 10.2k points)
Selected Answer

Let's break it down. Consider an ordered structure (directed graph).

  1. $\forall x \exists y : R(x,y) \quad \equiv$ Every vertex has atleast 1 outgoing edge.
     
  2. $\forall x \forall y : \Bigl ( R(x,y) \implies \lnot R(y,x) \Bigr) \quad \equiv$ If there is a directed edge from vertex $u$ to vertex $v$, there should not be an edge back from $v$ to $u$. That is, our relation $R(x,y)$ is antisymmetric.
     
  3. $\forall x \forall y \forall z : \Bigl ( R(x,y) \land R(y,z) \implies R(x,z) \Bigr ) \quad \equiv$ If $u \longrightarrow v \longrightarrow z$, then $u \to z$ is also true. That is, our relation $R(x,y)$ is transitive.
     
  4. $\forall x: \lnot R(x,x) \quad \equiv$ We cannot have a self-loop in the graph. That is, $R(x,y)$ is irreflexive.

 

Now, such a non-trivial (size $>0$) finite structure cannot exist.

Proof by contradiction:

Assume, for the sake of contradiction, that such a finite structure $S = (V,E)$ exists. Since it is finite, let the number of vertices in this structure be $|V| = n, n \in \mathbb{N}, n>0$.

Edit: A summarized version of the following proof is in the comments. You can directly skip to that.


Lemma 1: $v_n$ has an incoming edge from every vertex $v_i, i < n$

Proof by Induction:

Induction Hypothesis: $P(n) = $For every $1 \leq i < j \leq n$, there is an out edge from vertex $v_i$ to vertex $v_j$, that is $v_i \longrightarrow v_j$.

Base Cases:

  • Let $n = 2$.
    $v_1 \longrightarrow v_2$ must be true since there has to be an out edge from $v_1$ (Property A) and the only available vertex is $v_2$ (no self loops allowed - Property D).
    Hence, our hypothesis $P(2)$ is satisfied.
  • Let $n = 3$.
    There must be an out edge from $v_1$ to some vertex. Let's call that vertex $v_2$, that is $v_1 \longrightarrow v_2$.
    Similarly, there must be an out edge from $v_2$. But due to property B, we can't have an out edge from $v_2$ back to $v_1$. Hence, the out edge from $v_2$ must lead us to a new vertex. Lets call that $v_3$.

    Since $v_1 \longrightarrow v_2 \longrightarrow v_3$, due to Property C, we must have $v_1 \longrightarrow v_3$.
    Hence, our hypothesis $P(3)$ is satisfied.

Inductive Step:

For $P(n+1)$: The $n$th vertex $v_n$ must have an out edge. Since $P(n)$ is true, the $n$th vertex has incoming edges from all vertices $v_i, i < n$. Hence, the out edge from $v_n$ cannot be to any of those vertices. Self loops aren't allowed either.

Hence, the out edge from vertex $v_n$ must be to the new vertex $v_{n+1}$. That is, $\substack{\searrow\\[0.5em]\longrightarrow\\[0.5em]\nearrow}\; v_n \longrightarrow v_{n+1}$

Since every vertex $v_i, i < n$ has an out edge to $v_n$, and $v_n$ has an out edge to $v_{n+1}$, due to Property C, we have that $v_i$ has an out edge to $v_{n+1}$. That is, $v_i \longrightarrow v_{n+1}, \forall i \leq n$.

This is exactly what $P(n+1)$ states.

Hence, $P(n) \implies P(n+1)$.

Q.E.D

Since $P(n)$ is true as proven above, every vertex $v_i$ must have an out edge to the vertex $v_n$.


Since the $n$th vertex has incoming edges from all other vertices (Lemma 1), it cannot have an out edge to any vertex. It can't have self loop either. Thus, it fails to satisfy Property A.

Hence, our assumption that $S$ exists leads to a contradiction.

Q.E.D



The given logic formula can be satisfied by an infinite model.

For example, $R(x,y) \iff x < y, \quad x,y \in S$, where $S$ is any infinite ordered set, satisfies the given formula.

7 votes -- Pragy Agarwal ( 19.3k points)

consider the figure, draw edges as per the given proposition, there be a state in which you do whatever you want keeping the given conditions in view, you will always violate some, all are not true together.

In this case, shown by the diagram above, the proposition which says that there should not be any self loop is violated. There is no finite model to satisfy this.

2 votes -- Amar Vashishth ( 27.9k points)

Consider the following two statements.

  1. There are infinitely many interesting whole numbers.
  2. There are finitely many uninteresting whole numbers.

Which of the following is true?

  1. Statements 1 and 2 are equivalent.
  2. Statement 1 implies statement 2.
  3. Statement 2 implies statement 1.
  4. None of the above.

 

Long ago,in a planet far far away, there lived three races of intelligent inhabitants: the blues (who always tell the truth), the whites (who always lie), and the pinks (who, when asked a series of questions, start with a lie and then tell the truth and lie alternately). To three creatures, chosen from the planet and seated facing each other at $A$, $B$, and $C$ (see figure), the following three questions are put:

(i) What race is your left-hand neighbour?

(ii) What race is your right-hand neighbour?

(iii) What race are you?

Here are their answers:

(A) (i) White (ii) Pink (iii) Blue

(B) (i) Pink (ii) Pink (iii) Blue

(C) (i) White (ii) Blue (iii) Blue

What is the actual race of each of the three creatures?

  1. $A$ is Pink, $B$ is White, $C$ is Blue.
  2. $A$ is Blue, $B$ is Pink, $C$ is White.
  3. $A$ is Pink, $B$ is Blue, $C$ is Pink.
  4. $A$ is White, $B$ is Pink, $C$ is Blue.
  5. Cannot be determined from the above data.

All that glitters is gold. No gold is silver.

Claims:

(1) No silver glitters.

(2) Some gold glitters.

Then, which of the following is TRUE?

  1. Only claim $1$ follows.
  2. Only claim $2$ follows.
  3. Either claim $1$ or claim $2$ follows but not both.
  4. Neither claim $1$ nor claim $2$ follows.
  5. Both claim $1$ and claim $2$ follow.

Consider the following two statements.

  • S1: If a candidate is known to be corrupt, then he will not be elected
  • S2: If a candidate is kind, he will be elected


Which one of the following statements follows from S1 and S2 as per sound inference rules of logic?
 

  1. If a person is known to be corrupt, he is kind
  2. If a person is not known to be corrupt, he is not kind
  3. If a person is kind, he is not known to be corrupt
  4. If a person is not kind, he is not known to be corrupt

In a room there are only two types of people, namely Type 1 and Type 2. Type 1 people always tell the truth and Type 2 people always lie. You give a fair coin to a person in that room, without knowing which type he is from and tell him to toss it and hide the result from you till you ask for it. Upon asking the person replies the following

"The result of the toss is head if and only if I am telling the truth"

Which of the following options is correct?

  1. The result is head
  2. The result is tail
  3. If the person is of Type 2, then the result is tail
  4. If the person is of Type 1, then the result is tail

If the bank receipt is forged, then Mr. M is liable. If Mr. M is liable, he will go bankrupt. If the bank will loan him money, he will not go bankrupt. The bank will loan him money.

Which of the following can be concluded from the above statements?

  1. Mr. M is liable
  2. The receipt is not forged
  3. Mr. M will go bankrupt
  4. The bank will go bankrupt
  5. None of the above

The action for this problem takes place in an island of Knights and Knaves, where Knights always make true statements and Knaves always make false statements and everybody is either a Knight or a Knave. Two friends A and B lives in a house. The census taker (an outsider) knocks on the door and it is opened by A. The census taker says ''I need information about you and your friend. Which if either is a Knight and which if either is a Knave?". "We are both Knaves" says A angrily and slams the door. What, if any thing can the census taker conclude?

  1. A is a Knight and B is a Knave.
  2. A is a Knave and B is a Knight.
  3. Both are Knaves.
  4. Both are Knights.
  5. No conclusion can be drawn.
Consider the following logical inferences.
  

$I_{1}$: If it rains then the cricket match will not be played.
The cricket match was played.
Inference:  There was no rain.

$I_{2}$: If it rains then the cricket match will not be played.
It did not rain.
Inference: The cricket match was played.

    Which of the following is TRUE?
 
    (A) Both $I_{1}$ and $I_{2}$ are correct inferences
    (B) $I_{1}$ is correct but $I_{2}$ is not a correct inference
    (C) $I_{1}$ is not correct but $I_{2}$ is a correct inference
    (D) Both $I_{1}$ and $I_{2}$ are not correct inferences

If either wages or prices are raised, there will be inflation. If there is inflation, then either the government must regulate it or the people will suffer. If the people suffer, the government will be unpopular. Government will not be unpopular. Which of the following can be validly concluded from the above statements.

  1. People will not suffer
  2. If the inflation is not regulated, then wages are not raised
  3. Prices are not raised
  4. If the inflation is not regulated, then the prices are not raised
  5. Wages are not raised

Answers: Logical Reasoning

Selected Answer

As we know that there are infinite whole numbers.

Now if we say that all even whole numbers are interesting whole number then we will have infinite interesting whole numbers and infinite uninteresting whole numbers (odd whole number ). 

 

Now if we say that  whole numbers between 1 to 100 are interesting whole number then we will have finite interesting whole numbers and infinite uninteresting whole numbers (whole numbers excluding 1 to 100 ).

 

So from second example we can say that -

If  there are finitely many uninteresting whole numbers, then there are infinitely many interesting whole numbers.

Ans- C

 

 

3 votes -- Dhananjay Kumar Sharma ( 24.9k points)
Selected Answer

If A is Blue (honest), then

  • Whatever A says about B and C must be True.
  • A says that B is White(liar) and C is Pink(alternating). So, if A is Blue, B must be White and C must be Pink.
  • B says that C is Pink. But B is a liar, and B agrees with A on the race of C (they must not agree). Thus, we reached a contradiction.

So, A can't be Blue.


If B is Blue (honest), then

  • Whatever B says about A and C must be True.
  • B says that A is Pink(alternating) and C is Pink(alternating). So, if B is Blue, A must be Pink and C must be Pink.
  • Since A is pink, it must lie about B, say the truth about C and then lie about itself. Which it does.
  • Since C is pink, it must lie about A, say the truth about B, and then lie about itself. Which it does.

So we see that Blue B, Pink A and Pink C is a possible solution!

Thus, option C is correct.


 

However, there is another option e, which says Cannot be determined from the above data.

So, what if there are multiple solutions that satisfy these constraints? If that is the case, option e will be correct. Sadly, there is no way of proving that no other solutions work except checking each one of them (using branch and bound to somewhat improve). Sadly, that will be lengthy.

Here is a Python3 program that finds all solutions to this problem: http://ideone.com/7EFXCn

 

7 votes -- Pragy Agarwal ( 19.3k points)
Selected Answer

The correct answer is option a) Only claim 1 follows.

$\text{Glitters}(x) \implies \text{ Gold}(x) \implies \lnot \text{ Silver}(x)$. Hence, Claim 1 follows. If something Glitters, it cannot be Silver.


For claim 2:

The set of things that Glitter could be empty.

We can still assert that All that Glitters is Gold, because nothing Glitters in the first place.

So, in the case when nothing Glitters, there is no Gold that Glitters. Glitters is still a subset of Gold, but there is no element in the subset Glitters.

16 votes -- Pragy Agarwal ( 19.3k points)
$$\require{enclose}\enclose{circle}{\matrix{\\\rm is~Gold\\\enclose{circle}{\matrix{\\\rm Glitters\\\,}}\\\,}}\quad\enclose{circle}{\matrix{\\\rm Silver\\\,}}$$

Ans will be (e)

glitter is subset of gold, So some gold glitter and some not glitter, So (2) follows

silver is totally other set, because when something glitters, it must be gold,and it is given that no gold is silver.  So, glittering element can never be silver Here (1) follows
2 votes -- srestha ( 54.8k points)
Selected Answer

option c ...If a person is kind, he is not known to be corrupt

Let

$C(x): x \text{ is known to be corrupt}$
$K(x): x \text{ is kind}$
$E(x): x \text{ will be elected}$

  • $S1: C(x) \to \neg E(x)$
  • $S2: K(x) \to E(x)$

S1 can be written as $E(x) \to \neg C(x)$ as $A \to B = \neg B \to \neg A$.
Thus, from S1 and S2,

$K(x) \to E(x) \to \neg C(x)$.

Thus we get C option.

21 votes -- Anoop Sonkar ( 4.8k points)

$\begin{align*} S_1 &= C \rightarrow \neg E\\ S_2 &= K \rightarrow E\\ \end{align*}$

so, writing them using primary operators :
$\begin{align*} S_1 &= \neg C \vee \neg E\\ S_2 &= \neg K \vee E\\ \end{align*}$

on using resolution principle
$\neg E$ and $E$ cancels each other out
and conclusion = $\neg C \vee \neg K$

which can also be written as $K \rightarrow \neg C$ which is translated into English as = option C

5 votes -- Amar Vashishth ( 27.9k points)
Selected Answer
Person 1, result is head. No doubt here as he is a truth teller. 
Person 2. result is head if and only if he is telling truth. He is telling lies. So, the truth is the opposite of his statement. We can analyze his statement as two
  1. If I'm telling the truth result is head 
  2. If result is head I'm telling the truth

Both these are of the form $A \rightarrow B = \neg A \vee B$. Now, the truth will be the negation of these statements which will be $A \wedge \neg B$ which can be expressed as

  1. I'm telling the truth and result is not head
  2. Result is head and I'm telling false

Both of these means, result is head. (Actually even if iff is replaced with if, answer would be A)

So, option A.

27 votes -- Arjun Suresh ( 286k points)

we do not know what is the person from whom those words are coming from, we can have two cases :

  1. Truth-teller : definitely implies that result of toss is Head.
  2. Liar : the reality will be the negation of the statement.

The negation of $(x\iff y)$ is Exactly one of $x$ or $y$ holds. So, we negate the statement : "The result of the toss is head if and only if I am telling the truth". This give rise to two possibilities

  • it is head and lie spoken
  • it is not head and truth spoken

clearly the second one cannot be true because it cannot be a Reality that the liar speaks the truth.

so, this imply that even if we negate the statement to see the reality or don't do that; The reality is that the toss yielded a Head.

answer = option A

24 votes -- Amar Vashishth ( 27.9k points)
Selected Answer
Let us denote sentences with variables F:Bank receipt is forged

L:Mr M is liable

B:He will go bankrupt

M:Bank loan him money

1.F->L

2.L->B

3.M->B'

4.M

From 3 and 4 modus ponens we get

5.B'

From 2 and 5 modus tollens we get

6.L'

From 1 and 6 modus tollens we get

F'

Ans is bank receipt is not forged
7 votes -- Pooja Palod ( 31.2k points)
Selected Answer

Option B should be the correct answer, that is A is a Knave & B is a Knight.

A must be either a Knight or a Knave.


Suppose A is a Knight, it means that the statement "We are both Knaves." must be true.

This is contradicting our assumption.

So the assumption that "A is a Knight" is not logically satisfiable simultaneously with the statement he made, which implies that A must be a Knave.


Now since A is a Knave, the statement made by him : "We are both Knaves." must be false.

The statement "We are both Knaves." will be false in any one of the following 3 conditions :

1. A is a Knight, B is a Knave.

2. A is a Knave, B is a Knight.

3. A is a Knight, B is a Knight.


Bus since we have already deduced that A is a Knave so in order to make the statement "We are both Knaves." false, we are only left with condition 2.

So B must be a Knight.

9 votes -- Anurag Pandey ( 12.8k points)
Selected Answer
$I_1$ is a correct inference. $I_2$ is not a correct inference as it was not mentioned what would have happened if it hadn't rained- They might have played or they might not have played.
16 votes -- Arjun Suresh ( 286k points)

Let us assume p=It rains,q=cricket match will not be played.

I1: If it rains then the cricket match will not be played   (p->q)

The cricket match was played. (~q)
Inference:  There was no rain.(~p)

p->q

~q


~p    (Modus tollens )

Thus I1 is an inferenece.

I2:can be written as 

p->q

 ~p


~q

Not an inference.

Hence answer is B 

3 votes -- Arnabi ( 6k points)
Selected Answer
It is told in the question "If the people suffer, the government will be unpopular". And "government will not be unpopular" means, people will not suffer.
It is like A->B is true and ~B is given. So, ~A must be true.

So, (a) is valid (always true).

Lets take the English meaning

Government will not be unpopular

$\implies$ People will not suffer
$\implies$ Either no inflation or government regulates it
$\implies$ If no regulation then no inflation
$\implies$ if no regulation then no wage or price rise

So, (b) and (d) are valid (always true) and (c) and (e) are not valid.
7 votes -- Arjun Suresh ( 286k points)

If $Mr.M$ is guilty, then no witness is lying unless he is afraid. There is a witness who is afraid. Which of the following statements is true?

(Hint: Formulate the problem using the following predicates
$G - Mr.M$ is guilty
$W(x) - x$ is a witness
$L(x) - x$ is lying
$A(x) - x$ is afraid )

  1. $Mr.M$ is guilty.
  2. $Mr.M$ is not guilty.
  3. From these facts one cannot conclude that $Mr.M$ is guilty.
  4. There is a witness who is lying.
  5. No witness is lying.

Which one of the first order predicate calculus statements given below correctly expresses the following English statement?

 Tigers and lions attack if they are hungry or threatened.

  1. ∀x[(tiger(x) ∧ lion(x)) → {(hungry(x) ∨ threatened(x)) → attacks(x)}]
  2. ∀x[(tiger(x) ∨ lion(x)) → {(hungry(x) ∨ threatened(x)) ∧ attacks(x)}]
  3. ∀x[(tiger(x) ∨ lion(x)) → {attacks(x) → (hungry(x) ∨ threatened(x))}]
  4. ∀x[(tiger(x) ∨ lion(x)) → {(hungry(x) ∨ threatened(x)) → attacks(x)}]

Identify the correct translation into logical notation of the following assertion.

    Some boys in the class are taller than all the girls

Note: $\text{taller} (x, y)$ is true if $x$ is taller than $y$.

  1. $(\exists x) (\text{boy}(x) \rightarrow (\forall y) (\text{girl}(y) \land \text{taller}(x, y)))$
  2. $(\exists x) (\text{boy}(x) \land (\forall y) (\text{girl}(y) \land \text{taller}(x, y)))$
  3. $(\exists x) (\text{boy}(x) \rightarrow (\forall y) (\text{girl}(y) \rightarrow \text{taller}(x, y)))$
  4. $(\exists x) (\text{boy}(x) \land (\forall y) (\text{girl}(y) \rightarrow \text{taller}(x, y)))$

Suppose the predicate $F(x, y, t)$ is used to represent the statement that person $x$ can fool person $y$ at time $t$. Which one of the statements below expresses best the meaning of the formula $$∀x∃y∃t(¬F(x,y,t))$$?

  1. Everyone can fool some person at some time
  2. No one can fool everyone all the time
  3. Everyone cannot fool some person all the time
  4. No one can fool some person at some time
Show that the conclusion $(r \to q)$ follows from the premises:

$p, (p \to q) \vee (p \wedge (r \to q))$

Choose the correct alternatives (More than one may be correct).

Indicate which of the following well-formed formulae are valid:

  1. $\left(P\Rightarrow Q\right) {\wedge} \left(Q \Rightarrow R\right) \Rightarrow \left(P \Rightarrow R\right)$
  2. $\left(P\Rightarrow Q\right) \Rightarrow \left( \neg P \Rightarrow \neg Q\right)$
  3. $\left(P{\wedge} \left(\neg P \vee  \neg Q\right)\right) \Rightarrow Q$
  4. $\left(P \Rightarrow R\right) \vee \left(Q \Rightarrow R\right) \Rightarrow \left(\left(P \vee Q \right)  \Rightarrow R\right)$

Answer the following:

Which of the following well-formed formulas are equivalent?

  1. $P \rightarrow Q$
  2. $\neg Q \rightarrow \neg P$
  3. $\neg P \vee Q$
  4. $\neg Q \rightarrow P$

What is the first order predicate calculus statement equivalent to the following?

"Every teacher is liked by some student"

  1. $∀(x)\left[\text{teacher}\left(x\right) → ∃(y) \left[\text{student}\left(y\right) → \text{likes}\left(y,x\right)\right]\right]$
  2. $∀(x)\left[\text{teacher}\left(x\right) → ∃(y) \left[\text{student}\left(y\right) ∧ \text{likes}\left(y,x\right)\right]\right]$
  3. $∃(y) ∀(x)\left[\text{teacher}\left(x\right) → \left[\text{student}\left(y\right) ∧ \text{likes}\left(y,x\right)\right]\right]$
  4. $∀(x)\left[\text{teacher}\left(x\right) ∧ ∃(y) \left[\text{student}\left(y\right) → \text{likes}\left(y,x\right)\right]\right]$

$\def\graph{\text{ Graph}}
\def\connected{\text{ Connected}}$

Let $\graph(x)$ be a predicate which denotes that $x$ is a graph. Let $\connected(x)$ be a predicate which denotes that $x$ is connected. Which of the following first order logic sentences DOES NOT represent the statement:

"Not every graph is connected"

 

  1. $\lnot \forall x\, \Bigl (\graph(x) \implies \connected(x) \Bigr )$
  2. $\exists x\, \Bigl (\graph(x) \land \lnot \connected(x) \Bigr )$
  3. $\lnot \forall x \, \Bigl ( \lnot \graph(x) \lor \connected(x) \Bigr )$
  4. $\forall x \, \Bigl ( \graph(x) \implies \lnot \connected(x) \Bigr )$

 

Let $p, q, r$ denote the statements ”It is raining”, “It is cold”, and “It is pleasant, respectively. Then the statement “It is not raining and it is pleasant, and it is not pleasant only if it is raining and it is cold” is represented by

  1. $(\neg p \wedge r) \wedge (\neg r \rightarrow (p \wedge q))$
  2. $(\neg p \wedge r) \wedge ((p \wedge q) \rightarrow  \neg r)$
  3. $(\neg p \wedge r) \vee ((p \wedge q) \rightarrow  \neg r)$
  4. $(\neg p \wedge r) \vee (r \rightarrow (p \wedge q))$

 

Let $p$, $q$ and $r$ be propositions and the expression $\left ( p\rightarrow q \right )\rightarrow r$ be a contradiction. Then, the expression $\left ( r\rightarrow p \right )\rightarrow q$ is

(A) a tautology.

(B) a contradiction.

(C) always TRUE when $p$ is FALSE.

(D) always TRUE when $q$ is TRUE.
The statement $\left ( ¬p \right ) \Rightarrow \left ( ¬q \right )$ is logically equivalent to which of the statements below?

I. $p \Rightarrow q$

II. $q \Rightarrow p$

III. $\left ( ¬q \right ) \vee p$

IV. $\left ( ¬p \right ) \vee q$

(A) I. only

(B) I. and IV. only

(C) II. only

(D) II. and III. only

Answers: Predicate Logic

Selected Answer

 

$\newcommand{m}{\text{Mr. } M}$If $\m$ is guilty, then if we pick a witness, we know that the witness won't lie unless he is afraid. If the witness is afraid, it may lie or it may lot lie (nothing is guaranteed).

However, unless we know what the victim said in the court (whether he said that $\m$ was guilty or not guilty), we can't say anything about $\m$.

All we know is that we've a witness who is afraid, so he may or may not lie in the court. We haven't been told anything about what actually happened in the court proceeding.

So, we can't logically conclude anything about $\m$ being guilty or not guilty.

Thus, options a and b are False.

Furthermore, that witness who was afraid, he may or may not lie. Since he is afraid, we know that he "can" lie, but we're not guaranteed that he will lie.

Thus, options d and e are False too.

This leaves option c, and as we have seen earlier, we cannot conclude anything about $\m$ being guilty or not guilty.

Hence, option c is the correct answer. 


Although not necessary, the logic equivalent of the given statement will be: $$\begin{array}{c} G \implies \lnot \exists x: \Bigl (W(x) \land L(x) \land \lnot A(x) \Bigr )\\[1em] \equiv\\[1em] G \implies \forall x: \Biggl (W(x) \implies \Bigl ( \lnot A(x) \implies \lnot L(x) \Bigr ) \Biggr ) \end{array}$$

8 votes -- Pragy Agarwal ( 19.3k points)

 

 

I think this is the approach for this question.

first statement is the correct answer for this question.

 

 

 

4 votes -- Ravishankar ( 63 points)
Selected Answer

The statement "Tigers and lions attack if they are hungry or threatened" means that if an animal is either tiger or lion, then if it is hungry or threatened, it will attack. So option (D) is correct. 
Don't get confused by "and" between tigers and lions in the statement. This "and" doesn't mean that we will write "tiger(x) ∧ lion(x) ", because that would have meant that an animal is both tiger and lion, which is not what we want.

http://www.cse.iitd.ac.in/~mittal/gate/gate_math_2006.html

11 votes -- Anu ( 10.2k points)
option D
3 votes -- Manali ( 2.8k points)
Selected Answer

Now many people get confused when to use ∧ and when to use →. This question tests exactly that. 
We use ∧ when we want to say that the both predicates in this statement are always true, no matter what the value of x is. We use → when we want to say that although there is no need for left predicate to be true always, but whenever it becomes true, right predicate must also be true. 
Now we have been given the statement "Some boys in the class are taller than all the girls". Now we know for sure that there is atleast a boy in class. So we want to proceed with "(∃x) (boy(x) ∧" and not "(∃x) (boy(x) →", because latter would have meant that we are putting no restriction on the existence of boy i.e. there may be a boy-less class, which is clearly we don't want, because in the statement itself, we are given that there are some boys in the class. So options (A) and (C) are ruled out. 
Now if we see option (B), it says, every y in class is a girl i.e. every person in class is a girl, which is clearly false. So we eliminate this option also, and we get correct option (D). Let us see option (D)explicitly also whether it is true or not. So it says that if person y is a girl, then x is taller than y, which is really we wanted to say. 
So option (D) is correct.

http://www.cse.iitd.ac.in/~mittal/gate/gate_math_2004.html

 

33 votes -- Anu ( 10.2k points)
(∃x)(boy(x) ⋀ (∀y)(girl(y) → taller(x, y)))

Should be the answer.
6 votes -- Arjun Suresh ( 286k points)
Selected Answer

 

F(x, y, t) = person x can fool person y at time t. 

For the sake of simplicity propagate negation sign outward by applying de morgan's law.

∀x∃y∃t(¬F(x,y,t)) = ¬∃x∀y∀t(F(x, y, t)) [By applying de morgan's law.]

Now converting ¬∃x∀y∀t(F(x, y, t)) in english is simple.

¬∃xyt(F(x, y, t)) = There doesn't exist a person who can fool everyone all the time.

Which means No one can fool everyone all the time.

So option B is correct.

4 votes -- Soumya Jain ( 565 points)

B is the correct answer. The trick is to bring the negate sign to the extreme left. Form a sentence without using negate and just negate that.

$\forall x \exists y \exists t(\neg F(x,y,t)) \\= \neg(\neg\forall x \neg \exists y \neg \exists t) (\neg F(x,y,t)) \\= \neg (\neg\forall x \neg \exists y \neg \exists t ( F(x,y,t))) \\= \neg (\exists x \forall y \forall t ( F(x,y,t)))$.

32 votes -- Bhagirathi Nayak ( 13.1k points)
Selected Answer

P1 :P

P2: (P → Q) ∨ (P ∧ (R → Q) )

so P1 ∧ P2 = [P . [(P' + Q) +(PR' +PQ)]

                 = [P . [P' + Q + PR'  +PQ]]

                 = [ PR' +PQ]

                 = P(R → Q)

7 votes -- Prashant Singh ( 47.5k points)
To prove any wff valid or tautology try to use this analogy.

Since implication A->B is FALSE only when A=T and B=F.So to prove any implication is valid or not try to get TRUE->FALSE if we succeed then it is not valid,if we not then wff is valid.

So for option A

substitute P=T and R=F

RHS P->R become FALSE

LHS (P->Q)^(P->R)

To get true here we need T^T so substitute Q=T which makes P->Q TRUE and P->R FALSE so T^F=F which makes LHS=FALSE.

Hence we are unable to get T->F which proves wff given in OPTION A is valid.

NOTE: we can use similar kind of logic to prove contradiction.
5 votes -- junaid ahmad ( 1.4k points)
Selected Answer
  1. P→Q    = P'+Q
  2. ¬Q→¬P=Q+P'
  3. ¬PVQ   =P'+Q
    so A,B,C are equivalent .
2 votes -- kunal ( 20.3k points)
Selected Answer

Answer is B. In simpler way we can say If X is a teacher then there exists some Y who is a student and likes X.

A choice:  If X is a teacher, then there exists a Y such that if Y is a student, then Y likes X. 
C choice: There exist a student who likes all teachers.
D choice: Everyone is a teacher and there exists a Y such that if Y is student then y likes X. Assuming one cannot be both student and teacher at same time, this just means, everyone is a teacher. 

 

12 votes -- Manali ( 2.8k points)
Selected Answer
D says "all graphs are not connected"  but the question says " not every graph is connected" .i.e " there exists at least one graph which is not connected". Hence the answer is D
13 votes -- Manali ( 2.8k points)
Just writing to simplify each options

A)¬∀x( Graph(x)⟹ Connected(x))

it is not the case that every graph then it will be connected,which implies that

some graph my be disconnected.

 B)∃x( Graph(x)∧¬ Connected(x))

there exists some graph which are disconnected which implies

not every graph is connected.

C)¬∀x(¬ Graph(x)∨ Connected(x))

here no need to express it in english just solve first using

de morgn's law we will get it as option B)

 

D)∀x( Graph(x)⟹¬ Connected(x))

for all graph it is always disconnected...makes it FALSE

ANSWER D

∀x( Graph(x)⟹¬ Connected(x))∀x( Graph(x)⟹¬ Connected(x))∀x( Graph(x)⟹¬ Connected(x))∀x( Graph(x)⟹¬ Connected(x))∀x( Graph(x)⟹¬ Connected(x))
¬∀x(¬ Graph(x)∨ Connected(x))¬∀x(¬ Graph(x)∨ Connected(x))¬∀x(¬ Graph(x)∨ Connected(x))¬∀x(¬ Graph(x)∨ Connected(x))¬∀x(¬ Graph(x)∨ Connected(x))¬∀x(¬ Graph(x)∨ Connected(x))
3 votes -- sourav. ( 8.4k points)
$(\sim p \wedge r) \wedge (\sim r \rightarrow (p \wedge q))$

Answer is A
4 votes -- Prashant Singh ( 47.5k points)
option A seems to be correct.
2 votes -- Swapnil ( 1.9k points)
given (P-->Q)-->R is false..hence it is possible only when R is FALSE and (P-->Q) is TRUE

now even without checking any other option we can directly conclude option D is correct as (R-->P)-->Q can be written as

~(R-->P) v Q..which is TRUE whenever Q is TRUE

hence option (D)
5 votes -- sriv_shubham ( 2.4k points)
Selected Answer
~P--> ~Q  it can also be written as P v ~Q so statement 3 is correct

now taking the contrapositive of ~P--> ~Q we get Q-->P hence statement 2 is correct

So the answer is

OPTION (D)
6 votes -- sriv_shubham ( 2.4k points)
Given statement : ~p $\Rightarrow$ ~q

= ~(~p) $\vee$ ~q

= p $\vee$ ~q

= ~q $\vee$ p

= q $\Rightarrow$ p

$\therefore$ D should be answer.
2 votes -- Kantikumar ( 3.3k points)

Consider two well-formed formulas in propositional logic

$F1: P \Rightarrow \neg P$          $F2: (P \Rightarrow \neg P) \lor ( \neg P \Rightarrow P)$

Which one of the following statements is correct?

  1. F1 is satisfiable, F2 is valid
  2. F1 unsatisfiable, F2 is satisfiable
  3. F1 is unsatisfiable, F2 is valid
  4. F1 and F2 are both satisfiable
Choose the correct alternatives (more than one may be correct) and write the corresponding letters only:

If $F_1$, $F_2$ and $F_3$ are propositional formulae such that $F_1 \land F_2 \rightarrow F_3$ and $F_1 \land F_2 \rightarrow \sim  F_3$ are both tautologies, then which of the following is true:

(a). Both $F_1$ and $F_2$ are tautologies

(b). The conjunction $F_1 \land F_2$ is not satisfiable

(c). Neither is tautologous

(d). Neither is satisfiable

(e). None of the above.

$P$ and $Q$ are two propositions. Which of the following logical expressions are equivalent?

  1. $P ∨ \neg Q$
  2. $\neg(\neg P ∧ Q)$
  3. $(P ∧ Q) ∨ (P ∧ \neg Q) ∨ (\neg P ∧ \neg Q)$
  4. $(P ∧ Q) ∨ (P ∧ \neg Q) ∨ (\neg P ∧ Q)$

 

  1. Only I and II
  2. Only I, II and III
  3. Only I, II and IV
  4. All of I, II, III and IV

Choose the correct alternatives (more than one may be correct) and write the corresponding letters only:

Which of the following is/are a tautology?

  1. $a \vee b \to b \wedge c$
  2. $a \wedge b \to b \vee c$
  3. $a \vee b \to \left(b \to c \right)$
  4. $a \to b \to \left(b \to c \right)$

Let $a, b, c, d$ be propositions. Assume that the equivalence $a ⇔ ( b \vee \neg b)$ and $b ⇔c$ hold. Then the truth-value of the formula $(a ∧ b) → (a ∧ c) ∨ d$ is always

  1. True
  2. False
  3. Same as the truth-value of $b$
  4. Same as the truth-value of $d$

Consider the following expressions:

  1. $false$
  2. $Q$
  3. $true$
  4. $P\vee Q$
  5. $\neg Q\vee P$

The number of expressions given above that are logically implied by $P \wedge (P \Rightarrow Q)$ is ___________.

 

What is logically equivalent to "If Kareena and Parineeti go to the shopping mall then it is raining":

  1. If Kareena and Parineeti do not go to the shopping mall then it is not raining.
  2. If Kareena and Parineeti do not go to the shopping mall then it is raining.
  3. If it is raining then Kareena and Parineeti go to the shopping mall.
  4. If it is not raining then Kareena and Parineeti do not go to the shopping mall.
  5. None of the above.
Show that proposition $C$ is a logical consequence of the formula

$$A\wedge \left(A \to \left(B \vee C\right)\right) \wedge \left( B \to \neg A\right)$$

using truth tables.

The binary operation □ is defined as follows

                                                                                                                                                                                                                                                                           

P Q P □ Q
T T T
T F T
F T F
F F T

Which one of the following is equivalent to $P \vee Q$?

  1.    $\neg Q □ \neg P$
  2.    $P□\neg Q$
  3.    $\neg P□Q$
  4.    $\neg P□ \neg Q$
Show that the formula $\left[(\sim p \vee q) \Rightarrow (q \Rightarrow p)\right]$ is not a tautology.

Let $A$ be a tautology and $B$ any other formula. Prove that $(A \vee B)$ is a tautology.
If the proposition $\lnot p \to v$ is true, then the truth value of the proposition $\lnot p \lor \left ( p \to q \right )$, where $\lnot$ is negation, $\lor$ is inclusive OR and $\to$ is implication, is

a) True
b) Multiple Values
c) False
d) Cannot be determined

Which of the following propositions is a tautology?

  1. $(p \vee q) \rightarrow p$
  2. $p \vee (q \rightarrow p)$
  3. $p \vee (p \rightarrow q)$
  4. $p \rightarrow (p \rightarrow q)$

Which of the following is false? Read $\wedge$ as AND, $\vee$ as OR, $\sim$ as NOT,  $\rightarrow$ as one way implication and $\leftrightarrow$ as two way implication

  1. $((x \rightarrow y) \wedge x) \rightarrow y$

  2. $((\sim x \rightarrow y) \wedge (\sim x \rightarrow \sim y)) \rightarrow x$

  3. $(x \rightarrow (x \vee y))$

  4. $((x \vee y) \leftrightarrow (\sim x \rightarrow \sim y))$

 

Consider the following statements:

  • P: Good mobile phones are not cheap
  • Q: Cheap mobile phones are not good


L: P implies Q
M: Q implies P
N: P is equivalent to Q

Which one of the following about L, M, and N is CORRECT?

  1. Only L is TRUE.
  2. Only M is TRUE.
  3. Only N is TRUE.
  4. L, M and N are TRUE.

Which one of the following propositional logic formulas is TRUE when exactly two of $p,q$ and $r$ are TRUE?

  1. $(( p  \leftrightarrow q)  \wedge  r)  \vee  (p \wedge q \wedge  \sim r)$
  2. $( \sim (p \leftrightarrow q) \wedge r)\vee (p \wedge q \wedge \sim r)$
  3. $( (p \to q) \wedge r) \vee (p \wedge q \wedge \sim r)$
  4. $(\sim (p \leftrightarrow q) \wedge r) \wedge (p \wedge q \wedge \sim r) $

What is the converse of the following assertion?

  • I stay only if you go
  1. I stay if you go
  2. If I stay then you go
  3. If you do not go then I do not stay
  4. If I do not stay then you go
Let p, q, r and s be four primitive statements. Consider the following arguments:

P:  [(¬p v q) ∧ (r → s) ∧ (p v r)] → (¬s → q)
Q:  [(¬p ∧q) ∧ [q → (p → r)]] → ¬r
R:  [[(q ∧ r) → p] ∧ (¬q v p)] → r
S:  [p ∧ (p → r) ∧ (q v ¬ r)] → q

Which of the above arguments are valid?

P and Q only

P and R only

P and S only

P, Q, R and S

"If X then Y unless Z" is represented by which of the following formulas in prepositional logic? ("$\neg$" is negation, "$\land$" is conjunction, and "$\rightarrow$" is implication)

  1. $(X\land \neg Z) \rightarrow Y$
  2. $(X \land Y) \rightarrow \neg Z$
  3. $X \rightarrow(Y\land \neg Z)$
  4. $(X \rightarrow Y)\land \neg Z$
Determine whether each of the following is a tautology, a contradiction, or neither ("$\lor$" is disjunction, "$\land$" is conjunction, "$\rightarrow$" is implication, "$\neg$" is negation, and "$\leftrightarrow$" is biconditional (if and only if).

$A \leftrightarrow (A \lor A)$

$(A \lor B) \rightarrow B$

$A \land (\neg (A \lor B))$
Let P, Q and R be three atomic propositional assertions. Let X denote ( P ∨ Q ) → R and Y denote (P → R) ∨ (Q → R). Which one of the following is a tautology?

X ≡ Y

X → Y

Y → X

¬Y → X

Which one of the following is NOT equivalent to $p ↔ q$?

  1. $(\neg p ∨ q) ∧ (p ∨ \neg q)$
  2. $(\neg p ∨ q) ∧ (q → p)$
  3. $(\neg p ∧ q) ∨ ( p ∧ \neg q)$
  4. $(\neg p ∧ \neg q) ∨ (p ∧ q)$

The following propositional statement is  $\left(P \implies \left(Q \vee R\right)\right) \implies \left(\left(P \wedge Q \right)\implies R\right)$

  1.    satisfiable but not valid
  2.    valid
  3.    a contradiction
  4.    None of the above

Consider the following propositional statements:
P1 : ((A ∧ B) → C)) ≡ ((A → C) ∧ (B → C))
P2 : ((A ∨ B) → C)) ≡ ((A → C) ∨ (B → C))

Which one of the following is true?

  1.    P1 is a tautology, but not P2
  2.    P2 is a tautology, but not P1
  3.    P1 and P2 are both tautologies
  4.    Both P1 and P2 are not tautologies

The proposition $p \wedge (\sim p \vee q)$ is:

  1. a tautology

  2. logically equivalent to $p \wedge q$

  3. logically equivalent to $p \vee q$

  4. a contradiction

  5. none of the above

The following resolution rule is used in logic programming.
Derive clause (P ∨ Q) from clauses (P ∨ R), (Q ∨ ¬R)
Which of the following statements related to this rule is FALSE?

  1. ((P ∨ R) ∧ (Q ∨ ¬R)) ⇒ (P ∨ Q) is logically valid
  2. (P ∨ Q) ⇒ ((P ∨ R)) ∧ (Q ∨ ¬R)) is logically valid
  3. (P ∨ Q) is satisfiable if and only if (P ∨ R) ∧ (Q ∨ ¬R) is satisfiable
  4. (P ∨ Q) ⇒ FALSE if and only if both P and Q are unsatisfiable

Let $p$ and $q$ be propositions. Using only the Truth Table, decide whether 

$p \Longleftrightarrow q$ does not imply $p \to \lnot q$

is True or False.

Answers: Propositional Logic

Selected Answer
F1: P => ⌝ P

    =⌝ P V ⌝ P

    =⌝P      can be true when P is false ( Atleast one T hence satisfiable)

F2:    (P => ⌝ P)V(⌝ P=>P)

        =⌝ P V (P V P)

        = ⌝ P V P

         =T

VALID

Option A
16 votes -- Manali ( 2.8k points)
Selected Answer
Valid : A wff which is always true(tautology) is valid. i.e., its value is true for any set of assignment to its variables.

Satisfiable : A wff which is not a contradiction(always false) is satisfiable. It may be a tautology.
2 votes -- Kantikumar ( 3.3k points)
Selected Answer
answer = option B

$$\text{False} \rightarrow \text{anything} = \text{True, always}$$
9 votes -- Amar Vashishth ( 27.9k points)
(B) Only I, II and III. Draw truth table to check, evaluating individual expression will consume lot of time with no guaranteed answer.
11 votes -- Keith Kr ( 6.2k points)

answer B

I. P ~Q
II. ~ ( ~PQ) apply De Morgan's law. we get  P ~Q
III. (PQ)(P~ Q)( ~P ~Q)

=[(PQ)(P~ Q)]( ~P ~Q)

=[P(QV ~Q)]∨( ~P ~Q)

=P∨( ~P ~Q)

= P ~Q
 

5 votes -- Anu ( 10.2k points)
Selected Answer
Answer: B

$\left(a \wedge b \right) \to b \vee c$
$\implies \neg \left(a \wedge b \right) \vee b \vee c$
$\implies \neg a \vee \neg b \vee b \vee c$
$\implies T$

Option A is not TRUE when C is FALSE
Option C is not TRUE when b is TRUE and C is FALSE
Option D is not TRUE when a and b are TRUE and C is FALSE.
8 votes -- Rajarshi Sarkar ( 34.3k points)
Selected Answer

Given that, a\Leftrightarrowb∨~b

It is equivalent to a\LeftrightarrowTRUE

\therefore (a∧b)\rightarrow((a∧c)∨d)

wkt, 1∧x = x

\therefore (a∧b) = 1∧b = b

similarly, 1∧c = c

We now have, b \rightarrow(c∨d)

Which can be written as,

~b∨c∨d

We also know that b\Leftrightarrowc

\therefore ~b∨c = TRUE

\therefore TRUE∨d = TRUE

And hence answer is option a

16 votes -- Gate_15_isHere ( 639 points)
Selected Answer

$4$ should be the correct answer.

58 votes -- Anurag Pandey ( 12.8k points)
ans :4

all except the option i satisfies.

P and Q -> true, P or Q,~Q or P,Q
8 votes -- viv696 ( 2.1k points)
Selected Answer

Answer will be (D)

"If Kareena and Parineeti go to the shopping mall then it is raining"

Let Kareena and Parineeti go to the shopping mall =p

 it is raining = q

Now the statement told that p→q

a.If Kareena and Parineeti do not go to the shopping mall then it is not raining.

      i.e. ~p→ ~q

    So, it is not matching with the previous implication

b.If Kareena and Parineeti do not go to the shopping mall then it is raining.

    that means ~p→ q

    it is also not matching

c. If it is raining then Kareena and Parineeti go to the shopping mall.

  that means q→p . So, it is also false

d. If it is not raining then Kareena and Parineeti do not go to the shopping mall.

  i.e. ~q → ~p = q V ~p = p→q

So, correct option is (D)

 

12 votes -- srestha ( 54.8k points)
Selected Answer
A^(A---> (B v C)) ^ ( B ---> ~ A)
= A(A' + B + C)(A' + B')
= AB'(A' + B + C)
= AB'C
C is logical consequence of a formula X if,
 X ----> C is true

here X = A^(A---> (B v C)) ^ ( B ---> ~ A)
            = AB'C
cheking , AB'C  ----> C
=  (AB'C)' + C
=  A' + B + C' + C
= 1

C is logical consequence of A^(A---> (B v C)) ^ ( B ---> ~ A)..
8 votes -- Digvijay ( 46k points)
$A$ $B$ $C$ $A\to \left(B \vee C\right)$ $B\to\neg A$ $A\wedge \left(A \to \left(B \vee C\right)\right) \wedge \left( B \to \neg A\right)$ $C$
T T T T F F T
T T F T F F T
T F T T T T T
T F F F T F T
F T T T T F T
F T F T T F T
F F T T T F T
F F F T T F T
  1. Logical consequence (also entailment) is one of the most fundamental concepts in logic. It is the relationship between statements that holds true when one logically "follows from" one or more others.
2 votes -- Anu ( 10.2k points)
Selected Answer
Answer is B because the truth values for option B is same as that of P "or" Q.

The given truth table is for $Q \implies P$ which is $\bar Q+P$.

Now, with A option we get $\bar{ \bar{Q}}+P = P + Q$
12 votes -- chetna ( 465 points)
The answer will be A.

The given truth table is of the form P ⇐ Q which is Q'+P.

and option A satisfies that as Q' ⇐ P' is Q' + P.
2 votes -- Gate Keeda ( 18.8k points)
Selected Answer
a.

$\left[(\sim p \vee q) \Rightarrow (q \Rightarrow p)\right] \\ = \sim (\sim p \vee q)) \vee (q \Rightarrow p) \\= (p \wedge \sim q) \vee (\sim q \vee p) \\= p \vee \sim q$.

Hence not tautology.

b.

$(A \vee B) = T \vee B = T$
5 votes -- Arjun Suresh ( 286k points)
Selected Answer

Cannot be determined.

From the axiom $\lnot p \to v$, we can conclude that $p + v$.

So, $p$ can be True or False, i.e. nothing can be said about it's value.

$$\begin{align}
&\lnot p \lor (p \to q)\\[1em]
\equiv& \lnot p \lor ( \lnot p \lor q)\\[1em]
\equiv&\lnot p \lor q
\end{align}$$

 

Since nothing can be said about the Truth value of $p$, it implies that $\lnot p \lor q$ can also be True or False.

Hence, the value cannot be determined.

19 votes -- Pragy Agarwal ( 19.3k points)
Selected Answer
C) P OR (P -->Q) = P OR (NOT P OR Q)

                          =(P OR NOT P) OR Q                  Associativity rule

                          =T OR Q                                     

                          =T
10 votes -- Manali ( 2.8k points)
Selected Answer
OPTION D...  when x= F  & y=F
9 votes -- Manali ( 2.8k points)
Selected Answer
D)
Lets break the given compound statements into atomic statements.

A : Good mobile phones.
B : Cheap mobile phones.
 

P : A --> ~B    <=> ~A v ~B
Q : B --> ~A    <=> ~B v ~A <=> ~A v ~B (Disjunction is commutative)
Hence P <=> Q      ( P is equivalent to Q, which means P imples Q ,and Q implies P)
19 votes -- Srinath Jayachandran ( 3.7k points)
Selected Answer

A. will be true if P,Q,R are true,((p ↔q) ∧ r) will return true. So "exactly two" is false
C. if only r is true and p and q are false, first part of implication itself will result in true
D. if r is true or false, this returns false due to r and ~r present in conjunction. So, this is a CONTRADICTION. 

B is the answer. B is true if p is TRUE and q is FALSE or vice verse, and r is true or if p and q are TRUE and r is FALSE.

PS: Actually the question should have been "TRUE ONLY when exactly two of p,q and r are TRUE"

11 votes -- Manu Thakur ( 5.8k points)
the proposition logic formula is required to be true when any two of the p q r are true .so let's make truth table taking any two of p q r as true

P  Q  R

0   1   1

1    1    0

1     0    1

now write down the POS for above truth table

i.e. P'QR+PQR'+PQ'R  .

option B will satisfy the above POS expression hence answer.
4 votes -- preetam ( 137 points)
Selected Answer

I stay only if you go is equivelent to   If I stay then you go.

  A only if B  => A->B

A= "I stay" and B= "You go"

converse( A->B)  =  B->A

" If you go then I stay "

Answer is  A

11 votes -- Manali ( 2.8k points)
Selected Answer

An argument form is valid if no matter what propositions are substituted for the propositional variables in its premises, the conclusion is true if the premises are all true. i.e. $$\left( p_1 \wedge p_2 \wedge \dots \wedge p_n \right ) \rightarrow q$$ is a tautology.

12 votes -- Amar Vashishth ( 27.9k points)

P:  [(¬p v q) ∧ (r → s) ∧ (p v r)] → (¬s → q)

This must be valid ( All options contains P) No need to evaluate.

R:  [[(q ∧ r) → p] ∧ (¬q v p)] → r ->

This is invalid, Put q = False, P= True, R = False to derive "False" result !

S:  [p ∧ (p → r] ∧ (q v ¬ r)] → q This is valid !

->

p

P-> r

-------

r

q v ¬ r

----------

q

 

So Answer ->

3) P and S only
6 votes -- Akash ( 41.5k points)
Selected Answer

while ( not z ) {

    if (X) then

         Y

}

or

unless( z ) {

    if (X) then

         Y

}

this is what it means in programming. if you want to execute statement Y then X must be True and Z False,

which is equivalent to (X AND NOT Z)-->Y

option A

30 votes -- Vikrant Singh ( 13.4k points)
Answer is a) (X∧¬Z)→Y

((refer page 6,7 Discrete Math,ed 7,Kenneth H Rosen))

Implication "P implies Q" i.e (p→Q),where P is premise and Q is Conclusion, can be equivalently expressed in many ways. And the two equivalent expression relevant to the question are as follows

one is " if P then Q "

another is  "Q unless ¬P"  

both of these are equivalent to the propositional formula (P→Q),

Now compare "If X then Y unless Z" with  "Q unless ¬P" , here (¬P = Z) so (P = ¬Z) and (Q = Y)

compare with "if P then Q" , here (P = X) , (Q= Y)

So we get premise P= 'X' and '¬Z' ,conclusion Q = 'Y'

Equivalent propositional formula (X∧¬Z)→Y

EDIT:someone messaged me that i have taken "If X then (Y unless Z)" in above explanation and how to know if we take "(If X then Y) unless Z" or "If X then (Y unless Z)". So let me show both way gives same answer.

"(If X then Y) unless Z"  ⇔  "(X→Y)unless Z" ⇔ "¬Z→(X→Y)" ⇔ "¬Z→(¬X ⋁ Y)" ⇔ "Z ⋁ ¬X ⋁ Y"

 ⇔ "¬(X∧¬Z) ⋁ Y " ⇔ "(X∧¬Z)→Y"
8 votes -- Sourav Das ( 223 points)
Selected Answer

This can be solved by Truth table. But there is something else which can be done quickly. See what each formula means:

1.  A(AA) It says if A then (A or A) and if (A or A) then A. Always a tautology

2.  (AB)B If A or B then B. No guarantee that if only A is true, B need to be true. Hence neither tautology nor contradiction

3.  A(¬(AB)) When A is true ¬(A∨B) will be false. So, this formula is a contradiction

15 votes -- Arjun Suresh ( 286k points)

We can also solve it by the properties.

1.) A <--> ( A v A)

A <--> A (Since A + A is A.)

AA + A'A' ( Since A <--> B is AB +A'B')

Therefore A + A' is 1. Which is a Tautology.

2.) (A v B) --> B

A'B' + B ( Since A-->B is A' + B)

A' + B ( By law of Absorption.)

Hence it is neither Tautology nor Contradiction and Hence Contingency.

3.) A ∧ ( ¬ ( A v B))

Which can be written as

A.(A + B)'

A.(A'B') ( By de-morgan's Law)

A.A'B' = 0.

Hence it is a Contradiction.

 

  1.  
3 votes -- Gate Keeda ( 18.8k points)
Selected Answer
X = (P ⋁ Q) → R

= ~(P ⋁ Q) ⋁ R

= (~P ⋀ ~Q) ⋁ R

= (~P ⋁ R) ⋀ (~Q ⋁ R)

= (P →  R) ⋀ (Q → R)

So, X  → Y is true as (A ⋀ B) → (A ⋁ B) is always TRUE but reverse implication is not always true.

Hence, B.
12 votes -- Arjun Suresh ( 286k points)
Selected Answer
p ↔ q

= (p→ q) ∧ (q→p)

= (⏋p ∨ q) ∧ (q → p)         ( As p→ q = ⏋p ∨ q )

=(⏋p ∨ q) ∧ (⏋q ∨ p)

=(⏋p ∧ ⏋q) ∨ (p ∧ q)

So, answer C
18 votes -- Priya_das ( 765 points)
option c
2 votes -- GATERush ( 1.1k points)
Selected Answer
Answer a

It is false when P = T, Q = T, R = F

It is true (satisfiable) when P = T. Q = T, R = T
10 votes -- Anu ( 10.2k points)
Selected Answer
(D) Both P1 and P2 are not tautologies.

P1: If A is true and B is false, LHS of P1 is true but RHS becomes false. Hence not tautology.

P2: Forward side is true. But reverse side is not true. When A is false and B is true and C is false, RHS is true but LHS is false.

LHS of P2 can be simplified as follows:

((A∨B) → C) = (~(A∨B) ∨ C) = (~A ∧~B) ∨C) = (~A ∨C) ∧ (~B ∨C) = (A→C) ∧ (B→C)
9 votes -- Arjun Suresh ( 286k points)
Selected Answer
OPTION (B)
8 votes -- Manali ( 2.8k points)
p ^ (~p v q)

= (p ^ ~p) v (p ^ q)

= False V (p^q)

= (p^q)
3 votes -- Mridul Sachan ( 167 points)
TAKING OPTION (A)

((P ∨ R) ∧ (Q ∨ ¬R)) ⇒ (P ∨ Q) is logically valid.

((P + R) . (Q + ¬R))' + (P + Q)

((P' R') + (Q' R)) + (P + Q)

P + R' + Q + R

= 1 + P + Q = 1 SO TAUTOLOGY MEANS VALID. True

Option B

(P ∨ Q) ⇒ ((P ∨ R)) ∧ (Q ∨ ¬R)) is logically valid

(P  + Q)' + ((P + R)) .  (Q + ¬R))

P'Q' + PQ + PR' +QR WHICH IS CONTISGENCY SO ONLY SATISFIABLE.

So option B is false.
6 votes -- Prashant Singh ( 47.5k points)
Option B is false...
   ((P ∨ R)) ∧ (Q ∨ ¬R))
=  (P∧ ¬R) ∨ (Q ∧ R)
(P∨Q) doesn't imply (P∧ ¬R) ∨ (Q ∧ R)
4 votes -- Digvijay ( 46k points)
Selected Answer
$p$ $q$ $p \leftrightarrow q$ $p \to \lnot q$ $\left( p \leftrightarrow q \right ) \to \left ( p \to \lnot q \right )$
0 0 1 1 1
0 1 0 1 1
1 0 0 1 1
1 1 1 0 0

 

So, "imply" is FALSE making does not imply TRUE. 

9 votes -- Arjun Suresh ( 286k points)

Three candidates, Amar, Birendra and Chanchal stand for the local election. Opinion polls are conducted and show that fraction $a$ of the voters prefer Amar to Birendra, fraction $b$ prefer Birendra to Chanchal and fraction $c$ prefer Chanchal to Amar. Which of the following is impossible?

  1. $(a, b, c) = (0.51, 0.51, 0.51);$
  2. $(a, b, c) =(0.61, 0.71, 0.67);$
  3. $(a, b, c) = (0.68, 0.68, 0.68);$
  4. $(a, b, c) = (0.49, 0.49, 0.49);$
  5. None of the above.
Let $p, q, r, s$ represents the following propositions.

$p:x\in\left\{8, 9, 10, 11, 12\right\}$

$q:$ $x$ is a composite number.

$r:$ $x$ is a perfect square.

$s:$ $x$ is a prime number.

The integer $x\geq2$ which satisfies $\neg\left(\left(p\Rightarrow q\right) \wedge \left(\neg r \vee \neg s\right)\right)$ is ____________.

Answers:

Selected Answer

6 preference order for voter are possibe:

ABC.ACB,BCA,BAC,CAB,CBA also Given that 

a=ABC+ACB+CAB(A prefer over B)   ------(1)

b=BCA+BAC+ABC(B prefer over C)  -------(2)

c=CAB+CBA+BCA(C prefer over A)  -------(3)

Adding 1,2 and 3 we get 

a+b+c=2(ABC+BCA+CAB)+ACB+BAC+CAB

Now we know that ABC+ACB+BAC+BCA+CAB+CBA=1 therefore

[ABC+ACB+BAC+BCA+CAB+CBA]<[2(ABC+BCA+CAB)+ACB+BAC+CAB]<2(ABC+ACB+BAC+BCA+CAB+CBA)

Hence we can say that value of a+b+c must be between 1 and 2 

option c value greater than 2 hence correct answer is c

 

6 votes -- Saurav Shrivastava ( 1.2k points)
Selected Answer

~((p → q) $\wedge$ (~r $\vee$~s))
= (~(~p $\vee$ q)) $\vee$ (~(~r $\vee$ ~s))
=(p $\wedge$ ~q) $\vee$ (r $\wedge$ s)

Which can be read as (x∈ {8,9,10,11,12} AND x is not a composite number) OR (x is a perfect square AND x is a prime number)
Now for

  • x is a perfect square and x is a prime number.
  • it can never be true as every square has atleast 3 factors, 1,x and x.

So second condition can never be true..
That implies the first condition must be true..
x∈{8,9,10,11,12} AND x is not a composite number

But here only 11 is not a composite number.. so only 11 satisfies the above statement.. Hence,

ANSWER 11.

30 votes -- Abhilash Panicker ( 8.7k points)
Ans is 11
5 votes -- Sibarpit ( 173 points)
A binary operation $\oplus$ on a set of integers is defined as $x \oplus y = x^{2}+y^{2}$. Which one of the following statements is **TRUE** about $\oplus$?


(A) Commutative but not associative

(B) Both commutative and associative

(C) Associative but not commutative

(D) Neither commutative nor associative

Consider the set \(\{a, b, c\}\) with binary operators \(+\) and \(*\) defined as follows.

 +   a   b   c 
 a b a c
 b a b c
 c a c b

 

 *   a   b   c 
a a b c
b b c a
c c c b

For example, \(a + c = c, c + a = a, c * b = c\) and \(b * c = a\).

Given the following set of equations:
$$(a * x) + (a * y) = c \\
(b * x) + (c * y) = c$$
The number of solution(s) (i.e., pair(s) (x, y) that satisfy the equations) is

  1. 0
  2. 1
  3. 2
  4. 3
On the set $N$ of non-negative integers, the binary operation ______ is associative and non-commutative.

For the set N of natural numbers and a binary operation f : N x N → N, an element z ∊ N is called an identity for f, if f (a, z) = a = f(z, a), for all a ∊ N. Which of the following binary operations have an identity?

  1. f (x, y) = x + y - 3
  2. f (x, y) = max(x, y)
  3. f (x, y) = xy

 

  1. I and II only
  2. II and III only
  3. I and III only
  4. None of these

The binary operator ≠ is defined by the following truth table.

p q p ≠ q
0 0 0
0 1 1
1 0 1
1 1 0

Which one of the following is true about the binary operator ≠?

  1. Both commutative and associative
  2. Commutative but not associative
  3. Not commutative but associative
  4. Neither commutative nor associative

Answers: Binary Operation

Selected Answer
Answer is (A) Commutative but not associative.

$y \oplus x = y^2 + x^2 = x \oplus y$. Hence, commutative.

$ (x \oplus y) \oplus z = (x^2 + y^2) \oplus z = (x^2 + y^2)^2 + z^2$
$ x \oplus (y \oplus z) = x \oplus (y^2 + z^2) = x^2 + (y^2 + z^2)^2$

So, $( (x \oplus y) \oplus z) \neq (x \oplus (y \oplus z))$, hence not associative.
15 votes -- Arjun Suresh ( 286k points)
Selected Answer

consider each pair 

1. (a,a )   (a*a) +(a*a) = a+a = b   $\neq$ c so (a,a) is not possible 

2. (a,b)   (a*a) + (a*b) = a +b = a $\neq$c  so (a,b) is not possible 

3. (a,c)    (a*a)+(a*c) = a+c = c

               (b*a) +(c*c) = b + b =b $\neq$c , so (a,c) is not possible 

4. (b,a)   (a*b) +(a*a) = b +a = a $\neq$c , so (b,a) is not possible

5. (b,b)   (a*b) + (a*b) = b+b =b $\neq$c , so (b,b) is not possible

6. (b,c)    (a*b) + (a*c) = b + c = c

                 (b*b) + (c*c) = c+b = c , so (b,c) is a solution

7. (c,a)     (a*c) + (a*a) = c+a = a $\neq$c, so (c,a) is not possible

8.(c,b)      (a*c) + (a*b) = c+b = c 

                  (b*c) +(c*b) = a+c = c , so (c,b) is a solution

9. (c,c)      (a*c) +(a*c) =c+c= b $\neq$c, so (c,c) is not possible

so no of possible solution is 2

9 votes -- Praveen Saini ( 53k points)
Selected Answer
Define Binary operation $*$ on $(a,b)$ as : $a*b = a$

1. It is associative : $(a*b)*c = a*c = a$, and $a*(b*c) = a*b = a$

2. It is not commutative : $a*b = a$, whereas $b*a = b$.
11 votes -- Happy Mittal ( 10.7k points)

The most important associative operation that's not commutative is function composition.

If you have two functions f and g, their composition, usually denoted f∘g, is defined by 

                (f∘g)(x)=f(g(x)).
It is associative, (f∘g)∘h=f∘(g∘h),

but it's usually not commutative. f∘g is usually not equal to g∘f. 

 

For our case suppose $\forall$x $\in$ N of non-negative integers, if f(x)=x2 and g(x)=x+1, then (f∘g)(x)=(x+1)2 while  (g∘f)(x)=x2+1, and they're different functions.

 

4 votes -- Rajesh Pradhan ( 16.9k points)
Selected Answer

Answer: A

I. Identity element is 3.

II. Identity element is 1.

III. There is no identity element. (xy ≠ yx, when x ≠ y)

13 votes -- Rajarshi Sarkar ( 34.3k points)
Selected Answer
option A :  as it is XOR operation
11 votes -- GATERush ( 1.1k points)

Let # be the binary operator defined as

X#Y = X'+Y' where X and Y are Boolean variables.

Consider the following two statements.

(S1) (P#Q)#R = P#(Q#R)

(S2) Q#R = (R#Q)

Which are the following is/are true for the Boolean variables P, Q and R?

 

  1. Only S1 is true
  2. Only S2 is true
  3. Both S1 and S2 are true
  4. Neither S1 nor S2 are true

Answers: Boolean Algebra

Selected Answer
Answer=B

(P#Q)#R=(P'+Q')#R

=P.Q+R'

whereas

P#(Q#R)=P'+(Q#R)'

=P'+(Q'+R')'

=P'+QR
13 votes -- overtomanu ( 1.2k points)
X#Y=X'+Y'

      =(XY)'     (DEMORGAN'S LAW)

so this # operatoe is nand operator

Nand is commutative but not associative. So B is the answer
7 votes -- Pooja Palod ( 31.2k points)
Every subset of a countable set is countable.

State whether the above statement is true or false with reason.

Let $\Sigma$ be a finite non-empty alphabet and let $2^{\Sigma^*}$ be the power set of $\Sigma^*$. Which one of the following is TRUE

  1. Both $2^{\Sigma^*}$ and $\Sigma^*$ are countable
  2. $2^{\Sigma^*}$ is countable and $\Sigma^*$ is uncountable
  3. $2^{\Sigma^*}$ is uncountable and $\Sigma^*$ is countable
  4. Both $2^{\Sigma^*}$ and $\Sigma^*$ are uncountable

Answers: Countable Uncountable Set

Selected Answer
True

https://proofwiki.org/wiki/Subset_of_Countable_Set_is_Countable
4 votes -- Anu ( 10.2k points)
Selected Answer

A set is countable means there exist a enumeration procedure to generate each of its elements and  for a given element of set, it take finite step to generate it using the enumeration procedure.

Let ∑ = {a,b } and there exist a enumeration procedure to generate all the string of the language  ∑*.

∑* = { ∈ , a , b , aa, ab, ba, bb , aaa , ........ }

Here enumeration procedure is simply the generating string of the language  by length for the fixed length string are in alphabetical order.

This way ∑* is countably infinite & 2∑* will be uncountable set

Because the power set of countably infinite set are uncountable.

Ref: http://www.cs.xu.edu/csci250/06s/Theorems/powerSetuncountable.pdf

11 votes -- Sandeep Singh ( 8.9k points)
c,by diagonalisation theorem
3 votes -- VOOTLA SRINIVAS ( 293 points)

What is the cardinality of the set of integers X defined below?

X = {n | 1 ≤ n ≤ 123, n is not divisible by either 2, 3 or 5}

  1. 28
  2. 33
  3. 37
  4. 44
The number of onto functions (surjective functions) from set $X = \{1, 2, 3, 4\}$ to set $Y=\{a,b,c\}$ is ______.
The number of 4 digit numbers having their digits in non-decreasing order (from left to right) constructed by using the digits belonging to the set {1, 2, 3} is ________.

Answers: Counting

Selected Answer

No's divisible by 2 in X = 61        [ = integer(123/2) ]

No's divisible by 3 in X = 41 

No's divisible by 5 in X = 24

No's divisible by 2 and 3 .i,e by 6 = 20 

No's divisible by 2 and 5 i.e by 10 = 12 

No's divisible by 3 and 5 , i.e by 15 = 8 

No's divisible by 2 and 3 and 5 ..ie by 30 = 4 

 

No's divisible by either 2 or 3 or 5 = N(AUBUC) = N(A) +N(B)+N(C) -N(A∩B)-N(B∩C)-N(A∩C)+ N(A∩B∩C) 

= 61 +41+24 -20-12-8 +4 = 90 

X = { n ,1 ≤ n ≤ 123, n is not divisible by either 2, 3 or 5 }  

Cardinality = 123 - 90 = 33 

17 votes -- Praveen Saini ( 53k points)
Selected Answer

We have 3 elements in set B and 4 elements in set A and surjection means every element in B must be mapped to. So, this problem reduces to distributing 4 distinct elements (r = 4) among 3 distinct bins (n = 3) such that no bin is empty, which is given by n! S(r, n), where S(r, n) is Stirling's number of 2nd kind. So, here we need S(4, 3).

We have S(r+1, n) = n* S(r, n) + S(r, n-1)

So, Stirling numbers of second kind can be generated as follows:

1

1 1

1 3 1 

1 7 6 1

So, S(4,3) = 6 and 3! = 6 giving, number of surjective functions = 6*6 = 36

 

Ref: See Theorem 9:

http://www.cse.iitm.ac.in/~theory/tcslab/mfcs98page/mfcshtml/notes1/partset.html 
  
alternative approach , 

Answer is 36
for onto function from a set A(m-element) to a set B(n-element) ,
should be hold " m >= n"
then number of onto function $= n^m - ^nC_1(n-1)^m + ^nC_2(n-2)^m  -  ^nC_3(n-3)^m+$ .........and so on till $^nC_n(n-n)^m +,- ,$alternative 

                                           =
                                               
here m=4 and n=3 (here above condition valid)
then
number of onto function $= 3^4 - ^3C_1(3-1)^4 + ^3C_2(3-2)^4  -  ^3C_3(3-3)^4$
                                    $= 81 - 3*16 +3*1 - 1*0$
                                   $= 36$
ref@ http://www.cse.iitd.ac.in/~mittal/stirling.html

18 votes -- Arjun Suresh ( 286k points)
$\bf{Alternatively\; which\; is\; equivalent\; to\; put \; 4 \; different\;balls \; into\; 3\; different\; boxes}$

$\bf{Such\; that\; each \; box\; contain\; atleast\; one\; ball}$

$\bf{So\; Possible\; arrangements\; as \; (2,1,1)\; and \; its \; Permutation\;.}$

$\bf{So\; Total\; no.\; of\; ways\; \displaystyle = \binom{4}{2}\times \binom{2}{1}\times \binom{1}{1}\times 3 = 36}$
17 votes -- Jagdish Singh ( 491 points)
Selected Answer

Dynamic programming Approach

  1 digit 2 digit 3 digit 4 digits
Starting 3 1 1 1 1
Starting 2 1 2 3 4
Starting 1 1 3 6 10


Here Starting 1 means numbers starting with 1. And cell $(i, j)$ is for number of numbers starting with $i$ and having $j$ digits. We can have the relation $$ c(i, j) = \Sigma_{k=1}^i c(k, j-1)$$ as per the non-decreasing condition given in the question. So, our answer will be $c(1,4) + c(2, 4) + c(3, 4) = 1 + 4 + 10 = 15$


 

Brute force

3 3 3 3
2 2 2 2
2 2 2 3 
2 2 3 3
2 3 3 3
1 1 1 1
1 1 1 2
1 1 1 3
1 1 2 2
1 1 2 3
1 1 3 3
1 2 2 2
1 2 2 3
1 2 3 3
1 3 3 3

 

21 votes -- Arjun Suresh ( 286k points)
you can arrive at a solution by constructing a graph for each starting digit. for example root 3 means - starting with 3 it can have 3 child 1,2,3 and the construction goes

3 can three children 1, 2,3

2 can have two children 1, 2

1 can have only 1 as child. Graph need to be done till three levels

and finally count total number of leaves
16 votes -- Sankaranarayanan P.N ( 11k points)

Let R and S be any two equivalence relations on a non-empty set A. Which one of the following statements is TRUE?

  1. R ∪ S, R ∩ S are both equivalence relations
  2. R ∪ S is an equivalence relation
  3. R ∩ S is an equivalence relation
  4. Neither R ∪ S nor R ∩ S are equivalence relations

Consider the following relations:

  • R1 $(a,b)$ iff $(a+b)$ is even over the set of integers
  • R2 $(a,b)$ iff $(a+b)$ is odd over the set of integers
  • R3 $(a,b)$ iff $a.b > 0$ over the set of non-zero rational numbers
  • R4 $(a,b)$ iff $|a-b| \leq 2$ over the set of natural numbers

Which of the following statements is correct?

  1. R1 and R2 are equivalence relations, R3 and R4 are not
  2. R1 and R3 are equivalence relations, R2 and R4 are not
  3. R1 and R4 are equivalence relations, R2 and R3 are not
  4. R1, R2, R3 and R4 all are equivalence relations
State whether the following statements are TRUE or FALSE:

The union of two equivalence relations is also an equivalence relation.

Answers: Equivalence Classes

Selected Answer
RUS might not be transitive. Say (a,b) be present in R and (b,c) be present in S and (a, c) not present in either, R U S will contain, (a, b) and (b, c) but not (a, c) and hence not transitive.

option c.
5 votes -- anshu ( 2.9k points)
Selected Answer
R1) Reflexive : a+a=2a always even

 Symmetric: either (a,b) both must be odd or both must be even to have sum as even

therefore, if(a,b) then definately (b,a)

Transitive: if(a,b) and (b,c) , then both of them must be even pairs or odd pairs and therefore (a,c) is even

R2) Reflexive : a+a=2a cant be odd ever

R3) Reflexive: a.a>0

Symmetric: if a,b>0 then both must be +ve or -ve, which means b.a >0 also exists

Transitive : if a.b>0 and b.c>0 then to have b as same number, both pairs must be +ve or -ve which implies a.c>0

R4) Reflexive: |a-a|<=2

Symmetric: if |a-b|<=2 definately |b-a|<=2 when a,b are natural numbers

Transitive: |a-b|<=2 and |b-c|<=2, doesnt imply |a-c|<=2

ex: |4-2|<=2 and |2-0|<=2 , but |4-0|>2 ,

 

hence, R2 and R4 are not equivalence

B)
6 votes -- confused_luck ( 801 points)
ans is B.

for R1 and R3 are Reflexive symmetric and transitive.

R2 is not transitive. ex: (1,2) (2,3) (1,3), which is not satisfying condition.

R4 is not transitive . ex: (1,3) (3,5) (1,5), which is not satisfying condition.
5 votes -- jayendra ( 7.7k points)
Selected Answer
No union of two equivalence relation may not be equivalence relation because of transitive dependency.

equivalence relation : satisfy Reflexive, symmtric and transitive property

Reflexive $\cup$ Reflexive = Reflexive

Symmtric $\cup$ Symmtric = Symmtric

Transitive $\cup$ Transitive $\neq$ Transitive why

Example : R = { (1, 2) , (3,4)).....S = { (2, 3)}

Union = { (1, 2) , (3,4) , (2, 3) } which is not transitive i.e. (1, 3)  and (2, 4) is missing.

so False is amswer.
4 votes -- Prashant Singh ( 47.5k points)

Consider the field $C$ of complex numbers with addition and multiplication. Which of the following form(s) a subfield of C with addition and multiplication?

  • S1:  the set of real numbers
  • S2: {(a + ib) | a and b are rational numbers}
  • S3: {a + ib | (a2 + b2) ≤ 1}
  • S4: {ia | a is real}
  1. only S1
  2. S1 and S3
  3. S2 and S3
  4. S1 and S2

Answers: Fields

Selected Answer

A field is an algebric structure over two operations + and * if :

1. It is closed under both + and *.

2. + and * are both commutative and associative. (+ and * in this question are already commutative and associative, so no need to check).

3. Existence of additive identity(0) and multiplicative identity(1)

4. Existence of additive and multiplicative inverses for each non-zero element.

5. Distributive property of * over + (This is also satisfied in question)

So for each option, we have to check only properties 1, 3, and 4.

(S1) : set of all real numbers

1. Closed : Yes, real+real = real, real*real=real

3. Additive and multiplicative identity : Yes, 0 and 1 are real numbers

4. Additive and multiplicative inverse for each non-zero element : Yes, for any real number a, additive inverse is -a, which is also a real number, and multiplicative inverse is 1/a, which is also a real number.

(S2) : {(a + ib) | a and b are rational numbers}

1. Closed : Yes, rational+rational=rational, rational*rational=rational

3. Additive and multiplicative identity : Yes, 0+0i (additive identity) and 1+0i (multiplicative identity) belong to given set.

4. Additive and multiplicative inverse for each non-zero element : Additive inverse is -a-ib, which belongs to given set. Multiplicative identity is \frac{1}{a+ib} = \frac{a-ib}{a^2+b^2} = \frac{a}{a^2+b^2}+i\frac{-b}{a^2+b^2}, which also belongs to given set.

(S3) : {a + ib | (a2 + b2) ≤ 1}

1. Closed : No, for example : (0.3+0.4i) + (0.7 + 0.6i) = 1 + i. Here both complex numbers which were added were in the given set, but resultant complex number is not.

(S4) : {ia | a is real}

Here this set doesn't contain 1 (multiplicative identity)

So (S1) and (S2) are subfields of C. So option D) is correct.

10 votes -- Happy Mittal ( 10.7k points)
If the set $S$ has a finite number of elements, prove that if $f$ maps $S$ onto $S$, then $f$ is one-to-one.

Let $f \: \circ \: g$ denote function composition such that $(f \circ g)(x) = f(g(x))$. Let $f: A \rightarrow B$ such that for all $g \: : \: B \rightarrow A$ and $h \: : \: B \rightarrow A$ we have $f \: \circ \: g = f \: \circ \: h \: \Rightarrow g = h$. Which of the following must be true?

  1. $f$ is onto (surjective)
  2. $f$ is one-to-one (injective)
  3. $f$ is both one-to-one and onto (bijective)
  4. the range of $f$ is finite
  5. the domain of $f$ is finite

Let f be a function from a set A to a set B, g a function from B to C, and h a function from A to C, such that h(a) = g(f(a)) for all a ∈ A. Which of the following statements is always true for all such functions f and g?

  1. g is onto => h is onto
  2. h is onto => f is onto
  3. h is onto => g is onto
  4. h is onto => f and g are onto

Let $f: B \to C$ and $g: A \to B$ be two functions and let $h = f o g$. Given that $h$ is an onto function which one of the following is TRUE?

  1. $f$ and $g$ should both be onto functions
  2. $f$ should be onto but $g$ need not to be onto
  3. $g$ should be onto but $f$ need not be onto
  4. both $f$ and $g$ need not be onto

Consider the set of all functions $f:\{0,1, \dots,2014\} \to \{0,1,\dots, 2014\}$ such that $ f\left(f\left(i\right)\right)=i$, for all  $0 \leq i \leq 2014$. Consider the following statements:

$P$. For each such function it must be the case that for every $i,f(i) = i$.

$Q$. For each such function it must be the case that for some $i,f(i)=i$.

$R$. Each function must be onto.

Which one of the following is CORRECT?

  1. $P, Q$ and $R$ are true
  2. Only $Q$ and $R$ are true
  3. Only $P$ and $Q$ are true
  4. Only $R$ is true

What is the maximum number of different Boolean functions involving $n$ Boolean variables?

  1. $n^2$
  2. $2^n$
  3. $2^{2^n}$
  4. $2^{n^2}$

Let $X$ and $Y$ be finite sets and $f:X \to Y$ be a function. Which one of the following statements is TRUE?

  1. For any subsets $A$ and $B$ of $X, |fA \cup B| = |f(A)| + |f(B)|$
  2. For any subsets $A$ and $B$ of $X, f(A \cap B) = f(A) \cap f(B)$
  3. For any subsets $A$ and $B$ of $X, |f(A \cap B| = \min \{|f(A)|, |f(B)|\}$
  4. For any subsets $S$ and $T$ of $Y, f^{-1}(S \cap T) = f^{-1}(S) \cap f^{-1}(T)$

For a set $A$ define $\mathcal{P}(A)$ to be the set of all subsets of $A$. For example, if $A = \{1, 2\}$ then $\mathcal{P} (A) = \{ \emptyset, \{1, 2\}, \{1\}, \{ 2 \} \}$. Let $A \rightarrow \mathcal{P}(A)$ be a function and $A$ is not empty. Which of the following must be TRUE?

  1. $f$ cannot be one-to-one (injective)
  2. $f$ cannot be onto (surjective)
  3. $f$ is both one-to-one and onto (bijective)
  4. there is no such $f$ possible
  5. if such a function $f$ exists, then $A$ is infinite

Consider a function $f(x) = 1- |x| \text{ on } -1 \leq x \leq 1$. The value of $x$ at which the function attains a maximum, and the maximum value of the function are:

 

  1. 0, -1
  2. -1, 0
  3. 0, 1
  4. -1, 2

If $g(x) = 1 - x$ and $h(x) = \frac{x}{x-1}$, then $\frac{g(h(x))}{h(g(x))}$ is:

  1. $\frac{h(x)}{g(x)}$
  2. $\frac{-1}{x}$
  3. $\frac{g(x)}{h(x)}$
  4. $\frac{x}{(1-x)^{2}}$

Consider the operations

$\textit{f (X, Y, Z) = X'YZ + XY' + Y'Z'}$ and $\textit{g (X, Y, Z) = X'YZ + X'YZ' + XY}$

Which one of the following is correct?

  1. Both $\left\{\textit{f} \right\}$ and  $\left\{ \textit{g}\right\}$ are functionally complete
  2. Only  $\left\{ \textit{f} \right\}$  is functionally complete
  3. Only  $\left\{ \textit{g}\right\}$  is functionally complete 
  4. Neither $\left\{ \textit{f}\right\}$  nor  $\left\{\textit{g}\right\}$ is functionally complete

Let ܵ$S$ denote the set of all functions $f:\{0,1\}^4 \to \{0,1\}$. Denote by $N$ the number of functions from S to the set $\{0,1\}$. The value of $ \log_2 \log_2N $ is _______.

Let $X$ and $Y$ denote the sets containing 2 and 20 distinct objects respectively and $F$ denote the set of all possible functions defined from $X$ to $Y$. Let $f$ be randomly chosen from $F$. The probability of $f$ being one-to-one is ______.

The number of functions from an $m$ element set to an $n$ element set is

  1. $m + n$
  2. $m^n$
  3. $n^m$
  4. $m^*n$

 

How many onto (or surjective) functions are there from an $n$-element $(n ≥ 2)$ set to a $2$-element set?

(A) $ 2^{n}$
(B) $2^{n} – 1$
(C) $2^{n} – 2$
(D) $2(2^{n} – 2)$

Let $F$ be the set of one-to-one functions from the set $\{1, 2, \dots, n\}$ to the set $\{1, 2,\dots, m\}$ where $m\geq n\geq1$.

  1. How many functions are members of $F$?

  2. How many functions $f$ in $F$ satisfy the property $f(i)=1$ for some $i, 1\leq i \leq n$?

  3. How many functions $f$ in $F$ satisfy the property $f(i)<f(j)$ for all $1\leq i \leq j \leq n$?

 

Consider a function $T_{k, n}: \left\{0, 1\right\}^{n}\rightarrow \left\{0, 1\right\}$ which returns $1$ if at least $k$ of its $n$ inputs are $1$. Formally, $T_{k, n}(x)=1$ if $\sum ^{n}_{1} x_{i}\geq k$. Let $y \in \left\{0, 1\right\}^{n}$ be such that $y$ has exactly $k$ ones. Then, the function $T_{k, n-1} \left(y_{1}, y_{2},....y_{i-1}, y_{i+1},...,y_{n}\right)$ (where $y_{i}$ is omitted) is equivalent to

  1. $T_{k-1}, n(y)$
  2. $T_{k, n}(y)$
  3. $y_{i}$
  4. $\neg y_{i}$
  5. None of the above.

Given a boolean function f (x1, x2, ..., xn), which of the following equations is NOT true

  1. f (x1, x2, ..., xn) = x1'f(x1, x2, ..., xn) + x1f(x1, x2, ..., xn)
  2. f (x1, x2, ..., xn) = x2f(x1, x2, …, xn) + x2'f(x1, x2, …,xn)
  3. f (x1, x2, ..., xn) = xn'f(x1, x2, …, 0) + xnf(x1, x2, …,1)
  4. f (x1, x2, ..., xn) = f(0, x2, …, xn) + f(1, x2, .., xn)

Let $\Sigma = \left\{a, b, c, d, e\right\}$ be an alphabet. We define an encoding scheme as follows:

$g(a) = 3, g(b) = 5, g(c) = 7, g(d) = 9, g(e) = 11$.

Let $p_i$ denote the i-th prime number $\left(p_1 = 2\right)$.

For a non-empty string $s=a_1 \dots a_n$, where each $a_i \in \Sigma$, define $f(s)= \Pi^n_{i=1}P_i^{g(a_i)}$.

For a non-empty sequence$\left \langle s_j, \dots,s_n\right \rangle$ of stings from $\Sigma^+$, define $h\left(\left \langle s_i \dots s_n\right \rangle\right)=\Pi^n_{i=1}P_i^{f\left(s_i\right)}$

Which of the following numbers is the encoding, $h$, of a non-empty sequence of strings?

  1. $2^73^75^7$

  2. $2^83^85^8$

  3. $2^93^95^9$

  4. $2^{10}3^{10}5^{10}$

How many one-to-one functions are there from a set $A$ with $n$ elements onto itself?

Let $X,Y,Z$ be sets of sizes $x, y$ and $z$ respectively. Let $W = X \times Y$ and $E$ be the set of all subsets of $W$. The number of functions from $Z$ to $E$ is

  1. $z^{2^{xy}}$
  2. $z \times 2^{xy}$
  3. $z^{2^{x+y}}$
  4. $2^{xyz}$

Suppose X and Y are sets and $|X| \text{ and } |Y|$ are their respective cardinalities. It is given that there are exactly 97 functions from X to Y. From this one can conclude that

  1. $|X| =1, |Y| =97$

  2. $|X| =97, |Y| =1$

  3. $|X| =97, |Y| =97$

  4. None of the above

 

Let $R$ denote the set of real numbers. Let $f:R\times R \rightarrow R \times R$ be a bijective function defined by $f(x,y) = (x+y, x-y)$. The inverse function of $f$ is given by

(a) $f^{-1} (x,y) = \left( \frac {1}{x+y}, \frac{1}{x-y}\right)$

(b) $f^{ -1} (x,y) = (x-y , x+y)$

(c) $f^{-1} (x,y) = \left( \frac {x+y}{2}, \frac{x-y}{2}\right)$

(d) $f^{-1}(x,y)=\left [ 2\left(x-y\right),2\left(x+y\right) \right ]$

Let \(f : A \to B\) be an injective (one-to-one) function. Define \(g : 2^A \to 2^B\) as:
\(g(C) = \left \{f(x) \mid x \in C\right\} \), for all subsets $C$ of $A$.
Define \(h : 2^B \to 2^A\) as: \(h(D) = \{x \mid x \in A, f(x) \in D\}\), for all subsets $D$ of $B$. Which of the following statements is always true?

  1. \(g(h(D)) \subseteq D\)
  2. \(g(h(D)) \supseteq D\)
  3. \(g(h(D)) \cap D = \phi\)
  4. \(g(h(D)) \cap (B - D) \ne \phi\)
A function $f: \Bbb{N^+} \rightarrow \Bbb{N^+}$ , defined on the set of positive integers $\Bbb{N^+}$,satisfies the following properties:

                    $f(n)=f(n/2)$   if $n$ is even

                    $f(n)=f(n+5)$  if $n$ is odd

Let $R=\{ i \mid \exists{j} : f(j)=i \}$ be the set of distinct values that $f$ takes. The maximum possible size of $R$ is ___________.

Let S = {1, 2, 3,........, m}, m >3. Let X1.........Xn be subsets of S each of size 3. Define a function f from S to the set of natural numbers as, f(i) is the number of sets Xthat contain the element i. That is $f(i)=\left | \left\{j \mid i\in X_j \right\} \right|$   then $ \sum_{i=1}^{m} f(i)$ is:

  1. 3m
  2. 3n
  3. 2m+1
  4. 2n+1

Let $f: A \rightarrow B$ a function, and let E and F be subsets of $A$. Consider the following statements about images.

  • $S1: f(E \cup F) = f(E) \cup f(F)$
  • $S2: f(E \cap F)=f(E) \cap f(F)$

Which of the following is true about S1 and S2?

  1. Only S1 is correct
  2. Only S2 is correct
  3. Both S1 and S2 are correct
  4. None of S1 and S2 is correct
If p, q, r, s are distinct integers such that:

$f (p, q, r, s) = \text{ max } (p, q, r, s)$

$g (p, q, r, s) = \text{ min } (p, q, r, s)$

$h (p, q, r, s) = \text {remainder of } (p \times q) / (r \times s) \text{ if } (p \times q) > (r \times s)$
$\text{ or remainder of } (r \times s) / (p \times q) \text{ if } (r \times s) > (p \times q)$

Also a function $fgh (p, q, r, s) = f(p, q, r, s) \times g(p, q, r, s) \times h (p, q, r, s)$
Also the same operations are valid with two variable functions of the form $f(p, q)$
What is the value of $fg \left(h \left(2, 5, 7, 3\right), 4, 6, 8\right)$?

Answers: Functions

let set s={1,2,3,4}

now see mapping from s to s

for f to be onto every element of codomain must be mapped by every element in domain.

since cardinality is same for both domain and codomain. we can not have mapping like f(1)=1 & f(2)=1 if it happened then at least one element remain umapped in codomain,which resultant f not to be onto but it is given that f is onto.so every element in codomain have exactly one element in domain.so one of mapping be like f(1)=2, f(2)=3,f(3)=4,f(4)=1 which certainly prove that f is an one one function also.

NOTE:if s is infinite then this result may not always be true.
7 votes -- junaid ahmad ( 1.4k points)
i think domain of F must be finite.
morover i think domain of F i.e, A shud be singleton set.
bcoz it is given that for all g and h possible between B and A, f∘g=f∘h⇒g=h..
if domain of F contains more than 1 element in domain,  f∘g=f∘h is possible but, g will not be equal to h
example:
suppose
A,B are set of all integers
g(x)= {x| for all integers x}
h(x)= {1 | for any integer x}
f(x) = {2| for any integer x}
if we see here,
f∘g=f∘h
f∘g = {(x,2)| for all integers x belongs to B}
f∘h = {(x,2) | for all integers x belongs to B}
but actually g and h are not equal.
so domain of f cant contain more than 1 element to ensure "if  f∘g=f∘h then g=h."
if A contains only one element, there is no other way for g and h except to map to that one element.
i mean number of functions possible from B-->A will be only one function if A is singleton set so, g and h will be equal obviously if f∘g=f∘h.
so i think E is the answer
6 votes -- Motamarri Anusha ( 11.4k points)

We can tackle this question by elimination. 

| Domain | >= | Range |

So, if domain is finite, then range must be finite. both d and e must be true. So, domain is not finite since the question has a single option correct. 

Moreover, we can take an example to counter the statement that domain or range is finite. Example is -> 

Example 1-

if A = B = Set of all real no.s, and if g(x) = x-1, h(x) = x+1, f(x) = x (domain, range of all three functions not finite)

then the condition that f o g = f o h => g=h will also be satisfied. How?

The condition can be written as if g not equal h, then f o g not eq f o h.

In this case, let's assume f o g = f o h are equal even if g is not equal to h.

=>   x + 1 = x -1

=> 1 = -1 ( which is false always)

Hence, our assumption was wrong. Therefore, in this example the condition f o g = f o h => g=h is satisfied.

The options that remain are a,b,c.

Example 2-  

if A = Singleton Set, B = any set may or may not be singleton. From B -> A, only one function is possible because all the elements of the domain (B ) must be mapped to that single element in A only. Then, g = h is always true in this case. So, f o g = f o h => g=h will always be true. 

But, f from A -> B has a single element in the domain, so will be mapped to single element in B. Hence, for f is not onto. So, f is not a bijection also. Hence, option a and c are wrong. d and e were prooved wrong by the previous example.

So, the correct option is b. f must be one-one.

2 votes -- tarun_svbk ( 1k points)
Selected Answer

Let h be onto (onto means co-domain = range). So, h maps to every element in C from A. Since h(a) = g(f(a)), g should also map to all elements in C. So, g is also onto -> option (C).

 

10 votes -- Arjun Suresh ( 286k points)
Selected Answer
B. $g$ need not be onto.

Let,

$A = \left\{0, 1, 2\right\}, B = \left\{0, 3, 4, 25\right\}, C = \left\{3, 4, 5\right\}$

$f = \left\{(0,3), (3, 5), (4, 4), (25, 3) \right\}$

$g = \left\{(1,3), (2, 4), (0,0)\right\}$ ($25$ in $B$ not mapped to by $g$, hence $g$ is not ONTO)

$h = \left\{(0,3), (1, 5), (2, 4)\right\}$

Now, $h$ is an onto function but $g$ is not.

$f$ must be an onto function as otherwise we are sure to miss some elements in range of $h$ making it not onto.
14 votes -- Arjun Suresh ( 286k points)
Selected Answer
Let $f(i) = j$. Now, we have $f(j) = i$, as per the given condition $f(f(i)) = i$.

For any $i \neq j$, we can have a mapping $f(i) = j, f(j) = i$ thus avoiding the condition $f(i) = i$. But the domain containing odd number of elements, at least for one element we must have $f(i) = i$. So, Q must be TRUE.

Since $f(i) = j$ and $f(j) = i$, and since $0 \leq i \leq 2014$ $i$ must take all 2015 possible values (since $f$ is a function, it must have a value for any element in the domain). We can easily see that $f(i)$ cannot be the same for two different $i$s- because suppose $f(2) = 5$, and $f(3) = 5$. Now as per given condition, $f(5) = 2$ and $f(5) = 3$, which is not allowed in a function. So, all $f(i)$ values are unique $\implies$ co-domain = range as there are only 2015 values in co-domain. So, R is true.

An identity function satisfies the given conditions. But that alone cant prove that P is true. We can also have a different function where all even numbers maps to the next odd number and all odd numbers map to the previous even number which satisfies the given conditions, except the last one as we have odd number in set. i.e.,
$f(0) = 1, f(1) = 0, f(2) = 3, f(3) = 2 \dots, f(2013) = 2012,  f(2014) = 2014$.

This proves, P is false.

So, (B) is the answer.
21 votes -- Arjun Suresh ( 286k points)
Selected Answer

answer - C

size of domain = number of different combinations of inputs  = 2n

size of codomain = 2 ( {0,1} )

number of functions = (size of co-domain)(size of domain)

11 votes -- ankitrokdeonsns ( 9.1k points)
Selected Answer
D)

3 out of 4 options can be eliminated with the help of a counter example.

Let $X = \{ a , b , c \}$ and $Y = \{ 1 , 2 \}$
A Function $f$ maps each element of $X$ to exactly one element in $Y$.
Let $f(a)=1 , f(b)=1 , f(c) =1$ and
$A = \{ a  \}, B = \{ b , c \}$
A)
     $|f ( A \cup B )| = |f (\{a,b,c\})| = |\{1\}| = 1$
$|f(A)|+|f(B)| = 1 + 1 = 2$ , LHS != RHS.

B)
     $f ( A  \cap B ) = f (\{\}) = \{\}$.
$f(A) \cap f(B) = \{ 1\} \cap \{ 1\} = \{ 1\}$
LHS!=RHS
C)
     $|f ( A  \cap B )| = |f (\{\})| = |\{ \}| = 0$
$\min\{|f(A)|,|f(B)|\} = \min(1,1) = 1$
LHS!=RHS

D) Its easy to see that this is true because in a function a value can be mapped only to one value. The option assumes inverse of function $f$ exists.
20 votes -- Srinath Jayachandran ( 3.7k points)
Selected Answer

Even if it can be one-to-one in the following way,

But, It cannot be onto,because, the number of elements in domain $(A)$  $<$ the number of elements in co-domain ($P(A)$) . For a function to be onto, the domain should be able to cover all elements of co-domain with each element of the domain having exactly one image in co-domain.
so option(B)

8 votes -- Motamarri Anusha ( 11.4k points)
Selected Answer
Answer: C

Put the value of x of all the options in f(x) and find value of f(x).
9 votes -- Rajarshi Sarkar ( 34.3k points)

there are 2 parts 

part A says "value of x at which the function attains a maximum" so at x=0 ,function attains a maximum and

part B says "the maximum value of the function"  so f(0)=1-0=1

so ans should be 0,1

2 votes -- Anil Khatri ( 3.1k points)
Selected Answer
option a) is correct.

$g\left(h\left(x\right)\right) =g\left(\frac{x}{x-1}\right)$
    $=1-\frac{x}{x-1}$
    $= \frac{-1}{x-1}$

$h\left(g\left(x\right)\right) =h(1-x)$
  $=\frac{1-x}{-x}$

$\frac{g(h(x))}{h(g(x))} = \frac{x}{(1-x)(x-1)} = \frac{h(x)}{g(x)}$
       

option A)
12 votes -- GateMaster Prime ( 1.6k points)
Selected Answer

g is preserving 0 as when all inputs are zero, output is always 0 and so g cannot be functionally complete.

f is not preserving 0.
f is not preserving 1. (when all inputs are 1, output is 0).
f is not linear as in XY' only one (odd) input (X = 1, Y = Z = 0) needs to be 1 and in X'YZ two inputs (even) (X = 0, Y = Z = 1) need to be 1. 
f is not monotone as changing Y from 0 to 1, can take f from 1 to 0.
f is not self dual as f(X, Y, Z) ≠ ~f(~X, ~Y, ~Z)

So, f satisfies all 5 conditions required for functional completeness and hence B is the answer. 

http://cs.ucsb.edu/~victor/ta/cs40/posts-criterion.pdf

39 votes -- Arjun Suresh ( 286k points)
answer is b
4 votes -- naresh1845 ( 1.4k points)
Selected Answer
For a function from set A to set B, we need to have a mapping for all elements of A and mapping must be unique.
Let number of elements in A be $m$ and that in B be $n$

So, if we consider an element from A, it can be mapped to any of the element from B. i.e., it has $n$ possibilities when a function is formed. Similarly, for all other members also there are $n$ possibilities as one element from A can be mapped to  only a single element in B (though reverse need not true). So, for $n$ elements in A, we totally have $\underbrace{n \times \dots \times n}_{m \text{ times}} = n^m$ possible functions.

In the question Number of elements (functions) in $f$ is $2^{2^4}$ as $\{0,1\}^4$ contains $2^4$ elements. So, number of functions from $S$ to $\{0,1\}$ will be $2^{2^{2^4}}$. So, $\log_2 \log_2 N = 2^4 = 16.$
24 votes -- Arjun Suresh ( 286k points)

Number of functions in S is 2^16 so in N is (2^(2^16)), and value of  loglog n will be 16.

3 votes -- Manu Thakur ( 5.8k points)
Selected Answer
For a function, the first element in X has 20 choices (to map to) and the second element also has 20 choices. For a one-to-one function the second element has only 19 choices left after 1 being taken by the first. So, required probability

= 20 * 19 / (20 * 20) = 0.95
19 votes -- Vikrant Singh ( 13.4k points)
Selected Answer
No. of functions from an $m$ element set to an $n$ element set is $n^m$ as for each of the $m$ element, we have $n$ choices to map to, giving $\underbrace{n \times n \times \dots n}_{m \text{ times}} = n^m$.

PS: Each element of the domain set in a function must be mapped to some element of the co-domain set.
11 votes -- Digvijay ( 46k points)
Selected Answer

2^n - 2 in words (total functions - 2 functions where all elements maps exactly one element)

10 votes -- Bhagirathi Nayak ( 13.1k points)

No onto (or surjective) functions are there from an n-element (n≥2) set to a 2-element set => Total No of functions - (No of functions with 1 element from RHS not mapped) + (No of functions with 2 element from RHS not mapped) ,....(So on Using Inclusion Excusion principle = 2^n (Total no of functions ) - 2 * 1^n ( No of functions in which one element is excluded) + 0 (No element in RHS is selected) = 2^n -2 (C)

alternate 

http://gateoverflow.in/8212/gate2015-2_40

8 votes -- Akash ( 41.5k points)
Selected Answer
(a) A function from A to B must map every element in A. Being one-one, each element must map to a unique element in B. So, for $n$ elements in A, we have $m$ choices in B and so we can have $^m\mathbb{P}_n$ functions.

(b) Continuing from (a) part. Here, we are forced to fix $f(i) = 1$. So, one element from A and B gone with $n$ possibilities for the element in A and 1 possibility for that in B, and we get $n \times ^{m-1}\mathbb{P}_{n-1}$ such functions.

(c) $f(i) < f(j)$ means only one order for the $n$ selection permutations from B is valid. So, the answer from (a) becomes $^m\mathbb{C}_n$ here.
8 votes -- Arjun Suresh ( 286k points)
ANS : D

as number of y's exactly k and yi is missing . if yi =1   then result becomes 0  , because number of 1s are less than k now.

if yi= 0 then result becomes 1. as number of 1s remain same. removal of which won't effect final value.
2 votes -- pramod ( 3.2k points)
Selected Answer

Answer: D

Proceed by taking f(x1) = x1

LHS: f(x1)  = 0 when x= 0

LHS: f(x1)  = 1 when x= 1

RHS: f(0) + f(1) = 0 + 1 = always 1

9 votes -- Rajarshi Sarkar ( 34.3k points)

A,B,C are true.

Because in all these three cases we could a boolean variable and its compliment is added to same function.

ie : if x= 1 then x' =0 and viceversa.

1.f(x) + 0.f(x) = f(x)

Hence D is false.

 

10 votes -- siraj p s ( 97 points)
Selected Answer
It is clear from the choices that there are 3 strings in the sequence as we have the first 3 prime numbers in the product. Now, in $f(s)$ the first term is $2^x$for some $x$, so, A and C choices can be eliminated straight away as neither 7 nor 9 is a multiple of 2.

The sequence of strings are "a", "a" and "a"

$f(a) = 2^3 = 8$. So, we get $2^8 3^8 5^8$ as per the definition of $h$.
9 votes