Answers:
Every new set S_{n+1 }starts after n elements from the starting element of S_{n }. This means that we can find the starting number of S_{21} using Arithmetic progression formula.
Let Sum(n) denote sum of natural numbers uptil n:
S_{1} starts with = 1
S_{2} starts with = Sum(1) + 1= 2
S_{3} starts with = Sum(2) + 1 = (1+2) + 1 = 4
Similarly S_{21} 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 + (n1)*d ] where a= starting term , d= difference
Sum of elements in S_{21} = $\frac{21}{2}$ [2(211) + 20 ] = $\frac{21 * 442}{2}$ = 4641... Option D is correct
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?
 $0$
 $1$
 $n!$
 $\frac{1} {n+1} .^{2n}C_n$
Answers: Binary Tree
answer  B
number of distinct BSTs = ^{2n}C_{n}/(n + 1)
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.
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:
 $\frac{\left ( 2n \right )!}{2^{n}}$
 $\frac{\left ( 2n \right )!}{n!}$
 $\frac{\left ( 2n \right )!}{2^n . n!}$
 $n! / 2$
 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?
 $\frac{n!}{\left(n  r\right)!}$ and $\frac{\left(n + r  1\right)!}{r!\left(n  1\right)!}$, respectively.
 $\frac{n!}{\left(n  r\right)!}$ and $\frac{n!}{r!\left(n  1\right)!}$, respectively.
 $\frac{n!}{r!\left(n  r\right)!}$ and $\frac{\left(n  r + 1\right)!}{r!\left(n  1\right)!}$, respectively.
 $\frac{n!}{r!\left(n  r\right)!}$ and $\frac{n!}{\left(n  r\right)!}$, respectively.
 $\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:
 $\frac{\left ( 2n \right )!}{2^{n}}$
 $\frac{\left ( 2n \right )!}{n!}$
 $\frac{\left ( 2n \right )!}{2^{n} . n!}$
 $n!/2$
 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?
 $64$
 $65$
 $204$
 $144$
 $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.
 $2^{n}$
 $n^{2}$
 $\left(\frac{n}{n/2}\right)^{2}$
 $\left(\frac{2n}{n}\right)$
 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)?
 $2^9$
 $2^{19}$
 $^{8}\mathrm{C}_{4} \times^{11}\mathrm{C}_{5}$
 $^{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
 $ \begin{pmatrix} 15 \\ 11 \end{pmatrix}$
 11 . $ \begin{pmatrix} 15 \\ 11 \end{pmatrix}$
 15 . 14 . 13 . 12 . 11 .10 . 9 . 8 . 7 . 6 . 5
 (15 . 14 . 13 . 12 . 11 .10 . 9 . 8 . 7 . 6 . 5) . 11
In how many ways can we distribute 5 distinct balls, B_{1}, B_{2}, ..., B_{5} in 5 distinct cells, C_{1}, C_{2}, ...., C_{5} such that Ball B_{i} is not in cell C_{i}, ∀i = 1, 2, ..., 5 and each cell contains exactly one ball?
 44
 96
 120
 3125
For the interhostel sixaside 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.
 260
 340
 720
 1440
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?
 $3^{35}$
 $3^{50}2^{50}$
 $\begin{pmatrix} 35 \\ 2 \end{pmatrix}$
 $\begin{pmatrix} 50 \\ 15 \end{pmatrix}. 3^{35}$
 $\begin{pmatrix} 37 \\ 2 \end{pmatrix}$
How many disctict words can be formed by permuting the letters of the word ABRACADABRA?
 $\frac{11!}{5! \: 2! \: 2!}$
 $\frac{11!}{5! \: 4! }$
 $11! \: 5! \: 2! \: 2!\:$
 $11! \: 5! \: 4!$
 $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?
 13
 12
 11
 10
 9
A) 126 B) 125 C)123 D)121
A) 22 B)27 C)24 D)38
A line L in a circuit is said to have a stuckat0 fault if the line permanently has a logic value 0. Similarly a line L in a circuit is said to have a stuckat1 fault if the line permanently has a logic value 1. A circuit is said to have a multiple stuckat fault if one or more lines have stuck at faults. The total number of distinct multiple stuckat faults possible in a circuit with N lines is
 3^{N}
 3^{N}  1
 2^{N}  1
 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
 $P = Q  k$
 $P = Q + k$
 $P = Q$
 $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
 each is sorted in ascending order,
 B has 5 and C has 3 elements, and
 the result of merging B and C gives A
 2
 30
 56
 256
 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.
 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.
 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
 \(^{2n}\mathrm{C}_n\times 2^n\)
 \(3^n\)
 \(\frac{(2n)!}{2^n}\)
 \(^{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?
 \(\left( \begin{array}{c} m  k \\ n  1 \end{array} \right)\)
 \(\left( \begin{array}{c} m  kn + n  1 \\ n  1 \end{array} \right)\)
 \(\left( \begin{array}{c} m  1 \\ n  k \end{array} \right)\)
 \(\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?
 9
 8
 7
 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)?
 $^{20}\mathrm{C}_{10}$
 $2^{20}$
 $2^{10}$
 None of the above.
In how many ways can b blue balls and r red balls be distributed in n distinct boxes?
 $\frac{(n+b1)!\,(n+r1)!}{(n1)!\,b!\,(n1)!\,r!}$
 $\frac{(n+(b+r)1)!}{(n1)!\,(n1)!\,(b+r)!}$
 $\frac{n!}{b!\,r!}$
 $\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

$^{n1}C_k$

$^nC_k$

$^nC_{k+1}$

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?
 1638
 2100
 2640
 None of the above
How many sub strings of different lengths (nonzero) can be found formed from a character string of length $n$?
 $n$
 $n^2$
 $2^n$
 $\frac{n(n+1)}{2}$
The number of substrings (of all lengths inclusive) that can be formed from a character string of length $n$ is
 $n$
 $n^2$
 $\frac{n(n1)}{2}$
 $\frac{n(n+1)}{2}$
Answers: Combinatory
(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 twoelement swaps, For a set of elements and , there are 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.
=$\frac{(2n)!}{\underbrace{2!.2!.2! \dots 2!}_{n \text{ times }} \times n!}$
=$\frac{(2n)!}{2^n \times n!}$
Option c.
(i) Repetition is not allowed and the order of picking matters =
= r arrangement with no repetition = npr = $\frac{n!}{(nr)!}$
(ii) Repetition is allowed and the order of picking does not matter =
= combination with unlimited repetition = n1+rCr = $\frac{n1+r!}{(n1)!r!}$
Option A
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{2n2}{2}$ ways(Say w2)
and so on..
For last kingdom , we have 2 champions left = $\binom{2}{2}$ ways (say w_{n})
Total ways for assigning 2n champions to n kingdoms = w1 * w2 * .... * wn
= $\binom{2n}{2} * \binom{2n  2}{2} * . . . * \binom{2}{2}$
= (2n)! / 2^{n} So, Option A (Ans) .
for 8*8 chessboard
=n(n+1)(2n+1)/6
=8*9*17/6
=204
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
There are n men and n women
Now we can select 1 woman from n women in ^{n}C_{1}
With that 1 man can select ^{ n}C_{1} ways
So, by 1 woman and 1 man we can get ^{n}C_{1 * }^{n}C_{1} ways...................i
Similarly , Now we can select 2 woman from n women in ^{n}C_{2}
With that 2 man can select ^{ n}C_{2} ways
So, by 2 woman and 2 man we can get ^{n}C_{2}_{ * }^{n}C_{2} ways.........................ii
...........................................................
Now, by n woman and n man we can get ^{n}C_{n}_{ * }^{n}C_{n} ways........................iii
So, by adding these equation we get
^{n}C_{0}.^{n}C_{0} +^{n}C_{1 * }^{n}C_{1}+ ^{n}C_{2}_{ * }^{n}C_{2} + ^{n}C_{3 }_{* }^{n}C_{3}+.......................^{n}C_{n} * ^{n}C_{n } =(^{2n}C_{n})
Ans will be (D)
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
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}$
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.
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.
Use Derangement concept D5= 44 so answer is A
Number of ways = 5C0*5!  5C1*4! + 5C2*3!  5C3*2! + 5C4*1!  5C5*0! = 44
There are three ways to choose 6 Players.
 5C3*4C2*2C1=120
 5C2*4C2*2C2=60
 5C2*4C3*2C1=80
So total No of ways is 260.
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]
Distinct ways are there to split 50 identical coins among three people so that each person gets at least 5 coins
x_{1}+5+x_{2}+5+x_{3}+5 = 50
x_{1}+x_{2}+x_{3} = 35
Solving Non integral solution n=35 ,r =3
^{n+r1 }C _{r1 }= ^{35+31} C _{31 }= ^{37} C_{ 2}
Hence E is Answer
a) option answer .
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.
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
B is ans.
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
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
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^N1. (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.
The odd series is 1 3 5 7 ... 2k1
So, 1+(t11)2=2k1
or t1=k;
P = (k/2) [2x1+(k1)2]=k^2
The odd series is 2 4 6 8 10 ... 2k
So, 2+(t21)2=2k
or t2=k;
Q = (k/2) [2x2+(k1)2]=k^2+k
So P=Qk is answer...
answer  C
select any 3 elements from given 8 elements  ^{8}C_{3}
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 = ^{8}C_{3}
Same argument holds for picking up 5 elements initially. No of ways = ^{8}C_{5}
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 n2 (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 n2 balls and taking all possible permutations with n2 being identical. i.e., (n2 + 1)!/(n2)! = (n1). We can also use the following formula
^{n2+21}C_{21}_{ }=^{n1}C_{1}
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 n3 items with 2 dividers which will give (n3 + 2)!/(n3)!2!
= (n1)!/(n12)!2!
=^{n1}C_{2}
c._{ }^{nk+k1}C_{k}_{1}_{ }=^{n1}C_{k1}
Possible outcome for a couple:
 only wife comes
 both come
 none come
Thus 3 possibilities for each couple, so 3 x 3 x 3 x ... n times = $3^n$
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 mk*n balls remaining.
We can use balls & sticks method now !
n bags= n variables, they need to equal to mk*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, n1 ) = C(m  k*n + n  1, m k*n )
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.
This question is slightly ambigous. So first let us understand what question is asking. So in a book, we have letters AZ 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
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.
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.
r red balls can be distributed into n distinct boxes in C(n+r1,r) = .(n+r1)! / (n1)! r!
b blue balls can be distributed in C(n+b1,b) = (n+b1)! / (n1)! b!
By product rule total ways are (n+b1)! (n+r1)! / (n1)! b! (n1)! r!
SO THE ANSWER IS A.
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+1}C_{k}
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
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$
no of strings of length 1 = n
no of strings of length 2 = n1
no of strings of length 3 = n2
.
.
.
no of string of length n = 1
total = n + (n 1) + (n  2) + (n  2) + ..... + 1
= n(n+1)/2

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
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+1120224)=2296
A 10pennant means sum of numbers in sequence is 10. If we look at any 9pennent, we can make it a 10pennant by adding 1 into that sequence. Similarly, we can make any 8pennant a 10pennant by adding 2 into that sequence.
So all 10pennants can be formed by 8pennants and 9pennants, 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.
(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
First do prime factorization of 2014  2^{1} x 19^{1} x 53^{1}
Now to get a factor of 2014, we can choose any combination of the prime factors including 0. i.e; 2^{0 }and 2^{1} 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.)
total positive integral factor=(2x2x2)=8
no. of substrings of length n1 is 2
no. of substrings of length n2 is 3
so n(n+1)/2
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
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.
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.
$s_1 = s_2 = 1$ and $s_i = 1 + \min \left({s_{i1}, s_{i2}}\right) \text{ for } i > 2$.
Prove by induction on $n$ that $s_n=⌈\frac{n}{2}⌉$.
Answers: Counting
$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_{n2} =\lceil \frac{n2}{2} \rceil$ and $s_{n1} =\lceil \frac{n1}{2} \rceil$ (Induction hypothesis)
Now, we have to prove,
$s_n = \lceil \frac{n}{2} \rceil$
$s_n = 1 + \min(s_{n1}, s_{n2}) \\= 1 + \lceil \frac{n2}{2} \rceil \\= 1 + \lceil \frac{n}{2} \rceil 1 \\=\lceil \frac{n}{2}\rceil$
(Hence, proved)
Given , the cardinality of set = n
So consequently ,
No of entries in operation table(Cayley table) = n^{2}
And hence if we consider lower triangular or upper triangular half , we have : (n^{2} + 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}
$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)
Answers: Generating Functions
$(1z)^{3} = 1 + \binom{3}{1}z + \binom{4}{2}z^2 + \binom{5}{3}z^3 + \dots \infty$
$\color{navy}{(1+z)(1z)^{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}$
yes 15 is correct ans
Answers: Number Series
n^{2} + 96 = x^{2}
x^{2}  n^{2} = 96
(xn)(x+n) = 96
Since, x and n both should be positive integer. (xn) and (x+n) will be divisors of 96.
By observation, (xn) should be smaller than (x+n) because x and n are positive integers.
(xn) = k1 $\rightarrow$ x= n+k1
(x+n)= k2 $\rightarrow$ n+k1+n = k2 $\rightarrow$ 2n+k1 = k2 $\rightarrow$ 2n = k2k1 $\rightarrow$ $n = \left ( \frac{k2k1}{2} \right )$
As we have seen from above, $n = \left ( \frac{k2k1}{2} \right )$
Therefore, for n to be a positive integer, k2k1 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!
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?
 $\displaystyle\frac{(6+3)!}{2!}$
 $\displaystyle\frac{6!}{2!}$
 $\displaystyle\frac{3!3!}{2!}$
 $\displaystyle\frac{4!3!}{2!}$
 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
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.
The rules for the University of Bombay fiveaside 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?
 23
 91
 60
 49
 None of the above.
Answers: Pigeonhole
$\left \lceil N/12 \right \rceil$ = 5
On solving we get N=49 .
Hence answer is D.
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?
 $F_{n+2} = 1 + \sum ^{n}_{i=0} F_{i}$ for any integer $n \geq 0$
 $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$.
 $F_{3n}$ is even, for every integer $n \geq 0$.
 $F_{4n}$ is a multiple of $3$, for every integer $n \geq 0$.
 $F_{5n}$ is a multiple of $4$, for every integer $n \geq 0$.
Let H_{1}, H_{2}, H_{3}, ... be harmonic numbers. Then, for n ∊ Z^{+}, $\sum_{j=1}^{n} H_j$ can be expressed as
 nH_{n+1}  (n + 1)
 (n + 1)H_{n}  n
 nH_{n}  n
 (n + 1) H_{n+1}  (n + 1)
Answers: Recurrence
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
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}{ (n1) \times\frac1 2} + \color{green}{(n2) \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.
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?
 Only $(i)$
 Only $(ii)$
 Only $(iii)$
 Only $(iv)$
 $(i)$ and $(ii)$
Answers: Adjacency Matrix
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).
What is the chromatic number of an $n$ vertex simple connected graph which does not contain any odd length cycle? Assume $n > 2$.
 2
 3
 n1
 n
