Propositional and First-Order Logic

Overview

The study of logic provides the fundamental basis for all rigorous reasoning within computer science and mathematics. It is the language through which we can articulate and analyze computational processes, algorithm correctness, and system specifications with unambiguous precision. In this chapter, we shall explore the formal systems of logic that are indispensable for a computer science engineer. A mastery of these concepts is not merely an academic exercise; it is a prerequisite for a deep understanding of subjects ranging from digital circuit design and database theory to artificial intelligence and software verification.

We begin our investigation with Propositional Logic, a system that deals with simple, declarative statements that are either true or false. Here, we will introduce the core operators, or logical connectives, that allow us to construct complex expressions from elementary propositions. We will then proceed to establish the notion of logical equivalence, providing a formal toolkit for simplifying and manipulating these expressions. Subsequently, we will examine the rules of inference, which form the bedrock of deductive reasoning and allow us to construct valid arguments from a set of premises.

Finally, we will extend our framework to First-Order Logic, a significantly more expressive system that incorporates variables, predicates, and quantifiers. This extension allows us to reason about objects and their properties, a capability essential for modeling the complex domains encountered in advanced computer science. For the GATE examination, a strong command of both systems is critical, as questions frequently test the ability to translate natural language into formal expressions, determine the validity of arguments, and apply logical principles to solve algorithmic problems.

---

Chapter Contents

| # | Topic | What You'll Learn |
|---|-------|-------------------|
| 1 | Propositional Logic | Formalizing statements using propositions and connectives. |
| 2 | Logical Equivalences | Simplifying expressions using standard equivalence laws. |
| 3 | Rules of Inference | Deriving conclusions from a set of premises. |
| 4 | First-Order Logic | Extending logic with predicates and quantifiers. |

---

Learning Objectives

---

We now turn our attention to Propositional Logic...

Part 1: Propositional Logic

Introduction

Propositional Logic, also known as sentential calculus, serves as the bedrock of mathematical reasoning and digital computation. It is a formal system that deals with propositions—statements that can be definitively classified as either true or false—and the logical relationships that connect them. For a computer science engineer, a firm grasp of propositional logic is indispensable, as its principles directly underpin digital circuit design, algorithm analysis, artificial intelligence, database theory, and software verification.

In the context of the GATE examination, questions from this area test not only the mechanical application of rules but also the conceptual understanding of logical structures. We will systematically explore the fundamental components of this system, from basic propositions and logical connectives to the classification of complex logical statements. Our focus will remain steadfastly on the methods and principles most relevant to solving competitive examination problems, enabling the development of both accuracy and speed. Let us begin by defining the elementary unit of our study: the proposition.

---

Key Concepts

1. Logical Connectives

To construct more complex statements, known as compound propositions, we combine atomic propositions using logical connectives or operators. The truth value of a compound proposition is entirely determined by the truth values of its constituent parts and the connectives used.

a. Negation (NOT)

The negation of a proposition $p$, denoted by $\neg p$ (or sometimes $\sim p$), is the statement "it is not the case that $p$." It reverses the truth value of the original proposition.

| $p$ | $\neg p$ |
|:---:|:---:|
| $T$ | $F$ |
| $F$ | $T$ |

b. Conjunction (AND)

The conjunction of two propositions $p$ and $q$, denoted by $p \land q$, is true only when both $p$ and $q$ are true. It corresponds to the English word "and."

| $p$ | $q$ | $p \land q$ |
|:---:|:---:|:---:|
| $T$ | $T$ | $T$ |
| $T$ | $F$ | $F$ |
| $F$ | $T$ | $F$ |
| $F$ | $F$ | $F$ |

c. Disjunction (OR)

The disjunction of two propositions $p$ and $q$, denoted by $p \lor q$, is false only when both $p$ and $q$ are false. This is an inclusive OR, meaning it is true if at least one of the propositions is true.

| $p$ | $q$ | $p \lor q$ |
|:---:|:---:|:---:|
| $T$ | $T$ | $T$ |
| $T$ | $F$ | $T$ |
| $F$ | $T$ | $T$ |
| $F$ | $F$ | $F$ |

d. Implication (Conditional)

The implication $p \to q$ (read as "if $p$, then $q$") is a proposition that is false only in the case where the premise $p$ is true and the conclusion $q$ is false.

| $p$ | $q$ | $p \to q$ |
|:---:|:---:|:---:|
| $T$ | $T$ | $T$ |
| $T$ | $F$ | $F$ |
| $F$ | $T$ | $T$ |
| $F$ | $F$ | $T$ |

The cases where $p$ is false are noteworthy. When the premise is false, the implication is considered true regardless of the conclusion's truth value. This is known as vacuous truth.

e. Biconditional (If and Only If)

The biconditional statement $p \leftrightarrow q$ (read as "$p$ if and only if $q$") is true when $p$ and $q$ have the same truth value.

| $p$ | $q$ | $p \leftrightarrow q$ |
|:---:|:---:|:---:|
| $T$ | $T$ | $T$ |
| $T$ | $F$ | $F$ |
| $F$ | $T$ | $F$ |
| $F$ | $F$ | $T$ |

---

---

2. Tautology, Contradiction, and Contingency

We can classify compound propositions based on their truth values across all possible assignments to their variables.

Worked Example:

Problem: Determine if the proposition $S: (p \to q) \lor (q \to p)$ is a tautology, contradiction, or contingency.

Solution: We construct a truth table to analyze all possible truth value combinations for $p$ and $q$.

Step 1: List all possible truth values for $p$ and $q$.

| $p$ | $q$ |
|:---:|:---:|
| T | T |
| T | F |
| F | T |
| F | F |

Step 2: Evaluate the sub-expressions $p \to q$ and $q \to p$.

| $p$ | $q$ | $p \to q$ | $q \to p$ |
|:---:|:---:|:---:|:---:|
| T | T | T | T |
| T | F | F | T |
| F | T | T | F |
| F | F | T | T |

Step 3: Evaluate the final expression $(p \to q) \lor (q \to p)$.

| $p$ | $q$ | $p \to q$ | $q \to p$ | $(p \to q) \lor (q \to p)$ |
|:---:|:---:|:---:|:---:|:---:|
| T | T | T | T | T |
| T | F | F | T | T |
| F | T | T | F | T |
| F | F | T | T | T |

Result: Since the final column contains only $T$ values, the proposition is a tautology.

Answer: The proposition $S$ is a tautology.

---

3. Logical Equivalence

Two compound propositions, $P$ and $Q$, are said to be logically equivalent if $P \leftrightarrow Q$ is a tautology. We denote this by $P \equiv Q$. This concept is immensely powerful for simplifying complex expressions without resorting to truth tables.

Worked Example:

Problem: Show that $(\neg p \land (p \lor q)) \to q$ is a tautology using logical equivalences.

Solution:

Step 1: Let us begin by simplifying the antecedent, $(\neg p \land (p \lor q))$. We apply the distributive law.

Step 2: The term $(\neg p \land p)$ is a contradiction, which is always false ($F$).

