Propositional Logic in Artificial Intelligence

Propositional Logic is one of the fundamental techniques used in Knowledge Representation and Reasoning in Artificial Intelligence.

It provides a formal way to represent facts about the world and determine whether conclusions logically follow from those facts.

1. What is Propositional Logic?

Definition

Propositional Logic is a formal system of logic in which knowledge is represented using propositions that can have one of two truth values: True or False. Propositions are combined using logical operators such as AND, OR, NOT, IMPLIES, and IF AND ONLY IF.

In simple words:

Propositional Logic represents statements as True or False and uses logical rules to derive conclusions from those statements.

Example

Consider:

P = “It is raining.”
Q = “The road is wet.”

We can write:\[ P \rightarrow Q \]

Meaning:

If it is raining, then the road is wet.

If:\[ P = True \]

then, using the rule, we can conclude:\[ Q = True \]

2. Why is Propositional Logic Important in AI?

An AI system needs to represent knowledge about the world.

For example, a medical AI might have:

Patient has fever.
Patient has cough.
Fever and cough may indicate flu.

These facts and rules can be represented logically.

The basic process is:

             Real World
                 |
                 ↓
             Facts
                 |
                 ↓
       Propositional Logic
                 |
                 ↓
        Knowledge Base
                 |
                 ↓
             Inference
                 |
                 ↓
           New Conclusion

Thus, propositional logic provides a foundation for automated reasoning.

3. What is a Proposition?

A proposition is a declarative statement that is either True or False, but not both.

Examples

Statement	Proposition?	Reason
Delhi is in India.	Yes	Can be True/False
2 + 2 = 4.	Yes	True
5 > 10.	Yes	False
It is raining.	Yes	True or False
Close the door.	No	Command
What is your name?	No	Question
Wow!	No	Exclamation

Important point

A proposition must have a definite truth value.

4. Propositional Variables

Instead of repeatedly writing complete sentences, we use symbols.

For example:

P = It is raining.
Q = The road is wet.
R = I carry an umbrella.

Each variable represents a proposition.

Each variable can have one of two values:\[ P \in \{True, False\} \]

or:\[ P \in \{T,F\} \]

5. Simple and Compound Propositions

Simple Proposition

A proposition that cannot be divided into smaller propositions using logical connectives.

Example:

“It is raining.”

Represent it as:\[ P \]

Compound Proposition

A proposition formed by combining two or more propositions.

Example:

“It is raining AND the road is wet.”

Represent it as:\[ P \land Q \]

where:

P = It is raining
Q = Road is wet

6. Logical Connectives

The main logical operators are:

NOT
AND
OR
IMPLIES
BICONDITIONAL

These operators allow us to construct complex logical statements.

7. NOT — Negation

Symbol:\[ \neg P \]

or sometimes:\[ \sim P \]

Meaning:

NOT P

If:\[ P = True \]

then:\[ \neg P = False \]

Truth table

P	¬P
T	F
F	T

Example

P = “It is raining.”\[ \neg P \]

means:

“It is not raining.”

8. AND — Conjunction

Symbol:\[ P \land Q \]

Meaning:

P AND Q

The result is True only when both propositions are True.

Truth table

P	Q	P ∧ Q
T	T	T
T	F	F
F	T	F
F	F	F

Example

P = Student attends class.

Q = Student submits assignment.\[ P \land Q \]

means:

The student attends class AND submits the assignment.

Both conditions must be true.

9. OR — Disjunction

Symbol:\[ P \lor Q \]

Meaning:

P OR Q

The result is False only when both P and Q are False.

Truth table

P	Q	P ∨ Q
T	T	T
T	F	T
F	T	T
F	F	F

Example

P = Student studies.

Q = Student practices.\[ P \lor Q \]

means:

The student studies OR practices.

In standard propositional logic, OR is inclusive OR—if both are true, the result is also true.

10. IMPLICATION — IF…THEN

Symbol:\[ P \rightarrow Q \]

Meaning:

If P, then Q.

It is also called implication or conditional.

Example:

If it rains, then the road becomes wet.

Let:

P = It rains.
Q = Road becomes wet.

Then:\[ P \rightarrow Q \]

Truth table

P	Q	P → Q
T	T	T
T	F	F
F	T	T
F	F	T

The only false case is:

P is True but Q is False.

Important exam point

Students often think:

If P is false, then P → Q must be false.

That is not correct in classical propositional logic.

For example:

If it rains, then I carry an umbrella.

If it does not rain, the implication itself is not violated.

11. Biconditional — IF AND ONLY IF

Symbol:\[ P \leftrightarrow Q \]

Meaning:

P if and only if Q.

It means P and Q have the same truth value.

Truth table

P	Q	P ↔ Q
T	T	T
T	F	F
F	T	F
F	F	T

Example:

A number is even if and only if it is divisible by 2.

12. Summary of Logical Operators

Operator	Symbol	Meaning
NOT	¬P	Not P
AND	P ∧ Q	P and Q
OR	P ∨ Q	P or Q
Implication	P → Q	If P then Q
Biconditional	P ↔ Q	P if and only if Q

Priority / precedence

