Mathematical Language, Logic and Sets

Introduction

Computer applications are built from precise statements about data, conditions, objects, and relationships. A database query, an access-control rule, a validation condition, and an algorithmic decision all depend on mathematical ideas that allow meaning to be expressed without ambiguity. This chapter introduces three closely connected foundations: logic, which studies valid reasoning; predicates and quantifiers, which express properties and general claims; and set theory, which describes collections of objects and operations on them.

These ideas are not merely theoretical. The logical condition age ≥ 18 AND hasValidID, the query selecting users in a particular group, and the representation of a collection of permissions all use the concepts developed here.

Learning Objectives

By the end of this chapter, you should be able to:

• distinguish propositions from non-propositions;
• construct and interpret truth tables;
• use logical connectives, implications, biconditionals, and negation;
• identify tautologies, contradictions, and contingencies;
• establish logical equivalence and apply standard laws;
• translate predicates and quantifiers into formal and natural language;
• use valid inference rules and recognize common reasoning errors;
• describe sets, subsets, power sets, and Cartesian products;
• perform union, intersection, difference, complement, and symmetric difference;
• apply logic and set operations to specifications, queries, and program conditions.

1. Mathematical Language in Computing

Natural language often permits ambiguity. For example, “The system accepts students who submitted the form and paid the fee” may require clarification: must both actions be completed, or is either one sufficient? Mathematical notation supplies precise rules.

A statement or proposition is a declarative sentence that is definitely either true or false, but not both. Examples include:

• “7 is prime.” This is true.
• “10 < 4.” This is false.
• “The program terminated.” This is a proposition if its truth can be determined in the stated context.

Questions, commands, and open sentences are not propositions by themselves:

• “What time is it?” is a question.
• “Close the application.” is a command.
• “x + 2 = 5” is an open sentence because its truth depends on the value of x.

A proposition is commonly represented by a letter such as p, q, or r. Its truth value is written T or F.

2. Propositional Logic

2.1 Logical Connectives

Compound propositions are formed from simpler propositions using logical connectives.

The meaning of each connective is determined by its truth table.

2.2 Negation, Conjunction, and Disjunction

The negation ¬p is true when p is false. 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.

In programming, ∧ is usually represented by AND, and ∨ by OR. The inclusive meaning of “or” must be distinguished from ordinary conversational usage, where “or” may imply exclusivity.

2.3 Implication

The implication p → q is false only when p is true and q is false. In every other case it is true.

The proposition p is the antecedent and q is the consequent. “If a user is authenticated, then the user may access the dashboard” is represented by p → q. The implication does not state what happens when the user is not authenticated.

A useful equivalence is:

This explains why an implication with a false antecedent is true under classical propositional logic. Such a statement is called vacuously true.

The converse of p → q is q → p. The inverse is ¬p → ¬q. Neither is generally equivalent to the original implication. The contrapositive, ¬q → ¬p, is equivalent to p → q.

2.4 Biconditional and Exclusive OR

The biconditional p ↔ q is true when p and q have the same truth value. It can be expressed as:

The statement “a number is even if and only if it is divisible by 2” asserts both directions. In contrast, p ⊕ q is true when exactly one proposition is true:

2.5 Operator Precedence

Unless parentheses indicate otherwise, a common precedence order is:

1. ¬
2. ∧
3. ∨
4. →
5. ↔

For reliable specifications and programs, parentheses should be used even when precedence rules are known.

3. Truth Tables and Logical Classification

A truth table lists every possible combination of truth values. If a compound proposition contains n distinct elementary propositions, it has 2ⁿ rows. Thus, three propositions require 2³ = 8 rows.

A tautology is true for every assignment of truth values. A contradiction is false for every assignment. A contingency is true for some assignments and false for others.

For example, the law of excluded middle is a tautology:

The law of non-contradiction is also a tautology:

The expression p ∧ ¬p is a contradiction.

Worked Example 1: Evaluating a Compound Proposition

Let p be “the server is available” and q be “the network is connected.” Evaluate (p ∧ q) → p.

The final column is always true, so the expression is a tautology. Intuitively, if both p and q are true, p must be true; if p ∧ q is false, the implication is not violated.

4. Logical Equivalence and Laws

Two propositions are logically equivalent, written p ≡ q, if they have the same truth value for every possible assignment. Equivalence may be demonstrated by a truth table or by applying known laws.

Important laws include:

