# Chapter 1 Unit 1: Propositional Logic

**Contents**

## Write short answers

#### Question 1

What do you understand by 'Logic' and 'Propositional Logic'?

**Logic is a collection of rules for reasoning. In logic, we discuss about true or false of the statements and how to determine it with the help of other statements.**

**A proposition is a sentence that is either true or false. Propositional Logic is the logic of sentences.**

#### Question 2

Prove the following relation:

(P ^ Q) v (P ^ ~Q) = P

P | Q | ~Q | P^Q | P^~Q | (P^Q)v(P^~Q) |
---|---|---|---|---|---|

0 | 0 | 1 | 0 | 0 | 0 |

0 | 1 | 0 | 0 | 0 | 0 |

1 | 0 | 1 | 0 | 1 | 1 |

1 | 1 | 0 | 1 | 0 | 1 |

**The columns of P and (P ^ Q) v (P ^ ~Q) have the same entries. Hence, the relation is proved.**

#### Question 3

What is a proposition?

**A proposition is a sentence that is either true or false.**

#### Question 4

State the law represented by the following proposition and prove it with the help of a truth table:

P v P = P

**Idempotence law.**

P | P | PvP |
---|---|---|

0 | 0 | 0 |

1 | 1 | 1 |

#### Question 5

How will you distinguish a proposition from a compound proposition?

**A proposition represented as a simple sentence is called simple proposition whereas when two or more propositions are joined together with the help of some connecting words then the resulting proposition is said to be 'Compound Proposition'.**

#### Question 6

If (~P ⇒ Q) then write its :

(i) **Inverse****— (P ⇒ ~Q)**

(ii) **Converse****— (Q ⇒ ~P)**

#### Question 7

Define the following terms with a suitable example for each of them:

(a) Conjunction

**Conjunction joins two or more propositional statements with the help of 'and' connective. It is represented by symbol '^' or '.'(dot). The conjunction of two or more propositions results in true if all the propositions are true otherwise, false.**

**For example:****a: Sky is clear.****b: You can go out.****The conjunction of above mentioned propositions will be 'Sky is clear and you can go out'. It can be represented in expression form as (a ^ b). Alternatively, it can also be written as (a.b).**

(b) Disjunction

**Disjunction is the term used to combine two or more propositional statements with 'or' connective. It is represented with the symbol 'v' or '+'. It results in false if both the operands are false otherwise, true.**

**For example:****a: 8 is divisible by 2.****b: It is an even number.****These two propositions are combined using Disjunction like this — '8 is divisible by 2 or it is an even number.' It can be represented in expression form as (a v b). Alternatively, it can also be written as (a + b).**

(c) Converse

**A conditional obtained by interchanging the antecedent and consequent of the given conditional is known as Converse. The Converse of a given conditional** `'If a then b'`

**will be written as** `'If b then a'`

**.**

**For example:****If 16 is divisible by 2 then it is an even number.****Converse —****If 16 is an even number then it is divisible by 2.**

(d) Inverse

**Inverse is a conditional statement that can be obtained by negating the antecedent and consequent of the given conditional. The inverse of a given conditional** `'If a then b'`

**can be written as** `'If ~a then ~b'`

**.**

**For example:****If you practice well then you will win the match.****Inverse****— If you don't practice well then you won't win the match.**

## Answer the following

#### Question 1

The statements are given as:

If p : Jitendra Kumar is a computer teacher.

q : Rahul is a student.

Write these statements in symbolic form:

(a) Jitendra Kumar is a computer teacher and Rahul is a student.

**p . q**

(b) Jitendra Kumar is a computer teacher and Rahul is not a student.

**p . ~q**

(c) Jitendra Kumar is not a computer teacher and Rahul is a student.

**~p . q**

(d) Neither Jitendra Kumar is a computer teacher nor Rahul is a student.

**~p . ~q**

(e) Either Jitendra Kumar is a computer teacher or Rahul is a student.

**p + q**

#### Question 2

Show that X v ~ (Y ^ X) is a tautology.

