PRESENTATION 1

http://www.scribd.com/doc/127717948/Math-Discrete

PREDICATES AND QUANTIFIERS

• Predicate- true,false (proposition that contain variable)

        P(x)= X>0

• Quantification express the extent to which a predicate is true over a 

         range of elements

         x>0

         x= true

         x=false

• Universal Quantifiers

        P(x) is true for every x in the universe of 
        discourse.

        "xP(x)

        

        Eg:U={1,2,3}

        "xP(x) óP(1) Ù P(2) Ù P(3)

• Existensial Quantifiers

        P(x) is true for some x in the universe of 
        discourse

        $xP(x)

       

        ‘There is an x such that P(x),’For some x,
         P(x)’,’For at least one x,

   

        P(x)’,’I can find an x such that P(x)’.

       

       Eg: U={1,2,3}

       $xP(x)óP(1) Ú P(2) Ú P(3)

• Unique Existensial

        P(x) is true for one and only are x in the 
        universe of discourse

       $!xP(x)

        

       ‘There is a unique x such that P(x),’
        There is one and only one x such

        that P(x)’,’One can find only 
        one x such that P(x).’

        

        Eg:U={1,2,3}

        

        Truth Table:

        P(1)   P(2)   P(3)   $!xP(x)

0       0       0       0

0       0       1       1

0       1       0       1

0       1       1       0

1       0       0       1

1       0       1       0

1       1       0       0

1       1       1       0




EXAMPLE OF APPLICATION IN LIFE:

UNIVERSAL

EXISTENSIAL

UNIQUE

PROPOSITIONAL LOGIC

• Definition: A proposition is a declarative sentences that is either true or false.

• Example: X + 2 = 5

• Truth Table:

 NEGATION 

P	¬ P
TRUE	FALSE
FALSE	TRUE

CONJUNCTION

P	Q	P ˆ Q
TRUE	TRUE	TRUE
TRUE	FALSE	FALSE
FALSE	TRUE	FALSE
FALSE	FALSE	FALSE

DISJUNCTION

P	Q	P  ˇ  Q
TRUE	TRUE	TRUE
TRUE	FALSE	TRUE
FALSE	TRUE	TRUE
FALSE	FALSE	FALSE

EXCLUSIVE DISJUNCTION

P	Q	P     Q
TRUE	TRUE	FALSE
TRUE	FALSE	TRUE
FALSE	TRUE	TRUE
FALSE	FALSE	FALSE

IMPLICATION

P	Q	P            Q
TRUE	TRUE	TRUE
TRUE	FALSE	FALSE
FALSE	TRUE	TRUE
FALSE	FALSE	TRUE

BI-IMPLICATION

P	Q	P              Q
TRUE	TRUE	TRUE
TRUE	FALSE	FALSE
FALSE	TRUE	FALSE
FALSE	FALSE	TRUE

PROPOSITIONAL EQUIVALENCES

Before we proceed, we must first understand the terms and operators used in this topic.

   

PROPOSITION is the statement that 
is either true or false.
        

COMPOUND PROPOSITION is the 

statement that is formed using 
logical operators.

Propositional Equivalences

Tautology is compound proposition that is always true.

p	¬p	p v ¬p
TRUE	FALSE	TRUE
FALSE	TRUE	TRUE

Contradiction is compound proposition that is always false.

p	¬p	p Λ ¬p
TRUE	FALSE	FALSE
FALSE	TRUE	FALSE

Contigency is proposition that is neither tautology nor contradiction.

Logical equivalent: two compound propositions that have the same truth value.

Example:

If it rains then I stay at home.

If I do not stay at home, then it does rain.

Applications of logical equivalent are:

•  De Morgan Law
•  Distributive Law