Scribd
Upload
7 views2 pages

Module 1 Mathematical Logic Study Notes

This document covers the fundamentals of mathematical logic, including the definition of propositions, logical connectives, and truth tables. It explains implication variations, logical equivalence, key laws, and normal forms such as DNF and CNF. Additionally, it introduces rules of inference that are essential for valid reasoning.

Uploaded by

adiraj.kashyap.01
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
7 views2 pages

Module 1 Mathematical Logic Study Notes

This document covers the fundamentals of mathematical logic, including the definition of propositions, logical connectives, and truth tables. It explains implication variations, logical equivalence, key laws, and normal forms such as DNF and CNF. Additionally, it introduces rules of inference that are essential for valid reasoning.

Uploaded by

adiraj.kashyap.01
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Mathematical Logic - Module 1 Study

Notes
1. Introduction & Statements
Logic is the study of reasoning — rules and techniques for deciding if an argument is valid.
In computing, we use it to prove program correctness, and in mathematics to prove
theorems.

A proposition is a declarative sentence that is either TRUE or FALSE (but not both).

Examples: 'New Delhi is the capital of India.' (TRUE)

Non-examples: 'Sit down!' (command), 'What time is it?' (question)

2. Logical Connectives & Truth Tables


Logical connectives combine propositions:

Symbol Name Meaning

¬p Negation Not p

p∧q Conjunction p and q (True if both true)

p∨q Disjunction p or q (True if at least one


true)

p→q Implication If p, then q (False only if


T→F)

p↔q Biconditional p if and only if q

Special cases:
- Tautology: Always true (p ∨ ¬p)
- Contradiction: Always false (p ∧ ¬p)
- Contingency: Sometimes true, sometimes false

Example: Truth Table for p → q


p q p→q

T T T

T F F
F T T

F F T

3. Implication Variations
From p → q we can form:
- Converse: q → p
- Contrapositive: ¬q → ¬p (logically equivalent to original)
- Inverse: ¬p → ¬q

4. Logical Equivalence & Laws


Two propositions are equivalent if p ↔ q is a tautology.

Key Laws:
- De Morgan’s: ¬(p ∧ q) ≡ (¬p) ∨ (¬q); ¬(p ∨ q) ≡ (¬p) ∧ (¬q)
- Double Negation: ¬(¬p) ≡ p
- Commutative, Associative, Distributive Laws

5. Normal Forms (DNF, CNF, PDNF, PCNF)


DNF: OR of AND terms; CNF: AND of OR terms.
PDNF: Disjunction of minterms; PCNF: Conjunction of maxterms.
Steps to CNF:
1. Eliminate → and ↔
2. Apply De Morgan’s Laws to push negations
3. Distribute OR over AND

Example: p ↔ q
≡ (p → q) ∧ (q → p)
≡ (¬p ∨ q) ∧ (¬q ∨ p)

6. Theory of Inference
Rules of Inference are patterns of valid reasoning.
- Modus Ponens: p → q, p ⇒ q
- Modus Tollens: p → q, ¬q ⇒ ¬p
- Hypothetical Syllogism: p → q, q → r ⇒ p → r

You might also like