X | Y | Y^X | ~(Y^X) | Xv~(Y^X) |
---|---|---|---|---|

0 | 0 | 0 | 1 | 1 |

0 | 1 | 0 | 1 | 1 |

1 | 0 | 0 | 1 | 1 |

1 | 1 | 1 | 0 | 1 |

**Column X v ~ (Y ^ X) has all entries as 1. Hence, X v ~ (Y ^ X) is a tautology.**

#### Question 3

Construct the truth table for the following:

(a) p+(~q)

p | q | ~q | p+(~q) |
---|---|---|---|

0 | 0 | 1 | 1 |

0 | 1 | 0 | 0 |

1 | 0 | 1 | 1 |

1 | 1 | 0 | 1 |

(b) (~p)

p | ~p |
---|---|

0 | 1 |

1 | 0 |

(c) ~(p.q)

p | q | p.q | ~(p.q) |
---|---|---|---|

0 | 0 | 0 | 1 |

0 | 1 | 0 | 1 |

1 | 0 | 0 | 1 |

1 | 1 | 1 | 0 |

(d) (~p)+(~q)

p | q | ~p | ~q | (~p)+(~q) |
---|---|---|---|---|

0 | 0 | 1 | 1 | 1 |

0 | 1 | 1 | 0 | 1 |

1 | 0 | 0 | 1 | 1 |

1 | 1 | 0 | 0 | 0 |

#### Question 4

State whether the following expression is a Tautology, Contradiction or the Contingency with help of the truth table.

(X→Z) v ~[(X→Y) ^ (Y→Z)]

**X→Z is equivalent to X'+ Z**

X | X' | Z | X'+Z |
---|---|---|---|

0 | 1 | 0 | 1 |

0 | 1 | 1 | 1 |

1 | 0 | 0 | 0 |

1 | 0 | 1 | 1 |

**X→Y is equivalent to X' + Y**

X | X' | Y | X'+Y |
---|---|---|---|

0 | 1 | 0 | 1 |

0 | 1 | 1 | 1 |

1 | 0 | 0 | 0 |

1 | 0 | 1 | 1 |

**Y→Z is equivalent to Y' + Z**

Y | Y' | Z | Y'+Z |
---|---|---|---|

0 | 1 | 0 | 1 |

0 | 1 | 1 | 1 |

1 | 0 | 0 | 0 |

1 | 0 | 1 | 1 |

X→Y | Y→Z | (X→Y)^(Y→Z) | ~ |
---|---|---|---|

1 | 1 | 1 | 0 |

1 | 1 | 1 | 0 |

0 | 0 | 0 | 1 |

1 | 1 | 1 | 0 |

X→Z | ~[(X→Y) ^(Y→Z)] | (X→Z)v ~[(X→Y)^(Y→Z)] |
---|---|---|

1 | 0 | 1 |

1 | 0 | 1 |

0 | 1 | 1 |

1 | 0 | 1 |

**As all entries of column (X→Z) v ~[(X→Y) ^ (Y→Z)] is one hence, it is a Tautology.**

#### Question 5

The statements are given as:

If p : Today is a holiday.

q : I will go to attend a birthday party.

Express each of the following statement in words:

(a) p v ~ q

**Today is a holiday OR I will not go to attend a birthday party.**

(b) ~q

**I will not go to attend a birthday party.**

(c) (~p) ^ q

**Today is not a holiday AND I will go to attend a birthday party.**

(d) ~(p v q)

**It is not true that Today is a holiday OR I will go to attend a birthday party.**

(e) ~((~p) ^ q)

**It is not true that today is not a holiday AND I will go to attend a birthday party.**

(f) (~p) . ~q

**Today is not a holiday AND I will not go to attend a birthday party.**

#### Question 6

Consider the statements:

If p : You work hard.

q : You will succeed in your life.

Translate each of following symbolic expressions in meaningful sentences:

(a) p ⇒ q

**If you work hard then you will succeed in your life.**

(b) q ⇒ p

**If you will succeed in your life it means that you work hard.**