Answers: Chromatic Number
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 2colorable. 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/MAT307lecture07.pdf
Bipartite Graph: A graph which is 2colorable 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/highschool/mathematics/combinatoricsthefineartofcounting/lecturenotes/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
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.
If $G$ is the forest with $n$ vertices and $k$ connected components, how many edges does $G$ have?
 $\lfloor n/k \rfloor$
 $\lceil n/k \rceil$
 $nk$
 $nk+1$
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
 $k$ and $n$
 $k1$ and $k+1$
 $k1$ and $n1$
 $k+1$ and $nk$
The maximum number of possible edges in an undirected graph with n vertices and k components is ______.
Answers: Connected Components
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 nk vertices when introduced, to make up to n vertices, contributes to nk edges.
Hence, ans = option C = (nk)
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 (nk) each of which introduces an edge. Hence there are (nk)*1=(nk) edges.
B. $n+1$ (subsets of size < 2 are all disconnected) $+ 1$ (subsets of size >= 2 are all connected) $= n+2.$
Lower Bound: number of components decreased by one = $k  1$ (remove an isolated vertex which was a component)
Upper Bound: number of components = $n1$ (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 $n1$ vertices isolated making $n1$ components)
Therefore (C).
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+b1}{2} + \binom{1}{2} = \frac{1}{2} \left(a+b1\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) \\=abab+a \\= (a1)(b1) \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 $nk+1$ vertices, for a total of $\binom{nk+1}{2}$ edges.
in simple connected graph , number of edges ,
$(n1) \leq e \leq n. \frac{(n1)}{2}$
in simple unconnected graph with k component , number of edges ,
$(nk) \leq e \leq (nk).\frac{(nk+1)}{2 }$
note : put k=1 then it will be connected graph .
reference @ http://www.quora.com/Whatisthemaximumnumberofedgesingraphwithnverticesandkcomponents
another read @ http://stackoverflow.com/questions/24003861/maximumnumberofedgesinundirectedgraphwithnverticeswithkconnectedcom
if u want maximum number of nodes and k vertices then u should have k1 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 (k1) component one vertex and the remaining will be (n(k1)) now make that bigger one a complete graph . i.e ( nk1) ( nk1+1)/2 complete graph formula . n(n1)/2 = (nk)(nk+1)/2
${}^{\left(\frac{n^2n}{2}\right)}C_{\frac{n^23n} {2}}$
${\sum_{k=0}^{\left (\frac{n^23n}{2} \right )}} .^{\left(n^2n\right)}C_k$
${}^{\left(\frac{n^2n}{2}\right)}C_n$
${\sum_{k=0}^n}.^{\left(\frac{n^2n}{2}\right)}C_k$
$\frac{n(n1)} {2}$
$2^n$
$n!$
$2^\frac{n(n1)} {2} $
$n$
$\frac{n(n1)}{2}$
$n!$
$2^n$
$2^m, \: \text{ where } m=\frac{n(n1)}{2}$
Answers: Counting
Minimum no of edges has to be $\frac{n^2 3n}{2} = b$.
Maximum no of edges in simple graph = $\frac{n(n1)}{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,ab) + C(a,a(b+1)) + C(a,a(b+2)) + \dots +C(a,0)$
$= C(a,n) + C(a,n1) + C(a,n2) + \dots +C(a,0))\\ \left(\because ab = n \right)$
$= C\left(\frac{n(n1)}{2},n\right) + C\left(\frac{n(n1)}{2}, n1\right) \\+ C\left(\frac{n(n1)}{2},n2\right) + \dots +C\left(\frac{n(n1)}{2},0\right)$
$ =\sum_{k=0}^{n} {}^{\left(\frac{n^2n}{2}\right)}C_k$
Option D..
with n vertices we have ^{n}C_{2} edges and each subset of these edges will form a graph, so total number of undirected graph possible = 2^{n(n1)/2}
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.
answer = option C
Take the example of a triangle (K_{3}) 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 82 = 6 when there are no directed cycles. This corresponds to only option (c), and no other option.
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 mincut of $G$ is a cut in $G$ of minimum cardinality. Consider the following graph.

