Logical Statements & Implications — Evaluate simple logical statements and implications (intro) - Finite Mathematics

SECTION 1

Historical Context & Motivation

The study of formal logic is one of the oldest intellectual pursuits in Western civilization, stretching from ancient Greek philosophy to the foundations of modern computer science. The desire to distinguish valid reasoning from fallacious argumentation motivated thinkers across millennia to develop precise symbolic systems for capturing the structure of thought. Understanding how propositions combine, how one statement can imply another, and how truth values propagate through an argument is not merely an exercise in abstraction — it is the bedrock upon which mathematical proof, digital circuit design, database querying, and artificial intelligence are built.

Before the advent of symbolic notation, logical arguments were evaluated in natural language, which introduced ambiguity, equivocation, and error. The formalization of logic gave mathematicians and scientists a universal language — one free from the vagaries of everyday speech — in which the validity of an argument could be checked mechanically. This section traces that evolution, from Aristotle's syllogisms to the propositional calculus that underpins modern finite mathematics.

~350 BCE • Aristotle's Syllogistic Logic

Aristotle systematized deductive reasoning in his Organon, introducing syllogisms — structured arguments with two premises and a conclusion. This remained the dominant logical framework for nearly two thousand years.

1847 • Boole's Algebraic Logic

George Boole published The Mathematical Analysis of Logic, recasting logical propositions as algebraic equations with values 0 (false) and 1 (true). Boolean algebra later became the mathematical foundation for digital circuits.

1879 • Frege's Predicate Calculus

Gottlob Frege's Begriffsschrift introduced a formal symbolic language for logic, extending propositional logic with quantifiers and predicates. This marks the birth of modern mathematical logic.

1910–1913 • Russell & Whitehead's Principia Mathematica

Bertrand Russell and Alfred North Whitehead attempted to derive all of mathematics from logical axioms, demonstrating the central role of propositional and predicate logic in mathematical foundations.

1937 • Shannon's Logic Circuits

Claude Shannon showed that Boolean algebra could model electrical switching circuits, bridging abstract logic and engineering. Every modern computer operates on the logical connectives studied in this lesson.

The central question this lesson addresses is deceptively simple: given a collection of declarative statements and the logical connectives that join them, how do we determine whether the resulting compound statement is true or false? By the end of this lesson, you will be able to identify propositions, apply the standard connectives (negation, conjunction, disjunction, and especially the conditional implication), construct truth tables, and evaluate the truth value of compound statements with confidence.

SECTION 2

Core Principles & Definitions

Propositional logic begins with the simplest possible building block: a proposition (also called a statement). A proposition is any declarative sentence that is either true or false, but not both. "The integer 7 is prime" is a proposition (it is true). "Close the door" is not a proposition because it is a command and carries no truth value. Questions, exclamations, and vague sentences likewise fail to qualify. Every proposition is assigned a truth value — either T (true) or F (false) — and we typically denote propositions with lowercase letters such as p, q, and r.

Negation (¬p)

The negation of a proposition p reverses its truth value. If p is true, ¬p is false, and vice versa. Read as "not p."

Conjunction (p ∧ q)

The conjunction of p and q is true only when both component propositions are true. It captures the everyday meaning of "and."

Disjunction (p ∨ q)

The inclusive disjunction is true when at least one of p or q is true. It is false only when both are false. This is the logical "or."

Conditional (p → q)

The conditional (implication) "if p then q" is false only when p is true and q is false. In all other cases it is true.

Biconditional (p ↔ q)

The biconditional "p if and only if q" is true when both propositions share the same truth value — both true or both false.

✦

KEY TAKEAWAY

Think of the conditional p → q like a contractual promise. A professor says, "If you score above 90, then you get an A." The promise is broken (false) only when you score above 90 and do not receive an A. If you score below 90, the contract says nothing — no promise was violated — so the conditional is vacuously true regardless of the grade assigned. This is the single most counterintuitive point for newcomers: a conditional with a false hypothesis is always true.

SECTION 3

Visual Explanation — Truth Tables at a Glance

The most fundamental tool for evaluating logical statements is the truth table. A truth table exhaustively lists every possible combination of truth values for the component propositions and then computes the resulting truth value of the compound expression. For two propositions p and q, there are 2² = 4 rows; for three propositions, 2³ = 8 rows; in general, n propositions generate 2ⁿ rows. The diagram below provides a consolidated visual reference for the four primary binary connectives.