(c) (~p) ⇒ (~q)

**If you don't work hard then you will not succeed in your life.**

(d) (~q) ⇒ (~p)

**If you don't succeed in your life it means that you didn't work hard.**

#### Question 7

Construct the truth tables for the following:

(a) (p ⇒ q) ^ (q ⇒ p)

**p ⇒ q is equivalent to ~p + q****q ⇒ p is equivalent to ~q + p****So, (p ⇒ q) ^ (q ⇒ p) is equivalent to (~p + q) ^ (~q + p)**

p | ~p | q | ~q | ~p+q | ~q+p | (~p+q)^(~q+p) |
---|---|---|---|---|---|---|

0 | 1 | 0 | 1 | 1 | 1 | 1 |

0 | 1 | 1 | 0 | 1 | 0 | 0 |

1 | 0 | 0 | 1 | 0 | 1 | 0 |

1 | 0 | 1 | 0 | 1 | 1 | 1 |

(b) q ⇒ [(~p) v q]

**q ⇒ [(~p) v q] is equivalent to ~q v [(~p) v q]**

p | ~p | q | ~q | (~p)vq | ~qv[(~p)vq] |
---|---|---|---|---|---|

0 | 1 | 0 | 1 | 1 | 1 |

0 | 1 | 1 | 0 | 1 | 1 |

1 | 0 | 0 | 1 | 0 | 1 |

1 | 0 | 1 | 0 | 1 | 1 |

#### Question 8

Verify the following proposition with help of the truth table:

P v (~P ^ Q) = P v Q

P | ~P | Q | ~P^Q | Pv(~P^Q) | PvQ |
---|---|---|---|---|---|

0 | 1 | 0 | 0 | 0 | 0 |

0 | 1 | 1 | 1 | 1 | 1 |

1 | 0 | 0 | 0 | 1 | 1 |

1 | 0 | 1 | 0 | 1 | 1 |

**Columns of P v (~P ^ Q) and P v Q have the same entries. Hence, the proposition is proved.**

#### Question 9

Write converse, inverse and contrapositive of each statement:

(a) If it rains, then you will not play.**Converse****— If you will not play then it will rain.****Inverse****— If it doesn't rain then you will play.****Contrapositive****— If you will play then it will not rain.**

(b) If you work hard, then you will pass.**Converse****— If you will pass then you worked hard.****Inverse****— If you don't work hard, then you will not pass.****Contrapositive****— If you will not pass then you didn't work hard.**

(c) If I run fast, then I will win the race.**Converse****— If I will win the race then I ran fast.****Inverse****— If I don't run fast, then I will not win the race.****Contrapositive****— If I will not win the race then I didn't run fast.**

#### Question 10

Write the truth table of a two input conjunction and disjunction.

**Conjunction**

a | b | a ^ b |
---|---|---|

0 | 0 | 0 |

0 | 1 | 0 |

1 | 0 | 0 |

1 | 1 | 1 |

**Disjunction**

a | b | a v b |
---|---|---|

0 | 0 | 0 |

0 | 1 | 1 |

1 | 0 | 1 |

1 | 1 | 1 |

#### Question 11

Complete the following tables:

(a)

p | q | ~p | p⇒q | ~pvq |
---|---|---|---|---|

0 | 0 | 1 | 1 | 1 |

0 | 1 | 1 | 1 | 1 |

1 | 0 | 0 | 0 | 0 |

1 | 1 | 0 | 1 | 1 |

(b)

p | q | ~p | ~q | ~pvq | p^(~q) |
---|---|---|---|---|---|

0 | 0 | 1 | 1 | 1 | 0 |

0 | 1 | 1 | 0 | 1 | 0 |

1 | 0 | 0 | 1 | 0 | 1 |

1 | 1 | 0 | 0 | 1 | 0 |

(c)

p | q | p^q | pvq | (p^q)⇒(pvq) |
---|---|---|---|---|

0 | 0 | 0 | 0 | 1 |

0 | 1 | 0 | 1 | 1 |

