MGU Mathematics Series — Discrete Mathematics

Part I: Logic, Sets, and Mathematical Language

Statements · Connectives · Truth Tables · Arguments · Valid Reasoning

Chapter 2 of 14

MGU Mathematics Series · Discrete Mathematics · Library Textbook Edition

Chapter 2:
Logic and Truth

Statements, truth values, negation, conjunction, disjunction, conditionals, contrapositive, truth tables, logical equivalence, tautologies, and valid arguments — the grammar of mathematical reasoning

■ Part I: Logic, Sets, and Mathematical Language ■

■ 14 Sections • Chapter 2 of 14 ■

Follows Chapter 1: What Discrete Mathematics Studies · Prepares students for Chapter 3: Sets, Quantifiers, and Relations

Chapter 2 — Front Matter

Purpose and Overview

This chapter introduces formal logic as the mathematical study of statements, truth, and valid reasoning. Logic is not simply a matter of opinion or persuasion. In mathematics, a statement either must be true or must be false, and the tools of logic allow us to judge that question precisely — based not on feeling, but on structure.

Every field of careful reasoning depends on logic. Mathematicians use logic to write proofs. Programmers use logic to write conditions, filters, and decision structures. Engineers use logic to design digital circuits. Security analysts use logic to formalize access rules. The habits of mind introduced in this chapter will support everything that follows in this textbook.

Opening Question

"If it is raining, then the ground is wet."

"If the ground is wet, then it is raining."

Are these saying the same thing? Most people sense that something is different, but struggle to explain exactly what. By the end of this chapter, you will be able to state the difference precisely, prove that the two statements are logically distinct, and explain what it would take for each one to be false.

14Sections

10Objectives

24Key Terms

15+Worked Examples

Why This Chapter Matters

Mathematics depends on making claims that are either true or false, and then reasoning from those claims to conclusions. If you cannot tell whether a mathematical statement is well-formed, you cannot evaluate it. If you cannot distinguish between a statement and its converse, you may accept false conclusions. If you cannot recognize a valid argument, you may be fooled by one that sounds convincing but is logically broken.

Logic is the grammar of mathematical reasoning. Just as mastering grammar does not teach you everything you need to write well, mastering logic does not by itself make you a mathematician. But without it, careful reasoning is impossible.

Learning Objectives

1Identify statements and determine their truth values.
2Construct negations of statements correctly.
3Evaluate conjunctions, disjunctions, and conditional statements using truth tables.
4Identify the converse, inverse, and contrapositive of a conditional statement.
5Construct and interpret biconditional statements.
6Build truth tables for compound logical expressions.
7Determine whether two logical expressions are logically equivalent.
8Identify tautologies and contradictions.
9Evaluate whether a logical argument is valid or invalid.
10Recognize how logic appears in programming, search queries, and digital circuits.

Chapter 2 — Contents

Sections at a Glance

2.1What Logic StudiesReasoning, structure vs. content, propositional logic, why form matters more than subject matter
2.2Statements and Truth ValuesPropositions, truth values T and F, simple vs. compound statements, what is not a statement
2.3Negation¬p, reversing truth values, negating universal and existential claims, common negation errors
2.4Conjunction and Disjunctionp ∧ q, p ∨ q, inclusive or, truth tables for both connectives, real-world examples
2.5Conditional Statementsp → q, hypothesis, conclusion, vacuously true cases, multiple English phrasings of a conditional
2.6Converse, Inverse, and ContrapositiveDefinitions of all three, logical equivalence of conditional and contrapositive, the converse fallacy
2.7Biconditional Statementsp ↔ q, "if and only if," truth table, connection to proving both directions
2.8Truth TablesBuilding multi-column truth tables, operator precedence, three-variable tables, step-by-step method
2.9Logical EquivalenceP ≡ Q, De Morgan's Laws, conditional as disjunction, contrapositive equivalence, key equivalences
2.10Tautologies and ContradictionsDefinitions, Law of Excluded Middle, Law of Non-Contradiction, contingencies
2.11Valid and Invalid ArgumentsModus ponens, modus tollens, hypothetical syllogism, disjunctive syllogism, affirming the conclusion, denying the hypothesis
2.12Logic in Programming and Digital SystemsAND/OR/NOT in code, Boolean search queries, logic gates as connectives, bridge to Chapter 13
2.13Common Logic MistakesSeven recurring errors with explanations and prevention strategies
2.14Preparing for Quantifiers and ProofPreview of predicate logic, preview of proof methods, bridge to Chapters 3 and 4

Section 2.1

What Logic Studies

Logic is the study of reasoning. More precisely, it is the mathematical study of what follows from what — of when conclusions can be trusted to be true given that certain starting claims are true.

Ordinary conversation is full of informal reasoning. We say things like: "It must be broken — the light is off." Or: "If traffic is bad, I'll be late." These are examples of logical reasoning. But in ordinary conversation, people often accept reasoning that sounds plausible without checking whether it actually holds up. Mathematical logic provides a framework for analyzing the structure of reasoning independent of subject matter.

The central insight of mathematical logic is that what matters is not the particular topic — whether we are talking about rain, traffic, numbers, or circuits — but the form of the reasoning. A valid argument is valid because of its form, not because of its content.

In this chapter, we study propositional logic, which is the logic of statements that can be judged true or false. This is the most fundamental level of formal logic, and it underlies all of the proof techniques, set theory, algorithm analysis, and Boolean algebra that appear in later chapters.

Section 2.2

Statements and Truth Values

What Is a Statement?

A statement (also called a proposition) is a declarative sentence that has a definite truth value — it is either true or false, not both, and not neither.

Sentence	Is it a Statement?	Reason
"Seven is a prime number."	Yes — True	Has a definite truth value
"The sum of two even integers is odd."	Yes — False	Has a definite truth value
"Is seven a prime number?"	No	A question, not a declarative sentence
"Please study logic."	No	A command, not a statement
"This sentence is false."	No	A paradox — no consistent truth value
`x + 3 = 7`	Not yet	An open sentence — depends on x (handled later with quantifiers)

Definition — Statement and Truth Value

