Propositional Logic

INTRODUCTION TO PROPOSITIONAL LOGIC

SENTENCE

A number of words making complete grammatical structure having sense and meaning is called a sentence.

There are two types of sentence

Declarative Sentence:

Declarative sentence makes a statement that declares something (gives reliable information or idea).

Non-Declarative Sentence:

Statement that does not declares something(give ideas) are called non-declarative sentence.
Sentences which are imperative, interrogative or exclamatory are not propositions.

Imperative Sentence – Command / Request / Wishes
Interrogative Sentence – Question type
Exclamatory Sentence – Express strong feeling

TRUTH VALUE

The truth or falsify of a proposition is called truth value.

If a proposition is true then its truth value is T.
If a proposition is false then its truth value is F.

Note:

p, q, r, s ……….| P, Q, R, S ………. are used to denote proposition.
These variables are called proposition variables.

WHAT IS PROPOSITION OR STATEMENT?

A Propositional is a declarative sentence which is either TRUE of FALSE but not both.

Examples of Propositions with truth-values

1) The value of PI is 22/7 (True)

2) 2 + 2 = 3 (False)

3) 25 % 5 = 3 + 2 (True)

4) Delhi is the capital of England (False)

5) The sun rises in the east (True)

Sentences which are not propositions

1) Have a nice day (Wishes)

2) x + y = z (The value of x, y and z is not known)

3) What a beautiful Rose (Exclamatory)

4) 6 – x = 4 (The value of x is not known)

5) Please, take a cup of coffee (Request)

6) 1 + 3 + 5 +……………2n+1 (The value of n is not known)

7) To save rain water (Command)

8) What is your name? (Question)

Homework Exercise

Which of the following is/are proposition(s).

Also if you find the proposition, state whether it is TRUE or FALSE:

1) 9 is an odd number

2) x is an even number

3) Good Luck!

4) 9 – 3=7

5) Do your homework

6) The value of 0 factorial is 1

7) x % 5 = 25

8) What is the time now?

9) Do your homework

10) Dog is an animal

11) What a wonderful joke is this

12) The earth is round

13) Namakkal is in England

14) 7 – 4 = 5 + 2

15) Please help me

16) A * 5 = 75

17) Tajmahal is in Chennai

18) What is your name?

LOGIC

Any formal system can be consider a logic if it has

a well defined syntax
a well defined semantics and
a well defined proof-theory

The syntax of a logic defines the syntactically acceptable objects of the language, which are properly called well formed formula (wff)
The semantics of a logic associate each formula with a meaning
The proof theory is concerned with manipulating formulae according to certain rules

WELL FORMED FORMULA (wff)

Wffs are constructed using the following rules

All propositional constants and propositional variables are wffs
Truth values (true and false) are wffs
Each atomic formula is a wff

Example: 5 is a prime number, p, q

All connectives connecting wffs are wffs

Example: If A and B are wffs, then A, (A ∧ B), (A ∨ B), (A ⟶ B), and (A ↔ B)are also wff

If x is a variable, and A is a wff, then ∀ x A and x A are also wff

Are these expressions WFF?

1) P – Yes, all letters are wff

2) ~~~~(P∧Q) - Yes

3) (P∨Q∨R) – No, should be (P∨Q)∨R or P∨(Q∨R)

4) (~(P∧S)) –No, an extra pair of brackets

5) (P~) – No, put ~ in front of the propositions

6) ((P↔Q)) –No, an extra pair of brackets

7) ~(~G∧~(~P∧~Q)) – Yes

8) ∧pq – No, ∧ is placed between p and q

PROPOSITION TYPES: Atomic and Compound Proposition

To analyze these statements either individually or in a composite manner

Primary / Atomic Statements

A declarative sentence which cannot be further split up into simple sentences.

Example:

p: The sun rises in the east

Compound / Composite / Molecular Statements

Statement which contain one or more primary statements with some connectives.

Example:

p: The sun rises in the east

q: The sun sets in the west

p ∧ q: The sun rises in the east and sets in the west

BASIC LOGICAL OPERATIONS / CONNECTIVES

