Mathematical Logic, Boolean Algebra and Proof

Introduction and Context

Mathematical logic provides a precise language for reasoning about programs, data, algorithms, and digital systems. A program condition such as if (age ≥ 18 && hasID) is a logical expression. A database query combines predicates. A digital circuit implements Boolean operations. A proof establishes that an algorithm or circuit behaves correctly for every permitted input, not merely for selected test cases.

This chapter develops three closely related viewpoints:

1. Propositional and predicate logic, which formalize statements and conditions.
2. Boolean algebra, which provides algebraic rules for simplifying and implementing logic.
3. Proof techniques, which justify mathematical and computational claims.

The distinction between syntax and meaning is important. Syntax specifies how symbols may be combined; semantics specifies when an expression is true. In computing, this distinction appears in the difference between a valid expression and one that produces the intended result.

Learning Objectives

After studying this chapter, you should be able to:

• distinguish propositions, predicates, and open sentences;
• construct and interpret truth tables;
• use logical connectives, implication, and biconditional statements;
• apply universal and existential quantifiers and negate quantified statements;
• recognize logical equivalence and important laws of logic;
• translate between logic, Boolean algebra, programming conditions, and circuits;
• simplify Boolean expressions using algebraic laws and Karnaugh-map reasoning;
• construct direct, contradiction, contrapositive, and mathematical-induction proofs;
• assess the correctness and limitations of logical specifications in IT systems.

1. Propositions and Logical Connectives

A proposition is a declarative sentence that is either true or false, but not both. For example, “7 is prime” is a proposition, and its truth value is true. “The server is available” is a proposition whose truth value may change over time, but at a particular time it is either true or false. Questions, commands, and ambiguous sentences are not propositions in this sense.

A proposition represented by a letter such as p or q is called an atomic proposition. More complex propositions are formed with logical connectives.

The conjunction p ∧ q is true only when both components are true. The inclusive disjunction p ∨ q is false only when both components are false. Exclusive OR is true when exactly one input is true; it is not the same as inclusive OR.

Implication

The implication p → q is false only when p is true and q is false. In every other case it is true. This definition can initially seem counterintuitive, but it is appropriate for conditional claims: a promise “if p occurs, q will occur” is violated only by an occurrence of p without q.

The proposition p is the antecedent and q is the consequent. The converse is q → p, while the contrapositive is ¬q → ¬p. An implication is logically equivalent to its contrapositive, but generally not to its converse.

Truth Tables

A truth table lists every possible combination of truth values. With n independent propositions there are 2ⁿ rows. For two propositions:

Worked example. Determine whether the condition “a user may access a resource if the user is authenticated and either an administrator or the owner” is satisfied. Let a mean authenticated, r mean administrator, and o mean owner. The condition is:

If a = T, r = F, and o = T, then r ∨ o = T, so the entire condition is true. If authentication is false, the condition is false regardless of the other two values.

2. Logical Equivalence and Laws

Two propositions are logically equivalent, written p ≡ q, if they have the same truth value for every assignment of their variables. Equivalence can be proved by a truth table or by applying known laws.

Important laws include:

An implication can be rewritten as:

This identity explains the truth table for implication. It also supports simplification in software conditions and circuit design.

Worked simplification. Simplify ¬(p ∨ (¬p ∧ q)). First apply De Morgan’s law:

Apply De Morgan’s law again and double negation:

Distribute:

Thus the original expression is equivalent to ¬p ∧ ¬q.

3. Predicates and Quantifiers

A predicate is a statement containing variables whose truth depends on the values assigned to those variables. For example, P(x): x > 10 is false for x = 7 and true for x = 15. A predicate becomes a proposition when its variables are assigned values or bound by quantifiers.

The universal quantifier, ∀, means “for every,” while the existential quantifier, ∃, means “there exists at least one.” The domain must always be specified because the truth of a quantified statement depends on it.

Examples:

• ∀x ∈ ℤ, x + 0 = x is true.
• ∃x ∈ ℤ, x² = 9 is true because x may be 3 or −3.
• ∀x ∈ ℤ, x² ≥ x is false, for example at x = 0? It is true at 0, but false at x = −1 because 1 ≥ −1 is true; choose x = 2 gives 4 ≥ 2 true. In fact this statement is true for all integers. A careful check is essential before accepting a counterexample.

Negation rules are fundamental:

Therefore, “not every file is encrypted” means “there exists a file that is not encrypted,” whereas “no file is encrypted” means “every file is not encrypted.”