A statement is a declarative sentence that is either true or false, but not both. The truth value of a statement is T (true) or F (false).

We use lowercase letters — most often p, q, and r — to represent simple statements. A compound statement is formed by combining two or more simple statements using logical connectives such as "and," "or," "not," and "if…then."

Student Note

Statements in logic are more restricted than sentences in everyday language. A sentence like "That movie was amazing" is not a formal statement, because "amazing" is subjective. Logic requires statements with clear, determinate truth values.

Practice 2.2Identifying Statements

For each sentence, state whether it is a statement. If it is, give its truth value.

a. "Every integer is either even or odd."
b. "Stop and think carefully."
c. "What is 15 + 27?"
d. "The number 91 is prime."
e. "x² = 25."
f. "There are infinitely many prime numbers."
Explain in your own words why "x + 5 > 10" is not a statement on its own, but can become one.

Section 2.3

Negation

Definition — Negation

The negation of a statement p, written ¬p (read "not p"), is the statement that is true when p is false, and false when p is true.

p	¬p
T	F
F	T

Example 2.3.1

Negating a simple statement

ProblemLet p = "The number 15 is prime." Write the negation ¬p in plain English.
ThinkThe negation should be a statement that is true precisely when p is false. It is not simply inserting "not" anywhere — it is the statement with the opposite truth value.
SolveSince p says "15 is prime," its negation says "15 is not prime."
CheckIf 15 is prime, then p is true and ¬p is false. If 15 is not prime, then p is false and ¬p is true. This matches the definition. ✓

Answer: ¬p — "The number 15 is not prime."

Example 2.3.2

Negation requires care — universal statements

ProblemLet q = "All integers are positive." Write ¬q.
ThinkThe negation of "all integers are positive" is not "all integers are negative." The negation of a universal claim is an existential claim: it says there is at least one counterexample.
Solve¬q: "There exists an integer that is not positive."
CheckIf there is even one non-positive integer (such as −1 or 0), then q is false and ¬q is true. ✓

Answer: ¬q — "Not all integers are positive" (equivalently, "There exists an integer that is not positive.")

Student Warning — Negating Universal Statements

The negation of "All A are B" is not "All A are not B." It is "Some A are not B" — or equivalently, "There exists at least one A that is not B." We will develop this more fully in Chapter 3 when we study quantifiers.

Practice 2.3Negation Practice

Write the negation of each statement in plain English. Then determine whether the original or the negation is true.

a. "The number 4 is odd."
b. "All prime numbers are odd."
c. "Some even numbers are divisible by 3."
d. "No integer is between 0 and 1."
e. "The product of two negative numbers is always negative."

Section 2.4

Conjunction and Disjunction

Conjunction — "and"

Definition — Conjunction

The conjunction of statements p and q, written p ∧ q (read "p and q"), is the compound statement that is true when both p and q are true, and false otherwise.

p	q	p ∧ q
T	T	T
T	F	F
F	T	F
F	F	F

Disjunction — "or"

Definition — Disjunction

The disjunction of statements p and q, written p ∨ q (read "p or q"), is the compound statement that is true when at least one of p or q is true, and false only when both are false.

p	q	p ∨ q
T	T	T
T	F	T
F	T	T
F	F	F

Inclusive Or

In everyday English, "or" is sometimes exclusive ("you can have soup or salad, not both"). In mathematics and logic, "or" is inclusive: p ∨ q is true when both p and q are true. This is the standard logical interpretation unless otherwise specified.

Example 2.4.1

Evaluating a conjunction

ProblemLet p = "8 is even" and q = "8 is prime." Evaluate p ∧ q.
ThinkDetermine the truth value of each component, then apply the conjunction rule.
Solve p: "8 is even" — True (8 = 2 × 4) q: "8 is prime" — False (8 = 2 × 4, so it has divisors other than 1 and itself) Since q is false, p ∧ q is false.
CheckConjunction is true only when both parts are true. One part is false, so the result is correctly false. ✓

Answer: p ∧ q is FALSE.

Example 2.4.2

Evaluating a disjunction

ProblemWith p and q as above, evaluate p ∨ q.
ThinkDisjunction is true when at least one part is true.
Solvep is true; q is false. Since at least one component is true, p ∨ q is true.

Answer: p ∨ q is TRUE.

Example 2.4.3

Forming a compound statement from context

ProblemLet p = "The file exists" and q = "The file is readable." Write "The file exists and the file is readable" in symbols and determine when it is false.
SolveThe compound statement is p ∧ q. It is false whenever either the file does not exist or the file is not readable — that is, whenever at least one component is false.

Answer: p ∧ q; it is false whenever p is false, whenever q is false, or whenever both are false.

MGU Library Connection

This type of compound condition appears directly in programming and database queries. A condition like (file_exists AND file_readable) uses exactly this conjunction logic. See the MGU Computer Science pages for examples of Boolean conditions in code.

Practice 2.4Conjunction and Disjunction

Let p = "12 is divisible by 4" and q = "12 is divisible by 5." Evaluate p ∧ q and p ∨ q.
Let p = "−3 is negative" and q = "−3 is an integer." Evaluate p ∧ q and p ∨ q.
Write in symbols: "The server is online and the database is responding."
Write in symbols: "The account is locked or the password is expired."
In how many of the four possible truth-value assignments for p and q is p ∧ q true? Is p ∨ q true?
Give an example of two true statements p and q where p ∧ q is true. Give an example where p ∨ q is true but p ∧ q is false.

Section 2.5

Conditional Statements

Definition — Conditional Statement

The conditional statement formed from statements p and q, written p → q (read "if p, then q"), is the compound statement that is false only when p is true and q is false. In all other cases, it is true. The statement p is called the hypothesis and q is called the conclusion.

p	q	p → q
T	T	T
T	F	F
F	T	T
F	F	T

Why Is the Conditional True When p Is False?

This surprises most students. When p is false, p → q is true regardless of q. This is called the vacuously true case. Think of it this way: if I promise "If you complete all the exercises, I will give you full credit," my promise is only broken if you complete all the exercises and I fail to give you credit. If you do not complete the exercises, I have made no promise about what happens — so I cannot be said to have broken the promise. The conditional is vacuously satisfied.

