Logic

Overview

In our study of Artificial Intelligence, we are fundamentally concerned with the principles of reasoning. To build systems that can reason, we require a formal language with unambiguous syntax and semantics. Logic provides this foundation, serving as the principal tool for knowledge representation and automated inference. This chapter introduces the formalisms that allow an intelligent agent to represent its knowledge about the world and to deduce new conclusions from that knowledge. A mastery of these concepts is not merely an academic exercise; it is essential for understanding a wide array of AI topics, from automated planning to expert systems.

Our exploration will be structured into two primary domains. We begin with Propositional Logic, a system that deals with simple, declarative propositions and the logical connectives that combine them. While foundational, its expressive power is limited. We therefore advance to Predicate Logic, also known as First-Order Logic, which provides a far richer framework. This more powerful logic allows us to reason about objects, their properties, and the relations between them through the use of variables and quantifiers. For the GATE examination, a strong command of both systems is indispensable, as questions frequently test the ability to translate statements, determine logical equivalence, and prove the validity of arguments within these formal structures.

---

Chapter Contents

| # | Topic | What You'll Learn |
|---|-------|-------------------|
| 1 | Propositional Logic | Reasoning with simple declarative statements. |
| 2 | Predicate Logic | Reasoning about objects, properties, and relations. |

---

Learning Objectives

---

---

We now turn our attention to Propositional Logic...
## Part 1: Propositional Logic

Introduction

Propositional logic, also known as sentential logic, serves as the bedrock of formal reasoning within computer science and artificial intelligence. It provides a mathematical framework for representing and manipulating declarative statements, which are assertions that can be evaluated as either true or false. In the context of AI, propositional logic enables the construction of knowledge bases and the development of inference engines that can deduce new information from existing facts.

Our study will focus on the syntax and semantics of this logic. We will define propositions, explore the fundamental logical connectives used to build complex statements, and investigate the concepts of logical equivalence, tautology, and contradiction. A thorough understanding of these principles is not merely an academic exercise; it is essential for designing intelligent systems that can reason about the world in a precise and unambiguous manner, a skill frequently tested in the GATE examination.

---

Key Concepts

1. Logical Connectives and Truth Tables

To construct compound propositions, we use logical operators or connectives. The truth value of a compound proposition is determined entirely by the truth values of its constituent propositions and the connectives used.

The primary connectives are:
* Negation (NOT): $\neg p$. The negation of $p$ is true if and only if $p$ is false.
* Conjunction (AND): $p \land q$. The conjunction of $p$ and $q$ is true if and only if both $p$ and $q$ are true.
* Disjunction (OR): $p \lor q$. The disjunction of $p$ and $q$ is true if and only if at least one of $p$ or $q$ is true.
* Implication (IF...THEN): $p \implies q$. The implication is false only in the case where $p$ (the antecedent) is true and $q$ (the consequent) is false. In all other cases, it is true. This is a crucial point; a false antecedent always yields a true implication.
* Biconditional (IF AND ONLY IF): $p \iff q$. The biconditional is true if and only if $p$ and $q$ have the same truth value.

The behavior of these connectives is formally defined by a truth table.

p
q
¬p
p ∧ q
p ∨ q
p → q
p ↔ q

T
T
F
T
T
T
T


T
F
F
F
T
F
F


F
T
T
F
T
T
F


F
F
T
F
F
T
T

---

---

#
## 2. Logical Equivalence

Two compound propositions are said to be logically equivalent if they have the same truth value for all possible truth assignments of their constituent propositions. We denote equivalence using the symbol $\equiv$. Proving equivalence is a common task, often accomplished either by comparing truth tables or by applying a series of known equivalence laws.

Worked Example:

Problem: Prove that $(p \land q) \implies r$ is logically equivalent to $p \implies (q \implies r)$.

Solution:

We will use algebraic manipulation with known logical equivalences to transform the left-hand side (LHS) into the right-hand side (RHS).

Step 1: Start with the LHS and apply the implication equivalence law ($A \implies B \equiv \neg A \lor B$). Let $A = (p \land q)$ and $B = r$.