Quantifier order matters. Over the real numbers, ∀x ∃y (y > x) is true, but ∃y ∀x (y > x) is false. The first permits y to depend on x; the second requires one fixed y greater than every real number.

In databases and specifications, a predicate may express a constraint such as Valid(u):= authenticated(u) ∧ ¬suspended(u). A security requirement might be ∀u, access(u) → Valid(u). Such formalization exposes assumptions that informal requirements often hide.

4. Boolean Algebra and Digital Logic

Boolean algebra works with values 0 and 1, conventionally representing false and true. Its operations correspond closely to logical operations:

• Boolean complement x′ corresponds to logical NOT.
• Boolean product xy corresponds to AND.
• Boolean sum x + y corresponds to OR.

The symbols are analogous but not identical to ordinary arithmetic. In Boolean algebra, 1 + 1 = 1 and 1·1 = 1. A Boolean expression describes a switching function whose inputs and output are 0 or 1.

A logic gate implements an operation: NOT, AND, OR, NAND, NOR, XOR, and XNOR are common gates. NAND and NOR are functionally complete: any Boolean function can be constructed using only NAND gates or only NOR gates. This matters in hardware engineering because reducing the number or variety of gate types can simplify manufacturing and verification.

Canonical Forms

A Boolean function may be represented as a sum of products (SOP) or product of sums (POS). In SOP, each product term corresponds to a combination of input values that makes the function 1. For example:

This expression is 1 for the input combinations 011, 101, and 111. A complete canonical SOP uses every variable in every product term. Canonical forms are useful for deriving circuits directly from truth tables, although they may not be minimal.

Simplification and Karnaugh Maps

Algebraic simplification uses the laws listed earlier. For a small number of variables, a Karnaugh map groups adjacent 1-cells in powers of two: 1, 2, 4, 8, and so on. Adjacency includes wraparound edges. Each group eliminates variables that change within the group.

For example, suppose a function is 1 whenever a = 1 and either b or c is 1:

The factored form may use fewer gates. In a physical circuit, simplification can reduce propagation delay, power consumption, hardware cost, and opportunities for wiring errors. However, optimization must not violate timing, hazard, fan-in, or safety constraints.

5. Logic in Programming and Systems

Programming languages implement logical expressions, but their semantics may include features not present in elementary logic. Short-circuit evaluation stops evaluating a conjunction after a false operand or a disjunction after a true operand. Thus:

user != null && user.isActive()

can safely avoid calling isActive() when user is null. Reordering conditions can therefore change behavior if an expression has side effects, causes an exception, or is computationally expensive, even when the expressions are logically equivalent in a pure mathematical model.

Three-valued logics are also used in some database systems, where a comparison involving NULL may produce UNKNOWN rather than true or false. Classical equivalences must then be applied cautiously. For example, a Boolean law proved under two-valued semantics may not have the same operational interpretation under SQL’s three-valued logic.

Logical specifications support:

• access-control rules;
• validation and input constraints;
• search filters and database queries;
• test-case generation;
• model checking and formal verification;
• fault detection and digital control systems.

A useful professional practice is to separate business rules into named predicates, document their domains, and test boundary cases. Ambiguous conditions involving “and/or,” missing values, time zones, or permissions can become security vulnerabilities.

6. Methods of Mathematical Proof

A proof is a logically valid argument establishing that a claim follows from accepted definitions, axioms, and previously proved results. Testing can reveal a counterexample, but no finite collection of tests normally proves a universal claim.

Direct Proof

To prove P → Q directly, assume P and derive Q using valid steps.

Example. Prove: if n is an even integer, then n² is even.

By definition of evenness, n = 2k for some integer k. Therefore:

Since 2k² is an integer, n² is even.

Proof by Contrapositive

Because P → Q is equivalent to ¬Q → ¬P, one may prove the contrapositive instead.

Example. Prove that if n² is odd, then n is odd. The contrapositive is: if n is even, then n² is even, which was established above. Therefore the original claim is true.

Proof by Contradiction

To prove a claim P, assume ¬P and derive a contradiction, often a statement of the form R ∧ ¬R. The assumption must be clearly identified, and the contradiction must follow from valid reasoning.

Example. Prove that there is no largest integer. Assume there is a largest integer m. Then m + 1 is an integer and is greater than m, contradicting the assumption that m was largest. Hence no largest integer exists.

Proof by Cases

A claim may be established by partitioning all possibilities into exhaustive cases. For an integer, cases might be even and odd. The cases must cover every possibility, and each case must be proved.

Mathematical Induction