Which of the following sets of edges is a cut
 $\left\{(A, B), (E, F), (B, D), (A, E), (A, D)\right\}$
 $\left\{(B, D), (C, F), (A, B)\right\}$
 What is cardinality of mincut in this graph?
 Prove that if a connected undirected graph $G$ with $n$ vertices has a mincut of cardinality $k$, then $G$ has at least $(nk/2)$ edges
Answers: Cutvertices&edges
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.
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.
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 number of vertices of degree zero in G is:
$1$
$n$
$n + 1$
$2^n$
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:
 $\binom{n/2}{2}2^{n/2}$
 $2^{n2}$
 $2^{n3}\times 3$
 $2^{n1}$
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$?
 There are even number of vertices of even degree.
 There are odd number of vertices of even degree.
 There are even number of vertices of odd degree.
 There are odd number of vertices of odd degree.
 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?
 5
 6
 7
 8
Which one of the following is TRUE for any simple connected undirected graph with more than $2$ vertices?
 No two vertices have the same degree.
 At least two vertices have the same degree.
 At least three vertices have the same degree.
 All vertices have the same degree.
A graph $G=(V,E)$ satisfies $E \leq 3 V  6$. The mindegree of $G$ is defined as $\min_{v\in V}\left\{degree (v)\right \}$. Therefore, mindegree of $G$ cannot be
 3
 4
 5
 6
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
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.
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 note1 and note2) , right!
Hence n+1 vertices with degree 0
@arjun sir , is it a correct approach ?
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.
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 nelement set = [0,n1]
a vertex with a degree $0$ means that one of the vertex is disconnected
a vertex with a degree $n1$ means that a vertex is connected to every other n1 vertices.
Both statements cannot be true simultaneously.
This means that our assumption is Wrong and such a graph cannot exist.
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 $nk$ elements + the 2 common elements. This will be equal to $2^{nk}$ 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^{nk}$
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^{nk}$ 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^{n3}$.
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
Vertices 1, 3, 5,7, 9 have degree 8 and vertices 2, 4, 6, 8 have degree 7.
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.
answer = option B
There are n vertices and at least n1 edges. So, for each vertex, degree should range from 1 (since graph is connected) to n1 (since graph is simple). But we have n such vertices filling n things with n1 numbers. $$\bigg \lceil \frac{n}{n1} \bigg\rceil = \lceil 1.\sim \rceil = 2$$ So, at least 2 of them must be equal (pigeonhole principle).
$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}$
so,3V<=2*25=$\left \lfloor 50/3 \right \rfloor =16$
Ans:16
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
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(3n6))/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)
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
Which of the following graphs has an Eulerian circuit?
 Any $k$regular graph where $k$ is an even number.
 A complete graph on 90 vertices.
 The complement of a cycle on 25 vertices.
 None of the above
Answers: Euler Graph
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) kregular graph where k is even number.
a kregular 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{n1}{2}$ then $G$ is connected." [check this]
Here Degree of each vertex is $22$, which is of course greater that $\frac{251}{2}\left (=12 \right )$.
answer = Option C
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
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
 $2$
 $3$
 $4$
 $n2 \left \lfloor \frac{n}{2} \right \rfloor+2$
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?
 $3^9$
 $6^3$
 $3 \times 2^8$
 $27$
 $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.
 $\chi (G)\geq a(G)$
 $\chi (G)\leq a(G)$
 $a(G)\geq n/\chi (G)$
 $a(G)\leq n/\chi (G)$
 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/(2^{n1})
 1/n
 2/n
 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:
 If every vertex in $G$ has degree at most $d$ then $G$ admits a vertex coulouring using $d+1$ colours.
 Every cycle admits a vertex colouring using 2 colours
 Every tree admits a vertex colouring using 2 colours
Which of the above statements is/are TRUE? Choose from the following options:
 only i
 only i and ii
 only i and iii
 only ii and iii
 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
 2
 3
 4
 5
