Category: Propositional Logic

Tautology Contradiction Contingency

Propositions-

 

Before you go through this article, make sure that you have gone through the previous article on Propositions.

 

We have discussed-

  • Propositions are declarative statements that are either true or false but not both.
  • Connectives are used to combine the propositions.

 

 

In this article, we will discuss about the nature of proposition.

 

Also Read- Converting English Sentences to Propositional Logic

 

Determining Nature Of Proposition-

 

Here,

  • We will be given a compound proposition.
  • We will be asked to determine the nature of the given proposition.

 

 

Let us discuss all these terms one by one.

 

Tautology-

 

  • A compound proposition is called tautology if and only if it is true for all possible truth values of its propositional variables.
  • It contains only T (Truth) in last column of its truth table.

 

Contradiction-

 

  • A compound proposition is called contradiction if and only if it is false for all possible truth values of its propositional variables.
  • It contains only F (False) in last column of its truth table.

 

Contingency-

 

  • A compound proposition is called contingency if and only if it is neither a tautology nor a contradiction.
  • It contains both T (True) and F (False) in last column of its truth table.

 

Valid-

 

  • A compound proposition is called valid if and only if it is a tautology.
  • It contains only T (Truth) in last column of its truth table.

 

Invalid-

 

  • A compound proposition is called invalid if and only if it is not a tautology.
  • It contains either only F (False) or both T (Truth) and F (False) in last column of its truth table.

 

Falsifiable-

 

  • A compound proposition is called falsifiable if and only if it can be made false for some value of its propositional variables.
  • It contains either only F (False) or both T (Truth) and F (False) in last column of its truth table.

 

Unfalsifiable-

 

  • A compound proposition is called unfalsifiable if and only if it can never be made false for any value of its propositional variables.
  • It contains only T (Truth) in last column of its truth table.

 

Satisfiable-

 

  • A compound proposition is called satisfiable if and only if it can be made true for some value of its propositional variables.
  • It contains either only T (Truth) or both T (True) and F (False) in last column of its truth table.

 

Unsatisfiable-

 

  • A compound proposition is called unsatisfiable if and only if it can not be made true for any value of its propositional variables.
  • It contains only F (False) in last column of its truth table.

 

Important Points-

 

It is important to take a note of the the following points-

  • All contradictions are invalid and falsifiable but not vice-versa.
  • All contingencies are invalid and falsifiable but not vice-versa.
  • All tautologies are valid and unfalsifiable and vice-versa.
  • All tautologies are satisfiable but not vice-versa.
  • All contingencies are satisfiable but not vice-versa.
  • All contradictions are unsatisfiable and vice-versa.

 

 

Also Read- Converse, Inverse and Contrapositive

 

PRACTICE PROBLEMS BASED ON DETERMINING NATURE OF PROPOSITIONS-

 

Problem-01:

 

Determine the nature of following propositions-

  1. p ∧ ∼p
  2. (p ∧ (p → q)) → ∼q
  3. [ (p → q) ∧ (q → r) ] ∧ ( p ∧ ∼r)
  4. ∼(p → q) ∨ (∼p ∨ (p ∧ q))
  5. (p ↔ r) → (∼q → (p ∧ r))

 

Solution-

 

Let us solve all the parts one by one-

 

Part-01:

 

Method-01: Using Truth Table-

 

p∼pp ∧ ∼p
FTF
TFF

 

Clearly, last column of the truth table contains only F.

Therefore, given proposition is-

  • Contradiction
  • Invalid
  • Falsifiable
  • Unsatisfiable

 

Method-02: Using Algebra Of Proposition-

 

  • The given proposition is p ∧ ∼p
  • By complement law, p ∧ ∼p = F
  • So, given proposition is contradiction, invalid, falsifiable and unsatisfiable.

 

Method-03: Using Digital Electronics-

 

In terms of digital electronics,

  • The given proposition can be written as p.p’
  • Clearly, p.p’ = 0
  • So, given proposition is contradiction, invalid, falsifiable and unsatisfiable.

 

Part-02:

 

Method-01: Using Truth Table-

 

pq qp ∧ (p  q)∼q (p ∧ (p  q)) ∼q 
FFTFTT
FTTFFT
TFFFTT
TTTTFF

 

Clearly, last column of the truth table contains both T and F.

Therefore, given proposition is-

  • Contingency
  • Invalid
  • Falsifiable
  • Satisfiable

 

Method-02: Using Algebra Of Proposition-

 

We have-

(p ∧ (p → q)) → ∼q

= (p ∧ (∼p ∨ q)) → ∼q             { ∵ p → q = ∼p ∨ q }

= ∼(p ∧ (∼p ∨ q)) ∨ ∼q            { ∵ p → q = ∼p ∨ q }

= ∼((p ∧ ∼p) ∨ (p ∧ q)) ∨ ∼q   { Using Distributive law }

= ∼(F ∨ (p ∧ q)) ∨ ∼q              { Using Complement law }

= ∼(p ∧ q) ∨ ∼q                       { Using Identity law }

= ∼p ∨ ∼q ∨ ∼q                       { Using De Morgans law }

= ∼p ∨ ∼q

 

  • Clearly, the result is neither T nor F.
  • So, given proposition is a contingency, invalid, falsifiable and satisfiable.

 