Step 3: Using the identity law ($F \lor A \equiv A$), the antecedent simplifies to:

Step 4: Now, we substitute this simplified antecedent back into the original implication.

Step 5: We apply the implication equivalence law ($A \to B \equiv \neg A \lor B$).

Step 6: Apply De Morgan's Law to the negated term.

Step 7: Apply the double negation law.

Step 8: Apply the associative law.

Step 9: The term $(\neg q \lor q)$ is a tautology, which is always true ($T$).

Step 10: Finally, by the domination law, the expression simplifies to $T$.

Result: Since the expression simplifies to $T$, we have proven that it is a tautology.

---

Problem-Solving Strategies

For GATE, efficiency is paramount. While truth tables are fundamental, they are often too slow. Mastery of logical equivalences is the key to rapid and accurate problem-solving.

---

Common Mistakes

A clear understanding of common pitfalls can significantly improve accuracy in an exam setting.

---

---

Practice Questions

:::question type="MCQ" question="Let $p$ be 'The system is online' and $q$ be 'The network is congested'. The statement 'The system is online only if the network is not congested' can be logically represented as:" options=["$p \to \neg q$","$q \to p$","$\neg q \to p$","$p \land \neg q$"] answer="$p \to \neg q$" hint="Recall the translation for 'P only if Q'. 'The network is not congested' is the negation of $q$." solution="Step 1: Identify the propositions.
$p$: The system is online.
$q$: The network is congested.
$\neg q$: The network is not congested.

Step 2: Analyze the English statement. The phrase 'A only if B' is a standard form for an implication, which translates to $A \to B$.

Step 3: Apply the translation rule to the given statement.
Here, $A$ is 'The system is online' ($p$).
$B$ is 'the network is not congested' ($\neg q$).

Step 4: Construct the final logical expression.
Substituting $A$ with $p$ and $B$ with $\neg q$ into the form $A \to B$ gives us:

Result: The correct representation is $p \to \neg q$.
Answer: $\boxed{p \to \neg q}$"
:::

:::question type="NAT" question="Consider the propositional formula $\phi = (p \to q) \leftrightarrow (\neg q \to \neg p)$. For how many distinct assignments of truth values to the variables $p$ and $q$ does the formula $\phi$ evaluate to True?" answer="4" hint="This question asks to determine if the formula is a tautology. A tautology is true for all possible truth value assignments." solution="Step 1: The formula is $\phi = (p \to q) \leftrightarrow (\neg q \to \neg p)$. This compares an implication with its contrapositive.

Step 2: We know from the laws of logical equivalence that an implication is always logically equivalent to its contrapositive. That is, $p \to q \equiv \neg q \to \neg p$.

Step 3: Let $A = (p \to q)$ and $B = (\neg q \to \neg p)$. Since $A \equiv B$, the biconditional $A \leftrightarrow B$ will be true for all possible truth values of its constituent propositions. An expression of the form $X \leftrightarrow X$ is a tautology.

Step 4: The variables are $p$ and $q$. The total number of distinct truth value assignments for two variables is $2^2 = 4$. These assignments are (T, T), (T, F), (F, T), and (F, F).

Step 5: Since the formula is a tautology, it will be true for all 4 of these assignments.

Result: The formula evaluates to True for 4 distinct assignments.
Answer: $\boxed{4}$"
:::

:::question type="MSQ" question="Which of the following propositional formulae are tautologies? Let $T$ represent the logical constant True." options=["$(p \land q) \to p$","$(p \lor q) \to p$","$p \to (p \lor q)$","$p \to (p \land q)$"] answer="$(p \land q) \to p$,$p \to (p \lor q)$" hint="Use the implication equivalence $A \to B \equiv \neg A \lor B$ and simplify each option." solution="Let's analyze each option by converting the implication to its equivalent disjunctive form ($\neg A \lor B$) and simplifying.

Option A: $(p \land q) \to p$
Step 1: Apply implication equivalence.

Step 2: Apply De Morgan's Law.

Step 3: Apply associative and commutative laws.

Step 4: Simplify $\neg p \lor p \equiv T$.

Step 5: Apply domination law.

Result: This is a tautology. So, (A) is correct.

Option B: $(p \lor q) \to p$
Step 1: Apply implication equivalence.

Step 2: Apply De Morgan's Law.

Step 3: Apply distributive law.

Step 4: Simplify $\neg p \lor p \equiv T$.

Step 5: Apply identity law.

Result: This is not a tautology. It is false if $p$ is false and $q$ is true. So, (B) is incorrect.

Option C: $p \to (p \lor q)$
Step 1: Apply implication equivalence.

Step 2: Apply associative law.

Step 3: Simplify $\neg p \lor p \equiv T$.

Step 4: Apply domination law.

Result: This is a tautology. So, (C) is correct.

Option D: $p \to (p \land q)$
Step 1: Apply implication equivalence.

Step 2: Apply distributive law.

Step 3: Simplify $\neg p \lor p \equiv T$.

Step 4: Apply identity law.

Result: This is not a tautology. It is false if $p$ is true and $q$ is false. So, (D) is incorrect.

The correct options are (A) and (C).
Answer: $\boxed{(p \land q) \to p, p \to (p \lor q)}$"
:::

---

Summary

---

What's Next?

---

---

Part 2: Logical Equivalences

Introduction

In the domain of mathematical logic, our objective is often not merely to construct propositions, but to reason about them, to simplify them, and to determine when two different-looking statements convey the same essential truth. The concept of logical equivalence provides the formal framework for this undertaking. Two compound propositions are said to be logically equivalent if they have identical truth values for all possible truth assignments of their constituent atomic propositions.

The study of logical equivalences is fundamental to computer science, forming the bedrock for circuit design in digital logic, query optimization in databases, and program verification in software engineering. Mastery of these equivalences allows one to manipulate and simplify complex logical expressions with confidence and precision, a skill indispensable for rigorous analytical reasoning. In this section, we will explore the core definitions and the principal laws that govern these equivalences.

---

Key Concepts

Before delving into the laws of equivalence, we must first establish the classifications of compound propositions based on their truth values.

1. Tautology, Contradiction, and Contingency

The nature of a compound proposition can be determined by examining its truth table.

We observe that two propositions $P$ and $Q$ are equivalent, $P \equiv Q$, precisely when the proposition $P \leftrightarrow Q$ is a tautology. This is the foundational test for equivalence.

2. Standard Logical Equivalences

A set of fundamental equivalences, often called laws, provides the tools for the algebraic manipulation of logical propositions. These laws allow us to simplify complex statements without constructing full truth tables.

Worked Example:

Problem: Show that $\neg(p \lor (\neg p \land q))$ is logically equivalent to $\neg p \land \neg q$.

Solution:

We will start with the more complex expression and apply the laws of logical equivalence to simplify it.

Step 1: Apply De Morgan's Law to the outermost negation.

Step 2: Apply De Morgan's Law again to the second term.

Step 3: Apply the Double Negation Law to $\neg(\neg p)$.

Step 4: Apply the Distributive Law.

Step 5: Apply the Negation Law to $(\neg p \land p)$.

