Table of contents
1.
Introduction
2.
Questions
3.
Frequently Asked Questions
4.
Conclusion
Last Updated: Mar 27, 2024

Propositional and First Order Logic - Part 3

Author Abhay Trivedi
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

Propositional Logic transforms a complete sentence into a symbol. It makes it logical, whereas, in First-Order Logic, a particular sentence will be made that involves relations, functions, and constants. This article has popular propositional and first-order logic questions in past year gate exams.

Questions

61. ECL or emitter-coupled logic is the fastest of all logic families. High speed in ECL is possible because we use transistors in different amplifier configurations, in which they are never driven into ____. [UGC NET CS 2017 Jan - II ]

A. Race condition

B. Saturation

C. Delay

D. High impedance

Answer: B

62. Which of the subsequent statements is true? [UGC NET CS 2017 Jan - III]

Answer: B

63. The first-order logic (FOL) statement ((R ∨ Q) ∧ (P ∨ ¬Q)) is equivalent to which of the following? [UGC NET CS 2017 Jan - III]

A. ((R ∨ ¬Q) ∧ (P ∨ ¬Q) ∧ (R ∨ P))

B. ((R ∨ Q) ∧ (P ∨ ¬Q) ∧ (R ∨ P))

C. ((R ∨ Q) ∧ (P ∨ ¬Q) ∧ (R ∨ ¬P))

D. ((R ∨ Q) ∧ (P ∨ ¬Q) ∧ ( ¬R ∨ P))

Answer: B

Explanation: The FOL(first order logic) statement ((R ∨ Q) ∧ (P ∨ ¬Q)) is PR + ¬QR + PQ is equivalent to:

Option 1: ((R ∨ ¬Q) ∧ (P ∨ ¬Q) ∧ (R ∨ P)) is (R + ¬Q)(P + ¬Q)(R + P))

           i.e. = RP + R¬Q +P¬Q not equivalent to  PR + ¬QR + PQ.

Option 2: ((R ∨ Q) ∧ (P ∨ ¬Q) ∧ (R ∨ P)) is (R + Q)(P + ¬Q)(P + R)

           i.e. = PR + ¬QR + PQ is exactly same.

Option 3: ((R ∨ Q) ∧ (P ∨ ¬Q) ∧ (R ∨ ¬P)) is (R + Q)(P + ¬Q)(R + ¬P)

           i.e. = PR + ¬QR + R(P ↔ Q) not equivalent to  PR + ¬QR + PQ.

Option 4: ((R ∨ Q) ∧ (P ∨ ¬Q) ∧ ( ¬R ∨ P)) is (R + Q)(P + ¬Q)(¬R + P)

           i.e. = PR + PQ + P(Q → R)  not equivalent to  PR + ¬QR + PQ.

64. The Boolean expression [~(~p ∧ q) ∧ ~( ~p ∧ ~q)] ∨ (p ∧ r)] is equal to the Boolean function: [UGC NET CS 2016 Aug – II]

A. q

B. p ∧ r

C. p ∨ q

D. p

Answer: D

Explanation: We have Boolean expression: [~(~p ∧ q) ∧ ~( ~p ∧ ~q)] ∨ (p ∧ r)] = [(p ∨ ~q) ∧ (p ∨ q ) ∨ (p ∧ r)] = [p ∨ (p ∧ q) ∨ (p ∧ ~q) ∨(p ∧ r)] = p[1 ∨ q ∨ ~q ∨ r] = p So, option (D) is correct.

65. Let us assume that you construct ordered the tree to represent the compound proposition (~ (p ∧ q)) ↔ (~ p ∨ ~ q). Then, the prefix and postfix expressions determined using this ordered tree are given as ____ and _____, respectively. [UGC NET CS 2016 Aug – II]

A. ↔~∧pq∨ ~ ~ pq, pq∧~p~q~∨↔

B. ↔~∧pq∨ ~ p~q, pq∧~p~q~∨↔

C. ↔~∧pq∨ ~ ~ pq, pq∧~p~~q∨↔

D. ↔~∧pq∨ ~ p~ q, pq∧~p~ ~q∨↔

Answer: B

Explanation: We have compound proposition (~ (p ∧ q)) ↔ (~ p ∨ ~ q): Now we will construct ordered tree: We are asked to determine pre-order (i.e. parent-node left-node right-node), we will drive it from ordered tree i.e. ↔ ~ ∧ p q ∨ ~ p ~q And post-order(i.e. left-node right-node parent-node) from the ordered tree it is p q ∧ ~ p ~ q ~ ∨ ↔. So, option (B) is correct.