Step 2: Apply De Morgan's Law to the negated conjunction.

Step 3: Apply the associative law for disjunction to regroup the terms.

Step 4: Recognize the expression inside the parenthesis $(\neg q \lor r)$ as the disjunctive form of an implication. Apply the implication equivalence law in reverse ($\neg A \lor B \equiv A \implies B$).

Step 5: Apply the implication equivalence law one final time to the entire expression.

Result:

We have successfully transformed the LHS into the RHS. Therefore, we conclude:

---

#
## 3. Tautology, Contradiction, and Contingency

Based on their truth values across all possible interpretations, compound propositions can be classified into three categories.

To check if a statement is a tautology, one can either construct a full truth table and check if the final column contains only 'T', or one can use logical equivalences to simplify the expression to the logical constant for True ($T$).

Worked Example:

Problem: Determine if the statement $(p \land (p \implies q)) \implies q$ is a tautology.

Solution:

We will simplify the expression. If it simplifies to True ($T$), it is a tautology.

Step 1: Let the given expression be $S$.

Step 2: Apply the implication equivalence law to the inner implication $(p \implies q)$.

Step 3: Apply the distributive law to the expression within the first parenthesis.

Step 4: Simplify the term $(p \land \neg p)$, which is always a contradiction (False, $F$).

Step 5: Apply the identity law ($F \lor A \equiv A$).

Step 6: Apply the implication equivalence law to the main implication.

Step 7: Apply De Morgan's Law.

Step 8: Apply the associative law.

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

Step 10: Apply the domination law ($A \lor T \equiv T$).

Answer: Since the expression simplifies to True, the proposition $(p \land (p \implies q)) \implies q$ is a tautology. This specific tautology is a well-known rule of inference called Modus Ponens.

---

---

Problem-Solving Strategies

---

Common Mistakes

---

---

Practice Questions

:::question type="MCQ" question="Which of the following propositions is a contradiction?" options=["$(p \implies q) \lor (q \implies p)$","$(p \land q) \land (\neg p \lor \neg q)$","$(p \lor q) \lor (\neg p \lor \neg q)$","$p \implies (p \lor q)$"] answer="$(p \land q) \land (\neg p \lor \neg q)$" hint="Use De Morgan's law to simplify the second part of the expression and see if it contradicts the first part." solution="Let us analyze the option $(p \land q) \land (\neg p \lor \neg q)$.

Step 1: Apply De Morgan's Law to the second part of the expression, $(\neg p \lor \neg q)$.

Step 2: Substitute this back into the original expression.

Step 3: Let $A = (p \land q)$. The expression becomes $A \land \neg A$.

Step 4: By the law of non-contradiction, an expression of the form $A \land \neg A$ is always false ($F$).

Result:
The expression simplifies to $F$, which is a contradiction. Answer: \boxed{\text{Contradiction}}
"
:::

:::question type="NAT" question="Consider the propositional formula $F = (p \lor \neg q) \land (\neg p \lor q) \land (\neg p \lor \neg q)$. The number of truth assignments for the variables $p$ and $q$ that make the formula $F$ true is ___." answer="1" hint="Evaluate the formula for each of the four possible truth assignments for p and q: (T,T), (T,F), (F,T), (F,F)." solution="We need to find the number of satisfying assignments for the formula $F = (p \lor \neg q) \land (\neg p \lor q) \land (\neg p \lor \neg q)$. Let's test all four possible combinations of truth values for $p$ and $q$.

Case 1: $p=T, q=T$

Case 2: $p=T, q=F$

Case 3: $p=F, q=T$

Case 4: $p=F, q=F$

Result:
The formula $F$ is true only when $p=F$ and $q=F$. Thus, there is only one satisfying assignment. Answer: \boxed{1}
"
:::

:::question type="MSQ" question="Which of the following propositions are logically equivalent to $\neg(p \lor \neg q)$?" options=["$\neg p \land q$","$p \implies \neg q$","$\neg(q \implies p)$","$\neg p \implies q$"] answer="$\neg p \land q$,$\neg(q \implies p)$" hint="First, simplify the given expression using De Morgan's law. Then, simplify each option to see which ones match the simplified form." solution="Let us first simplify the given expression $\neg(p \lor \neg q)$.

