Set Theory & Logic

'When it is raining, peacocks dance.' Based only on this sentence, which one of the following options is necessarily true?

In the 2020 summer Olympics' Javelin throw finals, Neeraj Chopra exhibited a spectacular performance to win the gold medal. The silver medal was won by Jakub Vadlejch and the bronze medal was won by Vitezlav Vesely. Ther...

'When the teacher is in the room, all students stand silently.' If the above statement is true, which one of the following statements is not necessarily true?

For two different persons $x$ and $y$, the predicate $M(x, y)$ denotes that $x$ knows $y$. Consider the following statement. There is a person who does not know anyone else, but that person is known by everyone else. Whi...

The figure in Panel I below is a grid of cells with four rows and four columns. The numbers on the top and on the left represent the number of cells that are to be shaded in that column and row, respectively. Which one o...

Let $P(x)$ be an arbitrary predicate over the domain of natural numbers. Which ONE of the following statements is TRUE?

Based only on the conversation below, identify the logically correct inference: "Even if I had known that you were in the hospital, I would not have gone there to see you", Ramya told Josephine.

Consider the relationships among $P, Q, R, S$, and $T$ : $\bullet$ $P$ is the brother of $Q$. $\bullet$ $S$ is the daughter of $Q$. $\bullet$ $T$ is the sister of $S$. $\bullet$ $R$ is the mother of $Q$. The following st...

Which of the following predicate logic formulae/formula is/are CORRECT representation(s) of the statement: "Everyone has exactly one mother"? The meanings of the predicates used are: $\bullet$ mother $(y, x): y$ is the m...

Let $A$ and $B$ be non-empty finite sets such that there exist one-to-one and onto functions (i) from $A$ to $B$ and (ii) from $A \times A$ to $A \cup B$. The number of possible values of $|A|$ is _______

In an engineering college of 10,000 students, 1,500 like neither their core branches nor other branches. The number of students who like their core branches is 1/4 th of the number of students who like other branches. Th...

Let p and q be the following propositions: p : Fail grade can be given. q : Student scores more than 50% marks. Consider the statement: “Fail grade cannot be given when student scores more than 50% marks.” Which one of t...

The country of Zombieland is in distress since more than 75% of its working population is suffering from serious health issues. Studies conducted by competent health experts concluded that a complete lack of physical exe...

Consider two functions of time (t), $$f(t)=0.01\,t^2$$ $$g(t)=4\,t$$ where $$0 Now consider the following two statements : (i) For some $$t > 0,g(t) > f(t)$$. (ii) There exists a $$T$$, such that $$f(t) > g(t)$$ for all...

Geetha has a conjecture about integers, which is of the form $$\forall x\left( {P(x) \Rightarrow \exists yQ(x,y)} \right)$$, where P is a statement about integers, and Q is a statement about pairs of integers. Which of t...

Given below are four statements : Statement 1 : All students are inquisitive. Statement 2 : Some students are inquisitive. Statement 3 : No student is inquisitive. Statement 4 : Some students are not inquisitive. From th...

Some people believe that "what gets measured, improves". Some other believe that "what gets measured, gets gamed". One possible reason for the difference in the beliefs is the work culture in organizations. In organizati...

Let p and q be two propositions. Consider the following two formulae in propositional logic. S 1 : (¬p ∧ (p ∨ q)) → q S 2 : q → (¬p ∧ (p ∨ q)) Which one of the following choices is correct?

A polygon is convex if, for every pair of points. P and Q belonging to the polygon, the line segment PQ lies completely inside or on the polygon. Which one of the following is NOT a convex polygon?

Given below are two statements I and II and two conclusions I and II : Statement : I. All bacteria are microorganisms. II. All pathogens are microorganisms. Conclusions : I. Some pathogens are bacteria. II. All pathogens...

Choose the correct choice(s) regarding the following propositional logic assertion S: S : ((P ∧ Q)→ R)→ ((P ∧ Q)→ (Q → R))