66. Let A and B set in a finite universal set U. Given the following: |A ⊕ B|, |A - B|, |A ∪ B| and |A| + |B| Which is in order of increasing size? [UGC NET CS 2016 Aug – II]

A. |A – B| < |A ⊕ B| < |A| + |B| < |A ∪ B|

B. |A ⊕ B| < |A – B| < |A ∪ B| < |A| + |B|

C. |A ⊕ B| < |A| + |B| < |A – B| < |A ∪ B|

D. |A – B| < |A ⊕ B| < |A ∪ B| < |A| + |B|

Answer: D

Explanation: |A – B| = |A| - |A ∩ B|

|A ⊕ B| = |A| + |B| - 2|A ∩ B|

|A ∪ B| = |A| + |B| - |A ∩ B|

Therefore,

|A – B| < |A ⊕ B| < |A ∪ B| < |A| + |B|

So, option (D) is correct

67. Let ν(x) mean x is a vegetarian, m(y) for y is meat, and e(x, y) for x eats y. Based on these, consider the following sentences: I. ∀x ν(x ) ⇔ (∀y e(x, y) ⇒ ¬m(y)) II. ∀xν(x) ⇔ (¬(∃y m(y) ∧e(x, y))) III. ∀x (∃ym(y) ∧e(x, y)) ⇔ ¬ν(x) One can determine that: [UGC NET CS 2016 Aug - III]

A. Only I and II are equivalent sentences.

B. Only II and III are equivalent sentences.

C. Only I and III are equivalent sentences.

D. I, II, and III are equivalent sentences.

Answer: D

Explanation: I. If x is vegetarian, then all the food items he eats must not include a meat item

II. If x is vegetarian, then there should not be at least one mean item that x eats

III. If there exists one meat item that x eats, then x is not a vegetarian

All these sentences are equivalent. Hence, option D is correct.

68. Consider the following logical inferences : I1: If school will not open if it is Sunday. The school was open. Inference: It was not Sunday. I2: If it is Sunday, then the school will not open. It was not Sunday. Inference: The school was open. Which of the following is correct? [UGC NET CS 2016 Aug - III]

Answer: B

Explanation: p: it is Sunday q: the school will open

So if it is Sunday, then the school will not open represented as:

 p->~q so that it can imply q->~p (by contrapositive), so the first inference is correct for second.

If it is Sunday, then the school will not open represented as p->~q 

given ~p, so it can not imply ~p->q  (inverse implication) unless its converse(~q->p) is true, which is not true here.

Hence, option (B) is correct.

Note that only contrapositive holds true in all cases.

69. The negation of the following statement is? [UGC NET CS 2016 July – III]

“Either – 2 ≤ x ≤ – 1 or 1 ≤ x ≤2”.  

Answer: A

Explanation: “Either -2 ≤ x ≤ -1 or 1 ≤ x ≤ 2”. that is either x ≥ -2 or x ≤ -1 or 1 ≤ x or x ≤ 2”. To find negation of the statement: Negation of x ≥ -2 is x < 2, Negation of 1 ≤ x is x < 1, Negation of x ≤ -1 is x > -1, Negation of x ≤ 2 is x > 2. i.e. x < – 2 or 2 < x or – 1 < x < 1. Hence, option (A) is correct.

70. Which of the below are not valid arguments? [UGC NET CS 2015 Dec - II]

Answer: B

Explanation: Arguments (a) and (b) are not valid arguments.

If n is a real number, n>1, then n2>1. Suppose that n2>1, then n>1. This is a valid argument.

So, option (B) is correct.

71. Match the following terms: [UGC NET CS 2015 Dec - II]

  1. (1)
  2. (2)
  3. (3)
  4.  (4)

Answer: A

Explanation: The vacuous proof is a proof in which the implication p → q is true because p is false.

  • In trivial proof, the implication p → q is true based on the fact that q is true.
  • In Direct proof, the implication p → q is true proceeds by showing that q must be true when p is true.
  • In indirect proof, the implication p → q is true proceeds by showing that p must be false when q is false.

Hence, option (A) is correct.

72. Consider the following compound propositions as: (a)p ∨ ~(p ∧ q) (b)(p ∧ ~q) ∨ ~(p ∧ q) (c)p ∧ (q ∨ r) Which of the propositions are tautologies? [UGC NET CS 2015 Dec - II]

A. (a) and (c)

B. (b) and (c)

C. (a) and (b)

D. only (a)

Answer: D

