Chapter 1 Unit 1: Propositional Logic

PrevNextBack

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

PQ~QP^QP^~Q(P^Q)v(P^~Q)
001000
010000
101011
110101

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.

PPPvP
000
111

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.

XYY^X~(Y^X)Xv~(Y^X)
00011
01011
10011
11101

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)

pq~qp+(~q)
0011
0100
1011
1101

(b) (~p)

p~p
01
10

(c) ~(p.q)

pqp.q~(p.q)
0001
0101
1001
1110

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

pq~p~q(~p)+(~q)
00111
01101
10011
11000

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

XX'ZX'+Z
0101
0111
1000
1011

X→Y is equivalent to X' + Y

XX'YX'+Y
0101
0111
1000
1011

Y→Z is equivalent to Y' + Z

YY'ZY'+Z
0101
0111
1000
1011
X→YY→Z(X→Y)^(Y→Z)~
1110
1110
0001
1110
X→Z~[(X→Y)
^(Y→Z)]
(X→Z)v
~[(X→Y)^(Y→Z)]
101
101
011
101

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~pq~q~p+q~q+p(~p+q)^(~q+p)
0101111
0110100
1001010
1010111

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

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

p~pq~q(~p)vq~qv[(~p)vq]
010111
011011
100101
101011

Question 8

Verify the following proposition with help of the truth table:
P v (~P ^ Q) = P v Q

P~PQ~P^QPv(~P^Q)PvQ
010000
011111
100011
101011

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

aba ^ b
000
010
100
111

Disjunction

aba v b
000
011
101
111

Question 11

Complete the following tables:

(a)

pq~pp⇒q~pvq
00111
01111
10000
11011

(b)

pq~p~q~pvqp^(~q)
001110
011010
100101
110010

(c)

pqp^qpvq(p^q)⇒(pvq)
00001
01011
10011
11111

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)

pqrp⇒qq⇒r(p⇒q)
^(q⇒r)
(p⇒r)[(p⇒q)
^(q⇒r)]
⇒(p⇒r)
00011111
00111111
01010011
01111111
10001001
10101011
11010001
11111111

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

pqp⇒q(p⇒q)^p
0010
0110
1000
1111
(p⇒q)^pq[(p⇒q)^p]⇒q
001
011
001
111

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:

ABB'A⇒BB⇒AA⇒B
^
B⇒A
A.BB'+A.BA⇒B
^
B⇒A

B'+A.B
001111011
010100001
101010011
110111111

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

XYX ⇔ Y
001
010
100
111

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

aba⇒bb⇒a(a⇒b).(b⇒a)
00111
01100
10010
11111

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

pq~p~qp⇒q~p^~q~q⇒(~p^~q)(p⇒q)

[~q⇒
(~p^~q)]
00111111
01101011
10010001
11001011

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

(c) Differentiate between a tautology and a contradiction.

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

PQ~P~Q~P⇒Q(~P⇒Q)^PP^~QP^Q(P^~Q)v(P^Q)
001100000
011010000
100111101
110011011

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.

PQ~PQ'~P+Q'P.(~P+Q')P⇒Q(P⇒Q)'
00111010
01101010
10011101
11000010

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 symbolor ⇔ 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.