De Morgan’s laws are especially important in programming. The negation of “the user is active and verified” is “the user is not active or not verified,” not necessarily “the user is neither active nor verified.”

Worked Example 2: Simplifying a Condition

Simplify:

Using De Morgan’s law:

This expression is true when p and q have the same truth value. Therefore it is equivalent to p ↔ q.

Logical equivalence supports code optimization, query rewriting, and verification. However, an equivalent mathematical expression should only replace program code when evaluation order, side effects, null values, and language-specific behavior have also been considered.

5. Predicates and Quantifiers

A predicate is an open sentence containing variables. For example, P(x): “x is greater than 5.” P(8) is true, while P(3) is false. The set of permitted values is the domain.

Quantifiers express how broadly a predicate applies:

• Universal quantifier: ∀x P(x), meaning “for every x in the domain, P(x) is true.”
• Existential quantifier: ∃x P(x), meaning “there exists at least one x in the domain for which P(x) is true.”
• Unique existential quantifier: ∃!x P(x), meaning “there exists exactly one x for which P(x) is true.”

The domain must always be stated or understood. “Every account is active” may be true over the set of current accounts but false over all accounts ever created.

Negating Quantifiers

The main rules are:

Thus, “not every record is valid” means “at least one record is invalid.” It does not mean “no record is valid.”

For two variables, order matters. In general:

The first says every x may have a possibly different related y. The second says one particular y is related to every x.

Worked Example 3: Quantified Requirements

Consider the requirement: “Every registered user has at least one valid role.” Let U be the set of registered users and R(u, r) mean “user u has valid role r.” The formal statement is:

Its negation is:

In words: there exists a registered user who has no valid role. This form is useful for testing because a single such user is a counterexample to the original requirement.

6. Inference and Argument Validity

An argument consists of premises and a conclusion. It is valid when no assignment of truth values makes all premises true and the conclusion false. Validity concerns structure, not whether the premises happen to be factually true.

Modus Ponens

Example: If a file is encrypted, it requires a key. The file is encrypted. Therefore, it requires a key.

Modus Tollens

Example: If the deployment succeeded, a release record exists. No release record exists. Therefore, the deployment did not succeed, assuming the premise accurately describes the system.

Hypothetical Syllogism

Disjunctive Syllogism

Two common invalid patterns are:

• Affirming the consequent: p → q, q, therefore p.
• Denying the antecedent: p → q, ¬p, therefore ¬q.

For example, “If a user is an administrator, then the user can view reports. The user can view reports; therefore the user is an administrator” is invalid because other roles may also view reports.

7. Sets and Membership

A set is a well-defined collection of distinct objects. The objects are called elements or members. If x belongs to set A, we write x ∈ A; otherwise x ∉ A.

Sets can be represented by:

• roster notation: A = {2, 4, 6, 8};
• set-builder notation: A = {x ∈ ℕ | x is even and x ≤ 8};
• a verbal description.

The order of elements does not matter, and repetition does not create additional elements. Thus {1, 2, 3} = {3, 2, 1} and {1, 1, 2} = {1, 2}.

The cardinality |A| is the number of elements in a finite set. The empty set, written ∅, has cardinality 0. A universal set U contains all objects under discussion. The complement of A relative to U is:

8. Subsets and Power Sets

A is a subset of B, written A ⊆ B, if every element of A is also an element of B:

If A ⊆ B and A ≠ B, then A is a proper subset, written A ⊂ B. Every set is a subset of itself, and ∅ is a subset of every set.

The power set of A, written 𝒫(A), is the set of all subsets of A. If A is finite and |A| = n, then:

This follows because each of n elements has two independent choices: included or excluded. For A = {a, b},

The distinction between a ∈ A and {a} ⊆ A is important. The element a is an object; {a} is a set containing that object.

9. Set Operations

For sets A and B in a common universal set U:

• Union: A ∪ B = {x | x ∈ A or x ∈ B}
• Intersection: A ∩ B = {x | x ∈ A and x ∈ B}
• Difference: A \ B = {x | x ∈ A and x ∉ B}
• Symmetric difference: A △ B = (A \ B) ∪ (B \ A)

The cardinality formula for two finite sets is:

The subtraction avoids counting the intersection twice. If A and B are disjoint, A ∩ B = ∅, so |A ∪ B| = |A| + |B|.

Set operations obey laws parallel to logical laws. For example, De Morgan’s set laws are:

Worked Example 4: User Groups

Suppose a university system has:

• A = {students enrolled in programming};
• B = {students enrolled in databases}.

