Propositional logic

1. Propositional Logic

Propositional Logic is the foundational system in formal reasoning where statements are expressed as simple propositions that can be either true or false. Each proposition is treated as an indivisible unit. These statements cannot be broken down into smaller parts. Often represented with symbols like

Symbols: P,Q,R,...

Connectives: AND (∧), OR (∨), NOT (¬), IMPLIES (→).

These symbols and connectives allow us to combine these propositions and build more complex expressions. However, propositional logic does not look inside the structure of a statement—it only works with entire sentences as atomic entities.

Example 1 – Weather:

P: "It is raining."

Q: "The ground is wet."

P: >Expression: P → Q; P implies (right arrow) Q means "If it is raining, then the ground is wet."

Example 2 – Classroom:

R: "The projector is working."

S: "The lecture will start."

Expression: R ∧ S; R and S means "The projector is working AND the lecture will start."

Here, we only know whether each full sentence is true or false, but we cannot talk about which object is raining on, or who is giving the lecture.

2. First-Order Logic (FOL)

First-Order Logic (FOL), also known as Predicate Logic, extends this framework by allowing reasoning about the internal structure of statements. First-Order Logic expands on propositional logic by introducing objects, predicates, and quantifiers. Instead of treating each sentence as indivisible, FOL introduces:

Objects: individual entities in the domain of discourse.

Predicates: properties or relationships among objects (e.g., is Student(x), teaches(x, y)).

Quantifiers: tools to express generality, Such as:

→ Universal quantifier (∀): “For all”

→ Existential quantifier (∃): “There exists”

Example 1 – Mortality of Humans:

Predicate: Human(x), Mortal(x)

Rule: ∀x,Human(x) → Mortal(x) (All humans are mortal)

Fact: Human(Socrates)

Inference: Mortal(Socrates)

This shows how FOL can reason about individuals, not just whole sentences.

Example 2 – Classroom Relation:

Predicate: Teaches(Prof,Course), Student(y)

Statement: ∀y,Student(y) → ∃z,Teaches(z,y) → “Every student has at least one teacher.”

Example 3 – Library System:

Predicate: Borrowed(x,y) → “x borrowed y”

Statement: ∃x∃y:Borrowed(x,y) → “There exists at least one person who borrowed a book.”

This richer representation allows us to capture knowledge more precisely. For example:

In propositional logic, we might write P to mean “Socrates is mortal.”

In first-order logic, we can express it as ∀x,Human(x)→ Mortal(x) and then assert Human(Socrates). From this, logical inference can conclude Mortal(Socrates).

Thus, while propositional logic deals only with true/false values of entire sentences, first-order logic enables reasoning about individuals, their properties, and their relationships—making it far more powerful for knowledge representation and problem solving in fields such as mathematics, computer science, and artificial intelligence.

Key Difference (with Examples):

Aspect	Propositional Logic	First-Order Logic
Basic unit	Whole statements (true/false)	Objects + Predicates
Quantification	Not possible	Uses ∀ and ∃
Example	P: "Socrates is mortal."	∀x, Human(x) → Mortal(x))
Limitation	Cannot express relations or general rules	Can express rules, properties, and relationships