A commonly used order is:\[ \neg \quad > \quad \land \quad > \quad \lor \quad > \quad \rightarrow \quad > \quad \leftrightarrow \]

Parentheses should be used whenever there is any possibility of ambiguity.

13. Truth Tables

A truth table lists all possible combinations of truth values for propositions and shows the resulting truth value of a logical expression.

For two propositions P and Q, there are:\[ 2^2 = 4 \]

possible combinations.

For three propositions:\[ 2^3 = 8 \]

possible combinations.

In general, for \(n\) propositions:\[ \boxed{2^n} \]

rows are required.

14. Example of a Compound Expression

Consider:\[ P \land (Q \lor R) \]

Suppose:

P = Student studies
Q = Student practices
R = Student attends lecture

Then:\[ P \land (Q \lor R) \]

means:

The student studies AND either practices OR attends the lecture.

Truth table

P	Q	R	Q ∨ R	P ∧ (Q ∨ R)
T	T	T	T	T
T	T	F	T	T
T	F	T	T	T
T	F	F	F	F
F	T	T	T	F
F	T	F	T	F
F	F	T	T	F
F	F	F	F	F

15. Knowledge Representation Using Propositional Logic

One of the most important applications in AI is Knowledge Representation.

Suppose we have the following facts:

It is raining.

If it is raining, the road is wet.

We can represent:\[ P = \text{It is raining} \]\[ Q = \text{Road is wet} \]

Knowledge:\[ P \]

and\[ P \rightarrow Q \]

Now the AI can infer:\[ Q \]

Therefore:

The road is wet.

16. Knowledge Base

A Knowledge Base (KB) is a collection of facts and rules represented in a formal language.

For example:

KB:

P
P → Q
Q → R

The AI can infer:

P
↓
Q
↓
R

So if:

P = It is raining.
Q = Road is wet.
R = Driving may be dangerous.

Then the AI can reason:

It is raining → road is wet → driving may be dangerous.

17. Inference in Propositional Logic

Inference is the process of deriving new conclusions from existing knowledge.

Example:

Given:\[ P \]

and:\[ P \rightarrow Q \]

we can infer:\[ Q \]

This is known as Modus Ponens.

General form

\[ P,\quad P\rightarrow Q \]

Therefore:\[ \boxed{Q} \]

18. Another Example of Inference

Knowledge:

If a student studies, then the student passes.
Ravi studies.

Represent:\[ Studies(Ravi) \]

and:\[ Studies(Ravi)\rightarrow Pass(Ravi) \]

Therefore:\[ Pass(Ravi) \]

The reasoning is:

Ravi studies
      +
If Ravi studies → Ravi passes
      ↓
Ravi passes

This is the basic idea behind logical reasoning in AI.

19. Entailment

An important concept in AI logic is entailment.

Symbol:\[ KB \models \alpha \]

It means:

The knowledge base KB logically entails statement α.

In simple terms:

If everything in the knowledge base is true, then α must also be true.

Example

Knowledge base:\[ P \]\[ P\rightarrow Q \]

Therefore:\[ KB \models Q \]

because Q necessarily follows from the knowledge.

20. Syntactic vs Semantic Concepts

Two important ideas are:

Syntax

Syntax specifies how expressions are written.

Example:\[ P \land Q \]

is syntactically valid.

Semantics

Semantics specifies what the expression means and how truth values are assigned.

For example:

P = It is raining
Q = Road is wet

Then:\[ P\land Q \]

means:

It is raining and the road is wet.

In short

Concept	Meaning
Syntax	Structure/form of expression
Semantics	Meaning/truth of expression

21. Tautology

A tautology is a proposition that is always true, regardless of the truth values of its components.

Example:\[ P \lor \neg P \]

This is always true.

P	¬P	P ∨ ¬P
T	F	T
F	T	T

This is also known as the Law of Excluded Middle.

22. Contradiction

A contradiction is a proposition that is always false.

Example:\[ P \land \neg P \]

P	¬P	P ∧ ¬P
T	F	F
F	T	F

It is impossible for P and NOT P to both be true in classical logic.

23. Contingency

A proposition is a contingency when it is sometimes true and sometimes false.

Example:\[ P \land Q \]

P	Q	P ∧ Q
T	T	T
T	F	F
F	T	F
F	F	F

It is true in some cases and false in others.

Therefore:

Tautology      → Always True
Contradiction  → Always False
Contingency    → Sometimes True, Sometimes False

24. Logical Equivalence

Two propositions are logically equivalent if they have the same truth value under every possible interpretation.

Symbol:\[ P \equiv Q \]

A famous example is De Morgan’s Law:\[ \neg(P\land Q)\equiv(\neg P\lor\neg Q) \]

and:\[ \neg(P\lor Q)\equiv(\neg P\land\neg Q) \]

These laws are important when converting logical expressions into different forms.

25. Important Logical Laws

Identity Laws

\[ P\land True \equiv P \]\[ P\lor False \equiv P \]

Domination Laws

\[ P\lor True \equiv True \]\[ P\land False \equiv False \]

Idempotent Laws

\[ P\lor P\equiv P \]\[ P\land P\equiv P \]

Double Negation

