Predicate Logic

This chapter introduces predicate logic, a fundamental extension of propositional logic essential for formalizing statements with variables and quantifiers. Mastery of these concepts is crucial for advanced topics in discrete mathematics, artificial intelligence, and formal verification, and frequently tested in CMI examinations.

---

Chapter Contents

|

| Topic |

|---|-------| | 1 | Predicates and Quantifiers | | 2 | Negation of Quantified Statements |

---

We begin with Predicates and Quantifiers.

Part 1: Predicates and Quantifiers

Predicate logic extends propositional logic by allowing us to represent properties of individuals and relationships between them, enabling a more granular analysis of statements relevant to computer science and mathematics. This unit provides the foundational concepts for constructing and interpreting quantified statements.

---

Core Concepts

1. Predicates (Atomic Formulas)

A predicate is a property or relation involving variables that becomes a proposition (true or false) when specific elements are assigned to these variables or when the variables are quantified.

Worked Example:
Let $P(x)$ be the predicate "$x$ is an even number" and $Q(x,y)$ be the predicate "$x$ is greater than $y$". We want to express specific propositions using these predicates.

Step 1: Express "5 is an even number".

> $P(5)$

Step 2: Express "10 is greater than 7".

> $Q(10, 7)$

Answer: $P(5)$ and $Q(10, 7)$

:::question type="MCQ" question="Given the predicate $L(x,y)$ meaning '$x$ loves $y$', and the domain of discourse being all people. Which of the following correctly represents the statement 'Alice loves Bob'?" options=["$L(\text{person}, \text{person})$","$L(\text{Alice}, \text{Bob})$","$L(x,y)$","$L(\text{Bob}, \text{Alice})$"] answer="$L(\text{Alice}, \text{Bob})$" hint="Identify the specific individuals and their roles in the relation." solution="The predicate $L(x,y)$ means '$x$ loves $y$'. To express 'Alice loves Bob', Alice takes the role of $x$ and Bob takes the role of $y$. Therefore, the correct representation is $L(\text{Alice}, \text{Bob})$."
:::

---

2. Universal Quantifier ($\forall$)

The universal quantifier, denoted by $\forall$, is used to express that a predicate holds for all elements in a given domain of discourse.

Worked Example:
Translate the English sentence "All students are intelligent" into predicate logic. Let the domain of discourse be all people. Let $S(x)$ be "$x$ is a student" and $I(x)$ be "$x$ is intelligent".

Step 1: Identify the quantifier and the main assertion.

The sentence states that if someone is a student, then they are intelligent. This applies to all people.

Step 2: Formulate the logical expression.

> $\forall x (S(x) \implies I(x))$

Answer: $\forall x (S(x) \implies I(x))$

:::question type="MCQ" question="Let $C(x)$ be '$x$ is a cat' and $M(x)$ be '$x$ is a mammal'. The domain of discourse is all animals. Which expression correctly translates 'All cats are mammals'?" options=["$\exists x (C(x) \land M(x))$","$\forall x (C(x) \land M(x))$","$\forall x (C(x) \implies M(x))$","$\exists x (C(x) \implies M(x))$"] answer="$\forall x (C(x) \implies M(x))$" hint="The statement 'All A are B' is generally translated as $\forall x (A(x) \implies B(x))$. Consider the implication." solution="The statement 'All cats are mammals' means that for any animal, if it is a cat, then it must be a mammal. This is a universal statement requiring an implication.
$\forall x (C(x) \implies M(x))$ correctly captures this meaning.
$\exists x (C(x) \land M(x))$ would mean 'Some cats are mammals'.
$\forall x (C(x) \land M(x))$ would mean 'Every animal is both a cat and a mammal', which is incorrect.
$\exists x (C(x) \implies M(x))$ would mean 'There exists an animal $x$ such that if $x$ is a cat, then $x$ is a mammal', which is trivially true (e.g., pick a non-cat)."
:::

---

3. Existential Quantifier ($\exists$)

The existential quantifier, denoted by $\exists$, is used to express that a predicate holds for at least one element in a given domain of discourse.

Worked Example:
Translate the English sentence "Some birds can fly" into predicate logic. Let the domain of discourse be all animals. Let $B(x)$ be "$x$ is a bird" and $F(x)$ be "$x$ can fly".

