Unit-1: Logic And Preposition

1. Prepostition

A Prepostition is a declarative statement which is either true or false but not both(e.g. , Delhi is the capital of India (true) → Prepostition)

2. Negation

Let P be a Proposition, then its negation is denoted by ̅P or ~P.

P	~P
True	False
False	True

~(~P) = P

~(~(~P)) = ~P

3. Conjuction

Let P and Q are two prepostions then their conjuction is denoted by P∧Q and it is true if both are true , false otherwise

P	Q	P ∧ Q	Q ∧ P
True	True	True	True
True	False	False	False
False	True	False	False
False	False	False	False

∧ is commutative i.e, p ∧ q = q ∧ p

4. Disjunction

Let P and Q are two prepostions then their disjuction of P and Q is denoted by P ∨ Q .It is false only if both statements are false.

P	Q	P ∨ Q	Q ∨ P
True	True	True	True
True	False	True	True
False	True	True	True
False	False	False	False

∨ is both commutative and associative .
p ∨ q = q ∨ p (commutative)
p ∨ (q ∨ r) = (p ∨ q) ∨ r (associative)

5. Exclusive or (XOR)

If is true only if exaclty one input is true otherwise false. It is denoted by ⊕ symbol.

p	q	p ⊕ q
True	True	False
True	False	True
False	True	True
False	False	False

5. Conditional Statement (Implication)

A conditional statement is denoted by p → q , which means "if p then q." . The implication is false only when p is true and q is false — true in all other cases.

p	q	p → q
True	True	True
True	False	False
False	True	True
False	False	True

6. Converse Statement

The converse of a conditional statement p → q is q → p, meaning "if q, then p." . The converse just swaps the positions of p and q in the implication, so q → p instead of p → q.

p	q	q → p
True	True	True
True	False	True
False	True	False
False	False	True

7. Inverse Statement

The inverse of a conditional statement p → q is ~ p → ~ q, meaning "if not p, then not q." The inverse flips both p and q with their negations, so it checks the truth value for ~p → ~q.

p	q	~p	~q	~p → ~q
True	True	False	False	True
True	False	False	True	True
False	True	True	False	False
False	False	True	True	True

8. Contrapositive Statement

The contrapositive of a conditional statement p → q is ~ q → ~p, meaning "if not q, then not p."

p	q	~q	~p	~q → ~p
True	True	False	False	True
True	False	True	False	False
False	True	False	True	True
False	False	True	True	True

9. De Morgan's Laws

Law 1: Negation of a Conjunction

~(p ∧ q) ≡ ~p ∨ ~q

p	q	p ∧ q	~(p ∧ q)	~p	~q	~p ∨ ~q
True	True	True	False	False	False	False
True	False	False	True	False	True	True
False	True	False	True	True	False	True
False	False	False	True	True	True	True

Law 2: Negation of a Disjunction

~(p ∨ q) ≡ ~p ∧ ~q

p	q	p ∨ q	~(p ∨ q)	~p	~q	~p ∧ ~q
True	True	True	False	False	False	False
True	False	True	False	False	True	False
False	True	True	False	True	False	False
False	False	False	True	True	True	True

10. Biconditional Statement

A biconditional statement is denoted by p ↔ q meaning "p if and only if q" (p IFF q) — true when both p and q are the same.

p	q	p ↔q
True	True	True
True	False	False
False	True	False
False	False	True

11. Tautology

A tautology is a logical statement that is always true, regardless of the truth values of its components. For example, p ∨ ~p is a tautology.

p	~p	p ∨ ~p
True	False	True
False	True	True

12. Predicates

A predicate is a logical statement that contains variables and becomes true or false depending on the values of those variables. It is denoted as P(x), where P is a property and x is the subject.

Example:

Let P(x) be "x is an even number."

x	P(x): "x is even"
2	True
3	False
4	True
5	False

Quantifiers:

Predicates often use quantifiers:

Universal quantifier (∀): "For all x, P(x)" → ∀x P(x)
Existential quantifier (∃): "There exists an x such that P(x)" → ∃x P(x)

Example with Quantifiers:

Let Q(x) be "x is greater than 0."

∀x Q(x) → "For all x, x is greater than 0" (False for negative numbers)
∃x Q(x) → "There exists an x such that x is greater than 0" (True for positive numbers)

13. Proofs in Logic

A proof is a sequence of logical steps that show a statement is true, based on axioms, definitions, and previously proven theorems.

Types of Proofs:

Direct Proof: Start with the assumptions and use logical steps to arrive at the conclusion.
Indirect Proof (Contrapositive): Prove the contrapositive of the statement instead of the original statement.
Proof by Contradiction: Assume the statement is false, derive a contradiction, and conclude the statement must be true.
Proof by Cases: Split the problem into separate cases and prove each one individually.

Example: Direct Proof

Prove: If n is an even number, then n² is even.

Proof:

Assume n is even. By definition, n = 2k for some integer k.
Compute n²: n² = (2k)² = 4k².
Since 4k² = 2(2k²), n² is divisible by 2, so n² is even.
Therefore, if n is even, n² is even.

Example: Proof by Contradiction

Prove: √2 is irrational.

Proof:

Assume, for contradiction, that √2 is rational. Then, √2 = a/b, where a and b are integers with no common factors.
Square both sides: 2 = a²/b² → a² = 2b².
This implies a² is even, so a must be even. Let a = 2k.
Substitute: (2k)² = 2b² → 4k² = 2b² → b² = 2k².
Thus, b² is even, so b must also be even, contradicting the assumption that a and b have no common factors.
Therefore, √2 is irrational.