More formally: p → q asserts that the hypothesis p being true is sufficient to guarantee that q is true. If p is false, no such guarantee is required.

Ways to Read a Conditional

The statement p → q can be expressed many ways in English. Learning to recognize all of these forms is important for reading mathematical theorems.

Phrasing	Example with p = "n is even" and q = "n² is even"
"If p, then q."	"If n is even, then n² is even."
"p implies q."	"n is even implies n² is even."
"p only if q."	"n is even only if n² is even."
"q if p."	"n² is even if n is even."
"q whenever p."	"n² is even whenever n is even."
"p is sufficient for q."	"Being even is sufficient for n² to be even."
"q is necessary for p."	"n² being even is necessary for n to be even."

Example 2.5.1

Evaluating a conditional — the false case

ProblemLet p = "It is snowing" and q = "School is cancelled." Evaluate p → q for the case where it is snowing but school is not cancelled.
ThinkIdentify which row of the truth table applies: p is true, q is false.
SolveRow 2 of the truth table: p = T, q = F. The conditional p → q is FALSE.
CheckThis is the only case where the conditional fails — the hypothesis was true but the conclusion did not hold. ✓

Answer: p → q is FALSE. This is the only case that makes a conditional false.

Example 2.5.2

The vacuously true case

ProblemA theorem states: "If n is divisible by 6, then n is divisible by 3." Consider the case n = 5. Is the conditional true or false?
ThinkSince 5 is not divisible by 6, the hypothesis p is false. A false hypothesis makes the conditional vacuously true.
Solvep: "5 is divisible by 6" — False. Therefore, p → q is vacuously TRUE, regardless of whether 5 is divisible by 3.
CheckWe are not claiming anything about 5 being divisible by 3. The theorem makes no claim about numbers that are not divisible by 6. ✓

Answer: The conditional is TRUE (vacuously). The theorem does not make any claim about numbers not divisible by 6.

Student Warning — Vacuous Truth

Many students find it strange that a conditional with a false hypothesis is true. But consider: if the conditional were false in this case, that would mean we had identified a counterexample — and we have not. The only counterexample to "if p then q" is a situation where p is true and q is false.

Practice 2.5Conditional Statements

Let p = "The temperature is below 0°C" and q = "Water freezes." Write p → q in three different English phrasings.
For each case, determine the truth value of p → q.

a. p = T, q = T b. p = T, q = F c. p = F, q = T d. p = F, q = F
Let p = "n is divisible by 9" and q = "n is divisible by 3." The conditional p → q is true. Is the converse q → p also true? Give a counterexample if not.
Explain in your own words why the conditional "If 5 is even, then 5 is divisible by 10" is a true statement, even though 5 is not even.

Section 2.6

Converse, Inverse, and Contrapositive

Given a conditional p → q, there are three related statements formed by rearranging or negating the parts. Understanding how these relate to each other — and whether they share the same truth value — is essential for writing correct proofs.

Name	Symbolic Form	In Words (given "If p, then q")
Original	p → q	"If p, then q."
Converse	q → p	"If q, then p."
Inverse	¬p → ¬q	"If not p, then not q."
Contrapositive	¬q → ¬p	"If not q, then not p."

Key Equivalence Result

A conditional statement and its contrapositive are logically equivalent. The converse and the inverse are logically equivalent to each other — but not to the original conditional (in general).

p → q ≡ ¬q → ¬p (conditional and contrapositive agree)

q → p ≡ ¬p → ¬q (converse and inverse agree)

Example 2.6.1

Writing all four forms

ProblemLet p = "The integer n is even" and q = "The integer n² is even." Write the conditional, its converse, its inverse, and its contrapositive.
Solve Conditional: "If n is even, then n² is even." Converse: "If n² is even, then n is even." Inverse: "If n is not even, then n² is not even." Contrapositive: "If n² is not even, then n is not even."
CheckThe conditional and contrapositive should have the same truth value. In this case, both are true. The converse and inverse are also both true here — but this is not always the case.

Answer: See forms above. All four happen to be true in this example, but the conditional and contrapositive are always logically equivalent regardless.

Example 2.6.2

When the conditional and converse differ

ProblemConsider: "If a number is divisible by 4, then it is divisible by 2." Write the converse and determine whether it is true.
Solve Original: "If n is divisible by 4, then n is divisible by 2." — TRUE Converse: "If n is divisible by 2, then n is divisible by 4." — FALSE
CheckCounterexample for the converse: n = 6. Here 6 is divisible by 2 but not by 4. So the converse is false. ✓

Answer: The converse is FALSE. A counterexample is n = 6.

Student Warning — One of the Most Important Distinctions in Mathematics

Proving p → q does NOT prove q → p. These are logically distinct statements. Many errors in reasoning come from accidentally treating a conditional and its converse as equivalent. They are not. You must prove each direction separately.

Practice 2.6Converse, Inverse, Contrapositive

For each conditional, write the converse, inverse, and contrapositive. Then determine which forms are true and which are false.

a. "If n is divisible by 10, then n is divisible by 5."
b. "If a quadrilateral is a square, then it is a rectangle."
c. "If it is raining, then I carry an umbrella."
A student writes: "We proved that if p, then q. Therefore if q, then p." Explain the error.
If p → q is false, what are the truth values of p and q? What can you say about ¬q → ¬p?

Section 2.7

Biconditional Statements

Definition — Biconditional

The biconditional of statements p and q, written p ↔ q (read "p if and only if q"), is the compound statement that is true when p and q have the same truth value, and false when they have different truth values. The biconditional p ↔ q is logically equivalent to (p → q) ∧ (q → p).

p	q	p ↔ q
T	T	T
T	F	F
F	T	F
F	F	T

"If and Only If"

In mathematics, the phrase "if and only if" (often abbreviated iff) always signals a biconditional. When a theorem states p if and only if q, it is claiming two things simultaneously: (1) p → q, and (2) q → p. Proving a biconditional therefore typically requires proving both directions separately.

Example 2.7.1

A true biconditional