Step 1: Identify the quantifier and the relationship.

The sentence states that there is at least one animal that is a bird and can fly.

Step 2: Formulate the logical expression.

> $\exists x (B(x) \land F(x))$

Answer: $\exists x (B(x) \land F(x))$

:::question type="MCQ" question="Let $P(x)$ be '$x$ is a prime number' and $E(x)$ be '$x$ is an even number'. The domain of discourse is integers. Which expression correctly translates 'There is an even prime number'?" options=["$\forall x (P(x) \implies E(x))$","$\exists x (P(x) \land E(x))$","$\forall x (P(x) \land E(x))$","$\exists x (P(x) \implies E(x))$"] answer="$\exists x (P(x) \land E(x))$" hint="The statement implies the existence of a number that satisfies both properties simultaneously. Consider using conjunction." solution="The statement 'There is an even prime number' means that there exists at least one number that is both prime and even. This requires an existential quantifier and a conjunction.
$\exists x (P(x) \land E(x))$ correctly captures this meaning. (The number 2 is such a number).
$\forall x (P(x) \implies E(x))$ would mean 'All prime numbers are even', which is false.
$\forall x (P(x) \land E(x))$ would mean 'All numbers are prime and even', which is false.
$\exists x (P(x) \implies E(x))$ would mean 'There exists a number $x$ such that if $x$ is prime, then $x$ is even', which is trivially true (e.g., pick $x=4$, which is not prime, so $P(4)$ is false, making the implication true)."
:::

---

4. Free and Bound Variables

Variables in predicate logic can be either free or bound. A variable is bound if it falls within the scope of a quantifier; otherwise, it is free.

Worked Example:
Identify the free and bound variables in the formula $\forall x (P(x, y) \land \exists y Q(y, z))$.

Step 1: Identify the quantifiers and their scopes.

The first quantifier is $\forall x$. Its scope is $(P(x, y) \land \exists y Q(y, z))$.
The second quantifier is $\exists y$. Its scope is $Q(y, z)$.

Step 2: Determine which variables are bound by each quantifier.

• In $P(x, y)$, the variable $x$ is bound by $\forall x$. The variable $y$ is not bound by $\forall x$ (the $\exists y$ binds a different $y$ in a different part of the formula).
• In $\exists y Q(y, z)$, the variable $y$ in $Q(y, z)$ is bound by $\exists y$.
• The variable $z$ is not bound by any quantifier.

Step 3: List free and bound variables.

• Bound variables: $x$ (bound by $\forall x$), $y$ (bound by $\exists y$ within $Q(y,z)$).
• Free variables: $y$ (in $P(x,y)$), $z$.

Answer: Bound variables are $x$ and the $y$ in $Q(y,z)$. Free variables are the $y$ in $P(x,y)$ and $z$.

:::question type="MCQ" question="In the formula $\exists x (R(x, y) \lor \forall y S(y, z))$, which variables are free?" options=["$x, y, z$","$y, z$","$x, z$","$z$"] answer="$z$" hint="Trace the scope of each quantifier. A variable is free if it is not within the scope of any quantifier binding it." solution="Let's analyze the formula $\exists x (R(x, y) \lor \forall y S(y, z))$:

The quantifier $\exists x$ binds $x$ within the entire parenthesis $(R(x, y) \lor \forall y S(y, z))$. So, $x$ is a bound variable.

Inside the parenthesis, we have $R(x,y) \lor \forall y S(y,z)$.

In $R(x,y)$, $x$ is bound by $\exists x$. The variable $y$ in $R(x,y)$ is not bound by $\exists x$.

The quantifier $\forall y$ binds $y$ only within $S(y, z)$. So, the $y$ in $S(y,z)$ is bound by $\forall y$.

The variable $z$ is not within the scope of any quantifier that binds $z$.

Therefore, the variable $y$ in $R(x,y)$ is free, and $z$ is free. The variables $x$ (in $R(x,y)$) and $y$ (in $S(y,z)$) are bound. The question asks for free variables.

Wait, I made a mistake in the analysis for the $y$ in $R(x,y)$. The variable $y$ in $R(x,y)$ is not bound by any quantifier in this specific formula. The $\forall y$ only affects $S(y,z)$. Therefore, $y$ in $R(x,y)$ is free.

