Applications of Propositional Logic

Introduction

Propositional logic is not just a theoretical concept—it has numerous practical applications in computer science, digital electronics, artificial intelligence, and everyday reasoning. Understanding these applications helps us see why propositional logic is fundamental to modern technology.

1. Translating English Sentences to Propositional Logic

One of the most important skills is converting natural language statements into logical expressions.

Example 1: Simple Translation

English: “If it rains, then the match will be cancelled.”

Translation:

  • Let p = “It rains”
  • Let q = “The match will be cancelled”
  • Logical form: p → q

Example 2: Complex Translation

English: “You can take the course if you have completed the prerequisites and have permission from the instructor.”

Translation:

  • Let p = “You have completed the prerequisites”
  • Let q = “You have permission from the instructor”
  • Let r = “You can take the course”
  • Logical form: (p ∧ q) → r

Example 3: Negation in Translation

English: “The system will not work unless the battery is charged.”

Translation:

  • Let p = “The battery is charged”
  • Let q = “The system will work”
  • Logical form: ¬p → ¬q OR q → p

Example 4: Either…Or

English: “Either you study hard or you will fail the exam.”

Translation:

  • Let p = “You study hard”
  • Let q = “You will fail the exam”
  • Logical form: ¬p → q OR p ∨ q

2. System Specifications

Propositional logic is used to specify how systems should behave.

Example: Access Control System

Specification: “A user can access the file if the user is an administrator or if the user is the owner and has read permission.”

Translation:

  • Let a = “User is an administrator”
  • Let o = “User is the owner”
  • Let r = “User has read permission”
  • Let f = “User can access the file”
  • Logical form: (a ∨ (o ∧ r)) → f

Example: Alarm System

Specification: “The alarm sounds if a door is opened and the system is armed, or if motion is detected and the system is armed.”

Translation:

  • Let d = “Door is opened”
  • Let m = “Motion is detected”
  • Let s = “System is armed”
  • Let a = “Alarm sounds”
  • Logical form: ((d ∧ s) ∨ (m ∧ s)) → a
  • Simplified: ((d ∨ m) ∧ s) → a

3. Boolean Searches

Search engines and databases use propositional logic for queries.

Query: Find documents containing “Python” AND “Programming”

  • p = Document contains “Python”
  • q = Document contains “Programming”
  • Search logic: p ∧ q

Query: Find documents containing “Java” AND (“Programming” OR “Development”) but NOT “JavaScript”

  • j = Document contains “Java”
  • p = Document contains “Programming”
  • d = Document contains “Development”
  • s = Document contains “JavaScript”
  • Search logic: j ∧ (p ∨ d) ∧ ¬s

4. Logic Puzzles and Reasoning

Propositional logic helps solve complex reasoning problems.

Example: Three Suspects

Problem: Three suspects (Alice, Bob, and Charlie) are questioned about a robbery. They make the following statements:

  • Alice: “Bob did it.”
  • Bob: “Charlie did it.”
  • Charlie: “Bob is lying.”

If only one person is telling the truth, who committed the robbery?

Solution:

  • Let a = “Alice is telling the truth”
  • Let b = “Bob is telling the truth”
  • Let c = “Charlie is telling the truth”

If Alice is truthful: Bob did it (but then Charlie is also truthful - contradiction) If Bob is truthful: Charlie did it (but then Charlie’s statement is false - consistent) If Charlie is truthful: Bob is lying, meaning Charlie didn’t do it

Answer: Charlie committed the robbery (when Bob is the only one telling the truth).

5. Circuit Design (Digital Logic)

Propositional logic forms the basis of digital circuits.

Example: Half Adder

A half adder adds two binary digits and produces a sum and carry.

Inputs: A, B Outputs:

  • Sum (S): A ⊕ B (XOR)
  • Carry (C): A ∧ B (AND)

Truth Table:

ABSum (A ⊕ B)Carry (A ∧ B)
0000
0110
1010
1101

6. Software Verification

Propositional logic is used to verify that software meets its specifications.

Example: Login System

Requirement: “A user is logged in if and only if they have entered a valid username and a valid password.”

Translation:

  • Let u = “Valid username entered”
  • Let p = “Valid password entered”
  • Let l = “User is logged in”
  • Logical form: l ↔ (u ∧ p)

This can be verified in code:

if (validUsername AND validPassword):
    userLoggedIn = True
else:
    userLoggedIn = False

7. Artificial Intelligence

AI systems use propositional logic for knowledge representation and reasoning.

Example: Expert System

Knowledge Base:

  1. “If the patient has fever and cough, then the patient might have flu.”
  2. “If the patient has flu, then prescribe rest and fluids.”

Translation:

  • f = “Patient has fever”
  • c = “Patient has cough”
  • l = “Patient might have flu”
  • r = “Prescribe rest and fluids”

Rules:

  1. (f ∧ c) → l
  2. l → r

Chained reasoning: (f ∧ c) → r

8. Conditional Statements in Programming

All if-then-else statements in programming are based on propositional logic.

Example: Grade Calculation

if (score >= 90):
    grade = 'A'
elif (score >= 80 and score < 90):
    grade = 'B'
else:
    grade = 'C'

Logical form:

  • Let p = “score ≥ 90”
  • Let q = “score ≥ 80 and score < 90”
  • Logic: If p then A, else if q then B, else C

Law and contracts often use logical structures.

Example: Contract Clause

Clause: “The warranty is void if the product is damaged by water or if the seal is broken.”

Translation:

  • Let w = “Product damaged by water”
  • Let s = “Seal is broken”
  • Let v = “Warranty is void”
  • Logical form: (w ∨ s) → v

10. Database Queries (SQL)

SQL queries use logical operators.

Example: Employee Database

Query: “Find all employees who work in IT department AND have salary greater than 50000, OR work as managers.”

SELECT * FROM Employees
WHERE (department = 'IT' AND salary > 50000) OR position = 'Manager'

Logical form:

  • i = “Works in IT”
  • s = “Salary > 50000”
  • m = “Position is Manager”
  • Query logic: (i ∧ s) ∨ m

Key Points for Exams

  1. Always identify propositional variables clearly before translating
  2. “Unless” means “if not” - “A unless B” = “¬B → A” or “A ∨ B”
  3. “Only if” is different from “if” - “A only if B” = “A → B”
  4. “If and only if” means biconditional - use ↔
  5. “Either…or” can mean inclusive OR (∨) or exclusive OR (⊕) - check context
  6. Parentheses matter in complex expressions
  7. Practice translating both ways - English to logic and logic to English

Practice Problems

  1. Translate: “You cannot pass the exam unless you study hard.”

  2. Translate: “The server will restart if there is an error or if the administrator requests it.”

  3. Write a Boolean search query for: Documents containing “machine learning” but not containing “deep learning” or “neural networks”.

  4. Create a logical specification for: “A student gets a scholarship if they have GPA above 3.5 and participate in extracurricular activities.”

  5. A company policy states: “An employee gets a bonus if they complete the project on time and exceed the quality standards, or if they bring in a new client.” Express this in propositional logic.