ProblemLet p = "A triangle has three equal sides" and q = "A triangle has three equal angles." Evaluate p ↔ q.
ThinkA triangle has three equal sides if and only if it has three equal angles (the definition of an equilateral triangle). Both p and q are true for equilateral triangles and false otherwise — they always share the same truth value.
SolveSince p and q always have the same truth value, p ↔ q is TRUE.

Answer: p ↔ q is TRUE. This biconditional holds for all triangles.

Example 2.7.2

A false biconditional

ProblemLet p = "n is divisible by 4" and q = "n is divisible by 2." Evaluate p ↔ q for n = 6.
Solve p: "6 is divisible by 4" — FALSE q: "6 is divisible by 2" — TRUE p and q have different truth values, so p ↔ q is FALSE.

Answer: The biconditional is FALSE for n = 6. Divisibility by 4 and divisibility by 2 are not equivalent conditions.

Practice 2.7Biconditional Statements

Determine whether each biconditional is true or false. Explain your reasoning.

a. "An integer is even if and only if it is divisible by 2."
b. "A number is positive if and only if it is greater than zero."
c. "An integer n satisfies n² = 4 if and only if n = 2."
Write two true biconditional statements using mathematical concepts from Algebra II.
Explain why proving a biconditional p ↔ q requires proving two separate conditionals.

Section 2.8

Truth Tables

We now develop truth tables as a systematic method for evaluating the truth value of any compound logical expression for every possible combination of truth values of its component statements.

Building a Truth Table — Procedure

Step 1. Count the distinct simple statement variables. If there are n variables, the table has 2ⁿ rows.

Step 2. List all combinations of truth values for the variables.

Step 3. Evaluate the expression column by column, following operator precedence:

¬ (highest) → ∧ → ∨ → → → ↔ (lowest)

Use parentheses to override this order, just as in algebra.

Example 2.8.1

Truth table for a compound statement

ProblemBuild a truth table for (p ∧ q) → ¬p.
ThinkTwo variables → 4 rows. Evaluate p ∧ q first, then ¬p, then the full conditional.
Solve

p q p ∧ q ¬p (p ∧ q) → ¬p

T T T F F

T F F F T

F T F T T

F F F T T
CheckThe conditional is false only in row 1, where the hypothesis p ∧ q is true and the conclusion ¬p is false. All other rows correctly show true. ✓

p	q	p ∧ q	¬p	(p ∧ q) → ¬p
T	T	T	F	F
T	F	F	F	T
F	T	F	T	T
F	F	F	T	T

Answer: The expression is false only when both p and q are true.

Example 2.8.2

Verifying that a conditional and its contrapositive are equivalent

ProblemBuild a truth table with columns for p → q and ¬q → ¬p. Compare the columns.
Solve

p q ¬p ¬q p → q ¬q → ¬p

T T F F T T

T F F T F F

F T T F T T

F F T T T T
CheckThe two highlighted columns are identical in every row. ✓

p	q	¬p	¬q	p → q	¬q → ¬p
T	T	F	F	T	T
T	F	F	T	F	F
F	T	T	F	T	T
F	F	T	T	T	T

Answer: A conditional and its contrapositive always have the same truth value — they are logically equivalent.

Example 2.8.3

A three-variable truth table

ProblemBuild a truth table for p → (q ∨ r).
ThinkThree variables require 2³ = 8 rows.

Solve

p	q	r	q ∨ r	p → (q ∨ r)
T	T	T	T	T
T	T	F	T	T
T	F	T	T	T
T	F	F	F	F
F	T	T	T	T
F	T	F	T	T
F	F	T	T	T
F	F	F	F	T

Answer: The expression is false only in row 4, where p is true but both q and r are false.

Practice 2.8Truth Table Practice

Build a complete truth table for each expression.

¬p ∨ q
p → ¬q
¬(p ∨ q)
¬p ∧ ¬q
(p → q) ∧ (q → p)
p ↔ ¬p
(p ∧ q) ∨ r
p → (q → r)

Section 2.9

Logical Equivalence

Definition — Logical Equivalence

Two compound statements are logically equivalent if they have identical truth values in every row of their truth tables. We write P ≡ Q to indicate that expressions P and Q are logically equivalent.

Key Logical Equivalences

Double Negation¬(¬p) ≡ p
De Morgan — AND¬(p ∧ q) ≡ ¬p ∨ ¬q
De Morgan — OR¬(p ∨ q) ≡ ¬p ∧ ¬q
Commutative (∧)p ∧ q ≡ q ∧ p
Commutative (∨)p ∨ q ≡ q ∨ p
Distributivep ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
Conditionalp → q ≡ ¬p ∨ q
Contrapositivep → q ≡ ¬q → ¬p

Example 2.9.1

Verifying De Morgan's First Law

ProblemVerify that ¬(p ∧ q) ≡ ¬p ∨ ¬q using a truth table.
Solve

p q p ∧ q ¬(p ∧ q) ¬p ¬q ¬p ∨ ¬q

T T T F F F F

T F F T F T T

F T F T T F T

F F F T T T T
CheckThe two highlighted columns are identical in every row. ✓

p	q	p ∧ q	¬(p ∧ q)	¬p	¬q	¬p ∨ ¬q
T	T	T	F	F	F	F
T	F	F	T	F	T	T
F	T	F	T	T	F	T
F	F	F	T	T	T	T

Answer: De Morgan's first law is verified. ¬(p ∧ q) ≡ ¬p ∨ ¬q.

How to Apply De Morgan's Laws

To negate a conjunction: change "and" to "or" and negate each part. To negate a disjunction: change "or" to "and" and negate each part. The most common error is negating the parts without changing the connective.

Example 2.9.2

Negating a compound statement using De Morgan's Law

ProblemLet p = "The system has power" and q = "The network is connected." Negate the compound statement p ∧ q.
Solve ¬(p ∧ q) ≡ ¬p ∨ ¬q In plain English: "The system does not have power, or the network is not connected (or both)."

Answer: "The system does not have power, or the network is not connected."

Example 2.9.3

Applying the conditional equivalence

ProblemRewrite "If it is raining, then I carry an umbrella" using only negation and disjunction.
SolveUsing the equivalence p → q ≡ ¬p ∨ q:

"Either it is not raining, or I carry an umbrella."

Answer: p → q ≡ ¬p ∨ q. This rewriting is frequently used in proofs and circuit design.

Practice 2.9Logical Equivalence Practice

For each pair, determine whether the two expressions are logically equivalent. Show your work.

¬(p ∨ q) and ¬p ∧ ¬q
p → q and ¬p ∨ q
p → q and q → p
p → q and ¬q → ¬p
¬(p → q) and p ∧ ¬q
p ↔ q and (p → q) ∧ (q → p)

Section 2.10

Tautologies and Contradictions

Definitions — Tautology and Contradiction

A tautology is a compound statement that is true for every possible assignment of truth values to its component statements.

A contradiction is a compound statement that is false for every possible assignment of truth values to its component statements.

A compound statement that is neither is called a contingency — its truth value depends on the truth values of its components.

Example 2.10.1

A tautology — the Law of Excluded Middle

ProblemShow that p ∨ ¬p is a tautology.
Solve

p ¬p p ∨ ¬p

T F T

F T T

p	¬p	p ∨ ¬p
T	F	T
F	T	T

Answer: p ∨ ¬p is true in every row — it is a tautology. This is the Law of Excluded Middle: every statement is either true or false.

Example 2.10.2

A contradiction — the Law of Non-Contradiction

ProblemShow that p ∧ ¬p is a contradiction.
Solve

p ¬p p ∧ ¬p

T F F

F T F

p	¬p	p ∧ ¬p
T	F	F
F	T	F

Answer: p ∧ ¬p is false in every row — it is a contradiction. No statement can be both true and false simultaneously.

Example 2.10.3

A useful tautology

ProblemShow that (p → q) ↔ (¬q → ¬p) is a tautology.
Solve

p q p → q ¬q → ¬p (p → q) ↔ (¬q → ¬p)

T T T T T

T F F F T

F T T T T

F F T T T

Answer: The biconditional is true in every row — it is a tautology, confirming that a conditional and its contrapositive are always logically equivalent.

Practice 2.10Tautologies and Contradictions

For each expression, determine whether it is a tautology, a contradiction, or a contingency. Show a truth table.

p ∨ ¬p
p ∧ ¬p
(p → q) ∨ (q → p)
p ↔ ¬p
(p ∧ q) → p
¬(p ∨ q) ∧ p

Section 2.11

Valid and Invalid Arguments

Definitions — Argument and Validity

An argument is a sequence of statements in which some (called premises) are used to support a final statement (called the conclusion).

An argument is valid if, whenever all premises are true, the conclusion must also be true. An argument is invalid (a fallacy) if it is possible for all premises to be true and the conclusion to be false.

Validity Is About Form, Not Fact

An argument can be valid even if its premises are false in the real world. Validity is about the structure of the reasoning, not the factual truth of the claims. Conversely, an argument with true premises and a true conclusion can still be invalid if the reasoning is flawed.

Common Valid Argument Forms

Modus Ponens — Affirming the Hypothesis

Premise 1: p → q

Premise 2: p

∴ q

Modus Tollens — Denying the Conclusion

Premise 1: p → q

Premise 2: ¬q

∴ ¬p

Hypothetical Syllogism — Chain Rule

Premise 1: p → q

Premise 2: q → r

∴ p → r

Disjunctive Syllogism

Premise 1: p ∨ q

Premise 2: ¬p

∴ q

Common Invalid Argument Forms — Fallacies

Affirming the Conclusion — INVALID (Converse Fallacy)

Premise 1: p → q

Premise 2: q

∴ p ✗ FALLACY

Denying the Hypothesis — INVALID (Inverse Fallacy)

Premise 1: p → q

Premise 2: ¬p

∴ ¬q ✗ FALLACY

Example 2.11.1

Modus Ponens — a valid argument

ProblemEvaluate: "If a number is divisible by 10, then it is divisible by 5. 80 is divisible by 10. Therefore, 80 is divisible by 5."
ThinkLet p = "the number is divisible by 10" and q = "the number is divisible by 5." Identify the argument form.
SolvePremise 1: p → q. Premise 2: p. Conclusion: q. This is modus ponens — a valid argument form.

Answer: The argument is VALID. (The conclusion is also true as a matter of fact.)

Example 2.11.2

Affirming the Conclusion — an invalid argument

ProblemEvaluate: "If it is raining, then the ground is wet. The ground is wet. Therefore, it is raining."
ThinkLet p = "it is raining" and q = "the ground is wet." The form is p → q, q, ∴ p.
SolveThis is affirming the conclusion — a fallacy. The ground could be wet because a sprinkler ran, not rain. Even if both premises are true, the conclusion does not necessarily follow.
CheckSuppose a sprinkler ran. Then p is false and q is true. The premises are both satisfied, but the conclusion p is false. This is a counterexample to the argument's validity. ✓

Answer: The argument is INVALID.

Example 2.11.3

Modus Tollens — a valid argument

ProblemEvaluate: "If a number is prime, then it has exactly two positive divisors. 9 does not have exactly two positive divisors. Therefore, 9 is not prime."
Solve Premise 1: p → q Premise 2: ¬q Conclusion: ¬p → This is modus tollens — VALID.

Answer: VALID. (9 = 3 × 3, so 9 is correctly identified as not prime.)

Example 2.11.4

Verifying validity with a truth table

ProblemUse a truth table to verify modus ponens: if (p → q) ∧ p is true, then q must be true.
Solve

p q p → q (p → q) ∧ p q

T T T T T

T F F F F

F T T F T

F F T F F
CheckThe only row where (p → q) ∧ p is true is row 1 — and there, q is also true. There is no row where the hypothesis is true and the conclusion is false. ✓

Answer: Modus ponens is a VALID argument form.

Practice 2.11Argument Analysis

For each argument, identify the form and determine whether it is valid or invalid. Justify your answer.