Explanation: 

  • p ∨ ~(p ∧ q) = p + (pq)` = p + p` + q` = 1 + q` = 1, is a tautology.
  • (p ∧ ~q) ∨ ~(p ∧ q) = pq` + (pq)` = pq` + p` + q` = p` + q`, is not a tautology.
  • p ∧ (q ∨ r) = pq + pr, is NOT a tautology.

So, option (D) is correct.

73.

 

Answer: A

Explanation: "If my computations are valid and I pay the electric bill, I will run out of money.": if (c Λ b)→r "If I don't pay the electric bill, we will turn the power off. Hence, if I don't run out of money and the power is still on, my computations are incorrect.": (¬r Λ p)→¬c. So, option (A) is correct.

74. Match the following: [UGC NET CS 2015 Jun - II]

  1. (1)
  2. (2)
  3. (3)
  4. (4)

Answer: A

Explanation: 

  • (p → q) ⇔ (¬q → ¬p) is Contrapositive.
  • [(p ∧ q) → r] ⇔ [p → (q → r)] is exportation law.
  • (p → q) ⇔ [(p ∧ ¬q) → o] is Reductio ad absurdum.
  • (p ↔ q)⇔[(p → q)∧(q → p)] is Equivalence.

So, option (A) is correct.

75. Suppose a proposition is given as “ x ≥ 6, if x2 ≥ 5 and it's proof as If x ≥ 6, then x2 = x.x ≥ 6.6 = 36 ≥ 25. Which of the below are correct w.r.t. the given proposition and its proof? [UGC NET CS 2015 Jun - II]

Answer: C

Explanation: "x ≥ 6 if x2 ≥ 5 and it's proof as If x ≥ 6, then x2 = x.x ≥ 6.6 = 36 ≥ 25. It is clear from these statements that proof begins by assuming what is to be shown, and it is clear that the proof demonstrates the converse of what is to be proved; hence the proof is not correct. Statements (a) and (b) are correct, but (3) statement is not correct. Hence, option (C) is correct.

76. A horn clause is ___________. [UGC NET CS 2015 Dec – III]

Answer: D

Explanation: In logic programming, the horn clause has at most one positive literal. When there is exactly one positive literal, it is known as a definite clause, but it is called a goal clause when there is no positive literal. So, option (D) is correct.

77. In the Propositional Logic, given P and P → Q, we can infer __________. [UGC NET CS 2015 Dec – III]

A. ~ Q

B. Q

C. P ∧ Q

D. ~ P ∧ Q

Answer: B

Explanation: The rule of inference logic states that if a conditional statement (‘if p then q’) is valid, and the antecedent (p) holds (i.e., P and P → Q), then we may infer the consequent (q). Option Q is correct.

78. Which of the following is false for the PROLOG programming language? [UGC NET CS 2015 Jun - III]

Answer: B

Explanation: Regarding PROLOG, the statement "PROLOG is a strongly typed language" is False, among others. Hence, option (B) is correct.

79. Which one of the subsequent is true? [UGC NET CS 2015 Jun - III]

Answer: B

Explanation: The statement "The resolvent of two Horn clauses is a Horn clause." is true. So, option (B) is correct.

80. In the propositional logic, P ↔ Q is equivalent to which of the following (Where ~ denotes NOT): [UGC NET CS 2015 Jun - III]

A. ~( P ∨ Q ) ∧ ~ ( Q ∨ P )

B. ( ~P ∨ Q ) ∧ (~ Q ∨ P )

C. ( P ∨ Q ) ∧ ( Q ∨ P )

D. ~( P ∨ Q ) → ~ ( Q ∨ P )

Answer: B

Explanation: P ↔ Q = (P → Q) ∧ (Q → P) 

P ↔ Q = (~P ∨ Q) ∧ (~Q v P) 

So, option (B) is correct.

81. Determine the correct translation into the logical notation of the subsequent assertion.

Note: taller (x, y) is true if x is taller than y. [GATE-CS-2004]

Answer: D

Explanation: Many people get confused about when to use ∧ and when to use →. This question tests precisely that.

We use ∧ when we want to say that both predicates in this statement are always true, no matter the value of x.

We use → when we want to say that although there is no need for the left predicate always to be true, the right predicate must also be true whenever it becomes true.

D means there exist some boys x which taller than all girls y.

82. Equivalent logical expression for the WFF(Well Formed Formula), ~(∀x) F[x]. [UGC NET CS 2014 Dec - III]

A. ∀x (~F[x])

B. ~(∃x) F[x]

C. ∃x (~F[x])

D. ∀x F[x]

Answer: C

Explanation: ~ (∀x) F(x)

= (∃x)(~F(x))

So, option (C) is correct.

83. The resolvent to the set of the clauses (A ∨ B, ~A ∨ D, C ∨ ~B) is: [UGC NET CS 2014 Dec - III]

A. A ∨ B

B. C ∨ D

C. A ∨ C

D. A ∨ D

Answer: B

Explanation: C ∨ D

A∨B, ∼A∨D, C∨∼B

A and ∼A will cancel out, and so will B and ∼B.

Hence, option (B) is correct.

84. Consider the English sentence: “Agra and Gwalior are both in India.” A student has written a logical sentence for the above English sentence in First-Order Logic using the predicate In(x, y), which means x is in y, as follows: In(Agra, India) ∨ In(Gwalior, India). Which one of the subsequent is correct concerning the above logical sentence? [UGC NET CS 2018 July - II]

Answer: A

Explanation: In (Agra, India) means Agra is in India.

In (Gwalior, India) means Gwalior is in India.

In(Agra, India) ∨ In(Gwalior, India), here "∨" means "or". So the entire gives the meaning of Either Agra is in India or Gwalior is in India. Hence, the statement does not express the meaning of the English sentence, and option (A) is correct.

85. The equivalence of ¬∃x Q(x) is: [UGC NET CS 2018 July - II]

A. ∃x ¬Q(x)

B. ∀x ¬Q(x)

C. ¬∃x ¬Q(x)

D. ∀x Q(x)

Answer: B

Explanation: This is a simple property for negating Quantified,

¬∃x Q(x) = ∀x ¬Q(x) 

Hence, option (B) is correct.

86. Which of the following predicate formulae is NOT logically valid? Remember that W is a predicate formula without any free occurrence of x. [GATE CS 2020]

Answer: C

Explanation: ∀x (p(x) → W) ≡ ∀xp(x) → W is wrong. Since ∀x [p(x) → W]

≡ ∀x [¬p(x) ∨ W]

≡ ∀x (¬p(x) ∨ W

≡ ¬(∃x p(x)) ∨ W

≡ ∃x p(x) → W 

Hence, option (C) is correct.

87. Which one of the following is the main conjunctive normal form for [(pVq) ∧ ~p → ~q]? [NTA UGC NET 2019 June - II]

A. pV~q

B. pVq

C. ~pVq

D. ~pV~q

Answer: A

Explanation:

 

88. Match List-I with List-II [NTA UGC NET 2019 June - II]

Choose the correct option from the following:

A. a-ii, b-iii, c-i, d-iv

B. a-ii, b-i, c-iii, d-iv

C. a-iv, b-i, c-iii, d-ii

D. a-iv, b-iii, c-i, d-ii

Answer: B

Explanation:

 

Frequently Asked Questions

  1. What are propositional and first order logic?
    Propositional Logic converts a complete sentence into a symbol. It makes it logical, whereas, in First-Order Logic, a particular sentence will be made that involves relations, functions, and constants.
     
  2. What is the difference between propositional and first order logic?
    Propositional logic deals with simple declarative propositions, while first-order logic covers predicates and quantification. A proposition is a collection of declarative statements with either a truth value "true" or "false".
     
  3. What is propositional logic used for?
    We widely use propositional logic to make rules of inference and decision making. We can then use these rules of inferences to build arguments. It is hard to tell if a statement is valid when we have several premises. Thus, we use these inference rules to validate an argument and make a decision.
     
  4. What are the rules of propositional and first order logic?
    The propositions are equal or logically equal if they always have the same truth value. That is, p & q are logically equivalent if p is true whenever q is accurate, and vice-versa, and if p is false, whenever q is wrong, and vice-versa. If p & q are logically equivalent, we write p = q.
     
  5. Is the propositional and first order logic complete?
    Truth-functional propositional logic and first order logic is semantically complete but not syntactically complete. For example, the propositional logic statement consisting of a single propositional variable A is not a theorem nor its negation.

Conclusion

This article gives information about the propositional and first order logic and how this technique can improve an individual's skill to validate an argument and make a decision.

Also read Propositional and First Order Logic - Part 1Propositional and First Order Logic - Part 2.

Click here to read about Sequential circuits.

Recommended Readings:

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enroll in our courses and refer to the mock test and problems available. Take a look at the interview experiences and interview bundle for placement preparations.

Do upvote our blog to help other ninjas grow.

Happy Learning!

Live masterclass