Propositional Logic Fundamentals

Introduction to Propositional Logic

Propositional logic forms the backbone of many artificial‑intelligence algorithms and computer‑science reasoning techniques. By mastering the basic logical connectives—and (∧), or (∨), not (¬), implies (→), and if and only if (↔)—you’ll be able to model complex statements, verify program correctness, and design intelligent agents.

1. Conjunction (∧)

What is a conjunction?

A conjunction combines two propositions p and q into a single statement p ∧ q. The combined statement is true only when both p and q are true. In every other case—if either one is false or both are false—the conjunction evaluates to false.

Truth Table

• T ∧ T = T
• T ∧ F = F
• F ∧ settings = F

Mnemonic & Visual Aid

“AND needs ALL” – think of two light switches that must both be on for the lamp to glow. This visual metaphor helps you quickly recall that a conjunction fails if any component fails.

2. Implication (→)

Understanding the conditional

An implication p → q reads “if p then q”. Its truth value is false only when p is true and q is false; in all other cases it is true. This sometimes counter‑intuitive rule stems from the idea that a promise is only broken when the antecedent occurs without the consequent.

Example

Given p = true and q = false, the implication p → q is false. This matches the quiz answer.

Memory Tip

Remember the phrase “A true antecedent demands a true consequent”. If the antecedent is baklava (true) but the consequent is missing, the implication fails.

3. Contrapositive of a Conditional

Definition

The contrapositive flips the antecedent and consequent and negates both. Formally, the contrapositive of P → Q is ¬Q → ¬P. Importantly, a conditional and its contrapositive are logically equivalent—they have identical truth tables.

Quiz Illustration

Original statement: “If the system is full, then the reply cannot be sent.”
Identify P = “system is full” and Q = “reply cannot be sent”.
Contrapositive: “If the system is not full, then the reply can be sent.”

Mnemonic

Use FNFN (Flip‑Negate‑Flip‑Negate) to remember the transformation.

4. Bitwise XOR (⊕)

Operation Overview

The exclusive‑or returns 1 when the two input bits differ and 0 when they are the same. It is often used in error‑detection, cryptography, and parity checks.

Example Calculation

With x = 1 and y = 1, the XOR yields 0 because the bits are identical.

Quick Check

• 1 ⊕ 0 = 1
• 0 ⊕ 1 = 1
• 0 ⊕ 0 = 0
• 1 ⊕ 1 = 0

5. Tautologies and Contradictions

What is a tautology?

A tautology is a compound proposition that is true under every possible truth assignment. The classic example is the law of excluded middle: p ∨ ¬p.

Identifying a Tautology

From the quiz options, only p ∨ ¬p** is always true, making it the sole tautology.

Why Tautologies Matter

They serve as foundational proof steps in formal verification and are used to simplify logical expressions without changing meaning.

6. Operator Precedence in Propositional Logic

Standard Precedence Order

When multiple connectives appear without explicit parentheses, the following hierarchy is commonly adopted:

• ¬ (negation) – highest
• ∧ (conjunction)
• ∨ (disjunction)
• → (implication)
• ↔ (biconditional) – lowest

Applying the Rule

For the expressioncoordinates ¬p ∧ q, first negate p (producing ¬p), then combine the result with q using ∧. The final expression is (¬p) ∧ q.

Common Pitfalls

Never assume that ¬ applies to the whole expression unless parentheses dictate it. Misreading precedence leads to incorrect truth‑table construction.

7. Translating Natural Language to Logical Formulas

Step‑by‑Step Translation

Take the sentence: “You cannot ride the roller coaster if you are under 4 feet tall and not older than 16 years old.”
Identify atomic propositions:

• r: you are under 4 feet tall
• s: you are not older than 16 years
• q: you can ride the roller coaster

Why the Other Options Fail

• Reversing the direction (q → …) changes the logical relationship.
• Negating the whole antecedent (¬(r ∧ ¬s) → q) states the opposite condition.
• Placing ¬ on the consequent without the proper antecedent (¬q → (r ∧ ¬s)) misrepresents the conditional.

8. Biconditional (↔) Truth Evaluation

Definition

The biconditional p ↔ q is true when both propositions share the same truth value—both true or both false. It is false when the truth values differ.

Example

Given p = true and q = false, the biconditional evaluates to false. This matches the quiz answer.

Memory Aid

Think of ↔ as “if and only if”; it requires a perfect match.

9. Consolidated Study Guide

<、「
• Conjunction (∧): true only when both components are true.
• Implication (→): false only when antecedent is true and consequent false.
• Contrapositive: flip and negate both sides; logically equivalent to the original conditional.
• Bitwise XOR (⊕): true when inputs differ.
• Tautology: always true; e.g., p ∨ ¬p.
• Operator precedence: ¬ > ∧ > ∨ > → > ↔.
• Translation: map natural‑language clauses to atomic symbols, then apply the correct connective.
• Biconditional (↔): true when both sides share the same truth value.

Use these core concepts as a checklist when tackling exam questions or designing logical circuits in AI systems.

10. Frequently Asked Questions (FAQ)

Can a false antecedent make an implication true?

Yes. In propositional logic, any implication with a false antecedent is automatically true, regardless of the consequent’s truth value.

Why is p ∨ ¬p considered a tautology?

Because for any truth assignment to p, either p is true or its negation is true, guaranteeing the disjunction is always true.

Is the contrapositive always equivalent to the original conditional?

Exactly. Both statements share identical truth tables, making them interchangeable in proofs.