If |A| = 120, |B| = 90, and |A ∩ B| = 40, then:

Therefore, 170 students are enrolled in at least one of the two courses, not 210. The number enrolled in exactly one course is:

10. Cartesian Products and Relations

The Cartesian product of A and B is:

The ordered pair (a, b) differs from (b, a) unless a = b. If A and B are finite, then:

For A = {1, 2} and B = {x, y, z}, A × B contains six ordered pairs.

A relation from A to B is any subset of A × B. A database table can be viewed as a relation: each row is a tuple, and columns represent attributes. A function is a special relation in which every input has exactly one output.

Cartesian products support modeling of user-role assignments, state transitions, possible input combinations, and database schemas. They also clarify the size of a search space: if a program accepts k independent Boolean inputs, there are 2ᵏ possible input combinations.

11. Logic and Sets as Models of Programs and Queries

A program condition is a proposition evaluated at runtime. For example:

if (isAuthenticated AND (isAdmin OR hasPermission))
    allow access

Let A mean authenticated, D mean administrator, and P mean permitted. The condition is:

It can be expanded using distributivity:

This reveals that authentication is required in both access paths.

A database query such as “return active users from either the engineering or analytics group” can be represented as:

A query for users who are active but belong to neither group is:

Correct translation matters. Replacing the latter with (Active ∩ Engineering ∪ Analytics)ᶜ changes the scope of the complement and may return entirely different records.

12. Applied Case: Access-Control Specification

Background

A university information system provides access to examination results. The security team proposes this rule: “A person may view results if the person is authenticated and either is the student concerned, is an instructor for the course, or has a designated administrative role.”

Problem

The organization must convert the natural-language rule into a testable specification. Ambiguity could expose confidential records or incorrectly deny legitimate access.

Analysis

Let:

• A: the person is authenticated;
• S: the person is the student concerned;
• I: the person is an instructor for the course;
• R: the person has the designated administrative role.

The proposed condition is:

The parentheses are essential. The condition requires authentication for every category. Without them, an implementation such as A AND S OR I OR R, under common programming precedence, may grant access to an instructor or administrator who is not authenticated.

Approach and Solution

The team creates test cases based on the truth table’s meaningful categories:

The team also defines the underlying sets. Let U be all system users, A ⊆ U the authenticated users, and S, I, R ⊆ U the relevant role or relationship sets. The authorized users are:

Outcome

The formal model exposes two security requirements: authentication must be mandatory, and authorization must be based on at least one approved relationship. The specification can now be implemented, reviewed, and tested independently of a particular programming language.

Learning Points

• Natural-language requirements should be translated before implementation.
• Parentheses communicate security-critical scope.
• Sets model populations; logic models conditions on individual records.
• Counterexamples are valuable: one unauthorized truth assignment can reveal a flawed rule.
• Formal clarity supports auditability and reduces inconsistent interpretations.

13. Limitations, Governance, and Best Practices

Classical two-valued logic assumes that each proposition is true or false. Real systems may contain unknown, missing, stale, or conflicting data. SQL, for example, commonly uses three-valued logic involving TRUE, FALSE, and UNKNOWN when NULL values are present. Therefore, a classical expression may not behave identically in a database query.

Logical equivalence also has implementation limits. Two conditions may be mathematically equivalent but produce different behavior if evaluating one condition causes a side effect, raises an exception, or interacts differently with null values. Developers should consult the semantics of the target language or query system.

Best practices include:

1. define domains, variables, and symbols explicitly;
2. use parentheses in complex conditions;
3. distinguish implication from equivalence;
4. test both positive cases and counterexamples;
5. document whether “or” is inclusive or exclusive;
6. specify how missing and unknown data are handled;
7. use formal conditions to support, not replace, security and privacy review;
8. preserve least privilege when translating authorization rules;
9. validate query rewrites against representative data;
10. use automated tests derived from boundary and truth-table cases.

Formal logic is also relevant to AI and automated reasoning. Rule engines, constraint solvers, type systems, verification tools, and knowledge graphs use logical structures. However, automated output must still be checked for incorrect premises, incomplete domains, and inappropriate assumptions.

Chapter Summary

Propositional logic provides a precise language for statements and compound conditions. Negation, conjunction, disjunction, implication, biconditional, and exclusive OR have defined truth conditions. Truth tables classify expressions as tautologies, contradictions, or contingencies and establish logical equivalence. De Morgan’s laws, distributive laws, and implication equivalences are particularly useful in programming and query design.