Induction proves a statement P(n) for every integer n ≥ n₀. It requires:

1. Base case: prove P(n₀).
2. Inductive hypothesis: assume P(k) for an arbitrary integer k ≥ n₀.
3. Inductive step: use that assumption to prove P(k + 1).

The conclusion is that P(n) holds for all integers n ≥ n₀. The inductive hypothesis is not an assumption that the result is true for all values; it is a temporary assumption for one arbitrary k.

Worked example. Prove:

Base case: for n = 1, the left side is 1 and the right side is 1(2)/2 = 1.

Inductive hypothesis: assume:

For k + 1:

Factor:

This is the required formula with n replaced by k + 1. Therefore the claim holds for every integer n ≥ 1.

Strong induction allows the inductive step to use all earlier cases P(n₀), …, P(k). It is useful when a result depends on several smaller instances, as in recursive algorithms and prime-factorization arguments.

7. A Case Study: Verifying an Access-Control Rule

Background

Consider an illustrative university file service. A file may be downloaded when the requester is authenticated, the file is not classified as restricted, and either the requester owns the file or has a granted permission.

Problem

The initial implementation uses:

allow = authenticated && (!restricted || owner) && permission

The security team observes that owners are still required to have explicit permission, contrary to the policy.

Analysis

Let a mean authenticated, r mean restricted, o mean owner, and p mean permission. The implemented rule is:

The stated policy is:

These are not equivalent. For an authenticated owner downloading a non-restricted file with no explicit permission, the implementation gives false because p is false, while the policy gives true because o ∨ p is true.

Approach and Solution

The corrected implementation is:

allow = authenticated && !restricted && (owner || permission)

A truth table or automated equivalence checker should compare the implementation with the formal policy for all 16 combinations of four Boolean variables. Boundary tests should include unauthenticated owners, authenticated non-owners with permission, restricted owners, and missing identity data.

Outcome

The revised expression matches the stated rule under two-valued assumptions. The system should additionally define how missing permissions, revoked accounts, administrative overrides, and concurrent policy changes are handled.

Learning Points

Formalization exposes misplaced parentheses and policy ambiguity. Logical equivalence is stronger than a few successful examples. Security rules should be reviewed by domain experts, implemented with explicit operator precedence, and verified under the actual platform’s null and error semantics.

8. Limitations, Governance, and Best Practices

Classical logic assumes well-defined propositions and two truth values. Real IT systems may involve incomplete data, probabilistic events, temporal conditions, inconsistent requirements, or changing states. Temporal logic, fuzzy logic, modal logic, and three-valued semantics can address some of these situations, but they require their own definitions and validation.

Formal correctness also depends on the specification. A program can perfectly implement the wrong policy. Therefore, requirements engineering, stakeholder review, threat modeling, privacy analysis, and audit trails remain necessary. Automated theorem provers and AI-assisted coding tools can help generate tests or suggest proofs, but their outputs require human verification. An apparently valid simplification may silently change behavior around NULL values, integer overflow, exceptions, or concurrency.

Best practices include:

• define every variable and its domain;
• state whether OR is inclusive or exclusive;
• use parentheses rather than relying on precedence;
• simplify expressions only under stated semantic assumptions;
• use truth tables for small finite conditions;
• use formal tools for larger specifications;
• prove invariants for loops and recursive procedures;
• test counterexamples and boundary values;
• document exceptions, missing data, and override rules;
• review security-critical logic independently.

Chapter Summary

Mathematical logic represents propositions and predicates precisely. Connectives such as NOT, AND, OR, implication, and biconditional can be evaluated with truth tables and transformed using laws of logical equivalence. Quantifiers express claims over domains, and their negations exchange universal and existential forms. Boolean algebra gives a two-valued algebraic model for logic gates and supports circuit and condition simplification. Programming applications require attention to short-circuit evaluation, side effects, NULL values, and policy assumptions. Direct, contrapositive, contradiction, cases, and induction proofs provide complementary methods for establishing correctness. In professional IT practice, formal reasoning is most effective when combined with precise requirements, testing, security review, and awareness of real-system semantics.

Key Terms

Proposition: A declarative statement that is true or false.

Predicate: A statement containing variables whose truth depends on assigned values.

Truth value: The value true or false assigned to a proposition.

Negation: The logical operation that reverses a truth value.

Conjunction: The AND operation, true only when both operands are true.

Disjunction: The inclusive OR operation, true when at least one operand is true.

Exclusive OR: An operation true when exactly one operand is true.

Implication: A conditional proposition p → q.

