Propositional and Predicate Logic

Introduction

Logic provides a formal language for representing information, evaluating arguments, and determining whether conclusions follow from premises. In artificial intelligence and machine learning, logic is used in knowledge representation, rule-based systems, planning, software and hardware specification, database querying, verification, and satisfiability solving. It supplies precise mechanisms for distinguishing valid reasoning from unsupported inference.

This chapter develops two closely related systems. Propositional logic represents whole statements that are either true or false and combines them with logical connectives. Predicate logic, also called first-order logic, represents objects, their properties, and relationships using predicates, variables, and quantifiers. Propositional logic is simpler and computationally convenient, whereas predicate logic is more expressive.

A central distinction is between syntax and semantics. Syntax specifies how expressions may be formed. Semantics assigns meaning, usually through truth values or interpretations. A well-formed expression may be meaningful syntactically even when it is false under a particular interpretation.

Learning Objectives

After completing this chapter, a student should be able to:

1. Define propositions, predicates, logical connectives, interpretations, tautologies, contradictions, and contingencies.

2. Construct and interpret truth tables.

3. Prove logical equivalence using laws and truth tables.

4. Apply inference rules and assess the validity of arguments.

5. Translate between English statements and predicate-logic formulas.

6. Use universal and existential quantifiers correctly, including negated and nested quantifiers.

7. Convert propositional formulas into useful normal forms.

8. Explain satisfiability and its relationship to SAT solving.

9. Apply logic to AI knowledge representation and formal specifications.

10. Recognize limitations, ambiguity, and governance concerns in logical systems.

1. Propositions and Logical Syntax

A proposition is a declarative statement that has exactly one truth value: true or false. For example, “7 is prime” is a true proposition, while “9 is prime” is false. Questions, commands, and expressions such as “Close the door” or “What time is it?” are not propositions because they do not have truth values in the relevant sense.

A proposition is commonly represented by a lowercase letter such as p, q, or r. A simple proposition cannot be decomposed into smaller propositions using logical connectives. A compound proposition is formed from one or more propositions.

The principal connectives are:

• Negation: ¬p, read “not p”
• Conjunction: p ∧ q, read “p and q”
• Disjunction: p ∨ q, read “p or q”
• Exclusive disjunction: p ⊕ q, read “p or q, but not both”
• Implication: p → q, read “if p, then q”
• Biconditional: p ↔ q, read “p if and only if q”

A well-formed formula is an expression constructed according to the syntax rules of the logic. If p and q are propositions, then ¬p, (p ∧ q), and (p → q) are well-formed formulas.

1.1 Meaning of the Connectives

The truth value of ¬p is the opposite of the truth value of p. The conjunction p ∧ q is true only when both p and q are true. The inclusive disjunction p ∨ q is true when at least one of p and q is true. In ordinary mathematical logic, “or” is inclusive unless explicitly stated otherwise.

The implication p → q is false only when p is true and q is false. In all other cases it is true. This may initially seem unintuitive because an implication does not assert that p is true. It states that a true occurrence of p would guarantee q. The proposition p is the antecedent, and q is the consequent.

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

Two useful related forms of an implication are:

• Converse: q → p
• Contrapositive: ¬q → ¬p

An implication is logically equivalent to its contrapositive, but generally not to its converse.

2. Truth Tables and Logical Classification

A truth table lists the truth value of a formula for every possible assignment of truth values to its component propositions. If a formula contains n distinct propositions, its truth table has 2^n rows.

For example, the truth table for implication is:

| p | q | p → q |

|---|---|---|

| T | T | T |

| T | F | F |

| F | T | T |

| F | F | T |

The formula p → q can also be rewritten as ¬p ∨ q. Both formulas have identical truth values in every row.

Consider the formula (p ∧ q) → p. Its truth table is:

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

|---|---|---|---|

| T | T | T | T |

| T | F | F | T |

| F | T | F | T |

| F | F | F | T |

A formula true under every interpretation is a tautology. A formula false under every interpretation is a contradiction. A formula true under some interpretations and false under others is a contingency.