Corrected analysis:

• $\exists x$ binds $x$ in $R(x,y)$.


• $\forall y$ binds $y$ in $S(y,z)$.


• The $y$ in $R(x,y)$ is not bound by any quantifier.


• The $z$ in $S(y,z)$ is not bound by any quantifier.

So, the free variables are $y$ (from $R(x,y)$) and $z$.
Looking at the options, only '$y, z$' includes both.
Let's re-evaluate the solution based on the options. The options seem to imply a single variable, or a combination. The option '$y, z$' is available.

Let's re-check the question carefully: "which variables are free?"
In $\exists x (R(x, y) \lor \forall y S(y, z))$:

• $x$ in $R(x,y)$ is bound by $\exists x$.


• $y$ in $R(x,y)$ is not bound by any quantifier. It is free.


• $y$ in $S(y,z)$ is bound by $\forall y$.


• $z$ in $S(y,z)$ is not bound by any quantifier. It is free.

Thus, the free variables are $y$ and $z$.

The correct option is "$y, z$". I need to be careful with the solution explanation to reflect this accurately.

Let's refine the solution:
The formula is $\exists x (R(x, y) \lor \forall y S(y, z))$.

The quantifier $\exists x$ binds all occurrences of $x$ within its scope, which is $(R(x, y) \lor \forall y S(y, z))$. Thus, $x$ in $R(x, y)$ is bound.

The quantifier $\forall y$ binds all occurrences of $y$ within its scope, which is $S(y, z)$. Thus, $y$ in $S(y, z)$ is bound.

The variable $y$ in $R(x, y)$ is not within the scope of the $\forall y$ quantifier (which only applies to $S(y,z)$), and it is not bound by $\exists x$. Therefore, this occurrence of $y$ is free.

The variable $z$ in $S(y, z)$ is not bound by any quantifier. Therefore, $z$ is free.

The free variables in the formula are $y$ (from $R(x,y)$) and $z$.
"
The correct answer is "$y, z$". My reasoning was correct, just a momentary doubt.

"
Solution:
The formula is $\exists x (R(x, y) \lor \forall y S(y, z))$.

The quantifier $\exists x$ binds the variable $x$ within its scope, which is the entire expression $(R(x, y) \lor \forall y S(y, z))$. Therefore, the variable $x$ in $R(x, y)$ is bound.

The quantifier $\forall y$ binds the variable $y$ within its scope, which is $S(y, z)$. Therefore, the variable $y$ in $S(y, z)$ is bound.

The variable $y$ in $R(x, y)$ is not within the scope of the $\forall y$ quantifier (which only applies to $S(y,z)$), and it is not bound by $\exists x$. Therefore, this occurrence of $y$ is free.

The variable $z$ in $S(y, z)$ is not bound by any quantifier. Therefore, $z$ is free.

Thus, the free variables in the formula are $y$ and $z$.
"
This is good.

---

---

Part 2: Negation of Quantified Statements

This section covers the essential rules for negating statements involving universal ($\forall$) and existential ($\exists$) quantifiers, a fundamental skill in predicate logic for CMI examinations. We focus on direct application through worked examples.

---

Core Concepts

1. Negating Universal Statements

We define the negation of a universally quantified statement by transforming it into an existentially quantified statement where the predicate is negated.

Worked Example: Negate the statement: "All CMI students are proficient in discrete mathematics."

Step 1: Translate the statement into predicate logic.
Let $S$ be the domain of CMI students.
Let $P(x)$ be the predicate "$x$ is proficient in discrete mathematics."
The statement is $\forall x \in S, P(x)$.

Step 2: Apply the negation rule.
>

Step 3: Translate the negated statement back into natural language.
The negation is "There exists a CMI student $x$ such that $x$ is not proficient in discrete mathematics."
Answer: There exists a CMI student who is not proficient in discrete mathematics.

