Discrete Mathematics UNIT-1 NOTES

                                                        Propositional Logic:

Propositional calculus is a branch of logic. It is also called propositional logic, statement logic, sentential calculus, and sentential logic.

There is a need to develop a formal language to state the Rules and Theory.

- A formal language is one in which the syntax is well defined.

- This formal language is called an object language. 

An object language consists of declarative sentences. These can have two truth values 'T' or 'F', denoting whether the statement is True or False.

Declarative Statement: A statement is said to be declarative if has a truth value, i.e. T or F.

Proposition: A proposition is a declarative statement that is either True or False, but not both.

 

Atomic Statement: A statement is said to be atomic if it cannot be divided into smaller statements. Otherwise, it is called molecular.

Propositional consists of propositional variables and connectives. We denote the propositional variables by alphabets (A, B, p, q, etc). Connectives connect two or more propositional variables.

Some examples of Propositions are given below :

• "2 is less than 3" It has the truth value T or 1.
• "January has 30 days" It has the truth value F or 0.

The statement 'A is less than 2' is not a proposition as the truth value can't be decided without specifying the value of A.

Compound Propositions: Combining multiple propositions yield statements known as compound propositions. Connectives are used to combine propositions.

Connectives:

Five common connectives in propositional logic are:

•      OR, denoted by the symbol (∨)
•      AND, denoted by the symbol (∧)
•      NOT, denoted by the symbol (¬)
•      Implication, denoted by the symbol (→)
•      XOR This is represented with Symbol (⊕).

OR (∨) − The OR operation of two propositions A and B (A ∨ B) has the truth value 1 if at least one of the propositional variables A or B is True.

The truth table is as follows:

A	B	A ∨ B
True	True	True
True	False	True

False	True	True
False	False	False

AND: The AND operation of two propositions A and B has the truth value 1 only if both the propositional variables A and B are true.

The truth table is as follows −

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

Negation (¬): The negation of a proposition A (written as ¬A) is False when A is true and true when A is false.

The truth table is as follows −

A	¬ A
True	False
False	True

Conditional Statement: Implication A → B is the compound proposition “If A then B”. It is false only when A is True and B is False. This is known as a conditional statement.  (→)

The truth table is as follows,

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

Bi-Conditional Statement: "If and only if", denoted by the symbol ⇔, is a bi-conditional logical connective. It is true when A and B have the same truth values, i.e. when either both are false or both are true. 

The truth table is as follows −

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

Truth tables:

(a)  While constructing a truth table, one has to consider all possible assignments of True (T) and False (F) to the component statements.

(b)  Let p and q be propositions. Each of them can be either true or false, so there are 2² = 4 possibilities.

If there are three component statements, then there are 2³ = 8 possibilities.

While listing the possibilities, one should assign truth values to the component statements in a systematic way, to avoid duplication or omission. The easiest approach is to use the lexicographic ordering. 

Example: Construct a truth table for the formula  ¬ P  ∧  (P → Q)

As the first step,  list all the alternatives for P and Q.They are {(T, T), (T, F), (F, T), (F, F)}.

Substitute the truth values of each proposition in the compound proposition to determine its truth value.

List the values for P→Q. Make sure that it is F only if P is T and Q is F.

List the values for compound expression ¬ P ∧  (P → Q). 

Tabulate the truth values of P, Q, ¬ P,  (P → Q) and ¬ P ∧  (P → Q)

Problems:

1. Define Tautology with an example.

2. Obtain Conjunctive Normal Form (CNF) of the expression:  [Q ∨ (P ∧ R)] ∧ ¬ ((P ∨ R) ∧ Q)
3.  Let the truth values of p, q, and r be 0,1 and 1 respectively. Find the truth values of the following:
           i) (p ∨ q) ∨ r      ii) (p ∧ q) ∧ r     iii) (p ∧ q) → r
          iv) p ∨ (q ∧ r)     v) p ∧ (r → q)    vi) p → (q → ¬ r)

4. Identify the Principal Disjunctive Normal Form (PDNF) of the expression: P → {(P → Q) ∧ ¬ (¬Q ∨ ¬P)}

                       
5. Construct the truth table of the compound proposition (p ∨ q) ∧ [¬q ∧ (r ∨ ¬q)] ∨ ¬(q ∨ p).
6. Determine the Principal Disjunctive Normal Form (PDNF) of the compound proposition:
              P → {(P → Q) ∧ ¬(¬Q ∨ ¬P)} 
7. Construct the truth table of the following compound expression:
            (¬P ∧ (¬Q ∧ R)) ∨ (Q ∧ R) ∨ (P ∧ R) ∨ R
8. Construct the truth table for the following expression:
             (P ∧ Q) ∨ (¬P ∨ Q) ∨ (P ∨ ¬Q) ∨ (¬P ∨ ¬Q)  
9. Obtain Conjunctive Normal Form (CNF) of the formula
             [Q ∨ (P ∧ R)] ∧ ¬ ((P ∨ R) ∧ Q)