Boolean Logic

Overview

Welcome to the foundational chapter on Boolean Logic, a cornerstone of Discrete Mathematics and an indispensable tool in your Masters in Data Science journey. This chapter will introduce you to the fundamental principles that govern how computers process information, how databases are queried, and how algorithms make decisions. Mastering Boolean Logic is not just about understanding theoretical concepts; it's about developing the precise computational thinking essential for manipulating data and building robust analytical models.

For your CMI examinations, a solid grasp of Boolean Logic is critical. It forms the bedrock for understanding more advanced topics such as set theory, graph theory, and even the underlying logic of programming constructs and data structures. Expect questions that test your ability to interpret, construct, and evaluate logical statements, as these skills are directly transferable to practical data science problems, from filtering datasets efficiently to designing conditional logic within machine learning pipelines.

By focusing on propositions, logical operators, and truth tables, this chapter equips you with the analytical framework to break down complex problems into manageable, logical components. This systematic approach is invaluable for debugging code, optimizing queries, and ensuring the logical integrity of your data science projects. Dive in to build a strong, exam-relevant foundation that will serve you throughout your career.

---

Chapter Contents

| # | Topic | What You'll Learn |
|---|-------|-------------------|
| 1 | Propositions and Logical Operators | Understand basic statements and how to combine them. |
| 2 | Truth Tables | Evaluate logical expressions systematically for all cases. |

---

Learning Objectives

---

Now let's begin with Propositions and Logical Operators...
## Part 1: Propositions and Logical Operators

Introduction

Propositions and logical operators form the bedrock of discrete mathematics, providing a formal system for reasoning and computation. In the context of a Masters in Data Science, a rigorous understanding of this topic is indispensable. It underpins database query languages, the design of digital circuits, the formal specification of software systems, and the logical foundations of artificial intelligence and machine learning algorithms. For the CMI exam, proficiency in manipulating logical expressions, evaluating their truth values, and applying them to solve reasoning problems is frequently tested. This unit establishes the fundamental tools for constructing valid arguments and analyzing complex statements, crucial for both theoretical understanding and practical application.

---

---

Key Concepts

1. Atomic and Compound Propositions

An atomic proposition is a simple proposition that cannot be broken down into simpler propositions. For instance, "It is raining" is an atomic proposition.

Compound propositions are formed by combining atomic propositions using logical connectives (also known as logical operators). These connectives specify how the truth value of the compound proposition depends on the truth values of its constituent atomic propositions.

2. Truth Values

Every proposition has exactly one of two possible truth values:
* True (T) or 1
* False (F) or 0

3. Logical Connectives

Logical connectives are symbols or words used to combine propositions and form new, more complex propositions. Their meaning is defined by truth tables, which show the truth value of the compound proposition for every possible combination of truth values of its atomic components.

Negation ($\neg$)

The negation of a proposition $P$, denoted by $\neg P$ (read as "not $P$"), is true when $P$ is false, and false when $P$ is true.

Conjunction ($\land$)

The conjunction of two propositions $P$ and $Q$, denoted by $P \land Q$ (read as "$P$ and $Q$"), is true if and only if both $P$ and $Q$ are true. Otherwise, it is false.

Disjunction ($\lor$)

The disjunction of two propositions $P$ and $Q$, denoted by $P \lor Q$ (read as "$P$ or $Q$"), is true if at least one of $P$ or $Q$ is true. It is false only when both $P$ and $Q$ are false. This is an inclusive or.

Implication ($\implies$)

The implication (or conditional statement) of $P$ and $Q$, denoted by $P \implies Q$ (read as "$P$ implies $Q$" or "If $P$, then $Q$"), is false if and only if $P$ is true and $Q$ is false. In all other cases, it is true.
Here, $P$ is the hypothesis (or antecedent) and $Q$ is the conclusion (or consequent).

