Mathematical Logic & Predicates - Unit 1

 

Mathematical Foundation

Unit-1 - Mathematical Logic & Predicates

Propositional Logic Syntax - Truth Tables - CNF and DNF Normal Forms – Predicate Calculus - Universal & Existential Quantifiers - Rules of Inference – Mathematical Induction - Well-Formed Formulas for Automated Proving.

 

1. Propositional Logic — Syntax & Connectives

1.1 What is Logic?

•      Logic is the study of correct reasoning.

•      It separates valid from invalid arguments

•      It uses clear rules instead of vague words.

 

Key applications in computer science:

•      Design of computer circuits

•      Construction and verification of computer programs

•      Artificial intelligence and knowledge representation

•      Database query languages

 

1.2 Propositions

A proposition is a declarative sentence that is either true or false, but not both simultaneously.

Propositional Variables

- Represent propositions using letters: p, q, r, s, ...

- Truth values: T (True) or F (False)

- Atomic propositions: Cannot be broken down into simpler propositions

Propositions (valid)	Not Propositions
"New Delhi is the capital of India" — True	"What time is it?" — question
"2 + 2 = 4" — True	"Please close the door" — command
"Mumbai is in Karnataka" — False	"x + 1 = 5" — truth depends on x
"The moon is made of cheese" — False	"This statement is false" — paradox

 

1.3 Logical Connectives / Operators

(a) Negation ¬p (NOT)

The negation of p is true when p is false and false when p is true. Alternative notations: ¬p, ~p, p′, !p.

p	¬p
T	F
F	T

English forms: "It is not the case that p", "not p", "it is false that p.

Example:

- p: "Rahul's computer runs Windows"

- ¬p: "Rahul's computer does not run Windows"

 

(b) Conjunction p ∧ q (AND)

True only when BOTH p and q are true.

p	q	p ∧ q
T	T	T
T	F	F
F	T	F
F	F	F

English forms: "p and q", "p but q", "p while q", "p moreover q". Note: "but" logically means "and."

Example:

- p: "The sun is shining"

- q: "It is raining"

- p ∧ q: "The sun is shining and it is raining"

 

(c) Disjunction p ∨ q (Inclusive OR)

True when at least one of p, q is true (including when both are true).

p	q	p ∨ q
T	T	T
T	F	T
F	T	T
F	F	F

English forms: "p or q", "p and/or q." Example — a course pre-requisite "Calculus or Computer Science" is satisfied by taking either or both.

Example:

- p: "Student has taken Calculus"

- q: "Student has taken Computer Science"

- p ∨ q: "Student has taken Calculus or Computer Science"

- (This means student can take the class if they have taken either subject OR both)

 

(d) Exclusive OR pꚚq (XOR)

True when exactly one of p, q is true (not both).

p	q	pꚚq
T	T	F
T	F	T
F	T	T
F	F	F

Example — "I will use my savings to buy a car or travel to Europe" — cannot do both since either option exhausts the savings.

Example:

- p: "I will use my savings to buy a car"

- q: "I will use my savings to travel to Europe"

- p ⊕ q: "I will use my savings to buy a car or travel to Europe"

- (Cannot do both because one requires all savings)

 

(e) Conditional p → q (Implication)

p → q is false only when p is true and q is false; true in every other case.

p is the hypothesis/antecedent/premise; q is the conclusion/consequence.

p	q	p → q
T	T	T
T	F	F
F	T	T
F	F	T

 

English form	Example
"if p, then q"	If it rains, then the ground is wet
"p implies q"	Rain implies wet ground
"p only if q"	I go out only if it is not raining
"p is sufficient for q"	Being a square is sufficient for being a rectangle
"q is necessary for p"	Being a rectangle is necessary for being a square
"q if p" / "q whenever p"	The ground is wet if/whenever it rains
"q unless ¬p"	The ground is wet unless it does not rain

 

Converse, Contrapositive, Inverse

Term	Form	Example (p: it rains, q: ground wet)
Original	p → q	If it rains, the ground is wet
Converse	q → p	If the ground is wet, it rains
Inverse	¬p → ¬q	If it does not rain, the ground is not wet
Contrapositive	¬q → ¬p	If the ground is not wet, it did not rain

Note: Contrapositive (¬q→¬p) is ALWAYS logically equivalent to the original (p→q).

Converse and Inverse are NOT equivalent to the original, but ARE equivalent to each other

 

(f) Biconditional p ↔ q (IFF)

True when p and q have the SAME truth value. Logically, p ↔ q ≡ (p→q) ∧ (q→p).

English forms: "p if and only if q", "p is necessary and sufficient for q", "p exactly when q."

Key Property:

p ↔ q is logically equivalent to (p → q) ∧ (q → p)

p	q	p ↔ q
T	T	T
T	F	F
F	T	F
F	F	T

 

Example:

- p: "You can take the flight"

- q: "You buy a ticket"

- p ↔ q: "You can take the flight if and only if you buy a ticket"

- True when both conditions match (both true or both false)

 

1.4 Truth Tables of Compound Propositions

Construction Process:

1. List all propositional variables

2. Create columns for each variable

3. Create columns for intermediate steps

4. Final column for the compound proposition

5. Number of rows = 2^n (where n = number of variables)

 

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

p	q	¬q	p ∨ ¬q	p ∧ q	(p∨¬q)→(p∧q)
T	T	F	T	T	T
T	F	T	T	F	F
F	T	F	F	F	T
F	F	T	T	F	F

 

1.5 Operator Precedence

Order	Operator
1 (highest)	¬  negation
2	∧  conjunction
3	∨  disjunction
4	→  conditional
5 (lowest)	↔  biconditional

•      ¬p ∧ q  means  (¬p) ∧ q   —  NOT  ¬(p ∧ q)

•      p ∨ q ∧ r  means  p ∨ (q ∧ r)   —  NOT  (p ∨ q) ∧ r

•      p → q ∨ r  means  p → (q ∨ r)   —  NOT  (p → q) ∨ r

Exam Tip: Precedence 'what does this really mean' questions are a frequent 2–5 mark question. Memorize: ¬, ∧, ∨, →, ↔ (highest to lowest).

 

1.6 Bit Operations

A bit is a binary digit: 1 = True, 0 = False. A variable taking value 0 or 1 is a Boolean variable.

x	y	x∨y (OR)	x∧y (AND)	xꚚy (XOR)
0	0	0	0	0
0	1	1	0	1
1	0	1	0	1
1	1	1	1	0

A bit string is a finite sequence of bits; its length is the number of bits. Bitwise operations apply the corresponding logical operation position-by-position to two equal-length bit strings:

01 1011 0110  (String 1)
11 0001 1101  (String 2)
----------------------------
11 1011 1111  (Bitwise OR)
01 0001 0100  (Bitwise AND)
10 1010 1011  (Bitwise XOR)

 

1.7 Well-Formed Formula

1.       Basis: every propositional variable and constants T, F are WFFs (atomic formulas).

2.       Recursive step: if A, B are WFFs then (¬A), (A∧B), (A∨B), (A⊕B), (A→B), (A↔B) are WFFs.

3.       Closure: nothing else is a WFF.

⟨wff⟩ ::= p | T | F | ¬⟨wff⟩ | (⟨wff⟩∧⟨wff⟩) | (⟨wff⟩∨⟨wff⟩) | (⟨wff⟩→⟨wff⟩) | (⟨wff⟩↔⟨wff⟩)