Method-03: Using Digital Electronics-

 

We have-

(p ∧ (p → q)) → ∼q

= (p ∧ (∼p ∨ q)) → ∼q          { ∵ p → q = ∼p ∨ q }

= ∼(p ∧ (∼p ∨ q)) ∨ ∼q         { ∵ p → q = ∼p ∨ q }

 

Now in terms of digital electronics, we have-

= (p.(p’ + q))’ + q’

= (p.p’ + p.q)’ + q’

= (p.q)’ + q’                            { ∵ p.p’ = 0 }

= p’ + q’ + q’                           { Using De Morgan’s law }

= p’ + q’

 

  • Clearly, the result is neither 0 nor 1.
  • So, given proposition is a contingency, invalid, falsifiable and satisfiable.

 

Part-03:

 

Method-01: Using Truth Table-

 

Let [ (p → q) ∧ (q → r) ] ∧ ( p ∧ ∼r) = R (say)

 

pqr q r(p  q) ∧ (q  r)p ∧ ∼rR
FFFTTTFF
FFTTTTFF
FTFTFFFF
FTTTTTFF
TFFFTFTF
TFTFTFFF
TTFTFFTF
TTTTTTFF

 

Clearly, last column of the truth table contains only F.

Therefore, given proposition is-

  • Contradiction
  • Invalid
  • Falsifiable
  • Unsatisfiable

 

Method-02: Using Algebra Of Proposition-

 

We have-

[ (p → q) ∧ (q → r) ] ∧ ( p ∧ ∼r)

= [ (∼p ∨ q) ∧ (∼q ∨ r) ] ∧ ( p ∧ ∼r)                                               { ∵ p → q = ∼p ∨ q }

= [ ((∼p ∨ q) ∧ ∼q) ∨ ((∼p ∨ q) ∧ r) ] ∧ ( p ∧ ∼r)                            { Using Distributive law }

= [ ((∼p ∧ ∼q) ∨ (q ∧ ∼q)) ∨ ((∼p ∧ r) ∨ (q ∧ r)) ] ∧ ( p ∧ ∼r)         { Using Distributive law }

= [ ((∼p ∧ ∼q) ∨ F) ∨ ((∼p ∧ r) ∨ (q ∧ r)) ] ∧ ( p ∧ ∼r)                    { Using Complement law }

= [ (∼p ∧ ∼q) ∨ (∼p ∧ r) ∨ (q ∧ r) ] ∧ ( p ∧ ∼r)                               { Using Identity law }

= ((∼p ∧ ∼q) ∧ ( p ∧ ∼r)) ∨ ((∼p ∧ r) ∧ ( p ∧ ∼r)) ∨ ((q ∧ r) ∧ ( p ∧ ∼r))  { Using Distributive law }

= (∼p ∧ ∼q ∧ p ∧ ∼r) ∨ (∼p ∧ r ∧ p ∧ ∼r) ∨ (q ∧ r ∧ p ∧ ∼r)

= F ∨ F ∨ F                                                                                    { Using Complement law }

= F

 

  • Clearly, the result is F.
  • So, given proposition is a contradiction, invalid, falsifiable and unsatisfiable.

 

Method-03: Using Digital Electronics-

 

We have-

[ (p → q) ∧ (q → r) ] ∧ ( p ∧ ∼r)

= [ (∼p ∨ q) ∧ (∼q ∨ r) ] ∧ ( p ∧ ∼r)      { ∵ p → q = ∼p ∨ q }

 

Now in terms of digital electronics, we have-

= [ (p’ + q).(q’ + r) ] . (p.r’)

= [ p’.q’ + p’.r + q.q’ + q.r ] . (p.r’)

= [ p’.q’ + p’.r + 0 + q.r ] . (p.r’)             { ∵ q.q’ = 0 }

= [ p’.q’ + p’.r + q.r ] . (p.r’)

= p’.q’.p.r’ + p’.r.p.r’ + q.r.p.r’

= 0 + 0 + 0

= 0

 

  • Clearly, the result is 0.
  • So, given proposition is a contradiction, invalid, falsifiable and unsatisfiable.

 

Part-04:

 

Method-01: Using Truth Table-

 

Let ∼(p → q) ∨ (∼p ∨ (p ∧ q)) = R (say)

 

pq∼p
q∼(p  q)p ∧ q∼p ∨ (p ∧ q)
R
FFTTFFTT
FTTTFFTT
TFFFTFFT
TTFTFTTT

 

Clearly, last column of the truth table contains only T.

Therefore, given proposition is-

  • Tautology
  • Valid
  • Unfalsifiable
  • Satisfiable

 

Method-02: Using Algebra Of Proposition-

 

We have-

∼(p → q) ∨ (∼p ∨ (p ∧ q))

= ∼(∼p ∨ q) ∨ (∼p ∨ (p ∧ q))               { ∵ p → q = ∼p ∨ q }

= (p ∧ ∼q) ∨ (∼p ∨ (p ∧ q))                  { Using De Morgans law }

= (p ∧ ∼q) ∨ ((∼p ∨ p) ∧ (∼p ∨ q))       { Using Distributive law }

= (p ∧ ∼q) ∨ (T ∧ (∼p ∨ q))                  { Using Complement law }

= (p ∧ ∼q) ∨ (∼p ∨ q)                           { Using Identity law }

