Discrete Mathematics Propositional Logic - Discrete Mathematics

What is Propositional Logic in Discrete Mathematics?

Theoretical base for many areas of mathematics and computer science is provided by logical reasoning. Some of the areas such as artificial intelligence, programming languages etc.

By propositional logic, the statements are analyzed and the truth vales are assigned. The analysis is done either for individual statement or as a composite of statements.

Prepositional Logic – Definition

The declarative statement, which has either of the truth values, is termed as a proposition. Capital letters are used for representing propositional variables, and the variables are linked by a connective.

Some illustrations for propositions are:

  • "Apple is a fruit", for this, the truth value “TRUE” is returned.
  • "9+8+3=3 – 2", for this, the truth value “FALSE” is returned.

What are Connectives in Propositional Logic?

Propositional logic provides five different types of connectives -

  • OR (∨)
  • AND (∧)
  • Negation/ NOT (¬)
  • Implication / if-then (→)
  • If and only if (⇔).

OR (∨)

If any one of the variables, A or B is true, then the OR operation is true. The OR operation is represented as A∨B. The following is the truth table for OR operation -

A
B
A B
True
True
True
True
False
True
False
True
True
False
False
False

AND (∧)

If both the variables, A and B is true, then the AND operation is true. The AND operation is represented as A∧B. The following is the truth table for AND operation -

A
B
A B
True
True
True
True
False
False
False
True
False
False
False
False

Negation (¬)

For a true variable A, the negation is false. The Negation operation is represented as ¬A. The following is the truth table for this operation -

A
¬ A
True
False
False
True

Implication / if-then (→)

It is a conditional statement and If the variable A is true and the variable B is False, then this conditional statement would be false. The following is the truth table for this operation -

A
B
A B
True
True
True
True
False
False
False
True
True
False
False
True

If and only if (⇔)

If both variables A and B are same, that is either True or False, then the result is True. If both the Variables are not same, then the result is false. The following is the truth table for this operation -

A
B
A B
True
True
True
True
False
False
False
True
False
False
False
True

What are Tautologies?

For all the values of the propositional variables, tautology is always true.

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

The following is the truth table −

A
B
A B
(A B) A
[( A B ) A] B
True
True
True
True
True
True
False
False
False
True
False
True
True
False
True
False
False
True
False
True

It is observed that it is a tautology for every value is True.

What are Contradictions?

For all the values of the propositional variables, contradiction is always false.

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

The following is the truth table −

A
B
A B
¬ A
¬ B
(¬ A) ( ¬ B)
(A B) [( ¬ A) (¬ B)]
True
True
True
False
False
False
False
True
False
True
False
True
False
False
False
True
True
True
False
False
False
False
False
False
True
True
True
False

It is observed that it is a contradiction for every value is False.

What is a Contingency?

For each of the value of the propositional variables, contingency is either true or false.

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

The following is the truth table −

A
B
A B
¬ A
(A B) (¬ A)
True
True
True
False
False
True
False
True
False
False
False
True
True
True
True
False
False
False
True
False

It is observed that it is a contingency is either true or False.

What are Propositional Equivalences?

Two statements are said to be equivalent logically if they satisfy the following conditions -

  • •The truth values for each of the statement are same.
  • •The bi-conditional statement X⇔Y is a tautology.

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

According to Matching truth table method –

A
B
A B
¬ (A B)
¬ A
¬ B
[(¬ A) (¬ B)]
True
True
True
False
False
False
False
True
False
True
False
False
True
False
False
True
True
False
True
False
False
False
False
False
True
True
True
True

The statements are said to be equivalent as it is observed that the truth values of both the statements ¬(A∨B)and[(¬A)∧(¬B)] are true.

According to Bi-Conditional Method -

A
B
¬ (A B )
[(¬ A) (¬ B)]
[¬ (A B)] [(¬ A ) (¬ B)]
True
True
False
False
True
True
False
False
False
True
False
True
False
False
True
False
False
True
True
True

The statements are said to be equivalent as it is observed that [¬(A∨B)]⇔[(¬A)∧(¬B)] is a tautology.

Inverse, Converse, and Contra-positive

The conditional statement has two parts -

  • Hypothesis, p
  • Conclusion, q

It is denoted as p→q.

Example of Conditional Statement − “If you eat health food, you will not be sick.” For this statement, hypothesis is – eat health food and conclusion is – will not be sick.

Inverse

The negation of both hypothesis and conclusion is known as Inverse of the conditional statement.

Example – The inverse for the above discussed example is “If you do not eat health food, you will be sick.”

Converse

The interchange of hypothesis and conclusion is known as Converse of the conditional statement.

Example – The converse for the example is “You will not be sick if you eat health food”.

Contra-positive

The interchange of hypothesis and conclusion of inverse statement is Contra-positive.

Example − The Contra-positive for the example is “You will be sich if you do not eat health food”.

What is Duality Principle?

According to Duality principle, if the statement and true and if unions are interchanged into intersections and if universal set is interchanged into the Null set, the result of the interchange in both the cases is true.

Example − The dual of (A∩B)∪C is (A∪B)∩C

What are Normal Forms?

The propositions can be converted into any of the norm forms, which are of two types -

  • Conjunctive normal form
  • Disjunctive normal form

Conjunctive Normal Form

When AND operation is executed on the variables connected with OR operation, the compound statement formulated is said to be in conjunctive normal form.

Examples

  • (A∨B)∧(A∨C)∧(B∨C∨D)
  • (P∪Q)∩(Q∪R)

Disjunctive Normal Form

When OR operation is executed on the variables connected with AND operation, the compound statement formulated is said to be in disjunctive normal form.

Examples

  • (A∧B)∨(A∧C)∨(B∧C∧D)
  • (P∩Q)∪(Q∩R)

All rights reserved © 2018 Wisdom IT Services India Pvt. Ltd DMCA.com Protection Status

Discrete Mathematics Topics