Premise 1: If a polygon has four sides, then it is a quadrilateral. Premise 2: This polygon has four sides. Conclusion: This polygon is a quadrilateral.
Premise 1: If the code compiles, then there are no syntax errors. Premise 2: There are no syntax errors. Conclusion: The code compiles.
Premise 1: If n is odd, then n² is odd. Premise 2: n² is not odd. Conclusion: n is not odd.
Premise 1: If a triangle is equilateral, then it is equiangular. Premise 2: This triangle is not equilateral. Conclusion: This triangle is not equiangular.
Premise 1: If it is after midnight, the server backs up. Premise 2: If the server backs up, the log is written. Conclusion: If it is after midnight, the log is written.

Section 2.12

Logic in Programming and Digital Systems

The logical connectives studied in this chapter are not only abstract mathematical tools — they appear directly in the systems that power computing.

Logic in Programming

Logic	Symbol	Programming
Conjunction	p ∧ q	`p AND q` or `p && q`
Disjunction	p ∨ q	`p OR q` or `p \|\| q`
Negation	¬p	`NOT p` or `!p`

A login system might use a conjunction: access is granted only when both conditions are true.

IF (username_valid AND password_correct) THEN
    grant_access
END IF

A filter using disjunction accepts items meeting at least one criterion:

IF (item_in_stock OR pre_order_available) THEN
    show_item
END IF

A guard condition using negation:

IF NOT (account_locked) THEN
    allow_login_attempt
END IF

Logic in Search

Search engines and databases evaluate logical queries. A search like (mathematics AND discrete) NOT calculus returns documents containing both "mathematics" and "discrete" but not "calculus." This is exactly a conjunction combined with a negation.

Logic in Digital Circuits

Digital circuits are built from logic gates — physical components that implement the basic logical operations. An AND gate takes two inputs and produces an output that is high (1) only when both inputs are high. An OR gate produces a high output when at least one input is high. A NOT gate inverts its input. We will develop Boolean algebra and circuits in full in Chapter 13.

MGU Library Connection

MGU Computer Science pages — conditional statements and Boolean logic
MGU Cybersecurity pages — logical conditions in access control rules and firewall policies
Chapter 13 of this textbook — Boolean Algebra, Circuits, and Digital Logic
Appendix C — Logic Laws Reference

Practice 2.12Programming and Circuit Applications

A search database uses: (topic = "logic") AND (level = "introductory" OR level = "intermediate"). Let p = "topic is logic," q = "level is introductory," r = "level is intermediate." Write the condition as a logical expression and describe exactly when a document satisfies it.
An access control system grants access if a user has an active account AND (has administrator rights OR has been explicitly granted permission). Let a = "active account," m = "administrator rights," g = "explicitly granted." Write the expression and evaluate it when a = T, m = F, g = T.
A system denies access if the account is locked OR too many failed attempts have occurred. Let L = "account locked," F = "too many failed attempts." Write the expression for denying access. Then write the expression for allowing access using De Morgan's Law.
A digital AND gate outputs 1 only when both inputs are 1. Describe the output for: (a) inputs 1, 1; (b) inputs 1, 0; (c) inputs 0, 0. Which row of the conjunction truth table does each correspond to?

Section 2.13

Common Logic Mistakes

Mistake 1 — Confusing a Conditional with Its Converse

"If I study, I will pass. I passed. Therefore I studied."

This is the converse fallacy (affirming the conclusion). Proving p → q does NOT prove q → p. There may be other reasons for passing.

The conditional and its converse are not equivalent. You must prove each direction separately.

Mistake 2 — Treating "or" as Exclusive

"p or q is true, so at most one of them can be true."

In mathematics, "or" is inclusive. p ∨ q is true when both p and q are true. Exclusive or is a separate connective and must be explicitly specified.

Mistake 3 — Treating a False Hypothesis as a Problem

"The hypothesis of the conditional is false, so the conditional has no truth value."

A conditional with a false hypothesis is vacuously TRUE. A conditional only makes a claim about what happens when p is true. If p is false, no claim is violated.

Mistake 4 — Negating "All" as "None"

The negation of "All integers are positive" is "No integers are positive."

The negation of "All A are B" is "Some A are not B" — at least one counterexample exists. "None" is a much stronger claim that is not automatically entailed by the negation.

Mistake 5 — Applying De Morgan's Law Without Changing the Connective

¬(p ∧ q) = ¬p ∧ ¬q

¬(p ∧ q) ≡ ¬p ∨ ¬q. De Morgan's laws require changing the connective: "and" becomes "or," and "or" becomes "and."

Mistake 6 — Assuming Validity Guarantees True Conclusions

"The argument is valid, so the conclusion must be true."

A valid argument produces a true conclusion only if the premises are true. If premises are false, the conclusion may be false — but the argument is still valid by structure. Validity concerns form, not factual truth.

Mistake 7 — Confusing Logical Equivalence with Equality

"P ≡ Q, so they are equal expressions."

Logical equivalence (P ≡ Q) means the two expressions have the same truth value in every possible case. This is a relationship between logical expressions, not algebraic equality between numbers.

Section 2.14

Preparing for Quantifiers and Proof

Chapter 2 has built the foundation of formal logical reasoning. The next two chapters extend this foundation in two directions.

Chapter 3 introduces quantifiers — the logical tools that handle statements about "all" objects or "some" objects in a set. Quantifiers extend propositional logic to predicate logic, which is needed for formal mathematics, database queries, and program verification.

Chapter 4 introduces mathematical proof — the disciplined application of logic to establish that mathematical claims must be true. Proof methods such as direct proof, proof by contrapositive, and proof by contradiction are direct applications of the logical tools built here. Every major proof technique in Chapter 4 is a logical argument: it uses premises to reach a conclusion by valid inference. Without the foundation of this chapter, proof is impossible to do rigorously.

Practice 2.14Readiness Check

Write the contrapositive of: "If a program terminates, then it produces an output." Is the contrapositive logically equivalent to the original? Explain why.
A theorem states: p if and only if q. What two conditionals must be proved separately? Why is this more work than proving just p → q?
Give an example of a valid argument with false premises and a false conclusion. Explain why the argument is still valid.
You want to prove "If n is odd, then n² is odd." Which proof method from Chapter 4 could you use instead of a direct proof? State the equivalent claim you would prove.

Chapter 2 — Back Matter

Chapter Summary