= ((p ∧ ∼q) ∨ ∼p) ∨ q                           { Using Associative law }

= ((p ∨ ∼p) ∧ (∼q ∨ ∼p)) ∨ q                { Using Distributive law }

= (T ∧ (∼q ∨ ∼p)) ∨ q                           { Using Complement law }

= (∼q ∨ ∼p) ∨ q                                    { Using Identity law }

= ∼p ∨ (q ∨ ∼q)

= ∼p ∨ T                                               { Using Complement law }

= T                                                        { Using Identity law }

 

  • Clearly, the result is T.
  • So, given proposition is a tautology, valid, unfalsifiable and satisfiable.

 

Method-03: Using Digital Electronics-

 

We have-

∼(p → q) ∨ (∼p ∨ (p ∧ q))

= ∼(∼p ∨ q) ∨ (∼p ∨ (p ∧ q))          { ∵ p → q = ∼p ∨ q }

 

Now in terms of digital electronics, we have-

= (p’ + q)’ + (p’ + p.q)

= (p’ + q)’ + (p’ + p).(p’ + q)            { Using Transposition theorem }

= (p’ + q)’ + 1.(p’ + q)

= (p’ + q)’ + (p’ + q)

= p.q’ + p’ + q                                 { Using De Morgans law }

= (p + p’)(p’ + q’) + q                      { Using Transposition theorem }

= 1.(p’ + q’) + q

= p’ + (q’ + q)

= p’ + 1

= 1

 

  • Clearly, the result is 1.
  • So, given proposition is a tautology, valid, unfalsifiable and satisfiable.

 

Part-05:

 

Method-01: Using Truth Table-

 

Let (p ↔ r) → (∼q → (p ∧ r)) = R (say)

 

pqr∼q
 r p rp ∧ r∼q (p ∧ r)R
FFFTTTTFFF
FFTTTFFFFT
FTFFTTTFTT
FTTFTFFFTT
TFFTFTFFFT
TFTTTTTTTT
TTFFFTFFTT
TTTFTTTTTT

 

Clearly, last column of the truth table contains both T and F.

Therefore, given proposition is-

  • Contingency
  • Invalid
  • Falsifiable
  • Satisfiable

 

Method-02: Using Algebra Of Proposition-

 

We have-

(p ↔ r) → (∼q → (p ∧ r))

= (p ↔ r) → (q ∨ (p ∧ r))                                             { ∵ p → q = ∼p ∨ q }

= ∼(p ↔ r) ∨ q ∨ (p ∧ r)

= ∼((p → r) ∧ (r → p)) ∨ q ∨ (p ∧ r)                             { ∵ p ↔ q = (p → q) ∧ q → p) }

= ∼((∼p ∨ r) ∧ (∼r ∨ p)) ∨ q ∨ (p ∧ r)                           { ∵ p → q = ∼p ∨ q }

= ∼[ ((∼p ∨ r) ∧ ∼r) ∨ ((∼p ∨ r) ∧ p) ] ∨ q ∨ (p ∧ r)       { Using Distributive law }

= ∼[ ((∼p ∧ ∼r) ∨ (r ∧ ∼r)) ∨ ((∼p ∧ p) ∨ (r ∧ p)) ] ∨ q ∨ (p ∧ r)   { Using Distributive law }

= ∼[ ((∼p ∧ ∼r) ∨ F) ∨ (F ∨ (r ∧ p)) ] ∨ q ∨ (p ∧ r)         { Using Complement law }

= ∼[ (∼p ∧ ∼r) ∨ (r ∧ p) ] ∨ q ∨ (p ∧ r)                           { Using Identity law }

= [∼(∼p ∧ ∼r) ∧ ∼(r ∧ p) ] ∨ q ∨ (p ∧ r)                         { Using De Morgans law }

= [ (p ∨ r) ∧ (∼r ∨ ∼p) ] ∨ q ∨ (p ∧ r)                             { Using De Morgans law }

= ((p ∨ r) ∧ ∼r) ∨ ((p ∨ r) ∧ ∼p) ∨ q ∨ (p ∧ r)                 { Using Distributive law }

= ((p ∧ ∼r) ∨ (r ∧ ∼r)) ∨ ((p ∧ ∼p) ∨ (r ∧ ∼p)) ∨ q ∨ (p ∧ r)   { Using Distributive law }

= ((p ∧ ∼r) ∨ F) ∨ (F ∨ (r ∧ ∼p)) ∨ q ∨ (p ∧ r)                 { Using Complement law }

= (p ∧ ∼r) ∨ (r ∧ ∼p) ∨ q ∨ (p ∧ r)                                   { Using Identity law }

= (p ∧ ∼r) ∨ q ∨ (∼p ∧ r) ∨ (p ∧ r)

= (p ∧ ∼r) ∨ q ∨ ((∼p ∨ p) ∧ r)                                         { Using Distributive law }

= (p ∧ ∼r) ∨ q ∨ (T ∧ r)                                                    { Using Complement law }

= (p ∧ ∼r) ∨ q ∨ r                                                             { Using Identity law }

=  r ∨ (p ∧ ∼r) ∨ q

= ((r ∨ p) ∧ (r ∨ ∼r)) ∨ q                                                   { Using Distributive law }

