³í¸®¿Í ºÒÈ®½Ç¼º
(Logic and Uncertainty)
C ÀΰøÁö´É ÇÁ·Î±×·¡¹Ö : Herbert Schildt ÁöÀ½, ½Å°æ¼÷.·ù¼º·Ä ¿Å±è, ¼¼¿õ, 1991 (¿ø¼ : Artificial Intelligence using C, McGraw-Hill, 1987), page 341~404
1.1. ³í¸®ÀÇ °£´ÜÇÑ ¿ª»ç (A short History of Logic)
1.2. ¸íÁ¦³í¸® (Propositional Logic)
1.3. ¼ú¾î³í¸® (Predicate Calculus)
4. È®·ü½Ã½ºÅÛ (PROBABILISTIC SYSTEMS)
4.1. ±âº» È®·ü ÀÌ·Ð (Basic probability Theory)
4.3. Weakest-Link ¹æ½Ä (The Weakest-Link Approach)
4.4. Strongest-Link ¹æ½Ä (The Strongest-Link Approach)
4.5. ¹æ¹ý ¼±Åà (Choosing a Method)
ÀÌ Àå¿¡¼´Â ±â°è Áö´É (machine intelligence) °ú ¹ÐÁ¢È÷ °ü°èÀÖ´Â µÎ°¡Áö Áß¿äÇÑ °³³äÀ» ´Ù·é´Ù. ù ¹øÂ° °³³äÀº ºÒÈ®½Ç¼º ¶Ç´Â ´õ Á¤È®È÷ ³í¸® ¹®Àå¿¡¼ ºÒÈ®½Ç¼ºÀÇ ÇØ°á (resolution) ÀÌ´Ù. ¸í¹éÈ÷, ¸¹Àº Áö½ÄÀº ƯÈ÷ °üÂû¿¡¼ ¾ò¾îÁø´Ù¸é ¾î´À Á¤µµ °³¿¬¼ºÀÌ ÀÖ´Ù (probabilistic) : Áï, ¾î¶² °Í¿¡ ´ëÇÏ¿© ¿¡·¯ °¡´É¼ºÀ» ¿©ÀüÈ÷ Çã¿ëÇÏ´Â ¹Ý¸é ÂüÀ̶ó°í ¹ÏÀ» ¼ö ÀÖ´Ù. ÄÄÇ»ÅͰ¡ Àΰ£°ú °°ÀÌ »ý°¢Çϰí Ãß·ÐÇϱâ À§ÇÏ¿©, ÀÌ ºÒÈ®½Ç¼ºÀ» ³í¸®¿Í ÅëÇÕÇÒ °ÍÀÌ ¿ä±¸µÈ´Ù.
³í¸®ÀÇ °³³äÀ» ¼³¸íÇϱâ À§ÇØ, ÀÌ Àå¿¡¼´Â µÎ °³ÀÇ ÇÁ·Î±×·¥À» °³¹ßÇÑ´Ù. ù ¹øÂ° ÇÁ·Î±×·¥Àº ¾î¶² ³í¸®Àû º¯Çü (transformation) À» ¼öÇàÇϰí, µÎ ¹øÂ° ÇÁ·Î±×·¥Àº ³í¸® Ç¥Çö¿¡ ´ëÇÑ °£´ÜÇÑ ÀÚ±âÈ£Ãâ ÇÏÇâÆÄ¼ (recursive-descent parser) ¸¦ ±¸ÇöÇÑ´Ù. ¸¶Áö¸·À¸·Î, ³í¸®¿Í ºÒÈ®½Ç¼ºÀ» ¿¬°áÇÏ´Â ¿¹·Î¼, ÀÌ Àå¿¡¼´Â Á¦ 3 Àå¿¡¼ °³¹ßµÈ Àü¹®°¡½Ã½ºÅÛÀÌ °¢ ¼Ó¼º (attribute) ¿¡ È®½Ç¼º °è¼ö (certainty coefficient) ¸¦ Æ÷ÇÔÇϵµ·Ï º¯ÇüÇÑ´Ù. ±×¸®°í ³ª¼ ÇØ¿¡ ´ëÇÑ È®½Ç¼º ¿ä¼Ò¸¦ »ý¼ºÇϱâ À§ÇÏ¿© ÀÌ È®½Ç¼º °è¼öµéÀ» »ç¿ëÇÑ´Ù.
³í¸®´Â ÄÄÇ»ÅÍ ÇÁ·Î±×·¥ÀÇ Áß½ÉÀÌ´Ù. ¿©·¯ ¸é¿¡¼, ÇÁ·Î±×·¡¹Ö ¾ð¾î´Â ´Ü¼øÈ÷ Ưº°ÇÑ ÇüÅÂÀÇ ³í¸®¸¦ ±¸ÇöÇÑ °ÍÀÌ´Ù. C ¿Í °°Àº ¾ð¾î¿¡¼, ³í¸®´Â if ¹®ÀÇ »ç¿ë¿¡ ÀÇÇØ ¾Ë ¼ö ÀÖ´Â °Íó·³, ÀϹÝÀûÀ¸·Î ÀýÂ÷Àû (procedural) ÀÌÁö¸¸, ÇÁ·Ñ·Î±×¿Í °°Àº ¾ð¾î´Â ³ªÁß¿¡ ¼³¸íµÉ, ¼ú¾î³í¸® (predicate calculus) ¶ó ºÎ¸£´Â Ưº°ÇÑ À¯ÇüÀÇ ³í¸®¸¦ »ç¿ëÇÑ´Ù. ±×·¯³ª, ¾î¶² ŸÀÔÀÇ ¾ð¾î¿¡¼µç ³í¸®´Â ÇÁ·Î±×·¡¹ÖÀÇ ÁßÃ߸¦ Çü¼ºÇÑ´Ù. AI ¿¡ ´ëÇÑ ³í¸®ÀÇ Á߿伺 ¶§¹®¿¡ ±× ¿ª»ç¸¦ °£´ÜÈ÷ »ìÆìº»´Ù.
ÃÖÃÊ·Î ¾Ë·ÁÁø ³í¸®ÇÐÀÚ´Â ±×¸®½ºÀÇ Ã¶ÇÐÀÚÀÌÀÚ ÀÚ¿¬°úÇÐÀÚÀÎ Aristoteles À̾ú´Ù. ±×´Â, ÇöÀç Ãß·Ð³í¸® (syllogistic logic) ¶Ç´Â °íÀü ³í¸® (classic logic) ¶ó°í ºÎ¸£´Â ÀÌ·ÐÀ» °³¹ßÇß´Ù. ±âº»ÀûÀ¸·Î Ãß·Ð³í¸®´Â öÇÐÀû ³íÀïÀ¸·ÎºÎÅÍ Áø¸® (¶Ç´Â °ÅÁþ) À» À̲ø¾î³»´Â °ÍÀ» ´Ù·é´Ù. ÀÌ·± À¯ÇüÀÇ ³í¸®´Â »ç½Ç»ó ¸ðµç ÇÕ¸®Àû ³íÀïÀÇ ±âÃÊÀ̱⠶§¹®¿¡ ¾ÆÁ÷µµ ³Î¸® »ç¿ëµÈ´Ù. ¿¹¸¦µé¾î, ´ÙÀ½ÀÇ ÂªÀº ³íÀïÀ» °øºÎÇØ º¸ÀÚ :
Á¸ÀÌ ³²¼ºÀÌ µÇ±â Àü¿¡ ¼Ò³âÀ̾ú´Ù´Â °ÍÀº »ó½ÄÀûÀ¸·Î ¾Ë ¼ö ÀÖ´Ù. Ãß·Ð ÇüÅ·Πº¯ÇüµÈ ÈÄ¿¡ ÀÌ ³íÀïÀº ´ÙÀ½°ú °°ÀÌ µÈ´Ù.
¿©±â¼ ±âÈ£, J, M, B ´Â °¢°¢ John, Man, Boys ¸¦ ÀǹÌÇÑ´Ù. ¡æ ¸¦ "ÀǹÌÇÑ´Ù (implies)" ¶Ç´Â "ÀÌ´Ù (is)" ·Î Àоî¶ó.
¿©·¯¸é¿¡¼, Ãß·Ð³í¸®´Â ´Ü¼øÈ÷ »ó½ÄÀ» Çü½ÄÈÇÑ °ÍÀÌ´Ù. ±×·¯³ª, Ãß·Ð ³í¸®´Â ÀÚ¿¬¾ð¾î¿¡ ±âÈ£Çϱ⠶§¹®¿¡ Á¾Á¾ ºÎÁ¤È®ÇÏ°í ¿ÀÇØÀÇ ¼ÒÁö°¡ ÀÖ´Â ÀÚ¿¬¾ð¾îÀÇ ÀáÀçÀû °áÁ¡ ¶§¹®¿¡ ¾î·Á¿òÀÌ ÀÖ´Ù. ¶ÇÇÑ, »ç¶÷µéÀº ¼±ÅÃÇØ¼ µè°Å³ª ÀÐÀ¸·Á´Â °æÇâÀÌ Àִµ¥ À̰ÍÀÌ ´õ È¥¶õÀ» ÀÏÀ¸Å³ ¼ö ÀÖ´Ù. ÀÌ·¯ÇÑ Á¤È®¼ºÀÇ ºÎÁ· ¶§¹®¿¡ °á±¹ ±âÈ£³í¸®°¡ ³ª¿À°Ô µÇ¾ú´Ù.
±âÈ£³í¸®´Â Gottfried Leibnitz °¡ ½ÃÀÛÇßÁö¸¸ ±×°¡ Á×Àº ÈÄ ÀØÇôÁ³´Ù. ±×°ÍÀ» ¹ß¸íÇß´Ù°í ÀÎÁ¤µÇ´Â »ç¶÷ÀÎ George Boole ¿¡ ÀÇÇØ Àü ºÐ¾ß°¡ ´Ù½Ã ¹ß°ßµÇ¾ú´Ù. ÀÌ·± À¯ÇüÀÇ ³í¸®¸¦ ÀϹÝÀûÀ¸·Î ºÒ¸®¾ð ³í¸®ÇÏ°í ºÎ¸¥´Ù. ±âÈ£³í¸®´Â °³³äÀ» ±âÈ£·Î Ãß»óÈÇϰí, ¿¬»êÀÚ¸¦ »ç¿ëÇÏ¿© ÀÌ ±âÈ£¸¦ ¿¬°áÇÑ´Ù. ¿¹¸¦µé¾î, ´ÙÀ½À» °øºÎÇØº¸ÀÚ :
±âÈ£³í¸®´Â ´ëºÎºÐÀÇ ÀýÂ÷Àû (procedural) ÇÁ·Î±×·¡¹Ö ¾ð¾îÀÇ ±âÃʸ¦ Çü¼ºÇϴµ¥, ÀÌ Àå¿¡¼ ÃÊÁ¡À» µÑ ³í¸®ÀÇ ÇüÅÂÀÌ´Ù.
±âÈ£³í¸®´Â µÎ°¡Áö ±¸º°µÇ´Â, ÇÏÁö¸¸ ¿¬°áµÇ´Â ºÐ¾ß°¡ ÀÖ´Ù : ù ¹øÂ°·Î ¸íÁ¦³í¸® (propositional logic) ÀÌ°í ´Ù¸¥ Çϳª´Â ¼ú¾î³í¸® (predicate logic) ÀÌ´Ù. ¸íÁ¦³í¸®´Â ¸íÁ¦ÀÇ Âü°ú °ÅÁþÀ» ´Ù·ç´Â ¹Ý¸é, ¼ú¾î³í¸®´Â ´ë»ó (object) °ú ´ë»óÀÇ ºÎ·ù (class) »çÀÌÀÇ °ü°èµµ Æ÷ÇÔÇÑ´Ù.
¸íÁ¦³í¸®´Â ¿©·¯ ¸íÁ¦ÀÇ ¿Ç°í ±×¸§¿¡ ´ëÇÑ °áÁ¤À» ´Ù·é´Ù. ¸íÁ¦´Â Àû´çÈ÷ Çü¼ºµÈ, ÂüÀ̳ª °ÅÁþÀÎ ¹®ÀåÀÌ´Ù. ¸íÁ¦³í¸®´Â ¸íÁ¦µéÀ» ¿¬°áÇϱâ À§ÇÏ¿© ¿¬»êÀÚµéÀ» »ç¿ëÇÑ´Ù. ´ëºÎºÐ ÈçÈ÷ ¾²ÀÌ´Â ¿¬»êÀÚµéÀº ´ÙÀ½°ú °°´Ù : AND, OR, NOT, IMPLIES, EQUIVALENT
¿¹¸¦µé¾î, µÎ °³ÀÇ ¸íÁ¦ P ¿Í Q ¸¦ °¡Á¤ÇÏÀÚ. ´ÙÀ½ÀÇ Áø¸®Ç¥´Â P ¿Í Q ÀÇ ´Ù¸¥ °ªµé¿¡ ¿¬»êÀÚµéÀ» Àû¿ëÇÑ ÈÄÀÇ °¢ ¿¬»ê¿¡ ´ëÇÑ °á°ú °ªÀ» º¸¿©ÁØ´Ù.
P |
Q |
¡P (NOT) |
~Q |
P ¡ü Q |
P ¡ý Q |
P |
P ¡æ Q (IMPLIES) |
P ¡ê Q (EQUIVALENT) |
T T F F |
T F T F |
F F T T |
F T F T |
T F F F |
T T T F |
F T T F |
T F T T |
T F F T |
ÀÌ ¿¬»êµéÀº, »ç½Ç»ó ¸ðµç ÇÁ·Î±×·¡¹Ö ¾ð¾î¿Í ÇÁ·Î±×·¥ Á¦¾îÀÇ ±âÃʷμ ¸íÁ¦³í¸®¸¦ »ç¿ëÇϱ⠶§¹®¿¡ Àß ¾Ë¾Æ¾ß ÇÑ´Ù. ÀÌ ¿¬»êÀÚµéÀ» »ç¿ëÇÏ¿© ´ÙÀ½¿¡ ÀÖ´Â °Íó·³, º¹ÀâÇÑ ¼ö½ÄÀ» ¸¸µé¾î ³¾ ¼ö ÀÖ´Ù :
A AND B OR C AND NOT D
ÀÌ ¼ö½ÄÀº ¿ÞÂÊ¿¡¼ ¿À¸¥ÂÊÀ¸·Î °ªÀÌ °áÁ¤µÈ´Ù (evaluate). ¼ö½Ä¿¡ °ýÈ£¸¦ ÷°¡½ÃŰ¸é ¼öÇп¡¼¿Í °°Àº ¹æ¹ýÀ¸·Î ±â´ÉÀ» ÇÑ´Ù : °ýÈ£´Â ±× ¾È¿¡ ÀÖ´Â ¼ö½ÄÀÇ ÀϺΠ(subexpression) ÀÇ ¿ì¼±¼øÀ§¸¦ ³ôÀδÙ. ´ÙÀ½ ¼ö½ÄÀº ¹æ±Ý ÁÖ¾îÁø ¼ö½ÄÀÇ ÀÚ¿¬ÀûÀÎ °è»ê¼ø¼ (evaluation order) ¸¦ º¸¿©ÁÖ±â À§ÇÏ¿© °ýÈ£¸¦ »ç¿ëÇÑ´Ù.
(A AND B) OR (C AND NOT D)
¿©±â¼, °ýÈ£´Â ÀÚ¿¬ÀûÀÎ °è»ê ¼ø¼¸¦ ¹Ù²Ù±â À§ÇÏ¿© »ç¿ëµÈ´Ù :
A AND (B OR (C AND NOT D))
¸¹Àº ´Ù¸¥ ¹ýÄ¢µéÀÌ ¼ö½ÄÀÇ Á¶ÀÛÀ» ÅëÁ¦ÇÑ´Ù. ù ¹øÂ° ¹ýÄ¢Àº ±³È¯¹ýÄ¢ÀÌ´Ù. À̰ÍÀº ´ÙÀ½°ú °°´Ù.
P AND Q ¡ê Q AND P
P OR Q ¡ê Q OR P
¿©±â¼ ¡ê ´Â "~¿Í °°´Ù" ¸¦ ÀǹÌÇÑ´Ù.
°áÇÕ¹ýÄ¢Àº ´ÙÀ½°ú °°´Ù.
(P AND Q) AND R ¡ê P AND (Q AND R)
(P OR Q) OR R ¡ê P OR (Q OR R)
Á» ´õ Áß¿äÇÑ ¹ýÄ¢ÁßÀÇ Çϳª°¡ µå¸ð¸£°ÀÇ ¹ýÄ¢Àε¥, ´ÙÀ½°ú °°´Ù.
NOT (P OR Q) ¡ê NOT P AND NOT Q
NOT (P AND Q) ¡ê NOT P OR NOT Q
¹èºÐ¹ýÄ¢Àº ´ÙÀ½À» ¸»ÇÑ´Ù.
P AND (Q OR R) ¡ê (P AND Q) OR (P AND R)
P OR (Q AND R) ¡ê (P OR Q) AND (P OR R)
C ÀÚü°¡ ¸íÁ¦³í¸®¸¦ Áö¿øÇϱ⠶§¹®¿¡, ÀÌ·¯ÇÑ º¯È¯±ÔÄ¢ (transformation rule) À» Àû¿ëÇÒ C ÇÁ·Î±×·¥À» ÀÛ¼ºÇÏ´Â °ÍÀº ¾ÆÁÖ ½±´Ù. ¿¹¸¦µé¾î, Ãâ¹ßÁ¡À¸·Î¼ ´ÙÀ½ ÇÁ·Î±×·¥À» »ç¿ëÇÒ ¼ö ÀÖ´Ù. ÀÌ ÇÁ·Î±×·¥Àº µå¸ð¸£° º¯È¯À» ¼öÇàÇÑ´Ù. ÇÁ·Î±×·¥Àº ¾ÆÁÖ Âª°í, ±×°ÍÀÇ µ¿ÀÛÀº ¸í¹éÇØ¾ß ÇÑ´Ù. ÁÖ¿ä ·çÆ¾ÀÎ transform() Àº, ¸ÕÀú ¾î¶² À¯ÇüÀÇ ¼ö½ÄÀÌ ÀÖ´ÂÁö¸¦ °áÁ¤ÇÏ°í ±×¸®°í³ª¼ ¿ä±¸µÇ´Â´ë·Î º¯À» ¼öÇàÇÔÀ¸·Î½á ´ëºÎºÐÀÇ ÀÏÀ» ÇÑ´Ù.
/* Logical transformation program for DeMorgan's laws */
char input[80]; char token[80];
char *p_pos;
main() { for (; ;) { printf(" : "); gets(input) if (!*input) break; p_pos=input; transform(); } }
/* do the transformations */ transform() { char p[80], q[80], s[4]; char is_and;
/* try DeMorgan's theorems */ /* first, try form : not (p or q) ==> not p and not q */ get_token(); if (!strcmp(token, "not")) { get_token(); if (*token=='(') { get_token(); strcpy(p, token); get_token(); if (!strcmp(token, "and")) is_and=1; else is_and=0; get_token(); strcpy(q, token); get_token(); if (*token==')') { /* is a DeMorgan expression */ if (is_and) strcpy(s, "or"); else strcpy(s, "and"); printf("not %s %s not %s ¡¬n", p, s, q); return; } } } /* now try reverse transformation of form
not p or q ==> not (p and q)
*/ p_pos=input; /* reset */ get_token(); if (!strcmp(token, "not")) { get_token(); strcpy(p, token); get_token(); if (!strcmp(token, "and")) is_and=1; else is_and=0; get_token(); if (!strcmp(token, "not")) { get_token(); strcpy(q, token); if (is_and) strcpy(s, "or"); else strcpy(s, "and"); printf("not (%s %s %s) ¡¬n", p, s, q); } } }
/* return a token from the input stream */ get_token() { char *p;
p=token; /* skip spaces */ while (*p_pos==' ') p_pos++;
if (*p_pos=='¡¬0') { /* is end of input */ *p++='¡¬0'; return; } if (is_in(*p_pos, "()")) { *p=*p_pos; p++, p_pos++; *p='¡¬0'; return; }
/* read word until */ while (*p_pos!=' ' && !is_in(*p_pos, "()")) { *p=*p_pos++; p++; } *p='¡¬0': }
is_in(c, s) char c, *s; { while (*s) { if (c==*s) return 1; s++; } return 0; } |
ÀÌ ÇÁ·Î±×·¥À» »ç¿ëÇϱâ À§ÇØ, À¯È¿ÇÑ ¼ö½ÄÀ» ³Ö¾î¶ó. ±×·¯¸é ÇÁ·Î±×·¥Àº º¯È¯À» µð½ºÇ÷¹ÀÌÇÒ °ÍÀÌ´Ù. ¿¹¸¦µé¾î,
not (a and b) |
¸¦ ÀÔ·ÂÇϸé ÇÁ·Î±×·¥Àº º¯È¯ (µå¸ð¸£°ÀÇ ¹ýÄ¢¿¡ ÀÇÇØ¼)
not a or not b |
¸¦ µð½ºÇ÷¹ÀÌÇÒ °ÍÀÌ´Ù.
³ª¸ÓÁö º¯È¯±ÔÄ¢µéÀ» ±¸ÇöÇÏ´Â °ÍÀÌ Àç¹ÌÀÖ´Ù´Â °ÍÀ» ¾Ë ¼ö ÀÖÀ» °ÍÀÌ´Ù. ¶ÇÇÑ, ´Ü¼øÈ÷ ´äÀ» ÇÁ¸°Æ®ÇÏ´Â ´ë½Å, transform() À¸·Î ÇÏ¿©±Ý Àڽſ¡°Ô ¹Ýº¹ÀûÀ¸·Î (recursively) Àü´ÞÇÑ ½ºÆ®¸µÀ» »ý¼ºÇÏ°Ô ÇÏ¿© ´ÙÁߺ¯È¯ (multiple transformations) À» Çã¿ëÇÒ ¼ö ÀÖ´Ù.
¸íÁ¦³í¸®°¡ ºñ·Ï Áö´É°ú ÄÄÇ»ÅÍ ¾ð¾î¿¡ ´ëÇÑ ±âÃʸ¦ Çü¼ºÇÏÁö¸¸, ±×°Í¸¸À¸·Î ¼¼°è¿¡ ´ëÇÑ Àΰ£ÀÇ Áö½ÄÀ» Ç¥ÇöÇϱâ À§ÇÏ¿© ±×°ÍÀ» »ç¿ëÇÒ ¼ö´Â ¾ø´Ù. ¸íÁ¦³í¸®´Â ´ë»óµé »çÀÌÀÇ °ü°è¸¦ Ç¥ÇöÇÏ´Â ´É·ÂÀÌ ºÎÁ·Çϱ⠶§¹®¿¡, ÁÖ¾îÁø °æ¿ì¿¡ ´ëÇÑ ¿Ç°í ±×¸§À» °áÁ¤ÇÏ´Â µ¥¿¡¸¸ ÇÑÁ¤µÇ°í ºÐ·ù (classifications) ¿¡¼´Â »ç¿ëµÉ ¼ö ¾ø´Ù. ÀÌ ºÎÁ·Àº ´ÙÀ½ ÀýÀÇ ÁÖÁ¦ÀÎ ¼ú¾î³í¸®·Î À̲ö´Ù.
¼ú¾î³í¸®´Â ¹ÌÀûºÐÇÐ (calculus) À̶ó°í ÇÏ´Â ´õ ³ôÀº ¼öÇÐÀÇ °¡Áö¿Í °ü°è°¡ ÀüÇô ¾ø´Ù. ¶§·Î predicate logic À̶ó°í ºÒ¸®´Â predicate calculus ´Â ´Ü¼øÈ÷, °³°³ÀÇ ´ë»óµé¿¡ ´ëÇÑ ¹®ÀåÀÌ Áø¸®°ªÀ» À§ÇÏ¿© °ËÅäµÇ°Ô ÇÏ´Â ¸íÁ¦³í¸®¸¦ È®ÀåÇÑ °ÍÀÌ´Ù.
¼ú¾î³í¸®¿¡ ´ëÇÑ ±âÃÊ´Â, ±âº»ÀûÀ¸·Î ÀÎÀÚ¿¡ µû¶ó Âü°ªÀ̳ª °ÅÁþÀÇ °ªÀ» ¸®ÅÏÇÏ´Â ÇÔ¼öÀÎ ¼ú¾î (predicate) ÀÌ´Ù. (ÇÁ·Ñ·Î±×¸¦ ¾Ë¸é ±× °³³ä°ú À̸§¿¡ Ä£¼÷ÇÒ °ÍÀÌ´Ù). ÇѰ¡Áö °£´ÜÇÑ ¼ú¾î´Â is-hard ÀÏ ¼ö ÀÖ´Ù. ÀÎÀÚÀÎ rock À» °è»ê (evaluate) ÇÒ ¶§, is-hard ´Â Âü°ªÀ» ¸®ÅÏÇÒ °ÍÀÌ´Ù. ±×·¯³ª, ÀÎÀÚÀÎ cotton À» °è»êÇϸé is-hard ´Â °ÅÁþÀ» ¸®ÅÏÇÒ °ÍÀÌ´Ù. ¼ú¾î³í¸®¿¡¼ À̰ÍÀº ´ÙÀ½°ú °°ÀÌ ¾²¿©Áú °ÍÀÌ´Ù.
is_hard(rock) ¡æ true
is_hard(cotton) ¡æ false
ÀÌ µÎ°¡Áö ¼ú¾î¿Í ÀÎÀÚµéÀ» ¸íÁ¦³í¸®·Î ´ÙÀ½°ú °°ÀÌ ¾µ ¼ö ÀÖ´Ù.
a rock is hard
cotton is not hard
¼ú¾î³í¸®¿Í ¸íÁ¦³í¸® »çÀÌÀÇ ±Ùº»Àû Â÷ÀÌ´Â ¾Æ¸¶µµ ¼Ó¼º (attribute) À» ¼ÒÀ¯ÇÏ´Â ´ë»óÀ¸·ÎºÎÅÍ ±×°ÍÀ» ºÐ¸®ÇÑ´Ù´Â °ÍÀÌ´Ù : Áï, ¼ú¾î³í¸®¿¡¼, ¾î¶² ÁÖ¾îÁø ´ë»óÀÇ °ß°í¼ºµµ °áÁ¤ÇÏ´Â ÇÔ¼ö¸¦ ¸¸µé ¼ö ÀÖ´Ù. ±×·¯³ª, ¸íÁ¦³í¸®¿¡¼, °¢ °æ¿ì¿¡ ´ëÇÏ¿© »õ·Î¿î ¹®ÀåÀ» ¸¸µé¾î³»¾ß ÇÑ´Ù. ¼ú¾î´Â ¿©·¯ °³ÀÇ ÀÎÀÚ¸¦ °¡Áú ¼ö ÀÖ´Ù´Â °ÍÀ» ÀÌÇØÇÏ´Â °ÍÀÌ Áß¿äÇÏ´Ù. ¿¹¸¦µé¾î, ¼ú¾î equal Àº µÎ °³ÀÇ ÀÎÀÚ¸¦ ¿ä±¸ÇÏ°í µÑÀÌ °°À¸¸é ÂüÀ» ¸®ÅÏÇÑ´Ù.
¾Æ¸¶µµ ¼ú¾î³í¸®°¡ ¸íÁ¦³í¸®¿¡ ´ëÇÏ¿© Á¦°øÇÏ´Â °¡Àå Å« °³¼±Àº º¯¼öÀÇ »ç¿ë¿¡ ÀÖÀ» °ÍÀÌ´Ù. ¼ú¾î³í¸®´Â ´ÙÀ½¿¡ ÀÖ´Â °Íó·³, ¼ú¾îµéÀ» ÀϹÝÈÇϱâ À§ÇÏ¿© º¯¼ö¸¦ »ç¿ëÇÑ´Ù.
man(X) ¡æ not woman(X)
À̸¦ "¸¸¾à X °¡ ³²¼ºÀ̸é, X ´Â ¿©¼ºÀÌ ¾Æ´Ï´Ù" ¶ó°í Àоî¾ß ÇÑ´Ù.
¼ú¾î³í¸®ÀÇ ¶Ç ´Ù¸¥ Áß¿äÇÑ ¸éÀº ÇÑÁ¤ÀÚ (Quantifier) ÀÇ »ç¿ëÀÌ´Ù. ¼ú¾î³í¸®´Â µÎ °³ÀÇ ÇÑÁ¤ÀÚ¸¦ »ç¿ëÇϴµ¥, ¿©±â¿¡ Ç¥ÁØ Ç¥±â¹ýÀ¸·Î º¸¿©Áø´Ù.
ÀÇ¹Ì |
¼ú¾î³í¸® ±âÈ£ |
¼³¸í |
ÀüαâÈ£(îïöàÑÀûÜ, for all) |
¢£x ¶Ç´Â (x) |
¸ðµç x¿¡ ´ëÇÏ¿©, ¿µ¹®À¸·Î for all x. ¢£¸¦ »ý·«ÇÏ°í ±×³É (x) ·Î ¾²±âµµ ÇÑ´Ù. º¸Æí¾çȱâÈ£ ¶Ç´Â ÀüĪÁ¤·®ÀÚ ·Î ¹ø¿ª |
Á¸Àç±âÈ£(ðíî¤ÑÀûÜ, there exists) |
¢¤x |
¾î¶² x¿¡ ´ëÇÏ¿© ... ÀÎ x °¡ Àû¾îµµ Çϳª Á¸ÀçÇÑ´Ù. ¿µ¹®À¸·Î´Â for some x, there exist at least some x such that .... Á¸Àç ¾çȱâÈ£ ¶Ç´Â Á¸Àç Á¤·®ÀÚ ·Î ¹ø¿ª |
"for all" ÇÑÁ¤ÀÚ´Â
¸ðµç °í¾çÀÌ´Â µ¿¹°ÀÌ´Ù. (All cats are animals.)
¿Í °°Àº ¹®ÀåÀ» µ¿ÀÏÇÑ ¼ú¾î³í¸®·Î º¯È¯ÇÑ´Ù :
¢£x.cat(X) ¡æ animal(x)
"there exists" ÇÑÁ¤ÀÚ´Â
Tom À̶ó°í ÇÏ´Â »ç¶÷ÀÌ ÀÖ´Ù. (There is a person called Tom.)
¿Í °°Àº °³³äÀ» ´ÙÀ½°ú °°Àº Ç¥ÇöÀ¸·Î º¯ÇüÇÑ´Ù :
¢¤x.person(X) and name(X, Tom)
"name" Àº À̸§À» »ç¶÷°ú ¿¬°áÇϱâ À§ÇÏ¿© µÎ °³ÀÇ ÀÎÀÚ¸¦ »ç¿ëÇÑ´Ù´Â °ÍÀ» ÁÖ¸ñÇØ¾ß ÇÑ´Ù.
¼ú¾î³í¸®ÀÇ ´Ù¸¥ ¸éµéÀÌ ÀÖÁö¸¸, ÀÌ ¼³¸íÀÌ ±âº» °³³äÀ» Áֱ⿡ ´Ù¾çÇÑ ½Ç¼¼°è »ç½ÇµéÀ» ³í¸®Àû Ç¥ÇöÀ¸·Î ÀϹÝÈÇØ¼ Ç¥ÇöÇÒ ¼ö ÀÖ´Â ¼ö´ÜÀ» Á¦°øÇϱ⠶§¹®ÀÌ´Ù.
¸¸¾à ¼ú¾î³í¸®¿¡ ´ëÇÏ¿© ´õ ¸¹Àº °ÍÀ» ¹è¿ì´Â µ¥¿¡ °ü½ÉÀÌ ÀÖ´Ù¸é, ±× ÁÖÁ¦¿¡ °üÇÑ ¿©·¯ °¡Áö Ã¥µé°ú, ¼ú¾î³í¸®¸¦ ±¸ÇöÇÏ´Â ÇÁ·Ñ·Î±× ÇÁ·Î±×·¡¹Ö ¾ð¾î¸¦ ÂüÁ¶ÇØ¾ß ÇÑ´Ù. ÀÌ Ã¥ÀÌ ºñ·Ï C ·Î ¼ú¾î³í¸®ÀÇ Æ¯Á¤ÇÑ ¿¹µéÀ» °³¹ßÇÏÁö ¾ÊÁö¸¸ ¼ú¾î³í¸®¸¦ ±¸ÇöÇÏ´Â C ÇÁ·Î±×·¥À» ÀÛ¼ºÇϱ⸦ ¹Ù·¤·±Áöµµ ¸ðµç´Ù - ¾ÆÁÖ µµÀüÇÒ ¸¸ÇÑ ÀÏ·Î Áõ¸íµÈ´Ù.
³í¸®ÀÇ °¡Àå È£°¨ÀÌ °¡´Â ¸é ÁßÀÇ Çϳª´Â È®½ÇÇÏ´Ù´Â °ÍÀÌ´Ù. ³í¸®·Î Ç¥ÇöµÇ´Â °ÍµéÀº ÂüÀ̰ųª °ÅÁþÀÏ »ÓÀÌ´Ù. ±×·¯³ª ½Ç¼¼°è´Â ±×·¸Áö°¡ ¾Ê´Ù : Áß°£ Áö¿ªÀÌ ¸¹´Ù. ´õ Áß¿äÇϰÔ, ´ëºÎºÐÀÇ °üÂû¿¡ ´ëÇÑ À¯È¿¼º°ú ¿ÇÀ½Àº ±×°Í°ú °ü·ÃµÈ È®·ü¿ä¼Ò¿¡ ÀÇÇØ Áö¹è¸¦ ¹Þ´Â´Ù. ¿¹¸¦µé¾î, ¸Ó¸®À§·Î ³ª´Â Å« »õ¸¦ º¸¸é µ¶¼ö¸® ÀÏ ¼öµµ (could) ÀÖ¾úÁö¸¸ ¸Å ÀÏÁöµµ (might) ¸ð¸¥´Ù. ´ëºÎºÐ »ç¶÷µéÀº Àͼ÷ÇØ ÀÖÁö ¶§¹®¿¡ Å« ¾î·Á¿ò¾øÀÌ ÀÚ¿¬ °üÂû¿¡ ´ëÇÑ ºÒÈ®½Ç¼ºÀ» ´Ù·ê ¼ö ÀÖ´Ù. ±×·¯³ª, ÄÄÇ»ÅÍ·Î ÇÏ¿©±Ý ºÒÈ®½Ç¼ºÀ» ´Ù·ç°Ô ÇÏ´Â °ÍÀº ¾ó¸¶°£ÀÇ ³ë·ÂÀ» ¿ä±¸ÇÑ´Ù.
ºÒÈ®½Ç¼ºÀ» ÇØ°áÇϰųª ´Ù·ç´Â °ÍÀº ½Ç¼¼°è¿ÍÀÇ ¼º°øÀûÀÎ Á¢ÃËÀ» À§ÇÏ¿© ¿ä±¸µÇ±â ¶§¹®¿¡ ±â°èÁö´É (machine intelligence) ¿¡ Áß¿äÇÏ´Ù. ÆÐÅÏÀνĿ¡ ´ëÇÑ ÀåÀ¸·Î µ¹¾Æ°¡ »ý°¢Çغ¸ÀÚ : °Å±â¼ ºÎµúÄ£ °¡Àå ¾î·Á¿î ÇÏÁö¸¸ ÇØ°áµÇÁö ¾ÊÀº ¹®Á¦µé ÁßÀÇ Çϳª´Â ºÎºÐÀûÀ¸·Î¸¸ º¸ÀÌ´Â ¹°Ã¼ÀÇ ÀνÄÀÌ´Ù. ¿¹¸¦µé¾î, ÄÄÇ»ÅͰ¡ ´ÙÀ½ Àå¸éÀ» º¸¸é ±× ¹°Ã¼°¡ »ï°¢ÇüÀ̶ó°í ±â·ÏÇÒ °ÍÀΰ¡?
|
¶Ç ´Ù¸¥ ¿¹´Â ¿©·¯ °¡Áö Á¶°ÇÀÇ °á°ú¿¡ ¹ÙÅÁÀ» µÐ ¾÷¹«¸¦ ¼öÇàÇϵµ·Ï Áö½Ã¹ÞÀº ·Îº¿ÀÌ´Ù. Á¶°Çµé Áß ÇϳªÀÇ »óŰ¡ ¾Ë·ÁÁ® ÀÖÁö ¾Ê´Ù¸é ·Îº¿Àº ¹«¾ùÀ» Çϴ°¡? ÀÌ·¯ÇÑ ¼ºÁúÀÇ ¾î·Á¿î Á¡µéÀº ÄÄÇ»Å͸¦ ÀÚ¿¬ ȯ°æ¿¡ ÀûÀÀÇϵµ·Ï ¸¸µé·Á°í ÇÒ ¶§ ³Î¸® ÆÛÁö°Ô µÈ´Ù.
¾î¶² Á¤º¸°¡ ¾Ë·ÁÁ® ÀÖÁö ¾ÊÀº »óȲÀ» ÇØ°áÇÏ·Á°í ½ÃµµÇÏ´Â °ÍÀº AI ¿¬±¸ÀÇ µÎ °¡Áö Áß¿äÇÑ ºÐ¾ß·Î À̲ö´Ù. ù ¹øÂ° ºÐ¾ß´Â ÆÛÁö ·ÎÁ÷ (fuzzy logic) Àε¥ À̰ÍÀº ¹ÌÁöÀÇ °ªÀ» Æ÷ÇÔÇÏ´Â ³í¸®Àû Ç¥ÇöÀÇ °è»êÀ» ´Ù·é´Ù. µÎ ¹øÂ° ºÐ¾ß´Â È®·ü½Ã½ºÅÛ (probabilistic systems) À» ´Ù·ç´Âµ¥ À̰ÍÀº ´ä¿¡ µµ´ÞÇϱâ À§ÇÏ¿© ¿©·¯ »ç°ÇµéÀÇ ¹ß»ý È®·üÀ» ÀÌ¿ëÇÑ´Ù.
ÆÛÁö ·ÎÁ÷ (fuzzy logic) À̶õ ¿ë¾îÀÇ Á¤È®ÇÑ Àǹ̴Â, ³Ê¹«³ª ¸¹Àº ´Ù¸¥ »óȲ¿¡ Àû¿ëµÇ¾ú±â ¶§¹®¿¡ ¸ðÈ£ÇØÁø´Ù. ÀÌ ¼³¸í¿¡¼, ÆÛÁö ·ÎÁ÷ (fuzzy logic) Àº ¹ÌÁö¼ö¸¦ Æ÷ÇÔÇÒ ¼ö ÀÖ´Â ³í¸® ¼ö½ÄµéÀÇ °è»êÀ» ÀÏÄ´´Ù. ³í¸®´Â °áÁ¤Àû (deterministic) À̱⠶§¹®¿¡, ¹ÌÁö¼öÀÇ Á¸Àç°¡ ³í¸®Ç¥ÇöÀ» ¾µ¸ð¾ø°Ô ¸¸µç´Ù°í »ý°¢ÇÒ ¼öµµ ¸ð¸¥´Ù : ±×·¯³ª ¾î¶² °æ¿ì¿¡, ¹ÌÁö¼ö´Â ±× ¼ö½ÄÀÌ °è»êµÉ ¼ö ¾ø´Ù´Â °ÍÀ» ÀǹÌÇÏÁö ¾Ê´Â´Ù. ÆÛÁö ·ÎÁ÷¿¡¼, ³í¸®°ªÀº ´ÙÀ½ ÁßÀÇ ÇϳªÀÌ´Ù :
¹ÌÁöÀÇ °ªÀº Á¤È®È÷ ´ÙÀ½°ú °°´Ù : ÂüÀ̰ųª °ÅÁþÀÏ ¼ö ÀÖÁö¸¸ ½ÇÁ¦°ªÀÌ ¾Ë·ÁÁ® ÀÖÁö ¾Ê´Ù. ³í¸® ¼ö½Ä¿¡¼ ¹ÌÁö¼ö¸¦ ¾î¶»°Ô ´Ù·ê ¼ö ÀÖÀ»Áö º¸±â À§ÇÏ¿©, ³í¸® ¿¬»êÀڵ鿡 ´ëÇÏ¿© Ç¥ 1 ¿¡ ÀÖ´Â È®ÀåµÈ Áø¸®Ç¥¸¦ °øºÎÇØ º¸ÀÚ. ±×¸²¿¡¼ º¸¿©ÁÖµíÀÌ, NOT °ú EQUIVALENT ¿Í °°Àº ¸î¸î ¿¬»êµéÀº ¼ö½ÄÀÌ ¹ÌÁöÀÇ °ªÀ» Æ÷ÇÔÇÒ ¶§ Ç×»ó ºÒÈ®½ÇÇÏ´Ù. ±×·¯³ª, AND, OR, ±×¸®°í IMPLIES ¿¡ ´ëÇÏ¿© ¾î¶² °áÇÕµéÀº ¿©ÀüÈ÷ ¾Ë·ÁÁø °á°ú¸¦ »êÃâÇÒ °ÍÀÌ´Ù. ÀÌ °á°ú¿¡ ´ëÇÑ ÀÌÀ¯¸¦ ÀÌÇØÇϱâ À§ÇÏ¿©, AND ÀÇ °á°ú´Â ¾î´À ¿ÀÆÛ·£µå¶óµµ °ÅÁþÀ̸é Ç×»ó °ÅÁþÀÓÀ» ±â¾ïÇØ¾ß ÇÑ´Ù : ÇÑ ¿ÀÆÛ·£µå³ª µÎ ¿ÀÆÛ·£µå ¸ðµÎ°¡ ÂüÀ̸é OR ÀÇ °á°ú´Â ÂüÀÌ´Ù. ±×¸®°í, IMPLIES ¿¡ ´ëÇÏ¿© °ÅÁþÀÎ ÀüÁ¦´Â Ç×»ó ÂüÀ» ÀǹÌÇÑ´Ù (imply).
P |
Q |
¡P (NOT) |
P ¡ü Q |
P ¡ý Q |
P ¡æ Q (IMPLIES) |
P ¡ê Q (EQUIVALENT) |
T T F F U U T F |
T F T F T F U U |
F F T T U U F T |
T F F F U F U F |
T T T F T U T U |
T F T T U U U T |
T F F T U U U U |
Ç¥ 1. Áø¸®Ä¡Ç¥¸¦ È®ÀåÇÏ¸é ¾Ë·ÁÁöÁö ¾ÊÀº °Íµµ Æ÷ÇԵȴÙ.
ÆÛÁö ·ÎÁ÷ÀÇ ±ÔÄ¢µéÀ» ¾î¶»°Ô ÄÄÇ»ÅÍÈ ÇÏ´ÂÁö¸¦ º¸À̱â À§ÇÏ¿©, ÀÌ Àý¿¡¼´Â ÀÚ±âÈ£Ãâ ÇÏÇâ ³í¸® ¼ö½Ä ÆÄ¼ (recursive-descent logical-expression parser) ¸¦ °³¹ßÇÒ °ÍÀÌ´Ù. ÆÄ¼´Â ¼ö½ÄÀ» °è»êÇÏ´Â ·çƾµéÀÇ ÁýÇÕÀÓÀ» ±â¾ïÇØ¾ß ÇÑ´Ù. ÄÄÇ»ÅÍ ÇÁ·Î±×·¥ÀÌ °á°ú¸¦ °áÁ¤Çϱâ À§ÇÏ¿© »ê¼ú½ÄÀ» °è»êÇÒ ¼ö ÀÖ´Â °Í°ú ¶È°°ÀÌ, ÄÄÇ»ÅÍ ÇÁ·Î±×·¥Àº ³í¸® ¼ö½ÄÀ» °è»êÇÒ ¼ö ÀÖ´Ù. ÆÄ¼´Â ¸ðµç °í¼öÁØ ¾ð¾î ÄÄÆÄÀÏ·¯¿Í ´ëºÎºÐÀÇ ½ºÇÁ·¹µå½ÃÆ®¿Í µ¥ÀÌÅͺ£À̽º ÇÁ·Î±×·¥µé¿¡ ÀÇÇØ »ç¿ëµÈ´Ù.
¶ÇÇÑ 4 Àå¿¡¼ ÀÚ¿¬¾ð¾î ÆÄ¼ÀÇ »ç¿ëÀ» º¸¾Ò´Ù. ±×·¯³ª, ¾î¶² ÀÓÀÇÀÇ ³í¸® ¼ö½Äµµ °è»êÇÒ ·çƾÀ» ÀÛ¼ºÇÏ´Â ¹æ¹ýÀº Á÷°üÀûÀÎ °úÁ¤ÀÌ ¾Æ´Ï´Ù. ¿¹¸¦µé¾î, ´ÙÀ½ÀÇ À¯È¿ÇÑ ¼ö½ÄÀ» »ý°¢Çغ¸ÀÚ. ¿©±â¼ 1 Àº ÂüÀ» ³ªÅ¸³»°í, 0 Àº °ÅÁþÀ» ³ªÅ¸³»°í, U ´Â ¹ÌÁö¼ö¸¦ ³ªÅ¸³½´Ù.
1 AND 1
1 OR (U & 0)
NOT (1 | 0) & 1
¸ðµç ¼ö½ÄÀÌ 1 AND 1 ó·³ °£´ÜÇϸé, ¸ÕÀú ¿ÀÆÛ·£µå¸¦ Àаí, ±×¸®°í³ª¼ ¿ÀÆÛ·¹ÀÌÅÍ (¿¬»êÀÚ) ¸¦ Àаí, ¸¶Áö¸·À¸·Î µÎ ¹øÂ° ¿ÀÆÛ·£µå¸¦ Àд ·çƾÀ» ÀÛ¼ºÇÏ´Â °ÍÀÌ ½¬¿ï °ÍÀÌ´Ù. ±×·¯³ª ÀÌ·± ¹æ½ÄÀº ´õ º¹ÀâÇÏ°í °ýÈ£°¡ ¸¹Àº ¼ö½ÄÀ¸·Î ÀϹÝ鵃 ¼ö°¡ ¾ø´Ù. ¶ÇÇÑ, ·çƾÀº ¿©·¯ °¡Áö ¿¬»êÀÚµéÀÇ ¿ì¼±¼øÀ§¸¦ ¾î¶»°Ô ´Ù·ê °ÍÀΰ¡? ÀÌ·¯ÇÑ ¹®Á¦µéÀº ¿©±â¿¡ Á¦½ÃµÉ °Íµé°ú °°Àº ÆÄ¼¸¦ °³¹ßÇÏ°Ô ÇÑ´Ù.
ÆÄ¼¸¦ °£´ÜÇÏ°Ô À¯ÁöÇϱâ À§ÇÏ¿©, AND, OR, NOT ¿¬»êÀڵ鸸À» Áö¿øÇÒ °ÍÀÌ´Ù - ¼±ÅÃÇÑ´Ù¸é ³ªÁß¿¡ È®Àå½Ãų ¼öµµ ÀÖÁö¸¸, ÆÄ¼´Â ¿¬»êÀÚµéÀÇ ¿ì¼±¼øÀ§°¡ ´ÙÀ½°ú °°À» °ÍÀ¸·Î °¡Á¤ÇÑ´Ù :
ÃÖ°í NOT
AND
ÃÖÀú OR
ÆÄ¼¸¦ ÀÛ¼ºÇÒ ¼ö ÀÖ±â Àü¿¡, À¯È¿ÇÑ ¼ö½ÄÀÌ ±¸¼ºµÉ ¼ö ÀÖ´Â ¹æ¹ýÀ» ¹¦»çÇÏ´Â »ý¼º±ÔÄ¢À̶ó°í ºÒ¸®´Â Çü½Ä ±ÔÄ¢ (formal rules) µéÀÇ ÁýÇÕÀ» Á¤ÀÇÇØ¾ß ÇÑ´Ù. ÀÚ¿¬¾ð¾î 󸮿¡ °üÇÑ Àå¿¡¼ º¸¾ÒµíÀÌ ÀÚ±âÈ£Ãâ ÇÏÇâ ÆÄ¼´Â ¼ö½ÄÀÇ »ý¼º ±ÔÄ¢À» ÀÌ °æ¿ì¿¡´Â ³í¸® ¼ö½Ä - ±× ¼ö½ÄÀ» °è»êÇÏ´Â ÀÏ·ÃÀÇ ¼·Î, µÇºÎ¸£´Â ÇÔ¼öµé (mutually recursive functions) ·Î º¯È¯ÇÑ´Ù. ¸ðµç »ý¼º ±ÔÄ¢Àº ¿ÞÂʰú ¿À¸¥ÂÊÀ» »ý¼ºÇÒ ¼ö ÀÖ´Ù. ¶Ç´Â ¿À¸¥ÂÊÀ¸·Î º¯ÇüµÉ ¼ö ÀÖ´Ù. ±×·¯¹Ç·Î, À̸§ÀÌ »ý¼º ±ÔÄ¢ (production) ÀÌ´Ù. »ý¼º ±ÔÄ¢ÀÇ ÀϹÝÀûÀΠǥ±â (notation) ¿¡¼, ¼±ÅÃÀû »ý¼ºÀº »ç°¢ ¸ð¾çÀÇ °ýÈ£ ¾È¿¡ Æ÷ÇԵȴÙ. ¿¹¸¦µé¾î, ÀÌ Àå¿¡¼ °³¹ßµÈ ÆÄ¼¿¡ ÀÇÇØ »ç¿ëµÈ »ý¼º ±ÔÄ¢ÀÌ ´ÙÀ½¿¡ ÀÖ´Ù.
Expression ¡æ Term [OR Term]
Term ¡æ Factor [AND Factor]
Factor ¡æ [Primitive] [(Expression)] [NOT Factor]
Primitive ¡æ [True] [False] [Unknown]
ÀÌ »ý¼º ±ÔÄ¢µéÀº, AND, OR, NOT ¿¬»êÀÚµéÀ» »ç¿ëÇÏ¿© Çü¼ºÇÒ ¼ö ÀÖ´Â °ýÈ£°¡ Æ÷ÇÔÇÏ¿© °¡´ÉÇÑ À¯È¿¼ö½Äµé ¸ðµÎ¸¦ Á¤ÀÇÇÒ »Ó ¾Æ´Ï¶ó, ÀáÀçÀûÀ¸·Î ¿¬»êÀÚµéÀÇ ¿ì¼±¼øÀ§¸¦ °áÁ¤ÇÑ´Ù. ÀÌ ±ÔÄ¢µéÀÌ ÀÛµ¿ÇÏ´ÂÁö ¾Ë±â À§ÇÏ¿© ´ÙÀ½ ¼ö½ÄÀ» »ý°¢Çغ¸ÀÚ.
true AND (false OR true)
ù ¹øÂ° factor ´Â primitive ÀÎ true Àε¥, À̰ÍÀº µÎ ¹øÂ° factor ¸¦ Çü¼ºÇÏ´Â °ýÈ£°¡ ÀÖ´Â ¼ö½ÄÀÌ µû¶ó ³ª¿Â´Ù. °ýÈ£°¡ ÀÖ´Â ¼ö½Ä ¾È¿¡¼, false ´Â ù ¹øÂ° term À̰í true °¡ µÎ ¹øÂ° term ÀÌ´Ù.
´Ü¼ø¼ºÀ» À§ÇØ, ¿©±â ÁÖ¾îÁø ÆÄ¼´Â ´ÙÀ½ ±âÈ£µéÀ» »ç¿ëÇÑ´Ù :
±âÈ£ |
ÀÇ¹Ì |
& | ! u 1 0 |
AND OR NOT unknown true false |
¿©±â¿¡ ÀÖ´Â ÀÚ±âÈ£Ãâ ÇÏÇâ³í¸® ¼ö½Ä ÆÄ¼¸¦ °ËÅäÇÒ ¶§, ¹æ±Ý ÁÖ¾îÁø ¼³¸íÀ» ±â¾ïÇØ¾ß ÇÑ´Ù. ÀÌÁ¦ ÄÄÇ»ÅÍ¿¡ ÇÁ·Î±×·¥À» ³Ö¾î¾ß ÇÑ´Ù.
/* fuzzy-logic analyzer */
char expr[80]; char token[80]; char *p_pos;
main() { int result; for (; ;) { printf("enter expression : "); gets(expr) if (!*expr) break; p_pos=expr; analyze(&result); printf("answer is : "); switch (result) { case 1 : printf("true¡¬n"); break; case 0 : printf("false¡¬n"); break; case 'u' : printf("unknown¡¬n"); break; } } }
analyze(result) int *result; { get_token(); if (!*token) { serror(2); return; } level1(result); }
/* logic parser */ level1(result) int *result; { register char op; int hold;
level2(result); while ((op=*token)=='|') { get_token(); level2(&hold); determine(op, result, &hold); } }
level2(result) int *result; { int hold; char op;
level3(result); while ((op=*token)=='&') { get_token(); level3(&hold); determine(op, result, &hold); } }
level3(result) int *result; { register char op; op=0; if (*token=='!') { op='!'; get_token(); } level4(result); if (op) determine(op, result, result); }
level4(result) int *result; { if ((*token=='(')) { get_token(); level1(result); if (*token!=')') serror(1) get_token(); }
else primitive(result); }
primitive(result) int *result; { register int i;
if (is_in(*token, "01u")) { if (*token=='u') *result='u'; else *result=atoi(token); return get_token(); } serror(0); /* otherwise syntax error in expression */ }
determine(o, r, h) char o; int *r, *h; { register int t, ex; switch (o) { case '&' : if (*r!='u' && *h!='u') { *r=*r && *h; return; } if (*r=='u' && *h==0) *r=0; else if (*r==0 && *h=='u') *r=0; else *r='u'; break; case '|' : if (*r!='u' && *h!='u') { *r=*r && *h; return; } if (*r==1 && *h==1) *r=1; else *r='u'; break; case '!' : if (*r=='u') *r=!*r; else *r='u'; break; } }
serror(error) int error; { static char *e[]= { "syntax error", "unbalanced parenthesis", "no expression present" }; printf("%s¡¬n", e[error]); }
get_token() { char *p; p=token; /* skip spaces */ while (*p_pos==' ') p_pos++; if (*p_pos=='¡¬0') { /* is end of input * *p++='¡¬0'; return; } if (is_in(*p_pos, "()|&!")) { *p=*p_pos; p++, p_pos++; *p='¡¬0'; return; } /* read word until */ while (*p_pos!=' ' && !is_in(*p_pos, "()|&!")) { *p=*p_pos++; p++; } *p='¡¬0': }
is_in(c, s) char c, *s; { while (*s) { if (c=*s) return 1; s++; } return 0; } |
ÀÌ ÇÁ·Î±×·¥À» »ç¿ëÇÏ¿©
1 & (u|) |
°ú °°Àº ¼ö½ÄÀ» ³ÖÀ» ¼ö ÀÖ°í, Á¤È®È÷ ÂüÀ¸·Î °è»êµÉ °ÍÀÌ´Ù. ¹Ý¸é ¼ö½Ä
1 & u |
Àº ºÒÈ®½ÇÇϱ⠶§¹®¿¡ ¹ÌÁöÀÇ °ª (unknown) À¸·Î °è»êµÉ °ÍÀÌ´Ù.
ÆÄ¼¸¦ ÀÌÇØÇϱâ À§ÇÏ¿©, ´Ü¼øÈ÷ ¾Õ¿¡¼ ¼³¸íµÈ »ý¼º ±ÔÄ¢µéÀ» ±¸ÇöÇÑ´Ù´Â °ÍÀ» ±â¾ïÇØ¾ß ÇÑ´Ù. ÆÄ¼´Â AI ¿Í °ü°èÀÖ´Â ¸¹Àº ÇÁ·Î±×·¥ÀÇ ±âÃʸ¦ Çü¼ºÇÒ ¼ö ÀÖ´Â °¡Ä¡ÀÖ´Â µµ±¸À̱⠶§¹®¿¡ ±×°ÍÀ» ÀÌÇØÇÒ ¶§±îÁö ÆÄ¼ÀÇ µ¿ÀÛÀ» °øºÎÇØ¾ß ÇÑ´Ù. ÆÄ¼¸¦ °¡Áö°í ½ÇÇèÇØ º¸¶ó - ¾Æ¸¶µµ IMPLIES ¿Í EQUIVALENT ¿Í °°Àº ºÎ°¡ÀûÀÎ ¿¬»êµéÀ» ¼ö¿ëÇÏ´Â ¼öÁØÀ» ÷°¡Çϸé¼.
ºÒÈ®½Ç¼ºÀÇ Ã³¸®¸¦ ¿ä±¸ÇÏ´Â °¡Àå Áß¿äÇÑ ºÐ¾ßµé ÁßÀÇ Çϳª´Â Àü¹®°¡½Ã½ºÅÛÀÌ ÁÁÀº Á¶¾ðÀ» ÇÏ´Â °ÍÀ̶ó¸é, ¶ÇÇÑ ±× Á¶¾ðÀÌ Á¤È®ÇÑ È®·üÀ» ±â·ÏÇØ¾ß ÇÑ´Ù. ÀÌ Àý¿¡¼´Â 3 Àå¿¡¼ °³¹ßµÈ Àü¹®°¡½Ã½ºÅÛ¿¡ ÀÌ ±â´ÉÀ» ÷°¡ÇÑ´Ù. ±×·¯³ª, ¸ÕÀú, ÀüÅëÀû È®·üÀÌ·ÐÀÇ ±âÃÊ¿¡ ´ëÇÑ º¹½ÀÀÌ ¿©±â Á¦½ÃµÈ´Ù. ÀÌÁ¦ º¼ °Íó·³, ÀÌ ±ÔÄ¢µéÀ» AI decision-making ¿¡ Àû¿ëµÉ ¶§ ±×°ÍµéÀ» ±×°÷À¸·Î µ¹·Á¾ß ÇÑ´Ù.
ºÎºÐÀûÀ¸·Î, ¹ß»ýÇÒ ¼ö ÀÖ´Â °¡´ÉÇÑ »ç°ÇÀÇ ¼ö´Â ¹ß»ýÇϴ ƯÁ¤ »ç°ÇÀÇ È®·üÀ» °áÁ¤ÇÑ´Ù. ¾î¶² »óȲ¿¡ °ü°èµÇ´Â ¸ðµç °¡´ÉÇÑ »ç°ÇµéÀÇ ÁýÇÕÀº »ç°Ç °ø°£ (event space) À̶ó°í ºÒ¸°´Ù. ¹ß»ýÇÏ´Â »ç°Ç °ø°£ ¼Ó¿¡¼ °¢ »ç°ÇÀÇ °¡´É¼ºÀÌ °°À¸¸é, ±×¸®°í ¾î¶² »ç°Çµµ °ãÄ¡Áö ¾ÊÀ¸¸é ¹ß»ýÇϴ ƯÁ¤ »ç°Ç X ÀÇ È®·ü (P) ´Â ´ÙÀ½°ú °°´Ù.
Px = 1/N
¿©±â¼ N Àº °¡´ÉÇÑ »ç°ÇÀÇ ¼öÀÌ´Ù. ¿¹¸¦µé¾î, ´øÁ®Áø µ¿ÀüÀÇ ¾ÕÀÌ ³ª¿Ã È®·üÀº, µÎ °³ÀÇ °¡´ÉÇÑ »ç°Ç - ¾Õ°ú µÚ - ÀÌ ÀÖ°í µÎ »ç°ÇÀÌ ¹ß»ýÇÒ °¡´É¼ºÀÌ °°±â ¶§¹®¿¡, 1/2 ÀÌ´Ù. ÇϳªÀÇ ÁÖ»çÀ§¸¦ »ç¿ëÇÏ¿© 3 À» ´øÁú È®·üÀº 1/6 Àε¥, À̰ÍÀº 6 °¡Áö °¡´ÉÇÑ °á°ú°¡ ÀÖ°í ¸ðµç °á°ú°¡ ¹ß»ýÇÒ °¡´É¼ºÀÌ ¶È°°±â ¶§¹®ÀÌ´Ù.
AI ÇÁ·Î±×·¡¸Ó¿¡°Ô °¡Àå Èï¹ÌÀÖ´Â È®·üºÎºÐÀº »ç°ÇµéÀÇ ¼ö¿ ¶Ç´Â »ç°ÇµéÀÇ Á¶ÇÕÀÌ ¹ß»ýÇÒ °¡´É¼ºÀ» °è»êÇÏ´Â °ÍÀÌ´Ù. °ø½ÄÀû È®·ü À̷п¡¼, »ç°ÇµéÀÇ Á¶ÇÕÀÇ È®·üÀº ±× »ç°Çµé °¢°¢ÀÇ È®·üÀÇ °ö°ú °°´Ù. ¿¹¸¦µé¾î µ¿ÀüÀ» ´øÁø ÈÄ Â÷·Ê·Î ¼¼ ¹ø ¾ÕÀÌ ³ª¿Ã È®·üÀº
1/2 * 1/2 * 1/2 = 1/8
ÀÌ´Ù. ¼ö¿À̳ª Á¶ÇÕÀ» Çü¼ºÇÏ´Â »ç°ÇµéÀº °ü·ÃµÉ ÇÊ¿ä´Â ¾ø´Ù´Â °ÍÀ» ÀÌÇØÇÏ´Â °ÍÀº Áß¿äÇÏ´Ù. ¿¹¸¦µé¾î, µ¿ÀüÀÇ ¾ÕÀÌ ³ª¿À°í ÁÖ»çÀ§ÀÇ 4 ¸¦ ´øÁú È®·üÀº ´ÙÀ½°ú °°´Ù.
1/2 * 1/6 = 1/12
¸ðµç È®·üÀº 0 °ú 1 À» Æ÷ÇÔÇÏ¿© ±× »çÀÌÀÇ °ªÀÌ´Ù. 1 ÀÇ È®·üÀ» °®´Â »ç°ÇÀº È®½ÇÇÑ »ç½ÇÀÌ´Ù : ¿¹¸¦µé¾î, Á×À½Àº È®½ÇÇÑ »ç½ÇÀÌ´Ù. 0 ÀÇ È®·üÀ» °®´Â »ç°ÇÀº ºÒ°¡´ÉÀÌ´Ù : ¿¹¸¦µé¾î, ¿µ¿øÈ÷ »ç´Â °ÍÀº ºÒ°¡´ÉÀ¸·Î »ý°¢µÉ °ÍÀÌ´Ù. 0 º¸´Ù À۰ųª 1 º¸´Ù Å« È®·üÀ» °®´Â °ÍÀº °¡´ÉÇÏÁö ¾Ê´Ù.
¾Õ¿¡¼ ¾ð±ÞÇßµíÀÌ, È®½ÇÇÑ °üÂûÀº °ÅÀÇ ¾ø´Ù - ¿ÀÈ÷·Á, ±×°ÍÀº ±×·² °Í °°Àº °ÍÀÌ´Ù. ±×·¯³ª, ¾î¶² À¯ÇüÀÇ Á¤º¸´Â ´Ù¸¥ °Íº¸´Ù »ç½ÇÀÏ °¡´É¼ºÀÌ ´õ ³ô°í, ¼º°øÀûÀÎ Àü¹®°¡½Ã½ºÅÛÀº ±×·¯ÇÑ Á¤º¸ÀÇ È®·üÀ» °í·ÁÇØ¾ß ÇÑ´Ù. ºÒÈ®½Ç¼ºÀ» ÇØ°áÇÒ ¹æ¹ýÀ¸·Î ÀüÅëÀûÀÎ È®·ü ÀÌ·ÐÀ» »ç¿ëÇÑ È¿°ú¸¦ Á¶»çÇØ º¸±â Àü¿¡, Á¦ 3 ÀåÀÇ Àü¹®°¡½Ã½ºÅÛÀº ¾Ë°í ÀÖ´Â °¢ Á¤º¸°¡ È®·ü ÀÎÀÚ¸¦ °®Ãßµµ·Ï º¯ÇüµÇ¾î¾ß ÇÑ´Ù.
¸ÕÀú, Áö½Äº£À̽º¸¦ º¯°æÇØ¾ß ÇÑ´Ù. È®½Ç¼º ¿ä¼Ò°¡ °¢ ¼Ó¼º (attribute) ¿Í °ü·ÃµÇ°Ô ÇÏ´Â °ÍÀº, ´ÙÀ½¿¡ ÀÖ´Â °Íó·³ attribute ±¸Á¶¿¡ ¶Ç ´Ù¸¥ Çʵ带 ÷°¡ÇÒ °ÍÀ» ¿ä±¸ÇÑ´Ù.
struct attribute { char attrib[80]; float prob; /* probability associated with attribute */ struct attrubute *next; /* use linked list */ } at; |
¶ÇÇÑ prob ¶ó°í ÇÏ´Â ÃѰý º¯¼ö¸¦ ÷°¡ÇØ¾ß Çϴµ¥, ÀÌ º¯¼ö´Â ÇØ´äÀÌ ¿ÇÀ» È®·üÀ» °®´Â´Ù.
»ç¿ëÀÚ°¡ ´ë»ó¿¡ ´ëÇÑ °¢ ¼Ó¼ºÀ» ³ÖÀ» ¶§, ÇÁ·Î±×·¥Àº ¶ÇÇÑ ±× ¼Ó¼ºÀÌ Æ¯º°ÇÑ ´ë»ó¿¡ °ü·ÃµÇ´Â °¡´É¼ºÀ» ¹Ý¿µÇÏ´Â È®·ü¿ä¼Ò (probability factor) ¸¦ ÁÖµµ·Ï »ç¿ëÀÚ¿¡°Ô ¿ä±¸ÇÑ´Ù. ÀÌ ¿ä¼ÒÀÇ Àǹ̸¦ ÀÌÇØÇϱâ À§Çؼ, °¨±â¿Í °°ÀÌ º´À» ¹¦»çÇÏ´Â ¼Ó¼ºµéÀ» »ý°¢ÇØ º¸ÀÚ. ¸ðµç »ç¶÷ÀÌ ¶È°°Àº ½ÄÀ¸·Î °¨±â¸¦ ¾Î´Â °ÍÀº ¾Æ´Ï´Ù : ¾î¶² »ç¶÷µéÀº Ä๰ÀÌ ³ª°í, ¶Ç ¾î¶² »ç¶÷µéÀº Àçä±â¸¦ ÇÏ°í µîµî. °¨±âÀÇ Áõ»óÀ» Àü¹®°¡½Ã½ºÅÛÀÇ Áö½Äº£À̽º¿¡ ³ÖÀ¸¸é, ¹ß»ýÇÏ´Â °¢ Áõ»óÀÇ È®·üÀ» ³ªÅ¸³» ÁÖ¾î¾ß ÇÑ´Ù. ¿¹¸¦µé¾î, Ä๰ÀÌ ³ª´Â Áõ»ó¿¡ 90 % ÀÇ È®·üÀ» ÁÙ ¼ö ÀÖ´Ù. ¹Ý¸é¿¡ ¸ñÀÌ ¾ÆÇ Áõ»ó¿¡ 40 % ÀÇ È®·üÀ» ÁÙ ¼ö ÀÖ´Ù. ±×·¯¹Ç·Î enter() ÇÔ¼ö°¡ ¼Ó¼º°ú, °¢ ´ë»ó¿¡ °ü·ÃµÈ È®·üÀ» ¸ðµÎ ÀÔ·ÂÇϵµ·Ï ±×°ÍÀ» ¹Ù²Ù¾î¾ß ÇÑ´Ù.
/* input an object and its list of attributes */ enter() { int t, i; struct attribute *p, *oldp;
for (;;) { t=get_next(); /* get the index of the next available object in k_base */ if (t == -1) { printf("Out of list space.¡¬n"); return; } printf("Object name: "); gets(k_base[t].name);
if (!*k_base[t].name) { l_pos--; break; }
p=(struct attribute *) malloc(sizeof(at)); if (p=='¡¬0') { printf("Out of memory.¡¬n"); return; } k_base[t].alist=p; for (i=0;i<sizeof(p->attrib);i++) p->attrib[i]=' '; printf("Enter attributes (RETURN to quit)¡¬n"); for (;;) { printf("attribute : "); gets(p->attrib); if(!p->attrib[0]) break; printf("probability : (0-1): "); scanf("%f", &p->prob); getchar(); /* throw away crfl */ oldp=p; p->next=(struct attribute *) malloc(sizeof(at)); if (p->next == '¡¬0') { printf("Out of memory.¡¬n"); return; } p=p->next; p->next='¡¬0'; for (i=0;i<sizeof(p->attrib);i++) p->attrib[i]=' '; } oldp->next = '¡¬0'; } } |
Àü¹®°¡½Ã½ºÅÛ¿¡¼ ÇØ¾ß ÇÒ °áÁ¤ÀûÀÎ º¯°æÀº try() ¿Í trailno() °¡ ºÎÁ¤Àû ¹ÝÀÀÀ» ´Ù·ç´Â ¹æ¹ýÀÌ´Ù. 3 Àå¿¡¼ °³¹ßµÈ Ãʱ⠽ýºÅÛ¿¡¼ ºÎÁ¤Àû ¹ÝÀÀÀº Ç×»ó »ç¿ëÀÚ°¡ ÇöÀçÀÇ °¡Á¤À» °ÅÀýÇϰí ÀÖ´Ù´Â °ÍÀ» ³ªÅ¸³Â´Ù : ±×·¯³ª, È®·ü ½Ã½ºÅÛ¿¡¼ °ÅÀýÀº ±× ¼Ó¼ºÀ» ¹ß°ßÇÒ È®·üÀÌ ¹Ì¸® Á¤ÇØÁø ¾î¶² ¾çÀ» ÃʰúÇÒ ¶§¿¡¸¸ ¹ß»ýÇÒ °ÍÀÌ´Ù.
¿¹¸¦µé¾î, Ãʱ⠹öÀü¿¡¼ ¼Ó¼ºÀÇ ºÎÁ¤Àû ¹ÝÀÀÀ» ¹ÞÀ¸¸é ±× ¼Ó¼ºÀ» no µ¥ÀÌÅͺ£À̽º¿¡ ³õ°í, Ãß·ÐÀÇ ÇöÀç ¶óÀÎÀ» Ãë¼ÒÇÏ°í »õ·Î¿î ´ë»óÀÌ ½ÃµµµÇ°Ô Çß´Ù. ±×·¯³ª, ÀÌ »õ·Î¿î È®·ü ¹öÀüÀº ¿©ÀüÈ÷ ¼Ó¼ºÀ» no µ¥ÀÌÅͺ£À̽º¿¡ ³õÁö¸¸, Àý (clause) Àº ÀÌ ¼Ó¼ºÀ» ¹ß°ßÇÒ È®·üÀÌ 50 % ¸¦ ÃʰúÇÒ ¶§¿¡¸¸ ½ÇÆÐÇÒ °ÍÀÌ´Ù. (ÀÌ ºñÀ²Àº ÀÓÀÇ·Î ¼±ÅÃµÇ°í ¿øÇÑ´Ù¸é ¹Ù²Ü ¼ö ÀÖ´Ù). ÀÌ·± ½ÄÀ¸·Î, ÇÑ ´ë»ó°ú ¿¬°üµÉ ¼ö ÀÖ´Â ¼Ó¼ºµéÀº ±× ´ë»óÀÇ ¹¦»çÀÇ ÀϺθ¦ Çü¼ºÇÒ ¼ö ÀÖÁö¸¸, ±× ¼Ó¼ºÀ» ¹ß°ßÇÒ È®·üÀÌ ÃæºÐÈ÷ ³·À¸¸é, ±× ¼Ó¼ºÀ» °®Áö ¾Ê´Â´Ù°í ÇØ¼ ±× ´ë»óÀ» °ÅÀýÇÒ ¼ö´Â ¾ø´Ù. ¿©±â¿¡ º¯ÇüµÈ ÇÔ¼ö try() ¿Í trailno() °¡ Á¦½ÃµÈ´Ù :
/* try an object */ try(p, oob) struct attribute *p; char *ob; { char answer; struct attribute *a, *t;
if (!trailno(p, ob)) return 0;
if (!trailyes(p, ob)) return 0;
while(p) {
/* if already been asked then move oon to next attribute */ if (ask(p->attrib)) { printf("is/does/has it %s? ", p->attrib); answer=tolower(getche()); printf("¡¬n");
a=(struct attribute *) malloc(sizeof(at)); if (!a) { printf("out of memory¡¬n"); return ; } a->next='¡¬0'; switch(answer) { case 'n': strcpy(a->attrib, p->attrib); if (!no) { no=a; nonext=no; } else { nonext->next=a; nonext=a; } reject(ob, p->attrib, 'n'); /* reject if porb >= 50% */ if (p->prob>=0.5) return 0; case 'y': strcpy(a->attrib, p->attrib); if (!yes) { yes=a; yesnext=yes; } else { yesnext->next=a; yesnext=a; } compute_odds(p->prob); p=p->next; break; case 'w': /* why? */ reasoning(ob); break; } } else p=p->next; } return 1; }
/* see if it has any attributes known not to be part of the object by checking the no list */ trailno(p, ob) struct attribute *p; char *ob; { struct attribute *a, *t;
a=no; while(a) { t=p; while(t) { if (!strcmp(t->attrib, a->attrib)) { reject(ob, t->attrib, 'n'); if (t->prob>=0.5) return 0; /* reject only if high prob */ } t=t->next; } a=a->next; } return 1; } |
Àü¹®°¡°¡ ¿Ç´Ù°í ÆÇ´ÜÇÒ ÃÖÁ¾ È®·üÀ» °è»êÇÏ´Â »õ·Î¿î ·çƾ, compute-odds() °¡ ÇÊ¿äÇÒ °ÍÀÌ´Ù. ¿©±â¿¡ ÀÖ´Â ÇÔ¼ö´Â ÀüÅëÀûÀÎ È®·ü ¸ðµ¨À» °¡Á¤ÇÑ´Ù.
compute_odds(f) float f; { prob*=f; } |
compute-odds() ÇÔ¼ö´Â ÇöÀç ¼Ó¼º¿¡ ´ëÇÑ È®·üÀÌ Àü´ÞµÇ°í ÇØ¸¦ À§ÇÏ¿© È®·üÀ» update ÇÑ´Ù. È®·üÀû Àü¹®°¡½Ã½ºÅÛ Àüü°¡ ¿©±â¿¡ º¸¿©Áø´Ù. ÀÌÁ¦ ÄÄÇ»ÅÍ¿¡ ±×°ÍÀ» ÀÔ·ÂÇØ¾ß ÇÑ´Ù.
/* A probabilistic expert system that finds multiple goals and displays reasoning using classical probability theory */ #include "stdio.h" #incclude <malloc.h>
#define MAX 100 struct attribute { char attrib[80]; float prob; /* probability assoc with attribute */ struct attribute *next; /* use linked list */ } at;
struct object { char name[80]; struct attribute *alist; /* pointer to list of attributes */ } ob;
struct rejected_object { char name[80]; char attrib[80]; /* attribute that caused rejection */ char condition; /* should it or shouldn't it have been found ? */ } rj; struct rejected_object r_base[MAX];
struct object k_base[MAX]; /* holds the knowledge base */ int l_pos=-1; /* location of top of k_base */ int r_pos=-1; /* location of top of reject base */
struct attribute *yes, *no; /* used for yes and no lists */ struct attribute *yesnext, *nonext;
float prob; /* holds the probability of the current solution */
main() { char ch;
no=yes='¡¬0'; do { free_trails(); ch=menu(); switch(ch) { case 'e': enter (); break; case 'q': query(); break; case 's': save(); break; case 'l': load(); }
} while (ch != 'x'); }
free_trails() { struct attribute *p;
while(yes) { p=yes->next; free(yes); yes=p; }
while(no) { p=no->next; free(no); no=p; } r_pos=-1; }
/* input an object and its list of attributes */ enter() { int t, i; struct attribute *p, *oldp;
for (;;) { t=get_next(); /* get the index of the next available object in k_base */ if (t == -1) { printf("Out of list space.¡¬n"); return; } printf("Object name: "); gets(k_base[t].name);
if (!*k_base[t].name) { l_pos--; break; }
p=(struct attribute *) malloc(sizeof(at)); if (p=='¡¬0') { printf("Out of memory.¡¬n"); return; } k_base[t].alist=p; for (i=0;i<sizeof(p->attrib);i++) p->attrib[i]=' '; printf("Enter attributes (RETURN to quit)¡¬n"); for (;;) { printf("attribute : "); gets(p->attrib); if(!p->attrib[0]) break; printf("probability : (0-1): "); scanf("%f", &p->prob); getchar(); /* throw away crfl */ oldp=p; p->next=(struct attribute *) malloc(sizeof(at)); if (p->next == '¡¬0') { printf("Out of memory.¡¬n"); return; } p=p->next; p->next='¡¬0'; for (i=0;i<sizeof(p->attrib);i++) p->attrib[i]=' '; } oldp->next = '¡¬0'; } }
/* inquire information from the expert */ query() { int t; char ch; struct attribute *p; for (t=0;t<=l_pos;t++) { p=k_base[t].alist; prob=1,. 0; if (try(p, k_base[t].name)) { printf("%s fits current attributes¡¬n", k_base[t].name); printf("with probability factoor of %f¡¬n", prob); printf("continue? (Y/N): "); ch=tolower(getche()); printf("¡¬n"); if (ch=='n') return; } } printf("No (more) object(s) found¡¬n"); }
/* try an object */ try(p, ob) struct attribute *p; char *ob; { char answer; struct attribute *a, *t;
if (!trailno(p, ob)) return 0;
if (!trailyes(p, ob)) return 0;
while(p) { /* if already been asked then move on to next attribute */ if (ask(p->attrib)) { printf("is/does/has it %s? ", p->attrib); answer=tolower(getche()); printf("¡¬n");
a=(struct attribute *) malloc(sizeof(at)); if (!a) { printf("out of memory¡¬n"); return ; } a->next='¡¬0'; switch(answer) { case 'n': strcpy(a->attrib, p->attrib); if (!no) { no=a; nonext=n; } else { nonext->next=a; nonext=a; } reject(ob, p->attrib, 'n'); /* reject if porb >= 50% */ if (p->prob>=0.5) return 0; case 'y': strcpy(a->attrib, p->attrib); if (!yes) { yes=a; yesnext=yes; } else { yesnext->next=a; yesnext=a; } compute_odds(p->prob); p=p->next; break; case 'w': /* why? */ reasoning(ob); break; } } else p=p->next; } return 1; }
/* see if it has any attributes known not to be part of the object by checking the no list */ trailno(p, ob) struct attribute *p; char *ob; { struct attribute *a, *t;
a=no; while(a) { t=p; while(t) { if (!strcmp(t->attrib, a->attrib)) { reject(ob, t->attrib, 'n'); if (t->prob>=0.5) return 0; /* reject only if high prob */ } t=t->next; } a=a->next; } return 1; }
/* see if it has all attributes known to be part of the object by checking the yes list */ trailyes(p, ob) struct attribute *p; char *ob; { struct attribute *a, *t; char ok;
a=yes; while(a) { ok=0; t=p; while(t) { if (!strcmp(t->attrib, a->attrib)) { ok=1; /* does have a needed attribute */ compute_odds(t->prob); } t=t->next; } if (!ok) { reject(ob, a->attrib, 'y'); return 0; } a=a->next; } return 1; }
/* see if attribute already asked */ ask(attrib) char *attrib; { struct attribute *p, *q;
p=yes; while(p && strcmp(attrib, p->attrib)) p=p->next;
q=no; while(q && strcmp(attrib, q->attrib)) q=q->next;
if (q && q->prob<0.5) return 0; if (!p) return 1; /* false if end of list */ else return 0; }
/* show why a line of reasoning is being followed */ reasoning(ob) char *ob; { struct attribute *t; int i;
printf("Trying %s¡¬n", ob); if (yes) printf("it is/has/does:¡¬n"); t=yes; while(t) { printf("%s¡¬n", t->attrib); t=t->next; } if (no) printf('it is/has/does noot:¡¬n"); t=no; while(t) { printf("%s¡¬n", t-> attrib); t=t->next; }
for (i=0;i<=r_pos;i++) { printf("%s rejected because ", r_base[i].name); if (r_base[i].condition=='n') printf("%s is not an attribute.¡¬n", r_base[i].attrib); else printf("%s is a required attribute.¡¬n", r_base[i].attrib); } }
/* place rejected object into database */ reject(ob, at, cond) char *ob, *at, cond; { r_pos++;
strcpy(r_base[r_pos].name, ob); strcpy(r_base[r_pos].attrib, at); r_base[r_pos].condition=cond; }
/* get next free index in k_base array */ get_next() { l_pos++; if (l_pos<MAX) return l_pos; else return -1; }
menu() { char ch; printf("(E)nter, (Q)uery, (S)save, (L)oad, e(X)it¡¬n"); do { printf("choose one:"); ch=tolower(getche()); } while (!is_in(ch, "eqslx")); printf("¡¬n"); return ch; }
save() { int t, x; struct attribute *p; FILE *fp;
if ((fp=fopen("expert.dat", "w"))==0) { printf("cannot open file¡¬n"); return; } printf("saving knowledge base¡¬n"); for (t=0;t<=l_pos;++t) { for (x=0;x<sizeof(k_base[t].name);x++) putc(k_base[t].name[x], fp); p=k_base[t].alist; while(p) { for (x=0;x<sizeof(p->attrib);x++) putc(p->attrib[x], fp); fprintf(fp, "%f", p->prob); p=p->next; } /* end of list marker */ for (x=0;x<sizeof(p->attrib);x++) putc('¡¬0', fp); } putc(0, fp); fclose(fp); }
load() { int t, x; struct attribute *p, *oldp; FILE *fp;
if ((fp=fopen("expert.dat", "r"))==0) { printf("cannot open file¡¬n"); return; } printf("loading knowledge base¡¬n");
/* free any old lists */ clear_kbase(); for (t=0;t<MAX;++t) { if ((k_base[t].name[0]=getc(fp))==0) break; for (x=1;x<sizeof(k_base[t].name);x++) k_base[t].name[x]=getc(fp);
k_base[t].alist=(struct attribute *) malloc(sizeof(at)); p=k_base[t].alist; if(!p) { printf("Out of memory¡¬n"); return; } for (;;) { for (x=0;x<sizeof(p->attrib);x++) p->attrib[x]=getc(fp);
if (!p->attrib[0]) { oldp->next='¡¬0'; break; /* end of list */ } p->next=(struct attribute *) malloc(sizeof(at)); if (!p->next) { printf("out of memory¡¬n"); break; } fscanf(fp, "%f", &p->prob); oldp=p; p=p->next; } } fclose(fp); l_pos=t-1; } clear_kbase() { int t; struct attribute *p, *p2;
for (t=0;t<=l_pos;t++) { p=k_base[t].alist; while(p) { p2=p->next; free(p); p=p2;
} } }
is_in(ch, s) char ch, *s; { while(*s) if (ch==*s++) return 1; return 0; } compute_odds(f) float f; { prob*=f; } |
óÀ½ ÀÌ ÇÁ·Î±×·¥À» ¼öÇàÇÒ ¶§, ´ÙÀ½ Á¤º¸¸¦ ³Ö¾î¶ó.
´ë»ó ¼Ó¼º »ç°ú (apple) ½Ä¿ë 0.9, »¡°£»ö 0.4, ³ª¹«¿¡¼ ÀÚ¶÷ 1 ¿À·»Áö (orange) ½Ä¿ë 0.9, ¿À·»Áö»ö 0.9, ³ª¹«¿¡¼ ÀÚ¶÷ 1 °ÇÆ÷µµ (plum) ½Ä¿ë 0.8, º¸¶ó»ö 0.5, ³ª¹«¿¡¼ ÀÚ¶÷ 1 Æ÷µµ (grape) ½Ä¿ë 0.8, º¸¶ó»ö 0.5, ³ª¹«¿¡¼ ÀÚ¶÷ 0.01 |
Æ÷µµÀÇ ¹¦»ç¿¡¼, Áö½Äº£À̽º´Â Æ÷µµ°¡ ³ª¹«¿¡¼ ÀÚ¶ö °¡´É¼ºÀº 1 % »ÓÀ̶ó´Â »ç½ÇÀ» Æ÷ÇÔÇÑ´Ù. ÀÌ Ãß·ÐÀº Æ÷µµ°¡ ³ª¹«¿¡¼ ÀÚ¶õ´Ù´Â °ÍÀÌ ¾Æ´Ï´Ù - ¹°·Ð, ³ÕÄð¿¡¼ ÀÚ¶õ´Ù - ±×·¯³ª »ç¿ëÀÚ¿¡°Ô ¾ÆÁÖ Å« ³ÕÄðÀ» ³ª¹«·Î À߸ø ÀνÄÇÒ ±âȸ¸¦ Çã¿ëÇÑ´Ù. (±×¸®°í, ±× Á¡À» ¼³¸íÇÏ´Â µ¥¿¡ µµ¿òÀ» ÁØ´Ù !)
ÀÌ·¯ÇÑ Á¤º¸°¡ ÁÖ¾îÁ³À» ¶§, ¹ß»ýÇÒ ¼ö ÀÖ´Â ÇѰ¡Áö ´ëȰ¡ ¿©±â¿¡ ÀÖ´Ù :
is/has/does it edible ? y is/has/does it red ? y is/has/does it grew_on_tree ? y apple fits the current attributes with probability 0.36 continue ? n |
°¡´ÉÇÑ ¶Ç´Ù¸¥ ´ëȰ¡ ¿©±â ÀÖ´Ù :
is/has/does it edible ? y is/has/does it red ? n is/has/does it grew_on_tree ? y apple fits the current attributes with probability 0.36 continue ? y is/has/does it orange ? n is/has/does it purple ? y plum fits the current attributes with probability 0.4 continue ? y grape fits the current attributes with probability 0.04 continue ? n |
ù ¹øÂ° ´ëȰ¡ »êÃâµÈ ¹æ¹ýÀº, ¹ÝÀÀÀÌ ¸ðµÎ ±àÁ¤À̰í apple À» Á÷Á¢ °¡¸®Å°±â ¶§¹®¿¡ ½±´Ù. ¹®Á¦´Â ÀüÅëÀûÀÎ È®·ü ¸ðµ¨À» »ç¿ëÇÏ´Â Àü¹®°¡½Ã½ºÅÛÀÌ ÀÌ ÇØ°¡ ¿ÇÀ» È®·üÀº 36 % (1 * 0.4 * 0.9) ¸¸ Áشٴ °ÍÀÌ´Ù. ±×·¯³ª, À̰ÍÀº Ʋ¸° °Í °°´Ù - ±×¸®°í ½ÇÁ¦·Î Ʋ·È´Ù !
ÀüÅëÀûÀÎ È®·ü ¸ðµ¨Àº ÀÏ·ÃÀÇ »ç°ÇµéÀ» ´Ù·çµµ·Ï ¼³°èµÇ¾ú´Ù. ±×·¯³ª, Áö½Äº£À̽º¿¡¼ °¢ ¼Ó¼º°ú °ü·ÃµÈ È®·üÀº ´Ü¼øÈ÷ ¼Ó¼ºÀÌ Æ¯Á¤ÇÑ ´ë»ó°ú °ü·ÃµÇ´Â °¡´É¼ºÀÌ´Ù. ±×·¯¹Ç·Î, Áö½Äº£À̽º¿Í °ü·ÃµÈ È®½Ç¼º »ó¼ö (certainty coefficients) ´Â ÀüÅëÀûÀÎ È®·üÀÌ·ÐÀÇ ±â¹ýµéÀ» »ç¿ëÇÏ¿© ºÐ¼®µÉ ¼ö ¾ø´Ù. »ç½Ç, ÀüÅëÀûÀÎ È®·ü ¸ðµ¨À» »ç¿ëÇÏ´Â °ÍÀº ÀÌ»óÇÑ Àü¹®°¡½Ã½ºÅÛÀÌ´Ù.
µÎ ¹øÂ° ´ëÈ´Â Àü¹®°¡½Ã½ºÅÛÀÌ ¼Ó¼º ¸®½ºÆ®¿¡¼ °¡´ÉÇÑ »ý·«À» ÇØ°áÇϱâ À§ÇÏ¿© °¢ ¼Ó¼º°ú °ü·ÃµÈ È®·üÀ» »ç¿ëÇÒ ¼ö ÀÖ´Â ¹æ¹ýÀ» º¸¿©ÁØ´Ù. ´ë»óÀÌ »¡°£»öÀÎÁö¸¦ ¹¯´Â Áú¹®¿¡ »ç¿ëÀÚ°¡ ¾Æ´Ï¿À ¶ó°í ´ë´äÇÒ ¶§, ½Ã½ºÅÛÀº ±× ¹ÝÀÀÀ» no µ¥ÀÌÅͺ£À̽º¿¡ ÀúÀåÇÑ´Ù. ±×·¯³ª, »ç°ú°¡ »¡°£»öÀÏ È®·üÀº 40 % »Ó (³ë¶þ°Å³ª ÃÊ·Ï»öÀÏ ¼öµµ ÀÖ´Ù.) À̱⠶§¹®¿¡, ½Ã½ºÅÛÀº Ãß·ÐÀÇ ÀÌ ¶óÀÎÀ» ÁßÁöÇÏÁö ¾Ê´Â´Ù. ±×¸®°í³ª¼ ½Ã½ºÅÛÀº °¡´ÉÇÑ ÇØ·Î½á plum °ú grape ¸¦ °è¼Ó ¹ß°ßÇÑ´Ù.
¼º°øÀÇ È®·üÀÌ ³ªÅ¸³» ÁÖµíÀÌ, ÀüÅëÀûÀÎ È®·ü ¸ðµ¨À» Á¤º¸ÀÇ ºÒÈ®½Ç¼ºÀ» ÇØ°áÇÏ·Á°í Àû¿ë½Ãų ¶§ Àß µ¿ÀÛÇÏÁö ¾Ê´Â´Ù. ÀÌÁ¦ ÀÌ ¹®Á¦¸¦ ÇØ°áÇϱâ À§ÇÑ µÎ°¡Áö ´Ù¸¥, Á» ´õ ¼º°øÀûÀÎ ¹æ¹ýÀ» º¼ °ÍÀÌ´Ù.
È®½Ç¼º ¿ä¼Ò°¡ ƯÁ¤ÇÑ ¼Ó¼º°ú °ü·ÃµÉ ¶§, ±× ¼Ó¼ºÀÌ ¹®Á¦ÀÇ ´ë»óÀÇ ¿¹¿¡ ¼ÓÇÒ º°°³ÀÇ °¡´É¼ºÀÌ ÀÖ´Ù´Â °ÍÀ» ÀǹÌÇÑ´Ù. ±×·¯¹Ç·Î, ÇѰ¡Áö ¹æ½ÄÀº, ¾î¶² ÇØÀÇ È®½Ç¼ºÀº ±× ´ë»ó°ú °ü·ÃµÈ ÃÖ¼ÒÀÇ È®½Ç¼º »ó¼öÀ̾î¾ß ÇÑ´Ù´Â °ÍÀ» ¾Ï½ÃÇÑ´Ù. ÀÌ °³³äÀº °¡Àå ¾àÇÑ ¿¬°á (weakest link) ¸¸Å °ÇÑ Ã¼Àΰú À¯»çÇÏ´Ù.
È®½ÇÇÑ Àü¹®°¡½Ã½ºÅÛÀ¸·Î ÇÏ¿©±Ý ÀÌ·± ¹æ½ÄÀ¸·Î ºÒÈ®½Ç¼ºÀ» ÇØ°áÇÏ°Ô ÇÏ´Â °ÍÀº ¿©±â¿¡ ÀÖ´Â °Íó·³, compute_prob() ÇÔ¼ö·ÎÀÇ º¯È¸¸À» ¿ä±¸ÇÑ´Ù.
/* compute the probability of a solution */ /* weakest-link method */ compute_prob(f) float f; { if (prob>f) prob=f; } |
ÀÌ ¹öÀü¿¡¼, ÃÖÇÏÀÇ È®½Ç¼º ¿ä¼Ò°¡ Àüü ÇØ°¡ ¿ÇÀ» È®·üÀÌ µÈ´Ù. Àü¹®°¡½Ã½ºÅÛ¿¡¼ ÀÌ ÇÔ¼ö¸¦ ´ëüÇϸé, »ý¼ºµÉ ¼ö ÀÖ´Â ´ëÈ´Â ´ÙÀ½ÀÌ´Ù :
is/has/does it edible ? y is/has/does it red ? y is/has/does it grew_on_tree ? y apple fits the current attributes with probability 0.4 continue ? n |
»ý¼ºµÉ ¼ö ÀÖ´Â ¶Ç ´Ù¸¥ ´ëȰ¡ ¿©±âÀÖ´Ù :
is/has/does it edible ? y is/has/does it red ? n is/has/does it grew_on_tree ? y apple fits the current attributes with probability 0.4 continue ? y is/has/does it orange ? n is/has/does it purple ? y plum fits the current attributes with probability 0.5 continue ? y grape fits the current attributes with probability 0.2 continue ? n |
¾Ë ¼ö ÀÖµíÀÌ, ÇØ´Â °°Áö¸¸ È®·üÀÌ ¹Ù²î¾ú´Ù - ÀÌ °æ¿ì¿¡, ³ô¾ÆÁ³´Ù. °¡Àå ¾àÇÑ ¿¬°á ¹æ¹ýÀÇ ÁÖ¿äÇÑ ÀåÁ¡Àº, ´ë»ó°ú °ü·ÃµÈ ¸ðµç ¼Ó¼ºµéÀÌ »óÈ£ÀÇÁ¸ÀûÀÎ °Íó·³ : Áï, ÇØÀÇ °¡´É¼ºÀÌ ¿ä¼ÒµéÀÇ Á¶ÇÕ¿¡ ±âÃÊÇÏ´Â °Íó·³, ¼º°øÀÇ È®·üÀ» Áشٴ °ÍÀÌ´Ù. ÇÑÆí, °¡Àå °·ÂÇÑ ³íÀǰ¡ °¡Àå ¾àÇÑ ¿¬°áº¸´Ù ´õ Áß¿äÇÏ°Ô µÇ´Â »óȲµéÀÌ ÀÖ´Ù. ÀÌ·¯ÇÑ »óȲµéÀº °¡Àå °ÇÑ ¿¬°á (strongest-link) ¹æ½ÄÀ» ¿ä±¸ÇÑ´Ù.
¾î¶² ÀÀ¿ë¿¡¼, ÇØ°¡ ¿ÇÀ» È®·üÀº °¡Àå ¾àÇÑ Áö¿ø Áõ°Å¿¡ ÀÇÁ¸ÇÏ´Â °ÍÀÌ ¾Æ´Ï¶ó, ¿ÀÈ÷·Á °¡Àå °ÇÏ°Ô Áö¿øÇÏ´Â Áõ°Å¿¡ ±âÃʸ¦ µÐ´Ù. À̰ÍÀº ÇѰ¡Áö ³íÀǸ¸À¸·Î ÀïÁ¡À» °áÁ¤Çϱ⿡ ÃæºÐÇÑ ±×·± ³íÀï°ú ºñ½ÁÇÏ´Ù. ¿¹¸¦µé¾î, ź¾àÀ» ÀåÀüÇÑ ÃÑÀ» ¾ÆÀ̵éÀÌ ¹ß°ßÇÒ ¼ö ÀÖ´Â °÷¿¡ µÎ´Â °ÍÀÌ ¿Ö ³ª»Û°¡? ¾ÆÀ̰¡ ÃÑÀ» ½÷¼ ½Ã²ô·´°í È¥¶õ½º·¯¿î ¼Ò¸®¸¦ ³¾ ¼ö Àִٵ簡, ¾ÆÀ̰¡ ÃÑÀ» ½÷¼ Àç»ê¿¡ ¼ÕÇØ¸¦ ÀÔÈú ¼ö ÀÖ´Ù´Â °Í°ú °°Àº ¿©·¯ °¡Áö ÀÌÀ¯°¡ ÀÖ´Ù. ±×·¯³ª °¡Àå °·ÂÇÑ ³íÀÇ´Â, ¾ÆÀ̰¡ ÃÑÀ» ½÷¼ ´©±º°¡ »óó¸¦ ÀÔÈ÷°Å³ª Á×ÀÏ ¼ö ÀÖ´Ù´Â °ÍÀÌ´Ù. ºÐ¸íÈ÷, °¡Àå °·ÂÇÑ ³íÀǰ¡ µÇ´Â ÃÖÈÄÀÇ °ÍÀÌ´Ù.
Àü¹®°¡½Ã½ºÅÛ¿¡ Àû¿ëµÉ ¶§, °¡Àå °ÇÑ ¿¬°á (strongest-link) ¹æ¹ýÀº ´Ü¼øÈ÷, ÇØ°¡ ¿ÇÀ» È®·üÀº ¹ß»ýÇÒ °¡´É¼ºÀÌ °¡Àå Å« ¼Ó¼ºÀÇ È®·ü°ú °°´Ù´Â °ÍÀ» ÀǹÌÇÑ´Ù. ÀÌ ¹æ½ÄÀ» ±¸ÇöÇϱâ À§Çؼ, ¾Æ·¡¿¡ ÀÖ´Â °Íó·³ compute_prob() ÇÔ¼ö¸¦ º¯ÇüÇØ¾ß ÇÑ´Ù :
/* compute the probability of a solution */ /* strongest-link method */ compute_prob(f) float f; { if (prob<f) prob=f; } |
ÀÌ º¯È À̿ܿ¡, try() ¿¡ ÀÖ´Â, prob ÀÇ ÃʱⰪÀ» 1 ¿¡¼ 0 À¸·Î ¹Ù²Ù¾î¾ß ÇÑ´Ù. ÀüÅëÀûÀÎ È®·ü ¸ðµ¨°ú °¡Àå ¾àÇÑ ¿¬°á ¹æ¹ý¿¡¼ »ç¿ëµÈ´Ù. È¥µ¿À» ÇÇÇϱâ À§ÇÏ¿©, strongest-link Àü¹®°¡½Ã½ºÅÛ Àüü°¡ ¿©±â¿¡ º¸¿©Áø´Ù.
/* A probabilistic expert system that finds multiple goals and displays reasoning using the strongest link approach */
#include "stdio.h" #include <malloc.h>
#define MAX 100 struct attribute { char attrib[80]; float prob; /* probability assoc with attribute */ struct attribute *next; /* use linked list */ } at;
struct object { char name[80]; struct attribute *alist; /*pointer to list of attributes */ } ob;
struct rejected_object { char name[80]; char attrib[80]; /* attribute that caused rejection */ char condition; /* should it or shouldn't it have been found ? */ } rj; struct rejected_object r_base[MAX];
struct object k_base[MAX]; /* holds the knowledge base */ int l_pos=-1; /* location of top of k_base */ int r_pos=-1; /* location of top of reject base */
struct attribute *yes, *no; /* used for yes and no lists */ struct attribute *yesnext, *nonext;
float prob; /* holds the probability of the current solution */ main() { char ch;
no=yes='¡¬0'; do { free_trails(); ch=menu(); switch(ch) { case 'e': enter(); break; case 'q': query(); break; case 's': save(); break; case 'l': load(); }
} while (ch != 'x'); }
free_trails() { struct attribute *p;
while(yes) { p=yes->next; free(yes); yes=p; }
while(no) { p=no->next; free(no); no=p; } r_pos=-1; }
/* input an object and its list of attributes */ enter() { int t, i; struct attribute *p, *oldp;
for (;;) { t=get_next(); /* get the index of the next available object in k_base */ if (t == -1) { printf("Out of list space.¡¬n"); return; } printf("Object name: "); gets(k_base[t].name);
if (!*k_base[t].name) { l_pos--; break; }
p=(struct attribute *) malloc(sizeof(at)); if (p=='¡¬0') { printf("Out of memory.¡¬n"); return; } k_base[t].alist=p; for (i=0;i<sizeof(p->attrib);i++) p->attrib[i]=' '; printf("Enter attributes (RETURN to quit)¡¬n"); for (;;) { printf("attribute : "); gets(p->attrib); if(dp->attrib[0]) break; printf("probability : (0-1): "); scanf("%f", &p->prob); getchar(); /* throw away crfl */ oldp=p; p->next=(struct attribute *) malloc(sizeof(at)); if (p->next == '¡¬0') { printf("Out of memory.¡¬n"); return; } p=p->next; p->next='¡¬0'; for (i=0;i<sizeof(p->attrib);i++) p->attrib[i]=' '; } oldp->next = '¡¬0'; } }
/* inquire information from the expert */ query() { int t; char ch; struct attribute *p; for (t=0;t<=l_pos;t++) { p=k_base[t].alist; prob=0.0; /* strongest length initial point */ if (try(p, k_base[t].name)) { printf("%s fits current description¡¬n", k_base[t].name); printf("with probability factor of %f¡¬n", prob); printf("coontinue? (Y/N): "); ch=tolower(getche()); printf("¡¬n"); if (ch=='n') return; } } printf("No (more) object(s) found¡¬n"); }
/* try an object */ try(p, ob) struct attribute *p; char *ob; { char answer; struct attribute *a, *t;
if (!trailno(p, ob)) return 0;
if (!trailyes(p, ob)) return 0;
while(p) { /* if already been asked then move on to next attribute */ if (ask(p->attrib)) { printf("is/does/has it %s? ", p->attrib); answer=tolower(getche()); printf("¡¬n");
a=(struct attribute *) malloc(sizeof(at)); if (!a) { printf("out of memory¡¬n"); return ; } a->next='¡¬0'; switch(answer) { case 'n': strcpy(a->attrib, p->attrib); if (!no) { no=a; nonext=no; } else { nonext->next=a; nonext=a; } reject(ob, p->attrib, 'n'); /* reject if prob >= 50% */ if (p->prob>=0.5) return 0; case 'y': strcpy(a->attrib, p->attrib); if (!yes) { yes=a; yesnext=yes; } else { yesnext->next=a; yesnext=a; } compute_prob(p->prob); p=p->next; break; case 'w': /* why? */ reasoning(ob); break; } } else p=p->next; } return 1; }
/* see if it has any attributes known not to be part of the object by checking the no list */ trailno(p, ob) struct attribute *p; char *ob; { struct attribute *a, *t;
a=no; while(a) { t=p; while(t) { if (!strcmp(t->attrib, a->attrib)) { reject(ob, t->attrib, 'n'); if (t->prob>=0.5) return 0; /* reject only if high prob */ } t=t->next; } a=a->next; } return 1; }
/* see if it has all attributes known to be part of the object by checking the yes list */ trailyes(p, ob) struct attribute *p; char *ob; { struct attribute *a, *t; char ok;
a=yes; while(a) { ok=0; t=p; while(t) { if (!strcmp(t->attrib, a->attrib)) { ok=1; /* dooes have a needed attribute */ compute_prob(t->prob); } t=t->next; } if (!ok) { reject(ob, a->attrib, 'y'); return 0; } a=a->next; } return 1; }
/* see if attribute already asked */ ask(attrib) char *attrib; { struct attribute *p, *;
p=yes; while(p && strcmp(attrib, p->attrib)) p=p->next;
q=no; while(q && strcmp(attrib, q->attrib)) q=q->next;
if (q && q->prob<0.5) return 0; if (!p) return 1; /* false if end of list */ else return 0; }
/* show why a line of reasoning is being followed */ reasoning(ob) char *ob; { struct attribute *t; int i;
printf("Trying %s¡¬n", ob); if (yes) printf("it is/has/does:¡¬n"); t=yes; while(t) { printf("%s¡¬n", t->attrib); t=t->next; } if (no) printf("it is/has/does not:¡¬n"); t=no; while(t) { printf("%s¡¬n", t->attrib); t=t->next; }
for (i=0;i<r-pos;i++) { printf("%s rejected because ", r_base[i].name); if (r_base[i].condition=='n') printf("%s is not an attribute.¡¬n", r_base[i].attrib); else printf("%s is a required attribute.¡¬n", r_base[i].attrib); } }
/* place rejected object into database */ reject(ob, at, cond) char *ob, *at, cond; { r_pos++;
strcpy(r_base[r_pos].name, ob); strcpy(r_base[r_pos].attrib, at); r_base[r_pos].condition=cond; }
/* get next free index in k_base array */ get_next() { l_pos++; if (l_pos<MAX) return l_pos; else return -1; }
menu() { char ch; printf("(E)nter, (Q)uery, (S)save, (L)oad, e(X)it¡¬n"); do { printf("choose one:"); ch=tolower(getche()); } while (!is_in(ch, "eqslx")); printf("¡¬n"); return ch; }
save() { int t, x; struct attribute *p; FILE *fp;
if ((fp=fopen("expert.dat", "w"))==0) { printf("cannot open file¡¬n"); return; } printf("saving knowledge base¡¬n"); for (t=0;t<=l_pos;++t) { for (x=0;x<sizeof(k_base[t].name);x++) putc(k_base[t].name[x], fp); p=k_base[t].alist; while(p) { for (x=0;x<sizeof(p->attrib);x++) putc(p->attrib[x], fp); fprintf(fp, "%f", p->prob); p=p->next; } /* end of list market */ for (x=0;x<sizeof(p->attrib);x++) putc('¡¬0', fp); } putc(0, fp); fclose(fp); }
load() { int t, x; struct attribute *p, *oldp; FILE *fp;
if ((fp=fopen("expert.dat", "r"))==0) { printf("cannot open file¡¬n"); return; } printf("loading knowledge base¡¬n");
/* free any old lists */ clear_kbase(); for (t=0;t<MAX;++t) { if ((k_base[t].name[0]=getc(fp))==0) break; for (x=1;x<sizeof(k_base[t].name);x++) k_base[t].name[x]=getc(fp); k_base[t].alist=(struct attribute *) malloc(sizeof(at)); p=k_base[t[.alist; if(!p) { printf("Out of memory¡¬n"); return } for (;;) { for (x=0;x<sizeof(p->attrib);x++) p->attrib[x]=getc(fp); if (!p->attrib[0]) { oldp->next='¡¬0'; break; /* end of list */ } p->next=(struct attribute *) malloc(sizeof(at)); if (!p->next) { printf("out of memory¡¬n"); break; } fscanf(fp, "%f", &p->prob); oldp=p; p=p->next; } } fclose(fp); l_pos=t-1; }
clear_kbase() { int t; struct attribute *p, *p2;
for (t=0;t<=l_pos;t++) { p=k_base[t].alist; while(p) { p2=p->next; free(p); p=p2;
} } }
is_in(ch, s) char ch, *s; { while(*s) if (ch==*s++) return 1; return 0; }
/* compute the probability of a solution */
/* strongest-link mithod */ compute_prob(f) float f; { if (prob<f) prob=f; } |
ÀÌ ¹öÀüÀ» ¼öÇàÇÒ ¶§, apple °ú plum ¿¡ ´ëÇÑ È®½Ç¼º ¿ä¼Ò´Â 1 ÀÌ µÈ´Ù. grape ¿¡ ´ëÇÑ È®½Ç¼º ¿ä¼Ò´Â 0.8 ÀÌ´Ù.
ÀüÅëÀûÀÎ È®·ü ¹æ¹ýÀº, °¡¼³Àû Á¤º¸¸¦ »ç¿ëÇÏ¿© ¾î¶² »ç°ÇµéÀÇ È®·üÀ» ¿¹ÃøÇÒ Àü¹®°¡½Ã½ºÅÛ°ú °°Àº »ö´Ù¸¥ »óȲ¿¡¼¸¸ ÀÀ¿ëÇÒ ¼ö ÀÖ´Ù. ¿¹¸¦µé¾î, »ç°ÇµéÀÌ ´Þ¶ú´Ù¸é ¿ª»çÀûÀÎ »óȲÀÇ ¿©·¯ °¡Áö Ãâ·ÂµéÀÇ È®·üÀ» ÁÙ Àü¹®°¡½Ã½ºÅÛÀ» ¼³°èÇÒ ¼ö ÀÖ´Ù. ±×·¯³ª, ÀÌ·¯ÇÑ Á¾·ù¿¡¼ »ç¿ëÇÏ´Â °Í ¿Ü¿¡, ÀüÅëÀûÀÎ È®·ü ¸ðµ¨Àº Áö½Äº£À̽º ½Ã½ºÅÛ (knowledge-based systems) ¿¡¼ Àß µ¿ÀÛÇÏÁö ¾Ê´Â´Ù.
¸ðµç ¼Ó¼ºµéÀÇ Á¶ÇÕÀ» »ý°¢ÇØ¾ß ÇÒ ¶§´Â weakest-link ¹öÀüÀ» »ç¿ëÇØ¾ß ÇÑ´Ù. ÀÌ °æ¿ì¿¡, »ç¿ëÀÚ¿¡°Ô ÃÖ¾ÇÀÇ °æ¿ì (worst case) °¡ ¹«¾ùÀÎÁö¸¦ ¾Ë·Á¾ß ÇÑ´Ù. Áö½Äº£À̽º°¡ Àû´çÈ÷ Á¤ÀǵǸé ÃÖ¾ÇÀÇ °æ¿ì¿¡ ´ëÇÑ È®·üÀº ¿©ÀüÈ÷ ¸Å¿ì ³ôÀ» °ÍÀÌ´Ù.
¾î¶² ´ë»óÀ» ¸í½Ã (identify) Çϱâ À§Çؼ ¾î¶² ¼Ó¼ºÀÌ¶óµµ »ç¿ëÇÒ ¼ö ÀÖÀ» ¶§´Â ¾ðÁ¦³ª strongest-link ¹æ½ÄÀ» ½á¾ß ÇÑ´Ù. ÀÌ °æ¿ì¿¡, È®½Ç¼º ¿ä¼Ò´Â °¡Àå °·ÂÇÑ ³íÀÇÀÇ °¡´É¼ºÀ» ¹Ý¿µÇÑ´Ù.