Step 6: Apply the Identity Law.

Result:
We have successfully transformed the left-hand side into the right-hand side using a sequence of logical equivalences.

---

Problem-Solving Strategies

While algebraic manipulation using the laws of equivalence is the primary method for simplification, it is not the only one. For smaller expressions or for verification, truth tables provide a mechanical, albeit sometimes tedious, alternative.

---

Common Mistakes

A frequent source of error in manipulating logical expressions is the misapplication of the distributive and De Morgan's laws.

---

---

Practice Questions

:::question type="MCQ" question="The proposition $(p \rightarrow q) \land (\neg p \rightarrow q)$ is logically equivalent to which of the following?" options=["$p$","$q$","$\neg p$","$\neg q$"] answer="$q$" hint="First, convert the implications to their disjunctive normal form using the equivalence $A \rightarrow B \equiv \neg A \lor B$. Then apply the distributive law." solution="
Step 1: Convert the implications to their equivalent OR form.

Step 2: Apply the Double Negation Law.

Step 3: Apply the Distributive Law (in reverse). Here, $q$ is common to both clauses.

Step 4: Apply the Negation Law.

Step 5: Apply the Identity Law.

Result: The expression simplifies to $q$.
Answer: $\boxed{q}$
"
:::

:::question type="MCQ" question="Which of the following propositions is a tautology?" options=["$(p \lor q) \rightarrow p$","$p \lor (q \rightarrow p)$","$(p \land q) \rightarrow p$","$p \land (p \rightarrow q)$"] answer="$(p \land q) \rightarrow p$" hint="A proposition of the form $A \rightarrow B$ is a tautology if whenever $A$ is true, $B$ must also be true. Consider the definition of the $\land$ operator." solution="
Let us analyze each option.

Option A: $(p \lor q) \rightarrow p$
If $p=F$ and $q=T$, then $p \lor q$ is $T$, but $p$ is $F$. So, $T \rightarrow F$ is $F$. Not a tautology.

Option B: $p \lor (q \rightarrow p)$
If $p=F$, the expression becomes $F \lor (q \rightarrow F)$. If $q=T$, this is $F \lor (T \rightarrow F) \equiv F \lor F \equiv F$. Not a tautology.

Option C: $(p \land q) \rightarrow p$
Let's convert to its equivalent form: $\neg(p \land q) \lor p$.
Applying De Morgan's Law: $(\neg p \lor \neg q) \lor p$.
Using Associative and Commutative Laws: $(\neg p \lor p) \lor \neg q$.
Using Negation Law: $T \lor \neg q$.
Using Domination Law: $T$.
Since the expression simplifies to $T$, it is a tautology. This is also known as the Simplification rule of inference. If $p \land q$ is true, then by definition, $p$ must be true.

Option D: $p \land (p \rightarrow q)$
This simplifies to $p \land (\neg p \lor q) \equiv (p \land \neg p) \lor (p \land q) \equiv F \lor (p \land q) \equiv p \land q$. This is a contingency, not a tautology.
Answer: $\boxed{(p \land q) \rightarrow p}$
"
:::

:::question type="MSQ" question="Which of the following pairs of propositions are logically equivalent? Let $T$ be a tautology and $F$ be a contradiction." options=["$p \rightarrow q$ and $\neg q \rightarrow \neg p$","$p \rightarrow (q \rightarrow r)$ and $(p \land q) \rightarrow r$","$p \leftrightarrow q$ and $(p \land q) \lor (\neg p \land \neg q)$","$\neg(p \rightarrow q)$ and $p \lor \neg q$"] answer="A,B,C" hint="For each pair $(X, Y)$, check if $X \equiv Y$ using either algebraic simplification or by comparing their truth tables. Remember the equivalence for implication: $A \rightarrow B \equiv \neg A \lor B$." solution="
Option A: $p \rightarrow q$ and $\neg q \rightarrow \neg p$
This is the law of contraposition. Let's prove it.
$p \rightarrow q \equiv \neg p \lor q$.
$\neg q \rightarrow \neg p \equiv \neg(\neg q) \lor (\neg p) \equiv q \lor \neg p \equiv \neg p \lor q$.
Since both simplify to the same expression, they are equivalent. So, A is correct.

Option B: $p \rightarrow (q \rightarrow r)$ and $(p \land q) \rightarrow r$
Let's simplify both.
$p \rightarrow (q \rightarrow r) \equiv p \rightarrow (\neg q \lor r) \equiv \neg p \lor (\neg q \lor r) \equiv \neg p \lor \neg q \lor r$.
$(p \land q) \rightarrow r \equiv \neg(p \land q) \lor r \equiv (\neg p \lor \neg q) \lor r \equiv \neg p \lor \neg q \lor r$.
Since both simplify to the same expression, they are equivalent. This is known as the Exportation Law. So, B is correct.

Option C: $p \leftrightarrow q$ and $(p \land q) \lor (\neg p \land \neg q)$
The biconditional $p \leftrightarrow q$ is true if and only if $p$ and $q$ have the same truth value.
The expression $(p \land q) \lor (\neg p \land \neg q)$ is true if either ($p$ is true and $q$ is true) or ($p$ is false and $q$ is false). This is precisely the condition for $p \leftrightarrow q$ being true. Thus, they are equivalent. So, C is correct.

Option D: $\neg(p \rightarrow q)$ and $p \lor \neg q$
Let's simplify $\neg(p \rightarrow q)$.
$\neg(p \rightarrow q) \equiv \neg(\neg p \lor q) \equiv \neg(\neg p) \land \neg q \equiv p \land \neg q$.
The expression $p \land \neg q$ is not equivalent to $p \lor \neg q$. So, D is incorrect.
Answer: $\boxed{A,B,C}$
"
:::

:::question type="MCQ" question="The absorption law in propositional logic states that:" options=["$p \lor (p \land q) \equiv p$","$p \land (q \lor q) \equiv p$","$p \lor (p \lor q) \equiv p$","$p \land (p \rightarrow q) \equiv p$"] answer="$p \lor (p \land q) \equiv p$" hint="Recall the two forms of the absorption law. One involves OR with AND, and the other involves AND with OR." solution="
The absorption laws are:

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

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

Option A directly matches the first form of the absorption law. The other options are incorrect applications of logical laws.
Answer: $\boxed{p \lor (p \land q) \equiv p}$
"
:::

---

Summary

---

What's Next?

---

---

Part 3: Rules of Inference

Introduction

In the study of logic, our objective extends beyond merely assigning truth values to propositions. We are fundamentally concerned with the structure of arguments and the process of reasoning from a set of established truths, or premises, to a new truth, the conclusion. An argument's validity is not determined by the actual truth of its premises in the real world, but by its logical form. A valid argument guarantees that if its premises are true, its conclusion must necessarily be true.

Rules of inference are the foundational templates or schemata for constructing valid arguments. They provide the syntactical transformations that allow us to deduce conclusions from premises with logical certainty. Mastering these rules is indispensable for constructing formal proofs, a cornerstone of both mathematics and theoretical computer science. Whether we are proving the correctness of an algorithm, verifying a property of a data structure, or establishing a theorem in discrete mathematics, the underlying framework is invariably built upon these principles of logical deduction.