= ((r ∨ p) ∧ T) ∨ q                                                            { Using Complement law }

= p ∨ q ∨ r                                                                       { Using Identity law }

 

  • Clearly, the result is neither T nor F.
  • So, given proposition is a contingency, invalid, falsifiable and satisfiable.

 

Method-03: Using Digital Electronics-

 

We have-

(p ↔ r) → (∼q → (p ∧ r))

= (p ↔ r) → (q ∨ (p ∧ r))                      { ∵ p → q = ∼p ∨ q }

= ∼(p ↔ r) ∨ (q ∨ (p ∧ r))                     { ∵ p → q = ∼p ∨ q }

 

Now in terms of digital electronics, we have-

= (p.r + p’.r’)’ + (q + p.r)

= (p.r)’ . (p’.r’)’ + (q + p.r)                  (Using De Morgans Theorem)

= (p’ + r’) . (p + r) + (q + p.r)             (Using De Morgans Theorem)

= p’.p + p’.r + r’.p + r’.r + q + p.r

= 0 + p’.r + r’.p + 0 + q + p.r

= p’.r + r’.p + q + p.r

= (p’ + p).r + r’.p + q

= r + r’.p + q

= (r + r’).(r + p) + q                           (Using Transposition Theorem)

= p + q + r

 

  • Clearly, the result is neither 0 nor 1.
  • So, given proposition is a contingency, invalid, falsifiable and satisfiable.

 

To gain better understanding about Tautology, Contradiction and Contingency,

Watch this Video Lecture

 

Get more notes and other study material of Propositional Logic.

Converse Inverse Contrapositive | Problems

Logical Connectives-

 

Before you go through this article, make sure that you have gone through the previous article on Logical Connectives.

 

We have discussed-

  • Logical connectives are the operators used to combine one or more propositions.
  • In propositional logic. there are 5 basic connectives-

 

 

Also Read- Propositions

 

In this article, we will discuss Converse, Inverse and Contrapositive of a conditional statement.

 

Converse, Inverse and Contrapositive-

 

For a conditional statement p → q,

  • The converse statement is q → p
  • The inverse statement ∼p → ∼q
  • The contrapositive statement is ∼q → ∼p

 

 

Important Notes-

 

Note-01:

 

  • For conditional statements (p → q) only, the converse, inverse and contrapositive statements can be written.

 

Note-02:

 

Performing any two actions always result in the third one.

 

For example-

  • Inverse of converse is contrapositive.
  • Inverse of contrapositive is converse.
  • Converse of inverse is contrapositive.
  • Converse of contrapositive is inverse.
  • Contrapositive of inverse is converse.
  • Contrapositive of converse is inverse.

 

Note-03:

 

For a conditional statement p → q,

  • Its converse statement (q → p) and inverse statement (∼p → ∼q) are equivalent to each other.
  • p → q and its contrapositive statement (∼q → ∼p) are equivalent to each other.

 

Also Read- Converting English Sentences To Propositional Logic

 

PRACTICE PROBLEMS BASED ON CONVERSE, INVERSE AND CONTRAPOSITIVE-

 

Problem-01:

 

Write the converse, inverse and contrapositive of the following statements-

  1. If today is Sunday, then it is a holiday.
  2. If 5x – 1 = 9, then x = 2.
  3. If it rains, then I will stay at home.
  4. I will dance only if you sing.
  5. I will go if he stays.
  6. We leave whenever he comes.
  7. You will qualify GATE only if you work hard.
  8. If you are intelligent, then you will pass the exam.

 

Solution-

 

Part-01:

 

We have-

  • The given sentence is- “If today is Sunday, then it is a holiday.”
  • This sentence is of the form- “If p then q”.

 

So, the symbolic form is p → q where-

p : Today is Sunday

q : It is a holiday

 

Converse Statement- If it is a holiday, then today is Sunday.

Inverse Statement- If today is not Sunday, then it is not a holiday.

Contrapositive Statement- If it is not a holiday, then today is not Sunday.

 

Part-02:

 

We have-

  • The given sentence is- “If 5x – 1 = 9, then x = 2.”
  • This sentence is of the form- “If p then q”.

 

So, the symbolic form is p → q where-

p : 5x – 1 = 9

q : x = 2

 

Converse Statement- If x = 2, then 5x – 1 = 9.

Inverse Statement- If 5x – 1 ≠ 9, then x ≠ 2.

Contrapositive Statement- If x ≠ 2, then 5x – 1 ≠ 9.

 

Part-03:

 

We have-

  • The given sentence is- “If it rains, then I will stay at home.”
  • This sentence is of the form- “If p then q”.

 

So, the symbolic form is p → q where-

p : It rains

q : I will stay at home

 

Converse Statement- If I will stay at home, then it rains.

Inverse Statement- If it does not rain, then I will not stay at home.

Contrapositive Statement- If I will not stay at home, then it does not rain.

 

Part-04:

 

We have-

  • The given sentence is- “I will dance only if you sing.”
  • This sentence is of the form- “p only if q”.

 

So, the symbolic form is p → q where-

p : I will dance

q : You sing

 

Converse Statement- If you sing, then I will dance.

Inverse Statement- If I will not dance, then you do not sing.

Contrapositive Statement- If you do not sing, then I will not dance.

 

Part-05:

 