Step 1: Apply De Morgan's Law.

Step 2: Apply the double negation law $\neg(\neg q) \equiv q$.

Now we evaluate each option to see if it is equivalent to $\neg p \land q$.

• Option A: $\neg p \land q$

This is identical to our simplified expression. So, it is equivalent.

• Option B: $p \implies \neg q$

Using implication equivalence, this is $\neg p \lor \neg q$. This is not equivalent to $\neg p \land q$.

• Option C: $\neg(q \implies p)$

First, apply implication equivalence inside the parenthesis: $\neg(\neg q \lor p)$. Next, apply De Morgan's Law: $\neg(\neg q) \land \neg p$. Finally, apply double negation: $q \land \neg p$. By the commutative law, this is $\neg p \land q$. So, it is equivalent.

• Option D: $\neg p \implies q$

Using implication equivalence, this is $\neg(\neg p) \lor q$, which simplifies to $p \lor q$. This is not equivalent to $\neg p \land q$.

Result:
The propositions equivalent to $\neg(p \lor \neg q)$ are $\neg p \land q$ and $\neg(q \implies p)$. Answer: \boxed{\neg p \land q \text{ and } \neg(q \implies p)}
"
:::

:::question type="MCQ" question="The proposition $(p \implies q) \iff (\neg q \implies \neg p)$ is a:" options=["Tautology","Contradiction","Contingency","None of the above"] answer="Tautology" hint="The expression $(\neg q \implies \neg p)$ is the contrapositive of $(p \implies q)$. Recall the relationship between an implication and its contrapositive." solution="
Step 1: Identify the structure of the proposition. It is a biconditional $A \iff B$, where $A = (p \implies q)$ and $B = (\neg q \implies \neg p)$.

Step 2: Analyze the relationship between $A$ and $B$. The expression $B$ is the contrapositive of $A$.

Step 3: Recall the contrapositive law, which states that an implication is logically equivalent to its contrapositive.

Step 4: Since $A \equiv B$, the biconditional $A \iff B$ will be true for all possible truth assignments of $p$ and $q$. An expression that is always true is, by definition, a tautology.

Result:
The given proposition is a tautology. Answer: \boxed{\text{Tautology}}
"
:::

---

Summary

---

---

What's Next?

---

---

Part 2: Predicate Logic

Introduction

Predicate Logic, often referred to as First-Order Logic (FOL), represents a significant extension of the expressive power of Propositional Logic. While propositional logic deals with simple declarative sentences that are either true or false, predicate logic allows us to reason about objects, their properties, and the relations between them. It achieves this by introducing variables, predicates, and quantifiers, which enable the formulation of general statements about entire domains of objects.

For the GATE Data Science and Artificial Intelligence examination, a firm grasp of predicate logic is essential for topics in knowledge representation and automated reasoning. The ability to translate natural language statements into formal logical expressions, and to understand the equivalences between such expressions, is a frequently tested skill. This chapter will provide a rigorous foundation in the syntax and semantics of predicate logic, with a specific focus on the patterns and problem-solving techniques most relevant to the GATE syllabus.

---

Key Concepts

1. Components of Predicate Logic

To construct meaningful statements, we must first understand the fundamental building blocks of the language of predicate logic.

* Objects: These are the individual entities in the domain of discourse. We represent them using:
* Constants: Symbols that refer to specific objects (e.g., `John`, `BlockA`, `2`).
* Variables: Symbols that can refer to any object in the domain (e.g., $x, y, z$).

* Predicates: A predicate is a symbol that represents a property of an object or a relation between objects. It can be thought of as a function that maps one or more objects to a truth value (True or False).
* Example 1 (Property): `IsEven(x)` is a predicate that is true if the variable $x$ is an even number.
* Example 2 (Relation): `TallerThan(x, y)` is a predicate that is true if object $x$ is taller than object $y$.
The number of objects a predicate takes as arguments is its arity. `IsEven(x)` has arity one, while `TallerThan(x, y)` has arity two.