---

Key Concepts for Propositional Logic

We begin our exploration with rules of inference that operate on simple or compound propositions. These rules form the bedrock of logical deduction and are frequently combined to build more complex proofs.

1. Modus Ponens (Law of Detachment)

Modus Ponens, or "the way that affirms," is perhaps the most intuitive rule of inference. It states that if we have an implication and we know its antecedent (the 'if' part) is true, we can validly conclude that its consequent (the 'then' part) is also true.

Worked Example:

Problem: Given the premises:

If it is raining, the ground is wet.

It is raining.

What can be concluded?

Solution:

Step 1: Translate the premises into propositional logic.
Let $p$ be "It is raining" and $q$ be "The ground is wet".
The premises are:

$p \Rightarrow q$

$p$

Step 2: Apply the Modus Ponens rule.
The structure of the premises, $(p \Rightarrow q)$ and $p$, directly matches the template for Modus Ponens.

Step 3: Derive the conclusion.
According to Modus Ponens, from $p \Rightarrow q$ and $p$, we can infer $q$.

Answer: We can conclude that "The ground is wet" ($q$).

2. Modus Tollens (Law of Contraposition)

Modus Tollens, or "the way that denies," works in the opposite direction of Modus Ponens. If we have an implication and we know its consequent is false, we can validly conclude that its antecedent must also be false. This is based on the logical equivalence between an implication and its contrapositive ($p \Rightarrow q \equiv \neg q \Rightarrow \neg p$).

Worked Example:

Problem: Given the premises:

If a program is correct, it does not produce an error on test case A.

The program produced an error on test case A.

What is the logical conclusion?

Solution:

Step 1: Define the propositions.
Let $p$ be "The program is correct".
Let $q$ be "It does not produce an error on test case A".
The premises are:

$p \Rightarrow q$

$\neg q$ (The program did produce an error)

Step 2: Identify the applicable rule of inference.
The premises $p \Rightarrow q$ and $\neg q$ match the structure required for Modus Tollens.

Step 3: Conclude based on the rule.
Modus Tollens allows us to infer $\neg p$ from the given premises.

Answer: We can conclude that "The program is not correct" ($\neg p$).

3. Hypothetical Syllogism

This rule describes a chain of reasoning. If one event implies a second, and that second event implies a third, then the first event must imply the third. It allows us to combine conditional statements transitively.

4. Other Fundamental Rules

While Modus Ponens and Modus Tollens are central, several other rules are essential for constructing proofs.

| Rule Name | Tautology Form | Symbolic Form | Description |
| --------------------- | ------------------------------------------------------ | ----------------------------------- | ------------------------------------------------------------------------- |
| Disjunctive Syllogism | $((p \lor q) \land \neg p) \Rightarrow q$ | $p \lor q, \neg p \vdash q$ | If a disjunction is true and one disjunct is false, the other must be true. |
| Addition | $p \Rightarrow (p \lor q)$ | $p \vdash p \lor q$ | If a proposition is true, we can form a disjunction with any other proposition. |
| Simplification | $(p \land q) \Rightarrow p$ | $p \land q \vdash p$ | If a conjunction is true, then each of its components must be true. |
| Conjunction | $((p) \land (q)) \Rightarrow (p \land q)$ | $p, q \vdash p \land q$ | If two propositions are true separately, their conjunction is true. |
| Resolution | $((p \lor q) \land (\neg p \lor r)) \Rightarrow (q \lor r)$ | $p \lor q, \neg p \lor r \vdash q \lor r$ | A powerful rule that combines two disjunctions, eliminating a complementary pair. |

---

Rules of Inference for Quantified Statements

When our statements involve variables and quantifiers such as "for all" ($\forall$) and "there exists" ($\exists$), we require additional rules to handle them. These rules allow us to move between general statements about a domain and specific instances within that domain. Let the domain of discourse be $U$.

1. Universal Instantiation (UI)

This rule allows us to conclude that a property holds for a specific individual element of the domain if we know it holds for all elements of the domain.

• Formal Rule: From the premise $\forall x P(x)$, we can conclude $P(c)$ for any arbitrary element $c \in U$.
• Symbolic Form: $\forall x P(x) \vdash P(c)$

2. Universal Generalization (UG)

This rule is the reverse of UI, but it must be applied with great care. If we can show that a property $P(c)$ holds for an arbitrary element $c$ of the domain (meaning no specific properties of $c$ other than its membership in the domain were used), then we can generalize that the property holds for all elements.

• Formal Rule: From the premise $P(c)$ for an arbitrary $c \in U$, we can conclude $\forall x P(x)$.
• Symbolic Form: $P(c) \text{ for an arbitrary } c \vdash \forall x P(x)$

3. Existential Instantiation (EI)

If we know that there exists at least one element in the domain for which a property is true, we can give that element a name (a new constant symbol not used elsewhere in the proof) and proceed with our reasoning.

• Formal Rule: From the premise $\exists x P(x)$, we can conclude $P(c)$ for some specific, but potentially unknown, element $c \in U$.
• Symbolic Form: $\exists x P(x) \vdash P(c) \text{ for some element } c$

4. Existential Generalization (EG)

This rule is straightforward. If we can demonstrate that a property $P(c)$ is true for at least one specific element $c$ in the domain, we can generalize that there exists an element in the domain for which the property is true.

• Formal Rule: From the premise $P(c)$ for a particular element $c \in U$, we can conclude $\exists x P(x)$.
• Symbolic Form: $P(c) \vdash \exists x P(x)$

5. Mathematical Induction as a Rule of Inference

A particularly powerful rule of inference used for statements over the domain of natural numbers ($\mathbb{N} = \{0, 1, 2, \dots\}$) is the principle of mathematical induction. It allows us to prove that a property $P(n)$ holds for all natural numbers. It is a tautology derived from the axioms that define the natural numbers.

Worked Example:

Problem: Use mathematical induction to prove that for all non-negative integers $n$, the sum of the first $n$ integers is given by $\sum_{i=0}^{n} i = \frac{n(n+1)}{2}$.

Solution:

Let $P(n)$ be the proposition $\sum_{i=0}^{n} i = \frac{n(n+1)}{2}$.

Step 1: Establish the Base Case ($n=0$).
We must show that $P(0)$ is true.

Since both sides are equal, $P(0)$ is true.

Step 2: Formulate the Inductive Hypothesis.
Assume $P(k)$ is true for an arbitrary non-negative integer $k$.

Step 3: Prove the Inductive Step.
We must show that $P(k) \Rightarrow P(k+1)$ is true. That is, we must prove $\sum_{i=0}^{k+1} i = \frac{(k+1)((k+1)+1)}{2}$.

By the inductive hypothesis, we can substitute the formula for the sum up to $k$:

Now, we perform algebraic simplification:

This is precisely the formula for $P(k+1)$. Thus, we have shown that $P(k) \Rightarrow P(k+1)$.