1 | 0 | 0 | 1 | 1 |

1 | 1 | 1 | 1 | 1 |

#### Question 12

Differentiate between proposition and wff.

**A proposition is a sentence that is either true or false whereas wff (Well-Formed Formula) is a system of representing a propositional statement or expression in short form.**

#### Question 13

Show that the given statements are tautologies:

(a) [(p ⇒ q) ^ (q ⇒ r)] ⇒ (p ⇒ r)

p | q | r | p⇒q | q⇒r | (p⇒q) ^(q⇒r) | (p⇒r) | [(p⇒q) ^(q⇒r)] ⇒(p⇒r) |
---|---|---|---|---|---|---|---|

0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 |

0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 |

0 | 1 | 0 | 1 | 0 | 0 | 1 | 1 |

0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |

1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 |

1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 |

1 | 1 | 0 | 1 | 0 | 0 | 0 | 1 |

1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |

(b) [(p ⇒ q) ^ p] ⇒ q

p | q | p⇒q | (p⇒q)^p |
---|---|---|---|

0 | 0 | 1 | 0 |

0 | 1 | 1 | 0 |

1 | 0 | 0 | 0 |

1 | 1 | 1 | 1 |

(p⇒q)^p | q | [(p⇒q)^p]⇒q |
---|---|---|

0 | 0 | 1 |

0 | 1 | 1 |

0 | 0 | 1 |

1 | 1 | 1 |

#### Question 14

Answer the following questions:

(a) From premises A ⇒ B and B ⇒ A, conclude B' + A.B.