* Quantifiers: These are symbols that allow us to express the extent to which a predicate is true over a domain of objects.
* Universal Quantifier ($\forall$): Read as "for all" or "for every". A statement $\forall x P(x)$ asserts that $P(x)$ is true for every object $x$ in the domain.
* Existential Quantifier ($\exists$): Read as "there exists" or "for some". A statement $\exists x P(x)$ asserts that there is at least one object $x$ in the domain for which $P(x)$ is true.

* Logical Connectives: Predicate logic uses the same connectives as propositional logic:
* Conjunction ($\land$): AND
* Disjunction ($\lor$): OR
* Negation ($\neg$): NOT
* Implication ($\implies$): IF...THEN...
* Biconditional ($\iff$): IF AND ONLY IF

2. Translating Natural Language to Predicate Logic

A core skill for the GATE exam is the translation of English sentences into precise logical formulas. This requires identifying the correct quantifiers and connectives. Two patterns are particularly common and must be mastered.

Pattern 1: "All A are B"

This universal statement is translated using the universal quantifier ($\forall$) and implication ($\implies$). The general form is:
`All objects with property A also have property B.`

Pattern 2: "Some A are B"

This existential statement is translated using the existential quantifier ($\exists$) and conjunction ($\land$). The general form is:
`There exists at least one object that has both property A and property B.`

Worked Example:

Problem: Translate the sentence "Every student who studies AI is hardworking" into predicate logic. Let $S(x)$ be "$x$ is a student", $A(x)$ be "$x$ studies AI", and $H(x)$ be "$x$ is hardworking".

Solution:

Step 1: Identify the structure of the sentence.
The sentence is a universal statement ("Every student..."). It applies to all objects that satisfy a certain condition. The condition is "is a student and studies AI". The conclusion is "is hardworking".

Step 2: Formulate the antecedent (the condition).
The condition is that an object $x$ must be a student AND study AI. This is represented as $S(x) \land A(x)$.

Step 3: Formulate the consequent (the conclusion).
The property being ascribed is "hardworking". This is represented as $H(x)$.

Step 4: Combine the antecedent and consequent using the universal quantification pattern.
The pattern for "All X are Y" is $\forall x (X(x) \implies Y(x))$. Here, $X(x)$ is our condition $S(x) \land A(x)$ and $Y(x)$ is our conclusion $H(x)$.

Answer: The logical representation is $\forall x ((S(x) \land A(x)) \implies H(x))$.

---

---

#
## 3. Logical Equivalence and Inference

Understanding when two different-looking statements mean the same thing is critical for multiple-choice questions.

Law of Contraposition:
An implication and its contrapositive are logically equivalent. This is a powerful tool for rephrasing statements.

De Morgan's Laws for Quantifiers:
These laws describe how to negate a quantified statement. Negation "flips" the quantifier and moves inside the expression.

("It is not the case that all $x$ have property P" is equivalent to "There exists an $x$ that does not have property P.") ("It is not the case that there exists an $x$ with property P" is equivalent to "For all $x$, $x$ does not have property P.")

Worked Example:

Problem: Find a logically equivalent statement to: "All birds can fly."
Let $B(x)$ be "$x$ is a bird" and $F(x)$ be "$x$ can fly".

Solution:

Step 1: Translate the original statement into predicate logic.
This is a universal statement, so we use the pattern $\forall x (A(x) \implies B(x))$.

Step 2: Apply the Law of Contraposition to the inner implication.
The inner implication is $B(x) \implies F(x)$. Its contrapositive is $\neg F(x) \implies \neg B(x)$.

Step 3: Substitute the contrapositive back into the quantified statement.

Step 4: Translate the new logical statement back into English.
This statement reads: "For all objects $x$, if $x$ cannot fly, then $x$ is not a bird." Or, more naturally, "Anything that cannot fly is not a bird."

Answer: An equivalent statement is "Anything that cannot fly is not a bird."

---

Problem-Solving Strategies

When faced with a natural language translation problem in GATE, a systematic approach is crucial.

---

Common Mistakes

Students often fall into two main traps when translating sentences. Understanding these will help you avoid them.

