Implications
Adriano Joaquim de O Cruz
©2002
NCE/UFRJ
[email protected]
Implication

Logic:
– Logical Implication as regarded in
mathematical logic.
– Material conditional as regarded in
philosophical logic.
– Semantic entailment between two sets of
statements.
@2002 Adriano Cruz
NCE e IM - UFRJ
Implicações 2
Logic
• Logical implication is a logical relation that
holds between a set T of formulas and a formula
B when every model (or interpretation or
valuation) of T is also a model of B. In symbols,
• Without using the language of models, the
material conditional formed from the
conjunction of all the elements of T and B is
valid. That is, it is valid that
A1    An  B
@2002 Adriano Cruz
NCE e IM - UFRJ
Implicações 3
Definitions


A set of sentences logically implies a
sentence B if and only if it is impossible
that all the members of the set be true
while B false.
A peculiar feature of logical implication
is that a contradiction implies anything
and that anything implies a validity.
@2002 Adriano Cruz
NCE e IM - UFRJ
Implicações 4
Implication





If xA then yB.
P is a proposition described by the set A
Q is a proposition described by the set B
PQ: If xA then yB
P implies Q
@2002 Adriano Cruz
NCE e IM - UFRJ
Implicações 5
Implication





An implication is a logical construction that
tell us if one condition is true, then another
condition must also be true.
Implication is not if and only if.
Implication P -> Q is true even if only Q is
true.
Elephants can fly, therefore it is hot today.
This statement is true if it is hot today.
@2002 Adriano Cruz
NCE e IM - UFRJ
Implicações 6
Implication - uses




“Kid, if you mown the grass then I will pay
you $10.00.”
Only one consequence is certain. It is not
well defined what will happen if the grass is
not mowed.
“If you do not eat all your broccolis then you
will not have dessert.”
Two consequences are understood. The
other one is dessert as a consequence of all
broccolis eaten.
@2002 Adriano Cruz
NCE e IM - UFRJ
Implicações 7
Implication - uses





“Kid, if you mown the grass then I will pay
you $10.00.”
Only one consequence is certain. It is not
well defined what will happen if the grass is
not mowed.
This is the mathematical sense of the
implication
If the proposition A is true then B is too.
Nothing can be said about B when A is false.
@2002 Adriano Cruz
NCE e IM - UFRJ
Implicações 8
Implication





If I am elected I will decrease taxes
I was not elected, I did not decrease
taxes
I was not elected, I did decrease taxes
I was elected, I did not decrease taxes
I was elected, I did decrease taxes
@2002 Adriano Cruz
NCE e IM - UFRJ
Implicações 9
Implication – Truth table
A
B
A -> B
F
F
T
F
T
T
T
F
F
T
T
T
•A->B=(not A) or B
•A->B=(not A) or (A and B)
@2002 Adriano Cruz
NCE e IM - UFRJ
Implicações 10
Families of Implication