For example, p ∨ ¬p is a tautology, p ∧ ¬p is a contradiction, and p ∧ q is a contingency. Tautologies are important in verification because they represent conditions guaranteed by logical structure rather than by a particular data set.

2.1 Precedence and Parentheses

To avoid ambiguity, parentheses should be used. A common precedence convention is:

1. ¬

2. ∧

3. ∨ and ⊕

4. →

5. ↔

Thus ¬p ∨ q ∧ r is normally interpreted as (¬p) ∨ (q ∧ r). In professional specifications, explicit parentheses are preferable because different tools may use different conventions.

3. Logical Equivalence and Laws

Two formulas P and Q are logically equivalent, written P ≡ Q, if they have the same truth value under every interpretation. Equivalence can be established by constructing a truth table or by applying known equivalence laws.

Important laws include the following:

• Identity: p ∧ T ≡ p; p ∨ F ≡ p
• Domination: p ∨ T ≡ T; p ∧ F ≡ F
• Idempotence: p ∨ p ≡ p; p ∧ p ≡ p
• Double negation: ¬¬p ≡ p
• Complement: p ∨ ¬p ≡ T; p ∧ ¬p ≡ F
• Commutativity: p ∨ q ≡ q ∨ p; p ∧ q ≡ q ∧ p
• Associativity: (p ∨ q) ∨ r ≡ p ∨ (q ∨ r), with an analogous law for conjunction
• Distributivity: p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r); p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
• De Morgan’s laws: ¬(p ∧ q) ≡ ¬p ∨ ¬q; ¬(p ∨ q) ≡ ¬p ∧ ¬q
• Absorption: p ∨ (p ∧ q) ≡ p; p ∧ (p ∨ q) ≡ p
• Implication: p → q ≡ ¬p ∨ q
• Biconditional: p ↔ q ≡ (p → q) ∧ (q → p)

Worked Example 1: Simplifying a Formula

Simplify ¬(p → q) ∨ q.

Using the implication law:

¬(p → q) ∨ q ≡ ¬(¬p ∨ q) ∨ q.

By De Morgan’s law and double negation:

≡ (p ∧ ¬q) ∨ q.

Using distributivity:

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

The second factor is a tautology, so:

≡ p ∨ q.

Therefore, ¬(p → q) ∨ q ≡ p ∨ q.

4. Arguments and Rules of Inference

An argument consists of premises and a conclusion. It is valid if every interpretation that makes all premises true also makes the conclusion true. Validity concerns the structure of reasoning, not whether the premises are actually true in the real world. An argument that is valid and has true premises is sound.

A common way to represent an argument is:

P1, P2, ..., Pn ∴ C

The symbol ∴ means “therefore.”

Important inference rules include:

Modus ponens

p → q

p

∴ q

Modus tollens

p → q

¬q

∴ ¬p

Hypothetical syllogism

p → q

q → r

∴ p → r

Disjunctive syllogism

p ∨ q

¬p

∴ q

Conjunction

p

q

∴ p ∧ q

Simplification

p ∧ q

∴ p

Two frequent invalid patterns are:

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

For example, “If the server is overloaded, response time increases. Response time increased. Therefore, the server is overloaded” is not valid: other causes may explain the increased response time.

4.1 Testing Validity with Satisfiability

An argument with premises P1, ..., Pn and conclusion C is valid exactly when the formula

(P1 ∧ ... ∧ Pn) → C

is a tautology. Equivalently, the formula

P1 ∧ ... ∧ Pn ∧ ¬C

must be unsatisfiable. This connection is central to automated theorem proving and SAT-based verification.

5. Predicate Logic

Propositional logic treats statements as indivisible units. Predicate logic provides internal structure. A predicate is a property or relation that becomes a proposition when appropriate objects are substituted for its variables.

For example, Student(x) may mean “x is a student,” and Enrolled(x, c) may mean “x is enrolled in course c.” If a is a particular student, Student(a) is a proposition.

The main components of predicate logic are:

• Constants: names for particular objects, such as Alice or course101
• Variables: symbols such as x, y, and z whose values may vary
• Predicates: properties or relations, such as Skilled(x) or Likes(x, y)
• Functions: mappings from objects to objects, such as Manager(x)
• Quantifiers: symbols that specify how widely a statement applies

A domain of discourse is the collection of objects being considered. The same formula may have different meanings under different domains.

5.1 Universal and Existential Quantifiers

The universal quantifier, ∀, means “for every.” The formula

∀x Student(x) → HasID(x)

should be parenthesized as:

∀x (Student(x) → HasID(x)).

It states that every student has an identification record.

The existential quantifier, ∃, means “there exists at least one.” The formula

∃x (Student(x) ∧ HasID(x))

states that at least one object is both a student and an object with an identification record.

Quantifier scope is essential. Compare:

∀x ∃y Advises(y, x)

with:

∃y ∀x Advises(y, x).

The first says every person is advised by someone, possibly a different person for each individual. The second says there is one person who advises everyone. These formulas are not generally equivalent.

5.2 Translating English into Predicate Logic

Translation requires identifying the domain, predicates, and quantifier scope.

“Every employee uses a secure password” can be represented as:

∀x (Employee(x) → UsesSecurePassword(x)).

“Some employee does not use a secure password” can be represented as:

∃x (Employee(x) ∧ ¬UsesSecurePassword(x)).

“No employee uses a shared password” can be represented as:

∀x (Employee(x) → ¬UsesSharedPassword(x)).

An equivalent form is:

¬∃x (Employee(x) ∧ UsesSharedPassword(x)).

“Every analyst has a manager” is:

∀x (Analyst(x) → ∃y ManagerOf(y, x)).

The phrase “exactly one” requires both existence and uniqueness. “There is exactly one administrator” may be represented by:

∃x (Administrator(x) ∧ ∀y (Administrator(y) → y = x)).

5.3 Negating Quantified Statements

Quantifiers reverse under negation:

¬∀x P(x) ≡ ∃x ¬P(x)

¬∃x P(x) ≡ ∀x ¬P(x)

Therefore, “It is not true that every model passed the test” means “At least one model did not pass the test,” not “No model passed the test.”

For example:

¬∀x (Device(x) → Secure(x))

is equivalent to:

∃x ¬(Device(x) → Secure(x))

and hence to:

∃x (Device(x) ∧ ¬Secure(x)).

This transformation is particularly important in requirements analysis, where an incorrectly negated condition can reverse a safety or security requirement.

6. Normal Forms

Normal forms place formulas into standardized structural patterns. They support comparison, automated reasoning, circuit design, and SAT solving.

A formula is in negation normal form (NNF) if it uses only ∧, ∨, and ¬, with negation applied directly to atomic propositions. To convert a formula to NNF:

1. Eliminate → and ↔.

2. Push negations inward using De Morgan’s laws.

3. Eliminate double negations.

A formula is in disjunctive normal form (DNF) if it is a disjunction of conjunctions of literals. A literal is a proposition or its negation. For example:

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

is in DNF.

A formula is in conjunctive normal form (CNF) if it is a conjunction of disjunctions of literals. For example:

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

is in CNF.

Worked Example 2: Conversion to CNF

Convert p → (q ∧ r) to CNF.

First remove implication:

p → (q ∧ r) ≡ ¬p ∨ (q ∧ r).

Apply distributivity:

¬p ∨ (q ∧ r) ≡ (¬p ∨ q) ∧ (¬p ∨ r).

Thus the CNF is:

(¬p ∨ q) ∧ (¬p ∨ r).

CNF is especially important because a SAT instance is commonly represented as a conjunction of clauses, where each clause is a disjunction of literals.

6.1 Tseitin Transformation

Direct conversion to CNF can cause an exponential increase in formula size. A practical alternative is the Tseitin transformation, which introduces fresh variables representing subformulas. It produces a CNF formula equisatisfiable with the original formula, usually with only linear growth in size.