**We need to prove:****(A ⇒ B) ^ (B ⇒ A) ⇒ (B' + A.B) = 1**

**By using truth table:**

A | B | B' | A⇒B | B⇒A | A⇒B ^ B⇒A | A.B | B'+A.B | A⇒B ^ B⇒A ⇒ B'+A.B |
---|---|---|---|---|---|---|---|---|

0 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 1 |

0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 1 |

1 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 1 |

1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 |

**All the elements of the column (A ⇒ B) ^ (B ⇒ A) ⇒ (B' + A.B) are 1, i.e. a tautology. Hence, B' + A.B is the conclusion of premises A ⇒ B and B ⇒ A.**

**By using algebraic method:**

```
(A ⇒ B) ^ (B ⇒ A) ⇒ (B' + A.B)
((A ⇒ B) . (B ⇒ A))' + (B' + A.B) [a⇒b=a'+b]
((A' + B) . (B' + A))' + (B' + A.B)
(A' + B)' + (A + B')' + (B' + A.B) [Demorgan's Law]
(A'' . B') + (A' + B'') + (B' + A.B) [Demorgan's Law]
A.B' + A'.B + (B' + A.B)
A.B' + A'.B + [(A + B').(B + B')] [Distributive Law]
A.B' + A'.B + [(A + B'). 1] [B+B'=1]
A.B' + A'.B + A + B' [(A+B').1=A+B']
A.B' + B' + (A'.B + A)
A.B' + B' + [(A + A').(A + B)] [Distributive Law]
A.B' + B' + [1.(A + B)] [A+A'=1]
A.B' + B' + A + B
(A.B' + B) + B' + A
[(A + B).(B + B')] + B' + A [Distributive Law]
[(A + B).1] + B' + A [B+B'=1]
A + B + B' + A [B+B'=1]
A + 1 + A [1+A=1]
A + 1
1
```

(b) (i) Let P : He has fax and Q : He uses e-mail.

Write the following statement in terms of P and Q:

He has fax and he may or may not use e-mail.

**P ^ (Q v ~Q)**

(c) Write the law of conditional elimination.

**a → b = a' + b**

(d) Let X=1 represents "you work hard" and 0 otherwise.

Let Y=1 represents "you succeed" and 0 otherwise.

Using the information given above, construct:

(i) the truth table and

(ii) the logical expression for the following statement:

"If and only if you work hard you succeed".

**Truth Table**

X | Y | X ⇔ Y |
---|---|---|

0 | 0 | 1 |

0 | 1 | 0 |

1 | 0 | 0 |

1 | 1 | 1 |

Logical expression for the statement will be:

X ⇔ Y = X'.Y' + X.Y

#### Question 15

Answer the following questions:

(a) Draw the truth table to prove the following proportional expression:

a ⇒ b = (a ⇒ b) . (b ⇒ a)

**Truth Table**

a | b | a⇒b | b⇒a | (a⇒b).(b⇒a) |
---|---|---|---|---|

0 | 0 | 1 | 1 | 1 |

0 | 1 | 1 | 0 | 0 |

1 | 0 | 0 | 1 | 0 |

1 | 1 | 1 | 1 | 1 |

**As the columns a ⇒ b and (a ⇒ b) . (b ⇒ a) does not contain identical values hence this proportional expression is invalid.**

(b) Determine whether the given expression is valid or not:

(p ⇒ q) ⇒ [~q ⇒ (~p^~q)]

p | q | ~p | ~q | p⇒q | ~p^~q | ~q⇒(~p^~q) | (p⇒q) ⇒ [~q⇒ (~p^~q)] |
---|---|---|---|---|---|---|---|

0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 |

0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 |

1 | 0 | 0 | 1 | 0 | 0 | 0 | 1 |

1 | 1 | 0 | 0 | 1 | 0 | 1 | 1 |

**As the expression is a tautology hence, it is a valid expression.**

(c) Differentiate between a tautology and a contradiction.

Tautology | Contradiction |
---|---|

A proposition is a tautology if it is true under all conditions. | A proposition is a contradiction if it is false under all conditions. |

The column of a tautology in a truth table contains only 1's. | The column of contradiction in a truth table contains only 0's. |

#### Question 16

Using the truth table verify the expression

(~P ⇒ Q) ^ P = (P ^ ~Q) v (P ^ Q)

P | Q | ~P | ~Q | ~P⇒Q | (~P⇒Q)^P | P^~Q | P^Q | (P^~Q)v(P^Q) |
---|---|---|---|---|---|---|---|---|

0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |

0 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |

1 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 1 |

1 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 1 |

**The columns (~P ⇒ Q) ^ P and (P ^ ~Q) v (P ^ Q) have identical values hence the expression is proved.**

#### Question 17

If (X ⇒ Y) then write its:

(i) **Converse****— Y ⇒ X**

(ii) **Contrapositive****— ~Y ⇒ ~X**

#### Question 18

Define the term Contingency, Contradiction and Tautology.

**Contingency****When a propositional statement is concluded into true as well as false for different values of the variables, it is said to be Contingency.**

**Contradiction****When a propositional statement is false for all values of the variables, it is said to be Contradiction.**

**Tautology****When a propositional statement is true for all values of the variables, it is said to be Tautology.**

#### Question 19

Verify P . (~P + Q') = (P ⇒ Q)' using truth table.

P | Q | ~P | Q' | ~P+Q' | P.(~P+Q') | P⇒Q | (P⇒Q)' |
---|---|---|---|---|---|---|---|

0 | 0 | 1 | 1 | 1 | 0 | 1 | 0 |

0 | 1 | 1 | 0 | 1 | 0 | 1 | 0 |

1 | 0 | 0 | 1 | 1 | 1 | 0 | 1 |

1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 |

**The columns P.(~P+Q') and (P⇒Q)' have identical values. Hence, the expression is proved.**

#### Question 20

What is meant by implication? How is it different from biconditional?

**When two propositional statements are joined together such that the second statement is a logical consequent of the first, then the relation is said to be implication. It is denoted by → , ⇒ or ⊃ . For example, A → B refers to as 'A implies B' and has its literal meaning as 'if A is true then B is true'. A → B can be represented as A' + B.****A Bi-Conditional joins two logical statements in such a way that the result is true if both of them have the same truth values. It is represented by the symbol ↔or ⇔ and is said to be 'if and only if'. For example, A ⇔ B refers to 'A bi-conditional B' and can be represented as A'.B' + A.B.**