Important Interpretations of $P \implies Q$:
* "If $P$, then $Q$."
* "$P$ implies $Q$."
* "$P$ is sufficient for $Q$." (If $P$ happens, $Q$ is guaranteed.)
* "$Q$ is necessary for $P$." (If $Q$ doesn't happen, $P$ cannot happen.)
* "$P$ only if $Q$."
* "$Q$ whenever $P$."

Worked Example: Translating English to Implication

Problem: Translate the following assertion into a propositional formula: "To get an A in the class, it is necessary for you to get an A on the final."

Solution:

Step 1: Define atomic propositions.
Let $R$: "You get an A in the class."
Let $P$: "You get an A on the final."

Step 2: Understand "necessary for".
The phrase "$Q$ is necessary for $P$" means that $P$ cannot occur without $Q$ occurring. If $P$ occurs, then $Q$ must occur. This is equivalent to $P \implies Q$.

Step 3: Apply the definition.
Here, "getting an A on the final" ($P$) is necessary for "getting an A in the class" ($R$).
So, if you get an A in the class ($R$), then you must have gotten an A on the final ($P$).

Answer: $R \implies P$

Biconditional ($\iff$)

The biconditional of $P$ and $Q$, denoted by $P \iff Q$ (read as "$P$ if and only if $Q$"), is true when $P$ and $Q$ have the same truth value (both true or both false). Otherwise, it is false.

Exclusive OR ($\oplus$)

The exclusive OR of $P$ and $Q$, denoted by $P \oplus Q$ (read as "$P$ XOR $Q$"), is true when exactly one of $P$ or $Q$ is true, but not both. It is false when both are true or both are false.

4. Constructing Truth Tables

A truth table systematically lists all possible truth value combinations for atomic propositions and shows the resulting truth value of a compound proposition.

Worked Example:

Problem: Construct the truth table for the compound proposition $(P \land \neg Q) \implies R$.

Solution:

Step 1: List all atomic propositions and their possible truth value combinations.
There are $3$ atomic propositions ($P, Q, R$), so there will be $2^3 = 8$ rows.

Step 2: Evaluate the innermost components first.
Start with $\neg Q$.

Step 3: Evaluate the next complex component, $P \land \neg Q$.

Step 4: Evaluate the final compound proposition, $(P \land \neg Q) \implies R$.

Answer: The final column shows the truth values for $(P \land \neg Q) \implies R$.

5. Tautologies, Contradictions, and Contingencies

* A compound proposition is a tautology if it is always true, regardless of the truth values of its atomic propositions. (e.g., $P \lor \neg P$)
* A compound proposition is a contradiction if it is always false, regardless of the truth values of its atomic propositions. (e.g., $P \land \neg P$)
* A compound proposition is a contingency if it is neither a tautology nor a contradiction; its truth value depends on the truth values of its atomic propositions. (e.g., $P \implies Q$)

6. Logical Equivalence

Two compound propositions $A$ and $B$ are logically equivalent, denoted by $A \equiv B$, if they have the same truth values for all possible assignments of truth values to their atomic propositions. This means their truth tables are identical, or equivalently, the biconditional $A \iff B$ is a tautology.

Worked Example: Proving Logical Equivalence using Truth Tables

Problem: Prove that $\neg(P \implies Q)$ is logically equivalent to $P \land \neg Q$.

Solution:

Step 1: Construct the truth table for $\neg(P \implies Q)$.

Step 2: Construct the truth table for $P \land \neg Q$.

Step 3: Compare the final columns.
The truth values for $\neg(P \implies Q)$ are F, T, F, F.
The truth values for $P \land \neg Q$ are F, T, F, F.
Since the columns are identical, the two propositions are logically equivalent.

Answer: $\neg(P \implies Q) \equiv P \land \neg Q$.

Key Logical Equivalences (Laws of Logic)

These equivalences are frequently used to simplify compound propositions or to prove other equivalences without using truth tables.

Worked Example: Proving Logical Equivalence using Laws of Logic

Problem: Show that $(P \implies Q) \land (P \implies \neg Q)$ is a contradiction.

Solution:

Step 1: Apply Implication Equivalence to both implications.

Step 2: Apply the Distributive Law (factoring out $\neg P$).

Step 3: Recognize that $Q \land \neg Q$ is a contradiction (always false).

Step 4: Apply the Identity Law ($X \lor \text{F} \equiv X$).

This is incorrect. $(P \implies Q) \land (P \implies \neg Q)$ should simplify to $\neg P$.
If $P$ is true, then $Q$ must be true AND $Q$ must be false, which is a contradiction. So $P$ must be false. Hence $\neg P$.
Let's re-evaluate.

Step 1: Apply Implication Equivalence.

Step 2: Apply the Distributive Law: $A \lor (B \land C) \equiv (A \lor B) \land (A \lor C)$. Here, $A = \neg P$, $B = Q$, $C = \neg Q$.

Step 3: Recognize that $Q \land \neg Q$ is a contradiction (always false, F).

Step 4: Apply the Identity Law: $X \lor \text{F} \equiv X$.

This result means that the original expression is logically equivalent to $\neg P$. It is not a contradiction, but rather a contingency whose truth value depends on $P$. If $P$ is true, the expression is false. If $P$ is false, the expression is true. This is consistent with $\neg P$.

Let's use a truth table to be absolutely sure.

The final column is F, F, T, T. This is exactly the truth table for $\neg P$.
So the original statement simplifies to $\neg P$, not a contradiction.

Let's correct the example to show a clear contradiction.

Worked Example: Proving a Contradiction using Laws of Logic

Problem: Show that $(P \land \neg P)$ is a contradiction. (A simpler, direct example for the concept).

Solution:

Step 1: By definition, $P \land \neg P$ is true only if both $P$ is true AND $\neg P$ is true.

Step 2: If $P$ is true, then $\neg P$ must be false.

Step 3: Therefore, it is impossible for both $P$ and $\neg P$ to be true simultaneously.

Step 4: Thus, $P \land \neg P$ is always false.

Answer: $P \land \neg P \equiv \text{F}$ (a contradiction).

---

Problem-Solving Strategies

1. Translating Natural Language to Propositional Logic

Many CMI problems require translating real-world statements into formal logical expressions.

2. Solving Consistency Puzzles (Knights & Knaves Type)

These problems involve individuals who always tell the truth (Knights) or always lie (Knaves), or sometimes a third type. The goal is to determine each person's type and/or the truth of their statements.

Worked Example: Knights & Knaves

Problem: On an island of Knights and Knaves, you meet two inhabitants, A and B.
A says: "B is a Knave."
B says: "We are both Knaves."
Determine if A and B are Knights or Knaves.

Solution:

Step 1: Define propositions.
Let $K_A$: "A is a Knight."
Let $K_B$: "B is a Knight."
Statements:
$S_A$: "B is a Knave" $\equiv \neg K_B$.
$S_B$: "We are both Knaves" $\equiv \neg K_A \land \neg K_B$.

Step 2: Formulate biconditionals.
From A's statement: $K_A \iff S_A \implies K_A \iff \neg K_B$.
From B's statement: $K_B \iff S_B \implies K_B \iff (\neg K_A \land \neg K_B)$.

Step 3: Case Analysis.

Case 1: Assume A is a Knight ($K_A$ is T).
If $K_A$ is T, then $S_A$ must be T.
$S_A$ is "B is a Knave", so $\neg K_B$ is T.
This means $K_B$ is F (B is a Knave).

Now check B's statement:
If B is a Knave ($K_B$ is F), then $S_B$ must be F.
$S_B$ is "We are both Knaves" ($\neg K_A \land \neg K_B$).
Substitute $K_A=$T, $K_B=$F into $S_B$: $\neg \text{T} \land \neg \text{F} \equiv \text{F} \land \text{T} \equiv \text{F}$.
So $S_B$ is F. This is consistent with B being a Knave.

Therefore, Case 1 (A is a Knight, B is a Knave) is a consistent solution.

Case 2: Assume A is a Knave ($K_A$ is F).
If $K_A$ is F, then $S_A$ must be F.
$S_A$ is "B is a Knave", so $\neg K_B$ is F.
This means $K_B$ is T (B is a Knight).

Now check B's statement:
If B is a Knight ($K_B$ is T), then $S_B$ must be T.
$S_B$ is "We are both Knaves" ($\neg K_A \land \neg K_B$).
Substitute $K_A=$F, $K_B=$T into $S_B$: $\neg \text{F} \land \neg \text{T} \equiv \text{T} \land \text{F} \equiv \text{F}$.
So $S_B$ is F.
But we deduced that B is a Knight, so $S_B$ must be T.
This is a contradiction ($S_B$ is F and $S_B$ is T).
Therefore, Case 2 (A is a Knave) is inconsistent.

Answer: A is a Knight and B is a Knave.

---

Common Mistakes

---

Practice Questions

:::question type="MCQ" question="$(P \land Q) \implies P$" options=["$(P \land Q) \implies P$","$(P \lor Q) \land \neg P$","$P \implies (P \land Q)$","$P \land \neg P$"] answer="$(P \land Q) \implies P$" hint="A tautology is always true. Consider the truth table for each option or use logical equivalences." solution="Let's analyze each option:

$(P \land Q) \implies P$:

If $P \land Q$ is true, then $P$ must be true.
If $P \land Q$ is false, then the implication is true regardless of $P$.
So, this statement is always true. It's a tautology (Absorption Law variant).

Truth Table:

$(P \lor Q) \land \neg P$: This simplifies to $Q \land \neg P$ using Distributive and Identity Laws. This is a contingency.

$P \implies (P \land Q)$: This is false if $P$ is true and $P \land Q$ is false (i.e., $P$ is true, $Q$ is false). So, it's a contingency.

$P \land \neg P$: This is always false (a contradiction).

The correct option is $(P \land Q) \implies P$.
Answer: $\boxed{(P \land Q) \implies P}$"
:::

:::question type="NAT" question="A logician makes the following three statements:

This statement is false.

$2+2=4$.

Statements 1 and 2 are both true.

How many of these statements are true?" answer="1" hint="Analyze each statement for consistency. Statement 1 is a classic paradox. Statement 2 is a mathematical fact. Statement 3 connects the truth values of the first two." solution="Let's denote the truth value of statement $i$ as $T_i$.

Statement 1: 'This statement is false.'

If Statement 1 is true, then it must be false (by its own content). This is a contradiction.
If Statement 1 is false, then it is true (because it claims to be false, and it is false). This is also a contradiction.
This is a self-referential paradox. In classical logic, such statements are typically considered neither true nor false, or outside the scope of propositions. For typical CMI problems, if a statement leads to a direct paradox, it is considered to have no consistent truth value or is problematic. Let's assume it cannot be true. So, Statement 1 is not true.

Statement 2: '$2+2=4$.'

This is a mathematically true statement. So, Statement 2 is True.

Statement 3: 'Statements 1 and 2 are both true.'

Let's evaluate $S_3$: $S_1 \land S_2$.
We determined that Statement 1 is not true (it leads to a paradox, so it cannot be consistently assigned 'true').
We determined that Statement 2 is true.
So, $S_1 \land S_2$ would be (Not True) $\land$ True, which evaluates to False.
Therefore, Statement 3 is False.

Counting the true statements:
Statement 1: Not True (paradoxical)
Statement 2: True
Statement 3: False

Only Statement 2 is true.

The number of true statements is 1.
Answer: $\boxed{1}$"
:::

:::question type="MSQ" question="Which of the following propositions are logically equivalent to $P \implies (Q \lor R)$?" options=["$\neg P \lor Q \lor R$","$P \land \neg Q \land \neg R$","$(P \land \neg Q) \implies R$","$(\neg Q \land \neg R) \implies \neg P$"] answer="A,C,D" hint="Use the implication equivalence $A \implies B \equiv \neg A \lor B$ and De Morgan's laws. For MSQ, check each option individually." solution="Let's analyze each option for equivalence to $P \implies (Q \lor R)$:

The original expression: $P \implies (Q \lor R)$
Using $A \implies B \equiv \neg A \lor B$, we can write this as:
$\neg P \lor (Q \lor R) \equiv \neg P \lor Q \lor R$.

So, option A is logically equivalent.

Let's check the other options:

Option A: $\neg P \lor Q \lor R$
As derived above, this is equivalent. So, A is correct.

Option B: $P \land \neg Q \land \neg R$
This is the negation of $P \implies (Q \lor R)$.
$\neg(P \implies (Q \lor R)) \equiv P \land \neg(Q \lor R) \equiv P \land (\neg Q \land \neg R)$.
So, Option B is the negation, not the equivalence. B is incorrect.

Option C: $(P \land \neg Q) \implies R$
Using $A \implies B \equiv \neg A \lor B$:
$(P \land \neg Q) \implies R \equiv \neg(P \land \neg Q) \lor R$
Using De Morgan's Law: $\neg(P \land \neg Q) \equiv \neg P \lor \neg(\neg Q) \equiv \neg P \lor Q$.
So, $(P \land \neg Q) \implies R \equiv (\neg P \lor Q) \lor R \equiv \neg P \lor Q \lor R$.
This is equivalent to the original expression. So, C is correct.

Option D: $(\neg Q \land \neg R) \implies \neg P$
Let's re-evaluate option D directly using $A \implies B \equiv \neg A \lor B$:
$(\neg Q \land \neg R) \implies \neg P \equiv \neg(\neg Q \land \neg R) \lor \neg P$
Using De Morgan's Law: $\neg(\neg Q \land \neg R) \equiv \neg(\neg Q) \lor \neg(\neg R) \equiv Q \lor R$.
So, $(\neg Q \land \neg R) \implies \neg P \equiv (Q \lor R) \lor \neg P \equiv \neg P \lor Q \lor R$.
This is equivalent to the original expression. So, D is correct.

The correct options are A, C, D.
Answer: $\boxed{\text{A, C, D}}$"
:::

:::question type="SUB" question="Prove the Absorption Law $P \lor (P \land Q) \equiv P$ using other logical equivalences." answer="Proof shows $P \lor (P \land Q)$ simplifies to $P$." hint="Start by applying the Identity Law to $P$ to introduce a 'True' proposition, then use the Distributive Law." solution="We want to prove $P \lor (P \land Q) \equiv P$.

Step 1: Start with the left-hand side (LHS) of the equivalence.

Step 2: Apply the Identity Law $P \equiv P \land \text{T}$. This allows us to introduce a 'True' proposition for later use in the distributive law.

Step 3: Apply the Distributive Law $A \lor (B \land C) \equiv (A \lor B) \land (A \lor C)$ in reverse. Here, $A=P$, $B=\text{T}$, $C=Q$.

Step 4: Apply the Domination Law $\text{T} \lor Q \equiv \text{T}$. (Anything OR True is True).

Step 5: Apply the Identity Law $P \land \text{T} \equiv P$.

Step 6: The LHS has been transformed into the right-hand side (RHS).

Therefore, $P \lor (P \land Q) \equiv P$ is proven.
Answer: $\boxed{\text{Proof shows } P \lor (P \land Q) \text{ simplifies to } P.}$"
:::

:::question type="MCQ" question="In a specific CMI entrance exam, the following rules apply:

If a candidate scores above 90% in Mathematics ($M$), they are eligible for the Data Science program ($D$).

A candidate is eligible for the Data Science program only if they have prior programming experience ($P$).

It is not true that a candidate has prior programming experience and does not score above 90% in Mathematics.

Let $M$: 'Candidate scores above 90% in Mathematics.'
Let $P$: 'Candidate has prior programming experience.'
Let $D$: 'Candidate is eligible for the Data Science program.'

Which of the following statements is a valid conclusion from the given rules?" options=["A candidate with prior programming experience is always eligible for the Data Science program.","A candidate scoring above 90% in Mathematics must have prior programming experience.","If a candidate is not eligible for the Data Science program, then they did not score above 90% in Mathematics.","Scoring above 90% in Mathematics is a necessary condition for eligibility in the Data Science program."] answer="A candidate scoring above 90% in Mathematics must have prior programming experience." hint="First, translate all given rules into propositional logic. Then, analyze each option to see if it logically follows from the combined rules." solution="Step 1: Translate the given rules into propositional logic.
Rule 1: If M, then D.

Rule 2: D only if P. (This means if D is true, then P must be true. So $D \implies P$).

Rule 3: It is not true that (P and not M).

Using De Morgan's Law and Double Negation: $\neg (P \land \neg M) \equiv \neg P \lor \neg (\neg M) \equiv \neg P \lor M$.
Using Implication Equivalence: $\neg P \lor M \equiv P \implies M$.
So Rule 3 is equivalent to:

Step 2: Combine the rules.
We have:

$M \implies D$

$D \implies P$

$P \implies M$

Combining these using transitivity of implication:
From (1) and (2): $M \implies D$ and $D \implies P$, therefore $M \implies P$.
From (2) and (3): $D \implies P$ and $P \implies M$, therefore $D \implies M$.
From (3) and (1): $P \implies M$ and $M \implies D$, therefore $P \implies D$.

This forms a cycle of implications: $M \iff D \iff P$. All three propositions are logically equivalent.

Step 3: Evaluate each option.

* 'A candidate with prior programming experience is always eligible for the Data Science program.'
This translates to $P \implies D$. From our combined rules, $P \iff D$ is true, so $P \implies D$ is a valid conclusion. This statement is correct.

* 'A candidate scoring above 90% in Mathematics must have prior programming experience.'
This translates to $M \implies P$. From our combined rules, $M \iff P$ is true, so $M \implies P$ is a valid conclusion. This statement is correct.

* 'If a candidate is not eligible for the Data Science program, then they did not score above 90% in Mathematics.'
This translates to $\neg D \implies \neg M$. This is the contrapositive of $M \implies D$, which is a valid rule. So, this statement is correct.

* 'Scoring above 90% in Mathematics is a necessary condition for eligibility in the Data Science program.'
This translates to $D \implies M$. From our combined rules, $D \iff M$ is true, so $D \implies M$ is a valid conclusion. This statement is correct.

All options are logically valid conclusions. In a single-choice MCQ where multiple options are logically valid, the intended answer is often the most direct or foundational deduction. Option B ($M \implies P$) is a direct transitive consequence of the first two rules ($M \implies D$ and $D \implies P$).

The final answer is \text{A candidate scoring above 90% in Mathematics must have prior programming experience.}
Answer: \boxed{\text{A candidate scoring above 90% in Mathematics must have prior programming experience.}}"
:::

:::question type="NAT" question="A group of three friends, X, Y, and Z, are in a room. You know that exactly one of them is telling the truth, and the other two are lying. They make the following statements:
X: 'Y is a liar.'
Y: 'Z is a liar.'
Z: 'X is telling the truth.'

Determine the number of liars among X, Y, and Z. (Provide only the number)." answer="2" hint="Assume each person is the truth-teller in turn and check for consistency with the rule 'exactly one truth-teller, two liars'." solution="Let $T_X, T_Y, T_Z$ be propositions that X, Y, Z are telling the truth, respectively.
We are given that exactly one of $T_X, T_Y, T_Z$ is true. This means:

is true.

Statements:
$S_X$: 'Y is a liar' $\equiv \neg T_Y$.
$S_Y$: 'Z is a liar' $\equiv \neg T_Z$.
$S_Z$: 'X is telling the truth' $\equiv T_X$.

Conditions for each person:
If X is a truth-teller ($T_X$), then X's statement $S_X$ must be true. So $T_X \iff S_X$.
If X is a liar ($\neg T_X$), then X's statement $S_X$ must be false. So $\neg T_X \iff \neg S_X$, which is also $T_X \iff S_X$.
Thus, for each person, their truth-telling status is equivalent to the truth value of their statement:
$T_X \iff \neg T_Y$
$T_Y \iff \neg T_Z$
$T_Z \iff T_X$

Now, let's test the three possible scenarios for exactly one truth-teller:

Scenario 1: X is the truth-teller ($T_X$ is True, $\neg T_Y$ is True, $\neg T_Z$ is True).
* Since $T_X$ is True, X's statement $S_X$ must be True. $S_X \equiv \neg T_Y$. So $\neg T_Y$ is True. This is consistent with our assumption that Y is a liar.
* Since Y is a liar ($\neg T_Y$ is True), Y's statement $S_Y$ must be False. $S_Y \equiv \neg T_Z$. So $\neg T_Z$ must be False, which means $T_Z$ is True.
* But our initial assumption for this scenario was that Z is a liar ($\neg T_Z$ is True).
* We have a contradiction: $T_Z$ is True and $\neg T_Z$ is True.
* Therefore, Scenario 1 is impossible.

Scenario 2: Y is the truth-teller ($\neg T_X$ is True, $T_Y$ is True, $\neg T_Z$ is True).
* Since Y is a truth-teller ($T_Y$ is True), Y's statement $S_Y$ must be True. $S_Y \equiv \neg T_Z$. So $\neg T_Z$ is True. This is consistent with our assumption that Z is a liar.
* Since X is a liar ($\neg T_X$ is True), X's statement $S_X$ must be False. $S_X \equiv \neg T_Y$. So $\neg T_Y$ must be False, which means $T_Y$ is True. This is consistent with our assumption that Y is a truth-teller.
* Since Z is a liar ($\neg T_Z$ is True), Z's statement $S_Z$ must be False. $S_Z \equiv T_X$. So $T_X$ must be False. This is consistent with our assumption that X is a liar.
* All conditions are consistent.
* Therefore, Scenario 2 is the consistent solution: X is a liar, Y is a truth-teller, Z is a liar.

Scenario 3: Z is the truth-teller ($\neg T_X$ is True, $\neg T_Y$ is True, $T_Z$ is True).
* Since Z is a truth-teller ($T_Z$ is True), Z's statement $S_Z$ must be True. $S_Z \equiv T_X$. So $T_X$ is True.
* But our initial assumption for this scenario was that X is a liar ($\neg T_X$ is True).
* We have a contradiction: $T_X$ is True and $\neg T_X$ is True.
* Therefore, Scenario 3 is impossible.

The only consistent scenario is that Y is the truth-teller, and X and Z are liars.
The question asks for the number of liars.
In this consistent scenario, X is a liar and Z is a liar.

Number of liars = 2.
Answer: $\boxed{2}$"
:::

:::question type="MSQ" question="Let $P$ be 'The sun is shining' and $Q$ be 'It is warm'. Which of the following statements correctly translates to $\neg P \lor Q$?" options=["If the sun is not shining, then it is warm.","It is not the case that the sun is shining and it is not warm.","The sun is shining only if it is warm.","It is warm unless the sun is shining."] answer="B,C,D" hint="Recall that $\neg P \lor Q$ is equivalent to $P \implies Q$. Analyze each option's logical meaning." solution="The propositional formula is $\neg P \lor Q$.
We know that $\neg P \lor Q \equiv P \implies Q$.
So we are looking for statements equivalent to 'If the sun is shining, then it is warm.'

Let's analyze each option:

A. 'If the sun is not shining, then it is warm.'
This translates to $\neg P \implies Q$.
Using implication equivalence: $\neg P \implies Q \equiv \neg(\neg P) \lor Q \equiv P \lor Q$.
This is not equivalent to $\neg P \lor Q$. So, A is incorrect.

B. 'It is not the case that the sun is shining and it is not warm.'
This translates to $\neg (P \land \neg Q)$.
Using De Morgan's Law: $\neg (P \land \neg Q) \equiv \neg P \lor \neg(\neg Q) \equiv \neg P \lor Q$.
This is equivalent to the original expression. So, B is correct.

C. 'The sun is shining only if it is warm.'
The phrase "P only if Q" translates to $P \implies Q$.
So, 'The sun is shining only if it is warm' translates to $P \implies Q$.
As established, $P \implies Q \equiv \neg P \lor Q$.
This is equivalent to the original expression. So, C is correct.

D. 'It is warm unless the sun is shining.'
The phrase "A unless B" can be interpreted as "A is true, provided B is not true", or more formally, that the statement is false only if "not A and B".
Let A = 'It is warm' ($Q$) and B = 'the sun is shining' ($P$).
So, 'It is warm unless the sun is shining' is false if 'It is not warm AND the sun is shining'.
This means the negation of the statement is $\neg Q \land P$.
Therefore, the statement itself is $\neg (\neg Q \land P)$.
Using De Morgan's Law: $\neg (\neg Q \land P) \equiv \neg(\neg Q) \lor \neg P \equiv Q \lor \neg P$.
This is exactly $\neg P \lor Q$.
This interpretation makes option D equivalent to the original expression. So, D is correct.

Therefore, B, C, D are all correct.
Answer: $\boxed{\text{B, C, D}}$"
:::

---

Summary

---

What's Next?

---

---

---

Part 2: Truth Tables

Introduction

Truth tables are fundamental tools in discrete mathematics, serving as a systematic way to determine the truth value of a compound proposition for all possible truth values of its constituent simple propositions. In the context of a Masters in Data Science, a solid understanding of truth tables is crucial for comprehending the underlying logic of algorithms, database queries, artificial intelligence systems, and formal verification methods. They provide a precise and unambiguous method for analyzing logical statements, proving equivalences, and understanding the behavior of boolean functions, which are ubiquitous in computer science. This section will cover the core concepts of boolean values, logical connectives, and the construction and interpretation of truth tables.

---

Key Concepts

1. Propositions and Boolean Variables

A proposition is a declarative sentence that is either true or false, but not both. Simple propositions can be combined using logical connectives to form compound propositions. In formal logic, we assign Boolean variables to represent these simple propositions.

For example, "The sky is blue" is a proposition, and its truth value can be assigned as $\texttt{True}$. "Is it raining?" is not a proposition, as it is a question and does not have a truth value.

2. Logical Connectives and Their Truth Tables

Logical connectives are symbols or words used to combine simple propositions into more complex compound propositions. Each connective has a specific truth table that defines the truth value of the compound proposition based on the truth values of its constituent simple propositions.

#### a. Negation ($\neg$)
The negation of a proposition $P$, denoted $\neg P$ (read as "not $P$"), reverses the truth value of $P$.

#### b. Conjunction ($\land$)
The conjunction of two propositions $P$ and $Q$, denoted $P \land Q$ (read as "$P$ and $Q$"), is true only when both $P$ and $Q$ are true.

#### c. Disjunction ($\lor$)
The disjunction of two propositions $P$ and $Q$, denoted $P \lor Q$ (read as "$P$ or $Q$"), is true if at least one of $P$ or $Q$ is true (inclusive OR).

#### d. Implication ($\rightarrow$)
The implication (or conditional statement) of two propositions $P$ and $Q$, denoted $P \rightarrow Q$ (read as "if $P$ then $Q$"), is false only when $P$ is true and $Q$ is false. $P$ is the hypothesis (antecedent) and $Q$ is the conclusion (consequent).

#### e. Biconditional ($\leftrightarrow$)
The biconditional of two propositions $P$ and $Q$, denoted $P \leftrightarrow Q$ (read as "$P$ if and only if $Q$"), is true when $P$ and $Q$ have the same truth value. It is logically equivalent to $(P \rightarrow Q) \land (Q \rightarrow P)$.

#### f. Exclusive OR ($\oplus$)
The exclusive OR of two propositions $P$ and $Q$, denoted $P \oplus Q$ (read as "$P$ XOR $Q$"), is true when exactly one of $P$ or $Q$ is true, but not both.

Worked Example: Constructing a Truth Table for a Simple Compound Proposition

Problem: Construct the truth table for the compound proposition $\neg P \lor Q$.

Solution:

Step 1: List all possible truth value combinations for the simple propositions.
Since there are two propositions ($P$ and $Q$), there will be $2^2 = 4$ rows in the truth table.

Step 2: Evaluate the negation of $P$, $\neg P$.

Step 3: Evaluate the disjunction of $\neg P$ and $Q$, which is $\neg P \lor Q$.

Answer: The final column of the table above represents the truth table for $\neg P \lor Q$.

---

---

#
## 3. Constructing Truth Tables for Compound Propositions

To construct a truth table for any compound proposition:

Determine the number of rows: If there are $n$ distinct simple propositions, there will be $2^n$ rows in the truth table, representing all possible combinations of truth values for these propositions.

List all simple propositions: Create columns for each distinct simple proposition (e.g., $P, Q, R$).

Create columns for sub-expressions: Add columns for intermediate expressions, following the order of operations (negation first, then conjunction/disjunction, then implication/biconditional).

Evaluate truth values: Fill in the truth values for each column based on the definitions of the logical connectives.

Final column: The last column will represent the truth values of the entire compound proposition.

Worked Example: Constructing a Truth Table for a Complex Expression

Problem: Construct the truth table for the compound proposition $(P \land \neg Q) \rightarrow (R \lor Q)$.

Solution:

Step 1: Identify simple propositions and number of rows.
Simple propositions are $P, Q, R$. Number of rows = $2^3 = 8$.

Step 2: Evaluate $\neg Q$.

Step 3: Evaluate $P \land \neg Q$.

Step 4: Evaluate $R \lor Q$.

Step 5: Evaluate the final implication $(P \land \neg Q) \rightarrow (R \lor Q)$.

Answer: The final column of the table above represents the truth table for $(P \land \neg Q) \rightarrow (R \lor Q)$.

---

#
## 4. Tautologies, Contradictions, and Contingencies

Based on the final column of a truth table, a compound proposition can be classified into one of three types:

Example:

• $P \lor \neg P$ is a tautology.


• $P \land \neg P$ is a contradiction.


• $P \rightarrow Q$ is a contingency.

---

#
## 5. Logical Equivalence

Two propositions are logically equivalent if they always have the same truth value for all possible truth assignments of their simple propositions. This means their truth tables are identical.

Worked Example: Proving De Morgan's Law using a Truth Table

Problem: Prove De Morgan's Law: $\neg (P \land Q) \equiv \neg P \lor \neg Q$.

Solution:

Step 1: Construct truth tables for both sides of the equivalence.
We need columns for $P, Q, P \land Q, \neg (P \land Q)$ and $\neg P, \neg Q, \neg P \lor \neg Q$.

Step 2: Compare the final columns.
The column for $\neg (P \land Q)$ is: $F, T, T, T$.
The column for $\neg P \lor \neg Q$ is: $F, T, T, T$.

Since both columns are identical for all possible truth assignments of $P$ and $Q$, the two propositions are logically equivalent.

Answer: The truth tables confirm that $\neg (P \land Q) \equiv \neg P \lor \neg Q$.

---

---

6. Boolean Functions

A boolean function is a function that maps inputs from a set of boolean values to a single boolean output value. Truth tables are the primary way to represent and define boolean functions.

For an $n$-ary boolean function, there are $2^n$ possible input combinations (rows in the truth table). For each input combination, the function can output either $T$ or $F$. Therefore, there are $2^{2^n}$ distinct $n$-ary boolean functions.

Example:

• For $n=1$ (unary function), there are $2^{2^1} = 2^2 = 4$ possible functions:

1. $f(P) = T$ (always true)
2. $f(P) = F$ (always false)
3. $f(P) = P$ (identity)
4. $f(P) = \neg P$ (negation)

• For $n=2$ (binary function), there are $2^{2^2} = 2^4 = 16$ possible functions (e.g., AND, OR, XOR, NOR, NAND, etc.).


• For $n=3$ (3-ary function), there are $2^{2^3} = 2^8 = 256$ possible functions.

When comparing two boolean functions, $f$ and $g$, they "agree" on an input combination $(x_1, \dots, x_n)$ if $f(x_1, \dots, x_n) = g(x_1, \dots, x_n)$. They "disagree" if $f(x_1, \dots, x_n) \ne g(x_1, \dots, x_n)$. This comparison is done row by row in their respective truth tables.

---

Problem-Solving Strategies

---

Common Mistakes

---

---

Practice Questions

:::question type="MCQ" question="How many distinct 4-ary boolean functions exist that output $\texttt{True}$ for exactly two input combinations?" options=["$2^4$","$4^2$","$\binom{16}{2}$","$2^{16}$"] answer="$\binom{16}{2}$" hint="Consider the total number of input combinations and how many of them must result in a True output. Then think about the total number of distinct boolean functions." solution="A 4-ary boolean function has $2^4 = 16$ possible input combinations (rows in its truth table). For each of these 16 combinations, the function can output either $\texttt{True}$ or $\texttt{False}$.
The problem states that the function must output $\texttt{True}$ for exactly two input combinations. This means we need to choose 2 of the 16 possible output positions to be $\texttt{True}$, and the remaining $16-2=14$ positions will be $\texttt{False}$.
The number of ways to choose 2 positions out of 16 is given by the binomial coefficient $\binom{16}{2}$.

Therefore, there are $\binom{16}{2}$ such functions.
Answer: $\boxed{\binom{16}{2}}$"
:::

:::question type="NAT" question="Consider the following logical statement: $(P \land \neg Q) \lor (\neg P \rightarrow Q)$. How many rows in its truth table will result in a $\texttt{True}$ value?" answer="3" hint="Construct the full truth table step-by-step and count the True outcomes in the final column." solution="Let's construct the truth table for $(P \land \neg Q) \lor (\neg P \rightarrow Q)$.
First, identify the simple propositions: $P, Q$. Number of rows: $2^2 = 4$.

Step 1: Write down all combinations for $P$ and $Q$.
Step 2: Evaluate $\neg P$ and $\neg Q$.
Step 3: Evaluate $P \land \neg Q$.
Step 4: Evaluate $\neg P \rightarrow Q$.
Step 5: Evaluate the final disjunction $(P \land \neg Q) \lor (\neg P \rightarrow Q)$.

The final column shows $\texttt{True}$ for the first three rows.

Therefore, there are 3 rows that result in a $\texttt{True}$ value.
Answer: $\boxed{3}$"
:::

:::question type="MSQ" question="Which of the following propositions are logically equivalent to $P \rightarrow Q$? Select ALL correct options." options=["$\neg P \lor Q$","$\neg Q \rightarrow \neg P$","$Q \rightarrow P$","$\neg P \land \neg Q$"] answer="$\neg P \lor Q$, $\neg Q \rightarrow \neg P$" hint="Construct truth tables for $P \rightarrow Q$ and each option, then compare the final columns. Remember the definition of contrapositive." solution="Let's first establish the truth table for $P \rightarrow Q$:

Now, let's evaluate each option:

Option 1: $\neg P \lor Q$

Comparing the last column with $P \rightarrow Q$'s column, they are identical. So, $\neg P \lor Q$ is equivalent to $P \rightarrow Q$.

Option 2: $\neg Q \rightarrow \neg P$ (Contrapositive)

Comparing the last column with $P \rightarrow Q$'s column, they are identical. So, $\neg Q \rightarrow \neg P$ is equivalent to $P \rightarrow Q$.

Option 3: $Q \rightarrow P$ (Converse)

The column for $Q \rightarrow P$ is $T, T, F, T$, which is different from $P \rightarrow Q$'s column ($T, F, T, T$). So, $Q \rightarrow P$ is not equivalent to $P \rightarrow Q$.

Option 4: $\neg P \land \neg Q$

The column for $\neg P \land \neg Q$ is $F, F, F, T$, which is different from $P \rightarrow Q$'s column ($T, F, T, T$). So, $\neg P \land \neg Q$ is not equivalent to $P \rightarrow Q$.

The correct options are $\neg P \lor Q$ and $\neg Q \rightarrow \neg P$.
Answer: $\boxed{\neg P \lor Q, \neg Q \rightarrow \neg P}$"
:::

:::question type="SUB" question="Prove using a truth table that the proposition $(P \land Q) \rightarrow (P \lor Q)$ is a tautology." answer="The final column of the truth table for $(P \land Q) \rightarrow (P \lor Q)$ consists entirely of $\texttt{True}$ values, thus proving it is a tautology." hint="Construct the truth table for the given compound proposition step-by-step. If all entries in the final column are 'True', it is a tautology." solution="To prove that $(P \land Q) \rightarrow (P \lor Q)$ is a tautology, we must show that its truth value is always $\texttt{True}$, regardless of the truth values of $P$ and $Q$. We do this by constructing a truth table.

Step 1: List all possible truth value combinations for $P$ and $Q$.

Step 2: Evaluate the conjunction $P \land Q$.

Step 3: Evaluate the disjunction $P \lor Q$.

Step 4: Evaluate the implication $(P \land Q) \rightarrow (P \lor Q)$. An implication $A \rightarrow B$ is false only if $A$ is true and $B$ is false.

The final column of the truth table shows that the proposition $(P \land Q) \rightarrow (P \lor Q)$ is $\texttt{True}$ for all possible truth assignments of $P$ and $Q$. By definition, a proposition that is always true is a tautology. Therefore, $(P \land Q) \rightarrow (P \lor Q)$ is a tautology.
Answer: $\boxed{(P \land Q) \rightarrow (P \lor Q) \text{ is a tautology.}}$"
:::

:::question type="MCQ" question="A $2$-ary boolean function $f(P, Q)$ is defined such that $f(P, Q) = \texttt{True}$ if and only if $P$ is $\texttt{True}$ and $Q$ is $\texttt{False}$. Which of the following logical expressions represents this function?" options=["$P \lor \neg Q$","$P \land \neg Q$","$\neg P \lor Q$","$\neg (P \land Q)$"] answer="$P \land \neg Q$" hint="Construct the truth table based on the given definition and compare it to the truth tables of the options." solution="The function $f(P, Q)$ outputs $\texttt{True}$ if and only if $P$ is $\texttt{True}$ and $Q$ is $\texttt{False}$. Let's construct its truth table:

Now, let's evaluate each option:

$P \lor \neg Q$

This does not match $f(P, Q)$.

$P \land \neg Q$

This matches $f(P, Q)$ exactly.

$\neg P \lor Q$

This does not match $f(P, Q)$.

$\neg (P \land Q)$ (This is NAND)

This does not match $f(P, Q)$.

The only expression that matches the defined function is $P \land \neg Q$.
Answer: $\boxed{P \land \neg Q}$"
:::

---

Summary

---

What's Next?

---

---

Chapter Summary

---

Chapter Review Questions

:::question type="MCQ" question="Which of the following propositions is logically equivalent to $\neg(P \to (\neg Q \land R))$?" options=["$P \land (Q \lor \neg R)$","$P \land (\neg Q \land R)$","$\neg P \lor (Q \land \neg R)$","$\neg P \lor (\neg Q \land R)$"] answer="A" hint="Recall the equivalence $\neg(A \to B) \equiv A \land \neg B$ and De Morgan's Laws for negating conjunctions." solution="We want to find a proposition logically equivalent to $\neg(P \to (\neg Q \land R))$.

First, recall the logical equivalence for the negation of an implication:

Let $A = P$ and $B = (\neg Q \land R)$. Applying this equivalence, we get:

Next, apply De Morgan's Law to negate the conjunction $\neg(\neg Q \land R)$:


Substitute this result back into our expression:

Therefore, the correct option is A.

The final answer is $\boxed{A}$"
:::

:::question type="NAT" question="Consider the compound proposition $(P \lor \neg Q) \land (\neg P \lor R)$. How many rows in its truth table result in a 'True' value?" answer="5" hint="Construct a full truth table for the proposition involving $P, Q, R$. There are $2^3 = 8$ possible truth assignments. Evaluate the compound proposition for each row and count the number of 'True' outcomes." solution="To determine the number of 'True' rows, we construct a truth table for $(P \lor \neg Q) \land (\neg P \lor R)$. Since there are 3 distinct propositional variables ($P, Q, R$), the truth table will have $2^3 = 8$ rows.

| $P$ | $Q$ | $R$ | $\neg Q$ | $P \lor \neg Q$ | $\neg P$ | $\neg P \lor R$ | $(P \lor \neg Q) \land (\neg P \lor R)$ |
|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|
| T | T | T | F | T | F | T | T |
| T | T | F | F | T | F | F | F |
| T | F | T | T | T | F | T | T |
| T | F | F | T | T | F | F | F |
| F | T | T | F | F | T | T | F |
| F | T | F | F | F | T | T | F |
| F | F | T | T | T | T | T | T |
| F | F | F | T | T | T | T | T |

By counting the rows where the final expression $(P \lor \neg Q) \land (\neg P \lor R)$ evaluates to 'True' (highlighted in the last column), we find there are 5 such rows.

The final answer is $\boxed{5}$"
:::

:::question type="MCQ" question="Which of the following propositions is a tautology?" options=["$(P \land Q) \land \neg P$","$(P \lor Q) \leftrightarrow (\neg P \land \neg Q)$","$(P \land (P \to Q)) \to Q$","$(P \lor Q) \land (\neg P \lor \neg Q)$"] answer="C" hint="A tautology is a proposition that is always true, regardless of the truth values of its constituent simple propositions. You can use truth tables or apply logical equivalences to simplify and test each option." solution="Let's analyze each option using logical equivalences:

A. $(P \land Q) \land \neg P$
Using the commutative and associative laws for conjunction, and the contradiction law ($P \land \neg P \equiv F$):

This proposition is a contradiction, as it is always false.

B. $(P \lor Q) \leftrightarrow (\neg P \land \neg Q)$
Recall De Morgan's Law: $\neg P \land \neg Q \equiv \neg(P \lor Q)$.
Substituting this into the proposition:

Let $X = P \lor Q$. Then the proposition becomes $X \leftrightarrow \neg X$.
A biconditional $A \leftrightarrow B$ is true if and only if $A$ and $B$ have the same truth value. Since $X$ and $\neg X$ always have opposite truth values, $X \leftrightarrow \neg X$ is always false.
This proposition is a contradiction.

C. $(P \land (P \to Q)) \to Q$
This is a classic logical argument form known as Modus Ponens, which is a tautology. Let's prove it using logical equivalences:
Recall the equivalence for implication: $P \to Q \equiv \neg P \lor Q$.
Substitute this into the proposition:

Apply the distributive law $A \land (B \lor C) \equiv (A \land B) \lor (A \land C)$:

Since $P \land \neg P \equiv F$:

The identity law for disjunction states $F \lor X \equiv X$:

Now, apply the implication equivalence again:

By De Morgan's Law:

By associativity and commutativity of disjunction:

Since $\neg Q \lor Q \equiv T$:

The domination law for disjunction states $X \lor T \equiv T$:

This proposition is a tautology, as it is always true.

D. $(P \lor Q) \land (\neg P \lor \neg Q)$
This proposition is equivalent to the exclusive OR operation, $P \oplus Q$.
Let's test with a truth assignment:
If $P=T, Q=T$: $(T \lor T) \land (\neg T \lor \neg T) = T \land (F \lor F) = T \land F = F$.
Since it's false for at least one assignment, it is not a tautology.
This proposition is a contingency.

Therefore, option C is the only tautology.

The final answer is $\boxed{C}$"
:::

:::question type="Proof" question="Prove the logical equivalence $(P \land Q) \to R \equiv P \to (Q \to R)$ using a truth table." solution="To prove the logical equivalence $(P \land Q) \to R \equiv P \to (Q \to R)$ using a truth table, we must demonstrate that the columns representing the truth values of both compound propositions are identical for all possible truth assignments of $P, Q, R$. With 3 distinct propositional variables, the truth table will have $2^3 = 8$ rows.

We will construct the truth table step-by-step:

| $P$ | $Q$ | $R$ | $P \land Q$ | $(P \land Q) \to R$ | $Q \to R$ | $P \to (Q \to R)$ |
|:---:|:---:|:---:|:---:|:---:|:---:|:---:|
| T | T | T | T | T | T | T |
| T | T | F | T | F | F | F |
| T | F | T | F | T | T | T |
| T | F | F | F | T | T | T |
| F | T | T | F | T | T | T |
| F | T | F | F | T | F | T |
| F | F | T | F | T | T | T |
| F | F | F | F | T | T | T |

Upon comparing the column for $(P \land Q) \to R$ (column 5) with the column for $P \to (Q \to R)$ (column 7), we observe that their truth values are identical for every single row.

Therefore, the propositions $(P \land Q) \to R$ and $P \to (Q \to R)$ are logically equivalent. This specific equivalence is often referred to as the Exportation Law."
:::

---

What's Next?