Propositional Logic

Propositional Logic :

The propositional logic represents logic through propositions and logical connectives.

Proposition :

A Proposition is an elementary atomic sentence that can have either true or false as its value.

They are also known as sentences or statements.

example:    Wind is blowing.       ( It is a proposition as it may be either true or false )
                      It is raining.                 ( It is a proposition as it may be either true or false )

                      How are you?              ( It is NOT a proposition as it can not be true or false )    

Simple Proposition:

It is a single sentence that does not have any part with it. 

example:

                    It is raining.

                    Wind is blowing.

Compound Proposition:

These are formed by two or more propositions joined with operators known as Connectives ( AND , OR, ⇒& ⇔).

example:

                    It is raining and wind is blowing.

                    If you work hard then you will succeed.

Sentential Connectives:

They are the operators which join sentences or propositions to form compound propositions.

Following are the Sentential Connectives :

1) Disjunction (known as OR):    It is represented by symbol "+" or "∨".

    It means either one of the two arguments is true or both of them are true, it will be true.

    example:

               P + Q ( or P∨Q), means P OR Q :    It is true if either P is true, or Q is true, or both are true.

                        

P	Q	P∨Q
false	false	false
false	true	true
true	false	true
true	true	true

2) Conjunction (known as AND):    It is represented by symbol "." or "∧".

    It means if both arguments are true, it will be true.    

    example:

                P.Q ( or P∧Q), means P AND Q :    It is true if both P and Q are true.

P	Q	P∧Q
false	false	false
false	true	false
true	false	false
true	true	true

3) Conditional (known as If.. Then): It is also known as Implication. It is represented by symbol "⇒".

     It means if one argument is true then other must be true to get true, Rest cases are true.

     example:

               P ⇒Q ( or if P then Q ) :    It means if P is true then Q must be true.

P	Q	P⇒Q
false	false	true
false	true	true
true	false	false
true	true	true

4) Bi-conditional (known as If and only If): It is also known as Equivalence. It is represented by

     symbol "⇔". It means either both arguments are true or both are false it will result in true.

    example:

               P ⇔Q ( or P ≡Q ) :    It is true if both P and Q are either true or false.

P	Q	P⇔Q
false	false	true
false	true	false
true	false	false
true	true	true

*** Negation (known as NOT): It is not a connective but only an operator. It is represented by

     symbols "¬, ˜, ', -". It does not join statements but actually works on a single proposition.

     It changes the state of any proposition from true to false & vice versa.

    example:

               ˜P ( or  NOT P ) :    It is true if P is false.

P	˜P
false	true
true	false

WFF ( Well Formed Formulae ):

Propositions are also referred by the name Well Formed Formulae (WFF).

Truth Value:

Truth Value of a statement is its truth or falsity. All simple and compound statements (Propositions) have truth values, whether asserted or negated.

example:

                P is either true or false.

               ˜P is either true or false.

                P+Q  is either true or false.

                P.Q  is either true or false.

*** Inverse, Converse & Contrapositive ***

    Conditional statement IF... Then (P ⇒Q) has two parts

        a)  P (antecedent ) known as "Hypothesis"

        b) Q (consequent ) known as "Conclusion"

    Inverse: Inverse of a conditional statement is done by Negating both its hypothesis & conclusion. If

            the statement is "If P, then Q", its inverse is "If Not P, then Not Q".

            Inverse of   P⇒Q  is ˜P⇒˜Q

    Converse: Converse of a conditional statement is done by interchanging both hypothesis & 

            conclusion. If statement is "If P, then Q", its converse is "If Q, then P".

            Converse  of   P⇒Q  is   Q⇒P

    Contra-positive: Contra-positive of a conditional statement is done by interchanging the Negation

            of both hypothesis & conclusion. If statement is "If P, then Q", its contra-positive is "If Not Q,                then Not P".

            Contra-positive of   P⇒Q   is    ˜Q⇒˜P

Argument:    An argument contains two declarative sentences (Propositions) known as premises, along with a declarative sentence (Proposition) known as conclusion.

Premise:    A premise is a statement (Proposition) in an argument which provides reason for conclusion.

Conclusion:    A conclusion is a statement (Proposition) in an argument which provides logical result of relationship between premises.

Syllogism:    It is a form of logical argument that applies deductive reasoning to draw a conclusion based on two premises (Propositions) which are assumed to be true.

example:

                All humans will die.    (Premise 1)

                Raju is a human.          (Premise 2)

        therefore,

                Raju will die.               (Conclusion)

**************************************************************************

Some Questions on Propositional Logic

Question 1) Prove that (x ⇒ y) ∧ (y ⇒ x) = x⇔y

Solution (Algebra Method):    

                        L.H.S.   = (x ⇒ y) ∧ (y ⇒ x)

                                    = (x'+y).(y'+x)                (replacing with boolean expression)

                                    = x'.y'+x'.x+y.y'+y.x 

                                    = x'.y'+0+0+y.x                (complementarity law)

                                    = x'.y'+y.x                            ( property of 0)

                        R.H.S.  = x⇔y

                                    = x'.y'+y.x                            (replacing with boolean expression)

        here, we can see that L.H.S. = R.H.S.

        hence proved.

Solution (Truth Table): 

   

x	y	x ⇒ y	y ⇒ x	(x ⇒ y) ∧ ( y ⇒ x)	x ⇔ y
0	0	1	1	1	1
0	1	1	0	0	0
1	0	0	1	0	0
1	1	1	1	1	1

        from above truth table we can easily see that (x ⇒ y) ∧ (y ⇒ x) = x⇔y.

        hence proved.

Question 2) Find the converse, inverse & contra-positive of P ⇒ Q, if,

                       P:    It is raining.

                       Q:   It is cloudy.

Solution:

                           Inverse ( ˜P⇒˜Q )                  :    If it is not raining then it is not cloudy.

                    Converse ( Q⇒P )                     :    If it is cloudy then it is raining.

                    Contra-positive ( ˜Q⇒˜P )    :    If it is not cloudy then it is not raining.