We have-

  • The given sentence is- “I will go if he stays.”
  • This sentence is of the form- “q if p”.

 

So, the symbolic form is p → q where-

p : He stays

q : I will go

 

Converse Statement- If I will go, then he stays.

Inverse Statement- If he does not stay, then I will not go.

Contrapositive Statement- If I will not go, then he does not stay.

 

Part-06:

 

We have-

  • The given sentence is- “We leave whenever he comes.”
  • We can replace “whenever” with “if”.
  • Then, the sentence is- “We leave if he comes.”
  • This sentence is of the form- “q if p”.

 

So, the symbolic form is p → q where-

p : He comes

q : We leave

 

Converse Statement- If we leave, then he comes.

Inverse Statement- If he does not come, then we do not leave.

Contrapositive Statement- If we do not leave, then he does not come.

 

Part-07:

 

We have-

  • The given sentence is- “You will qualify GATE only if you work hard.”
  • This sentence is of the form- “p only if q”.

 

So, the symbolic form is p → q where-

p : You will qualify GATE

q : You work hard

 

Converse Statement- If you work hard, then you will qualify GATE.

Inverse Statement- If you will not qualify GATE, then you do not work hard.

Contrapositive Statement- If you do not work hard, then you will not qualify GATE.

 

Part-08:

 

We have-

  • The given sentence is- “If you are intelligent, then you will pass the exam.”
  • This sentence is of the form- “If p then q”.

 

So, the symbolic form is p → q where-

p : You are intelligent

q : You will pass the exam

 

Converse Statement- If you will pass the exam, then you are intelligent.

Inverse Statement- If you are not intelligent, then you will not pass the exam.

Contrapositive Statement- If you will not pass the exam, then you are not intelligent.

 

Problem-02:

 

What is the converse of the statement- “I stay only if you go”?

  1. I stay if you go.
  2. If I stay, then you go.
  3. If you do not go, then I do not stay.
  4. If I do not stay, then you go.

 

Solution-

 

  • Try solving this problem yourself.
  • Solution is in the linked video lecture.
  • Option (A) is correct.

 

To gain better understanding about converting Converse, Inverse and Contrapositive,

Watch this Video Lecture

 

Next Article- Tautology, Contradiction and Contingency

 

Get more notes and other study material of Propositional Logic.

Logical Connectives | Propositional Logic

Logical Connectives-

 

Before you go through this article, make sure that you have gone through the previous article on Logical Connectives.

 

We have discussed-

  • Logical connectives are the operators used to combine one or more propositions.
  • In propositional logic. there are 5 basic connectives-

 

 

In this article, we will discuss-

  • Some important results, properties and formulas of conditional and biconditional.
  • Converting English sentences to propositional logic.

 

Conditional-

 

If p and q are two propositions, then-

Proposition of the type “If p then q” is called a conditional or implication proposition.

 

  • It is true when both p and q are true or when p is false.
  • It is false when p is true and q is false.

 

Also Read- Propositions

 

Truth Table-

 

pq q
FFT
FTT
TFF
TTT

 

Significance Of P→Q:

 

p → q may be interpreted as-

  • If p then q
  • p implies q
  • q follows from p
  • q if p
  • q whenever p
  • p only if q
  • p is sufficient for q
  • q is necessary for p
  • q without p is possible and can exist
  • p without q is impossible and can not exist

 

Formulas-

 

While solving questions, remember-

  • You can always replace p → q with ∼p ∨ q.
  • p → q is equivalent to ∼q → ∼p.

 

Proof-

 

The following table clearly shows that p → q and ∼p ∨ q are logically equivalent-

 

pq q∼p ∨ q
FFTT
FTTT
TFFF
TTTT

 

Also,

The following derivation shows that p → q and ∼q → ∼p are logically equivalent-

∼q → ∼p

= ∼(∼q) ∨ ∼p

= q ∨ ∼p

= ∼p ∨ q

 

Biconditional-

 

If p and q are two propositions, then-

Proposition of the type “p if and only if q” is called a biconditional or bi-implication proposition.

 

  • It is true when either both p and q are true or both p and q are false.
  • It is false in all other cases.

 

Truth Table-

 

pq q
FFT
FTF
TFF
TTT

 

Significance Of P↔Q:

 

p ↔ q may be interpreted as-

  • (If p then q) and (If q then p)
  • p if and only if q
  • q if and only if p
  • (p if q) and (q if p)
  • p is necessary and sufficient for q
  • q is necessary and sufficient for p
  • p and q are necessary and sufficient for each other
  • p and q can not exist without each other
  • Either p and q both exist or none of them exist
  • p and q are equivalent
  • ∼p and ∼q are equivalent

 

Formulas-

 

While solving questions, remember-

  • Biconditional is equivalent to EX-NOR Gate.
  • You can always replace p ↔ q with (p ∧ q) ∨ (∼p ∧ ∼q).

 

Proof-

 

The following table clearly shows that p ↔ q and (p ∧ q) ∨ (∼p ∧ ∼q) are logically equivalent-

 

pq q(p ∧ q) ∨ (∼p ∧ ∼q)
FFTT
FTFF
TFFF
TTTT

 

Converting English Sentences To Propositional Logic-

 

While solving questions, the following replacements are very useful-

 

