Introduction to Logic in
Computer Science
Logic forms the bedrock of computer science, providing a structured way to
reason and build intelligent systems. It's the art of drawing sound
conclusions from given facts.
What is Propositional Logic?
Definition Applications AI Example
Propositional Logic deals with Used extensively in algorithm "If user clicks 'yes' AND internet is
statements that are definitively true design, AI decision systems, and available → Start video call." This
or false. It's the simplest form of validating digital circuits. It's crucial simple rule demonstrates its power.
logic, focusing on propositions. for clear, unambiguous instructions.
What is a Proposition?
A proposition is a declarative sentence with a clear truth ❌ Invalid Propositions:
value: either true (T) or false (F).
• "Go away!" (command)
✅ Valid Propositions: • "What time is it?" (question)
• "It is raining." 🔍 Real-world Example:
• "5 is greater than 2."
"The light is ON" is a proposition. Its truth value depends on
whether the light is actually on or off.
Types of Propositions & Conditional Statements
Atomic Proposition Compound Proposition Conditional (Implication)
A simple, indivisible statement, like "It is sunny." Formed by connecting atomic propositions with P → Q ("If P then Q"). Only false if P is true and Q
logical operators, e.g., "It is sunny AND it is is false. E.g., "If it rains, the ground will be wet."
warm."
💻 AI Example: "If user confirms (P), then place the order (Q)."
Tautology, Contradiction, and Contingency
Tautology Contradiction Contingency
Always true, regardless of proposition truth Always false. E.g., P ∧ ¬P (It's raining AND it's Sometimes true, sometimes false. Its truth
values. E.g., P ∨ ¬P (It's raining OR it's not not raining). value depends on the constituent
raining). propositions. Used in checking valid
arguments.
Propositional Equivalence
Two statements are logically equivalent if they always have the same truth
value under all circumstances.
Example: De Morgan’s Law
¬(P ∧ Q) ≡ ¬P ∨ ¬Q
This means "NOT (P AND Q)" is equivalent to "(NOT P) OR (NOT Q)".
Application
Essential for simplifying complex conditions in programming and
optimizing AI logic trees for efficiency and readability.
Propositional Calculus
Propositional Calculus is a formal system comprising rules and techniques to manipulate and derive conclusions from propositions.
1 2 3
Axioms Inference Rules Proofs & Derivations
Fundamental truths assumed without Rules for deriving new propositions Systematic sequences of
proof, forming the basis of logical from existing ones, like Modus Ponens propositions, each following from
deductions. (If P and P→Q, then Q) and Modus axioms or previous steps, to establish
Tollens. validity.
📍 Application: Used extensively in AI inference engines, automated reasoning systems, and proof assistants for formal verification.
Sets and Set Theory
A set is a fundamental concept in mathematics and computer science, defined as
a well-defined collection of distinct objects, often called elements.
Definition
E.g., A = {2, 4, 6, 8}. Each element is unique and its order doesn't matter.
Daily Use
Your phone contacts are a set of unique phone numbers and names.
Fundamental to CS
Crucial for databases, machine learning, and designing efficient
algorithms, allowing us to manage and query data effectively.
Set Operations
Set operations allow us to combine, filter, and compare sets, forming the basis of data manipulation in computing.
Union (∪)
All elements present in set A, or set B, or both. Represents the combination of elements.
Intersection (∩)
Only the common elements found in both set A and set B. Identifies shared components.
Difference (−)
Elements that are in set A but are not in set B. Represents elements unique to the first set.
Complement
All elements not in set A (within a defined universal set). Represents everything outside a given set.
🧠 AI Example: Finding the intersection of "relevant search results" and "matching keywords" to refine search.
Venn Diagrams
Like Maths Like Both Like Physics
Principle of Inclusion and Exclusion
The Principle of Inclusion and Exclusion is used to accurately count the total number of elements in the union of multiple sets by
avoiding double-counting elements that belong to more than one set.
📌 Formula: |A ∪ B| = |A| + |B| − |A ∩ B|
🧠 Example: In a class, 50 students like Java, 30 like Python, and 10 like both. Total unique students liking either language = 50 (Java) +
30 (Python) − 10 (Both) = 70 students.