Generalization of Material Implication
A  B = ¬A  B
R(x, y) =  ( 1  μ A (x))  (μ B (y) /(x, y)
(x,y)
R(x,y) =  1  ( 1  μ A (x)+ μ B (y))/(x, y)
(x,y)
min ( 1, a + b)
@2002 Adriano Cruz
NCE e IM - UFRJ
Implicações 11
Families of Implication

Propositional Calculus
A  B = ¬A  (A  B)
R( x, y) =  (1  μ A ( x))  ( μ A ( x)  μB ( y) /( x, y)
( x,y )

There are over 40 implication relations
reported in the literature
@2002 Adriano Cruz
NCE e IM - UFRJ
Implicações 12
Interpretations of Implication



A -> B as A entails B
Entailment is a relation between sets of
formulae such that, if A and B are sets of
formulae of a formal language, then A entails
B if and only if every model (or interpretation)
that makes all the members of A true, makes
at least one of the members of B true.
Entailment differs from implication, where the
truth of one (A) suggests the truth of the other
(B), but does not require it.
@2002 Adriano Cruz
NCE e IM - UFRJ
Implicações 13
Interpretations of Implication

There are fuzzy ways to interpret the
fuzzy rule if … then … else

First: A -> B as A entails (coupled) with
B
R( x, y) =  T ( μ A ( x) , μB ( y )) /( x, y)
(x,y)

Where T is a T-norm operator
@2002 Adriano Cruz
NCE e IM - UFRJ
Implicações 14
A coupled with B

Commonly used T-norms are:

Mamdani:
R( x, y) =  μ A ( x)  μB ( y) /( x, y)
( x,y )

Larson
R( x, y) =  μ A ( x)  μB ( y) /( x, y)
(x,y)

Bounded Product
R( x, y) =  0  ( μ A ( x) + μB ( y )  1) /( x, y)
(x,y)
@2002 Adriano Cruz
NCE e IM - UFRJ
Implicações 15
Implication Relation


Implication can be described as a
relation
The relation is defined by the T-norm
 μ(x , y ) /(x , y )
R(xi , yi ) =
i
(xi
i
i
i
,yi )
R(x,y) =  μ(x,y) /(x, y)
(x,y)
@2002 Adriano Cruz
NCE e IM - UFRJ
Implicações 16
Inference
Inference


Fuzzy inference refers to computational
procedures used for evaluating fuzzy
rules of the form if x is A then y is B
There are two important inferencing
procedures
– Generalized modus ponens (GMP) - mode
that affirms
– Generalized modus tollens (GMT) – mode
that denies
@2002 Adriano Cruz
NCE e IM - UFRJ
Implicações 18
Modus Ponens






If x is A then y is B
We know that x is A’ then we can infer
that y is B’
All men are mortal (rule)
Socrates is a man (this is true)
So Socrates is mortal (as a
consequence)
(A and (A -> B)) -> B
@2002 Adriano Cruz
NCE e IM - UFRJ
Implicações 19
Fuzzy Modus Ponens






If x is A then y is B
We know that x is A’ then we can infer
that y is B’
Tall men are heavy (rule)
John is tall (this is true)
So John is heavy (as a consequence)
(A and (A -> B)) -> B
@2002 Adriano Cruz
NCE e IM - UFRJ
Implicações 20
Fuzzy Modus Ponens proof - I
( A  ( A  B))  B start
( A  ( A  B))  B implication
( A  A)  ( A  B))  B distributivity
(   (A  B))  B
A B  B
@2002 Adriano Cruz
NCE e IM - UFRJ
Implicações 21
Fuzzy Modus Ponens proof - II
A B  B
( A  B )  B implication
( A  B )  B DeMorgan
( A  ( B  B)) Associativity
( A  X)
X
@2002 Adriano Cruz
NCE e IM - UFRJ
Implicações 22
Modus Tollens






If x is A then y is B
We know that y is not B then we can
infer that x is not A
All murderers owns axes (rule)
John does not own an axe (this is true)
So John is not a murderer (as a
consequence)
(not B and (A -> B)) -> not A
@2002 Adriano Cruz
NCE e IM - UFRJ
Implicações 23
Fuzzy Modus Tollens






If x is A then y is B
We know that y is not B then we can
infer that x is not A
All rainy days are cloudy (rule)
Today is not cloudy (this is true)
So Today is not raining (as a
consequence)
(not B and (A -> B)) -> not A
@2002 Adriano Cruz
NCE e IM - UFRJ
Implicações 24
Fuzzy Modus Tollens proof ?
@2002 Adriano Cruz
NCE e IM - UFRJ
Implicações 25
Reasoning Methods

Backward Chaining: the reasoning engine is
presented with a goal and asked to find all the
relevant, supporting processes that lead to this goal.

Forward Chaining: data is collected and and a
sustainable problem state and, eventually a solution
state is built.

Fuzzy Reasoning: rules are run in parallel. Every rule
contributes to the final shape of the consequent
solution. When all rules are evaluated the resulting
fuzzy sets are defuzzified.
@2002 Adriano Cruz
NCE e IM - UFRJ
Implicações 26
How to find the consequent





If x is A then y is B
This rule is a relation R(x,y)
If x is A’, we want to know whether y is
B’
B’= A’  R(x,y)
B’ (y)=x[A’(x) R(x,y)]
@2002 Adriano Cruz
NCE e IM - UFRJ
Implicações 27
Example

Consider the fuzzy set A
uA(3)
1.0
0.5
1

2
3
4
5
6
7
8
9
10
and the fuzzy set B
uB(y)
1.00
0.67
0.33
1
@2002 Adriano Cruz
2
3
4
5
6
7
8
9
NCE e IM - UFRJ
10
Implicações 28
Example 1
10
A =  μ A (xi ) / xi = 0.5/ 2 +1.0/ 3 + 0.5/ 4
i=0
10
B =  μB (yi ) / yi = 0.33/ 5 + 0.67/ 6 +1.0/ 7 + 0.67/ 8 + 0.33/ 9
i=0
@2002 Adriano Cruz
NCE e IM - UFRJ
Implicações 29
Example 2

We will use the Mamdani implication function
μ(xi , yi ) = μA(xi )  μB (yi )
R(xi , yi ) =
 μ(x , y ) /(x , y )
i
(xi
i
i
i
,yi )
R(xi , yi ) = 0.33/( 2,5)+ 0.5/( 2,6 )+ 0.5/( 2,7 )+
0.5/( 2,8)+ 0.33/( 2,9 )+ 0.33/( 3,5)+ 0.67/( 3,6 ) +
1.0/( 3,7 )+ 0.67/( 3,8) + 0.33/( 3,9 ) + 0.33/( 4,5)+
0.5/( 4,6 ) + 0.5/( 4,7 ) + 0.5/( 4,8)+ 0.33/( 4,9 )
@2002 Adriano Cruz
NCE e IM - UFRJ
Implicações 30
Example 3
R(xi , yi ) =
 μ(x , y ) /(x , y )
i
(xi
i
i
i
,yi )
B
5
6
7
8
9
A 2 0, 33 0, 50 0, 50 0, 50 0, 33
3 0, 33 0, 67 1, 00 0, 66 0, 33
4 0, 33 0, 50 0, 50 0, 50 0, 33
@2002 Adriano Cruz
NCE e IM - UFRJ
Implicações 31
Example 4


Consider the rule if x is A then y is B
Consider the statement x is A’, what is
the conclusion?
1.00
uA(4)=1.0
1
2
3
4
5
6
7
8
9
10
10
A =  μ A (xi ) / xi = 1.0/ 4
'
i=0
@2002 Adriano Cruz
NCE e IM - UFRJ
Implicações 32
Example 5
uA(3)
1.0
0.5
1
2
3
4
5
6
7
8
9
10
uB(y)
1.00
0.67
0.33
1
2
3
4
5
1.00
1 2 3 4 5
@2002 Adriano Cruz
6
7
8
9
10
uA(4)=1.0
6
7
8
9
10
NCE e IM - UFRJ
Implicações 33
Example 6
10
A =  μ A (xi ) / xi = 0.5/ 2 +1.0 / 3 + 0.5/ 4
i=0
10
B =  μB (yi ) / yi = 0.33/ 5 + 0.67/ 6 +1.0 / 7 + 0.67/ 8 + 0.33/ 9
i=0
10
A =  μ A (xi ) / xi = 1.0 / 4
'
i=0
@2002 Adriano Cruz
NCE e IM - UFRJ
Implicações 34
Example 7

B’(yi)=A’(xi)oR(xi,yi)
B' (yi ) = [ 0 0 1]°0.33 0.50 0.50 0.50 0.33


0.33 0.67 1.00 0.66 0.33
0.33 0.50 0.50 0.50 0.33
'
B = 0.33/ 5 + 0.50/ 6 + 0.50/ 7 + 0.50/ 8 + 0.33/ 9
@2002 Adriano Cruz
NCE e IM - UFRJ
Implicações 35
Example 8
uB(y)
1.00
0.67
0.33
1
2
3
4
5
6
7
8
9
10
uB’(y)
0.50
0.33
1
@2002 Adriano Cruz
2
3
4
5
6
7
8
NCE e IM - UFRJ
9
10
Implicações 36