Step 4: Conclude by the Principle of Mathematical Induction.
Since we have established the base case $P(0)$ and the inductive step $\forall k [P(k) \Rightarrow P(k+1)]$, we can conclude that $P(n)$ is true for all non-negative integers $n$.

Answer: $\forall n \in \mathbb{N}, \sum_{i=0}^{n} i = \frac{n(n+1)}{2}$.

---

Problem-Solving Strategies

---

Common Mistakes

---

Practice Questions

:::question type="MCQ" question="Consider the following premises:

If the server is down, no user can log in.

If the network is congested, the server is down.

The network is congested.

Which of the following can be logically concluded?" options=["The server is not down.","All users can log in.","No user can log in.","The network is not congested."] answer="No user can log in." hint="Use Hypothetical Syllogism followed by Modus Ponens." solution="Step 1: Translate the premises into symbolic logic.
Let $p$: The network is congested.
Let $q$: The server is down.
Let $r$: No user can log in.

Premises:

$q \Rightarrow r$

$p \Rightarrow q$

$p$

Step 2: Apply Hypothetical Syllogism to premises 1 and 2.
From $p \Rightarrow q$ and $q \Rightarrow r$, we can conclude $p \Rightarrow r$.

Step 3: Apply Modus Ponens.
We now have the derived premise $p \Rightarrow r$ and the given premise $p$.
Using Modus Ponens, we can conclude $r$.

Result:
The conclusion is $r$, which translates to 'No user can log in'.
Answer: \boxed{\text{No user can log in.}}"
:::

:::question type="MSQ" question="Let the domain of discourse be all integers. Which of the following arguments are valid?
Let $P(x)$ be '$x$ is an even number' and $Q(x)$ be '$x$ is divisible by 2'." options=["Given $\forall x (P(x) \Rightarrow Q(x))$ and $P(3)$, we can conclude $Q(3)$.","Given $\forall x (P(x) \Leftrightarrow Q(x))$ and $\neg Q(7)$, we can conclude $\neg P(7)$.","Given $\exists x P(x)$, we can conclude $P(4)$.","Given $P(8)$, we can conclude $\forall x P(x)$."] answer="Given $\forall x (P(x) \Leftrightarrow Q(x))$ and $\neg Q(7)$, we can conclude $\neg P(7)$." hint="Analyze each option using the rules for quantified statements. Pay close attention to the difference between universal and existential quantifiers." solution="

• Option A: This is an application of Universal Instantiation to get $P(3) \Rightarrow Q(3)$, followed by Modus Ponens. However, the premise $P(3)$ ('3 is an even number') is false. While the logical form is valid, the argument is not sound because a premise is false. Thus, we cannot soundly conclude $Q(3)$.

• Option B: From $\forall x (P(x) \Leftrightarrow Q(x))$, we use Universal Instantiation to get $P(7) \Leftrightarrow Q(7)$. This is equivalent to $(P(7) \Rightarrow Q(7)) \land (Q(7) \Rightarrow P(7))$. Given $\neg Q(7)$, we apply Modus Tollens to $(P(7) \Rightarrow Q(7))$ and $\neg Q(7)$ to validly conclude $\neg P(7)$. This argument is valid.

• Option C: Given $\exists x P(x)$, we cannot conclude $P(4)$. Existential quantification only guarantees the existence of some $x$ for which $P(x)$ is true, not a specific one like $4$. This is an invalid deduction.

• Option D: Given $P(8)$, we cannot conclude $\forall x P(x)$. Proving a property for a single, specific instance ($P(8)$) is not sufficient to generalize it to all integers. This is an invalid deduction.

Therefore, only the argument in Option B is logically valid.
Answer: \boxed{\text{Given } \forall x (P(x) \Leftrightarrow Q(x)) \text{ and } \neg Q(7), \text{ we can conclude } \neg P(7).}"
:::

:::question type="MCQ" question="Let $P(x)$ be a predicate on the set of integers. Consider the statement: $(P(10) \land \forall k \ge 10 [P(k) \Rightarrow P(k+1)])$. What is the strongest valid conclusion?" options=["$\forall n \in \mathbb{Z}, P(n)$","$\forall n \ge 10, P(n)$","$\forall n \le 10, P(n)$","$P(n)$ is true for all even integers $n \ge 10$"] answer="$\forall n \ge 10, P(n)$" hint="This is a direct application of the principle of mathematical induction, but with a different starting point (base case)." solution="Step 1: Identify the components of the argument.
The given statement has the form of mathematical induction.

• Base Case: $P(10)$ is given as true. The induction starts at $n=10$.


• Inductive Step: $\forall k \ge 10 [P(k) \Rightarrow P(k+1)]$ is given. This means that for any integer $k$ from 10 onwards, if $P(k)$ is true, then $P(k+1)$ is also true.

Step 2: Apply the principle of induction.
Since the base case is true for $n=10$ and the inductive step guarantees that truth propagates from any $k \ge 10$ to $k+1$, we can conclude that the property $P(n)$ holds for all integers greater than or equal to 10.

Step 3: Evaluate the options.

• $\forall n \in \mathbb{Z}, P(n)$: This is incorrect. We have no information about integers less than 10.


• $\forall n \ge 10, P(n)$: This is the correct conclusion based on our analysis.


• $\forall n \le 10, P(n)$: This is incorrect. The implication goes from $k$ to $k+1$, not downwards.


• $P(n)$ is true for all even integers $n \ge 10$: This is a weaker conclusion than what can be drawn. The argument proves it for all integers $n \ge 10$, not just the even ones.

Result:
The strongest valid conclusion is $\forall n \ge 10, P(n)$.
Answer: \boxed{\forall n \ge 10, P(n)}"
:::

:::question type="NAT" question="Consider the following proof sequence:

$p \Rightarrow q$ (Premise)

$\neg r \Rightarrow \neg q$ (Premise)

$p$ (Premise)

$q$ (From 1, 3)

$q \Rightarrow r$ (From 2)

$r$ (From 4, 5)

A single rule of inference was used to derive each of lines 4, 5, and 6. The rule used to derive line 5 is the Law of Contraposition. How many of the three derivations (to get lines 4, 5, and 6) use Modus Ponens?" answer="2" hint="Identify the rule of inference used for each step. The Law of Contraposition states that an implication is equivalent to its contrapositive." solution="Step 1: Analyze the derivation of line 4.

• Premise 1: $p \Rightarrow q$


• Premise 3: $p$


• Conclusion: $q$

This is a direct application of Modus Ponens.

Step 2: Analyze the derivation of line 5.

• Premise 2: $\neg r \Rightarrow \neg q$


• Conclusion: $q \Rightarrow r$

This is an application of the Law of Contraposition, which states that $(A \Rightarrow B) \Leftrightarrow (\neg B \Rightarrow \neg A)$. This is an equivalence rule, not Modus Ponens.

Step 3: Analyze the derivation of line 6.

• Derived Premise 4: $q$


• Derived Premise 5: $q \Rightarrow r$


• Conclusion: $r$