Answers: Graph Coloring
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 =>
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 !
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
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)
α(G) χ(G) ≥ n (its a theorem)
option C
Answer is (C)
For the given condition we can simply design a KMAP and mark an edge between every two adjacent cells in KMap.(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 (n1) 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/electricalengineeringandcomputerscience/6042jmathematicsforcomputersciencespring2005/assignments/pset5_soln.pdf
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.
4 colors are required to color the graph in the prescribed way.
answer = option C
Ans C
The maximum number of edges in a nnode undirected graph without self loops is
 $n^2$
 $\frac{n(n1)}{2}$
 $n1$
 $\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?
 A tree has no bridges
 A bridge cannot be part of a simple cycle
 Every edge of a clique with size ≥ 3 is a bridge (A clique is any complete subgraph of a graph)
 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
 4
 7
 23
 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?
 10
 11
 18
 19
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
 Hamiltonian cycle
 grid
 hypercube
 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?
 $\bar{G}$ is always connected.
 $\bar{G}$ is connected if $G$ is not connected.
 At least one of $G$ and $\bar{G}$ connected.
 $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
 regular
 complete
 Hamiltonian
 Euler
(a) $n1$
(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?
 $G$ has no cycles
 The graph obtained by removing any edge from $G$ is not connected
 $G$ has at least one cycle
 The graph obtained by removing any two edges from $G$ is not connected
 None of the above
i) Determine size of E
ii) Show that G is connected
Answers: Graph Connectivity
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 ^{N}C_{2} ways = N(N1)/2
In a cycle if we remove an edge, it will still be connected. So, bridge cannot be part of a cycle.
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 13399100
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 1113399100
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 ..91011
so we got another point
1910113399100
now to reach 11 from 1
max value of i = 3 so j= 3*i= 9 so 39
13910113399100
Solved problem into half give u idea how to get minimum for rest of graph.
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.
2*6 + 4*3 + 3*x = 27*2
x=10.
Number of vertices = 6 + 3 +x = 19
The correct answer is (D).
This is possible with spanning tree.
A spanning tree with n nodes has n1 edges.
Therefore, Answer is (A)
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.
I think it is (D)
Correct answer would be C) At least one of G and Gbar 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 Gbar is not connected at the same time, which is impossible.
Here is the total Possibility
G Gbar Possible/NotPossible
Connected Connected Possible
Connected Disconnected Possible
DisConnected Connected Possible
Dis  Connected DisConnected NotPossible
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.
For making a cyclic graph, the minimum number of edges have to be equal to the number of vertices.
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.
The articulation points are 2,3,5.
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 n1 edges. If we remove 2 out of n, we get n2 edges, which can connect at max n1 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.
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.
as M+N=12
total no of edges =MN =M(12M)
take the derivative of this equation with respect to M.
d(total no of edges)/d(M)= 122M
second order derivative is negative so this function will attain maximum value at 122M=0
so M=6
and N=6
total no of edges = MN= 36.
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.
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)
$2E=$ sum of the degrees
$ 2E = 4*3+40*5+100*8= 1012$
$E = 1012/2 = 506$ edges.
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^{n1}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 $k1$ 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.
Answers: Graph Isomorphism
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
its n=5 only.
only C5 is isomorphic to its complement.
No of edges in graph + no of edges in complement of graph = n(n1)/2 // No Of edges in complete graph of N vertices
5 + 5 = n(n1)/2 // Here in C_{5 }5 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 .
Answers: Graph Matching
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.
Note: To understand the solution please go through the definitions of perfect matching
The complete graph k_{n }have a perfect matching only when n is even.. So let n=2m.
Let the vertices be V_{1 , }V_{2} ,......,V_{2m. }
v_{1} can be joined to any other 2m1 vertices
v_{2} can be joined to any other 2m3 vertices
Similarly go till V_{2m} which will have only one vertex to be joined with..
No of Perfect matches= (2m1)(2m3)(2m5).....(3)(1)
In the above question 2m=6
So No. of perfect matches=5*3*1=15
Answers: Graph Planarity
Answers: Groups
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.
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?
 7, 6, 5, 4, 4, 3, 2, 1
 6, 6, 6, 6, 3, 3, 2, 2
 7, 6, 6, 4, 4, 3, 2, 2
 8, 7, 7, 6, 4, 2, 1, 1
 I and II
 III and IV
 IV only
 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 6tuples is NOT graphic?
 $(1,1,1,1,1,1)$
 $(2,2,2,2,2,2)$
 $(3,3,3,1,0,0)$
 $(3,2,1,1,1,0)$
Answers: Havel Hakimi Theorem
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 HavelHakimi Algorithm.
you can implement it by following one simple video. Here it is. :)
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 : d21, d21, d31 . . . , 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 optionD
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.
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
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 <= 3V  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.
(A) 15 (B) 30 (C) 90 (D) 360
Answers: Permutation
From 6 vertices we can select 4 distinct vertices in _{6}C_{4} = 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 = (n1)! 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.
Answer would be ^{6}C_{4} * 4! /(4*2) =45
Explanation:
Number of ways to choose 4 vertices = ^{6}C_{4}
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)
Answers: Regular Graph
n vertices are adjacent to n1 vertices and an edge contributes two degree so dividing by 2.
so in d regular graph No of edges will be n*d/2
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}$?
 $\frac{m}{n  1}$
 $m^{n  1}$
 $n^{n  2}$
 $n^{n  1}$
 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
 2
 3
 n
Answers: Spanning Tree
Answer will be (C)
e.g. for K_{4} no. of spanning tree will be 16
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.
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.
starting from 3 vertices only we can do 3 edges so atleast 3 spanning trees
Which of the following is NOT a sufficient and necessary condition for an undirected graph $G$ to be a tree?
 $G$ is connected and has $n 1$ edges.
 $G$ is acyclic and connected.
 $G$ is acyclic and has $n  1$ edges.
 $G$ is acyclic, connected and has $n  1$ edges.
 $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
 $\mid S\mid = 2\mid T \mid$
 $\mid S \mid = \mid T \mid  1$
 $\mid S\mid = \mid T \mid$
 $\mid S \mid = \mid T\mid + 1$
Answers: Trees
Option a $\iff$ Option b $\iff$ Option c $\iff$ Option d.
 You need atleast $n1$ 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 $n1$ 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 $(n1)$ edges.
 You can't fit $(n1)$ edges between $(n1)$ vertices without causing cycles. Thus, if graph with $(n1)$ edges is acyclic, it must connect $n$ vertices. Hence, an acyclic graph with $(n1)$ 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 $(n1)$ 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.
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
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:
 12
 8
 less than 8
 more than 12
Answers: Vertex Cover
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).
Q12 The maximum possible value of xy^{2}z^{3} 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:
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
gcd(x,y): gcd of x and y
∀x∀y( x >= 0 ∧ y>=0 ) $\rightarrow$ (LCM(x,y) * GCD(x,y) = x*y )
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.
Which one of the following Boolean expressions is NOT a tautology?
 $((\,a\,\to\,b\,)\,\wedge\,(\,b\,\to\,c))\,\to\,(\,a\,\to\,c)$
 $(\,a\,\to\,c\,)\,\to\,(\,\sim b\,\to\,(a\,\wedge\,c))$
 $(\,a\,\wedge\,b\,\wedge\,c)\,\to\,(\,c\vee\,a)$
 $a\,\to\,(b\,\to\,a)$
Answers: Boolean Expressions
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..
option B reduces to A+B rest all reduces to 1
Hence, B is not a tautology.
$$(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
(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
 $\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)$
 $\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)$
 $\forall x \exists y \left(\text{fsa}\left(x\right) \wedge \text{pda}\left(y\right) \wedge \text{equivalent}\left(x,y\right)\right)$
 $\forall x \exists y \left(\text{fsa}\left(y\right) \wedge \text{pda}\left(x\right) \wedge \text{equivalent}\left(x,y\right)\right)$