Biconditional: A proposition asserting that two statements have the same truth value.

Logical equivalence: Equality of truth values for every assignment.

Predicate domain: The set from which quantified variables take values.

Universal quantifier: The symbol ∀, meaning for every.

Existential quantifier: The symbol ∃, meaning there exists at least one.

Boolean algebra: An algebraic system for two-valued variables and operations.

Logic gate: A physical or simulated device implementing a Boolean operation.

Canonical form: A standard Boolean representation such as sum of products.

Contrapositive: The equivalent conditional ¬q → ¬p of p → q.

Proof by contradiction: A proof method that derives impossibility from the negation of a claim.

Mathematical induction: A proof method using a base case and an inductive step.

Invariant: A property that remains true throughout an algorithm or system process.

Review Questions

5 Short Answer Questions

1. What is the difference between a proposition and a predicate?
2. When is an implication p → q false?
3. State both De Morgan laws.
4. Why does the order of quantifiers matter?
5. What are the two essential parts of a proof by induction?

5 Long Answer Questions

1. Construct a truth table for (p ∧ q) → (p ∨ q) and explain the result.
2. Explain logical equivalence and simplify a Boolean expression using at least three algebraic laws.
3. Describe universal and existential quantifiers, including the rules for negating each.
4. Compare direct proof, contrapositive proof, contradiction, and induction, giving an IT-related example for two methods.
5. Explain why a Boolean expression that is mathematically equivalent may behave differently in a programming language with short-circuit evaluation or NULL values.

3 Analytical / Application Questions

1. Formalize an access rule requiring authentication, a non-suspended account, and either ownership or an administrator role. Then identify two boundary cases that should be tested.
2. A circuit outputs 1 for inputs 011, 101, and 111. Write its canonical SOP expression and simplify it using Boolean algebra.
3. A recursive algorithm is claimed to terminate and return a correct result for every non-negative integer input. Design an induction-based proof outline, identifying a suitable base case, inductive hypothesis, and inductive step.

Multiple Choice Questions with Answers

Question 1

Which truth assignment makes the implication p → q false?

A. p = T and q = T

B. p = T and q = F

C. p = F and q = T

D. p = F and q = F

Correct Answer: B. p = T and q = F

Question 2

Which expression is logically equivalent to ¬(p ∨ q)?

A. ¬p ∨ ¬q

B. p ∧ q

C. ¬p ∧ ¬q

D. p ∨ ¬q

Correct Answer: C. ¬p ∧ ¬q

Question 3

What does ∃x P(x) assert?

A. P is true for every x

B. P is false for every x

C. There is at least one x for which P is true

D. There is exactly one x for which P is true

Correct Answer: C. There is at least one x for which P is true

Question 4

Which Boolean expression is equivalent to a ∧ (b ∨ c)?

A. (a ∧ b) ∨ (a ∧ c)

B. (a ∨ b) ∧ c

C. a ∨ (b ∧ c)

D. a ∧ b ∧ c

Correct Answer: A. (a ∧ b) ∨ (a ∧ c)

Question 5

What is the contrapositive of p → q?

A. q → p

B. ¬p → ¬q

C. ¬q → ¬p

D. p ↔ q

Correct Answer: C. ¬q → ¬p

Question 6

If p = F, q = T, and r = F, what is the value of p ∨ (q ∧ r)?

A. True

B. False

C. Undefined

D. Both true and false

Correct Answer: B. False

Question 7

Which item is required in a proof by mathematical induction?

A. A probability distribution

B. A base case and an inductive step

C. A truth table with exactly four rows

D. A counterexample to the claim

Correct Answer: B. A base case and an inductive step

Question 8

The canonical SOP expression for a function equal to 1 on inputs 011, 101, and 111 is:

A. a′bc + ab′c + abc

B. abc′ + a′b′c + ab′c′

C. a′b′c + ab′c + abc′

D. a′bc′ + abc + ab′c′

Correct Answer: A. a′bc + ab′c + abc

Question 9

Which statement correctly describes exclusive OR?

A. It is true when both inputs are true

B. It is true when at least one input is true

C. It is true when exactly one input is true

D. It is always false when inputs differ

Correct Answer: C. It is true when exactly one input is true

Question 10

Why can a logically equivalent rearrangement change program behavior?

A. Truth tables are invalid for programs

B. Programming languages may use short-circuit evaluation or side effects

C. Boolean algebra applies only to numbers greater than zero

D. Implication has no truth value

Correct Answer: B. Programming languages may use short-circuit evaluation or side effects