\[ \neg(\neg P)\equiv P \]

De Morgan’s Laws

\[ \boxed{\neg(P\land Q)\equiv\neg P\lor\neg Q} \]\[ \boxed{\neg(P\lor Q)\equiv\neg P\land\neg Q} \]

26. Propositional Logic and AI Reasoning

The basic AI reasoning process can be visualized as:

        WORLD
          |
          ↓
        Facts
          |
          ↓
   Propositional Logic
          |
          ↓
    Knowledge Base
          |
          ↓
       Inference
          |
          ↓
      New Facts
          |
          ↓
       Decision

For example, an AI system may have:

Fact:
It is raining.

Rule:
If it rains → road is wet.

Inference:
Road is wet.

Rule:
If road is wet → drive carefully.

Inference:
Drive carefully.

This shows how logical reasoning can support decision-making.

27. Advantages of Propositional Logic

1. Simple

It is easier to understand than more complex logic systems.

2. Formal

Statements have precise syntax and semantics.

3. Supports automated reasoning

Computers can use algorithms to determine logical consequences.

4. Useful for knowledge representation

Facts and rules can be stored in a knowledge base.

5. Foundation for AI logic

It provides a foundation for:

theorem proving
inference
expert systems
automated reasoning
planning
constraint solving

28. Limitations of Propositional Logic

This is particularly important when comparing it with First-Order Logic, which comes next in your syllabus.

1. Cannot represent individuals easily

Suppose:

Ravi is a student.

We can represent this as one proposition:\[ P \]

But propositional logic does not naturally represent:

Ravi
Aman
Priya

as individuals with properties.

2. Cannot naturally represent relationships

Consider:

Ravi teaches MCA students.

Propositional logic cannot naturally express the relationship:

Ravi → teaches → MCA students

First-Order Logic is much better suited for this.

3. No variables

We cannot naturally write:

Every student studies.

In First-Order Logic:\[ \forall x(Student(x)\rightarrow Studies(x)) \]

This cannot be expressed naturally in basic propositional logic.

4. Knowledge can become very large

If we need to represent many individuals and relationships, the number of propositions can become huge.

29. Propositional Logic vs First-Order Logic

Feature	Propositional Logic	First-Order Logic
Basic unit	Proposition	Predicate
Variables	No	Yes
Individuals	Limited	Yes
Relations	Limited	Yes
Quantifiers	No	Yes
∀ and ∃	No	Yes
Expressiveness	Lower	Higher
Reasoning	Relatively simpler	More complex
Example	`P → Q`	`Student(x) → Studies(x)`

Simple distinction

Propositional Logic:

Ravi is a student.

Represent as:\[ P \]

First-Order Logic:\[ Student(Ravi) \]

Now we can also express:\[ \forall x(Student(x)\rightarrow Studies(x)) \]

Meaning:

Every student studies.

This is why your syllabus moves from:

Propositional Logic → Propositional Theorem Proving → First-Order Logic.

30. Real-Life AI Example

Consider a simple smart classroom system.

Facts:\[ LectureToday \]\[ StudentPresent \]

Rules:\[ LectureToday \rightarrow AttendanceRequired \]\[ AttendanceRequired \land StudentPresent \rightarrow RecordAttendance \]

The AI can infer:\[ AttendanceRequired \]

and then:\[ RecordAttendance \]

So:

Lecture Today
      ↓
Attendance Required
      ↓
Student Present
      ↓
Record Attendance

This is a simple example of knowledge representation + inference.

31. Propositional Logic in the AI Syllabus

You should understand the following sequence:

Propositional Logic
        |
        ↓
Propositions
        |
        ↓
Logical Connectives
        |
        ↓
Truth Tables
        |
        ↓
Knowledge Representation
        |
        ↓
Inference
        |
        ↓
Theorem Proving
        |
        ↓
Resolution
        |
        ↓
Horn Clauses
        |
        ↓
Forward Chaining
        |
        ↓
Backward Chaining

These are closely connected topics.

32. Exam-Oriented Answer

Propositional Logic — Definition

Propositional Logic is a formal knowledge representation language in Artificial Intelligence in which knowledge is represented using propositions that are either true or false. Propositions can be combined using logical connectives such as NOT, AND, OR, implication and biconditional. Propositional logic is used for representing facts, constructing knowledge bases, and performing logical inference and automated reasoning.

Main components

Propositions
Propositional variables
Logical connectives
Truth values
Truth tables
Logical expressions
Knowledge bases
Inference
Entailment

Key formulas

\[ \neg P \]\[ P\land Q \]\[ P\lor Q \]\[ P\rightarrow Q \]\[ P\leftrightarrow Q \]

33. One-Minute Revision

Remember P-L-K-I-E:

P → Propositions
L → Logical Connectives
K → Knowledge Base
I → Inference
E → Entailment

And remember:

Proposition
     ↓
Logical Expression
     ↓
Knowledge Base
     ↓
Inference
     ↓
Conclusion

The next topic in your syllabus, “Propositional Theorem Proving — Inference and Proofs,” builds directly on this. There we move from representing knowledge to proving that a conclusion logically follows from the knowledge base.