$$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
 $\forall d (\text{Rainy}(d) \wedge \text{~Cold}(d))$
 $\forall d ( \text{~Rainy}(d) \to \text{Cold}(d))$
 $\exists d(\text{~Rainy}(d) \to \text{Cold}(d))$
 $\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.
 $[\beta \rightarrow (\exists x, \alpha(x))] \rightarrow [\forall x, \beta \rightarrow \alpha(x)]$
 $[\exists x, \beta \rightarrow \alpha(x)] \rightarrow [\beta \rightarrow (\forall x, \alpha(x))]$
 $[(\exists x, \alpha(x)) \rightarrow \beta] \rightarrow [\forall x, \alpha(x) \rightarrow \beta]$
 $[(\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))]
 [∃ x, α → (∀y, β → (∃u, ∀ v, y))]
 [∃ x, α → (∀y, β → (∃u, ∀ v, ¬y))]
 [∀ x, ¬α → (∃y, ¬β → (∀u, ∃ v, ¬y))]
 [∃ x, α ʌ (∀y, β ʌ (∃u, ∀ v, ¬y))]
Which one of these firstorder logic formulae is valid?
 ∀x(P(x) => Q(x)) => (∀xP(x) => ∀xQ(x))
 ∃x(P(x) ∨ Q(x)) => (∃xP(x) => ∃xQ(x))
 ∃x(P(x) ∧ Q(x)) <=> (∃xP(x) ∧ ∃xQ(x))
 ∀x∃y P(x, y) => ∃y∀x P(x, y)
"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
 satisfiable and valid
 satisfiable and so is its negation
 unsatisfiable but its negation is valid
 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?
 $(\forall x)(\exists y)[(a(x, y) \vee b(x, y)) \to c(x, y)]$
 $(\exists x)(\forall y)[(a(x, y) \vee b(x, y)) \wedge\neg c(x, y)]$
 $\neg (\forall x)(\exists y)[(a(x, y) \wedge b(x, y)) \to c(x, y)]$
 $\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?
 $\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)$
 $\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)$
 $\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)$
 $\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 wellformed formulae is a tautology?
 $\forall x \, \exists y \, R(x,y) \, \leftrightarrow \, \exists y \, \forall x \, R(x, y)$
 $( \forall x \, [\exists y \, R(x,y) \, \rightarrow \, S(x, y)]) \, \rightarrow \, \forall x \, \exists y \, S(x, y)$
 $[ \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)]$
 $\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 }.
 $(∀x∀y P(x, y)) \Rightarrow (∀y∀x P(x, y))$
 $(∀x∃y \neg P(x, y)) \Rightarrow \neg (∃x∀y P(x, y))$
 $(∃x∃y P(x, y)) \Rightarrow (∃y∃x P(x, y))$
 $(∃x∀y P(x, y)) \Rightarrow (∀y∃x P(x, y))$
 $(∀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?
 \(I_1\) satisfies \(\alpha\), \(I_2\) does not
 \(I_2\) satisfies \(\alpha\), \(I_1\) does not
 Neither \(I_1\) nor \(I_2\) satisfies \(\alpha\)
 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
 $\forall x(P(x) \implies (G(x) \wedge S(x)))$
 $\forall x((G(x) \wedge S(x)) \implies P(x))$
 $\exists x((G(x) \wedge S(x)) \implies P(x))$
 $\forall x((G(x) \vee S(x)) \implies P(x))$
Which one of the following wellformed formulae in predicate calculus is NOT valid ?
 $(\forall x p(x) \implies \forall x q(x)) \implies (\exists x \neg p(x) \vee \forall x q(x))$
 $(\exists x p(x) \vee \exists x q (x)) \implies \exists x (p(x) \vee q (x))$
 $\exists x (p(x) \wedge q(x)) \implies (\exists x p(x) \wedge \exists x q(x))$
 $\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)
 ((∀x)[α] ⇒ (∀x)[β]) ⇒ (∀x)[α ⇒ β]
 (∀x)[α] ⇒ (∃x)[α ∧ β]
 ((∀x)[α ∨ β] ⇒ (∃x)[α]) ⇒ (∀x)[α]
 (∀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)?
 $\Psi \wedge \Phi \wedge [\forall x \in A : \neg S(x, x)]$
 $\Psi \wedge \Phi \wedge [\forall x \in A : S(x, x)]$
 $\Psi \wedge \Phi \wedge [\forall x,y \in A : S(x, x) \wedge S(x, y) \rightarrow S(y,y)]$
 $\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)]$
 $\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)))?$$
 all flies eat bats
 every fly is eaten by some bat
 bats eat only flies
 every bat eats flies
 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"?
 $\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]$
 $\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]$
 $\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]$
 $\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]$
 $\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 firstorder logic sentence $F:\forall x(\exists yR(x,y))$. Assuming nonempty logical domains, which of the sentences below are implied by $F$?
 $\exists y(\exists xR(x,y))$
 $\exists y(\forall xR(x,y))$
 $\forall y(\exists xR(x,y))$
 $¬\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 wellformed formulae:
 $\neg \forall x(P(x))$
 $\neg \exists x(P(x))$
 $\neg \exists x(\neg P(x))$
 $\exists x(\neg P(x))$
Which of the above are equivalent?
 I and III
 I and IV
 II and III
 II and IV
“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?
 $\forall x: glitters (x)\Rightarrow \neg gold(x)$
 $\forall x: gold (x)\Rightarrow glitters(x)$
 $\exists x: gold(x)\wedge \neg glitters(x)$
 $\exists x: glitters(x)\wedge \neg gold(x)$
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
(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))$$
$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.
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)))$$
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
expresses the statement "there exists a prime number" (the number 1 also satisfies this statement).
Note here that is equivalent to .
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/FirstOrder_Logic#Semantics
ref@ http://math.stackexchange.com/questions/1037795/whatisthemeaningofthispredicatestatement
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)
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)
B) All nonrainy days are cold
C)Some nonrainy days are cold.
D) Some rainy days are not cold.
option D
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.
[(∃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
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
[∀ 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
(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.
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)
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
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
$= ¬(\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.
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.
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.
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).
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.
@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)[P_{x}⇔(∀y)[¬Q_{xy}]]⇒(∀x)[¬P_{x}]
LHS:(∀x)[P_{x}⇔(∀y)[¬Q_{xy}]]
consider only (∀y)[¬Q_{xy}] 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)[P_{x}⇔True], "P_{x}⇔True" this means P_{x }is True, which is same as writing "P_{x}" only_{.}
Finally, we reduced LHS to (∀x)[P_{x}]
α: (∀x)[P_{x}]⇒(∀x)[¬P_{x}]
LHS: (∀x)[P_{x}].
LHS is false for I_{1} bcoz not all x are primes False ⇒ Anything is True. For I_{1} α is true hence I_{1} satisfies α.
Similarly, LHS is false for I_{2} also bcoz not all x are composite. hence I_{2} satisfies α.
Option D.
$\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 nonprime natural numbers. So, FALSE $\Rightarrow$ FALSE returns TRUE making both $I_1$ and $I_2$ satisfy $\alpha$. D choice.
Answer is D.
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
(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.
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 ...
So only bats eat flies.
Option e
Just translating to English:
 Every women who is a lawyer admires some women judge.
 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.
 Every women who is a lawyer admires every judge.
 There is some judge who is admired by every women lawyer.
 Every women lawyer admire some judge.
So, option E is the 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)
so B is the ans.
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.
(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.
"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.
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"
Let's break it down. Consider an ordered structure (directed graph).
 $\forall x \exists y : R(x,y) \quad \equiv$ Every vertex has atleast 1 outgoing edge.
 $\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.
 $\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.
 $\forall x: \lnot R(x,x) \quad \equiv$ We cannot have a selfloop in the graph. That is, $R(x,y)$ is irreflexive.
Now, such a nontrivial (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.
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.
Consider the following two statements.
 There are infinitely many interesting whole numbers.
 There are finitely many uninteresting whole numbers.
Which of the following is true?
 Statements 1 and 2 are equivalent.
 Statement 1 implies statement 2.
 Statement 2 implies statement 1.
 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 lefthand neighbour?
(ii) What race is your righthand 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?
 $A$ is Pink, $B$ is White, $C$ is Blue.
 $A$ is Blue, $B$ is Pink, $C$ is White.
 $A$ is Pink, $B$ is Blue, $C$ is Pink.
 $A$ is White, $B$ is Pink, $C$ is Blue.
 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?
 Only claim $1$ follows.
 Only claim $2$ follows.
 Either claim $1$ or claim $2$ follows but not both.
 Neither claim $1$ nor claim $2$ follows.
 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?
 If a person is known to be corrupt, he is kind
 If a person is not known to be corrupt, he is not kind
 If a person is kind, he is not known to be corrupt
 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?
 The result is head
 The result is tail
 If the person is of Type 2, then the result is tail
 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?
 Mr. M is liable
 The receipt is not forged
 Mr. M will go bankrupt
 The bank will go bankrupt
 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?
 A is a Knight and B is a Knave.
 A is a Knave and B is a Knight.
 Both are Knaves.
 Both are Knights.
 No conclusion can be drawn.
$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.
 People will not suffer
 If the inflation is not regulated, then wages are not raised
 Prices are not raised
 If the inflation is not regulated, then the prices are not raised
 Wages are not raised
Answers: Logical Reasoning
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
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
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.
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
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.
$\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
 If I'm telling the truth result is head
 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
 I'm telling the truth and result is not head
 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.
we do not know what is the person from whom those words are coming from, we can have two cases :
 Truthteller : definitely implies that result of toss is Head.
 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
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
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.
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
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.
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 )
 $Mr.M$ is guilty.
 $Mr.M$ is not guilty.
 From these facts one cannot conclude that $Mr.M$ is guilty.
 There is a witness who is lying.
 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.
 ∀x[(tiger(x) ∧ lion(x)) → {(hungry(x) ∨ threatened(x)) → attacks(x)}]
 ∀x[(tiger(x) ∨ lion(x)) → {(hungry(x) ∨ threatened(x)) ∧ attacks(x)}]
 ∀x[(tiger(x) ∨ lion(x)) → {attacks(x) → (hungry(x) ∨ threatened(x))}]
 ∀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$.
 $(\exists x) (\text{boy}(x) \rightarrow (\forall y) (\text{girl}(y) \land \text{taller}(x, y)))$
 $(\exists x) (\text{boy}(x) \land (\forall y) (\text{girl}(y) \land \text{taller}(x, y)))$
 $(\exists x) (\text{boy}(x) \rightarrow (\forall y) (\text{girl}(y) \rightarrow \text{taller}(x, y)))$
 $(\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))$$?
 Everyone can fool some person at some time
 No one can fool everyone all the time
 Everyone cannot fool some person all the time
 No one can fool some person at some time
$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 wellformed formulae are valid:
 $\left(P\Rightarrow Q\right) {\wedge} \left(Q \Rightarrow R\right) \Rightarrow \left(P \Rightarrow R\right)$
 $\left(P\Rightarrow Q\right) \Rightarrow \left( \neg P \Rightarrow \neg Q\right)$
 $\left(P{\wedge} \left(\neg P \vee \neg Q\right)\right) \Rightarrow Q$
 $\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 wellformed formulas are equivalent?
 $P \rightarrow Q$
 $\neg Q \rightarrow \neg P$
 $\neg P \vee Q$
 $\neg Q \rightarrow P$
What is the first order predicate calculus statement equivalent to the following?
"Every teacher is liked by some student"
 $∀(x)\left[\text{teacher}\left(x\right) → ∃(y) \left[\text{student}\left(y\right) → \text{likes}\left(y,x\right)\right]\right]$
 $∀(x)\left[\text{teacher}\left(x\right) → ∃(y) \left[\text{student}\left(y\right) ∧ \text{likes}\left(y,x\right)\right]\right]$
 $∃(y) ∀(x)\left[\text{teacher}\left(x\right) → \left[\text{student}\left(y\right) ∧ \text{likes}\left(y,x\right)\right]\right]$
 $∀(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"
 $\lnot \forall x\, \Bigl (\graph(x) \implies \connected(x) \Bigr )$
 $\exists x\, \Bigl (\graph(x) \land \lnot \connected(x) \Bigr )$
 $\lnot \forall x \, \Bigl ( \lnot \graph(x) \lor \connected(x) \Bigr )$
 $\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
 $(\neg p \wedge r) \wedge (\neg r \rightarrow (p \wedge q))$
 $(\neg p \wedge r) \wedge ((p \wedge q) \rightarrow \neg r)$
 $(\neg p \wedge r) \vee ((p \wedge q) \rightarrow \neg r)$
 $(\neg p \wedge r) \vee (r \rightarrow (p \wedge q))$
(A) a tautology.
(B) a contradiction.
(C) always TRUE when $p$ is FALSE.
(D) always TRUE when $q$ is TRUE.
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
$\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}$$
I think this is the approach for this question.
first statement is the correct answer for this question.
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
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 boyless 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
Should be the 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.
¬∃x∀y∀t(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.
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)))$.
P_{1} :P
P_{2}: (P → Q) ∨ (P ∧ (R → Q) )
so P_{1} ∧ P_{2} = [P . [(P' + Q) +(PR' +PQ)]
= [P . [P' + Q + PR' +PQ]]
= [ PR' +PQ]
= P(R → Q)
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.
 P→Q = P'+Q
 ¬Q→¬P=Q+P'
 ¬PVQ =P'+Q
so A,B,C are equivalent .
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.
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))
Answer is A
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)
now taking the contrapositive of ~P> ~Q we get Q>P hence statement 2 is correct
So the answer is
OPTION (D)
= ~(~p) $\vee$ ~q
= p $\vee$ ~q
= ~q $\vee$ p
= q $\Rightarrow$ p
$\therefore$ D should be answer.
Consider two wellformed 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?
 F1 is satisfiable, F2 is valid
 F1 unsatisfiable, F2 is satisfiable
 F1 is unsatisfiable, F2 is valid
 F1 and F2 are both satisfiable
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?
 $P ∨ \neg Q$
 $\neg(\neg P ∧ Q)$
 $(P ∧ Q) ∨ (P ∧ \neg Q) ∨ (\neg P ∧ \neg Q)$
 $(P ∧ Q) ∨ (P ∧ \neg Q) ∨ (\neg P ∧ Q)$
 Only I and II
 Only I, II and III
 Only I, II and IV
 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?
 $a \vee b \to b \wedge c$
 $a \wedge b \to b \vee c$
 $a \vee b \to \left(b \to c \right)$
 $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 truthvalue of the formula $(a ∧ b) → (a ∧ c) ∨ d$ is always
 True
 False
 Same as the truthvalue of $b$
 Same as the truthvalue of $d$
Consider the following expressions:
 $false$
 $Q$
 $true$
 $P\vee Q$
 $\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":
 If Kareena and Parineeti do not go to the shopping mall then it is not raining.
 If Kareena and Parineeti do not go to the shopping mall then it is raining.
 If it is raining then Kareena and Parineeti go to the shopping mall.
 If it is not raining then Kareena and Parineeti do not go to the shopping mall.
 None of the above.
$$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$?
 $\neg Q □ \neg P$
 $P□\neg Q$
 $\neg P□Q$
 $\neg P□ \neg Q$
Let $A$ be a tautology and $B$ any other formula. Prove that $(A \vee B)$ is a tautology.
a) True
b) Multiple Values
c) False
d) Cannot be determined
Which of the following propositions is a tautology?
 $(p \vee q) \rightarrow p$
 $p \vee (q \rightarrow p)$
 $p \vee (p \rightarrow q)$
 $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

$((x \rightarrow y) \wedge x) \rightarrow y$

$((\sim x \rightarrow y) \wedge (\sim x \rightarrow \sim y)) \rightarrow x$

$(x \rightarrow (x \vee y))$