---

Practice Questions

:::question type="MCQ" question="Let $C(x)$ be '$x$ is a course', $D(x)$ be '$x$ is difficult', and $R(x)$ be '$x$ is rewarding'. Which of the following is the logical representation of the statement, 'All difficult courses are rewarding'?" options=["$\exists x (C(x) \land D(x) \land R(x))$","$\forall x ((C(x) \land D(x)) \implies R(x))$","$\forall x (C(x) \land (D(x) \implies R(x)))$","$\forall x (D(x) \land R(x))$"] answer="$\forall x ((C(x) \land D(x)) \implies R(x))$" hint="The statement is universal ('All'). The condition for a course being rewarding is that it is both a course and difficult." solution="
Step 1: Identify the structure. The statement is universal ('All'), so we will use the $\forall$ quantifier. The structure is 'All things with property A are things with property B'.

Step 2: Define property A. Property A is 'is a difficult course'. This means an object $x$ must be a course, $C(x)$, AND it must be difficult, $D(x)$. So, property A is represented by $(C(x) \land D(x))$.

Step 3: Define property B. Property B is 'is rewarding', represented by $R(x)$.

Step 4: Apply the universal quantification pattern: $\forall x (A(x) \implies B(x))$.
Substituting our properties, we get:

This matches the second option.
Answer: \boxed{\forall x ((C(x) \land D(x)) \implies R(x))}
"
:::

:::question type="NAT" question="Consider a domain of integers $\{1, 2, 3, 4\}$. Let $P(x)$ be the predicate '$x$ is prime' and $E(x)$ be the predicate '$x$ is even'. The statement $\exists x (P(x) \land \neg E(x))$ asserts that there is a prime number that is not even. How many values of $x$ in the domain satisfy the predicate $(P(x) \land \neg E(x))$?" answer="1" hint="Check each integer in the domain. A number is prime if it is greater than 1 and divisible only by 1 and itself. The prime numbers in the domain are 2 and 3." solution="
Step 1: Identify the predicate to be satisfied: $(P(x) \land \neg E(x))$. This means we are looking for numbers that are prime AND not even.

Step 2: Evaluate the predicate for each element in the domain $\{1, 2, 3, 4\}$.

• For $x=1$: $P(1)$ is False (1 is not prime). The conjunction is False.


• For $x=2$: $P(2)$ is True. $E(2)$ is True, so $\neg E(2)$ is False. The conjunction $P(2) \land \neg E(2)$ is False.


• For $x=3$: $P(3)$ is True. $E(3)$ is False, so $\neg E(3)$ is True. The conjunction $P(3) \land \neg E(3)$ is True.


• For $x=4$: $P(4)$ is False. The conjunction is False.

Step 3: Count the number of values for which the predicate is true.
The predicate is true only for $x=3$. Therefore, there is only one such value.

Answer: \boxed{1}
"
:::

:::question type="MSQ" question="Let $S(x)$ be '$x$ is a server' and $F(x)$ be '$x$ is fast'. The statement 'No server is fast' is represented as $\forall x (S(x) \implies \neg F(x))$. Which of the following statements are logically equivalent to this representation? " options=["$\forall x (F(x) \implies \neg S(x))$","$\neg \exists x (S(x) \land F(x))$","$\forall x (\neg S(x) \lor \neg F(x))$","$\exists x (S(x) \land \neg F(x))$"] answer="$\forall x (F(x) \implies \neg S(x))$,$\neg \exists x (S(x) \land F(x))$,$\forall x (\neg S(x) \lor \neg F(x))$" hint="Consider the contrapositive, De Morgan's law, and the definition of implication ($P \implies Q \equiv \neg P \lor Q$)." solution="
The original statement is $L_1: \forall x (S(x) \implies \neg F(x))$.

Let's analyze each option:

$\forall x (F(x) \implies \neg S(x))$: This is the contrapositive of the original statement's inner implication. The contrapositive of $(P \implies \neg Q)$ is $(\neg(\neg Q) \implies \neg P)$, which simplifies to $(Q \implies \neg P)$. In our case, this is $(F(x) \implies \neg S(x))$. Since an implication is equivalent to its contrapositive, this statement is equivalent. This option is correct.