In propositional logic generally we use five connectives which are −

AND (∧)
OR (∨)
NOT (~)
Implication / if-then / Conditional (→)
If and only if / Biconditional (↔)

AND / Conjunction (∧)

When p and q are any propositions, the proposition "p and q" is a compound proposition, denoted by p ∧ q and referred as the conjunction of p and q.
The conjunction of p and q is true only when both p and q are true. Otherwise, it is false.

Truth table of p ∧ q

p	Q	p ∧ q
True	True	True
True	False	False
False	True	False
False	False	False

Example:

12 is divisible by 3 and 3 is a prime number

p: 12 is divisible by 3 → True

q: 3 is a prime number →True

p∧ q: True ∧ True = True

Disjunction / OR (∨)

If p and q are two propositions, then "p or q" is a compound proposition, denoted by p ∨ q and referred to as the disjunction of p and q.
The disjunction of p and q is true whenever at least one of the two propositions is true, and it is false only when both p and q are false.

Truth table of p ∨ q

p	q	p V q
True	True	True
True	False	True
False	True	True
False	False	False

Example:

12 is divided by 3 or 4 is a prime number

p: 12 is divided by 3 → True

q: 4 is a prime number → False

pVq: True V False = True

Negation (¬)

It means the opposite of the original proposition.
Let p be a proposition, ¬p is called negation of p which simply states that ‘It is not the case that p’
if p is true then¬pis false and vice versa.
¬p is also denoted as ~p and p’

Truth table of ¬ p

p	¬ p
True	False
False	True

Example:

p: Chennai is in India

¬p: Chennai is not in India

Conditional Proposition

If p and q are two propositions then the compound proposition "if p, then q", i.e., denoted by p→q iscalled a conditional proposition or an implication.
The implication p→ q is false only when p is true, and q is false; otherwise, it is always true.

Truth table of p → q

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

Example:

If a = b and b = c, then a = c.

If I get money, then I will purchase a computer.

If you win in sports then, you will be selected.

Biconditional Proposition

If p and q are two propositions, the compound proposition "p if and only if q" (p ↔ q)is called a biconditional proposition or an equivalence
Alternatively, ‘p ↔ q’is also expressed as ‘p iff q’ and ‘p is necessary and sufficient for q’ and vice versa
The equivalence p ↔ q is true whenever the truth values of p and q are same

Truth table of p ↔ q

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

Example:

Two lines are parallel if and only if they have the same slope

You will pass the exam if and only if you will work hard.

TAUTOLOGY, CONTRADICTIONS AND CONTINGENCY

Tautology - Compound proposition which is always TRUE

A compound proposition P = P(p_1,p_{2, . . . . .}p_n), where p_1,p_{2, . . . . .}p_n are propositions, is called a tautology, if it is true for everywhere in the last column of its truth table.
i.e., it contains the only True in the final column of its truth table.

Example: Prove that the proposition (p⟶q) ↔(∼q⟶∼p) is a tautology.

Make the truth table of the above proposition

P	q	p→q	~q	~p	~q⟶∼p	(p→q)⟷( ~q⟶~p)
T	T	T	F	F	T	T
T	F	F	T	F	F	T
F	T	T	F	T	T	T
F	F	T	T	T	T	T

As the final column contains all True’s, so it is a tautology.

Example − Prove [(A→B)∧A]→B is a tautology

A	B	A → B	(A → B) ∧ A	[( A → B ) ∧ A] → B
T	T	T	T	T
T	F	F	F	T
F	T	T	F	T
F	F	T	F	T

As we can see every value of [(A→B)∧A]→B is "True", it is a tautology.

Contradictions - Compound proposition which is always FALSE

A compound proposition P is called a contradiction, if it is false for everywhere in the last column of its truth table.
i.e., it contains only False in the final column of its truth table

Example − Prove (A∨B)∧[(¬A)∧(¬B)] is a contradiction

