Mathematical Foundation - 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

 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⟩)

2. Propositional Equivalences

2.1 Tautology, Contradiction, Contingency

Term	Definition	Example
Tautology	Always TRUE for every assignment	p ∨ ¬p
Contradiction	Always FALSE for every assignment	p ∧ ¬p
Contingency	Neither — mixture of T and F	p ∧ q, p → q

2.2 Logical Equivalence

Two compound propositions A, B are logically equivalent (A ≡ B, or A ⇔ B) if they have the same truth value in every row of the truth table — equivalently, A ↔ B is a tautology.

2.3 Algebra of Propositions / Logical Equivalences

Name	Primal Form	Dual Form
Identity laws	p∨F≡p	p∧T≡p
Domination laws	p∧F≡F	p∨T≡T
Idempotent laws	p∧p≡p	p∨p≡p
Double negation	¬(¬p)≡p
Commutative laws	p∧q≡q∧p	p∨q≡q∨p
Associative laws	(p∧q)∧r≡p∧(q∧r)	(p∨q)∨r≡p∨(q∨r)
Distributive laws	p∧(q∨r)≡(p∧q)∨(p∧r)	p∨(q∧r)≡(p∨q)∧(p∨r)
De Morgan's laws	¬(p∨q)≡¬p∧¬q	¬(p∧q)≡¬p∨¬q
Absorption laws	p∧(p∨q)≡p	p∨(p∧q)≡p
Negation laws	p∧¬p≡F	p∨¬p≡T

Conditional-related Equivalences

Name	Equivalence
Conditional–disjunction	p→q ≡ ¬p∨q
Contrapositive	p→q ≡ ¬q→¬p
Implication (alt.)	p∨q ≡ ¬p→q
Negation of conditional	¬(p→q) ≡ p∧¬q
Distribution over ∧	(p→q)∧(p→r) ≡ p→(q∧r)
Distribution over ∨	(p→r)∧(q→r) ≡ (p∨q)→r

Biconditional Equivalences

Equivalence
p↔q ≡ (p→q)∧(q→p)
p↔q ≡ ¬p↔¬q
p↔q ≡ (p∧q)∨(¬p∧¬q)
¬(p↔q) ≡ p↔¬q

2.4 Constructing New Logical Equivalences

Prove: ¬(p → q) ≡ p ∧ ¬q