The drawn of the 21st century witnessed the melting glaciers oscillating between giving too much and too little to billions of people who depend on them for fresh water. The UN climate report estimates that without deep...

Which one of the following predicate formulae is NOT logically valid? Note that W is a predicate formula without any free occurrence of x .

"A recent High Court judgement has sought to dispel the idea of begging as a disease — which leads to its stigmatization and criminalization — and to regard it as a symptom. The underlying disease is the failure of the s...

Consider the first order predicate formula φ: ∀x[(∀z z|x ⇒ ((z = x) ∨ (z = 1))) ⇒ ∃w (w > x) ∧ (∀z z|w ⇒ ((w = z) ∨ (z = 1)))] Here 'a|b' denotes that 'a divides b', where a and b are integers. Consider the following set...

Three of the five students allocated to a hostel put in special requests to the warden. Given the floor plan of the vacant rooms, select the allocation plan that will accommodate all their requests. Request by X: Due to...

In a college, there are three student clubs. Sixty students are only in the Drama club, 80 students are only in the Dance club, 30 students are only in the Maths club, 40 students are in both Drama and Dance clubs, 12 st...

The police arrested four criminals - P, Q, R and S. The criminals knew each other. They made the following statements: P says "Q committed the crime." Q says "S committed the crime." R says "I did not do it." S says "Wha...