The four truth tables above cover conjunction (∧), disjunction (∨), the conditional (→), and the biconditional (↔). Notice that conjunction is the most restrictive — only one row yields true — while disjunction is the most permissive — only one row yields false. The conditional stands out because it is false in exactly one scenario: when the hypothesis is true and the conclusion is false.

When reading the conditional truth table, pay special attention to the last two rows. When the hypothesis p is false, the conditional p → q is true regardless of the truth value of q. This property is called vacuous truth, and it is consistent with the mathematical convention that a conditional promise is violated only when the antecedent holds but the consequent fails.

SECTION 4

Mathematical Framework — Formal Notation & Equivalences

With the truth table definitions in hand, we can now express several important logical equivalences that are used to simplify compound statements and prove arguments valid. The following equations formalize relationships among the connectives and provide tools for algebraic manipulation of propositions.

CONDITIONAL EQUIVALENCE

p → q ≡ ¬p ∨ q

An implication "if p then q" is logically equivalent to "not p or q." This can be verified by comparing the truth tables of both expressions column by column — they match in all four rows. The symbol ≡ denotes logical equivalence.

CONTRAPOSITIVE

p → q ≡ ¬q → ¬p

The contrapositive of an implication always has the same truth value as the original. If "rain implies wet ground" is true, then "not wet ground implies not rain" is equally true. The contrapositive is a powerful proof technique.

DE MORGAN'S LAWS

¬(p ∧ q) ≡ ¬p ∨ ¬q and ¬(p ∨ q) ≡ ¬p ∧ ¬q

De Morgan's Laws describe how negation distributes over conjunction and disjunction. Negating an "and" turns it into an "or" of negations, and vice versa. These laws are essential when simplifying negated compound statements.

BICONDITIONAL EXPANSION

p ↔ q ≡ (p → q) ∧ (q → p)

The biconditional "p if and only if q" asserts that the implication runs in both directions. This decomposition is frequently used when proving biconditional statements: prove the forward direction and the reverse direction separately.

⚠

Converse vs. Contrapositive

Students often confuse the converse (q → p) with the contrapositive (¬q → ¬p). The converse is NOT logically equivalent to the original conditional — it may have a different truth value. The contrapositive, however, is always equivalent. For example, "If it is a dog, then it is an animal" is true, and its contrapositive "If it is not an animal, then it is not a dog" is also true. But the converse "If it is an animal, then it is a dog" is clearly false.

SECTION 5

Related Forms of the Conditional

Given a conditional statement p → q, three related statements arise naturally: the converse, the inverse, and the contrapositive. Understanding which of these forms are logically equivalent to the original and which are not is crucial for constructing valid proofs and avoiding logical errors. The diagram below illustrates the relationships among these four forms.

The conditional (p → q) and its contrapositive (¬q → ¬p) are always logically equivalent, as are the converse (q → p) and the inverse (¬p → ¬q). However, the conditional and its converse are generally NOT equivalent. The diagonal green and pink lines indicate the equivalent pairs.

Form	Symbolic	Equivalent to p → q?	Example ("If it rains, then the ground is wet")
Conditional	p → q	— (original)	If it rains, then the ground is wet.
Converse	q → p	No	If the ground is wet, then it rains. (False — a sprinkler could wet the ground.)
Inverse	¬p → ¬q	No	If it does not rain, then the ground is not wet. (False — same sprinkler counterexample.)
Contrapositive	¬q → ¬p	Yes	If the ground is not wet, then it did not rain. (True.)

Summary of the four forms associated with a conditional statement

SECTION 6

Worked Example — Evaluating a Compound Logical Statement

Let us work through a complete example that combines multiple connectives. Suppose we are given the propositions p: "5 > 3" (true), q: "2 + 2 = 5" (false), and r: "The empty set is a subset of every set" (true). We want to determine the truth value of the compound statement (p → q) ∨ (¬q ∧ r).

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

1
Step 1 — Identify the truth values of the atomic propositions

We begin by recording the truth values of each simple proposition. We have p = T (since 5 > 3 is true), q = F (since 2 + 2 ≠ 5), and r = T (since the empty set is indeed a subset of every set).

p = T, q = F, r = T
2
Step 2 — Evaluate the negation ¬q

Since q is false, its negation ¬q reverses the truth value. Therefore ¬q = T.

¬q = T
3
Step 3 — Evaluate the conditional p → q

The conditional p → q is false only when the hypothesis p is true and the conclusion q is false. Here p = T and q = F, so p → q = F. This is the sole scenario in which a conditional is false.