$\neg \exists x (S(x) \land F(x))$: This means 'There does not exist an x that is both a server and fast'. This is the natural language meaning of 'No server is fast'. Let's prove the equivalence. Using De Morgan's law for quantifiers on this statement gives $\forall x \neg(S(x) \land F(x))$. By propositional De Morgan's law, this is $\forall x (\neg S(x) \lor \neg F(x))$. This is equivalent to $\forall x (S(x) \implies \neg F(x))$ by the definition of implication. This option is correct.

$\forall x (\neg S(x) \lor \neg F(x))$: As shown in the previous point, the original statement $L_1$ can be rewritten using the definition of implication ($P \implies Q \equiv \neg P \lor Q$). So, $\forall x (S(x) \implies \neg F(x))$ is equivalent to $\forall x (\neg S(x) \lor \neg F(x))$. This option is correct.

$\exists x (S(x) \land \neg F(x))$: This statement means 'There exists a server that is not fast'. This is not equivalent to 'No server is fast'. For example, if there is one slow server and one fast server, this statement is true, but the original statement ('No server is fast') is false. This option is incorrect.

Answer: \boxed{\forall x (F(x) \implies \neg S(x)), \neg \exists x (S(x) \land F(x)), \forall x (\neg S(x) \lor \neg F(x))}
"
:::

:::question type="MCQ" question="Which sentence is represented by the logical expression $\exists x (Laptop(x) \land (\forall y (Laptop(y) \implies Price(x) \le Price(y))))$? Assume $Price(x)$ is a function returning the price of $x$." options=["All laptops have the same price.","There exists an expensive laptop.","There is a laptop that is cheaper than all other laptops.","There exists a laptop with the minimum price."] answer="There exists a laptop with the minimum price." hint="Break down the expression. The outer $\exists x$ says 'there is a laptop x such that...'. The inner $\forall y$ describes a property of this specific laptop x." solution="
Step 1: Analyze the outer part of the expression.
$\exists x (Laptop(x) \land ...)$ means "There exists an object $x$ which is a laptop and has some other property".

Step 2: Analyze the inner part of the expression.
The other property is $(\forall y (Laptop(y) \implies Price(x) \le Price(y)))$. This is a universal statement about a different variable $y$. It says, "For any object $y$, if $y$ is a laptop, then the price of our specific $x$ is less than or equal to the price of $y$."

Step 3: Combine the two parts.
The full expression states: "There exists a laptop $x$ such that for all other laptops $y$, the price of $x$ is less than or equal to the price of $y$."

Step 4: Rephrase in natural language.
This is the definition of a laptop having the minimum price. It is the cheapest or is tied for the cheapest.

Answer: \boxed{There exists a laptop with the minimum price.}
"
:::

---

Summary

---

What's Next?

Chapter Summary

---

Chapter Review Questions

:::question type="MCQ" question="Let $S(x)$ denote '$x$ is a student', $C(y)$ denote '$y$ is a course', and $E(x, y)$ denote '$x$ is enrolled in $y$'. Which of the following is the correct logical translation of the statement 'There is a student who is enrolled in every course'?" options=["$\forall x (S(x) \rightarrow (\exists y (C(y) \land E(x, y))))$","$\exists x (S(x) \land (\forall y (C(y) \rightarrow E(x, y))))$","$\exists x \exists y (S(x) \land C(y) \land E(x, y))$","$\forall y (C(y) \rightarrow (\exists x (S(x) \land E(x, y))))$"] answer="$\exists x (S(x) \land (\forall y (C(y) \rightarrow E(x, y))))$" hint="The primary quantifier is 'There is a student...', which suggests an existential quantifier over students. The condition on this student is that they are enrolled in 'every course', which suggests a universal quantifier over courses." solution="Let us deconstruct the statement 'There is a student who is enrolled in every course'.

The statement asserts the existence of a particular type of individual. This translates to the existential quantifier $\exists x$.