Consider the first-order logic sentence $$\varphi \equiv \,\,\,\,\,\,\,\exists s\exists t\exists u\forall v\forall w$$ $$\forall x\forall y\psi \left( {s,t,u,v,w,x,y} \right)$$ where $$\psi $$ $$(𝑠,𝑡, 𝑢, 𝑣, 𝑤, 𝑥, �...

Let N be the set of natural numbers. Consider the following sets. $$\,\,\,\,\,\,\,\,$$ $$P:$$ Set of Rational numbers (positive and negative) $$\,\,\,\,\,\,\,\,$$ $$Q:$$ Set of functions from $$\left\{ {0,1} \right\}$$ t...

Consider the first-order logic sentence $F: \forall x(\exists y R(x, y))$. Assuming non-empty logical domains, which of the sentences below are implied by $F$? I. $\quad \exists y(\exists x R(x, y))$ II. $\quad \exists y...

Six people are seated around a circular table. There are at least two men and two women. There are at least three right-handed persons. Every woman has a left-handed person to her immediate right. None of the women are r...

The statement $(\neg p) \Rightarrow(\neg q)$ is logically equivalent to which of the statements below? I. $\quad p \Rightarrow q$ II. $q \Rightarrow p$ III. $(\neg q) \vee p$ IV. $(\neg p) \vee q$

All hill-stations have a lake. Ooty has two lakes. Which of the statement(s) below is/are logically valid and can be inferred from the above sentences? $$\,\,\,\,\,\,\,\,\,$$$$(i)$$ $$\,\,\,\,\,\,\,\,\,\,$$ Ooty is not a...

Which one of the following well-formed formulae in predicate calculus is NOT valid?

Consider the following statements relating to the level of poker play of four players $$P, Q, R$$ and $$S.$$ $$\,\,\,\,\,\,\,\,\,{\rm I}.\,\,\,\,\,\,\,\,$$ P always beats Q $$\,\,\,\,\,\,\,{\rm I}{\rm I}.\,\,\,\,\,\,\,\,...

Consider the following expressions: $$\,\,\,\,\,\,\,\,\,\,\,\,\,$$ $$(i)$$ $$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$$ false $$\,\,\,\,\,\,\,\,\,\,\,\,$$ $$(ii)$$ $$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$$ $$Q$$ $$\,\,\,\,\,\,\,\,\,\,\,$...

Let $$p,q,r,s$$ represent the following propositions. $$p:\,\,\,x \in \left\{ {8,9,10,11,12} \right\}$$ $$q:\,\,\,x$$ is a composite number $$r:\,\,\,x$$ is a perfect square $$s:\,\,\,x$$ is a prime number The integer $$...

Among $$150$$ faculty members in an institute, $$55$$ are connected with each other through Facebook ® and $$85$$ are connected through WhatsApp ® . $$30$$ faculty members do not have Facebook ® or whatsApp ® accounts. T...

The cardinally of the power set of $$\left\{ {0,1,2,\,\,....,\,\,10} \right.\left. \, \right\}$$ is _____________.

For a set A, the power set of A is denoted by 2 A . If A = {5, {6}, {7}}, which of the following options are TRUE? I. $$\phi \in {2^A}$$ II. $$\phi \subseteq {2^A}$$ III. $$\left\{ {5,\left\{ 6 \right\}} \right\} \in {2^...

Which one of the following well formed formulae is a tautology?

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 whi...

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...

Suppose $$𝑈$$ is the power set of the set $$S = \left\{ {1,2,3,4,5,6,} \right\}$$. For any $$T \in U,$$ let $$\left| T \right|$$ denote the number of elements in $$𝑇$$ and $$T'$$ denote the complement of $$𝑇.$$ For an...

Which one of the following propositional logic formulas is TRUE when exactly two of $$p, q,$$ and $$r$$ are TRUE ?

Let $$X$$ and $$Y$$ be finite sets and $$f:X \to Y$$ be a function. Which one of the following statements is TRUE?

The CORRECT formula for the sentence, "not all rainy days are cold" is

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 ab...

Consider the following relation on subsets of the set S integers between 1 and 2014. For two distinct subsets U and V of S we say U < V if the minimum element in the symmetric difference of the two setss is in U. Conside...

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 of the following about L, M, and N is Correct?

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

What is the logical translation of the following statement? "None of my friends are perfect."

Which one of the following is NOT logically equivalent to $$\neg \exists x\left( {\forall y\left( \alpha \right) \wedge \left( {\forall z\left( \beta \right)} \right)} \right)?$$

Consider the following logical inferences. $${{\rm I}_1}:$$ If it rains then the cricket match will not be played. The cricket match was played. Inference: there was no rain. $${{\rm I}_2}:$$ If it rains then the cricket...

What is the correct translation of the following statement into mathematical logic? "Some real numbers are rational"

Which one of the following options is correct given three positive integers $$x, y$$ and $$z$$, and a predicate $$P\left( x \right) = \neg \left( {x = 1} \right) \wedge \forall y\left( {\exists z\left( {x = y * z} \right...

Suppose the predicate $$F(x,y,t)$$ is used to represent the statements that person $$x$$ can fool person $$y$$ at time $$t$$. Which one of the statements below expresses best the meaning of the formula $$\forall x\exists...

What is the possible number of reflexive relations on a set $$5$$ elements?

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\left( x \right):\,\,x$$ is a gold orn...

Consider the following well-formed formulae: $${\rm I}.$$ $$\,\,\neg \forall x\left( {P\left( x \right)} \right)$$ $${\rm I}{\rm I}.\,\,\,\,\,\,\neg \exists x\left( {P\left( x \right)} \right)$$ $${\rm I}{\rm I}{\rm I}.\...

A set of Boolean connectives is functionally complete if all Boolean function can be synthesized using those, Which of the following sets of connectives is NOT functionally complete?

$$P$$ and $$Q$$ are two propositions. Which of the following logical expressions are equivalent? $${\rm I}.$$ $${\rm P}\, \vee \sim Q$$ $${\rm I}{\rm I}.$$ $$ \sim \left( { \sim {\rm P} \wedge Q} \right)$$ $${\rm I}{\rm...

Which of the following is the negation of $$$\left[ {\forall x,\alpha \to \left( {\exists y,\beta \to \left( {\forall u,\exists v,\gamma } \right)} \right)} \right]?$$$

Let fsa and $$pda$$ be two predicates such that fsa$$(x)$$ means $$x$$ is a finite state automation, and pda$$(y)$$ means that $$y$$ is a pushdown automation. Let $$equivalent$$ be another predicate such that $$equivalen...

Which of the following first order formulae is logically valid? Here $$\alpha \left( x \right)$$ is a first order formulae with $$x$$ as a free variable, and $$\beta $$ is a first order formula with no free variable.

If $$P, Q, R$$ are subsets of the universal set $$U$$, then $$\left( {P \cap Q \cap R} \right) \cup \left( {{P^c} \cap Q \cap R} \right) \cup {Q^c} \cup {R^c}$$ is

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 st...

Let E, F and G be finite sets. Let $$X = \,\left( {E\, \cap \,F\,} \right)\, - \,\left( {F\, \cap \,G\,} \right)$$ and $$Y = \,\left( {E\, - \left( {E\, \cap \,G} \right)} \right)\, - \,\left( {E\, - \,F\,} \right)$$. Wh...

Let $$X,. Y, Z$$ be sets of sizes $$x, y$$ and $$z$$ respectively. Let $$W = X x Y$$ and $$E$$ be the set of all subjects of $$W$$. The number of functions from $$Z$$ to $$E$$ is

Which one of the first order predicate calculus statements given below correctly expresses the following English statement? Tigers and lion attack if they are hungry of threatened.

Let $$P, Q$$, and $$R$$ be sets. Let $$\Delta $$ denote the symmetric difference operator defined as $$P\Delta Q = \left( {P \cup Q} \right) - \left( {P \cap Q} \right)$$. Using venn diagrams, determine which of the foll...

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...

Consider the following propositional statements: $${\rm P}1:\,\,\left( {\left( {A \wedge B} \right) \to C} \right) \equiv \left( {\left( {A \to C} \right) \wedge \left( {B \to C} \right)} \right)$$ $${\rm P}2:\,\,\left(...

Consider the following first order logic formula in which $$R$$ is a binary relation symbol. $$\forall x\forall y\left( {R\left( {x,\,y} \right) \Rightarrow R\left( {y,x} \right)} \right).$$ The formula is

Let $$A$$, $$B$$ and $$C$$ be non-empty sets and let $$X = (A - B) - C$$ and $$Y = (A - C) - (B - C)$$ Which one of the following is TRUE?

What is the first order predicate calculus statement equivalent to the following? Every teacher is liked by some student

Let A be a set with n elements. Let C be a collection of distinct subsets of A such that for any two subsets $${S_1}$$ and $${S_2}$$ in C, either $${S_1}\, \subset \,{S_2}$$ or $${S_2}\, \subset \,{S_1}$$. What is the ma...

Let $$P, Q$$ and $$R$$ be three atomic prepositional assertions. Let $$X$$ denotes $$\left( {P \vee Q} \right) \to R$$ and $$Y$$ denote $$\left( {P \to R} \right) \vee \left( {Q \to R} \right)$$. Which one of the followi...

Let $$p, q, r$$ and $$s$$ be four primitive statements. Consider the following arguments: $$P:\left[ {\left( {\neg p \vee q} \right) \wedge \left( {r \to s} \right) \wedge \left( {p \vee r} \right)} \right] \to \left( {\...

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: $$$\left( {\exists x} \right)\left( {\forall y} \right)\left[ {\le...

The following propositional statement is $$$\left( {P \to \left( {Q \vee R} \right)} \right) \to \left( {\left( {P \wedge Q} \right) \to R} \right)$$$

Let $${R_1}$$ be a relation from $$A = \left\{ {1,3,5,7} \right\}$$ to $$B = \left\{ {2,4,6,8} \right\}$$ and $${R_2}$$ be another relation from $$B$$ to $$C$$ $$ = \left\{ {1,2,3,4} \right\}$$ as defined below: i) An el...

The following resolution rule is used in logic programming. Derive clause $$\left( {P \vee Q} \right)$$ from clauses $$\left( {P \vee R} \right)$$, $$\left( {Q \vee \neg R} \right)$$. Which of the following statements re...

Let $$A$$ be a set of $$n\left( { > 0} \right)$$ elements. Let $${N_r}$$ be the number of binary relations on $$A$$ and Let $${N_r}$$ be the number of functions from $$A$$ to $$A$$. (a) Give the expression for $${N_r}$$...

"If X then Y unless Z" is represented by which of the following formulas in propositional logic? (" $$\neg $$ " is negation, " $$ \wedge $$ " is conjunction, and " $$ \to $$ " is implication)

Determine whether each of the following is a tautology, a contradiction, or neither ("$$ \vee $$" is disjunction, "$$ \wedge $$" is conjuction, "$$ \to $$" is implication, "$$\neg $$" is negation, and "$$ \leftrightarrow...

Let $$f:\,A\, \to B$$ be a function, and let E and F be subsets of A. Consider the following statements about images. $$S1:\,f\,\left( {E\, \cup \,F} \right)\, = \,f\left( E \right)\, \cup \,f\,\left( F \right)$$ $$S2:\,...

Consider the following statements: S1: There exist infinite sets A, B, C such that $$A\, \cap \left( {B\, \cup \,C} \right)$$ is finite. S2: There exist two irrational numbers x and y such that (x + y) is rational. Which...

Consider two well-formed formulas in propositional logic $$F1:P \Rightarrow \neg P$$ $$F2:\left( {P \Rightarrow \neg P} \right) \vee \left( {\neg P \Rightarrow } \right)$$ Which of the following statements is correct?

Let $$a, b, c, d$$ be propositions. Assume that the equivalences $$a \leftrightarrow \left( {b \vee \neg b} \right)$$ and $$b \leftrightarrow c$$ hold. Then the truth value of the formulae $$\left( {a\, \wedge \,b} \righ...

Let P(S) denote the power set of a set S. Which of the following is always true?

The number of binary relations on a set with $$n$$ elements is:

(a) Show that the formula $$\left[ {\left( { \sim p \vee Q} \right) \Rightarrow \left( {q \Rightarrow p} \right)} \right]$$ is not a tautology. (b) Let $$A$$ be a tautology and $$B$$ be any other formula. Prove that $$\l...

What is the converse of the following assertion? I stay only if you go

Which one of the following is false? Read $$ \wedge $$ as AND, $$ \vee $$ as OR, $$ \sim $$ as NOT, $$ \to $$ as one way implication and $$ \leftrightarrow $$ two way implication.

Let $$A$$ and $$B$$ be sets and let $${A^c}$$ and $${B^c}$$ denote the complements of the sets $$A$$ and $$B$$. The set $$\left( {A - B} \right) \cup \left( {B - A} \right) \cup \left( {A \cap B} \right)$$ is equal to

The number of elements in the power set $$P(S)$$ of the set $$S = \left\{ {\left\{ \phi \right\},1,\left\{ {2,3} \right\}} \right\}$$ is

Let $$p$$ and $$q$$ be propositions. Using only the truth table decide whether $$p \Leftrightarrow q$$ does not imply $$p \to \sim q$$ is true or false.

Let $$S$$ be an infinite set and $${S_1},\,\,{S_2},....\,\,{S_n}$$ be sets such that $${S_1} \cup {S_2} \cup ....... \cup {S_n} = S$$. Then

Let $${\rm A}$$ be a finite set of size $$n$$. The number of elements in the power set of $${\rm A} \times {\rm A}$$ is

Show that proposition $$C$$ is a logical consequence of the formula $$A \wedge \left( {A \to \left( {B \vee C} \right) \wedge \left( {B \to \sim A} \right)} \right)$$ using truth tables.

Uses Modus ponens $$\left( {A,\,\,A \to B\,|\,\, = B} \right)$$ or resolution to show that the following set is inconsistent: (1) $$Q\left( x \right) \to P\left( x \right)V \sim R\left( a \right)$$ (2) $$R\left( a \right...

Which of the following is/are tautology?

Which of the following predicate calculus statements is/are valid?

Indicate which of the following well-formed formula are valid: