Skip to content

LOGIC IN COMPUTER SCIENCE – QUICK REVISION GUIDE

1️⃣ Introduction to Logic

Logic = formal way to reason correctly.

Used in:

  • Program correctness
  • AI reasoning
  • Databases
  • Verification & model checking

Two main types:

  • Propositional Logic (PL) → deals with true/false statements
  • Predicate Logic (FOL) → adds variables & quantifiers

📌 Exam tip: Always distinguish syntax vs semantics.

2️⃣ Declarative Sentences

A declarative sentence:

  • States a fact
  • Has a truth value (T/F)

✅ Examples:

  • “2 is even” → T
  • “x > 3” → ❌ (not declarative unless x defined)

In PL:

  • Represented by symbols: p, q, r

📌 Non-declarative: commands, questions, emotions.

3️⃣ Natural Deduction (ND)

🔹 Part A: Rules

Used to prove validity.

Common rules (from your sheet):

  • ∧e (and elimination)
  • ∧i (and introduction)
  • →e (modus ponens)
  • →i (implication introduction)
  • ¬i (negation intro)
  • ⊥e (contradiction)

Example: From p → q and p, derive q (→e)

🔹 Part B: Proof Structure

To prove ⊢ p → q:

  1. Assume p
  2. Derive q
  3. Discharge assumption → p → q

📌 Exam trick: For implication proofs → assume LHS.

4️⃣ Propositional Logic as a Formal Language

PL = (Alphabet + Syntax + Well-formed formulas)

Alphabet:

  • Propositions: p, q
  • Connectives: ¬ ∧ ∨ →
  • Brackets: ( )

WFF examples:

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

📌 Binding order:

¬ > ∧ > ∨ > →

5️⃣ Semantics (Meaning)

Semantics = truth under an interpretation

Truth Assignment:

V(p) = T or F

Example:

Formula: ¬p ∧ q

p q Result
T T F
F T T

📌 Validity: True in all interpretations 📌 Satisfiable: True in some interpretation

6️⃣ Soundness & Completeness

Very important theory question.

  • Soundness: If ⊢ φ then ⊨ φ (Proofs don’t prove false things)

  • Completeness: If ⊨ φ then ⊢ φ (All truths are provable)

📌 One line memory:

Sound = no false proofs Complete = no missing truths

7️⃣ Normal Forms

Used in SAT & logic simplification.

🔹 CNF (Conjunctive Normal Form)

  • AND of ORs Example:
(p ∨ q) ∧ (¬p ∨ r)

🔹 DNF (Disjunctive Normal Form)

  • OR of ANDs Example:
(p ∧ q) ∨ (¬p ∧ r)

📌 Steps to convert:

  1. Remove →
  2. Push ¬ inside
  3. Distribute

8️⃣ Horn Clauses

Special CNF with at most one positive literal.

Forms:

  • Fact: p
  • Rule: p ∧ q → r
  • Goal: ¬p

Used in:

  • Prolog
  • Logic programming

📌 Example:

¬p ∨ ¬q ∨ r

9️⃣ Predicate Logic (FOL)

🔹 Part 1: Basics

  • Predicates: P(x)
  • Domain
  • Constants, variables

Example:

P(x): x is even

🔹 Part 2: Quantifiers

  • ∀x → “for all”
  • ∃x → “there exists”

Examples:

∀x (x > 0 → x² > 0)
∃x (x² = 4)

🔹 Part 3: Negation Rules

Very common exam trick!

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

🔹 Part 4: Models & Satisfaction

Given:

  • Domain
  • Interpretation of predicates

Check:

∀x ∃y P(x,y) ∧ Q(y,x)

📌 Method: Fix x → try all y → check relation tables.

🔟 Verification by Model Checking

Automatic verification of systems.

Given:

  • States
  • Transitions
  • Labels
  • LTL formula

Check if formula holds from initial state.

Example:

G(p → F q)

Meaning: “Whenever p happens, q eventually happens.”

📌 LTL operators:

  • G = always
  • F = eventually
  • X = next

1️⃣1️⃣ Program Verification (Hoare Logic)

Form:

{P} C {Q}

Example:

{y = 5}
y := y + 2
{y = 7}

Array question:

  • Pre: n > 0
  • Post: sum = sum of even elements

📌 Key idea: invariant thinking

1️⃣2️⃣ ALM – Modal Logic & LTL

Modal logic talks about time & necessity.

Operators:

  • □p → always p
  • ◇p → eventually p

LTL grammar validity:

  • Atomic → valid
  • Xφ, Fφ, Gφ → valid
  • φ U ψ → valid

📌 Invalid if grammar rules violated.

🎯 LAST 30-MINUTE STRATEGY

✔ Revise:

  • Quantifier negations
  • ND implication proofs
  • CNF / Horn clause pattern
  • LTL operators meaning

✔ In exam:

  • Write steps, even if unsure
  • Draw truth tables
  • Clearly state assumptions

Comments