¬(p → q)
≡ ¬(¬p ∨ q)        [Conditional–Disjunction Equivalence]
≡ ¬(¬p) ∧ ¬q       [De Morgan's Law]
≡ p ∧ ¬q           [Double Negation Law]

Prove: ¬(p ∨ (¬p ∧ q)) ≡ ¬p ∧ ¬q

¬(p ∨ (¬p ∧ q))
≡ ¬p ∧ ¬(¬p ∧ q)          [De Morgan's Law]
≡ ¬p ∧ (¬(¬p) ∨ ¬q)       [De Morgan's Law]
≡ ¬p ∧ (p ∨ ¬q)           [Double Negation]
≡ (¬p ∧ p) ∨ (¬p ∧ ¬q)    [Distributive Law]
≡ F ∨ (¬p ∧ ¬q)           [Negation Law]
≡ ¬p ∧ ¬q                 [Identity Law]

Prove: (p ∧ q) → (p ∨ q) is a tautology

(p∧q) → (p∨q)
≡ ¬(p∧q) ∨ (p∨q)          [Conditional–Disjunction]
≡ (¬p∨¬q) ∨ (p∨q)         [De Morgan's Law]
≡ (¬p∨p) ∨ (¬q∨q)         [Commutative + Associative]
≡ T ∨ T                    [Negation Law]
≡ T                        [Domination Law] — hence a tautology.

3. CNF and DNF Normal Forms

3.1 Basic Terms

•      Literal: a variable or its negation, e.g., p, ¬p.

•      Minterm (fundamental conjunction)

•       Maxterm (fundamental disjunction)

3.2 Disjunctive Normal Form (DNF)

A formula is in DNF if it is a disjunction of minterms (an "OR of ANDs" / "sum of products").

Construction Method (Truth-Table Method)

·         Build the truth table of the formula.

·         For every row where the formula is TRUE, form a minterm: use the variable itself if its value is T in that row, and its negation if F.

·         Take the disjunction (OR) of all such minterms — this is the DNF (also called the Principal/Canonical DNF).

Find DNF of p → q

p	q	p→q	Minterm (if True)
T	T	T	p ∧ q
T	F	F	—
F	T	T	¬p ∧ q
F	F	T	¬p ∧ ¬q

DNF: (p ∧ q) ∨ (¬p ∧ q) ∨ (¬p ∧ ¬q)

3.3 Conjunctive Normal Form (CNF)

A formula is in CNF if it is a conjunction of maxterms (an "AND of ORs" / "product of sums").

Construction Method (Truth-Table Method)

·         Build the truth table of the formula.

·         For every row where the formula is FALSE, form a maxterm: use the negated variable if its value is T in that row, and the variable itself if F.

·         Take the conjunction (AND) of all such maxterms — this is the CNF (Principal/Canonical CNF).

Find CNF of p → q

p	q	p→q	Maxterm (if False)
T	T	T	—
T	F	F	¬p ∨ q
F	T	T	—
F	F	T	—

CNF: (¬p ∨ q)

3.4 Algebraic Method (Direct Conversion without Truth Table)

·         Eliminate ↔: replace p↔q with (p→q)∧(q→p), or (p∧q)∨(¬p∧¬q).

·         Eliminate →: replace p→q with ¬p∨q.

·         Push ¬ inward using De Morgan's laws and double negation until every ¬ is directly on a variable.

·         Distribute ∧ over ∨ (for CNF) or ∨ over ∧ (for DNF) using the distributive laws.

 Example — Convert ¬(p → q) ∨ (r ↔ p) to CNF

Step 1 (eliminate ↔): r↔p  →  (r→p)∧(p→r)
Step 2 (eliminate →): ¬(p→q)=¬(¬p∨q);  r→p=¬r∨p;  p→r=¬p∨r
  Expression: ¬(¬p∨q) ∨ [(¬r∨p) ∧ (¬p∨r)]
Step 3 (De Morgan): ¬(¬p∨q) = p∧¬q
  Expression: (p∧¬q) ∨ [(¬r∨p)∧(¬p∨r)]
Step 4 (distribute ∨ over ∧):
  = [(p∧¬q)∨(¬r∨p)] ∧ [(p∧¬q)∨(¬p∨r)]
  = [(p∨¬r∨p)∧(¬q∨¬r∨p)] ∧ [(p∨¬p∨r)∧(¬q∨¬p∨r)]
Simplify (p∨¬r∨p≡p∨¬r ; p∨¬p∨r≡T, drop it):

Final CNF = (p ∨ ¬r) ∧ (¬q ∨ ¬r ∨ p) ∧ (¬q ∨ ¬p ∨ r)

3.5 Satisfiability

•      Satisfiable: at least one truth assignment makes the proposition TRUE.

•      Unsatisfiable: FALSE for every assignment (i.e., it is a contradiction).

•      A satisfying assignment is called a solution.

Example

Q = (p ∨ ¬q) ∧ (q ∨ ¬r) ∧ (r ∨ ¬p). This is satisfiable whenever p, q, r all share the same truth value:

•      All True: (T∨F)∧(T∨F)∧(T∨F) = T∧T∧T = T

•      All False: (F∨T)∧(F∨T)∧(F∨T) = T∧T∧T = T

Applications of Satisfiability

•      n-Queens problem — placing n queens with no two attacking.

•      Sudoku — modeled with hundreds of Boolean variables.

•      Circuit design verification and software test-case generation.

•      AI planning — finding an action sequence achieving a goal.

Truth tables can check satisfiability for small n (≤ ~20 variables); in general SAT is NP-Complete, but modern SAT solvers handle millions of variables for structured real-world problems.

 4.Predicate Calculus (Predicate Logic)

4.1. Introduction

In mathematics and computer science, we often encounter statements involving variables, such as:

●        x > 10

●        x = y + 5

●        x + y = z

When the values of the variables are not specified, these expressions cannot be classified as either True (T) or False (F). Therefore, they are not propositions.

Example:

x > 10

If x = 15, then 15 > 10 is True.

If x = 5, then 5 > 10 is False.

The truth value depends entirely on the value assigned to the variable.

4.2. Predicate

A statement involving a variable can be split into two parts. Example: "x is greater than 10."

Part	Content
Subject	x
Predicate	is greater than 10

 

The predicate describes a property or relationship that the subject may satisfy. We denote it using a symbol such as P:

P(x): x > 10

●        P → predicate

●        x → variable

●        P(x) → propositional function of x

4.3. Propositional Function

A propositional function is a statement containing one or more variables, whose truth value depends on the values assigned to those variables.

One Variable

P(x): x > 10

Assign	Statement	Result
x = 15	P(15): 15 > 10	P(15) = T
x = 5	P(5): 5 > 10	P(5) = F

 

Key idea: P(x) is not a proposition while x is unspecified. Once a value is substituted (e.g., P(15)), it becomes a proposition with a definite truth value.

Two Variables

P(x, y): x = y + 5

Assign	Statement	Result
x = 10, y = 5	10 = 5 + 5  ⇒  10 = 10	P(10,5) = T
x = 8, y = 5	8 = 5 + 5  ⇒  8 = 10	P(8,5) = F

Three Variables

P(x, y, z): x + y = z

Assign	Statement	Result
x=3, y=4, z=7	3 + 4 = 7	P(3,4,7) = T
x=3, y=4, z=8	3 + 4 = 8	P(3,4,8) = F

 

The number of variables in a predicate is called its arity.

4.4. Predicate Logic / Predicate Calculus

Predicate logic (also called predicate calculus) is a branch of mathematical logic dealing with:

●        Predicates

●        Variables

●        Constants

●        Quantifiers

●        Logical connectives

●        Relationships between objects

Example: "All students in the class have passed."

This requires a quantifier ("for all") and is written as:

∀x  P(x)

where P(x) means "x is a student who has passed."

 

5.Quantifiers in Predicate Logic

5.1. Quantifier

A quantifier is a symbol or expression used in predicate logic to indicate how many elements in the domain satisfy a given predicate.

In simple terms: a quantifier tells us whether a predicate is true for all elements, or for at least one element, of the domain.

There are two fundamental quantifiers:

●        Universal Quantifier (∀)

●        Existential Quantifier (∃)

5.2. Universal Quantifier

The universal quantifier states that a predicate is true for every element in the specified domain. It is represented by:

∀

It is read as:

●        for all

●        for every

●        for each

General Form

∀x  P(x)

Read as: "For all x, P(x) is true." or "For every x, P(x) is true."

Example 1

Consider the statement:

Every student in the class has an ID card.

Let

P(x): x is a student who has an ID card

Then:

∀x  P(x)

means: Every student has an ID card.

Example 2 — Mathematical Statement

Consider:

Every natural number is greater than or equal to 1.

Let the domain be the set of natural numbers.

P(x): x ≥ 1

Then:

∀x  P(x)      or      ∀x (x ≥ 1)

5.3. Meaning of Universal Quantifier

Suppose the domain is:

D = {1, 2, 3, 4, 5}

and

P(x): x < 10

Then ∀x P(x) means:

P(1) ∧ P(2) ∧ P(3) ∧ P(4) ∧ P(5)

That is:

(1<10) ∧ (2<10) ∧ (3<10) ∧ (4<10) ∧ (5<10)

All statements are true. Therefore:

∀x  P(x) = T

Important point: For a universal statement to be true, the predicate must be true for every element in the domain. Even one counterexample makes the universal statement false.

5.4. Existential Quantifier

The existential quantifier states that a predicate is true for at least one element in the specified domain. It is represented by:

∃

It is read as:

●        there exists

●        there is at least one

●        for some

General Form

∃x  P(x)

Read as: "There exists an x such that P(x) is true."

5.5. Example of Existential Quantifier

Consider:

Some student scored more than 90 marks.

Let

P(x): x scored more than 90 marks

Then:

∃x  P(x)

means: There exists at least one student who scored more than 90 marks.

Mathematical Example

Let:

D = {1, 2, 3, 4, 5}      and      P(x): x > 3

Then ∃x P(x) means: there exists at least one element x such that x > 3.

Value	Statement	Result
x = 4	P(4): 4 > 3	P(4) = T
x = 5	P(5): 5 > 3	P(5) = T

 

Therefore:

∃x  P(x) = T

Only one true instance is sufficient to make an existential statement true.

5.6. Negation of Quantifiers

Negation of quantifiers is a very important topic in predicate logic. The two fundamental rules are:

¬(∀x P(x))  ≡  ∃x ¬P(x)

and

¬(∃x P(x))  ≡  ∀x ¬P(x)

These are called the negation laws of quantifiers, or De Morgan's laws for quantifiers.

Summary Table

Quantifier	Symbol	Read As	True When
Universal	∀x P(x)	For all x, P(x) is true	P(x) is true for every element in the domain
Existential	∃x P(x)	There exists an x such that P(x) is true	P(x) is true for at least one element in the domain

 6. Mathematical Induction

6.1. Definition

Mathematical induction is a method of proof used to establish that a proposition P(n) is true for every integer n ≥ n₀, by:

●        proving a base case P(n₀), and

●        showing that whenever P(k) is true, P(k+1) is also true.

6.2. Principle of Mathematical Induction

Suppose P(n) is a proposition involving a positive integer n. To prove:

P(n) is true for all n ≥ n₀

we use the following two steps.

Step 1 — Base Case

Prove that:

P(n₀) is true

Usually, n₀ = 1.

Step 2 — Inductive Step

Assume that:

P(k) is true

for an arbitrary integer k ≥ n₀. This assumption is called the Induction Hypothesis.

Then prove:

P(k+1) is true

Conclusion: If both steps are successfully proved, then P(n) is true for all n ≥ n₀.

6.3. Basic Structure

The mathematical induction process can be represented as a chain:

P(n₀) → P(n₀+1) → P(n₀+2) → P(n₀+3) → ....

The reasoning is:

●        P(n₀) is true

●        P(k) ⇒ P(k+1)

Therefore:

P(n) is true for all n ≥ n₀

6.4. Steps in Mathematical Induction

For every induction problem, students should follow these five steps.

1. State the proposition — write the statement as P(n): Given statement.

2. Base Case — put the first value, usually n = 1, into the statement and verify it.

3. Induction Hypothesis — assume the statement is true for n = k. Write P(k): statement involving k.

4. Inductive Step — replace n by k + 1, write P(k+1), and use the induction hypothesis to prove it.

5. Conclusion — state that P(n) is true for all n ≥ 1.

6.5. Example 1 — Sum of the First n Natural Numbers

Prove that: 1 + 2 + 3 + .... + n  =  n(n+1) / 2      for all n ≥ 1

  Step 1: Define P(n)

P(n): 1 + 2 + 3 + .... + n = n(n+1) / 2

  Step 2: Base Case

Put n = 1.

Side	Value
LHS	1
RHS	1(1+1)/2 = 2/2 = 1

 

Since LHS = RHS, P(1) is true.

  Step 3: Induction Hypothesis

Assume the result is true for n = k:

1 + 2 + 3 + .... + k = k(k+1) / 2

This is the Induction Hypothesis.

  Step 4: Prove P(k+1)

We need to prove:

1 + 2 + .... + k + (k+1) = (k+1)(k+2) / 2

Using the induction hypothesis:

1 + 2 + .... + k + (k+1) = k(k+1)/2 + (k+1)

Take (k+1) common:

= (k+1) [ k/2 + 1 ]  =  (k+1) [ (k+2)/2 ]

Therefore:

= (k+1)(k+2) / 2

Hence, P(k+1) is true.

  Step 5: Conclusion

Since:

●        P(1) is true, and

●        P(k) ⇒ P(k+1),

by the principle of mathematical induction:

1 + 2 + 3 + .... + n = n(n+1) / 2   is true for all n ≥ 1

6.6. Example 2 — Sum of the First n Odd Numbers

Prove that: 1 + 3 + 5 + .... + (2n − 1) = n²      for all n ≥ 1

  Step 1: Base Case

For n = 1:

Side	Value
LHS	1
RHS	1² = 1

 

Since LHS = RHS, P(1) is true.

  Step 2: Induction Hypothesis

Assume that:

1 + 3 + 5 + .... + (2k − 1) = k²

  Step 3: Prove P(k+1)

We need to prove:

1 + 3 + 5 + .... + (2k−1) + [2(k+1)−1] = (k+1)²

Using the induction hypothesis:

k² + 2(k+1) − 1

= k² + 2k + 2 − 1

= k² + 2k + 1

= (k+1)²

Hence, P(k+1) is true.

Conclusion

Hence, by mathematical induction:

1 + 3 + 5 + .... + (2n − 1) = n²   for all n ≥ 1

 

 

 7.Well-Formed Formulas for Automated Proving

7.1. Introduction

In mathematical logic, a Well-Formed Formula (WFF) is a formula that is constructed according to the formal syntax or rules of the logical system.

Well-formed formulas matter in automated theorem proving because a computer must be able to recognize whether a logical expression is correctly written before it can process or prove it.

7.2. Definition of Well-Formed Formula

A Well-Formed Formula (WFF) is a formula that is constructed according to the syntactic rules of a formal logical language.

For example:

p ∧ q   is a WFF

Similarly:

p → (q ∨ r)   is a WFF

But:

∧ p q   is NOT a WFF

This is not a correctly formed formula in standard infix propositional notation.

Important point: WFF deals with the syntax of a formula, not its truth value. For example, p ∨ q is a WFF whether it is true or false.

7.3. WFF in Propositional Logic

A formula is constructed using:

●        Propositional variables

●        Logical connectives

●        Parentheses

Common propositional variables are: p, q, r, s, …

Common logical connectives are:

Symbol	Name	Meaning
¬	NOT	Negation
∧	AND	Conjunction
∨	OR	Disjunction
→	Conditional	If … then
↔	Biconditional	If and only if

7.4. Rules for Constructing WFF

The formation rules can be given recursively.

  Rule 1: Atomic Propositions

Every propositional variable is a WFF. Therefore:

p,   q,   r   are WFFs

  Rule 2: Negation

If P is a WFF, then:

¬P is also a WFF

Example: p is a WFF, therefore ¬p is also a WFF.

  Rule 3: Binary Connectives

If P and Q are WFFs, then the following are also WFFs:

(P ∧ Q)     (P ∨ Q)     (P → Q)     (P ↔ Q)

  Rule 4: Nothing Else

Any expression that cannot be constructed using these rules is not a WFF.

7.5. Examples of WFF

Example 1

p ∧ q

Both p and q are WFFs. Therefore:

p ∧ q is a WFF

Example 2

¬p

Since p is a WFF:

¬p is a WFF

Example 3

p → (q ∨ r)

Since q ∨ r is a WFF, therefore:

p → (q ∨ r) is a WFF

7.6. Non-Well-Formed Formulas

The following are examples of incorrectly constructed formulas:

Expression	Why It Fails
p ∧	Connective has no second operand
∨ p	Connective is missing a left operand
p q	Two variables placed together with no connective

 

These are not WFFs because they violate the formation rules.

7.7. WFF in Predicate Logic

In predicate logic, formulas are constructed using:

●        Variables

●        Constants

●        Predicates

●        Functions

●        Logical connectives

●        Quantifiers

For example:

P(x)  is a well-formed atomic formula

Similarly:

P(x) ∧ Q(x)  is a WFF

And:

∀x P(x)  is also a WFF

7.8. Formation Rules for Predicate Logic

  Rule 1: Predicate

If P is a predicate and x is a variable, then:

P(x) is a WFF

Example: Student(x)

  Rule 2: Negation

If P(x) is a WFF:

¬P(x) is also a WFF

Example: ¬Student(x)

  Rule 3: Logical Connectives

If P(x) and Q(x) are WFFs, then:

P(x) ∧ Q(x)     P(x) ∨ Q(x)     P(x) → Q(x)

are WFFs.

  Rule 4: Universal Quantifier

If P(x) is a WFF, then:

∀x P(x) is a WFF

Example:

∀x (Student(x) → Passed(x))

Meaning: Every student passed.

  Rule 5: Existential Quantifier

If P(x) is a WFF, then:

ⱻx P(x) is a WFF

Example:

∃x (Student(x) ∧ Passed(x))

Meaning: There exists at least one student who passed.

 

7.9. WFF and Automated Proving

What Is Automated Theorem Proving?

Automated theorem proving (ATP) is a branch of artificial intelligence and computer science in which a computer automatically determines whether a mathematical or logical statement follows from given assumptions.

A computer cannot process arbitrary natural-language statements directly — the statement must first be represented in a formal logical language.

For example, the sentence:

Every student who studies passes the examination.

may be represented as:

∀x (Student(x) → Studies(x) → Passes(x))

depending on the intended meaning. The resulting logical formula can then be processed by an automated theorem prover.

7.10. Role of WFF in Automated Proving

A typical automated proving process is:

Natural Language → Logical Representation → WFF → Logical Transformation → Proof

Key point: The system first checks whether the formula follows the syntax of the formal language. If it is not a WFF, the automated prover cannot correctly interpret it.