:::question type="MCQ" question="Which of the following is the correct negation of the statement: 'Every integer $n$ is such that $n^2 \ge n$'?" options=["There exists an integer $n$ such that $n^2 < n$.","Every integer $n$ is such that $n^2 < n$.","There exists an integer $n$ such that $n^2 \le n$.","Every integer $n$ is such that $n^2 \le n$. "] answer="There exists an integer $n$ such that $n^2 < n$." hint="Identify the quantifier and the predicate, then apply the negation rule." solution="Step 1: Identify the original statement's structure.
The statement is $\forall n \in \mathbb{Z}, (n^2 \ge n)$.
Here, $P(n)$ is the predicate $n^2 \ge n$.

Step 2: Apply the rule for negating a universal quantifier.

Step 3: Negate the predicate $P(n)$.
The negation of $n^2 \ge n$ is $n^2 < n$.

Step 4: Combine to form the negated statement.

This translates to: 'There exists an integer $n$ such that $n^2 < n$.'"
:::

---

2. Negating Existential Statements

We define the negation of an existentially quantified statement by transforming it into a universally quantified statement where the predicate is negated.

Worked Example: Negate the statement: "Some programming languages support multiple inheritance."

Step 1: Translate the statement into predicate logic.
Let $L$ be the domain of programming languages.
Let $P(x)$ be the predicate "$x$ supports multiple inheritance."
The statement is $\exists x \in L, P(x)$.

Step 2: Apply the negation rule.
>

Step 3: Translate the negated statement back into natural language.
The negation is "For all programming languages $x$, $x$ does not support multiple inheritance."
Answer: All programming languages do not support multiple inheritance (or, no programming language supports multiple inheritance).

:::question type="MCQ" question="What is the negation of the statement: 'There exists a real number $x$ such that $x^2 + 1 = 0$'?" options=["For all real numbers $x$, $x^2 + 1 \neq 0$.","For all real numbers $x$, $x^2 + 1 = 0$.","There exists a real number $x$ such that $x^2 + 1 \neq 0$.","There is no real number $x$ such that $x^2 + 1 \neq 0$. "] answer="For all real numbers $x$, $x^2 + 1 \neq 0$." hint="Recall the negation rules for existential quantifiers." solution="Step 1: The original statement is $\exists x \in \mathbb{R}, (x^2 + 1 = 0)$.
Let $P(x)$ be the predicate $x^2 + 1 = 0$.

Step 2: Apply the negation rule for existential quantifiers:

Step 3: Negate the predicate $P(x)$.
The negation of $x^2 + 1 = 0$ is $x^2 + 1 \neq 0$.

Step 4: Combine to form the negated statement.

This translates to: 'For all real numbers $x$, $x^2 + 1 \neq 0$.'"
:::

---

3. Negating Multiply Quantified Statements

We apply the negation rules sequentially from left to right, moving the negation symbol past each quantifier and negating the predicate at the end.

Worked Example 1: Negate the statement: "For every natural number $x$, there exists a natural number $y$ such that $y > x$." (Every natural number has a successor).

Step 1: Translate to predicate logic.
Let $P(x,y)$ be the predicate $y > x$.
The statement is $\forall x \in \mathbb{N}, \exists y \in \mathbb{N}, P(x,y)$.

Step 2: Apply the negation rule for the first quantifier ($\forall x$).
>

Step 3: Apply the negation rule for the second quantifier ($\exists y$).
>

Step 4: Negate the predicate $P(x,y)$.
The negation of $y > x$ is $y \le x$.

Step 5: Combine and translate back.
>

Answer: There exists a natural number $x$ such that for all natural numbers $y$, $y \le x$. (This statement claims there is a largest natural number, which is false but correctly formed).

Worked Example 2: Negate the statement: "There exists a real number $M$ such that for every real number $x$, $|x| \le M$." (The set of real numbers is bounded).

Step 1: Translate to predicate logic.
Let $P(M,x)$ be the predicate $|x| \le M$.
The statement is $\exists M \in \mathbb{R}, \forall x \in \mathbb{R}, P(M,x)$.

Step 2: Apply the negation rule for the first quantifier ($\exists M$).
>

Step 3: Apply the negation rule for the second quantifier ($\forall x$).
>

Step 4: Negate the predicate $P(M,x)$.
The negation of $|x| \le M$ is $|x| > M$.

Step 5: Combine and translate back.
>