This is another direct application of Modus Ponens.

Step 4: Count the number of times Modus Ponens was used.
Modus Ponens was used to derive line 4 and line 6. Therefore, it was used 2 times.

Result: 2
Answer: \boxed{2}"
:::

---

Summary

---

What's Next?

---

---

---

Part 4: First-Order Logic

Introduction

In our study of mathematical logic, we begin with propositional logic, a system that allows us to reason about the truth values of complete, declarative statements. While powerful, its expressive capacity is limited. It cannot, for instance, reason about the properties of objects or the relationships between them. Consider the statement, "All computer science students must study Discrete Mathematics." Propositional logic can only treat this as a single atomic proposition, say $P$, obscuring the internal structure involving "all students" and the property of "studying Discrete Mathematics."

To overcome this limitation, we turn our attention to First-Order Logic (FOL), also known as Predicate Logic. It extends propositional logic by introducing a richer vocabulary of predicates, variables, and quantifiers. This allows us to make general assertions about collections of objects and to formalize statements of much greater complexity. For the GATE examination, a firm grasp of First-Order Logic is indispensable, particularly for translating natural language statements into formal logical expressions, a skill frequently tested.

---

Key Concepts

1. Components of First-Order Logic

A well-formed formula (WFF) in First-Order Logic is constructed from several basic building blocks.

* Constants: These are symbols that represent specific objects or individuals in the domain of discourse. For example, `2`, `c`, `'GATE'` could be constants.
* Variables: These are symbols, such as $x, y, z$, that act as placeholders for objects. Variables do not refer to a specific object but range over the entire domain.
* Predicates: A predicate is a symbol that represents a property of an object or a relationship between objects. A predicate takes one or more arguments (variables or constants) and evaluates to either true or false.
* $P(x)$ is a unary predicate (denoting a property). Example: $IsEven(x)$ could mean "$x$ is an even number."
* $Q(x, y)$ is a binary predicate (denoting a relation). Example: $GreaterThan(x, y)$ could mean "$x$ is greater than $y$."
* Functions: A function symbol represents a mapping from one or more elements of the domain to a single element of the domain. For example, $plus(x, y)$ could represent the sum $x+y$. (Note: In many GATE problems, functions are implicitly part of the predicates).
* Logical Connectives: First-Order Logic uses the same connectives as propositional logic: $\land$ (conjunction), $\lor$ (disjunction), $\neg$ (negation), $\implies$ (implication), and $\iff$ (biconditional).
* Quantifiers: These are the defining features of FOL, allowing us to specify the scope of a predicate.

2. Quantifiers in Detail

Quantifiers bind variables, specifying how many individuals in the domain a formula applies to.

The Universal Quantifier ($\forall$)

The symbol $\forall$, read as "for all" or "for every," is the universal quantifier. The expression $\forall x P(x)$ asserts that the predicate $P(x)$ is true for every object $x$ in the domain of discourse.

Consider the statement: "Every student in the class passed the exam."
Let the domain be all students in the class.
Let $S(x)$ be the predicate "$x$ is a student in the class."
Let $P(x)$ be the predicate "$x$ passed the exam."

The formal representation is:

This reads: "For every $x$, if $x$ is a student in the class, then $x$ passed the exam."

The Existential Quantifier ($\exists$)

The symbol $\exists$, read as "there exists" or "for some" or "there is at least one," is the existential quantifier. The expression $\exists x P(x)$ asserts that there is at least one object $x$ in the domain of discourse for which the predicate $P(x)$ is true.

Consider the statement: "Some students are GATE toppers."
Let the domain be all people.
Let $S(x)$ be the predicate "$x$ is a student."
Let $T(x)$ be the predicate "$x$ is a GATE topper."

The formal representation is:

This reads: "There exists an $x$ such that $x$ is a student and $x$ is a GATE topper."

3. Free and Bound Variables

The scope of a quantifier is the part of the formula to which it applies. A variable is said to be bound if it falls within the scope of a corresponding quantifier. A variable that is not bound is free.

Consider the formula:

* In the subformula $\forall x (P(x) \land Q(y))$, the quantifier $\forall x$ binds the variable $x$ within the parentheses. The variable $y$ is free.
* In the overall formula, the $x$ in $R(x)$ is not within the scope of the $\forall x$ quantifier, so this occurrence of $x$ is free.
* Therefore, in the complete formula, $y$ is a free variable, and the second occurrence of $x$ is a free variable.

A formula with no free variables is called a sentence or a closed formula. Sentences have a definite truth value (true or false).

4. Expressing Uniqueness

A common task in translating statements to FOL is expressing quantity, particularly "exactly one." This requires a combination of existential and universal quantifiers. Let us build this concept systematically.

Let $P(x)$ be a property.

a) At least one $x$ has property $P$:
This is the standard existential quantification.

b) At most one $x$ has property $P$:
This means that if we find two individuals, say $x$ and $y$, that both have property $P$, then they must be the same individual.

c) Exactly one $x$ has property $P$:
This is the conjunction of "at least one" and "at most one." While we could combine the two formulas above, more compact and equivalent forms are used in practice.

Worked Example:

Problem: Translate the statement "Every computer has exactly one central processing unit (CPU)" into a first-order logic formula.
Use the predicates:
* $Computer(x)$: $x$ is a computer.
* $CPU(y)$: $y$ is a CPU.
* $Has(x, y)$: computer $x$ has CPU $y$.

Solution:

Step 1: Deconstruct the statement. The outer structure is "For every computer...". This immediately suggests a universal quantifier for computers.

Step 2: The inner part of the statement is "...has exactly one CPU." This requires expressing the uniqueness of the CPU for a given computer $x$. Let the property $P(y)$ be $Has(x, y) \land CPU(y)$. We need to state that for a given $x$, there is exactly one $y$ with this property.

Step 3: Apply one of the "exactly one" formula structures. Let's use Form 1: $\exists y (P(y) \land \forall z (P(z) \implies z=y))$.

Substituting $P(y)$ with $(Has(x, y) \land CPU(y))$ and using $z$ as the second variable for the CPU:

Step 4: Combine the outer and inner parts into the final formula.

Answer: The logical formula is $\forall x (Computer(x) \implies \exists y ((Has(x, y) \land CPU(y)) \land \forall z ((Has(x, z) \land CPU(z)) \implies z=y)))$. Assuming the domain for $y$ and $z$ is implicitly CPUs, this can be simplified, but the above is the most rigorous translation based on the given predicates.

---

Problem-Solving Strategies

Translating natural language into First-Order Logic can be challenging. A systematic approach is often effective.

---

Common Mistakes

---

Practice Questions

:::question type="MCQ" question="Which of the following is the correct translation of the statement 'Not all birds can fly'?" options=["$\forall x (Bird(x) \land \neg CanFly(x))$","$\neg \forall x (Bird(x) \implies \neg CanFly(x))$","$\exists x (Bird(x) \land \neg CanFly(x))$","$\forall x (Bird(x) \implies \neg CanFly(x))$"] answer="$\exists x (Bird(x) \land \neg CanFly(x))$" hint="The statement 'Not all P are Q' is equivalent to 'Some P are not Q'." solution="
Step 1: Analyze the initial statement: 'Not all birds can fly'. This is the negation of 'All birds can fly'.

