CS 621 Artificial Intelligence Lecture 7 - 16/08/05
Prof. Pushpak Bhattacharyya
Fuzzy Set (contd)
16-08-05 Prof. Pushpak Bhattacharyya, IIT Bombay
2
Fuzzy Subset
U = {1, 2, 3, 4,….,10}
A = {1, 2, 3, 4, 5}
B = {2, 3, 4}
B ⊂ A in CRISP SET THEORY μA(x) >= μB(x), ∀x
In terms of membership predicate Crisp subsethood
μS1(x) <= μS2(x), ∀x
Geometric Interpretation
(0,1) (1,1)
(0,0) (1,0)
A B1
B2 B3 x2
x1
U = {x1 , x2}
B s are such that
16-08-05 Prof. Pushpak Bhattacharyya, IIT Bombay
4
Geometric Interpretation (Contd 1)
• The points within the hypercube for which A is the upper right corner are the subsets of A.
• Space defined by the square is the power set of A.
• Formulation of ZADEH, classical fuzzy set theory
• For B to be a subset of A, μB(x) <= μA(x), ∀x.
This means B ∈ P(A) crisply. A
B
Geometric Interpretation (Contd 2)
• Each B
iis a subset of A to some degree.
A B1 B3
B2
• Result of Union, Intersection, Complement is a SET
• Subsethood is a question
16-08-05 Prof. Pushpak Bhattacharyya, IIT Bombay
6
Fuzzy Definition of Subsethood
• S(B,A) = subsethood of B wrt A
= 1 – ∑
xmax(0, μ
B(x) – μ
A(x))
∑
xμ
B(x)
• Question – Can S(B,A) be 0.
Theorem
• S(B,A) = m(A ∩ B) m(B)
m(S) = cardinality of S
= ∑xμS(x)
16-08-05 Prof. Pushpak Bhattacharyya, IIT Bombay
8
Proof of the Theorem
Proof:
RHS = 1 – ∑xmax(0, μB(x) – μA(x))
∑xμB(x)
= ∑x μB(x) – ∑xmax(0, μB(x) – μA(x)) m(B)
Proof of the Theorem (Contd)
= ∑xmin(μA(x), μB(x)) m(B)
= m(A ∩ B) m(B)
= LHS
16-08-05 Prof. Pushpak Bhattacharyya, IIT Bombay
10
Entropy of Subsethood
E(A) = m(A ∩ Ac) m(A ∪ Ac) S(B,A) = m(A ∩ B)
m(B)
S(A ∪ Ac, A ∩ Ac) = m((A ∪ Ac) ∩ (A ∩ Ac)) m(A ∪ Ac)
= m(A ∩ Ac) = E(A) m(A ∪ Ac)
Entropy of Fuzzy Set
• Entropy of fuzzy set is the degree by which A ∪ A
cis a subset of A ∩ A
c• Entropy is a measure by which WHOLE IS A SUBSET of its OWN PART !!!
• Subsethood in non-classical fuzzy logic is
a degree statement. This influences the
notion of Implication.
16-08-05 Prof. Pushpak Bhattacharyya, IIT Bombay
12
Fuzzy Logic
Set Theory Logic
Set S μ
S(x)
S
1∪ S
2μ
S1(x) ν μ
S2(x)
S
1∩ S
2μ
S1(x) Λ μ
S2(x)
S
1⊂ S
2μ
S1(x) → μ
S2(x)
Definitions of Logic Operations
Let P
1and P
2be fuzzy logic variables /predicates.
0 <= t(P
1) <= 1
0 <= t(P
2) <= 1 Fuzzy Logic
16-08-05 Prof. Pushpak Bhattacharyya, IIT Bombay
14
Fuzzy Operations
• Fuzzy ν :
max (t(P
1), t(P
2))
• Fuzzy Λ :
min(t(P
1), t(P
2))
• Fuzzy ~ :
1 – t(P)
Implication
• LUKISEWITZ LOGIC
Many multi-valued logic in 1930 t(P
1) → t(P
2)
= min (1, 1-t(P
1) + t(P
2))
16-08-05 Prof. Pushpak Bhattacharyya, IIT Bombay
16
Inferencing
• Modus Ponens
Given P
1& P
1→ P
2conclude P
2t(P
1) = 1,
t(P
1→ P
2) = 1
conclude t(P
2) = 1
- classical logic
Modus Tolens
• Given ~P
2and P
1→ P
2conclude ~P
1i.e t(P2) = 0,
t(P
1→ P
2) = 1
Conclude t(P
2) = 0
16-08-05 Prof. Pushpak Bhattacharyya, IIT Bombay
18
In Fuzzy Logic
We are given
t(P1) = a, 0<= a <= 1
t(P1 → P2) = b, 0<= b <=1 What can we say for t(P2)
t(P1 → P2) =min(1, 1 – t(P1) + t(P2)) By definition Luk. system of logic From given values
t(P1 → P2) = min(1, 1 – a + t(P2)) t(P1 → P2) = b
Case 1
b = min(1, 1 – a + t(P2)) b = 1
1 – a + t(P2) >= 1 or t(P2) >= a
- case of complete truth transfer
16-08-05 Prof. Pushpak Bhattacharyya, IIT Bombay
20
Case 2
b < 1
1 – a + t(P2) = b or t(P2) = a + b – 1 Combining 1 and 2 t(P2) = a + b -1
But this allows t(P2) to be < 0 t(P2) = max(0, a + b -1)
Fuzzy modus ponens.
Fuzzy Modus Tolens
t(P1 → P2) = b
t(P2) <= a, 0<=a<=1 What is t(P1)
Exercise: Deduce expression for fuzzy modus tolens