Sec 2.1Logic is the mathematical study of reasoning. Propositional logic studies statements that can be judged true or false, and evaluates arguments based on their form rather than their subject matter.
Sec 2.2A statement is a declarative sentence with a definite truth value (T or F). Questions, commands, and paradoxes are not statements. Simple statements are represented by letters p, q, r. Compound statements combine simple ones using connectives.
Sec 2.3Negation (¬p) reverses the truth value of a statement. Negating a universal claim ("all") produces an existential claim ("at least one is not"), not a total reversal.
Sec 2.4Conjunction (p ∧ q) is true only when both parts are true. Disjunction (p ∨ q) is true when at least one part is true. "Or" in logic is inclusive — it includes the case where both parts are true.
Sec 2.5A conditional (p → q) is false only when the hypothesis p is true and the conclusion q is false. It is vacuously true whenever the hypothesis is false. The conditional has many English phrasings including "if p then q," "p only if q," and "p is sufficient for q."
Sec 2.6The converse (q → p), inverse (¬p → ¬q), and contrapositive (¬q → ¬p) are formed from a conditional. A conditional and its contrapositive are always logically equivalent. The converse and inverse are equivalent to each other, but not to the original conditional.
Sec 2.7The biconditional (p ↔ q) is true when p and q have the same truth value. "If and only if" (iff) signals a biconditional. Proving a biconditional requires proving both p → q and q → p.
Sec 2.8Truth tables evaluate compound expressions for every combination of truth values. With n variables, the table has 2ⁿ rows. Columns are evaluated using operator precedence: ¬, then ∧, then ∨, then →, then ↔.
Sec 2.9Two expressions are logically equivalent (P ≡ Q) if their truth tables are identical. Key equivalences include De Morgan's Laws (negating ∧ yields ∨ and vice versa) and the conditional rewriting p → q ≡ ¬p ∨ q.
Sec 2.10A tautology is true in every row; a contradiction is false in every row. The Law of Excluded Middle (p ∨ ¬p) is a tautology. The Law of Non-Contradiction (p ∧ ¬p) is a contradiction.
Sec 2.11A valid argument makes it impossible for all premises to be true and the conclusion false. Common valid forms: modus ponens, modus tollens, hypothetical syllogism, disjunctive syllogism. Common fallacies: affirming the conclusion, denying the hypothesis.
Sec 2.12Logical connectives appear directly in programming conditions (AND, OR, NOT), database search queries, and digital logic gates. Chapter 13 develops Boolean algebra and circuits in full.
Sec 2.13Seven recurring errors: confusing conditional and converse; treating "or" as exclusive; mishandling vacuous truth; negating "all" as "none"; misapplying De Morgan's Law; assuming validity guarantees truth; confusing equivalence with equality.
Sec 2.14Chapter 3 extends logic to quantifiers ("for all" and "there exists"). Chapter 4 applies logical argument forms to mathematical proof. All proof methods introduced in Chapter 4 are grounded in the logical tools of this chapter.

Key Terms Review

statement

A declarative sentence with a definite truth value — either true or false, not both and not neither.

truth value

The designation T (true) or F (false) assigned to a statement.

negation (¬p)

The statement with the opposite truth value of p. True when p is false; false when p is true.

conjunction (p ∧ q)

True only when both p and q are true. Corresponds to "and."

disjunction (p ∨ q)

True when at least one of p or q is true. Corresponds to inclusive "or."

conditional (p → q)

False only when p is true and q is false. Corresponds to "if p, then q."

hypothesis

The "if" part of a conditional statement (p in p → q). Also called antecedent or premise.

conclusion

The "then" part of a conditional statement (q in p → q). Also called consequent.

converse

The statement q → p, formed by swapping hypothesis and conclusion of p → q.

inverse

The statement ¬p → ¬q, formed by negating both parts of p → q.

contrapositive

The statement ¬q → ¬p. Logically equivalent to the original conditional p → q.

biconditional (p ↔ q)

True when p and q have the same truth value. Corresponds to "if and only if."

logical equivalence

P ≡ Q: two expressions with identical truth values in every row of their truth tables.

tautology

A compound statement that is true in every row of its truth table.

contradiction

A compound statement that is false in every row of its truth table.

contingency

A compound statement that is neither a tautology nor a contradiction.

argument

A sequence of premises used to support a conclusion.

valid argument

An argument where it is impossible for all premises to be true and the conclusion to be false.

fallacy

An invalid argument form — one in which true premises can lead to a false conclusion.

modus ponens

From p → q and p, conclude q. A valid argument form.

modus tollens

From p → q and ¬q, conclude ¬p. A valid argument form.

De Morgan's Laws

¬(p ∧ q) ≡ ¬p ∨ ¬q and ¬(p ∨ q) ≡ ¬p ∧ ¬q. Used to negate compound statements.

vacuously true

A conditional p → q is vacuously true when p is false, regardless of q.

propositional logic

The branch of formal logic that studies statements and their combinations using connectives, without analyzing internal structure.

Concept Review Questions

What is a statement in formal logic? Give two examples of statements and two examples of sentences that are not statements, with explanations.
What is the truth value of a negation when the original statement is true? When it is false?
Under what conditions is a conjunction false? Under what conditions is a disjunction false?
Under what conditions is a conditional statement false? Why is the conditional vacuously true when the hypothesis is false?
How do the converse, inverse, and contrapositive of a conditional differ from the original?
Which pairs among a conditional, its converse, its inverse, and its contrapositive are logically equivalent?
What is a biconditional? When is it true?
What does it mean for two compound statements to be logically equivalent?
What is a tautology? What is a contradiction? Give one example of each.
What makes an argument valid? Is a valid argument always one with a true conclusion? Explain.
What is the fallacy of affirming the conclusion? Give a concrete example.
State De Morgan's two laws in both symbolic and plain English forms.

Skill Practice

Part AStatements and Negations

For each, state whether it is a statement. If it is, write its negation.

"Every prime number is odd."
"What is the square root of 16?"
"The product of two odd numbers is odd."
"Some integers are negative."
"Turn in your work on time."
"This statement is false."

Part BEvaluating Compound Statements