Step 2: First, let's write the formula for 'All birds can fly'. Using predicates $Bird(x)$ and $CanFly(x)$, this is:

Step 3: Now, negate the formula from Step 2.

Step 4: Apply De Morgan's law for quantifiers, which states that $\neg (\forall x P(x)) \equiv \exists x (\neg P(x))$.

Step 5: Use the logical equivalence $\neg(A \implies B) \equiv A \land \neg B$.

Result: This formula reads "There exists an $x$ such that $x$ is a bird and $x$ cannot fly," which is the precise meaning of "Not all birds can fly" or "Some birds cannot fly." This matches the third option.
Answer: $\boxed{\exists x (Bird(x) \land \neg CanFly(x))}$
"
:::

:::question type="NAT" question="Consider the first-order logic formula $\phi = \forall x ((\exists y P(x, y, z)) \implies (\forall z Q(y, z)))$. What is the number of free variables in $\phi$?" answer="2" hint="A variable is free if it is not bound by any quantifier. Check the scope of each quantifier carefully." solution="
Step 1: Identify all variables in the formula. The variables are $x, y, z$.

Step 2: Identify the quantifiers and their scopes.

• The quantifier $\forall x$ has the scope $((\exists y P(x, y, z)) \implies (\forall z Q(y, z)))$. Any occurrence of $x$ within this scope is bound. The variable $x$ in $P(x, y, z)$ is therefore bound.

• The quantifier $\exists y$ has the scope $P(x, y, z)$. Any occurrence of $y$ within this scope is bound. The variable $y$ in $P(x, y, z)$ is therefore bound.

• The quantifier $\forall z$ has the scope $Q(y, z)$. Any occurrence of $z$ within this scope is bound. The variable $z$ in $Q(y, z)$ is therefore bound.

Step 3: Check each variable's status.

• $x$: Bound by $\forall x$.


• $y$: The $y$ in $P(x, y, z)$ is bound by $\exists y$. However, the $y$ in $Q(y, z)$ is outside the scope of $\exists y$. Thus, this occurrence of $y$ is free.


• $z$: The $z$ in $P(x, y, z)$ is not in the scope of any quantifier for $z$. Thus, this occurrence of $z$ is free. The $z$ in $Q(y, z)$ is bound by $\forall z$.

Step 4: Count the unique free variables. The variable $y$ has a free occurrence, and the variable $z$ has a free occurrence. Therefore, there are two free variables in the formula $\phi$.

Result: The number of free variables is 2.
Answer: $\boxed{2}$
"
:::

:::question type="MSQ" question="Which of the following formulae correctly represent the statement 'There are at least two distinct items that are faulty'? Use the predicate $Faulty(x)$ and $x \neq y$ for '$x$ and $y$ are not equal'." options=["$\exists x \exists y (Faulty(x) \land Faulty(y))$","$\exists x \exists y (x \neq y \land Faulty(x) \land Faulty(y))$","$\neg \forall x \forall y ( (Faulty(x) \land Faulty(y)) \implies x=y )$","$\exists x \exists y (x \neq y \implies (Faulty(x) \land Faulty(y)))$"] answer="B,C" hint="The core of the problem is to ensure the two items are 'distinct'. Think about what 'at most one' means and how its negation relates to 'at least two'." solution="
Let's analyze each option:

Option A: $\exists x \exists y (Faulty(x) \land Faulty(y))$
This states that there exists an $x$ that is faulty and there exists a $y$ that is faulty. However, it does not enforce that $x$ and $y$ must be different. If there were only one faulty item, say $a$, we could choose $x=a$ and $y=a$, making the formula true. So, this only guarantees at least one faulty item. It is incorrect.

Option B: $\exists x \exists y (x \neq y \land Faulty(x) \land Faulty(y))$
This states that there exist two individuals, $x$ and $y$, such that they are not equal, $x$ is faulty, and $y$ is faulty. This perfectly captures the meaning of "at least two distinct items that are faulty." This is correct.

Option C: $\neg \forall x \forall y ( (Faulty(x) \land Faulty(y)) \implies x=y )$
The inner formula, $\forall x \forall y ( (Faulty(x) \land Faulty(y)) \implies x=y )$, means "at most one item is faulty." By negating this entire statement, we are asserting that "it is not the case that at most one item is faulty," which is logically equivalent to "there are more than one (i.e., at least two) faulty items." This is correct.

Option D: $\exists x \exists y (x \neq y \implies (Faulty(x) \land Faulty(y)))$
This statement is logically weak. If we pick any two items $x$ and $y$ that are identical ($x=y$), the premise $x \neq y$ becomes false. A false premise makes the implication true. So, this formula is true in any domain with at least one object, regardless of whether anything is faulty. It is incorrect.

Therefore, options B and C are correct.
Answer: $\boxed{B, C}$
"
:::

:::question type="MCQ" question="Let $L(x,y)$ be the predicate '$x$ likes $y$'. Which formula represents the statement 'There is someone whom everyone likes'?" options=["$\forall x \exists y L(x,y)$","$\forall y \exists x L(x,y)$","$\exists x \forall y L(y,x)$","$\exists y \forall x L(x,y)$"] answer="$\exists y \forall x L(x,y)$" hint="The order of quantifiers is critical. Does the person who is liked depend on who is doing the liking, or is there one person liked by all?" solution="
Step 1: Deconstruct the sentence: "There is someone whom everyone likes."

Step 2: Identify the core quantifiers and structure. "There is someone" points to an existential quantifier ($\exists$). "everyone likes" points to a universal quantifier ($\forall$).

Step 3: Determine the order. The statement asserts the existence of a single person (let's call them $y$) who is liked by all people (let's call them $x$). The choice of $y$ is independent of $x$. This means the existential quantifier must have a wider scope than the universal one.

Step 4: Formulate the expression.

• "There is someone, $y$..." translates to $\exists y$.


• "...such that for everyone, $x$..." translates to $\forall x$.


• "...$x$ likes $y$." translates to $L(x,y)$.

Step 5: Combine the parts:

Step 6: Analyze the other options to confirm understanding.

• $\forall x \exists y L(x,y)$: "For every person $x$, there is some person $y$ that $x$ likes." This means "Everyone likes someone."


• $\forall y \exists x L(x,y)$: "For every person $y$, there is someone $x$ who likes them." This means "Everyone is liked by someone."


• $\exists x \forall y L(y,x)$: "There is a person $x$ such that for all $y$, $y$ likes $x$." This is equivalent to the correct answer, just with variables swapped.


• $\exists y \forall x L(x,y)$: "There is a person $y$ such that for all $x$, $x$ likes $y$." This is the direct translation.

Result: The formula $\exists y \forall x L(x,y)$ correctly states that there exists a specific individual $y$ such that for all individuals $x$, the relation $L(x,y)$ holds.
Answer: $\boxed{\exists y \forall x L(x,y)}$
"
:::