Answer: For every real number $M$, there exists a real number $x$ such that $|x| > M$. (This statement claims that for any proposed bound, there's a real number larger than it, correctly reflecting that real numbers are unbounded).

:::question type="MCQ" question="Consider the statement: 'For every positive integer $a$, there exists a positive integer $b$ such that $a \cdot b = 1$.' Which of the following is its correct negation?" options=["There exists a positive integer $a$ such that for every positive integer $b$, $a \cdot b \neq 1$.","For every positive integer $a$, for every positive integer $b$, $a \cdot b \neq 1$.","There exists a positive integer $a$ such that there exists a positive integer $b$ such that $a \cdot b \neq 1$.","For every positive integer $a$, there exists a positive integer $b$ such that $a \cdot b = 1$."] answer="There exists a positive integer $a$ such that for every positive integer $b$, $a \cdot b \neq 1$." hint="Apply the negation rules for multiple quantifiers sequentially from left to right." solution="Step 1: Translate the original statement into predicate logic.
Let the domain be positive integers ($\mathbb{Z}^+$).
The statement is $\forall a \in \mathbb{Z}^+, \exists b \in \mathbb{Z}^+, (a \cdot b = 1)$.
Let $P(a,b)$ be the predicate $a \cdot b = 1$.

Step 2: Apply the negation operator to the entire statement.

Step 3: Move the negation past the first quantifier ($\forall a$).

Step 4: Move the negation past the second quantifier ($\exists b$).

Step 5: Negate the predicate $P(a,b)$.
The negation of $a \cdot b = 1$ is $a \cdot b \neq 1$.

Step 6: Combine and translate back into natural language.

This translates to: 'There exists a positive integer $a$ such that for every positive integer $b$, $a \cdot b \neq 1$.'"
:::

---

Advanced Applications

We can apply these rules to more complex logical expressions involving multiple predicates and propositional connectives within the quantified scope.

Worked Example: Negate the statement: "For every student $s$, if $s$ studies diligently, then $s$ will pass the exam."

Step 1: Translate to predicate logic.
Let $S$ be the domain of students.
Let $D(s)$ be "$s$ studies diligently."
Let $P(s)$ be "$s$ will pass the exam."
The statement is $\forall s \in S, (D(s) \to P(s))$.

Step 2: Apply the negation rule for the universal quantifier.
>

Step 3: Apply the negation rule for implication.
Recall that $\neg (A \to B) \equiv A \land \neg B$.
Here, $A = D(s)$ and $B = P(s)$.
>

Step 4: Translate back into natural language.
Answer: There exists a student $s$ such that $s$ studies diligently AND $s$ will not pass the exam.

:::question type="MSQ" question="Which of the following statements are logically equivalent to the negation of 'There exists a program $P$ such that for every input $I$, $P$ terminates for $I$ AND $P$ produces the correct output for $I$'?" options=["For every program $P$, there exists an input $I$ such that $P$ does not terminate for $I$ OR $P$ does not produce the correct output for $I$.","For every program $P$, there exists an input $I$ such that $P$ does not terminate for $I$ AND $P$ does not produce the correct output for $I$.","It is not the case that there exists a program $P$ such that for every input $I$, $P$ terminates for $I$ AND $P$ produces the correct output for $I$.","For every program $P$, there exists an input $I$ such that $P$ does not terminate for $I$ OR $P$ produces the correct output for $I$."] answer="For every program $P$, there exists an input $I$ such that $P$ does not terminate for $I$ OR $P$ does not produce the correct output for $I$.,It is not the case that there exists a program $P$ such that for every input $I$, $P$ terminates for $I$ AND $P$ produces the correct output for $I$." hint="Negate quantifiers and then apply De Morgan's laws for the conjunction." solution="Step 1: Translate the original statement into predicate logic.
Let $T(P,I)$ be '$P$ terminates for $I$'.
Let $C(P,I)$ be '$P$ produces the correct output for $I$'.
The statement is $\exists P \forall I (T(P,I) \land C(P,I))$.

Step 2: Apply the negation operator.

Step 3: Move the negation past the first quantifier ($\exists P$).

Step 4: Move the negation past the second quantifier ($\forall I$).

Step 5: Apply De Morgan's Law to negate the conjunction.
Recall that $\neg (A \land B) \equiv \neg A \lor \neg B$.
Here, $A = T(P,I)$ and $B = C(P,I)$.

Step 6: Translate back to natural language.
'For every program $P$, there exists an input $I$ such that $P$ does not terminate for $I$ OR $P$ does not produce the correct output for $I$.'

Option 1 matches this derived negation. Option 3 is simply the original statement prefixed with 'It is not the case that', which is always logically equivalent to its negation by definition."
:::

---

Problem-Solving Strategies

---

Common Mistakes

---

Practice Questions

:::question type="MCQ" question="Which of the following is the correct negation of the statement: 'Every person has a unique best friend'?" options=["There exists a person who does not have a unique best friend.","There exists a person who has multiple best friends.","Every person has at least two best friends.","No person has a best friend."] answer="There exists a person who does not have a unique best friend." hint="First, formalize the original statement carefully, then apply the negation rules." solution="Step 1: Formalize the original statement.
Let $P(x,y)$ mean '$y$ is $x$'s best friend'.
'Every person $x$ has a unique best friend $y$' can be written as:

Step 2: Apply negation.

Step 3: Move negation inwards.

Using $\neg (A \land B) \equiv \neg A \lor \neg B$:

Now negate $\neg (\forall z (P(x,z) \to z=y))$:

Using $\neg (A \to B) \equiv A \land \neg B$:

So, the full negation is:

Step 4: Interpret the negation.
This means 'There exists a person $x$ such that for all $y$, either $y$ is not $x$'s best friend, OR there exists another person $z$ who is also $x$'s best friend and $z$ is not $y$ (i.e., $x$ has multiple best friends), OR $x$ has no best friend at all (if no $y$ satisfies $P(x,y)$).
This simplifies to: 'There exists a person who does not have a unique best friend.' This covers cases where a person has no best friend or multiple best friends."
:::

:::question type="NAT" question="Let $P(x,y)$ be the predicate '$x$ divides $y$'. Consider the statement: 'For every integer $x$, there exists an integer $y$ such that $P(x,y)$ and $y \neq x$'. If the domain is all non-zero integers, how many quantifiers change their type (from universal to existential or vice versa) when this statement is negated?" answer="2" hint="Apply the negation rules systematically." solution="Step 1: Formalize the original statement.
Let the domain be non-zero integers ($\mathbb{Z}^*$).
The statement is $\forall x \in \mathbb{Z}^$, \exists y \in \mathbb{Z}^, (P(x,y) \land y \neq x).

Step 2: Apply negation to the statement.

Step 3: Move negation inwards.

Step 4: Quantifier changes:
The first quantifier changed from $\forall x$ to $\exists x$. (1 change)
The second quantifier changed from $\exists y$ to $\forall y$. (1 change)
Total changes = 2.

Step 5: Complete the negation (not required for the question, but useful for verification).
Negate the conjunction using De Morgan's:

In words: 'There exists a non-zero integer $x$ such that for every non-zero integer $y$, $x$ does not divide $y$ or $y = x$.'

The number of quantifiers that changed their type is 2."
:::

:::question type="MCQ" question="The negation of 'There is a computer science student who has taken every course in the curriculum' is:" options=["Every computer science student has not taken every course in the curriculum.","Every computer science student has taken at least one course not in the curriculum.","For every computer science student, there exists a course in the curriculum that they have not taken.","There is a computer science student who has not taken any course in the curriculum."] answer="For every computer science student, there exists a course in the curriculum that they have not taken." hint="Identify the quantifiers and predicates, then apply the negation rules sequentially." solution="Step 1: Formalize the original statement.
Let $S$ be the set of computer science students.
Let $C$ be the set of courses in the curriculum.
Let $T(s,c)$ be the predicate '$s$ has taken $c$'.
The statement is $\exists s \in S, \forall c \in C, T(s,c)$.

Step 2: Apply negation.

Step 3: Move negation past the first quantifier ($\exists s$).

Step 4: Move negation past the second quantifier ($\forall c$).

Step 5: Translate back into natural language.
'For every computer science student $s$, there exists a course $c$ in the curriculum that $s$ has not taken.'
This matches the third option."
:::

:::question type="MSQ" question="Let $R$ be a binary relation on a set $A$. Consider the statement: 'For every $x \in A$, there exists $y \in A$ such that $(x,y) \in R$ and $(y,x) \notin R$'. Which of the following are equivalent to the negation of this statement?" options=["There exists $x \in A$ such that for every $y \in A$, $(x,y) \notin R$ or $(y,x) \in R$.","There exists $x \in A$ such that for every $y \in A$, if $(x,y) \in R$ then $(y,x) \in R$.","For every $x \in A$, for every $y \in A$, $(x,y) \notin R$ or $(y,x) \in R$.","There exists $x \in A$ such that for every $y \in A$, it is not true that $((x,y) \in R \land (y,x) \notin R)$."] answer="There exists $x \in A$ such that for every $y \in A$, $(x,y) \notin R$ or $(y,x) \in R$.,There exists $x \in A$ such that for every $y \in A$, if $(x,y) \in R$ then $(y,x) \in R$.,There exists $x \in A$ such that for every $y \in A$, it is not true that $((x,y) \in R \land (y,x) \notin R)$." hint="Apply negation rules for quantifiers and then De Morgan's laws for the conjunction. Remember that $A \to B \equiv \neg A \lor B$." solution="Step 1: Formalize the original statement.
Let $P(x,y)$ be $(x,y) \in R$ and $Q(x,y)$ be $(y,x) \notin R$.
The statement is $\forall x \exists y (P(x,y) \land Q(x,y))$.

Step 2: Apply negation.

Step 3: Move negation inwards.

Step 4: Apply De Morgan's Law to negate the conjunction.

Step 5: Translate back and check options.
$\neg P(x,y)$ is $(x,y) \notin R$.
$\neg Q(x,y)$ is $(y,x) \in R$.
So the negation is: 'There exists $x \in A$ such that for every $y \in A$, $(x,y) \notin R$ or $(y,x) \in R$.' This matches Option 1.

Let's check other options:
Option 2: 'There exists $x \in A$ such that for every $y \in A$, if $(x,y) \in R$ then $(y,x) \in R$.'
Recall that $A \to B \equiv \neg A \lor B$. So, 'if $(x,y) \in R$ then $(y,x) \in R$' is equivalent to '$(x,y) \notin R$ or $(y,x) \in R$'.
Thus, Option 2 is equivalent to Option 1 and is also correct.

Option 3: 'For every $x \in A$, for every $y \in A$, $(x,y) \notin R$ or $(y,x) \in R$.'
This statement starts with $\forall x \forall y$, which is incorrect as our negation starts with $\exists x \forall y$. So, Option 3 is incorrect.

Option 4: 'There exists $x \in A$ such that for every $y \in A$, it is not true that $((x,y) \in R \land (y,x) \notin R)$.'
This is literally the step $\exists x \forall y \neg (P(x,y) \land Q(x,y))$ before applying De Morgan's. Thus, this is also equivalent to the negation and is correct.

Therefore, Options 1, 2, and 4 are correct."
:::

---

Summary

---

What's Next?

Chapter Summary

Chapter Review Questions

:::question type="MCQ" question="Which of the following is logically equivalent to the negation of the statement $\forall x (P(x) \implies \exists y (Q(y) \land R(x,y)))$?" options=["$\exists x (P(x) \land \forall y (\neg Q(y) \lor \neg R(x,y)))$", "$\exists x (\neg P(x) \lor \forall y (\neg Q(y) \lor \neg R(x,y)))$", "$\forall x (P(x) \land \exists y (\neg Q(y) \land \neg R(x,y)))$", "$\exists x (P(x) \land \exists y (\neg Q(y) \lor \neg R(x,y)))$"] answer="$\exists x (P(x) \land \forall y (\neg Q(y) \lor \neg R(x,y)))$" hint="Apply De Morgan's laws for quantifiers and propositional logic equivalences step-by-step." solution="Let the given statement be $S$.
$S = \forall x (P(x) \implies \exists y (Q(y) \land R(x,y)))$
We need to find $\neg S$.

$\neg S \equiv \neg (\forall x (P(x) \implies \exists y (Q(y) \land R(x,y))))$

Apply quantifier negation: $\equiv \exists x \neg (P(x) \implies \exists y (Q(y) \land R(x,y)))$

Apply implication equivalence $\neg (A \implies B) \equiv A \land \neg B$: $\equiv \exists x (P(x) \land \neg (\exists y (Q(y) \land R(x,y))))$

Apply quantifier negation again: $\equiv \exists x (P(x) \land \forall y \neg (Q(y) \land R(x,y)))$

Apply De Morgan's law $\neg (A \land B) \equiv \neg A \lor \neg B$: $\equiv \exists x (P(x) \land \forall y (\neg Q(y) \lor \neg R(x,y)))$

Therefore, the equivalent statement is $\exists x (P(x) \land \forall y (\neg Q(y) \lor \neg R(x,y)))$."}
:::

:::question type="NAT" question="Let the domain of discourse be the set of integers $D = \{-5, -4, \dots, 4, 5\}$. Consider the predicate $P(x)$ defined as '$x^2 < 10$'. How many elements in $D$ satisfy the predicate $P(x)$?" answer="7" hint="List the integers in the domain whose square is less than 10." solution="We need to find integers $x$ in $D = \{-5, -4, \dots, 4, 5\}$ such that $x^2 < 10$.
Let's test values:
* $(\pm 0)^2 = 0 < 10$ (satisfies)
* $(\pm 1)^2 = 1 < 10$ (satisfies)
* $(\pm 2)^2 = 4 < 10$ (satisfies)
* $(\pm 3)^2 = 9 < 10$ (satisfies)
* $(\pm 4)^2 = 16 \not< 10$ (does not satisfy)
* $(\pm 5)^2 = 25 \not< 10$ (does not satisfy)
The integers satisfying $P(x)$ are $\{-3, -2, -1, 0, 1, 2, 3\}$.
There are 7 such elements."}
:::

:::question type="MCQ" question="Let $S(x)$ be 'x is a student', $C(y)$ be 'y is a course', and $T(x,y)$ be 'x is taking y'. Which of the following predicate logic statements correctly translates the English sentence: 'Every student is taking at least one course'?" options=["$\forall x (S(x) \implies \exists y (C(y) \land T(x,y)))$", "$\forall x \exists y (S(x) \land C(y) \land T(x,y))$", "$\exists y \forall x (S(x) \land C(y) \implies T(x,y))$", "$\forall x (S(x) \land \exists y (C(y) \implies T(x,y)))$"] answer="$\forall x (S(x) \implies \exists y (C(y) \land T(x,y)))$" hint="Break down the sentence: 'Every student...' suggests a universal quantifier over students. '...is taking at least one course' suggests an existential quantifier over courses, connected with 'taking'." solution="Let's analyze the English sentence: 'Every student is taking at least one course'.
'Every student': This implies a universal quantifier over students. So, $\forall x (S(x) \implies ...)$. The implication is used because we are talking about if x is a student, then* something follows.
'...is taking at least one course': For each student, there exists some course they are taking. So, $\exists y (C(y) \land T(x,y))$. Here, we use conjunction because the student must be taking a course (C(y)) AND that specific course* (T(x,y)).
Combining these, we get $\forall x (S(x) \implies \exists y (C(y) \land T(x,y)))$.

Let's look at why other options are incorrect:
$\forall x \exists y (S(x) \land C(y) \land T(x,y))$: This means 'For every x, there exists a y such that x is a student AND y is a course AND x is taking y'. This falsely implies that everything* in the domain is a student, or that if x is a student, then it is necessarily taking a course AND for every x and y, x is a student and y is a course. The implication for 'every student' is lost.
$\exists y \forall x (S(x) \land C(y) \implies T(x,y))$: This translates to 'There exists a course y such that for every x, if x is a student and y is a course, then x is taking y'. This means there is one specific course that all students* are taking, which is not what the original sentence says.
* $\forall x (S(x) \land \exists y (C(y) \implies T(x,y)))$: This means 'For every x, x is a student AND there exists a y such that if y is a course, then x is taking y'. The initial conjunction $S(x) \land ...$ means that every element in the domain must be a student, which is incorrect. Also, $C(y) \implies T(x,y)$ for the existential part is not the correct formulation for 'taking at least one course'."}
:::

What's Next?