This individual must be a student. So, we have $\exists x (S(x) \land \dots)$. We use conjunction ($\land$) because we are asserting the existence of an object that is both a student and possesses another property.

The property this student possesses is that 'they are enrolled in every course'. This is a statement about this specific student $x$ and all courses.

To translate 'for every course $y$', we use the universal quantifier $\forall y$.

The structure for a universal statement 'All $A$s are $B$s' is $\forall y (A(y) \rightarrow B(y))$. Here, $A(y)$ is '$y$ is a course' ($C(y)$), and $B(y)$ is '$x$ is enrolled in $y$' ($E(x, y)$).

Thus, 'for every course $y$, if $y$ is a course, then $x$ is enrolled in $y$' becomes $\forall y (C(y) \rightarrow E(x, y))$.

Combining these parts, we arrive at the final expression:

This matches option B.
Answer: \boxed{\exists x (S(x) \land (\forall y (C(y) \rightarrow E(x, y))))}
"
:::

:::question type="NAT" question="A Boolean function is defined over three propositional variables $P$, $Q$, and $R$. The function evaluates to True if and only if an odd number of variables are True. How many combinations of input values in its truth table result in an output of False?" answer="4" hint="A truth table for a function of 3 variables has $2^3$ rows. First, determine for how many of these rows the function's condition (odd number of True inputs) is met." solution="The function $f(P, Q, R)$ is defined over 3 variables. The total number of possible input combinations (rows in the truth table) is $2^3 = 8$.

The function evaluates to True if the number of variables with a value of True is odd. We need to count these cases:

Exactly one variable is True:

- (T, F, F), (F, T, F), (F, F, T)
- This can be calculated as choosing 1 variable out of 3 to be True: $\binom{3}{1} = 3$ cases.

Exactly three variables are True:

- (T, T, T)
- This can be calculated as choosing 3 variables out of 3 to be True: $\binom{3}{3} = 1$ case.

The total number of cases where the function is True is the sum of these counts: $3 + 1 = 4$.

The question asks for the number of combinations where the output is False. This will be the total number of combinations minus the number of combinations where the output is True.

Number of False outputs = (Total combinations) - (Number of True outputs)

Therefore, the function evaluates to False for 4 combinations of input values.
Answer: \boxed{4}
"
:::

:::question type="MCQ" question="Consider the following argument:
Premise 1: If the program compiles, then it is syntactically correct. $(C \rightarrow S)$
Premise 2: If the program is syntactically correct, then it will not produce an error during linking. $(S \rightarrow \neg L)$
Premise 3: The program produces an error during linking. $(L)$
Which of the following conclusions is guaranteed to be true?" options=["The program compiles.","The program does not compile.","The program is syntactically correct.","The program both compiles and is syntactically correct."] answer="The program does not compile." hint="Use the rules of Modus Tollens and Hypothetical Syllogism to combine the given premises and derive a valid conclusion." solution="Let us formalize the given statements:

• $C$: The program compiles.


• $S$: The program is syntactically correct.


• $L$: The program produces an error during linking.

The premises are:

$C \rightarrow S$

$S \rightarrow \neg L$

$L$

We can proceed with a step-by-step derivation:

Step 1: Combine Premise 1 and Premise 2 using Hypothetical Syllogism.
From $(C \rightarrow S)$ and $(S \rightarrow \neg L)$, we can infer $(C \rightarrow \neg L)$.
This new statement means 'If the program compiles, then it will not produce an error during linking'.

Step 2: Use the result from Step 1 with Premise 3.
We have the derived statement $(C \rightarrow \neg L)$ and the premise $L$.
From $L$, we can state its double negation, $\neg(\neg L)$.
Now, we have $(C \rightarrow \neg L)$ and $\neg(\neg L)$. This is a direct application of Modus Tollens.
Modus Tollens states that from $P \rightarrow Q$ and $\neg Q$, we can infer $\neg P$.
Here, $P$ is $C$ and $Q$ is $\neg L$.
Therefore, we can infer $\neg C$.

The conclusion $\neg C$ corresponds to the statement 'The program does not compile'. This matches option B.
Answer: \boxed{The program does not compile.}
"
:::

---

What's Next?