Let p = "18 is divisible by 3" (T) and q = "18 is divisible by 7" (F). Evaluate each.

p ∧ q
p ∨ q
¬p ∨ q
p → q
q → p
p ↔ q
¬(p ∧ q)
¬p ∨ ¬q

Part CConverse, Inverse, Contrapositive

Write all four forms for each conditional. Determine which are true.

"If n is divisible by 6, then n is divisible by 2."
"If a quadrilateral is a square, then all its angles are right angles."
"If n² is odd, then n is odd."
"If a function is differentiable, then it is continuous."

Part DTruth Tables

(p ∨ q) → ¬p
¬p → (p → q)
(p ↔ q) ∧ ¬q
p → (q ∧ r)
(p → q) ↔ (¬q → ¬p)

Part EArguments

Name the argument form and determine whether it is valid or invalid.

p → q; p; ∴ q
p → q; q; ∴ p
p → q; ¬q; ∴ ¬p
p → q; ¬p; ∴ ¬q
p → q; q → r; ∴ p → r
p ∨ q; ¬q; ∴ p

Error Analysis

Each problem contains an error. Identify it and write the correct reasoning.

Problem 1

A student writes: "The negation of 'All students passed the exam' is 'No students passed the exam.'"

What is wrong? Write the correct negation.

Problem 2

A student evaluates p → q with p = F and q = F and concludes: "Both parts are false, so the conditional is false."

Identify the error. What is the correct truth value?

Problem 3

A student reasons: "My program returned the correct answer, so the algorithm must be correct." Identify the logical fallacy and name it.

What argument form does this resemble? Why is it invalid?

Problem 4

A student simplifies: ¬(p ∧ q) = ¬p ∧ ¬q

What law was misapplied? What is the correct expression?

Problem 5

A student says: "The converse of 'If n is divisible by 4, then n is divisible by 2' is also true, so the converse of every true conditional is true."

Why is this reasoning flawed? Give a conditional whose converse is false.

Chapter 2 Checkpoint

Complete without assistance — assesses all key skills and concepts from Chapter 2

Section A — Statements and Truth Values

Which of the following are statements? For each that is a statement, determine whether it is true or false.
a. "Every even integer greater than 2 can be written as the sum of two primes."
b. "What is 7 + 5?"
c. "Stop and think carefully."
d. "The square root of 9 is 4."
Let p = "The number 12 is divisible by 3" and q = "The number 12 is divisible by 5." Evaluate: (a) p ∧ q, (b) p ∨ q, (c) ¬p, (d) ¬p ∧ q.

Section B — Conditionals

Let p = "A quadrilateral has four equal sides" and q = "A quadrilateral is a rhombus." Write in plain English: (a) p → q, (b) the converse, (c) the contrapositive. Which of (a) and (b) are logically equivalent? Explain.
Determine the truth value of p → q in each case: (a) p = T, q = T; (b) p = T, q = F; (c) p = F, q = T; (d) p = F, q = F.

Section C — Truth Tables

Build a complete truth table for (p ∨ q) → ¬p.
Build a truth table showing that ¬(p ∧ q) ≡ ¬p ∨ ¬q.

Section D — Logical Equivalence and Tautologies

Is p → q logically equivalent to q → p? Provide evidence from a truth table.
Determine whether (p → q) ∧ ¬q is a tautology, a contradiction, or a contingency.

Section E — Arguments

Identify the argument form and determine whether it is valid or invalid: Premise 1: If the temperature drops below 0°C, then water freezes. Premise 2: Water is not frozen. Conclusion: The temperature has not dropped below 0°C.
Give an example of an argument that has the form of affirming the conclusion. Explain why it is invalid.

Section F — Short Answer

Explain in your own words why a conditional with a false hypothesis is considered vacuously true.
A programmer writes: IF (x > 0) AND (y > 0) THEN output "both positive". Under what conditions does the output occur? Write the equivalent logical expression using formal connectives.

Looking Ahead

Chapter 3: Sets, Quantifiers, and Relations

Chapter 2 gave you the grammar of logical reasoning — how to form, evaluate, and combine statements, and how to judge whether an argument is valid. Chapter 3 will extend this foundation in a new direction: sets and quantifiers. You have already seen that some sentences, like "x + 3 = 7," are not statements because their truth depends on the value of x. Quantifiers — "for all" and "there exists" — allow us to turn such open sentences into genuine statements. "For all integers x, x + 3 = 7" is false. "There exists an integer x such that x + 3 = 7" is true. Chapter 3 will give you the tools to write, interpret, negate, and reason about statements of exactly this kind — and to see how sets provide the language for describing the collections that quantifiers range over.

MGU Library Connection

Appendix C — Logic Laws Reference (complete equivalence tables)
Appendix F — Proof Strategy Guide (proof methods using logical tools from this chapter)
Chapter 4: Methods of Proof (direct proof, contrapositive, contradiction — all grounded in Chapter 2)
Chapter 13: Boolean Algebra, Circuits, and Digital Logic (logic gates implement conjunction, disjunction, and negation in hardware)
MGU Computer Science pages — Boolean conditions, control flow, search query logic
MGU Cybersecurity pages — access control policies as logical expressions

Chapter 2:Logic and Truth

Purpose and Overview

Why This Chapter Matters

Learning Objectives

Sections at a Glance

What Logic Studies

Statements and Truth Values

What Is a Statement?

Negation

Conjunction and Disjunction

Conjunction — "and"

Disjunction — "or"

Conditional Statements

Why Is the Conditional True When p Is False?

Ways to Read a Conditional

Converse, Inverse, and Contrapositive

Biconditional Statements

Truth Tables

Logical Equivalence

Key Logical Equivalences

Tautologies and Contradictions

Valid and Invalid Arguments

Common Valid Argument Forms

Common Invalid Argument Forms — Fallacies

Logic in Programming and Digital Systems

Logic in Programming

Logic in Search

Logic in Digital Circuits

Common Logic Mistakes

Preparing for Quantifiers and Proof

Chapter Summary

Key Terms Review

Concept Review Questions

Skill Practice

Error Analysis

Chapter 2 Checkpoint

Chapter 2:
Logic and Truth