---

Summary

---

What's Next?

---

Chapter Summary

---

Chapter Review Questions

:::question type="MCQ" question="Consider the following first-order logic statement, where the domain is the set of all integers: $\forall x \exists y ((x > 0) \rightarrow (y < 0 \land xy = -10))$. Which of the following is the most accurate negation of this statement?" options=["$\exists x \forall y ((x \le 0) \lor (y \ge 0 \lor xy \ne -10))$","$\exists x \forall y ((x > 0) \land (y \ge 0 \lor xy \ne -10))$","$\forall x \exists y ((x > 0) \land (y \ge 0 \lor xy \ne -10))$","$\exists x \forall y ((x \le 0) \land (y \ge 0 \land xy \ne -10))$"] answer="B" hint="To negate the statement, first negate the quantifiers ($\forall \rightarrow \exists$, $\exists \rightarrow \forall$). Then, negate the inner logical expression. Recall that the negation of an implication $P \rightarrow Q$ is $P \land \neg Q$." solution="Let the original statement be $S$.

To find the negation, $\neg S$, we proceed in steps.

Step 1: Negate the quantifiers.
The negation of $\forall x$ is $\exists x$.
The negation of $\exists y$ is $\forall y$.
So, the structure becomes:

Step 2: Negate the inner implication.
We use the rule $\neg(P \rightarrow Q) \equiv P \land \neg Q$.
Here, $P$ is $(x > 0)$ and $Q$ is $(y < 0 \land xy = -10)$.
Applying the rule, we get:

Step 3: Negate the conjunction inside.
We use De Morgan's Law: $\neg(A \land B) \equiv \neg A \lor \neg B$.
Here, $A$ is $(y < 0)$ and $B$ is $(xy = -10)$.
Applying the law, we get:

Step 4: Substitute back into the full expression.
Substituting the result from Step 3 into the expression from Step 2 gives the final negated statement:

This matches option B.
Answer: $\boxed{B}$
"
:::

:::question type="NAT" question="Consider the compound proposition $F = ((P \rightarrow Q) \land (Q \rightarrow R)) \rightarrow (P \rightarrow R)$. How many combinations of truth values for the propositional variables $P, Q,$ and $R$ result in the proposition $F$ being true?" answer="8" hint="Analyze the structure of the proposition. Does it correspond to a known rule of inference or a logical equivalence? Consider constructing a truth table or identifying if it's a specific type of proposition (tautology, contradiction, or contingency)." solution="The given proposition is:

This logical structure represents the Hypothetical Syllogism rule of inference. A rule of inference, when expressed as a conditional statement, is always a tautology. A tautology is a proposition that is true for all possible truth assignments of its variables.

Let's verify this using a truth table. There are 3 variables ($P, Q, R$), so there are $2^3 = 8$ possible combinations of truth values.

Let $A = P \rightarrow Q$, $B = Q \rightarrow R$, and $C = P \rightarrow R$.
The proposition is $(A \land B) \rightarrow C$.

| P | Q | R | $A = P \rightarrow Q$ | $B = Q \rightarrow R$ | $A \land B$ | $C = P \rightarrow R$ | $F = (A \land B) \rightarrow C$ |
|---|---|---|---|---|---|---|---|
| T | T | T | T | T | T | T | T |
| T | T | F | T | F | F | F | T |
| T | F | T | F | T | F | T | T |
| T | F | F | F | T | F | F | T |
| F | T | T | T | T | T | T | T |
| F | T | F | T | F | F | T | T |
| F | F | T | T | T | T | T | T |
| F | F | F | T | T | T | T | T |

As shown in the final column of the truth table, the proposition $F$ is true for all 8 combinations of truth values for $P, Q,$ and $R$.

Therefore, the number of combinations that result in $F$ being true is 8.
Answer: $\boxed{8}$
"
:::

:::question type="MSQ" question="Let the universe of discourse be the set of all people. Consider the following predicates:

• $S(x)$: '$x$ is a student.'


• $E(x)$: '$x$ is an engineer.'


• $L(x, y)$: '$x$ likes $y$.'

Which of the following English sentences are correct translations of the first-order logic formula $\forall x (S(x) \land \neg E(x) \rightarrow \exists y (E(y) \land L(x, y)))$?
" options=["Every person who is a student but not an engineer likes at least one engineer.","For any person $x$, if $x$ is a student and not an engineer, then there exists some person $y$ who is an engineer and whom $x$ likes.","There is a student who is not an engineer and who likes all engineers.","All non-engineer students like some engineer."] answer="A,B,D" hint="Break down the formula piece by piece. $\forall x$ means 'For all x' or 'Every x'. The structure is $\forall x(P(x) \rightarrow Q(x))$, which translates to 'For every x, if P(x) is true, then Q(x) is true'. Analyze what $P(x)$ and $Q(x)$ represent in this context." solution="Let's analyze the given first-order logic formula:

The structure is a universally quantified implication: $\forall x (P(x) \rightarrow Q(x))$.

• The universal quantifier $\forall x$ means "For all people x" or "Every person x".


• The antecedent (the 'if' part) is $P(x) \equiv S(x) \land \neg E(x)$. This translates to "$x$ is a student AND $x$ is not an engineer".


• The consequent (the 'then' part) is $Q(x) \equiv \exists y (E(y) \land L(x, y))$. This translates to "There exists a person $y$ such that $y$ is an engineer AND $x$ likes $y$". In simpler terms, "$x$ likes at least one engineer".

Combining these pieces, the formula states: "For every person $x$, if $x$ is a student and not an engineer, then $x$ likes at least one engineer."

Now let's evaluate the given options:

• A: Every person who is a student but not an engineer likes at least one engineer. This is a direct and accurate translation of the formula. The phrase "student but not an engineer" corresponds to $S(x) \land \neg E(x)$, and "likes at least one engineer" corresponds to $\exists y (E(y) \land L(x, y))$. This is a correct translation.

• B: For any person $x$, if $x$ is a student and not an engineer, then there exists some person $y$ who is an engineer and whom $x$ likes. This is a more literal, step-by-step translation of the logical symbols into English. It perfectly matches the structure and meaning of the formula. This is a correct translation.

• C: There is a student who is not an engineer and who likes all engineers. This translates to $\exists x (S(x) \land \neg E(x) \land \forall y (E(y) \rightarrow L(x, y)))$. This formula is existentially quantified ($\exists x$) and states that the student likes all engineers ($\forall y$), which is fundamentally different from the original formula's universal quantification ($\forall x$) and liking some engineer ($\exists y$). This is an incorrect translation.

• D: All non-engineer students like some engineer. This is a concise and natural-sounding English sentence that captures the exact meaning of the formula. "Non-engineer students" corresponds to $S(x) \land \neg E(x)$, and "like some engineer" corresponds to $\exists y (E(y) \land L(x, y))$. The word "All" at the beginning captures the universal quantifier $\forall x$. This is a correct translation.

Therefore, options A, B, and D are correct. Answer: $\boxed{A, B, D}$ " :::

---

What's Next?