chapter

Propositional Logic and Logical Equivalence Short Notes for GATE DA

Propositional Logic and Logical Equivalence short notes for GATE DA: 1 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice

propositional logic and logical equivalence short notes

Summary: Core Equivalences and Rules

.summary-card { padding: 1.5rem; background: var(--color-bg); color: var(--color-text); display: flex; flex-direction: column; gap: 1.5rem; } .summary-section { border-bottom: 1px solid var(--color-border); padding-bottom: 1rem; } .summary-section:last-child { border-bottom: none; } .section-title { color: var(--color-primary); font-weight: 700; margin-bottom: 0.8rem; font-size: 1.1rem; } .rule-list { list-style: none; padding: 0; margin: 0; } .rule-list li { margin-bottom: 0.5rem; padding-left: 1.2rem; position: relative; font-family: monospace; font-size: 0.95rem; } .rule-list li::before { content: '★'; position: absolute; left: 0; color: var(--color-primary); } .absolute-rule { background: color-mix(in srgb, #e74c3c 10%, transparent); padding: 0.5rem 0.8rem; border-radius: 4px; margin-bottom: 0.5rem; font-size: 0.9rem; } .absolute-rule strong { color: #e74c3c; } 1. The Golden Equivalences p \to q \equiv \neg p \lor q p \to q \equiv \neg q \to \neg p \neg (p \land q) \equiv \neg p \lor \neg q \neg (p \lor q) \equiv \neg p \land \neg q 2. Translation Dictionary " p only if q " ⟹ p \to q " p unless q " ⟹ \neg q \to p \equiv p \lor q " p is necessary for q " ⟹ q \to p " p is sufficient for q " ⟹ p \to q 3. The Absolute Rules p \to q is NOT equivalent to q \to p (Converse). p \to q is NOT equivalent to \neg p \to \neg q (Inverse). To prove equivalence, convert everything to \neg, \land, \lor form.

Try a question

Answer it here to see how it works. Nothing is recorded until you sign in.

Question 1

Level 1: Warm-up

Which one of the following propositions is logically equivalent to p \to \neg q by the law of material implication?

Question 2

Level 1: Warm-up

Which one of the following propositions is logically equivalent to \neg p \to q by the law of material implication?

Question 3

Level 1: Warm-up

When fully simplifying the proposition \neg (p \land \neg q) using fundamental logical equivalences, which of the following is an IMPOSSIBLE final result?

Question 4

Level 1: Warm-up

Consider the following statements about propositional variables x and y : S1: x \to y is logically equivalent to \neg x \to \neg y . S2: \neg (x \land y) is logically equivalent to \neg x \lor \neg y . S3: x \lor y is logically equivalent to \neg (\neg x \land \neg y) . Which of the following options is correct?

Question 5

Level 1: Warm-up

When fully simplifying the proposition \neg (p \to q) using fundamental logical equivalences, which of the following is an IMPOSSIBLE final result?

Question 6

Level 1: Warm-up

Consider the following statements about propositional variables p and q : S1: p \to q is logically equivalent to \neg p \lor q . S2: \neg (p \land q) is logically equivalent to \neg p \land \neg q . S3: p ⟺ q is logically equivalent to (p \to q) \land (q \to p) . Which of the following options is correct?

Question 7

Level 1: Warm-up

When fully simplifying the proposition \neg (p \to (q \to r)) using fundamental logical equivalences, which of the following is an IMPOSSIBLE final result?

Question 8

Level 1: Warm-up

Consider the following statements about propositional variables p and q : S1: p \to q is logically equivalent to \neg p \lor q . S2: \neg (p \land q) is logically equivalent to \neg p \land \neg q . S3: p ⟺ q is logically equivalent to (p \land q) \lor (\neg p \land \neg q) . Which of the following options is correct?

Question 9

Level 1: Warm-up

Which one of the following propositions is logically equivalent to p \to q by the law of material implication?

Question 10

Level 1: Warm-up

Consider the following assertion and reason about translating English to propositional logic. Assertion (A): The statement " p only if q " is logically equivalent to p \to q . Reason (R): In the phrase " p only if q ", the proposition p represents the necessary condition for q .

Free preview ends here

Login to view the complete short notes

Creating an account is free. You get the rest of this chapter, step-by-step solutions, and a study plan built around the topics you are actually weak at.

Why MastersUp

Personalised first. High quality throughout.

Most platforms hand everyone the same content. Here the content moves with your performance, topic by topic.

Built around you, not around a syllabus PDF

Every answer you give moves your topic-level intelligence rate. The next question, the next revision card and tomorrow's plan all change with it.

Revision that hits your weak spots

We only revise topics you have actually attempted and are still below the safe bar on — never the same chapter on repeat.

Questions calibrated to the real exam

Each question carries a measured toughness. You are served a rung above your current level, so practice keeps stretching you.

Notes written for recall, not for volume

Full lesson cards for first study, curated short-note cards for the last mile — with derivations, traps and exam patterns marked.

One place for everything

Notes, chapter practice, previous-year questions, test series and full-length papers — all feeding one picture of your preparation.

Honest progress

No vanity streaks. Progress here means chapters mastered and accuracy that held up on harder questions.

Unlock the whole course

Full notes and short notes, the complete question bank with worked solutions, mock tests, full-length papers, and an adaptive plan that rebuilds itself as you improve.

View all plans Start free

Propositional Logic and Logical Equivalence Short Notes for GATE DA

Propositional Logic and Logical Equivalence short notes for GATE DA: 1 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice questions.

Summary: Core Equivalences and Rules

1. The Golden Equivalences

$p \to q \equiv \neg p \lor q$
$p \to q \equiv \neg q \to \neg p$
$\neg (p \land q) \equiv \neg p \lor \neg q$
$\neg (p \lor q) \equiv \neg p \land \neg q$

2. Translation Dictionary

" $p$ only if $q$ " $⟹ p \to q$
" $p$ unless $q$ " $⟹ \neg q \to p \equiv p \lor q$
" $p$ is necessary for $q$ " $⟹ q \to p$
" $p$ is sufficient for $q$ " $⟹ p \to q$

3. The Absolute Rules

$p \to q$ is NOT equivalent to $q \to p$ (Converse).

$p \to q$ is NOT equivalent to $\neg p \to \neg q$ (Inverse).

To prove equivalence, convert everything to

\neg, \land, \lor

form.

Propositional Logic and Logical Equivalence: Solved Questions with Step-by-Step Explanations (10 Problems)

Question 1 · Analytical Aptitude MCQ

Which one of the following propositions is logically equivalent to $p \to \neg q$ by the law of material implication?

A.
$

eg p \lor

eg q$
B.
$

eg p \land q$
C.
$p \lor

eg q$
D.
$p \land

eg q$

Correct Answer:

Step-by-Step Solution

Key idea: The law of material implication states that $A \to B \equiv \neg A \lor B$ .

Step 1: Identify the components of the given conditional: $A = p$ and $B = \neg q$ .

Step 2: Apply the material implication rule: $p \to \neg q \equiv \neg p \lor \neg q$ .

Step 3: This matches Option A exactly.

Answer: Option A.

Question 2 · Analytical Aptitude MCQ

Which one of the following propositions is logically equivalent to $\neg p \to q$ by the law of material implication?

A.
$\neg p \lor q$
B.
$p \land q$
C.
$p \lor q$
D.
$\neg p \land \neg q$

Correct Answer:

Step-by-Step Solution

Key idea: The law of material implication states that $A \to B \equiv \neg A \lor B$ .

Step 1: Identify the components of the given conditional: $A = \neg p$ and $B = q$ .

Step 2: Apply the material implication rule: $\neg p \to q \equiv \neg (\neg p) \lor q$ .

Step 3: Simplify the double negation: $\neg (\neg p) \equiv p$ .

Step 4: The final expression is $p \lor q$ .

Answer: Option C.

Question 3 · Analytical Aptitude MCQ

When fully simplifying the proposition $\neg (p \land \neg q)$ using fundamental logical equivalences, which of the following is an IMPOSSIBLE final result?

A.
$\neg p \lor q$
B.
$p \to q$
C.
$q \lor \neg p$
D.
$\neg p \land q$

Correct Answer:

Step-by-Step Solution

Key idea: Apply De Morgan's Law and material implication to simplify $\neg (p \land \neg q)$ .

Step 1: Apply De Morgan's Law to the negation: $\neg (p \land \neg q) \equiv \neg p \lor \neg (\neg q) \equiv \neg p \lor q$ .

Step 2: Recognize that $\neg p \lor q$ is the material implication form of $p \to q$ .

Step 3: By commutativity of OR, $\neg p \lor q \equiv q \lor \neg p$ .

Step 4: The form $\neg p \land q$ is the negation of $p \to q$ (i.e., $\neg (p \to q)$ ), not an equivalent form. Thus, it is an impossible final result.

Answer: D

Question 4 · Analytical Aptitude MCQ

Consider the following statements about propositional variables $x$ and $y$ :

S1: $x \to y$ is logically equivalent to $\neg x \to \neg y$ .

S2: $\neg (x \land y)$ is logically equivalent to $\neg x \lor \neg y$ .

S3: $x \lor y$ is logically equivalent to $\neg (\neg x \land \neg y)$ .

Which of the following options is correct?

A.
Only S1 is TRUE
B.
Only S2 and S3 are TRUE
C.
Only S1 and S2 are TRUE
D.
All S1, S2, and S3 are TRUE

Correct Answer:

Step-by-Step Solution

Key idea: Use fundamental logical equivalences to verify each statement.

Step 1: S1 claims $x \to y \equiv \neg x \to \neg y$ . This is the inverse fallacy. The contrapositive is $\neg y \to \neg x$ , not the inverse. So S1 is FALSE.

Step 2: S2 claims $\neg (x \land y) \equiv \neg x \lor \neg y$ . This is exactly De Morgan's Law. So S2 is TRUE.

Step 3: S3 claims $x \lor y \equiv \neg (\neg x \land \neg y)$ . Applying De Morgan's to the right side gives $\neg (\neg x) \lor \neg (\neg y) \equiv x \lor y$ . So S3 is TRUE.

Step 4: Only S2 and S3 are TRUE.

Answer: B

Question 5 · Analytical Aptitude MCQ

When fully simplifying the proposition $\neg (p \to q)$ using fundamental logical equivalences, which of the following is an IMPOSSIBLE final result?

A.
$p \land \neg q$
B.
$\neg q \land p$
C.
$p \to q$
D.
$\neg (\neg p \lor q)$

Correct Answer:

Step-by-Step Solution

Key idea: Apply material implication and De Morgan's Law to simplify $\neg (p \to q)$ .

Step 1: Convert the conditional to material implication: $p \to q \equiv \neg p \lor q$ . Thus, $\neg (p \to q) \equiv \neg (\neg p \lor q)$ . This matches option (D).

Step 2: Apply De Morgan's Law: $\neg (\neg p \lor q) \equiv \neg (\neg p) \land \neg q \equiv p \land \neg q$ . This matches option (A).

Step 3: By commutativity of AND, $p \land \neg q \equiv \neg q \land p$ . This matches option (B).

Step 4: The form $p \to q$ is equivalent to $\neg p \lor q$ , which is the exact opposite of the simplified expression. Thus, it is an impossible final result.

Answer: C

Question 6 · Analytical Aptitude MCQ

Consider the following statements about propositional variables $p$ and $q$ :

S1: $p \to q$ is logically equivalent to $\neg p \lor q$ .

S2: $\neg (p \land q)$ is logically equivalent to $\neg p \land \neg q$ .

S3: $p ⟺ q$ is logically equivalent to $(p \to q) \land (q \to p)$ .

Which of the following options is correct?

A.
Only S1 and S2 are TRUE
B.
Only S1 and S3 are TRUE
C.
Only S2 and S3 are TRUE
D.
All S1, S2, and S3 are TRUE

Correct Answer:

Step-by-Step Solution

Key idea: Use fundamental logical equivalences to verify each statement.

Step 1: S1 claims $p \to q \equiv \neg p \lor q$ . This is the exact definition of material implication. So S1 is TRUE.

Step 2: S2 claims $\neg (p \land q) \equiv \neg p \land \neg q$ . This violates De Morgan's Law, which states $\neg (p \land q) \equiv \neg p \lor \neg q$ . So S2 is FALSE.

Step 3: S3 claims $p ⟺ q \equiv (p \to q) \land (q \to p)$ . This is the standard expansion of the biconditional. So S3 is TRUE.

Step 4: Only S1 and S3 are TRUE.

Answer: B

Question 7 · Analytical Aptitude MCQ

When fully simplifying the proposition $\neg (p \to (q \to r))$ using fundamental logical equivalences, which of the following is an IMPOSSIBLE final result?

A.
$p \land q \land \neg r$
B.
$\neg r \land q \land p$
C.
$p \land (q \land \neg r)$
D.
$p \to (q \land r)$

Correct Answer:

Step-by-Step Solution

Key idea: Apply material implication and De Morgan's Law to simplify the nested conditional.

Step 1: Convert the inner conditional: $q \to r \equiv \neg q \lor r$ .

Step 2: Convert the outer conditional: $p \to (\neg q \lor r) \equiv \neg p \lor (\neg q \lor r)$ .

Step 3: Apply negation to the entire expression: $\neg (\neg p \lor \neg q \lor r) \equiv p \land q \land \neg r$ . This matches option (A).

Step 4: By commutativity of AND, $p \land q \land \neg r \equiv \neg r \land q \land p$ . This matches option (B).

Step 5: By associativity of AND, $p \land q \land \neg r \equiv p \land (q \land \neg r)$ . This matches option (C).

Step 6: The form $p \to (q \land r)$ is equivalent to $\neg p \lor (q \land r)$ , which is not equivalent to $p \land q \land \neg r$ . Thus, it is an impossible final result.

Answer: D

Question 8 · Analytical Aptitude MCQ

Consider the following statements about propositional variables $p$ and $q$ :

S1: $p \to q$ is logically equivalent to $\neg p \lor q$ .

S2: $\neg (p \land q)$ is logically equivalent to $\neg p \land \neg q$ .

S3: $p ⟺ q$ is logically equivalent to $(p \land q) \lor (\neg p \land \neg q)$ .

Which of the following options is correct?

A.
Only S1 is TRUE
B.
Only S1 and S3 are TRUE
C.
Only S2 and S3 are TRUE
D.
All S1, S2, and S3 are TRUE

Correct Answer:

Step-by-Step Solution

Key idea: Use fundamental logical equivalences to verify each statement.

Step 1: S1 claims $p \to q \equiv \neg p \lor q$ . This is the exact definition of material implication. So S1 is TRUE.

Step 2: S2 claims $\neg (p \land q) \equiv \neg p \land \neg q$ . This violates De Morgan's Law, which states $\neg (p \land q) \equiv \neg p \lor \neg q$ . So S2 is FALSE.

Step 3: S3 claims $p ⟺ q \equiv (p \land q) \lor (\neg p \land \neg q)$ . This is the standard expansion of the biconditional (true when both are true, or both are false). So S3 is TRUE.

Step 4: Only S1 and S3 are TRUE.

Answer: B

Question 9 · Analytical Aptitude MCQ

Which one of the following propositions is logically equivalent to $p \to q$ by the law of material implication?

A.
p \lor \neg q
B.
\neg p \land q
C.
p \land \neg q
D.
\neg p \lor q

Correct Answer:

Step-by-Step Solution

Key idea: This is a direct equivalence recall question. The law of material implication provides a standard way to rewrite a conditional as a disjunction.

Step 1: Recall the material implication equivalence from the equivalence toolkit: $p \to q \equiv \neg p \lor q$ .

Step 2: The rule is: negate the premise, keep the conclusion, and change the connective from $\to$ to $\lor$ .

Step 3: Match with the options. Option D is $\neg p \lor q$ , which matches exactly.

Answer: Option D ( $\neg p \lor q$ ).

Common trap: Choosing $\neg p \lor q$ is correct, but choosing $p \lor \neg q$ (Option A) is the most common error. This mistake negates the conclusion instead of the premise. The rule is: negate the <b>premise</b> (the left side of $\to$ ), not the conclusion.

Verification: Build a quick truth table. When $p = T, q = F$ : $p \to q = F$ , and $\neg p \lor q = F \lor F = F$ . They match in all 4 rows.

Question 10 · Analytical Aptitude MCQ

Consider the following assertion and reason about translating English to propositional logic.

Assertion (A): The statement " $p$ only if $q$ " is logically equivalent to $p \to q$ .

Reason (R): In the phrase " $p$ only if $q$ ", the proposition $p$ represents the necessary condition for $q$ .

A.
Both A and R are true, and R is the correct explanation of A
B.
Both A and R are true, but R is NOT the correct explanation of A
C.
A is true, but R is false
D.
A is false, but R is true

Correct Answer:

Step-by-Step Solution

Key idea: "p only if q" translates to $p \to q$ , where q is the necessary condition.

Step 1: Evaluate Assertion (A): The phrase " $p$ only if $q$ " indeed translates to $p \to q$ . So A is TRUE.

Step 2: Evaluate Reason (R): In the conditional $p \to q$ , $p$ is the sufficient condition and $q$ is the necessary condition. R claims $p$ is the necessary condition for $q$ , which is FALSE.

Step 3: Since A is true and R is false, the correct option is C.

Answer: Option C.

More short notes in this unit

Logical Reasoning and Constraint Deduction Short Notes