“Equisatisfiable” means that the two formulas are either both satisfiable or both unsatisfiable; it does not necessarily mean that they have identical truth values under the same assignments to the original variables.

7. Satisfiability and SAT Solving

A formula is satisfiable if at least one interpretation makes it true. It is unsatisfiable if no interpretation does so. A satisfying interpretation is called a model of the formula.

For example, (p ∨ q) ∧ ¬p is satisfiable because p = false and q = true satisfies it. The formula p ∧ ¬p is unsatisfiable.

The Boolean satisfiability problem, or SAT, asks whether a propositional formula has a satisfying assignment. SAT was the first problem proved NP-complete, meaning that proposed solutions can be verified efficiently and that every problem in NP can be transformed into SAT in polynomial time.

Modern SAT solvers commonly use conflict-driven clause learning (CDCL). A simplified view of CDCL is:

1. Select a variable and assign a value.

2. Propagate consequences of the assignment.

3. Detect a conflict if a clause becomes false.

4. Analyze the conflict and learn a new clause preventing the same problematic combination.

5. Backtrack to an appropriate earlier decision.

6. Repeat until a model is found or unsatisfiability is proved.

SAT solving is used in scheduling, hardware verification, configuration, planning, test generation, and software analysis. Predicate-logic problems are generally more expressive but computationally harder. Restricted fragments, finite domains, and transformations into propositional form make automated reasoning feasible in many applications.

8. Logic in AI and Formal Specification

Logic-based knowledge representation stores facts and rules in a form that supports inference. A small expert system might contain:

Bird(Tweety)

∀x (Bird(x) ∧ Healthy(x) → CanFly(x))

Healthy(Tweety)

From these facts, a reasoning system can infer CanFly(Tweety), assuming the rule and its predicates accurately represent the domain.

Logic is also used to specify system requirements. For example:

∀x (Request(x) → Eventually(Response(x)))

expresses a response obligation, although the phrase “eventually” belongs more naturally to temporal logic than ordinary first-order logic. This illustrates an important modeling issue: selecting a logic whose expressive power matches the requirement.

In software verification, assertions may be translated into logical conditions. A program path is unsafe if its path condition together with the negation of a safety property is satisfiable. If the resulting formula is unsatisfiable, that path cannot violate the property under the stated assumptions.

In machine learning, logic may complement statistical models. A classifier can assign probabilities, while logical constraints can enforce consistency, such as requiring a prediction to satisfy legal, physical, or organizational rules. However, hard logical constraints can be brittle when data are noisy or predicates are uncertain. Hybrid neuro-symbolic systems therefore combine learned representations with symbolic reasoning.

9. Illustrative Case Study: Access-Control Verification

Background

Consider an illustrative university research platform. Users may access a confidential dataset only if they are authorized researchers, have completed security training, and connect through an approved device.

Problem

The platform specification is written informally:

“A user may download the dataset only when the user is an authorized researcher, has completed training, and uses an approved device. No guest account may download the dataset.”

Ambiguity in this requirement could lead to unauthorized access.

Analysis

Let:

• Researcher(x): x is a researcher
• Authorized(x): x is authorized
• Trained(x): x has completed training
• ApprovedDevice(x): x is using an approved device
• Guest(x): x is a guest account
• Download(x): x downloads the dataset

A direct formalization is:

∀x (Download(x) → (Researcher(x) ∧ Authorized(x) ∧ Trained(x) ∧ ApprovedDevice(x))).

The guest restriction is:

∀x (Guest(x) → ¬Download(x)).

If the organization instead intends to state that every authorized, trained researcher on an approved device must be allowed to download, the direction of implication would differ:

∀x ((Researcher(x) ∧ Authorized(x) ∧ Trained(x) ∧ ApprovedDevice(x)) → Download(x)).

These are not equivalent. The first is a necessary-condition rule: downloads cannot occur unless all conditions hold. The second is a sufficient-condition rule: whenever all conditions hold, a download must occur.

Approach and Solution

The engineering team should:

1. Define the domain and predicates explicitly.

2. Distinguish necessary conditions from sufficient conditions.

3. Add assumptions about identity, device association, and time validity.

4. Translate the policy into rules used by an access-control engine.

5. Test satisfiability of combinations of permissions and denials.

6. Check boundary cases, such as a user who is both a researcher and a guest.

If “guest” is intended to override all other permissions, the policy should include an explicit rule, such as:

∀x (Guest(x) → ¬Download(x)).

A conflict can arise if another rule implies Download(x) for the same individual. The policy should define precedence or ensure that such combinations are impossible.

Outcome

Formalization exposes ambiguities that natural language can conceal. A SAT or constraint solver can search for an assignment representing an unauthorized download. If such an assignment exists, it is a counterexample requiring policy revision. If the relevant violation formula is unsatisfiable, the formal model supports the claim that the specified rules prevent that class of violation.

Learning Points

The case demonstrates that logic is not merely a theoretical notation. It is a method for clarifying requirements, detecting contradictions, generating test cases, and supporting auditable enforcement. It also shows that correctness depends on the predicates and assumptions chosen by the modeler.

10. Limitations, Ethics, and Best Practices

Logic systems are precise but not automatically truthful. A conclusion may be valid while the premises are incomplete, outdated, biased, or factually wrong. Predicate definitions may encode organizational assumptions, and an apparently neutral rule can produce discriminatory outcomes when applied to unequal data or social conditions.

Classical logic uses two truth values and ordinarily does not represent uncertainty, vagueness, contradiction tolerance, or time. Probabilistic logic, fuzzy logic, paraconsistent logic, temporal logic, and non-monotonic logic address some of these limitations. They should be selected according to the problem rather than treated as interchangeable replacements.

Best practices include:

• Define the domain, symbols, and assumptions before formalization.
• Parenthesize formulas and document operator precedence.
• Separate necessary conditions from sufficient conditions.
• Test formulas with truth tables or automated tools where practical.
• Check edge cases, empty domains, contradictory rules, and quantifier scope.
• Preserve traceability from requirements to formal statements and tests.
• Treat solver output as evidence about the model, not as proof that the real system is correct.
• Review rules for privacy, fairness, accessibility, and legal compliance.
• Record versions of policies and knowledge bases so decisions are auditable.

Contemporary developments include SMT solving, which extends SAT with theories such as arithmetic and arrays; answer-set programming for non-monotonic reasoning; knowledge graphs combining graph structure with logical constraints; and neuro-symbolic AI, which integrates learned models with formal rules. These developments increase capability but do not remove the need for careful modeling and human oversight.

Chapter Summary

Propositional logic represents whole statements using logical connectives, while predicate logic represents objects, properties, relations, and quantified claims. Truth tables provide a complete semantic method for evaluating formulas and classifying them as tautologies, contradictions, or contingencies. Logical equivalence permits formulas to be rewritten without changing their meaning, and inference rules provide valid patterns for deriving conclusions.

Predicate logic introduces constants, variables, predicates, functions, and universal and existential quantifiers. Correct quantifier scope and careful negation are essential for accurate translation of natural-language requirements. Normal forms, particularly CNF and DNF, support automated reasoning. Satisfiability asks whether a formula has a model and forms the basis of SAT solving, verification, planning, and configuration.

In AI and software engineering, logic supports knowledge representation, policy specification, access control, testing, and formal verification. Its effectiveness depends on appropriate predicates, complete assumptions, and careful interpretation. Logical validity does not guarantee that a model reflects reality, so ethical review, documentation, and governance remain necessary.

Key Terms

Proposition: A declarative statement with exactly one truth value.

Predicate: A property or relation that becomes a proposition when its arguments are specified.

Logical connective: An operator used to combine or modify propositions.

Interpretation: An assignment of meanings or truth values to symbols.

Tautology: A formula true under every interpretation.

Contradiction: A formula false under every interpretation.

Contingency: A formula true under some interpretations and false under others.

Logical equivalence: Equality of truth values under every interpretation.

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

Contrapositive: The formula ¬q → ¬p associated with p → q.

Argument validity: The property that true premises cannot lead to a false conclusion.

Domain of discourse: The collection of objects quantified over in predicate logic.

Universal quantifier: The symbol ∀, meaning “for every.”

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

Literal: A proposition or its negation.

CNF: Conjunctive normal form, a conjunction of disjunctive clauses.

DNF: Disjunctive normal form, a disjunction of conjunctive terms.

Satisfiable: True under at least one interpretation.

Model: An interpretation that satisfies a formula.

SAT solver: An algorithmic system that determines whether a propositional formula is satisfiable.

Review Questions

Short Answer Questions

1. What distinguishes a proposition from a non-propositional sentence?

2. Define tautology, contradiction, and contingency.

3. State De Morgan’s laws for conjunction and disjunction.

4. What is the difference between a universal and an existential quantifier?

5. Why is CNF important in SAT solving?

Long Answer Questions

1. Explain implication, converse, and contrapositive, and show why an implication is equivalent to its contrapositive but not generally to its converse.

2. Describe how truth tables can be used to test logical equivalence and argument validity.

3. Explain the syntax and semantics of predicate logic, including constants, variables, predicates, functions, and quantifiers.

4. Convert a propositional formula to CNF and discuss why direct conversion can cause formula-size growth.

5. Discuss the role of propositional and predicate logic in AI knowledge representation and formal software specification.

Analytical / Application Questions

1. Formalize the statement “Every authenticated employee may access the internal system only if the employee has valid training,” and explain whether the resulting implication expresses a necessary or sufficient condition.

2. Determine whether the following argument is valid: If a model is overfitted, its test error increases. The test error increased. Therefore, the model is overfitted. Justify your answer using an inference pattern or counterexample.

3. Design a logical access-control policy for a health-data system involving clinicians, training, emergency access, and guest users. Identify at least one possible conflict and explain how a satisfiability check could reveal it.

Multiple Choice Questions with Answers

Question 1

Which formula is a tautology?

A. p ∧ ¬p

B. p ∨ ¬p

C. p ∧ q

D. p → ¬p

Correct Answer: B. p ∨ ¬p

Question 2

When is p → q false?

A. When p and q are both true

B. When p is false and q is true

C. When p is true and q is false

D. When p and q are both false

Correct Answer: C. 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: B. ¬p ∨ q

Question 4

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

A. Modus tollens

B. Disjunctive syllogism

C. Modus ponens

D. Hypothetical syllogism

Correct Answer: C. Modus ponens

Question 5

Which formula means that at least one object has property P?

A. ∀x P(x)

B. ¬∀x P(x)

C. ∃x P(x)

D. ∀x ¬P(x)

Correct Answer: C. ∃x P(x)

Question 6

Which is equivalent to ¬∀x P(x)?

A. ∀x ¬P(x)

B. ∃x ¬P(x)

C. ¬∃x ¬P(x)

D. ∃x P(x)

Correct Answer: B. ∃x ¬P(x)

Question 7

Which formula is in conjunctive normal form?

A. (p ∧ q) ∨ r

B. p ∨ (q ∧ r)

C. (p ∨ q) ∧ (¬p ∨ r)

D. ¬(p ∧ q)

Correct Answer: C. (p ∨ q) ∧ (¬p ∨ r)

Question 8

A propositional formula is satisfiable when:

A. It is true under every interpretation

B. It is false under every interpretation

C. It is true under at least one interpretation

D. It contains no negations

Correct Answer: C. It is true under at least one interpretation

Question 9

Which argument pattern is generally invalid?

A. p → q, p, therefore q

B. p → q, ¬q, therefore ¬p

C. p ∨ q, ¬p, therefore q

D. p → q, q, therefore p

Correct Answer: D. p → q, q, therefore p

Question 10

What is the main purpose of a Tseitin transformation?

A. To replace predicate logic with probability theory

B. To produce an equisatisfiable CNF formula efficiently

C. To make every formula a tautology

D. To eliminate all variables from a formula

Correct Answer: B. To produce an equisatisfiable CNF formula efficiently