p → q = F
4
Step 4 — Evaluate the conjunction ¬q ∧ r

Conjunction requires both operands to be true. We have ¬q = T and r = T, so ¬q ∧ r = T.

¬q ∧ r = T
5
Step 5 — Evaluate the disjunction (p → q) ∨ (¬q ∧ r)

Finally, we apply disjunction to the results of Steps 3 and 4. Disjunction is true when at least one operand is true. We have F ∨ T = T.

(p → q) ∨ (¬q ∧ r) = T

💡

Order of Operations in Logic

Just as arithmetic has PEMDAS, logic has a standard precedence: ¬ (negation) binds most tightly, followed by ∧ (conjunction), then ∨ (disjunction), then → (conditional), and finally ↔ (biconditional). Parentheses always override this default ordering. When in doubt, add parentheses to make your intent unambiguous.

SECTION 7

Strengths & Limitations of Propositional Logic

Propositional logic is a powerful and elegant framework, but it is important to understand both what it can accomplish and where it falls short. The table below contrasts the strengths of propositional logic with its inherent limitations, providing context for why more expressive systems (such as predicate logic) are eventually needed.

Strengths	Limitations
Decidable: truth tables provide a mechanical, guaranteed method for checking validity.	Exponential growth: n propositions require 2ⁿ rows in a truth table, making brute-force evaluation impractical for large n.
Clear semantics: each connective has a precise, unambiguous definition.	Cannot express internal structure of propositions — "all dogs are mammals" must be a single atomic proposition, losing its quantified structure.
Foundation for digital circuits, programming conditionals, and database queries.	Cannot handle variables, quantifiers (∀, ∃), or relational predicates — these require predicate (first-order) logic.
Algebraic laws (De Morgan's, distributive, etc.) enable systematic simplification.	The material conditional (→) does not capture all senses of "if…then…" in natural language (e.g., causal, counterfactual).

Strengths vs. limitations of propositional logic

✦

KEY TAKEAWAY

Propositional logic is analogous to assembly language in computing: it is low-level, precise, and forms the foundation upon which all higher-level logical systems are built. Just as you cannot write complex software in assembly alone without great difficulty, you cannot express sophisticated mathematical arguments purely in propositional logic. But understanding it thoroughly is essential before moving to predicate logic, proof theory, or any formal verification system.

SECTION 8

Connection to Advanced Theory — From Propositions to Predicates

The propositional logic studied in this lesson is sometimes called "zeroth-order logic" because it treats propositions as indivisible atoms. In subsequent coursework, you will encounter predicate (first-order) logic, which opens up propositions to reveal their internal structure — subjects, predicates, and quantifiers. The table below compares the two systems.

Feature	Propositional Logic	Predicate (First-Order) Logic
Basic unit	Atomic proposition (p, q, r)	Predicate with variables: P(x), R(x, y)
Quantifiers	Not available	Universal (∀x) and existential (∃x)
Decidability	Decidable (truth tables)	Semi-decidable (Church–Turing theorem)
Expressiveness	Limited — whole sentences as atoms	Can express "for all x" and "there exists x" claims
Application	Circuit design, simple arguments, truth-functional analysis	Mathematical proofs, database queries (SQL), AI knowledge bases

Propositional logic vs. predicate logic

Additionally, the concepts of tautology (a statement true under every possible truth assignment), contradiction (always false), and contingency (sometimes true, sometimes false) will become central when you study logical equivalence and argument validity in greater depth. For instance, the statement p ∨ ¬p is a tautology (the law of the excluded middle), while p ∧ ¬p is a contradiction. Recognizing these patterns is a stepping stone toward formal proof methods such as natural deduction and resolution.

SECTION 9

Practice Problems

Question 1: CONCEPTUAL

Explain in your own words why the conditional p → q is considered true when the hypothesis p is false, regardless of the truth value of q. Use a real-world analogy to justify this convention.

Show answer

The conditional p → q functions like a promise: it specifies what must happen when p is true. When p is false, the promise is never activated, so it cannot be violated. Consider the statement "If you finish your thesis by Friday, then the department will fund your conference trip." If you do not finish the thesis by Friday, the department has made no commitment — the promise is neither fulfilled nor broken. In formal logic, we say the conditional is vacuously true in this case. This convention ensures that the conditional has a definite truth value in every possible scenario, which is essential for constructing complete truth tables and analyzing argument validity.

Question 2: BASIC CALCULATION

Let p be true and q be false. Evaluate the compound statement ¬(p ∧ q) → (p ∨ q). Show each step.

Show answer

First evaluate the inner conjunction: p ∧ q = T ∧ F = F. Then negate: ¬(p ∧ q) = ¬F = T. This is the hypothesis of the conditional. Next evaluate the conclusion: p ∨ q = T ∨ F = T. Now apply the conditional: T → T = T. The compound statement evaluates to true. Notice we could also verify this using the equivalence p → q ≡ ¬p ∨ q, rewriting ¬(p ∧ q) → (p ∨ q) as ¬¬(p ∧ q) ∨ (p ∨ q) = (p ∧ q) ∨ (p ∨ q), which with p = T and q = F gives F ∨ T = T, confirming our result.

Question 3: INTERMEDIATE

Construct a truth table for the statement (p → q) ∧ (q → r) → (p → r). Determine whether this statement is a tautology, a contradiction, or a contingency.

Show answer

With three propositions, the truth table has 2³ = 8 rows. For each row, first compute p → q and q → r, then their conjunction, and finally evaluate whether that conjunction implies p → r. In every one of the eight rows, the entire expression evaluates to true. For example, when p = T, q = T, r = F: p → q = T, q → r = F, so (p → q) ∧ (q → r) = F. The overall conditional F → F = T. When p = T, q = T, r = T: all sub-expressions are T, and T → T = T. Since the result is true in every row, the statement is a tautology. This tautology is known as the hypothetical syllogism — it formalizes the transitivity of implication.

Question 4: APPLIED

A software specification states: "If the user is authenticated (A) and has admin privileges (B), then the user can delete records (D)." Symbolize this as a logical statement and determine its truth value in the scenario where the user is authenticated, does NOT have admin privileges, and CAN delete records.

Show answer

The specification is symbolized as (A ∧ B) → D. In the given scenario, A = T, B = F, and D = T. Evaluating the hypothesis: A ∧ B = T ∧ F = F. Since the hypothesis is false, the conditional is vacuously true: F → T = T. This means the specification is NOT violated in this scenario — the specification only promises what happens when both conditions are met. Importantly, the specification says nothing about whether a non-admin authenticated user may or may not delete records; that situation falls outside the scope of the guarantee. A system designer who wants to prevent such access would need an additional rule, such as ¬B → ¬D.

Question 5: CRITICAL THINKING

Prove that the conditional p → q is logically equivalent to its contrapositive ¬q → ¬p by constructing a truth table for both expressions and comparing their columns. Then explain why the converse q → p is NOT equivalent to p → q by identifying a specific row where they differ.

Show answer

Construct a four-row truth table with columns for p, q, ¬p, ¬q, p → q, ¬q → ¬p, and q → p. Row 1 (T, T): p → q = T, ¬q → ¬p = F → F = T. Equal. Row 2 (T, F): p → q = F, ¬q → ¬p = T → F = F. Equal. Row 3 (F, T): p → q = T, ¬q → ¬p = F → T = T. Equal. Row 4 (F, F): p → q = T, ¬q → ¬p = T → T = T. Equal. Since p → q and ¬q → ¬p agree in all four rows, they are logically equivalent. Now examine q → p: in Row 2 (T, F), q → p = F → T = T, but p → q = F. In Row 3 (F, T), q → p = T → F = F, but p → q = T. These two rows demonstrate that the converse does not match the original conditional, so q → p is NOT equivalent to p → q. This distinction is critical in mathematical proofs: proving the converse does not establish the original statement.

SUMMARY

Lesson Summary

Summary

This lesson introduced the foundations of propositional logic, beginning with the concept of a proposition — a declarative sentence with a definite truth value — and progressing through the five primary logical connectives: negation (¬), conjunction (∧), disjunction (∨), the conditional (→), and the biconditional (↔). We saw that truth tables provide an exhaustive, mechanical method for evaluating any compound statement.

A central focus was the conditional implication (p → q), which is false only when the hypothesis is true and the conclusion is false — a point that relies on the concept of vacuous truth. We distinguished the contrapositive (¬q → ¬p) — which is logically equivalent to the original — from the converse (q → p) and inverse (¬p → ¬q), which are not. Key equivalences such as De Morgan's Laws and the conditional equivalence (p → q ≡ ¬p ∨ q) provide the algebraic tools needed to simplify and transform logical expressions. These foundations prepare you for predicate logic, formal proofs, and applications in computer science and discrete mathematics.