WordReplacement
AndConjunction (∧)
OrDisjunction (∨)
ButAnd
WheneverIf
WhenIf
Either p or qp or q
Neither p nor qNot p and Not q
p unless q∼q → p
p is necessary but not sufficient for q(q → p) and ∼(p → q)

 

To understand better, let us try solving the following problems.

 

PRACTICE PROBLEMS BASED ON CONVERTING ENGLISH SENTENCES-

 

Problem-01:

 

Write the following English sentences in symbolic form-

  1. If it rains, then I will stay at home.
  2. If I will go to Australia, then I will earn more money.
  3. He is poor but honest.
  4. If a = b and b = c then a = c.
  5. Neither it is hot nor cold today.
  6. He goes to play a match if and only if it does not rain.
  7. Birds fly if and only if sky is clear.
  8. I will go only if he stays.
  9. I will go if he stays.
  10. It is false that he is poor but not honest.
  11. It is false that he is poor or clever but not honest.
  12. It is hot or else it is both cold and cloudy.
  13. I will not go to class unless you come.
  14. We will leave whenever he comes.
  15. Either today is Sunday or Monday.
  16. You will qualify GATE only if you work hard.
  17. Presence of cycle in a single instance RAG is a necessary and sufficient condition for deadlock.
  18. Presence of cycle in a multi instance RAG is a necessary but not sufficient condition for deadlock.
  19. I will dance only if you sing.
  20. Neither the red nor the green is available in size 5.

 

Solution-

 

Part-01:

 

We have-

  • The given sentence is- “If it rains, then I will stay at home.”
  • This sentence is of the form- “If p then q”.

 

So, the symbolic form is p → q where-

p : It rains

q : I will stay at home

 

Part-02:

 

We have-

  • The given sentence is- “If I will go to Australia, then I will earn more money.”
  • This sentence is of the form- “If p then q”.

 

So, the symbolic form is p → q where-

p : I will go to Australia

q : I will earn more money

 

Part-03:

 

We have-

  • The given sentence is- “He is poor but honest.”
  • We can replace “but” with “and”.
  • Then, the sentence is- “He is poor and honest.”

 

So, the symbolic form is p ∧ q where-

p : He is poor

q : He is honest

 

Part-04:

 

We have-

  • The given sentence is- “If a = b and b = c then a = c.”
  • This sentence is of the form- “If p then q”.

 

So, the symbolic form is (p ∧ q) → r where-

p : a = b

q : b = c

r : a = c

 

Part-05:

 

We have-

  • The given sentence is- “Neither it is hot nor cold today.”
  • This sentence is of the form- “Neither p nor q”.
  • “Neither p nor q” can be re-written as “Not p and Not q”.

 

So, the symbolic form is ∼p ∧ ∼q where-

p : It is hot today

q : It is cold today

 

Part-06:

 

We have-

  • The given sentence is- “He goes to play a match if and only if it does not rain.”
  • This sentence is of the form- “p if and only if q”.

 

So, the symbolic form is p ↔ q where-

p : He goes to play a match

q : It does not rain

 

Part-07:

 

We have-

  • The given sentence is- “Birds fly if and only if sky is clear.”
  • This sentence is of the form- “p if and only if q”.

 

So, the symbolic form is p ↔ q where-

p : Birds fly

q : Sky is clear

 

Part-08:

 

We have-

  • The given sentence is- “I will go only if he stays.”
  • This sentence is of the form- “p only if q”.

 

So, the symbolic form is p → q where-

p : I will go

q : He stays

 

Part-09:

 

We have-

  • The given sentence is- “I will go if he stays.”
  • This sentence is of the form- “q if p”.

 

So, the symbolic form is p → q where-

p : He stays

q : I will go

 

Part-10:

 

We have-

  • The given sentence is- “It is false that he is poor but not honest.”
  • We can replace “but” with “and”.
  • Then, the sentence is- “It is false that he is poor and not honest.”

 

So, the symbolic form is ∼(p ∧ ∼q) where-

p : He is poor

q : He is honest

 

Part-11:

 

We have-

  • The given sentence is- “It is false that he is poor or clever but not honest.”
  • We can replace “but” with “and”.
  • Then, the sentence is- “It is false that he is poor or clever and not honest.”

 

So, the symbolic form is ∼((p ∨ q) ∧ ∼r) where-

p : He is poor

q : He is clever

r : He is honest

 

Part-12:

 

We have-

  • The given sentence is- “It is hot or else it is both cold and cloudy.”
  • It can be re-written as- “It is hot or it is both cold and cloudy.”

 

So, the symbolic form is ∨ (q ∧ r) where-

p : It is hot

q : It is cold

r : It is cloudy

 

Part-13:

 

We have-

  • The given sentence is- “I will not go to class unless you come.”
  • This sentence is of the form- “p unless q”.

 

So, the symbolic form is ∼ q → p where-

p : I will go to class

q : You come

 

Part-14:

 

We have-

  • The given sentence is- “We will leave whenever he comes.”
  • We can replace “whenever” with “if”.
  • Then, the sentence is- “We will leave if he comes.”
  • This sentence is of the form- “q if p”.

 

So, the symbolic form is p → q where-

p : He comes

q : We will leave

 

Part-15:

 

We have-

  • The given sentence is- “Either today is Sunday or Monday.”
  • It can be re-written as- “Today is Sunday or Monday.”

 