A	B	A ∨ B	¬ A	¬ B	(¬ A) ∧ ( ¬ B)	(A ∨ B) ∧ [( ¬ A) ∧ (¬ B)]
T	T	T	F	F	F	F
T	F	T	F	T	F	F
F	T	T	T	F	F	F
F	F	F	T	T	T	F

As we can see every value of (A∨B)∧[(¬A)∧(¬B)] is “False”, it is a contradiction.

Example: Show that the proposition p ∧∼p is a contradiction.

p	∼p	p ∧∼p
T	F	F
F	T	F

Since, the last column contains all False's, so it's a contradiction.

Contingency- Compound proposition which is sometimes TRUE and sometimes FALSE

If a proposition is neither a tautology nor a contradiction, it is called a contingency.
i.e.,which has both some true and some false values for every value of its propositional.

p	q	p →q	p∧q	(p →q)⟶ (p∧q )
T	T	T	T	T
T	F	F	F	T
F	T	T	F	F
F	F	T	F	F

Example − Prove (A∨B)∧(¬A) a contingency

The truth table is as follows −

A	B	A∨B	¬ A	(A∨B)∧(¬ A)
T	T	T	F	F
T	F	T	F	F
F	T	T	T	T
F	F	F	T	F

As we can see every value of (A∨B)∧(¬A) has both “True” and “False”, it is a contingency.

PROPOSITIONAL EQUIVALENCES

Two propositions are said to be logically equivalent if they have exactly the same truth values under all circumstances.
Two propositions are logically equivalent if any of the following 3 conditions hold −

The truth tables of each proposition have the same truth values.
The bi-conditional proposition X⇔Y (≡) is a tautology.
By using the below table which contains the fundamental logical equivalent expressions.

Note:

A truth table is a table that displays the relationships between the truth values of sub-propositions and that of compound proposition constructed from them.
Number of rows needed to construct the truth table of given statement is 2ⁿ rows where n is the number of variables used in the given proposition

Propositions	Number of variables	Number of rows needed
p →¬p	1 variable	2¹ = 2 rows
(A∨B)∧[(¬A)∧(¬B)]	2 variable	2² = 4 rows
p ∨ (q ∧ r) = (p ∨ q) ∧ (p ∨ r)	3 variable	2³ = 8 rows

DUALITY PRINCIPLE

Duality principle states that for any true proposition, the dual proposition obtained by

· replace ∧ by ∨

· replace ∨ by ∧

· replace T by F

· replace F by T

LAWS OF THE ALGEBRA OF PROPOSITIONS

Name of the law	Primal Form	Dual Form
Idempotent laws	p ∨ p = p	p ∧ p=p
Identity laws	p ∨ F = p	p ∧ T= p
Dominant laws	p ∧ F=F	p ∨ T = T
Complement laws	p ∨ ¬p = T	p ∧ ¬p = F
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)
Absorption laws	p ∨ (p ∧ q) = p	p ∧ (p ∨ q) = p
Involution laws	¬¬p = p
De Morgan's laws	(i) ¬(p ∨ q) = ¬p ∧ ¬q	(ii) ¬(p ∧ q) =¬p ∨ ¬q

Example − Prove ¬(A∨B)and[(¬A)∧(¬B)] are equivalent

Testing by 1^st method (Matching truth table)

A	B	A ∨ B	¬ (A ∨ B)	¬ A	¬ B	[(¬ A) ∧ (¬ B)]
T	T	T	F	F	F	F
T	F	T	F	F	T	F
F	T	T	F	T	F	F
F	F	F	T	T	T	T

Here, we can see the truth values of ¬(A∨B)and[(¬A)∧(¬B)] are same, hence the propositions are equivalent.

Testing by 2^nd method (Bi-conditionality)

A	B	¬ (A ∨ B )	[(¬ A) ∧ (¬ B)]	[¬ (A ∨ B)] ⇔ [(¬ A ) ∧ (¬ B)]
T	T	F	F	T
T	F	F	F	T
F	T	F	F	T
F	F	T	T	T

As [¬(A∨B)]⇔[(¬A)∧(¬B)] is a tautology, the propositions are equivalent.

Search This Blog

Deepa PhD CS