0.3 Discrete structures logic  (Page 18/23)

Thus the left side can be substituted for the right side whenever necessary in reasoning and vice versa.

Example

As an example of inference using these rules, let us consider the following reasoning:

A check is void if it has not been cashed for 30 days. This check has not been cashed for 30 days. Therefore this check is void. You can not cash a check which is void. Therefore you can not cash this check. We now have a check which can not be cashed.

This can be put into symbolic form using the following predicates assuming the universe is the set of all objects:

C(x): x is a check.

T(x): x has been cashed within 30 days.

V(x): x is void.

S(x): x can be cashed.

This_check represents a specific object in the universe which corresponds to "this check".

∀x [ [ C(x) ⋀ ¬T(x) ] →V(x) ]

¬T( This_check )

-----------------------------------

V( This_check )

∀x [ [ C(x) ⋀ V(x) ] →¬S(x) ]

----------------------------------------------

¬S( This_check )

-----------------------------------------------

∃x [ C(x) ⋀ ¬S(x) ] .

Here the reasoning proceeds as follows:

From ∀x [ [ C(x) ⋀ ¬T(x) ] →V(x) ]by Universal Instantiation

[ [ C( This_check ) ⋀¬T( This_check ) ] →V( This_check ) ]

Since This_check is a check and ¬T( This_check ) ,

[ C( This_check ) ⋀¬T( This_check ) ] holds.

Hence

[ [ C( This_check ) ⋀¬T( This_check ) ] →V( This_check ) ]

[ C( This_check ) ⋀¬T( This_check ) ]

---------------------------------------------------------

V( This_check )

by Modus Ponens.

Then from ∀x [ [ C(x) ⋀V(x) ] →¬S(x) ]by Universal Instantiation,

[ [ C( This_check ) ⋀V( This_check ) ] →¬S( This_check ) ]

Since V( This_check ) , and C( This_check ),

[ [ C( This_check ) ⋀V( This_check ) ] →¬S( This_check ) ]

[ C( This_check ) ⋀V( This_check ) ]

----------------------------------------------------

¬S( This_check )

by Modus Ponens.

Since C( This_check ) also holds,

¬S( This_check )

C( This_check )

----------------------------------------------------

C( This_check ) ⋀¬S( This_check )

Then by Existential Generalization ∃x [ C( x ) ⋀¬S(x) ] .

Quantifiers and connectives

Quantifiers and connectives 1

There are following four important relationships between quantifiers and connectives. They are used frequently in reasoning.

1. ∀x [ P(x) ⋀Q(x) ] ⇔[ ∀x P(x) ⋀∀x Q(x) ]

2. [ ∀x P(x) ⋁∀x Q(x) ] ⇒∀x [ P(x) ⋁Q(x) ]

3. ∃x [ P(x) ⋁Q(x) ] ⇔[ ∃x P(x) ⋁∃x Q(x) ]

4. ∃x [ P(x) ⋀Q(x) ] ⇒[ ∃x P(x) ⋀∃x Q(x) ]

Let us see what these mean with examples.

Let P(x) represent "x is rich", and Q(x) "x is happy", and let the universe be a set of three people. Also let LHS (RHS) denote the left (right) hand side of the implication or equivalence. Then

1. ∀x [ P(x) ⋀Q(x) ] ⇔[ ∀x P(x) ⋀∀x Q(x) ]can be illustrated as in Figure 1:

2. [ ∀x P(x) ⋁∀x Q(x) ] ⇒∀x [ P(x) ⋁Q(x) ]for the same interpretation as 1. above can be shown in Figure 2:

That is, LHS says everyone is rich or everyone is happy, and RHS says everyone is rich or happy. Thus if LHS is true, then RHS is certainly true. However on RHS it can happen that two people are rich but the third is not rich but happy. In that case LHS is not true while RHS is true. Thus RHS does not necessarily imply LHS.