So, the symbolic form is p ∨ q where-

p : Today is Sunday

q : Today is Monday

 

Part-16:

 

We have-

  • The given sentence is- “You will qualify GATE only if you work hard.”
  • This sentence is of the form- “p only if q”.

 

So, the symbolic form is p → q where-

p : You will qualify GATE

q : You work hard

 

Part-17:

 

We have-

  • The given sentence is- “Presence of cycle in a single instance RAG is a necessary and sufficient condition for deadlock.”
  • This sentence is of the form- “p is necessary and sufficient for q”.

 

So, the symbolic form is p ↔ q where-

p : Presence of cycle in a single instance RAG

q : Presence of deadlock

 

Part-18:

 

We have-

  • The given sentence is- “Presence of cycle in a multi instance RAG is a necessary but not sufficient condition for deadlock.”
  • This sentence is of the form- “p is necessary but not sufficient for q”.

 

So, the symbolic form is (q → p) ∧ ∼(p → q) where-

p : Presence of cycle in a multi instance RAG

q : Presence of deadlock

 

Part-19:

 

We have-

  • The given sentence is- “I will dance only if you sing.”
  • This sentence is of the form- “p only if q”.

 

So, the symbolic form is p → q where-

p : I will dance

q : You sing

 

Part-20:

 

We have-

  • The given sentence is- “Neither the red nor the green is available in size 5.”
  • This sentence is of the form- “Neither p nor q”.
  • “Neither p nor q” can be written as “Not p and Not q”.

 

So, the symbolic form is ∼p ∧ ∼q where-

p : Red is available in size 5

q : Green is available in size 5

 

Problem-02:

 

Consider the following two statements-

S1 : Ticket is sufficient to enter movie theater.

S2 : Ticket is necessary to enter movie theater.

 

Which of the statements is/ are logically correct?

  1. S1 is correct and S2 is incorrect.
  2. S1 is incorrect and S2 is correct.
  3. Both are correct.
  4. Both are incorrect.

 

Solution-

 

Statement S1 : Ticket is Sufficient To Enter Movie Theater-

 

This statement is of the form- “p is sufficient for q” where-

p : You have a ticket

q : You can enter a movie theater

So, the symbolic form is p → q

 

For p → q to hold, its truth table must hold-

 

p

(Ticket)

q

(Entry)

 q

(Ticket is sufficient for entry)

FFT
FTT
TFF
TTT

 

Here,

  • Row-2 states it is possible that you do not have a ticket and you can enter the theater.
  • However, it is not possible to enter a movie theater without ticket.
  • Row-3 states it is not possible that you have a ticket and you do not enter the theater.
  • However, there might be a case possible when you have a ticket but do not enter the theater.
  • So, the truth table does not hold.

 

Thus, the statement- “Ticket is sufficient for entry” is logically incorrect.

 

Statement S2 : Ticket is Necessary To Enter Movie Theater-

 

This statement is of the form- “q is necessary for p” where-

p : You can enter a movie theater

q : You have a ticket

So, the symbolic form is p → q

 

For p → q to hold, its truth table must hold-

 

p

(Entry)

q

(Ticket)

 q

(Ticket is necessary for entry)

FFT
FTT
TFF
TTT

 

Here, All the rows of the truth table make the correct sense.

Thus, the statement- “Ticket is necessary for entry” is logically correct.

 

Thus, Option (B) is correct.

 

To gain better understanding about converting English sentences,

Watch this Video Lecture

 

Next Article- Converse, Inverse and Contrapositive

 

Get more notes and other study material of Propositional Logic.

Logical Connectives | Truth Tables | Examples

Propositions-

 

Before you go through this article, make sure that you have gone through the previous article on Propositions.

 

We have discussed-

  • Proposition is a declarative statement that is either true or false but not both.
  • Connectives are used to combine the propositions.

 

 

In this article, we will discuss about connectives in propositional logic.

 

Logical Connectives-

 

Connectives are the operators that are used to combine one or more propositions.

 

In propositional logic, there are 5 basic connectives-

 

Name of ConnectiveConnective WordSymbol
NegationNot or or or
ConjunctionAnd
DisjunctionOr
ConditionalIf-then
BiconditionalIf and only if

 

1. Negation-

 

If p is a proposition, then negation of p is a proposition which is-

  • True when p is false
  • False when p is true.

 

Truth Table-

 

p∼p
FT
TF

 

Example-

 

If p : It is raining outside.

Then, Negation of p is-

∼p : It is not raining outside.

 

2. Conjunction-

 

If p and q are two propositions, then conjunction of p and q is a proposition which is-

  • True when both p and q are true
  • False when both p and q are false

 

Truth Table-

 

pqp ∧ q
FFF
FTF
TFF
TTT

 

Example-

 

If p and q are two propositions where-

  • p : 2 + 4 = 6
  • q : It is raining outside.

 

Then, conjunction of p and q is-

p ∧ q : 2 + 4 = 6 and it is raining outside

 

3. Disjunction-

 

If p and q are two propositions, then disjunction of p and q is a proposition which is-

  • True when either one of p or q or both are true
  • False when both p and q are false

 

Truth Table-

 

pqp ∨ q
FFF
FTT
TFT
TTT

 

Example-

 