14. Vacuous and Trivial Proofs

Vacuous Proof

A vacuous proof shows a statement is true because the hypothesis is always false. Since an implication (p → q) is true when p is false, the statement holds vacuously.

Example:

Prove: "If 3 is even, then 3² is negative."

Proof:

The statement is of the form: p → q, where p: "3 is even" and q: "3² is negative."
The hypothesis (3 is even) is false.
Since p is false, the implication is automatically true, regardless of q.
Therefore, the statement is true by vacuous proof. ️

Trivial Proof

A trivial proof shows a statement is true because the conclusion is always true, no matter the hypothesis. Since an implication (p → q) is true when q is true, the statement is automatically true.

Example:

Prove: "If 5 is prime, then 2 + 2 = 4."

Proof:

The statement is of the form: p → q, where p: "5 is prime" and q: "2 + 2 = 4."
The conclusion (2 + 2 = 4) is always true.
Since q is true, the implication is true, regardless of p.
Therefore, the statement is true by trivial proof. /li>

Key Points:

Vacuous Proof: True because the hypothesis is false (p is false).
Trivial Proof: True because the conclusion is true (q is true).

15. Common Mistakes in Proofs

When constructing proofs, it's easy to make mistakes that lead to incorrect conclusions. Let’s explore some common errors!

1. Assuming What You Want to Prove (Circular Reasoning)

This happens when the conclusion is used as part of the proof itself.

Example (Incorrect Proof):

Prove: If n is even, then n² is even.

Assume n² is even. ( This assumes the conclusion!)
Since n² is even, n must be even.
Therefore, if n is even, n² is even. (Circular reasoning)

Fix: Start from the definition of even numbers, not the conclusion.

2. Misunderstanding Implications

Remember: p → q is not the same as q → p. Confusing these leads to incorrect conclusions.

Example (Incorrect Proof):

Prove: If n is divisible by 4, then n is even.

Assume n is even.
Since n is even, n must be divisible by 4. (Not true: 6 is even but not divisible by 4)

Fix: Understand the difference between a statement and its converse.

3. Ignoring Edge Cases

Failing to consider special or boundary cases can make a proof incomplete.

Example (Incorrect Proof):

Prove: If n² is positive, then n is positive.

Assume n² is positive.
Since squaring a positive number gives a positive result, n must be positive.

Problem: What about n = -1? n² = 1 is positive, but n is negative.

Fix: Account for negative numbers and refine the statement.

4. Misusing Quantifiers

Be careful with universal (∀) and existential (∃) quantifiers — swapping them changes the meaning of a statement.

Example (Incorrect Statement):

∀x ∃y (x + y = 0) is true. (For every x, there exists a y such that x + y = 0)

∃y ∀x (x + y = 0) is false. (There’s no single y that works for all x!)

Fix: Understand how quantifiers affect logical statements.

5. Gaps in Logical Steps

Skipping important logical steps or making unjustified leaps can make a proof invalid.

Example (Incorrect Proof):

Prove: If n is an even integer, then n + 1 is odd.

Assume n is even.
Therefore, n + 1 is odd. (Step missing!)

Fix: Fill in the missing step: n = 2k, so n + 1 = 2k + 1 (definition of an odd number).

Key Takeaways:

Avoid **circular reasoning** — don’t assume what you’re trying to prove.
Understand the difference between a statement, its converse, and its contrapositive.
Always check **edge cases** to avoid overlooking counterexamples.
Use **quantifiers carefully** — they can completely change the meaning of a statement.
Write every step explicitly — don’t skip logical connections, even if they seem obvious.

16. Counterexamples and Proof of Equivalence

1. Counterexamples

A counterexample is a specific example that disproves a statement. If a single example makes a statement false, the entire statement is false.

Example:

Statement: "If a number is odd, then its square is even."

Counterexample:

Let n = 3.

3 is odd, but 3² = 9, which is not even.

Since we found an example where the statement fails, it is false by counterexample.

2. Proof of Equivalence

To prove two statements are logically equivalent (p ↔ q), you need to show both directions:

p → q (If p, then q)
q → p (If q, then p)

Example:

Prove: "n is even ↔ n² is even."

Proof:

1. Forward Direction (p → q):

If n is even, then n = 2k for some integer k.

Compute n²: n² = (2k)² = 4k² = 2(2k²).
Since n² is divisible by 2, it is even.

2. Reverse Direction (q → p):

If n² is even, we show that n must also be even.

If n were odd, n² would be odd (odd × odd = odd).
Since n² is even, n cannot be odd, so n must be even.

Both directions are true, so n is even ↔ n² is even. ️

3. Truth Table Method for Equivalence

You can also use a truth table to check if two statements are logically equivalent.

Example:

Prove: p ∨ q is equivalent to q ∨ p (Commutativity of OR).

p	q	p ∨ q	q ∨ p
True	True	True	True
True	False	True	True
False	True	True	True
False	False	False	False

Since the columns for p ∨ q and q ∨ p are identical, they are logically equivalent. ️

Key Takeaways:

Counterexample: A single example that disproves a statement.
Proof of Equivalence: Show both p → q and q → p.
Truth Tables: Useful for verifying logical equivalence step by step.