Propositional Logic

Propositional or Sentence

An expression consisiting of some symbols, letters and words is called a sentence it is true or false.
For example :
- Jaipur is capital of Rajasthan. → yes it is true statement.
- 2 + 3 = 5 → true statment
- 9 < 6 → false statement
- Mumbai is in America. → false statement
- "Wish you happy life" is not a proposition because truth or false is not certain.

Truth Value

If any proposition is true then its truth value is denoted by T and if the proposition is false then its truth value is denoted by F.
Example
- 1 is less than 3 → T
- 14 is odd number → F

Type of proposition

Simple Proposition → The proposition having one subject and one predicate (property) is called a simple proposition.
- Example
  - this flower is pink.
  - Every even number is divisible by 2.
Compound Proposition → Two or more simple proposition when combined by various connectivities into a single composite sentence is called compound proposition.
- Example
  - The earath is round and revolves around the sun.
  - A triangle is equilateral if its three sides are equal.

Loginal Connectives

How two sentence are connected.

The particular workds and symbols used to join tow or more proposition into a single composite form or compound proposition are called logical connectives.

Logical connectives words

Symbol

Uses

And/conjunction/join

∧

p ∧ q

or/disjunction/meet

∨

p ∨ q

Negation

- or ~

~p

Equivalent

↔

p ↔ q

Conditional "if ... then .... "

⇒

p ⇒ q

Biconditional "if and only if"(iff)

⇔

p ⇔ q

Basic Logical Operation

1. Conjunction: Any two proposition can be combined by the word "And" to form a compound proposition said to be the conjunction.

Truth table

p

q

p ∧ q

T

F

T

F

A short trick would be treat 'T' as 1 and 'F' as 0 and answer will be multiplication of both. T ∧ F = F as 1 * 0 = 0

Example
- Delhi is in India and 2 + 2 = 4 → T
- Delhi is in India and 2 + 2 = 5 → F
- Delhi is in Russia and 2 + 2 = 4 → F

2. Disjunction: Any two proposition can be combined by the word "or" to form a compound proposition said to be the disjunction.

Truth table

p

q

p ∨ q

T

F

T

F

T

F

Example
- Delhi is in India or 2 + 2 = 4 → T
- Delhi is in India or 2 + 2 = 5 → T
- Delhi is in Russia or 2 + 2 = 4 → T
- Delhi is in Russia or 2 + 2 = 6 → F

3. Negation : The negatiion proposition of any given proposition p is the proposition whose truth value is opposite to p.

Truth table

p

~p

T

F

T

Example
- p ≡ "This flower is pink."
- ~p ≡ "This flower is not pink."

Tautologies and contradiction

A proposition is said to be an tautologies if it contain only 'T' in last column of truth table and if it contain only 'F' in last column of truth table then it is called contradiction.

Contingency

A preposition what is neither tautolgy nor contradiction.

Questions

1. Show that the following proposition is tautologies {(P ∨ ~Q) ∧ (~P ∨ ~Q)} ∨ Q

Solution :

P

Q

~P

~Q

E = P ∨ ~Q

G = ~P ∨ ~Q

E ∧ G

(E ∧ G) ∨ Q

T

F

T

F

T

F

T

F

T

F

T

F

T

F

T

Its tautologies as answer column is all 'T'.

2. Prove that the proposition p ∨ ~ (q ∨ r) and (p ∨ ~q) ∨ ~r are equivalent.

Hint : As this have 3 variables so the possible combination would be 2³ = 8

3. Determine whether the following proposition is contradiction or a tautolgy.
(p ∨ q)∧(p ∨ ~q)∧(~p ∨ q)∧(~p ∨ ~q)

4. Determine whether the following is tautology or contradiction.
Q ∨ (P ∧ ~Q) ∨ (~P ∨ ~Q)

Conditional Statement

Many statements are of the form "if p then q" such statement are said to be the conditional statement and denoted by p ⇒ q or p → q.

Truth Table

p

q

p → q

T

F

T

F

T

Hint : where ever p is F then p→q will be T, and where p is T and q is also T then only p→q will be T.

Biconditional Statement

A statement "p if and only if q" such statement are said to be bi-conditional statement and denoted by p ⇔ q or p ⟷ q