If p and q are two propositions where-

  • p : 2 + 4 = 6
  • q : It is raining outside

 

Then, disjunction of p and q is-

p ∨ q : 2 + 4 = 6 or it is raining outside

 

4. Conditional-

 

If p and q are two propositions, then-

  • Proposition of the type “If p then q” is called a conditional or implication proposition.
  • It is true when both p and q are true or when p is false.
  • It is false when p is true and q is false.

 

Truth Table-

 

pq q
FFT
FTT
TFF
TTT

 

Examples-

 

  • If a = b and b = c then a = c.
  • If I will go to Australia, then I will earn more money.

 

5. Biconditional-

 

If p and q are two propositions, then-

  • Proposition of the type “p if and only if q” is called a biconditional or bi-implication proposition.
  • It is true when either both p and q are true or both p and q are false.
  • It is false in all other cases.

 

Truth Table-

 

pq q
FFT
FTF
TFF
TTT

 

Examples-

 

  • He goes to play a match if and only if it does not rain.
  • Birds fly if and only if sky is clear.

 

Important Notes-

 

Note-01:

 

  • Negation ≡ NOT Gate of digital electronics.
  • Conjunction ≡ AND Gate of digital electronics.
  • Disjunction ≡ OR Gate of digital electronics.
  • Biconditional = EX-NOR Gate of digital electronics.

 

Note-02:

 

  • Each logical connective has some priority.
  • This priority order is important while solving questions.
  • The decreasing order of priority is-

 

 

Note-03:

 

  • Negation, Conjunction, Disjunction and Biconditional are both commutative and associative.
  • Conditional is neither commutative nor associative.

 

To gain better understanding about Logical Connectives,

Watch this Video Lecture

 

Next Article- Converting English Sentences To Propositional Logic

 

Get more notes and other study material of Propositional Logic.

Propositional Logic | Propositions Examples

Propositions-

 

In propositional logic,

  • Proposition is a declarative statement declaring some fact.
  • It is either true or false but not both.

 

Propositions Examples-

 

The examples of propositions are-

  • 7 + 4 = 10
  • Apples are black.
  • Narendra Modi is president of India.
  • Two and two makes 5.
  • 2016 will be the lead year.
  • Delhi is in India.

 

Here,

  • All these statements are propositions.
  • This is because they are either true or false but not both.

 

Types Of Propositions-

 

In propositional logic, there are two types of propositions-

 

 

  1. Atomic propositions
  2. Compound propositions

 

1. Atomic Propositions-

 

  • Atomic propositions are those propositions that can not be divided further.
  • Small letters like p, q, r, s etc are used to represent atomic propositions.

 

Examples-

 

The examples of atomic propositions are-

  • p : Sun rises in the east.
  • q : Sun sets in the west.
  • r : Apples are red.
  • s : Grapes are green.

 

2. Compound Propositions-

 

  • Compound propositions are those propositions that are formed by combining one or more atomic propositions using connectives.
  • In other words, compound propositions are those propositions that contain some connective.
  • Capital letters like P, Q, R, S etc are used to represent compound propositions.

 

Examples-

 

  • P : Sun rises in the east and Sun sets in the west.
  • Q : Apples are red and Grapes are green.

 

Statements That Are Not Propositions-

 

Following kinds of statements are not propositions-

  1. Command
  2. Question
  3. Exclamation
  4. Inconsistent
  5. Predicate or Proposition Function

 

Examples-

 

Following statements are not propositions-

  • Close the door.                   (Command)
  • Do you speak French?       (Question)
  • What a beautiful picture!    (Exclamation)
  • I always tell lie.                   (Inconsistent)
  • P(x) : x + 3 = 5                    (Predicate)

 

PRACTICE PROBLEMS BASED ON PROPOSITIONS-

 

Identify which of the following statements are propositions-

  1. France is a country.
  2. 2020 will be a leap year.
  3. Sun rises in the west.
  4. P(x) : x + 6 = 7
  5. P(5) : 5 + 6 = 2
  6. Apples are oranges.
  7. Grapes are black.
  8. Two and two makes 4.
  9. x > 10
  10. Open the door.
  11. Are you tired?
  12. What a bright sunny day!
  13. Mumbai is in India.
  14. I always tell truth.
  15. I always tell lie.
  16. Do not go there.
  17. This sentence is true.
  18. This sentence is false.
  19. It will rain tomorrow.
  20. Fan is rotating.

 

Solutions-

 

  1. Proposition (True)
  2. Proposition (True)
  3. Proposition (False)
  4. Not a proposition (Predicate)
  5. Proposition (False)
  6. Proposition (False)
  7. Proposition (False)
  8. Proposition (True)
  9. Not a proposition (Predicate)
  10. Not a proposition (Command)
  11. Not a proposition (Question)
  12. Not a proposition (Exclamation)
  13. Proposition (True)
  14. Proposition (True)
  15. Not a proposition (Inconsistent)
  16. Not a proposition (Command)
  17. Proposition (True)
  18. Not a proposition (Inconsistent)
  19. Proposition (Will be confirmed tomorrow whether true or false)
  20. Proposition (True if fan is rotating otherwise false)

 

To gain better understanding about Propositions,

Watch this Video Lecture

 

Next Article- Logical Connectives

 

Get more notes and other study material of Propositional Logic.