Predicates express properties involving variables, while universal and existential quantifiers express general and existence claims. Quantifier order and negation must be handled carefully. Valid inference rules such as modus ponens and modus tollens support reliable reasoning, whereas affirming the consequent and denying the antecedent are invalid.

Set theory models collections of data. Membership, subsets, power sets, Cartesian products, relations, union, intersection, difference, complement, and symmetric difference provide tools for representing populations and relationships. Cardinality formulas prevent errors in counting overlapping groups. Together, logic and sets support precise specifications, database queries, access-control rules, program conditions, testing, and formal analysis.

Key Terms

Proposition: A declarative statement that is either true or false.

Predicate: An open sentence whose truth depends on one or more variables.

Truth value: The value T or F assigned to a proposition.

Negation: The logical operation that reverses a proposition’s truth value.

Conjunction: A compound proposition using “and.”

Disjunction: A compound proposition using inclusive “or.”

Implication: A conditional proposition of the form p → q.

Biconditional: A proposition asserting both directions, p ↔ q.

Tautology: A proposition true under every truth assignment.

Contradiction: A proposition false under every truth assignment.

Logical equivalence: Equality of truth values for all assignments.

Quantifier: A symbol indicating the scope of a predicate, such as ∀ or ∃.

Domain: The collection of values over which variables range.

Inference: Deriving a conclusion from premises.

Set: A well-defined collection of distinct objects.

Subset: A set whose every element belongs to another set.

Power set: The set of all subsets of a given set.

Cartesian product: The set of ordered pairs formed from two sets.

Cardinality: The number of elements in a finite set.

Complement: The elements of the universal set that are not in a specified set.

Review Questions

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 of De Morgan’s laws for propositions.
4. What is the power set of a set?
5. Define the Cartesian product A × B.

Long Answer Questions

1. Explain the major logical connectives and illustrate each with a truth table or example.
2. Describe logical equivalence and explain how it supports program simplification and query rewriting.
3. Explain universal and existential quantifiers, including the rules for negating them.
4. Discuss subsets, power sets, cardinality, and Cartesian products with suitable examples.
5. Explain how set operations and logical operators can jointly model a database query.

Analytical / Application Questions

1. A system grants access when a user is verified and either owns a resource or has an administrator role. Formalize the condition and identify the access result when the user is unverified but is an administrator.
2. In a university, 150 students take Mathematics, 110 take Programming, and 55 take both. Determine the number taking at least one course and explain the set formula used.
3. Analyze the statement: “If a transaction is approved, it is logged. The transaction is logged; therefore it was approved.” Identify the inference error and provide a counterexample.

Multiple Choice Questions with Answers

Question 1

Which statement is a proposition?

A. Please restart the computer.

B. Is the server available?

C. 11 is a prime number.

D. x + 2 = 7

Correct Answer: C. 11 is a prime number.

Question 2

When is p → q false?

A. When p is false and q is true

B. When p is true and q is false

C. When both p and q are false

D. When both p and q are true

Correct Answer: B. When p is true and q is false

Question 3

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 4

What does ∃x P(x) mean?

A. P(x) is true for every x

B. P(x) is false for every x

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

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

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

Question 5

Which inference rule has the form p → q, p, therefore q?

A. Modus ponens

B. Modus tollens

C. Denying the antecedent

D. Affirming the consequent

Correct Answer: A. Modus ponens

Question 6

If A = {1, 2, 3}, what is |𝒫(A)|?

A. 3

B. 6

C. 8

D. 9

Correct Answer: C. 8

Question 7

If |A| = 20, |B| = 15, and |A ∩ B| = 5, what is |A ∪ B|?

A. 25

B. 30

C. 35

D. 40

Correct Answer: A. 25

Question 8

Which set contains all elements in A or B, including elements in both?

A. A ∩ B

B. A \ B

C. A ∪ B

D. A △ B

Correct Answer: C. A ∪ B

Question 9

If A has 2 elements and B has 4 elements, how many ordered pairs are in A × B?

A. 2

B. 4

C. 6

D. 8

Correct Answer: D. 8

Question 10

Which condition represents authenticated users who are either students or instructors?

A. A ∪ (S ∩ I)

B. A ∩ (S ∪ I)

C. (A ∩ S) ∪ Iᶜ

D. Aᶜ ∩ (S ∪ I)

Correct Answer: B. A ∩ (S ∪ I)