Truth Table

p

q

p ⟷ q

T

F

T

F

T

F

Hint : only in T T and F F case the output is T.

Converse, Inverse and Contrapositive of Conditinal statement

1. Converse of conditional statement

Let p → q be a conditional statement then q → p is called its converse.
Example : If X is a labourer then he is poor.
Its converse → If X is poor then he is labourer.

2. Inverse of conditional statement

Let p → q be a conditional statement then ~p → ~q is called its inverse.
Example : If Harsa read book then he will get knowledge.
Its inverse → If Harsa not read book then he will not get knowledge.

3. Contrapositive of conditional statement

Let p → q be a conditional statement then ~q → ~p is called contrapositive.
Example : If f(x) is differentiable then it is continuous.
Its contrapositive → If f(x) is not continuous then it is not differentiable.

Questions

1. Show that (p ∧ q) → (p ∨ q) is a tautolgy.

2. Is the formula tautolgy p → (p ∧ (q → p))

3. Prove that following is tautology or not (p ∨ q ∨ r) ↔ [(((p → q)→ q)→ r)→ r]

4. show that p ⇒ (q⇒r) ≡ (p ∧ q) ⇒ r

Algebra of preposition

These are useful to simplify expression.

Idempotent law
- p ∧ p ⇔ p and p ∨ p ⇔ p
Associative law
- (p ∨ q) ∨ r = p ∨ (q ∨ r)
  and (p ∧ q) ∧ r = p ∧ (q ∧ r)
Commutative law
- p ∧ q ⇔ q ∧ p and p ∨ q ⇔ q ∨ p
Distributive law
- p ∨ (q ∧ r) = (p ∨ q) ∧ (p ∨ r)
- p ∧ (q ∨ r) = (p ∧ q) ∨ (p ∧ r)
De-Morgan law
- ~(p ∧ q) ⇔ ~p ∨ ~q and ~(p ∨ q) ⇔ ~p ∧ ~q
p → q ⇔ ~p ∨ q

Normal Form

When there are big big statement then their truth tables become very large. So, by using normal form we can convert them into small statements.
There are two type of normal form
1. Conjunction Normal Form.
2. Disjunction Normal Form.

Normal Form

Let A(p1, p2, p3, ...., pn) be a statement formula then the construction of truth table may not be practical always.
So, we consider alternate procedure known as reduction to normal form.

1. Disconjunction Normal Form : A statement form which consists of disjunction(or) between conjunction(and) is called DBF.
Example : (1) (p ∧ q) ∨ r
(2) (p ∧ ~q) ∨ (~p ∧ r) ∨ (r ∧ ~q)

Example : Obtain the DNF of the form (p → q) ∧ (~p ∧ q)
Solution :
we know that
p → q ⇔ ~p ∨ q
So, (~p ∨ q) ∧ (~p ∧ q)
Apply distributive law
(~p ∧ ~p ∧ q) ∨ (q ∧ ~p ∧ q)
⇒ (~p ∧ q) ∨ (q ∧ ~p)

2. Conjunction Normal Form : A statement form which consists of conjunction between disjunction is called CNF.
Example : (i) p ∧ q (ii) (~p ∨ q) ∧ (~p ∨ r)

Example : Obtain CNF of the form (p ∧ q) ∨ (~p ∧ q ∧ r)
Solution : (p ∧ q) ∨ (~p ∧ q ∧ r)
using distibutive law
(p ∨ (~p ∧ q ∧ r)) ∧ (q ∨ (~p ∧ q ∧ r))
[(p ∨ ~p) ∧ (p ∨ q) ∧ (p ∨ r)] ∧ [(q ∨ ~p) ∧ (q ∨ q) ∧ (q ∨ r)]
⇒ (p ∨ q) ∧ (p ∨ r) ∧ [(q ∨ ~p) ∧ q ∧ (q ∨ r)]

Questions

Obtain DNF of p ∨ (~p → (q ∨ (q → ~r)))
Obtain CNF of (p → q) ∧ (q ∨ (p ∧ r)))
Find CNF of p ∧ (p → q)
Obtain CNF of (~p → r) ∧ (q ↔ p)
(q ↔ p) becomes ((q → p) ∧ (p → q)