$((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?
 Only L is TRUE.
 Only M is TRUE.
 Only N is TRUE.
 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?
 $(( p \leftrightarrow q) \wedge r) \vee (p \wedge q \wedge \sim r)$
 $( \sim (p \leftrightarrow q) \wedge r)\vee (p \wedge q \wedge \sim r)$
 $( (p \to q) \wedge r) \vee (p \wedge q \wedge \sim r)$
 $(\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
 I stay if you go
 If I stay then you go
 If you do not go then I do not stay
 If I do not stay then you go
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)
 $(X\land \neg Z) \rightarrow Y$
 $(X \land Y) \rightarrow \neg Z$
 $X \rightarrow(Y\land \neg Z)$
 $(X \rightarrow Y)\land \neg Z$
$A \leftrightarrow (A \lor A)$
$(A \lor B) \rightarrow B$
$A \land (\neg (A \lor B))$
X ≡ Y
X → Y
Y → X
¬Y → X
Which one of the following is NOT equivalent to $p ↔ q$?
 $(\neg p ∨ q) ∧ (p ∨ \neg q)$
 $(\neg p ∨ q) ∧ (q → p)$
 $(\neg p ∧ q) ∨ ( p ∧ \neg q)$
 $(\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)$
 satisfiable but not valid
 valid
 a contradiction
 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?
 P1 is a tautology, but not P2
 P2 is a tautology, but not P1
 P1 and P2 are both tautologies
 Both P1 and P2 are not tautologies
The proposition $p \wedge (\sim p \vee q)$ is:

a tautology

logically equivalent to $p \wedge q$

logically equivalent to $p \vee q$

a contradiction

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?
 ((P ∨ R) ∧ (Q ∨ ¬R)) ⇒ (P ∨ Q) is logically valid
 (P ∨ Q) ⇒ ((P ∨ R)) ∧ (Q ∨ ¬R)) is logically valid
 (P ∨ Q) is satisfiable if and only if (P ∨ R) ∧ (Q ∨ ¬R) is satisfiable
 (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
=⌝ 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
Satisfiable : A wff which is not a contradiction(always false) is satisfiable. It may be a tautology.
$$\text{False} \rightarrow \text{anything} = \text{True, always}$$
answer B
I. P∨ ~Q
II. ~ ( ~P∧Q) apply De Morgan's law. we get P∨ ~Q
III. (P∧Q)∨(P∧~ Q)∨( ~P∧ ~Q)
=[(P∧Q)∨(P∧~ Q)]∨( ~P∧ ~Q)
=[P(QV ~Q)]∨( ~P∧ ~Q)
=P∨( ~P∧ ~Q)
= P∨ ~Q
$\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.
Given that, ab∨~b
It is equivalent to aTRUE
(a∧b)((a∧c)∨d)
wkt, 1∧x = x
(a∧b) = 1∧b = b
similarly, 1∧c = c
We now have, b (c∨d)
Which can be written as,
~b∨c∨d
We also know that bc
~b∨c = TRUE
TRUE∨d = TRUE
And hence answer is option a
$4$ should be the correct answer.
all except the option i satisfies.
P and Q > true, P or Q,~Q or P,Q
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)
= 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)..
$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 
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$
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.
$\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$
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.
=(P OR NOT P) OR Q Associativity rule
=T OR Q
=T
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)
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"
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.
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
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.
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 >
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
((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"
This can be solved by Truth table. But there is something else which can be done quickly. See what each formula means:
1. A↔(A∨A) It says if A then (A or A) and if (A or A) then A. Always a tautology
2. (A∨B)→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∧(¬(A∨B)) When A is true ¬(A∨B) will be false. So, this formula is a contradiction
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 demorgan's Law)
A.A'B' = 0.
Hence it is a Contradiction.
= ~(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.
= (p→ q) ∧ (q→p)
= (⏋p ∨ q) ∧ (q → p) ( As p→ q = ⏋p ∨ q )
=(⏋p ∨ q) ∧ (⏋q ∨ p)
=(⏋p ∧ ⏋q) ∨ (p ∧ q)
So, answer C
It is false when P = T, Q = T, R = F
It is true (satisfiable) when P = T. Q = T, R = T
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)
= (p ^ ~p) v (p ^ q)
= False V (p^q)
= (p^q)
((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.
((P ∨ R)) ∧ (Q ∨ ¬R))
= (P∧ ¬R) ∨ (Q ∧ R)
(P∨Q) doesn't imply (P∧ ¬R) ∨ (Q ∧ R)
$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.
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?
 $(a, b, c) = (0.51, 0.51, 0.51);$
 $(a, b, c) =(0.61, 0.71, 0.67);$
 $(a, b, c) = (0.68, 0.68, 0.68);$
 $(a, b, c) = (0.49, 0.49, 0.49);$
 None of the above.
$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:
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
~((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^{2 }.
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.
(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
 0
 1
 2
 3
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?
 f (x, y) = x + y  3
 f (x, y) = max(x, y)
 f (x, y) = x^{y}
 I and II only
 II and III only
 I and III only
 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 ≠?
 Both commutative and associative
 Commutative but not associative
 Not commutative but associative
 Neither commutative nor associative
Answers: Binary Operation
$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.
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
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$.
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 nonnegative integers, if f(x)=x^{2} and g(x)=x+1, then (f∘g)(x)=(x+1)^{2} while (g∘f)(x)=x^{2}+1, and they're different functions.
Answer: A
I. Identity element is 3.
II. Identity element is 1.
III. There is no identity element. (x^{y} ≠ y^{x}, when x ≠ y)
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?
 Only S1 is true
 Only S2 is true
 Both S1 and S2 are true
 Neither S1 nor S2 are true
Answers: Boolean Algebra
(P#Q)#R=(P'+Q')#R
=P.Q+R'
whereas
P#(Q#R)=P'+(Q#R)'
=P'+(Q'+R')'
=P'+QR
=(XY)' (DEMORGAN'S LAW)
so this # operatoe is nand operator
Nand is commutative but not associative. So B is the answer
State whether the above statement is true or false with reason.
Let $\Sigma$ be a finite nonempty alphabet and let $2^{\Sigma^*}$ be the power set of $\Sigma^*$. Which one of the following is TRUE?
 Both $2^{\Sigma^*}$ and $\Sigma^*$ are countable
 $2^{\Sigma^*}$ is countable and $\Sigma^*$ is uncountable
 $2^{\Sigma^*}$ is uncountable and $\Sigma^*$ is countable
 Both $2^{\Sigma^*}$ and $\Sigma^*$ are uncountable
Answers: Countable Uncountable Set
https://proofwiki.org/wiki/Subset_of_Countable_Set_is_Countable
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
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}
 28
 33
 37
 44
Answers: Counting
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 20128 +4 = 90
X = { n ,1 ≤ n ≤ 123, n is not divisible by either 2, 3 or 5 }
Cardinality = 123  90 = 33
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, n1)
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(melement) to a set B(nelement) ,
should be hold " m >= n"
then number of onto function $= n^m  ^nC_1(n1)^m + ^nC_2(n2)^m  ^nC_3(n3)^m+$ .........and so on till $^nC_n(nn)^m +, ,$alternative
=
here m=4 and n=3 (here above condition valid)
then
number of onto function $= 3^4  ^3C_1(31)^4 + ^3C_2(32)^4  ^3C_3(33)^4$
$= 81  3*16 +3*1  1*0$
$= 36$
ref@ http://www.cse.iitd.ac.in/~mittal/stirling.html
$\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}$
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, j1)$$ as per the nondecreasing 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
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
Let R and S be any two equivalence relations on a nonempty set A. Which one of the following statements is TRUE?
 R ∪ S, R ∩ S are both equivalence relations
 R ∪ S is an equivalence relation
 R ∩ S is an equivalence relation
 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 nonzero rational numbers
 R4 $(a,b)$ iff $ab \leq 2$ over the set of natural numbers
Which of the following statements is correct?
 R1 and R2 are equivalence relations, R3 and R4 are not
 R1 and R3 are equivalence relations, R2 and R4 are not
 R1 and R4 are equivalence relations, R2 and R3 are not
 R1, R2, R3 and R4 all are equivalence relations
The union of two equivalence relations is also an equivalence relation.
Answers: Equivalence Classes
option c.
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: aa<=2
Symmetric: if ab<=2 definately ba<=2 when a,b are natural numbers
Transitive: ab<=2 and bc<=2, doesnt imply ac<=2
ex: 42<=2 and 20<=2 , but 40>2 ,
hence, R2 and R4 are not equivalence
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.
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.
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  (a^{2} + b^{2}) ≤ 1}
 S4: {ia  a is real}
 only S1
 S1 and S3
 S2 and S3
 S1 and S2
Answers: Fields
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 nonzero 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 nonzero 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 nonzero element : Additive inverse is aib, which belongs to given set. Multiplicative identity is , which also belongs to given set.
(S3) : {a + ib  (a^{2} + b^{2}) ≤ 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.
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?
 $f$ is onto (surjective)
 $f$ is onetoone (injective)
 $f$ is both onetoone and onto (bijective)
 the range of $f$ is finite
 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?
 g is onto => h is onto
 h is onto => f is onto
 h is onto => g is onto
 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?
 $f$ and $g$ should both be onto functions
 $f$ should be onto but $g$ need not to be onto
 $g$ should be onto but $f$ need not be onto
 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?
 $P, Q$ and $R$ are true
 Only $Q$ and $R$ are true
 Only $P$ and $Q$ are true
 Only $R$ is true
What is the maximum number of different Boolean functions involving $n$ Boolean variables?
 $n^2$
 $2^n$
 $2^{2^n}$
 $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?
 For any subsets $A$ and $B$ of $X, fA \cup B = f(A) + f(B)$
 For any subsets $A$ and $B$ of $X, f(A \cap B) = f(A) \cap f(B)$
 For any subsets $A$ and $B$ of $X, f(A \cap B = \min \{f(A), f(B)\}$
 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?
 $f$ cannot be onetoone (injective)
 $f$ cannot be onto (surjective)
 $f$ is both onetoone and onto (bijective)
 there is no such $f$ possible
 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:
 0, 1
 1, 0
 0, 1
 1, 2
If $g(x) = 1  x$ and $h(x) = \frac{x}{x1}$, then $\frac{g(h(x))}{h(g(x))}$ is:
 $\frac{h(x)}{g(x)}$
 $\frac{1}{x}$
 $\frac{g(x)}{h(x)}$
 $\frac{x}{(1x)^{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?
 Both $\left\{\textit{f} \right\}$ and $\left\{ \textit{g}\right\}$ are functionally complete
 Only $\left\{ \textit{f} \right\}$ is functionally complete
 Only $\left\{ \textit{g}\right\}$ is functionally complete
 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 _______.
(A) $ 2^{n}$
(B) $2^{n} – 1$
(C) $2^{n} – 2$
(D) $2(2^{n} – 2)$
Let $F$ be the set of onetoone functions from the set $\{1, 2, \dots, n\}$ to the set $\{1, 2,\dots, m\}$ where $m\geq n\geq1$.

How many functions are members of $F$?

How many functions $f$ in $F$ satisfy the property $f(i)=1$ for some $i, 1\leq i \leq n$?

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, n1} \left(y_{1}, y_{2},....y_{i1}, y_{i+1},...,y_{n}\right)$ (where $y_{i}$ is omitted) is equivalent to
 $T_{k1}, n(y)$
 $T_{k, n}(y)$
 $y_{i}$
 $\neg y_{i}$
 None of the above.
Given a boolean function f (x_{1}, x_{2}, ..., x_{n}), which of the following equations is NOT true
 f (x_{1}, x_{2}, ..., x_{n}) = x_{1}'f(x_{1}, x_{2}, ..., x_{n}) + x_{1}f(x_{1}, x_{2}, ..., x_{n})
 f (x_{1}, x_{2}, ..., x_{n}) = x_{2}f(x_{1}, x_{2}, …, x_{n}) + x_{2}'f(x_{1}, x_{2}, …,x_{n})
 f (x_{1}, x_{2}, ..., x_{n}) = x_{n}'f(x_{1}, x_{2}, …, 0) + x_{n}f(x_{1}, x_{2}, …,1)
 f (x_{1}, x_{2}, ..., x_{n}) = f(0, x_{2}, …, x_{n}) + f(1, x_{2}, .., x_{n})
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 ith prime number $\left(p_1 = 2\right)$.
For a nonempty 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 nonempty 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 nonempty sequence of strings?

$2^73^75^7$

$2^83^85^8$

$2^93^95^9$

$2^{10}3^{10}5^{10}$
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
 $z^{2^{xy}}$
 $z \times 2^{xy}$
 $z^{2^{x+y}}$
 $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

$X =1, Y =97$

$X =97, Y =1$

$X =97, Y =97$

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, xy)$. The inverse function of $f$ is given by
(a) $f^{1} (x,y) = \left( \frac {1}{x+y}, \frac{1}{xy}\right)$
(b) $f^{ 1} (x,y) = (xy , x+y)$
(c) $f^{1} (x,y) = \left( \frac {x+y}{2}, \frac{xy}{2}\right)$
(d) $f^{1}(x,y)=\left [ 2\left(xy\right),2\left(x+y\right) \right ]$
Let \(f : A \to B\) be an injective (onetoone) 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?
 \(g(h(D)) \subseteq D\)
 \(g(h(D)) \supseteq D\)
 \(g(h(D)) \cap D = \phi\)
 \(g(h(D)) \cap (B  D) \ne \phi\)
$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 X_{1}.........X_{n} 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 X_{j }that 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:
 3m
 3n
 2m+1
 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?
 Only S1 is correct
 Only S2 is correct
 Both S1 and S2 are correct
 None of S1 and S2 is correct
$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
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.
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
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) = x1, 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 oneone.
Let h be onto (onto means codomain = 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).
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.
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$ codomain = range as there are only 2015 values in codomain. 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.
answer  C
size of domain = number of different combinations of inputs = 2^{n}
size of codomain = 2 ( {0,1} )
number of functions = (size of codomain)^{(size of domain)}^{ }
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.
Even if it can be onetoone in the following way,
But, It cannot be onto,because, the number of elements in domain $(A)$ $<$ the number of elements in codomain ($P(A)$) . For a function to be onto, the domain should be able to cover all elements of codomain with each element of the domain having exactly one image in codomain.
so option(B)
Put the value of x of all the options in f(x) and find value of f(x).
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)=10=1
so ans should be 0,1
$g\left(h\left(x\right)\right) =g\left(\frac{x}{x1}\right)$
$=1\frac{x}{x1}$
$= \frac{1}{x1}$
$h\left(g\left(x\right)\right) =h(1x)$
$=\frac{1x}{x}$
$\frac{g(h(x))}{h(g(x))} = \frac{x}{(1x)(x1)} = \frac{h(x)}{g(x)}$
option A)
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.
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.$
Number of functions in S is 2^16 so in N is (2^(2^16)), and value of loglog n will be 16.
= 20 * 19 / (20 * 20) = 0.95
PS: Each element of the domain set in a function must be mapped to some element of the codomain set.
2^n  2 in words (total functions  2 functions where all elements maps exactly one element)
No onto (or surjective) functions are there from an nelement (n≥2) set to a 2element 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
(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 ^{m1}\mathbb{P}_{n1}$ 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.
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.
Answer: D
Proceed by taking f(x_{1}) = x_{1}
LHS: f(x_{1}) = 0 when x_{1 }= 0
LHS: f(x_{1}) = 1 when x_{1 }= 1
RHS: f(0) + f(1) = 0 + 1 = always 1
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.
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$.