¼­¼ú ³í¸®¸¦ ÀÌ¿ëÇÑ Áö½ÄÀÇ Ç¥±â

 

ÀΰøÁö´É : Elaine Rich Àú¼­, À¯¼®ÀÎ.ÀüÁÖ½Ä.ÇÑ»ó¿µ Æí¿ª, »óÁ¶»ç, 1986 (¿ø¼­ : Artificial Intelligence, McGraw-Hill, 1983,  Artificial Intelligence (2nd ed, 1991)), Page 145~185

 

1. Áö½ÄÀÇ Ç¥±â

2. ³í¸® ±âÈ£¿¡ ÀÇÇÑ »ç½ÇÀÇ Ç¥±â

3. °è»ê °¡´ÉÇÑ ÇÔ¼ö¿Í ¼ú¾îÇü ¸íÁ¦¿¡ ÀÇÇÑ Áö½ÄÀÇ Ç¥±â

4. ºñ±³ Èí¼ö ¹æ¹ý (Resolution)

     (1) ÀýÀÇ ÇüÅ (Clause Form) ·Î º¯È¯

     (2) ºñ±³ Èí¼ö °úÁ¤ÀÇ ±âº» ¿ø¸®

     (3) ¸íÁ¦ ³í¸®¿¡¼­ÀÇ ºñ±³ Èí¼ö ¹æ¹ý

     (4) ´ÜÀÏÈ­ ¾Ë°í¸®Áò (Unification Algorithm)

     (5) ¼­¼ú ³í¸®¿¡¼­ÀÇ ºñ±³ Èí¼ö ¹æ¹ý

     (6) ¿©·¯ ġȯÀÇ ¼öÇà

     (7) Áú¹®¿¡ ´äÇϱâ

5. ¿¬¿ª¹ý (Natural Deduction)

6. ¿ä¾à

7. ¿¬½À¹®Á¦

 

 

1. Áö½ÄÀÇ Ç¥±â

Àΰø Áö´É ºÐ¾ß¿¡ ¼ÓÇÏ´Â º¹ÀâÇÑ ¹®Á¦¸¦ Ç®±â À§Çؼ­´Â ¸¹Àº ¾çÀÇ Áö½ÄÀÌ ÇÊ¿äÇϸç, ¶ÇÇÑ ÀÌ Áö½ÄÀ» ó¸®ÇÏ´Â ±â¹ýÀ» »ç¿ëÇÏ¿© »õ·Î¿î ¹®Á¦¿¡ ´ëÇÑ Ç®À̸¦ ¾òÀ» ¼ö ÀÖ´Ù.

Ž»öÀ» ¹ÙÅÁÀ¸·Î ÇÏ¿© Áö½ÄÀ» ó¸®ÇÏ´Â ¸Å¿ì ÀϹÝÀûÀÎ ¹æ¹ý¿¡ °üÇÏ¿© Áö±Ý±îÁö ¾Ë¾Æº¸¾Ò´Ù. ÀÌ ¹æ¹ýÀº ¹®Á¦¸¦ Ǫ´Âµ¥ »ç¿ëµÉ Áö½ÄÀÇ Ç¥±â ¹æ¹ý¿¡ ´ëÇؼ­´Â ¾ð±ÞÇÒ ÇÊ¿ä°¡ ¾øÀ» ¸¸Å­ ¸Å¿ì ÀϹÝÀûÀÎ ¹æ¹ýÀ̾ú´Ù. ¿¹¸¦ µé¾î, A* ¾Ë°í¸®Áò¿¡¼­´Â ¹®Á¦ ¿µ¿ª¿¡ Ư¼öÇÑ Áö½Ä¿¡ ´ëÇØ ³íÀÇÇÏÁö ¾Ê°íµµ ÈÄ°è ³ëµå¸¦ ¸¸µé°í, ÇÔ¼ö h' ÀÇ °ªÀ» °è»êÇÒ ¼ö ÀÖ¾ú´Ù. ºñ·Ï ÀÌ·¸°Ô Áö½ÄÀÇ Ç¥±â ¹æ¹ý¿¡´Â ¹«°üÇÑ Ç®ÀÌ ±â¹ýÀ» »ç¿ëÇÏ¿©, ´Ù¾çÇÑ ¿©·¯ °¡Áö ¹®Á¦¸¦ ÀûÀýÈ÷ Ç® ¼ö ÀÖ°í, ¸¹Àº ¹®Á¦ Ç®ÀÌ ¹æ¹ýÀÇ ±âÃʸ¦ ÀÌ·ê ¼ö ÀÖÁö¸¸, ¹Ù·Î ÀÌ·¯ÇÑ ÀϹݼº ¶§¹®¿¡ À̵éÀÇ »ç¿ë ¹üÀ§´Â ¸Å¿ì Á¦ÇѵǾî ÀÖ´Ù. Áö½ÄÀÇ Ç¥±â ¹æ¹ý¿¡ µû¶ó Ư¼öÇÑ Áö½ÄÀ» Ç¥±âÇÏ´Â ¸ðµ¨À» »ç¿ëÇÏ¿©, ÀÌ ¸ðµ¨¿¡ ÀÛ¿ëÇÏ´Â »ó´çÈ÷ Ư¼öÇÏ°í °­·ÂÇÑ Ãß·Ð ±â¹ýÀ» ¾ò¾î ¹®Á¦¸¦ Ç® ¼ö ÀÖ´Ù.

Àΰø Áö´É ºÐ¾ßÀÇ ÇÁ·Î±×·¥¿¡¼­´Â, Áö½ÄÀ̳ª »ç½ÇÀ» Ç¥±âÇϱâ À§ÇØ ¿©·¯ ¸¹Àº ±â¹ýµéÀÌ »ç¿ëµÈ´Ù. ±×·¯³ª ÀÌ ±â¹ýµéÀ» ³íÀÇÇϱ⿡ ¾Õ¼­, Áö½ÄÀ» Ç¥±âÇÒ ¶§ ¾ð±ÞµÇ´Â ´ÙÀ½ »çÇ׿¡ ´ëÇØ »ìÆì º¸¾Æ¾ß ÇÑ´Ù :

Ç¥±âµÈ »ç½ÇÀ» ¹®Á¦ Ç®ÀÌ¿¡ »ç¿ëÇϱâ À§Çؼ­´Â, »ç½ÇÀ» Ç¥±âµÈ »ç½Ç·Î ´ëÀÀ½ÃÅ°°í, Ç¥±âµÈ »ç½ÇÀ» »ç½Ç·Î ´ëÀÀ½Ãų ÇÔ¼ö°¡ ÀÖ¾î¾ß ÇÑ´Ù.

»ç½ÇÀ» Ç¥±âÇϱâ À§ÇØ °¡Àå ³Î¸® ¾²ÀÌ´Â ÇÑ °¡Áö ¹æ¹ýÀº ÀÚ¿¬ ¾ð¾î (natural language) ·Î Ç¥±âµÈ ¹®ÀåÀÌ´Ù. ÇÁ·Î±×·¥¿¡¼­ »ç¿ëµÉ »ç½ÇÀÇ Ç¥±â¹ý°ú´Â °ü°è¾øÀÌ ½Ã½ºÅÛ¿¡ ½±°Ô Á¤º¸¸¦ ÀÔ·ÂÇÏ°í, »ç¿ëÇϱâ À§Çؼ­ »ç½ÇÀ» Ç¥±âÇÏ´Â ÀÚ¿¬ ¾ð¾î¿¡ ´ëÇØ ¾Ë¾Æ º¼ ÇÊ¿ä°¡ ÀÖ´Ù. ÀÌ °æ¿ì, ¹®ÀåÀ» ½ÇÁ¦·Î »ç¿ëµÉ Ç¥±â·Î, Ç¥±âµÈ »ç½ÇÀ» ´Ù½Ã ¹®ÀåÀ¸·Î ´ëÀÀ½Ãų ÇÔ¼ö°¡ ÀÖ¾î¾ß ÇÑ´Ù.

¼öÇÐÀû ³í¸®¸¦ »ç¿ëÇÏ¿© »ç½ÇÀ» Ç¥±âÇÑ °£´ÜÇÑ ¿¹¸¦ »ìÆì º¸ÀÚ. ´ÙÀ½°ú °°Àº ¿µ¾î ¹®ÀåÀÌ ÀÖ´Ù :

    Spot is a dog. (½ºÆÌÀº °­¾ÆÁöÀÌ´Ù.)

ÀÌ ¹®ÀåÀ» ³í¸® Çü½ÄÀ» »ç¿ëÇÏ¿©

    Dog (Spot)

À̶ó Ç¥±âÇÒ ¼ö ÀÖ´Ù. ¸ðµç °³°¡ ²¿¸®¸¦ °¡Áö°í ÀÖÀ½À» Ç¥±âÇϱâ À§ÇØ, ³í¸®ÀÇ ¿¬¿ª Ãß·Ð ±â¹ýÀ» »ç¿ëÇÏ¿©

    Hastail (Spot)

À̶ó°í ÀÌ »ç½ÇÀ» Ç¥±âÇÒ ¼ö ÀÖ´Ù. À̶§ ÀûÀýÇÑ ´ëÀÀ ÇÔ¼ö¸¦ »ç¿ëÇÏ¿©, ÀÌ¿¡ ´ëÀÀÇÏ´Â ¿µ¾î ¹®Àå,

    Spot  has a tail (½ºÆÌÀº ²¿¸®¸¦ °¡Áö°í ÀÖ´Ù.)

À» ¾òÀ» ¼ö ÀÖ´Ù. ȤÀº »õ·Ó°Ô Ç¥±âµÈ »ç½ÇÀ» ÀÌ¿ëÇÏ¿©, ÇÊ¿äÇÑ ¾î¶² ÇൿÀ» ÀûÀýÈ÷ ÃëÇÒ ¼ö ÀÖ´Ù. ±×¸² 1 Àº ¼¼ Á¾·ùÀÇ ´ë»óÀÌ ¼­·Î ¾î¶»°Ô °ü·ÃµÇ¾î ÀÖ´ÂÁö¸¦ º¸¿© ÁØ´Ù.

±×¸² 1  »ç½Ç°ú Ç¥±â °£ÀÇ ´ëÀÀ

ÀϹÝÀûÀ¸·Î ÀÌ¿ë °¡´ÉÇÑ ´ëÀÀ ÇÔ¼ö´Â ÀÏ ´ë ÀÏ ´ëÀÀÀÌ ¾Æ´Ï¶ó, »ç½Ç»ó À̵éÀº ÇÔ¼ö¶ó±âº¸´Ù ´Ù ´ë ´Ù °ü°è (many-to-many relation) ¶ó º¼ ¼ö ÀÖ´Ù (Áï, Á¤ÀÇ ±¸¿ª¿¡ ¼ÓÇÏ´Â °¢ ¿ø¼Ò°¡ °øº¯¿ª ³»ÀÇ ¿©·¯ ¿ø¼Ò¿¡ ´ëÀÀÇϸç, Á¤ÀÇ ±¸¿ª¿¡ ¼ÓÇÏ´Â ¿©·¯ ¿ø¼Ò°¡ °øº¯¿ª ³»ÀÇ ÇÑ ¿ø¼Ò¿¡ ´ëÀÀÇÑ´Ù). ÀÌ°ÍÀº ƯÈ÷ ÁÖ¾îÁø ¾î¶² »ç½ÇÀ» ¿µ¹®À¸·Î Ç¥±âÇßÀ» ¶§ ¹ß»ýÇÑ´Ù. ¿¹¸¦ µé¾î ¹®Àå "All dog have tails" ¿Í ¹®Àå "Every dog has tail" Àº °°Àº »ç½ÇÀ» ³ªÅ¸³½´Ù. ¹Ý¸é ÀüÀÚ´Â ¸ðµç °³°¡ Àû¾îµµ ÇϳªÀÇ ²¿¸®¸¦ °¡Á³´Ù´Â »ç½ÇÀ̳ª, ȤÀº ÇÑ ¸¶¸®ÀÇ °³°¡ ¿©·¯ °³ÀÇ ²¿¸®¸¦ °¡Á³´Ù´Â »ç½ÇÀ» ³ªÅ¸³½´Ù. ¾ÕÀÇ °£´ÜÇÑ ¿¹¿¡¼­ ¾Ë ¼ö ÀÖµíÀÌ, ¿µ¾î ¹®ÀåÀ» ³í¸® ¸íÁ¦¿Í °°Àº ´Ù¸¥ Ç¥±â¹ýÀ» »ç¿ëÇÏ¿© ¹Ù²Ù¾î Ç¥ÇöÇϱâ À§Çؼ­´Â ¹®ÀåÀÌ ¾î¶² »ç½ÇÀ» ³ªÅ¸³»´ÂÁö °áÁ¤ÇÑ ÈÄ, ÀÌ »ç½ÇÀ» ÀûÁ¤ÇÑ Çü½ÄÀ» »ç¿ëÇÏ¿©, ¹®Á¦¸¦ Ç® ¶§ Á÷Á¢ ó¸®µÉ ¼ö ÀÖµµ·Ï Ç¥±âµÈ ÇüÅ·Π¹Ù²Ù¾î Ç¥ÇöÇØ¾ß ÇÑ´Ù.

2. ³í¸® ±âÈ£¿¡ ÀÇÇÑ »ç½ÇÀÇ Ç¥±â

³í¸® ±âÈ£¸¦ »ç¿ëÇÏ¿© »ç½ÇÀ» Ç¥±âÇÒ ¼ö Àִµ¥, ³í¸® Çü½Ä·Ð¿¡¼­´Â, ¼öÇÐÀû ¿¬¿ª Ãß·Ð ±â¹ýÀ» ÀÌ¿ëÇÏ¿© ÀÌ¹Ì Á¸ÀçÇÏ´Â »ç½Ç·ÎºÎÅÍ »õ·Î¿î »ç½ÇÀ» À̲ø¾î³½´Ù. ³í¸® Çü½ÄÀ¸·Î Ç¥±âµÈ ÀÌ¹Ì ¾Ë°í ÀÖ´Â ¹®ÀåÀ¸·ÎºÎÅÍ »õ·Î¿î ¹®ÀåÀÌ ÂüÀÎÁö¸¦ Ãß·ÐÇϸ鼭 Áõ¸íÇÒ ¼ö ÀÖ´Ù. ÀÌ¹Ì ÂüÀ¸·Î ÀÎÁ¤µÈ ¸íÁ¦µé·ÎºÎÅÍ »õ·Î¿î ÂüÀÎ ¸íÁ¦¸¦ ¿¬¿ª Ãß·ÐÇϸç Áõ¸íÇÏ´Â ÀÌ ¹æ¹ýÀº ´ÜÁö ¼öÇп¡¼­¸¸ÀÌ ¾Æ´Ï¶ó, ¹®Á¦¿¡ ´ëÇÑ Ç®À̸¦ ¾ò°íÀÚ ÇÏ´Â Àΰø Áö´É ºÐ¾ß¿¡¼­µµ »ç¿ëµÉ ¼ö ÀÖ´Ù. Á¤¼ö·ÐÀ̳ª ±âÇÏÇаú °°Àº ¼öÇÐÀûÀÎ ¹®Á¦¸¦ Áõ¸íÇÏ´Â °ÍÀº Ãʱâ Àΰø Áö´É ºÐ¾ßÀÇ °ü½ÉÀ̾úÀ¸¸ç, ÇöÀç¿¡µµ ¿©ÀüÈ÷ ÀÌ ºÐ¾ß¿¡¼­ ÁßÃßÀûÀÎ ºÎºÐÀÌ µÇ°í ÀÖ´Ù. ±×·¯³ª ÀÌ·¯ÇÑ ¼öÇÐÀû ±â¹ýÀ» ¼öÇÐÀÇ ¹üÀ§¸¦ ¹þ¾î³ª, ÀϹÝÀûÀÎ ¹®Á¦¿¡±îÁö ÀÌ¿ëÇÒ ¼ö ÀÖ´Ù. ¾î·Á¿î Ž»ö ¹®Á¦¸¦ Á¦¾îÇϱâ À§Çؼ­´Â, ¿¬¿ª Ãß·Ð ±â¹ý°ú °æÇèÀûÀ¸·Î ¾òÀº Áö½ÄÀÇ »ç¿ëÀÌ ÇÊ¿äÇѵ¥, ÀÌ·¯ÇÑ Ãø¸é¿¡¼­ º¼ ¶§ Ž»öÀÇ Á¦¾î ¹®Á¦¿Í ¼öÇÐÀÇ ¿©·¯ º¹ÀâÇÑ ¹®Á¦´Â ¼­·Î ´Ù¸¦ ¹Ù°¡ ¾ø´Ù.

¸ÕÀú, ¸íÁ¦ ³í¸® (propositional logic) ¸¦ »ç¿ëÇÏ¿©, Àΰø Áö´É ºÐ¾ß¿¡¼­ ÇÊ¿ä·Î ÇÏ´Â Áö½ÄÀ» Ç¥±âÇÏ´Â ¹æ¹ý¿¡ ´ëÇØ »ìÆì º¸ÀÚ. ¸íÁ¦ ³í¸®´Â ´Ù·ç±â ½±°í, ¶ÇÇÑ ÀÌ¿¡ ´ëÇÑ °áÁ¤ °úÁ¤ (decision procedure) ÀÌ Á¸ÀçÇϱ⠶§¹®¿¡ Áö½ÄÀ» Ç¥±âÇϴµ¥ »ç¿ëµÈ´Ù. ¸íÁ¦ ³í¸®¿¡¼­ÀÇ Àß ±¸¼ºµÈ °ø½Ä (well-formed formulas : wffs) À¸·Î ¾²¿©Áø ³í¸®Àû ¸íÁ¦ ÇüÅ·ΠÇö½Ç ¼¼°èÀÇ »ç½ÇÀ» Ç¥±âÇϴµ¥, ÀÌ¿¡ ´ëÇÑ ¿¹°¡ ±×¸² 2 ¿¡ ÀÖ´Ù.

ÀÌ ¸íÁ¦µéÀ» »ç¿ëÇÏ¿©, ¿¹¸¦ µé¾î, ¸¸¾à ºñ°¡ ¿À¸é ³¯¾¾°¡ ¸¼Áö ¾Ê´Ù¶ó´Â °ÍÀ» ¿¬¿ª Ãß·ÐÇÒ ¼ö ÀÖ´Ù.

ºñ°¡ ¿À°í ÀÖ´Ù.

        RAINING

³¯¾¾°¡ ¸¼´Ù.

        SUNNY

¹Ù¶÷ÀÌ ºÐ´Ù.

        WINDY

¸¸¾à ºñ°¡ ¿À¸é ³¯¾¾°¡ ¸¼Áö ¾Ê´Ù.

        RAINING ¡æ ~SUNNY

±×¸² 2  ¸íÁ¦ ³í¸®ÀÇ ¿¹

À§ÀÇ ¿¹·ÎºÎÅÍ ¸íÁ¦ ³í¸®ÀÇ ÇѰ輺¿¡ ´ëÇØ ¾Ë¾Æ º¸ÀÚ.

    Socrates is a man. (¼ÒÅ©¶óÅ×½º´Â »ç¶÷ÀÌ´Ù.)

¶ó´Â ¹®ÀåÀ»

    SOCRATESMAN

À̶ó°í Ç¥±âÇÒ °æ¿ì,

    Plato is a man. (ÇöóÅæÀº »ç¶÷ÀÌ´Ù.)

¶ó´Â ¹®ÀåÀ»

    PLATOMAN

À¸·Î Ç¥±âµÈ´Ù. »ç½ÇÀÇ Ç¥±â¸¦ À§ÇØ À§¿Í °°Àº ¹æ¹ýÀ» »ç¿ëÇÑ´Ù¸é, À§ÀÇ µÎ ¹®ÀåÀº ¿ÏÀüÈ÷ µ¶¸³ÀûÀÎ ÁÖÀåÀ¸·Î °£ÁֵǾî À̷κÎÅÍ ¼ÒÅ©¶óÅ×½º¿Í ÇöóÅæ °£ÀÇ ¾î¶² À¯»ç¼ºµµ À̲ø¾î ³¾ ¼ö ¾ø´Ù. ÀÌ »ç½ÇÀ»

    MAN(SOCRATES)

    MAN(PLATO)

¶ó°í Ç¥±âÇÏ´Â °ÍÀÌ ´õ¿í ÀûÀýÇѵ¥, À̴ ǥ±âÀÇ ±¸Á¶¿¡ Áö½Ä ÀÚüÀÇ ±¸Á¶°¡ ¹Ý¿µµÇ±â ¶§¹®ÀÌ´Ù.

    All men are mortal. (¸ðµç »ç¶÷Àº Á״´Ù.)

¶ó´Â ¹®ÀåÀ» Ç¥±âÇÒ ¶§, ÀÌ¹Ì ¾Ë·ÁÁø Á×Àº »ç¶÷ °³°³Àο¡ ´ëÇØ º°°³ÀÇ ¹®ÀåÀ» »ç¿ëÇÏÁö ¾ÊÀ» °æ¿ì »ç¶÷¿¡ ´ëÇÑ ÇÑÁ¤ (quantification) ÀÌ ÇÊ¿äÇϱ⠶§¹®¿¡ ¸íÁ¦ ³í¸®¿¡ ÀÇÇØ À̸¦ Ç¥±âÇÏ´Â °ÍÀº ¾î·Á¿î ÀÏÀÌ´Ù.

Áö½ÄÀ» Ç¥±âÇÏ´Â ¹æ¹ýÀ¸·Î ¼­¼ú ³í¸®°¡ ¸¹ÀÌ »ç¿ëµÇ´Âµ¥, ÀÌ°ÍÀº ¸íÁ¦ ³í¸®·Î Ç¥±âÇϱ⿡ ºÎÀûÇÕÇÑ °ÍµéÀ» ¼­¼ú ³í¸®·Î ÀûÀýÈ÷ Ç¥±âÇÒ ¼ö Àֱ⠶§¹®ÀÌ´Ù. ¼­¼ú ³í¸®¿¡¼­ Çö½Ç ¼¼°èÀÇ »ç½ÇÀº wff ·Î ¾²¿©Áø ¾ð¸í (statement) À¸·Î Ç¥±âµÈ´Ù. ±×·¯³ª »ç½ÇÀ» Ç¥±âÇϴµ¥ ¼­¼ú ³í¸®¸¦ »ç¿ëÇÏ´Â °¡Àå Áß¿äÇÑ ÀÌÀ¯´Â Áö½ÄÀÇ Ç¥±â ¹æ¹ýÀ¸·Î ³í¸®Àû ¾ð¸íÀ» »ç¿ëÇÒ °æ¿ì ÀÌ Áö½ÄÀ¸·ÎºÎÅÍÀÇ Ãß·ÐÀÌ °¡´ÉÇϱ⠶§¹®ÀÌ´Ù. ¸íÁ¦ ³í¸®¿¡¼­ÀÇ ¸íÁ¦¿¡ ´ëÇÑ Å¸´ç¼ºÀ» °áÁ¤ÇÏ´Â °ÍÀº °è»êÇϱ⠾î·Á¿î °ÍÀÌÁö¸¸, ¿¹¿Ü°¡ ¾ø´Â ÀÏÁ¤ÇÑ ¹æ¹ý¿¡ µû¶ó ÇÒ ¼ö ÀÖ´Ù. µû¶ó¼­ Áö½ÄÀ» Ç¥±âÇÏ´Â ÀûÀýÇÑ ¹æ¹ýÀ¸·Î ¼­¼ú ³í¸®¸¦ äÅÃÇϱ⿡ ¾Õ¼­, ÀÌ ¼­¼ú ³í¸®¸¦ »ç¿ëÇÒ ¶§, Áö½ÄÀ¸·ÎºÎÅÍÀÇ Ãß·ÐÀÌ °¡´ÉÇÑÁö ¿©ºÎ¸¦ Á¶»çÇØ¾ß ÇÑ´Ù. ´ÙÇàÈ÷ ÀÌ Á¶»ç¿¡ ´ëÇÑ °á°ú´Â ±àÁ¤ÀûÀÌ´Ù. ¼­¼ú ³í¸®´Â ÀÌ¹Ì Á¸ÀçÇÏ´Â ¹®ÀåÀ¸·ÎºÎÅÍ »õ·Î¿î ¹®ÀåÀ» Ãß·ÐÇÏ´Â ¹æ¹ýÀ» Á¦°øÇÑ´Ù. ±×·¯³ª ¸íÁ¦ ³í¸®¿¡¼­¿Í´Â ´Þ¸®, ¼­¼ú ³í¸®¿¡´Â °áÁ¤ ÇÁ·Î½ÃÁê¾î (decision procedure) °¡ ºÒÇÊ¿äÇÏ´Ù. Á¦¾ÈµÈ Á¤¸®°¡ Á¤¸»·Î Á¤¸®¶ó¸é, ÀÌ¿¡ ´ëÇÑ Áõ¸íÀ» ã±â À§ÇÑ °úÁ¤ÀÌ ÇÊ¿äÇÏÁö¸¸, Á¦¾ÈµÈ ¹®ÀåÀÌ Á¤¸®°¡ ¾Æ´Ï¶ó¸é ÀÌ °úÁ¤ÀÇ ¼öÇàÀÌ Á¾·áµÇÁö ¾Ê´Â °æ¿ì°¡ ÀÖ´Ù. ÀÌ·± °£´ÜÇÑ °úÁ¤Àº ÀÏÁ¤ÇÑ ¹æ¹ý¿¡ µû¶ó °ø¸®¿¡ Ãß·Ð ±ÔÄ¢À» Àû¿ëÇÏ¿© Á¤¸®¸¦ »ý¼ºÇϴµ¥, ÀÌ·¸°Ô ÇÏ¿© »ý¼ºµÈ °¢°¢ÀÇ Á¤¸®°¡ óÀ½¿¡ Áõ¸íÇÏ°íÀÚ ÇÏ´Â Á¤¸®ÀÎÁö Á¶»çÇÏ°Ô µÈ´Ù. ±×·¯³ª ÀÌ ¹æ¹ýÀº Ưº°È÷ È¿À²ÀûÀ̶ó°í ´Ü¾ðÇÒ ¼ö ¾ø±â ¶§¹®¿¡, ´õ ÁÁÀº ¹æ¹ýÀ» ã¾Æ¾ß ÇÑ´Ù. ¼­¼ú ³í¸®¸¦ À§ÇÑ ¾î¶² °áÁ¤ ÇÁ·Î½ÃÁê¾îµµ Á¸ÀçÇÏÁö ¾Ê´Â´Ù´Â ºÎÁ¤ÀûÀÎ °á°ú°¡ Àΰø Áö´É ºÐ¾ß¿¡ °ÅÀÇ Á÷Á¢ÀûÀÎ ¿µÇâÀº ³¢Ä¡Áö ¸øÇÑ´Ù ÇÒÁö¶óµµ, ÀÌ ºÎÁ¤ÀûÀÎ °á°ú´Â µµ¿òÀÌ µÈ´Ù. ¿Ö³ÄÇϸé, ºñ·Ï Á¤¸®°¡ ¾Æ´Ñ °Í¿¡ ´ëÇؼ­´Â Á¾·á°¡ º¸ÀåµÇÁö ¾Ê´õ¶óµµ, È¿À²ÀûÀÎ Áõ¸í °úÁ¤À» ã´Â Ž»ö °úÁ¤¿¡¼­ Á¤¸®¸¦ Áõ¸íÇÒ ¼ö ÀÖ´Â °úÁ¤À» ¹ß°ßÇÏ°Ô µÈ´Ù¸é, ¿øÇÏ´Â Ç®À̸¦ ¾ò¾ú´Ù´Â »ç½ÇÀ» ÀÌ ºÎÁ¤ÀûÀÎ °á°ú·ÎºÎÅÍ ¾Ë ¼ö Àֱ⠶§¹®ÀÌ´Ù. ¶ÇÇÑ ¸ðµç °¡´ÉÇÑ ÀԷ¿¡ ´ëÇØ À¯ÇÑ ½Ã°£ ³»¿¡ °á°ú¸¦ Ãâ·ÂÇÏ´Â °áÁ¤ ÇÁ·Î½ÃÁê¾î´Â Á¸ÀçÇÒ ¼ö ¾ø´Ù´Â »ç½ÇÀÌ Çö½ÇÀÇ ¹®Á¦¸¦ Ǫ´Â °úÁ¤¿¡¼­ ÁÖ¾îÁö´ÂÁöÀÇ ¸ðµç ÀԷ¿¡ ´ëÇØ À¯ÇÑ ½Ã°£ ³»¿¡ °á°ú¸¦ Ãâ·ÂÇÏ´Â °áÁ¤ ÇÁ·Î½ÃÁê¾î°¡ Á¸ÀçÇÒ ¼ö ¾ø´Ù´Â °ÍÀ» ÀǹÌÇÏÁö´Â ¾Ê´Â´Ù. ¼­¼ú ³í¸®ÀÇ ÀÌ·ÐÀûÀÎ ºñ°áÁ¤¼º (undecidability) ¿¡µµ ºÒ±¸ÇÏ°í Àΰø Áö´É ºÐ¾ß¿¡¼­ »ç¿ëµÉ Áö½ÄÀ» Ç¥±âÇÏ°í ó¸®ÇÏ´Â ÀûÀýÇÑ ¹æ¹ýÀ¸·Î ÀÌ ¼­¼ú ³í¸®°¡ »ç¿ëµÈ´Ù.

°£´ÜÇÑ ¿¹¸¦ »ìÆ캽À¸·Î½á, Áö½ÄÀ» Ç¥±âÇϱâ À§ÇØ »ç¿ëµÇ´Â ¼­¼ú ³í¸®¸¦ ³íÀÇÇØ º¸ÀÚ. ´ÙÀ½ ¹®ÀÚÀÇ ÁýÇÕÀÌ ÁÖ¾îÁ³´Ù :

    1. Marcus was a man. (¸¶Ä¿½º´Â »ç¶÷À̾ú´Ù.)

    2. Marcus was a Pompeian. (¸¶Ä¿½º´Â ÆûÆäÀÌ »ç¶÷À̾ú´Ù.)

    3. All Pompeians were Roman. (¸ðµç ÆûÆäÀÌ »ç¶÷Àº ·Î¸¶ÀÎÀ̾ú´Ù.)

    4. Caesar was ruler.( ½ÃÀÌÀú´Â ÅëÄ¡ÀÚ¿´´Ù.)

    5. All Romans were either loyal to Caesar or hated him.
       (¸ðµç ·Î¸¶ÀεéÀº ½ÃÀÌÀú¿¡ Ã漺ÇÏ¿´°Å³ª ±×¸¦ ¹Ì¿öÇÏ¿´´Ù.)

    6. Everyone is loyal to someone. (¸ðµç »ç¶÷Àº ´©±º°¡¿¡°Ô Ã漺ÇÑ´Ù.)

    7. People only try to assassinate rulers they are not loyal to.
       (»ç¶÷Àº ±×µéÀÌ Ã漺ÇÏÁö ¾Ê´Â ÅëÄ¡ÀÚÀÇ ¾Ï»ìÀ» ±âµµÇÑ´Ù.)

    8. Marcus tried to assassinate Caesar. (¸¶Ä¿½º´Â ½ÃÀÌÀú¸¦ ¾Ï»ìÇÏ·Á Çß´Ù.)

À§ ¹®ÀåÀ¸·Î Ç¥±âµÈ »ç½ÇÀ» ¼­¼ú ³í¸®ÀÇ ´ÙÀ½°ú °°Àº wff µéÀÇ ÁýÇÕÀ¸·Î Ç¥±âÇÒ ¼ö ÀÖ´Ù :

    1. Marcus was a man.
               man(Marcus)

ÀÌ¿Í °°ÀÌ Ç¥±âÇÔÀ¸·Î½á ¸¶Ä¿½º°¡ »ç¶÷À̶ó´Â Áß¿äÇÑ »ç½ÇÀº Ç¥ÇöÇÒ ¼ö ÀÖÁö¸¸, ¿µ¾î ¹®Àå¿¡¼­ÀÇ Á¤º¸, Áï ½ÃÁ¦¿Í °°Àº °ÍÀº ³ªÅ¸³¾ ¼ö ¾ø´Ù. ÀÌ·¯ÇÑ »ý·«À» ¹Þ¾ÆµéÀÏ ¼ö ÀÖÀ» ÁöÀÇ ¿©ºÎ´Â ¾î¶² °÷¿¡ Áö½ÄÀ» »ç¿ëÇÏ´À³Ä¿¡ ÀÇÇØ °áÁ¤µÈ´Ù.

    2. Marcus was a Pompeian.
           Pompeian(Marcus)

    3. All Pompeians were Romans.
           ¢£x Pompeian(x) ¡æ Roman(x)

    4. Caesar was a ruler.
           ruler(Caesar)

¿©±â¼­´Â ¸¹Àº »ç¶÷ÀÌ µ¿ÀÏÇÑ À̸§À» °¡Áú ¼ö ÀÖÀ½¿¡µµ ºÒ±¸ÇÏ°í Ç¥±â¿¡ »ç¿ëµÈ À̸§ÀÌ À¯ÀÏÇÑ »ç¶÷À» ³ªÅ¸³»´ÂÁö¿¡ ´ëÇØ ¾ð±ÞÇÏÁö ¾Ê¾Ò´Ù. ¶§¶§·Î, µ¿ÀÏÇÑ À̸§À» °¡Áø ¿©·¯ »ç¶÷ Áß¿¡¼­ ƯÁ¤ÇÑ ¾ð¸í¿¡ ¾ð±ÞµÉ »ç¶÷À» °áÁ¤Çϱâ À§ÇØ ¸¹Àº ¾çÀÇ Áö½Ä°ú Ãß·ÐÀÌ »ç¿ëµÈ´Ù.

¿µ¹®¿¡¼­ 'or' ´Â Æ÷¼·ÀûÀÎ ³í¸®ÇÕ (inclusive or) À» ÀǹÌÇÒ ¶§µµ, ¹èŸÀûÀÎ ³í¸®ÇÕ (exclusive or) À» ÀǹÌÇÒ ¶§µµ ÀÖ´Ù. À§¿¡¼­ÀÇ 'or' ´Â Æ÷¼·ÀûÀÎ ³í¸®ÇÕÀ¸·Î »ç¿ëµÇ¾ú´Ù. ¿µ¾î ¹®Àå¿¡ ³ªÅ¸³­ or °¡ ½ÇÁ¦·Î ¹èŸÀûÀÎ ³í¸®ÇÕÀ» ÀǹÌÇÒ ¼öµµ Àִµ¥, ÀÌ°ÍÀº ´ÙÀ½°ú °°ÀÌ Ç¥±âÇÏ¿© ³ªÅ¸³½´Ù :

    ¢£x Roman(x) ¡æ ((loyalto(x, Caesar) ¡ý hate(x, Caesar))
                           ¡ü ~(loyalto(x, Caesar) ¡ü hate(x, Caesar))

    6. Everyone is loyal to someone.
           ¢£x¢¤y loyalto(x, y)

¿µ¾î ¹®ÀåÀ» ³í¸®Àû ¹®ÀåÀ¸·Î º¯È¯½Ãų ¶§ ¹ß»ýÇÏ´Â °¡Àå Å« ¹®Á¦´Â ÇÑÁ¤»ç (quantifier) ÀÇ ¹üÀ§ÀÌ´Ù. À§ ¹®ÀåÀÌ, °¢ »ç¶÷¿¡ ´ëÇØ ±×°¡ Ã漺ÇÒ ¾î¶² »ç¶÷ - °¢ »ç¶÷Àº ¼­·Î ´Ù¸¥ »ç¶÷¿¡ Ã漺ÇÒ ¼öµµ ÀÖ´Ù - ÀÌ Á¸ÀçÇÏ´Â °ÍÀ» ¸»Çϴ°¡, ȤÀº ¸ðµç »ç¶÷ÀÌ Ã漺ÇÒ ¾î¶² »ç¶÷ÀÌ Á¸ÀçÇÏ´Â °Í (ÀÌ°ÍÀº ¢¤y ¢£x loyal to (x, y) ¶ó ¾µ ¼ö ÀÖ´Ù) À» ¸»Çϴ°¡? µÎ °¡Áö ¹ø¿ª Áß, »óȲ¿¡ µû¶ó ´õ¿í ÀûÀýÇÑ °ÍÀ» ÅÃÇØ »ç¿ëÇÑ´Ù.

    7. People only try to assassinate rulers they are not loyal to.
            ¢£x¢£y person(x) ¡ü ruler(y) ¡ü tryassassinate(x, y) ¡æ ~loyalto(x, y)

ÀÌ ¹®ÀåÀº ¸Å¿ì ¸ðÈ£ÇÏ´Ù. ÀÌ ¹®ÀåÀÌ »ç¶÷µéÀÌ ¾Ï»ìÇÏ°íÀÚ ÇÏ´Â ÅëÄ¡ÀÚ´Â ±×µéÀÌ Ã漺ÇÏÁö ¾Ê´Â ÅëÄ¡ÀÚÀÓ (¿©±â¼­´Â ÀÌ Àǹ̷Π»ç¿ëÇÑ´Ù) À» ÀǹÌÇÏ´ÂÁö ȤÀº »ç¶÷µéÀÌ ÀǵµÇÏ´Â À¯ÀÏÇÑ ÇàÀ§´Â ±×µéÀÌ Ã漺ÇÏÁö ¾Ê´Â ÅëÄ¡ÀÚ¸¦ ¾Ï»ìÇÏ°íÀÚ ÇÏ´Â ÇàÀ§ÀÓÀ» ÀǹÌÇÏ´ÂÁö È®½ÇÈ÷ ¾Ë ¼ö ¾ø´Ù.

ÀÌ ¹®ÀåÀ» Ç¥±âÇÒ ¶§, "¾Ï»ìÀ» ±âµµÇÑ´Ù" ¸¦ ÇϳªÀÇ ¼­¼úÇü ¸íÁ¦ (predicate) ·Î ¼±ÅÃÇÏ¿´´Ù. ÀÌ ¼­¼úÇü ¸íÁ¦´Â ¾Ï»ìÀ» ±âµµÇÑ´Ù´Â °ÍÀ» Ãß·ÐÇÒ ¶§ ÀÌ¿ëµÉ »ç½ÇÀ» ¸Å¿ì °£´ÜÈ÷ Ç¥±âÇÑ °ÍÀÌ´Ù. ±×·¯³ª ÀÌ Ç¥±â¹ýÀ¸·Î´Â, ¾Ï»ìÀ» ±âµµÇÏ´Â °Í°ú ´Ù¸¥ ¾î¶² °ÍÀ» ½ÃµµÇÏ´Â °Í °£ÀÇ °ü°è ¹× ¾Ï»èÀ» ±âµµÇÏ´Â °Í°ú ½ÇÁ¦·Î ¾Ï»ìÇÑ °Í °£ÀÇ °ü°è¸¦ ½±°Ô ³ªÅ¸³¾ ¼ö°¡ ¾ø´Ù. ¸¸¾à ÀÌ·¯ÇÑ °ü°è°¡ ÇÊ¿äÇÏ´Ù¸é, ´Ù¸¥ Ç¥±â¹ýÀ» ¼±ÅÃÇØ¾ß ÇÑ´Ù.

    8. Marcus tried to assassinate Caesar.
           tryassassinate(Marcus, Caesar)

¿µ¾î ¹®ÀåÀ» ³í¸®Àû ¾ð¸íÀ¸·Î º¯È¯½ÃÅ°·Á´Â À§ÀÇ °£´ÜÇÑ ½Ãµµ·ÎºÎÅÍ, ÀÌ ÀÛ¾÷ÀÌ ¾ó¸¶³ª ¾î·Á¿î °ÍÀÎÁö¸¦ ¾Ë ¼ö ÀÖ´Ù.

    Was Marcus loyal to Caesar? (¸¶Ä¿½º´Â ½ÃÀÌÀú¿¡ Ã漺ÇÏ¿´´Â°¡?)

¶ó´Â Áú¹®¿¡ ´ëÇÑ ´äÀ» ã±â À§ÇØ ¾Õ¿¡¼­ ¼Ò°³µÈ ¿©´ü °³ÀÇ ¾ð¸íÀ» »ç¿ëÇÑ´Ù°í ÇÏÀÚ. ¾ð¸í 7 °ú 8 À» »ç¿ëÇÏ¿© ¸¶Ä¿½º´Â ½ÃÀÌÀú¿¡ Ã漺ġ ¾Ê¾ÒÀ½À» Áõ¸íÇÒ ¼ö ÀÖ´Ù (½ÃÁ¦ÀÇ ±¸º°Àº ¹«½ÃÇÑ´Ù). ¿øÇÏ´Â ¸ñÇ¥ - ~loyalto(Marcus, Caesar) - ·ÎºÎÅÍ ÈÄÁø Ãß·ÐÇϸ鼭, Çü½ÄÀûÀÎ Áõ¸íÀ» ÇØ º¸ÀÚ. ÀÌ ¸ñÇ¥¸¦ Áõ¸íÇϱâ À§ÇØ Ãß·Ð ±ÔÄ¢À» »ç¿ëÇÏ¿©, ¸¸Á·½º·´Áö ¸øÇÑ °ÍÀÌ Çϳªµµ ³²Áö ¾ÊÀ» ¶§±îÁö ÀÌ ¸ñÇ¥¸¦ ´Ù¸¥ ¸ñÇ¥·Î º¯È¯ÇÏ°í, »õ·ÎÀÌ ¾òÀº ¸ñÇ¥¸¦ ´Ù½Ã ´Ù¸¥ ¸ñÇ¥·Î °è¼Ó º¯È¯½ÃŲ´Ù. ÀÌ °úÁ¤¿¡´Â AND-OR ±×·¡ÇÁÀÇ Å½»öÀÌ ÇÊ¿äÇÏ´Ù. ÆíÀÇ»ó, ÇϳªÀÇ À¯ÀÏÇÑ °æ·Î¸¸À» º¸ÀÌ°íÀÚ ÇÑ´Ù. ±×¸² 3 Àº ÇÊ¿äÇÏÁö¸¸ ¾òÀ» ¼ö ¾ø´Â ¸ñÇ¥ÀÇ ÁýÇÕÀ» °øÁýÇÕÀ¸·Î Ãà¼Ò½ÃÅ´À¸·Î½á ¸ñÇ¥ÀÇ Áõ¸íÀ» ã¾Æ³»·Á´Â ½Ãµµ¸¦ º¸¿© ÁØ´Ù. ±×·¯³ª ¸ñÇ¥ person(Marcus) °¡ ÀÌ¿ë °¡´ÉÇÑ ¾î¶² ¾ð¸í¿¡ ÀÇÇؼ­µµ ¸¸Á·µÉ ¼ö ¾ø±â ¶§¹®¿¡ ÀÌ ½Ãµµ´Â ½ÇÆÐÀÌ´Ù.

±×¸² 3  ~Loyalto(Marcus, Caesar) À» Áõ¸íÇÏ´Â °úÁ¤

ºñ·Ï ¸¶Ä¿½º°¡ »ç¶÷ÀÎÁö´Â ¾Ë°í ÀÖÁö¸¸, ¾ÕÀÇ ¾ð¸íµé·ÎºÎÅÍ´Â ¸¶Ä¿½º°¡ Àΰ£ÀÓÀ» Ãß·ÐÇÒ ¼ö ¾ø´Ù. À̸¦ À§ÇØ ´ÙÀ½°ú °°ÀÌ Ç¥±âµÈ »ç½ÇÀÌ ÇÊ¿äÇÏ´Ù :

    9. All men are people.
           ¢£x man(x) ¡æ person(x)

ÀÌÁ¦ ¿øÇÏ´Â ¸ñÇ¥¸¦ ¸¸Á·½ÃÄÑ, ¸¶Ä¿½º°¡ ½ÃÀÌÀú¿¡ Ã漺ÇÏÁö ¾Ê¾Ò´Ù´Â °ÍÀ» Áõ¸íÇÒ ¼ö ÀÖ´Ù.

ÀÌ °£´ÜÇÑ ¿¹·ÎºÎÅÍ, ¿µ¾î ¹®ÀåÀ» ³í¸®Àû ¾ð¸íÀ¸·Î ¹Ù²ã »õ·Î¿î ¾ð¸íÀ» ¿¬¿ª Ãß·ÐÇÏ´Â °úÁ¤¿¡¼­, ´ÙÀ½°ú °°Àº ¼¼ °¡Áö Áß¿äÇÑ ¹®Á¦Á¡ÀÌ ¹ß»ýÇÔÀ» ¾Ë ¼ö ÀÖ´Ù :

¿¬¿ª Ãß·ÐÇÒ ¾ð¸íÀ» ¹Ì¸® ¾Ë ¼ö ¾ø´Â »óȲ¿¡¼­´Â ¶Ç ´Ù¸¥ ¹®Á¦°¡ ¹ß»ýÇÑ´Ù. À§ÀÇ ¿¹¿¡¼­´Â "Was Marcus loyal to Caesar?" ¶ó´Â Áú¹®¿¡ ´ëÇÑ ´äÀ» ã¾Æ¾ß ÇÑ´Ù.

    loyalto (Marcus, Caesar)

¸¦ Áõ¸íÇØ¾ß ÇÒÁö, ȤÀº

    ~loyalto (Marcus, Caesar)

¸¦ Áõ¸íÇØ¾ß ÇÒÁö¸¦ ÇÁ·Î±×·¥Àº ¾î¶»°Ô °áÁ¤Çϴ°¡? À̸¦ À§ÇØ ¿©·¯ °¡Áö ¹æ¹ýÀÌ Àִµ¥, Á¦¾ÈµÈ Áø¸®·ÎºÎÅÍ °ø¸® (axiom) ·Î ÈÄÁø Ãß·ÐÇÏ´Â ¹æ¹ý ´ë½Å, ÀüÁø Ãß·ÐÇÏ¸é ¾î¶² ´äÀ» ¾ò°Ô µÉÁö ¾Ë¾Æº¸ÀÚ. ÀϹÝÀûÀ¸·Î, ÀÌ ¹æ¹ý¿¡´Â °ø¸®·ÎºÎÅÍÀÇ ÀüÁø Ã߷нà ºÐ±â °è¼ö°¡ ¾öû³ª°Ô Ä¿¼­ ÁÖ¾îÁø ½Ã°£ ³»¿¡ ´äÀ» ¾òÀ» ¼ö ¾ø´Ù´Â ¹®Á¦Á¡ÀÌ Á¸ÀçÇÑ´Ù.

´Ù¸¥ ¶Ç ÇϳªÀÇ ¹æ¹ýÀº °æÇèÀû Áö½ÄÀÇ ±ÔÄ¢À» »ç¿ëÇÏ¿© °¡´É¼ºÀÌ ³ôÀº ´äÀ» ã¾Æ, ¸ÕÀú ÀÌ°Í¿¡ ´ëÇÑ Áõ¸íÀ» ½ÃµµÇÏ´Â °ÍÀÌ´Ù. ÇÕ´çÇÑ ¸¸Å­ÀÇ ³ë·Â ÈÄ¿¡µµ ÀÌ°ÍÀ» Áõ¸íÇÒ ¼ö ¾ø´Ù¸é, ´Ù¸¥ ´ä¿¡ ´ëÇØ ½ÃµµÇÑ´Ù. Á¤¸®°¡ ¾Æ´Ñ °ÍÀ» Áõ¸íÇÏ°íÀÚ ÇÒ °æ¿ì, ¾î¶² Áõ¸í °úÁ¤µµ À¯ÇÑ ½Ã°£ ³»¿¡ ÀÌ°Í¿¡ ´ëÇÑ °á°ú¸¦ ³¾ ¼ö ¾ø±â ¶§¹®¿¡, ³ë·Â¿¡ Á¦ÇÑÀ» µÐ´Ù´Â °³³äÀº Áß¿äÇÏ´Ù. ¶Ç ´Ù¸¥ ¹æ¹ýÀº µÎ ´ä¿¡ ´ëÇÑ Áõ¸íÀ» µ¿½Ã¿¡ ½ÃµµÇÏ¿© µÑ Áß ¾î´À Çϳª¿¡ ´ëÇÑ Áõ¸íÀ» ãÀ¸¸é, ÀÌ °úÁ¤À» Áß´ÜÇÏ´Â °ÍÀÌ´Ù. ±×·¯³ª Áú¹®¿¡ ´ëÇÑ ´äÀ» ãÀ» ¶§ ÀÌ¿ë °¡´ÉÇÑ Á¤º¸°¡ ÃæºÐÈ÷ ÁغñµÇÁö ¾ÊÀ» °æ¿ì, ÇÁ·Î±×·¥ÀÌ À¯ÇÑ ½Ã°£ ³»¿¡ ´äÀ» ãÁö ¸øÇÒ ¼ö°¡ ÀÖ´Ù. ´Ù¸¥ ¶Ç ÇϳªÀÇ ¹æ¹ýÀº ÇÑ ´äÀ» Áõ¸íÇÔ°ú µ¿½Ã¿¡ ÀÌ°ÍÀÌ ´äÀÌ ¾Æ´ÔÀ» Áõ¸íÇÏ´Â °ÍÀÌ´Ù. DISPROVER ¿¡ ÀÌ ±â¹ýÀÌ »ç¿ëµÇ¾ú´Âµ¥ DISPROVER ´Â Ç®ÀÌ°¡ Á¸ÀçÇÏÁö ¾ÊÀ½À» º¸ÀδÙ. ¸¸¾à Ç®ÀÌ°¡ Á¸ÀçÇÒ °æ¿ì, DISPROVER ´Â Ç®À̸¦ ãÀ» ¼ö ÀÖÀ½À» ¾Ë¸®´Â Á¤º¸¸¦ Á¦°øÇÑ´Ù.

3. °è»ê °¡´ÉÇÑ ÇÔ¼ö¿Í ¼ú¾îÇü ¸íÁ¦¿¡ ÀÇÇÑ Áö½ÄÀÇ Ç¥±â

¾Õ Àý¿¡¼­ ³íÀÇµÈ ¿¹¿¡¼­, °£´ÜÇÑ ¸ðµç »ç½ÇÀº

    tryassassinate(Marcus, Caesar)

¿Í °°Àº °³°³ ¼­¼úÇü ¸íÁ¦ÀÇ °áÇÕÀ¸·Î Ç¥±âµÇ¾ú´Ù. »ç½ÇÀÇ ¼ö°¡ Àû°Å³ª, »ç½Ç ÀÚü°¡ ¸Å¿ì ºñ ±¸Á¶ÀûÀÏ °æ¿ì, ÀÌ¿Í °°ÀÌ Ç¥ÇöÇÒ ¼ö ÀÖ´Ù. ±×·¯³ª

gt (1, 0)          lt (0, 1)

gt (2, 1)          lt (1, 2)

gt (3, 2)          lt (2, 3)

.                   .

.                   .

.                   .

°ú °°ÀÌ °£´ÜÇÑ ¿¹¸¦ Ç¥±âÇÏ°íÀÚ ÇÏ´Â °æ¿ì¸¦ »ìÆì º¸ÀÚ.

À§ »ç½ÇÀ» °¢°¢ °³º°ÀûÀ¸·Î Ç¥±âÇÏ´Â °ÍÀº ºñÈ¿À²ÀûÀÌ´Ù. ¿Ö³ÄÇϸé, ÀÌ¿Í °°Àº »ç½ÇÀÌ ¹«ÇÑÈ÷ ¸¹ÀÌ Á¸ÀçÇϱ⠶§¹®ÀÌ´Ù. ÇÊ¿ä¿¡ µû¶ó °¢°¢À» ¾ò¾î³¾ ¼ö ÀÖ´Â ÇÔ¼ö°¡ Á¸ÀçÇÒ °æ¿ì, ÀÌ »ç½ÇÀ» ¸ðµÎ ±â·ÏÇÏ´Â °ÍÀº ¸Å¿ì ºñÈ¿À²ÀûÀÌ´Ù. Áï °è»êÀÌ °¡´ÉÇÑ ¼­¼úÇü ¸íÁ¦¸¦ »ç¿ëÇÏ¿© »ç½ÇÀ» ´õ¿í ÀûÀýÈ÷ Ç¥±âÇÒ ¼ö ÀÖ´Ù. Áõ¸í °úÁ¤ÀÌ ÀÌ·¯ÇÑ ¼­¼úÇü ¸íÁ¦¸¦ ÀÌ¿ëÇÒ °æ¿ì, µ¥ÀÌÅÍ º£À̽º¿¡¼­ ±×°ÍÀ» ã°Å³ª, ¿¬¿ª Ãß·ÐÇÏ´Â ´ë½Å, ÀÌ ¼­¼úÇü ¸íÁ¦¸¦ Æò°¡ÇÏ¿© Áø¸®°ªÀ» µ¹·ÁÁÖ´Â °úÁ¤À» Á¤ÇØÁø ±ÔÄ¢°ú ÇÔ²² ±ÔÁ¤ÇÏ¿©, ÇÊ¿ä¿¡ µû¶ó È£ÃâÇÑ´Ù.

°è»êÀÌ °¡´ÉÇÑ ¼­¼úÇü ¸íÁ¦»Ó¸¸ ¾Æ´Ï¶ó, °è»ê °¡´ÉÇÑ ÇÔ¼ö¸¦ ÀûÀýÈ÷ »ç¿ëÇÔÀ¸·Î½á »ç½ÇÀ» ´õ¿í È¿À²ÀûÀ¸·Î Ç¥ÇöÇÒ ¼ö ÀÖ´Ù.

    gt (2 + 3, 1)

ÀÇ Áø¸®°ªÀ» ±¸ÇÑ´Ù°í °¡Á¤ÇÏÀÚ. ¸Å°³ º¯¼ö·Î 2 ¿Í 3 ÀÌ ÁÖ¾îÁø µ¡¼À ÇÔ¼ö°ªÀ» ¸ÕÀú °è»êÇÑ ÈÄ, ¸Å°³ º¯¼ö 5 ¿Í 1 À» gt ¿¡ º¸³½´Ù.

´ÙÀ½ ¿¹´Â °è»ê °¡´ÉÇÑ ÇÔ¼ö¿Í ¼­¼úÇü ¸íÁ¦¸¦ ÀûÀýÈ÷ »ç¿ëÇÏ´Â ¹æ¹ýÀ» ¼³¸íÇØ ÁØ´Ù. ÀÌ°ÍÀº µîÈ£ÀÇ °³³äÀ» ÀÌ¿ëÇÏ¿©, Áõ¸íÀÇ ¼öÇà µ¿¾È ÇÊ¿ä¿¡ µû¶ó °°Àº ¹°Ã¼µéÀ» ¼­·ÎÀÇ ´ë¿ë¹°·Î »ç¿ëÇÑ´Ù.

¸¶Ä¿½º¿¡ ´ëÇÑ ´ÙÀ½ »ç½ÇµéÀ» »ìÆì º¸ÀÚ :

    1. Marcus was a man. (¸¶Ä¿½º´Â »ç¶÷À̾ú´Ù.)

                     man (Marcus)

¿©±â¼­µµ ½ÃÁ¦¸¦ ¹«½ÃÇÏ¿´´Ù.

    2. Marcus was a Pompeian. (¸¶Ä¿½º´Â ÆûÆäÀÌ »ç¶÷À̾ú´Ù.)

                    Pompeian (Marcus)

    3. Marcus was born in 40 A.D. (¸¶Ä¿½º´Â A.D. 40 ³â¿¡ ž´Ù.)

                    born (Marcus, 40)

ÆíÀÇ»ó, ÀÏ»ó »ýÈ°¿¡¼­ A.D. ¸¦ »ý·«ÇÏ¿´´Ù. ¸¸¾à B.C ¸¦ Ç¥±âÇØ¾ß ÇÒ °æ¿ì, À½¼ö ±âÈ£¿Í °°Àº °ÍÀ» »ç¿ëÇÏ¿© À̸¦ Ç¥±âÇÒ ¼ö ÀÖ´Ù. ¸¸¾à ¹®ÀåÀ» Ç¥±âµÈ ¹®ÀåÀ¸·Î, Ç¥±âµÈ ¹®ÀåÀ» ¹®ÀåÀ¸·Î º¯È¯½Ãų ¼ö ÀÖ´Â ¹æ¹ýÀÌ ÀÖ´Ù¸é, Ç¥±âµÈ ¹®ÀåÀÌ ¹®Àå°ú À¯»çÇÒ ÇÊ¿ä´Â ¾ø´Ù. ÀÌ·¯ÇÑ ÀÌÀ¯ ¶§¹®¿¡, ¾ç¼ö¿Í À½¼ö°°Àº Ç¥±â¹ýÀ» ¼±ÅÃÇÏ¿© ÇÁ·Î±×·¥À» ½±°Ô ó¸®ÇÒ ¼ö ÀÖ´Ù.

    4. All men are mortal. (¸ðµç »ç¶÷Àº Á״´Ù.)

                    ¢£x man(x) ¡æ mortal(x)

    5. All Pompeians died when the volcano erupted in 79 A.D.
       (A.D. 79 ³â¿¡ È­»êÀÌ Æø¹ßÇÏ¿´À» ¶§, ¸ðµç ÆûÆäÀÌ »ç¶÷µéÀº Á×¾ú´Ù.)

                    erupted (volcano, 79) ¡ü ¢£x (Pompeian(x) ¡æ died(x, 79))

ÀÌ ¹®ÀåÀº À§ÀÇ µÎ °¡Áö »ç½ÇÀ» Ç¥±âÇϸç, ¶ÇÇÑ ÆûÆäÀÌ »ç¶÷µéÀ» Á×°Ô Çß´ø È­»êÀÇ ºÐÃâÀ̶ó´Â Áõ¸íÇÒ ¼ö ¾ø´Â »ç½ÇÀ» Ç¥±âÇÑ´Ù. ¸¸¾à µ¿½Ã¿¡ ¹ß»ýÇÑ »ç°Ç °£¿¡ Àΰú °ü°èÀÇ °¡´É¼ºÀÌ ÀÖ´Ù°í »ý°¢µÇ¸é, ÀÌ·± Àΰú °ü°è¸¦ °¡Á¤ÇÑ´Ù.

ÀÌ ¹®ÀåÀ» ¹ø¿ªÇÒ ¶§ ¹ß»ýÇÏ´Â ¶Ç ´Ù¸¥ ¹®Á¦´Â È­»êÀÌ ³ªÅ¸³»´Â ´ë»óÀ» °áÁ¤ÇÏ´Â ¹®Á¦ÀÌ´Ù. Áö±¸»ó¿¡´Â ¸¹Àº È­»êÀÌ Á¸ÀçÇÑ´Ù. ¹°·Ð ¿©±â¼­ ¸»ÇÏ´Â È­»êÀº ÆûÆäÀÌ ±Ùó¿¡ ÀÖ°í A.D. 79 ³â¿¡ Æø¹ßÇÑ º£¼öºñ¾î½º È­»êÀÌ´Ù. ÀϹÝÀûÀ¸·Î ´ë»óÀ» °áÁ¤Çϱâ À§Çؼ­´Â ¸¹Àº Ã߷аú À̸¦ À§ÇÑ Áö½ÄÀÌ ÇÊ¿äÇÏ´Ù.

    6. No mortal lives longer than 150 years. (¾î¶² »ý¹°µµ 150 ³â ÀÌ»ó »ì ¼ö ¾ø´Ù.)

                    ¢£x¢£t1¢£t2 mortal(x) ¡ü born(x, t1) ¡ü gt(t2-t1, 150) ¡æ dead(x, t2)

¿©·¯ °¡Áö ¹æ¹ýÀ» »ç¿ëÇÏ¿© ÀÌ ¹®ÀåÀÇ ³»¿ëÀ» ³ªÅ¸³¾ ¼ö ÀÖ´Ù. ¿¹¸¦ µé¾î "age" ¶ó´Â ÇÔ¼ö¸¦ »ç¿ëÇÏ¿© ÀÌ°ÍÀÇ ÇÔ¼ö°ªÀÌ 150 º¸´Ù Àû°Å³ª °°À½À» ÁÖÀåÇÒ ¼ö ÀÖ´Ù. ±×·¯³ª À§¿¡ º¸¿©Áø Ç¥±â°¡ À̺¸´Ù ´õ¿í °£´ÜÇÏ°í, ÀÌ ¹®ÀåÀÇ Ç¥Çö¿¡ ÀûÇÕÇÏ´Ù.

    7. It is now 1985. (¿ÃÇØ´Â 1985 ³âÀÌ´Ù.)

                    now = 1985

¿©±â¼­´Â ¼­·Î ´ë½Å »ç¿ëÇÒ ¼ö ÀÖ´Â µ¿ÀϹ°ÀÇ °³³äÀ» ÀÌ¿ëÇÏ¿´´Ù.

Is Marcus alive? (¸¶Ä¿½º´Â »ì¾Æ Àִ°¡?) ¶ó´Â Áú¹®¿¡ ´ëÇÑ ´äÀ» ã¾Æ º¸ÀÚ. ÁÖ¾îÁø ¾ð¸íµé·ÎºÎÅÍ, µÎ °¡Áö ¹æ¹ý¿¡ ÀÇÇØ ÀÌ ¹®Á¦¿¡ ´ëÇÑ ´äÀ» Ãß·ÐÇÒ ¼ö ÀÖ´Ù. È­»ê Æø¹ß·Î ¸¶Ä¿½º°¡ Á×¾ú´Ù´Â °ÍÀ» º¸ÀÏ ¼öµµ ÀÖ°í, 150 ³â ÀÌ»ó »ì ¼ö ¾ø´Ù´Â »ç½Ç·Î ±×´Â Á×¾î¾ß¸¸ ÇÑ´Ù´Â °ÍÀ» º¸ÀÏ ¼ö ÀÖ´Ù. ±×·¯³ª ¾ÕÀÇ ¿¹¿¡¼­Ã³·³ ÀÌ µÎ °æ·Î¸¦ µû¶ó °¡¸ç Áõ¸íÀ» ¿Ï¼ºÇϱâ À§ÇØ ±âŸ Áö½ÄµéÀÌ ÇÊ¿äÇÏ´Ù. ¿¹¸¦ µé¾î, Á×À½¿¡ °üÇØ ¸»ÇÏ´Â ¾ð¸íÀº ÀÖÁö¸¸, Á¸ÀçÇÏ°í ÀÖÀ½°ú °ü·ÃµÈ ¾ð¸íµéÀº ¾ø´Ù. µû¶ó¼­ ´ÙÀ½°ú °°Àº »ç½ÇµéÀ» ÷°¡ÇÑ´Ù :

    1. Alive means not dead. (»ì¾Æ ÀÖÀ½Àº Á×Áö ¾Ê¾ÒÀ½À» ÀǹÌÇÑ´Ù.)

                    ¢£x¢£t alive(x, t) ¡ê ~dead(x, t)

Á×Áö ¾ÊÀº °ÍÀº »ì¾Æ ÀÖ´Â °ÍÀ» ÀǹÌÇÑ´Ù´Â »ç½ÇÀº »ý¹°¿¡ ´ëÇؼ­¸¸ ¼º¸³ÇÑ´Ù. µû¶ó¼­ ¾ö°ÝÈ÷ ¸»Çϸé À§ ¾ð¸íÀº ¿ÇÁö ¾Ê´Ù (ÀÇÀÚ´Â Á×Àº °Íµµ »ì¾Æ ÀÖ´Â °Íµµ ¾Æ´Ï´Ù). ¿©±â¼­µµ ½ÃÁ¦¸¦ ¹«½ÃÇß´Ù. ÀÌ°ÍÀº ¸ðµç »óȲ¿¡¼­ µ¿ÀÏÇÑ Àǹ̸¦ °®´Â °æ¿ì´Â µå¹°´Ù´Â »ç½ÇÀ» º¸¿© ÁØ´Ù.

    2. If someone dies, then he is dead at all later times.
       (¸¸¾à ´©±º°¡°¡ Á״´ٸé, ±×´Â ±× ÈÄ ½Ã´ë¿¡¼­µµ Á×¾î ÀÖ´Ù.)

                    ¢£x¢£t1¢£t2 died(x, t1) ¡ü gt(t2, t1) ¡æ dead(x, t2)

ÀÌ°ÍÀº Á×Àº »ç¶÷Àº ±× ÀÌÈÄ¿¡µµ Á×¾î ÀÖÀ½À» ³ªÅ¸³½ °ÍÀ¸·Î, ±×°¡ Á×¾ú´ø ÇØ¿¡ ±×°¡ Á×¾î ÀÖ´ÂÁö¿¡ ´ëÇÑ Àǹ®Àº ¹«½ÃÇÏ¿´´Ù. ÀÌ Àǹ®À» ÇØ°áÇϱâ À§ÇØ, Çظ¦ º¸´Ù ÀÛÀº ½Ã°£ ´ÜÀ§·Î ³ª´©¾î¾ß ÇÑ´Ù. ¸¸¾à (year 1, month 2) µ¿¾È¿¡ Á×¾ú´ø »ç¶÷¿¡ ´ëÇØ month 2 °¡ month 1 º¸´Ù ¾Õ¼³ ¶§ "One is dead at (year 1, month 1)" °ú °°Àº ±ÔÄ¢À» ÷°¡ÇÒ ¼ö ÀÖ´Ù. ÇÊ¿ä¿¡ µû¶ó ÀÏ, ½Ã°£±îÁö Çظ¦ ¼¼ºÐÇÒ ¼ö ÀÖ´Ù.

Áö±Ý±îÁö Ç¥±âµÇ¾ú´ø ¸ðµç »ç½Ç¿¡ ´ëÇÑ ¿ä¾àÀÌ ±×¸² 4 ¿¡ ³ªÅ¸³ª ÀÖ´Ù.

1. man (Marcus)

2. Pompeian (Marcus)

3. born (Marcus, 40)

4. ¢£x man (x) ¡æ mortal (x)

5. ¢£x Pompeian (x) ¡æ died (x, 79)

6. erupted (volcano, 79)

7. ¢£x¢£t1¢£t2 mortal (x) ¡ü born (x, t1) ¡ü gt (t2-t1, 150) ¡æ dead(x, t2)

8. now = 1985

9. ¢£x¢£t alive(x, t) ¡ê ~dead(x, t)

10.¢£x¢£t1¢£t2 died(x, t1) ¡ü gt(t2, t1) ¡æ dead(x, t2)

±×¸² 4  ¸¶Ä¿½º¿¡ °üÇÑ »ç½ÇµéÀÇ ÁýÇÕ

 

±×¸² 5  Marcus Is Dead ¸¦ Áõ¸íÇÏ´Â ÇÑ ¹æ¹ý

±×¸² 6  That Marcus Is Dead ¸¦ Áõ¸íÇÏ´Â ´Ù¸¥ ¹æ¹ý

    ~alive (Marcus, now)

¸¦ Áõ¸íÇÔÀ¸·Î½á, "Is Marcus alive?" ¶ó´Â Áú¹®¿¡ ´ëÇÑ ´äÀ» ã¾Æ º¸ÀÚ. ±×¸² 5 ¿Í ±×¸² 6 ¿¡ À̸¦ À§ÇÑ µÎ °¡Áö Áõ¸íÀÌ ¼Ò°³µÇ¾ú´Ù. °¢ Áõ¸íÀÇ ³¡¿¡ ³ªÅ¸³­ nil Àº Áõ¸íµÇ±â À§ÇØ ³²¾Æ ÀÖ´Â Á¶°ÇÀÇ ¸®½ºÆ®°¡ ÀüºÎ »ç¿ëµÇ¾î ¼º°øÀûÀ¸·Î Áõ¸íµÇ¾úÀ½À» ³ªÅ¸³½´Ù. Áõ¸í °úÁ¤ Áß ³ªÅ¸³­

    a ¡ü b ¡æ c

ÇüÅÂÀÇ ¾ð¸í¿¡¼­ a ¿Í b ´Â µ¶¸³ÀûÀÎ ºÎ ¸ñÇ¥·Î½á ¼³Á¤µÇ¾ú´Ù. ±×·¯³ª a ¿Í b °¡ µ¿ÀÏÇÑ º¯¼ö¸¦ »ç¿ëÇÒ °æ¿ì, ÀÌµé °¢°¢¿¡ ´ëÇØ ¸ð¼øÀÌ ¾ø´Â ġȯ ´ë»óÀ» ¸¸µé ¼ö Àֱ⠶§¹®¿¡ µ¶¸³ÀûÀÎ ºÎ ¸ñÇ¥°¡ ¾Æ´Ò ¼öµµ ÀÖ´Ù. ¿¹¸¦ µé¾î ±×¸² 6 ÀÇ ¾ð¸í 3 À» »ç¿ëÇÏ´Â ´Ü°è¸¦ »ìÆì º¸ÀÚ. t1 ¿¡ 40 À» ´ëÀÔÇÔÀ¸·Î½á ¾ð¸í 3 À» »ç¿ëÇÏ¿© ¸ñÇ¥

    born (Marcus, t1)

À» ¸¸Á·½Ãų ¼ö ÀÖÁö¸¸, ¶ÇÇÑ µÎ °³ÀÇ t1 ÀÌ ¾ð¸í 4 ¿¡ ³ªÅ¸³­ °Í°ú µ¿ÀÏÇÑ º¯¼öÀ̱⠶§¹®¿¡

    gt (now-t1, 150)

¿¡ ³ªÅ¸³­ t1 ¿¡ 40 À» ´ëÀÔÇØ¾ß ÇÑ´Ù. ÈǸ¢ÇÑ Áõ¸í °úÁ¤¿¡´Â ÀÏÄ¡ÇÏ´Â °ÍÀÌ Á¸ÀçÇÏ´ÂÁö °áÁ¤ÇÏ´Â ¹æ¹ý°ú Áõ¸íÀ» ÅëÇØ ±ÕÀÏÇÏ°Ô ´ëÀÔÇÏ´Â °ÍÀ» º¸ÀåÇÏ´Â ¹æ¹ýÀÌ Æ÷ÇԵǾî¾ß ÇÑ´Ù. ÀÌ µÎ °¡Áö¸¦ À§ÇØ »ç¿ëµÇ´Â ±â¹ýÀÌ ´ÙÀ½¿¡ ¼Ò°³µÈ´Ù.

Áö±Ý±îÁö º¸¾Æ ¿Â Áõ¸íÀ¸·ÎºÎÅÍ ´ÙÀ½ µÎ °¡Áö°¡ ¸í¹éÇØÁ³´Ù :

ù¹ø° °üÂû·ÎºÎÅÍ, Áß¿äÇÑ Ãß·ÐÀ» ¼öÇàÇϱâ À§Çؼ­´Â Ãß·Ð °úÁ¤ Áß ´õ¿í °¡±õ°Ô °á·ÐÀ¸·Î À̲ô´Â ¾ð¸íÀÌ ÇÊ¿äÇÔÀ» ¾Ë ¼ö ÀÖ´Ù. ÄÄÇ»ÅͷκÎÅÍ ÀÌ ¾ð¸íÀ» ¾ò¾î³»´Â °ÍÀº ¾î·Á¿î ¹®Á¦·Î¼­, ÀÌ°Í¿¡ ´ëÇÑ ÀûÀýÇÑ ´äÀ» ¿©ÀüÈ÷ ãÁö ¸øÇß´Ù.

µÎ¹ø° »ç½Ç·ÎºÎÅÍ ÀÌ¿Í °°Àº Áõ¸íÀ» À§ÇØ ÇÊ¿äÇÑ ÀÏÀ» ¼öÇàÇÏ´Â ÇÁ·Î±×·¥À» ÀÛ¼ºÇÏ´Â °ÍÀÌ »ç½Ç»ó ½¬¿î ÀÏÀÌ ¾Æ´ÔÀ» ¾Ë ¼ö ÀÖ´Ù. ´ÙÀ½ Àý¿¡¼­´Â ¸ÕÀú ÇϳªÀÇ Á¤Çü (canonical form) À¸·Î º¯È­½Ãų ¾ð¸í¿¡ ´ëÇØ Àû¿ëÇÏ¿© º¹À⼺À» ÁÙÀÌ´Â ºñ±³ Èí¼ö ¹æ¹ý (resolution) À̶ó ºÒ¸®´Â Áõ¸í °úÁ¤À» ´Ù·ç¾ú´Ù.

4. ºñ±³ Èí¼ö ¹æ¹ý (Resolution)

¾Õ Àý¿¡¼­ ¾ð±ÞÇÑ °Íó·³, ¼­¼ú ³í¸®¿¡¼­ ¾ð¸íµéÀ» Ãß·ÐÇÒ ¶§ °ü°èµÇ´Â ¸¹Àº °úÁ¤À» ÇϳªÀÇ °úÁ¤À¸·Î ¼öÇàÇÏ´Â Áõ¸í °úÁ¤ÀÌ Á¸ÀçÇÑ´Ù¸é, °è»ê¸é¿¡¼­ º¼ ¶§ ÀÌ°ÍÀº ¸Å¿ì À¯¿ëÇÏ°Ô »ç¿ëµÉ °ÍÀÌ´Ù. ºñ±³ Èí¼ö ¹æ¹ýÀº ÀÌ Á¶°ÇÀ» ¸¸Á·ÇÏ´Â Áõ¸í °úÁ¤À¸·Î½á ¾Æ·¡ ¼³¸íÇÒ ¸Å¿ì Æí¸®ÇÑ ÇüÅ·Πº¯È¯µÈ ¾ð¸í¿¡ ´ëÇØ ÀÛ¿ëÇϱ⠶§¹®¿¡ È¿°úÀûÀÌ´Ù.

ºñ±³ Èí¼ö °úÁ¤Àº ºÎÁ¤ (refutation) ¿¡ ÀÇÇØ Áõ¸íÀ» ¼öÇàÇÑ´Ù. ´Ù½Ã ¸»ÇÏ¸é ¾ð¸íÀ» Áõ¸íÇϱâ À§ÇØ ÀÌ ¾ð¸íÀ» ºÎÁ¤ÇÏ°í, À̷κÎÅÍ ¾ò¾îÁø ¾ð¸íÀÌ ÀÌ¹Ì ¾Ë·ÁÁø ¾ð¸í°ú ¸ð¼øµÈ´Ù. ÀÌ ¹æ¹ýÀº Áõ¸íÀ» À§ÇØ Áõ¸íµÉ Á¤¸®·ÎºÎÅÍ °ø¸®·Î ÈÄÁø Ãß·ÐÇÏ´ø Áö±Ý±îÁöÀÇ ±â¹ýµé°ú ´ëÁ¶¸¦ ÀÌ·é´Ù. ÀÌ ±â¹ýÀ» ÀÚ¼¼È÷ ¼³¸íÇϱ⿡ ¾Õ¼­, ¸ÕÀú ¾ð¸íÀ» Ç¥ÁØÇü (standard form) À¸·Î Ç¥±âÇÏ´Â ¹æ¹ý¿¡ ´ëÇØ ¾Ë¾Æ º¸ÀÚ.

(1) ÀýÀÇ ÇüÅ (Clause Form) ·Î º¯È¯

¸¶Ä¿½º¸¦ ¾Ë°í ÀÖ´Â ¸ðµç ·Î¸¶ÀÎÀº ½ÃÀÌÀú¸¦ ¹Ì¿öÇÏ´Â »ç¶÷À̰ųª ȤÀº ´©±º°¡¸¦ ¹Ì¿öÇÏ´Â »ç¶÷µéÀ» ¹ÌÄ£ »ç¶÷À¸·Î °£ÁÖÇÏ´Â »ç¶÷À̶ó°í °¡Á¤ÇÏÀÚ. ÀÌ »ç½ÇÀ» wff ·Î Ç¥±âÇÏ¸é ´ÙÀ½°ú °°´Ù :

    ¢£x [Roman(x) ¡ü know(x, Marcus)]
                           ¡æ [hate(x, Caesar) ¡ý (¢£y (¢¤z hate(y, z))
                               ¡æ thinkcrazy(x, y))]

ÀÌ °ø½ÄÀ» Áõ¸í¿¡ »ç¿ëÇÒ ¶§ ¸Å¿ì º¹ÀâÇÑ ÀÏÄ¡ °úÁ¤ÀÌ ÇÊ¿äÇÏ´Ù. thinkcrazy (x, y) ¿Í °°Àº ºÎºÐÀÌ ÀÏÄ¡µÇ¾ú´Ù°í ÇÒ ¶§, ÀÌ ÀÏÄ¡µÈ ºÎºÐÀÌ »ðÀԵǾî ÀÖ´Â ºÎºÐ°ú »ðÀԵǾî ÀÖÁö ¾Ê´Â ºÎºÐÀ» Æ÷ÇÔÇÏ°í ÀÖ´Â °ø½ÄÀÇ ³ª¸ÓÁö¸¦ ÀûÀýÈ÷ ó¸®ÇØ¾ß ÇÑ´Ù. ¸¸¾à °£´ÜÇÑ ÇüÅ·Π°ø½ÄÀÌ Ç¥ÇöµÇ¾ú´Ù¸é, ºñ±³Àû ½±°Ô ÀÌ°ÍÀ» ó¸®ÇÒ ¼ö ÀÖ´Ù. ´ÙÀ½°ú °°Àº »óȲÀ̶ó¸é °ø½ÄÀ» ½±°Ô ó¸®ÇÒ ¼ö ÀÖ´Ù :

³í¸®°öÀÇ Á¤±ÔÇü (conjunctive normal form) Àº ÀÌ ¼ºÁúÀ» ¸ðµÎ °¡Áö°í ÀÖ´Ù. ¿¹¸¦ µé¾î, À§¿¡ ÁÖ¾îÁø »ç½ÇÀ» ³í¸®°öÀÇ Á¤±ÔÇüÀ¸·Î Ç¥±âÇÏ¸é ´ÙÀ½°ú °°´Ù :

    ~Roman(x) ¡ý ~know(x, Marcus) ¡ý hate(x, Caesar) ¡ý ~hate(y, z) ¡ý thinkcrazy(x, z)

wff ¸¦ ³í¸®°öÀÇ Á¤±ÔÇüÀ¸·Î º¯È¯½ÃÅ°´Â ¾Ë°í¸®ÁòÀÌ Àֱ⠶§¹®¿¡, ÀÌ ÇüÅ·Π¹Ù²ï wff ¿¡¸¸ Àû¿ëÇÏ´Â Áõ¸í °úÁ¤ (¿¹, ºñ±³ Èí¼ö ¹æ¹ý) À» »ç¿ëÇصµ ÀϹݼºÀº »ó½ÇµÇÁö ¾Ê´Â´Ù.

wff ¸¦ ³í¸®°öÀÇ Á¤±ÔÇüÀ¸·Î º¯È¯½ÃÅ°±â À§ÇØ, ´ÙÀ½°ú °°Àº ÀÏ·ÃÀÇ ´Ü°è¸¦ ¼öÇàÇÑ´Ù :

    1. a ¡æ b ¿Í ~a ¡ý b °¡ µ¿Ä¡¶ó´Â »ç½ÇÀ» ÀÌ¿ëÇÏ¿©, ¡æ À» Á¦°ÅÇÑ´Ù. À§¿¡ ÁÖ¾îÁø wff ¸¦ ÀÌ°ÍÀ¸·Î º¯È¯½ÃÅ°¸é ´ÙÀ½°ú °°´Ù :

            ¢£x ~[Roman(x) ¡ü know(x, Marcus)]
            ¡ý [hate(x, Caesar) ¡ý (¢£y ~(¢¤z hate(y, z))
                    ¡ý thinkcrazy(x, y))]

    2. ~(~p) = p ¿Í ~¢£xp(x) = ¢¤x~p(x) ¿Í ~¢¤xp(x) = ¢£x~p(x) ¶ó´Â »ç½ÇÀ» ÀÌ¿ëÇÏ¿© ~ ÀÇ ¹üÀ§¸¦ Ãà¼ÒÇÑ´Ù. ´Ü°è 1 ·ÎºÎÅÍ ¾òÀº wff ¿¡ ÀÌ ÀüÀ̸¦ ¼öÇàÇϸé

            ¢£x[~Roman(x) ¡ý ~know(x, Marcus)]
            ¡ý [hate(x, Caesar) ¡ý (¢£y¢£z ~hate(y, z)
                     ¡ý thinkcrazy(x, y))]

        ¸¦ ¾ò°Ô µÈ´Ù.

    3. °¢ ÇÑÁ¤»ç°¡ ±ÕÀÏÇÑ º¯¼ö¿Í °áÇյǵµ·Ï º¯¼ö¸¦ Ç¥ÁØÈ­ÇÑ´Ù. º¯¼ö´Â °¡»ó À̸§À̱⠶§¹®¿¡, ÀÌ °úÁ¤ÀÌ wff ÀÇ Áø¸®°ª¿¡ ¿µÇâÀ» ¹ÌÄ¡Áö ¾Ê´Â´Ù. ¿¹¸¦ µé¾î, ´ÙÀ½ °ø½Ä

            ¢£xP(x) ¡ý ¢£xQ(x)

        ´Â

            ¢£xP(x) ¡ý ¢£yQ(y)

        ·Î ¹Ù²Ü ¼ö ÀÖ´Ù. ÀÌ ´Ü°è´Â ´ÙÀ½ ´Ü°èÀÇ Áغñ ´Ü°èÀÌ´Ù.

    4. »ó´ëÀû ¼ø¼­´Â º¯È­½ÃÅ°Áö ¾Ê°í, °ø½ÄÀÇ ÁÂÃø¿¡ Ç¥±âµÈ ÇÑÁ¤»ç¸¦ À̵¿½ÃŲ´Ù. º¯¼ö À̸§ °£¿¡ ¾î¶² Ãæµ¹µµ ¹ß»ýÇÏÁö ¾Ê±â ¶§¹®¿¡ ÀÌ°ÍÀÌ °¡´ÉÇÏ´Ù. ´Ü°è 2 ¿¡¼­ ¾òÀº °ø½Ä¿¡ ÀÌ ÀÛ¾÷À» ¼öÇàÇϸé

            ¢£x¢£y¢£z[~Roman(x) ¡ý ~know(x, Marcus)]
            ¡ý [hate(x, Caesar) ¡ý (~hate(y, z)
                     ¡ý thinkcrazy(x, y))]

        ¸¦ ¾ò´Â´Ù. ÀÌ·¸°Ô ¾òÀº °ø½ÄÀ» ÇÁ¸®³Ø½º Á¤±ÔÇü (prenex normal form) À¸·Î Ç¥±âµÇ¾ú´Ù°í ÇÑ´Ù. ÇÁ¸®³Ø½º Á¤±ÔÇüÀº ÇÑÁ¤»ç¸¦ Á¢µÎ»ç·Î ÇÏ¿© ±× ´ÙÀ½¿¡ ÇÑÁ¤»ç¿¡ ¿µÇâÀ» ¹ÞÁö ¾Ê´Â ¸ðÇüÀÌ µÚµû¶ó ³ª¿Â´Ù.

    5. Á¸Àç ÇÑÁ¤ ±âÈ£ (existential quantifier) ¸¦ Á¦°ÅÇÑ´Ù. Á¸Àç ÇÑÁ¤ ±âÈ£·Î ÇÑÁ¤µÈ º¯¼ö¸¦ Æ÷ÇÔÇÑ °ø½ÄÀº ÀÌ °ø½ÄÀ» ÂüÀ¸·Î ¸¸µå´Â °ªÀÌ Á¸ÀçÇÔÀ» ³ªÅ¸³½´Ù. ¿øÇÏ´Â °ªÀ» ¸¸µå´Â ÇÔ¼ö¸¦ ºÒ·¯ º¯¼ö¿¡ ´ëÄ¡½ÃÅ´À¸·Î½á, ÇÑÁ¤»ç¸¦ Á¦°ÅÇÒ ¼ö ÀÖ´Ù. »ç½Ç»ó °ªÀ» ¸¸µå´Â ¹æ¹ýÀº ¾Ë ÇÊ¿ä°¡ ¾ø±â ¶§¹®¿¡, ¸ðµç ġȯ¿¡ ´ëÇØ »õ·Î¿î ÇÔ¼ö ¸íĪÀ» »ç¿ëÇØ¾ß Çϸç, À̶§ ´ÜÁö ÀÌ·± ÇÔ¼ö°¡ Á¸ÀçÇÏ´ÂÁö¸¸ ¾Ë¸é µÈ´Ù. ¿¹¸¦ µé¾î, °ø½Ä

            ¢¤y President(y)

        ¸¦

            President(S1)

        ·Î ¹Ù²Ü ¼ö ÀÖ´Ù. ¿©±â¼­ s1 Àº ¸Å°³ º¯¼ö°¡ ¾øÀÌ President ¸¦ ¸¸Á·½ÃÅ°´Â °ªÀ» ¸¸µå´Â ÇÔ¼öÀÌ´Ù.

        ¸¸¾à Á¸Àç ÇÑÁ¤ ±âÈ£°¡ Àüü ÇÑÁ¤ ±âÈ£ (universal quantifier) ÀÇ ¹üÀ§ ³»¿¡ ¹ß»ýÇÑ´Ù¸é ¼­¼úÇü ¸íÁ¦¸¦ ¸¸Á·½ÃÅ°´Â °ªÀº Àüü ÇÑÁ¤ ±âÈ£·Î ÇÑÁ¤µÈ º¯¼öÀÇ °ª¿¡ ÀÇÇØ °áÁ¤µÈ´Ù. ¿¹¸¦ µé¾î, °ø½Ä

            ¢£x¢¤y fatherof (y, x)

        ¿¡¼­, fatherof ¸¦ ¸¸Á·½ÃÅ°´Â y ÀÇ °ªÀº ƯÁ¤ÇÑ x ÀÇ °ª¿¡ ÀÇÇØ °áÁ¤µÈ´Ù. µû¶ó¼­ ½Ä¿¡ Æ÷ÇÔµÈ Àüü ÇÑÁ¤ ±âÈ£ÀÇ ¼ö¿Í µ¿ÀÏÇÑ ¼öÀÇ ¸Å°³ º¯¼ö¸¦ °¡Áø ÇÔ¼ö¸¦ ¸¸µé¾î¾ß¸¸ ÇÑ´Ù. µû¶ó¼­ ÀÌ ¿¹¸¦ ´ÙÀ½°ú °°ÀÌ ¹Ù²Ü ¼ö ÀÖ´Ù :

            ¢£x fatherof (S2(x), x)

        ÀÌ·¸°Ô ¸¸µé¾îÁø ÇÔ¼ö¸¦ ½ºÄÝ·¥ ÇÔ¼ö (Skolem function) ¶ó Çϸç, ¾î¶² ¸Å°³ º¯¼öµµ °¡Áö°í ÀÖÁö ¾ÊÀº ½ºÄÝ·¥ ÇÔ¼ö¸¦ ½ºÄÝ·¥ »ó¼ö (Skolem constant) ¶ó ÇÑ´Ù.

    6. Á¢µÎ»ç¸¦ Á¦°ÅÇÑ´Ù. ³²¾Æ ÀÖ´Â º¯¼öµéÀº Àüü ÇÑÁ¤ ±âÈ£·Î ÇÑÁ¤µÈ º¯¼öµéÀ̱⠶§¹®¿¡, Á¢µÎ»ç¸¦ »ý·«ÇÒ ¼ö ÀÖ°í, »ç¿ëµÉ ¾î¶² Áõ¸í °úÁ¤¿¡¼­µçÁö °ø½Ä¿¡ ³ªÅ¸³­ º¯¼ö°¡ Àüü ÇÑÁ¤ ±âÈ£·Î ÇÑÁ¤µÈ º¯¼ö¶ó°í °¡Á¤ÇÒ ¼ö ÀÖ´Ù. ´Ü°è 4 ¿¡¼­ ¾òÀº °ø½ÄÀ»

            ~Roman(x) ¡ý ~know(x, Marcus) ¡ý hate(x, Caesar)
           ¡ý ~hate(y, z) ¡ý thinkcrazy(x, y)

        ¸¦ ¾ò´Â´Ù. ±×·¯³ª ¹èºÐ ¹ýÄ¢ [(a ¡ü b) ¡ý c) = (a ¡ý c) ¡ü (b ¡ý c)] À» »ç¿ëÇØ¾ß ÇÒ °æ¿ì°¡ ÀÖ´Ù. ¿¹¸¦ µé¾î, °ø½Ä

            (winter ¡ü wearingboots) ¡ý (summer ¡ü wearingsandals)

        ¸¦

            [winter ¡ý (summer ¡ü wearingsandals)]
           ¡ü [wearingboots
               ¡ý (summer ¡ü wearingsandals)]

        ·Î ¹Ù²Ü ¼ö ÀÖ´Ù. ³í¸®ÇÕÀ¸·Î °áÇÕµÈ ³í¸®°ö ÀÎÀÚ°¡ Æ÷ÇԵǾî Àֱ⠶§¹®¿¡, À̸¦

            (winter ¡ý summer)
       ¡ü (winter ¡ý wearingsandals)
       ¡ü (wearingboots ¡ý summer)
       ¡ü (wearngboots ¡ý wearingsandals)

        ·Î ¹Ù²Ü ¼ö ÀÖ´Ù.

    8. °¢ ³í¸®°ö ÀÎÀÚ¸¦ µ¶¸³µÈ Àý (clause) À̶ó ºÎ¸¥´Ù. wff °¡ ÂüÀ̱â À§Çؼ­´Â, ÀÌ°ÍÀ¸·ÎºÎÅÍ ¾òÀº ¸ðµç ÀýÀÌ ÂüÀ̾î¾ß ÇÑ´Ù. ¸¸¾à ¿©·¯ °³ÀÇ wff µéÀ» »ç¿ëÇÒ °æ¿ì, º»·¡ wff µé¿¡ ÀÇÇØ Ç¥±âµÇ¾ú´ø °Í°ú µ¿ÀÏÇÑ »ç½ÇµéÀ» Ç¥±âÇϱâ À§ÇØ ÀÌµé °¢°¢À¸·ÎºÎÅÍ ¾òÀº ¸ðµç ÀýÀ» °áÇÕÇÒ ¼ö ÀÖ´Ù.

    9. ´Ü°è 8 ·ÎºÎÅÍ ¾òÀº Àý ¼Ó¿¡ ³ªÅ¸³­ º¯¼öµéÀ» Ç¥ÁØÈ­ÇÑ´Ù. ÀÌ·¸°Ô ÇÔÀ¸·Î½á ¾î¶² µÎ °³ÀÇ Àýµµ µ¿ÀÏÇÑ º¯¼ö¸¦ ¾ð±ÞÇÏÁö ¸øÇϵµ·Ï º¯¼öµéÀ» ¸íÇÒ ¼ö ÀÖ´Ù. À̸¦ À§ÇØ

            (¢£xP(x) ¡ü Q(x)) = ¢£xP(x) ¡ü ¢£xQ(x)

        ¶ó´Â »ç½ÇÀ» ÀÌ¿ëÇÑ´Ù. °¢ ÀýÀÌ µ¶¸³ÀûÀÎ ³í¸®°ö ÀÎÀÚÀ̸ç, º¯¼öµéÀÌ Àüü ÇÑÁ¤ ±âÈ£·Î ÇÑÁ¤µÇ¾ú±â ¶§¹®¿¡, ºñ·Ï µ¿ÀÏÇÑ wff ·Î ¾ò¾îÁø º¯¼ö¶ó ÇÒÁö¶óµµ, µÎ ÀýÀÇ º¯¼öµé °£¿¡ ¾î¶² °ü°è¸¦ ÁöÀ» ÇÊ¿ä´Â ¾ø´Ù.

ºñ±³ Èí¼ö °úÁ¤ µ¿¾È ¶§¶§·Î Àüü ÇÑÁ¤ ±âÈ£·Î ÇÑÁ¤µÈ º¯¼ö¿¡ ƯÁ¤ÇÑ °ªÀ» ġȯÇÒ ÇÊ¿ä°¡ Àֱ⠶§¹®¿¡, Ç¥ÁØÈ­¸¦ ¼öÇàÇÏ´Â ¸¶Áö¸· ´Ü°è°¡ Áß¿äÇÑ Àǹ̸¦ °¡Áø´Ù. ±×·¯³ª ´ëºÎºÐÀÇ °æ¿ì, °¡Àå ÀϹÝÀûÀÎ ÇüÅ·Î, °¡´ÉÇÑ ÇÑ ¿À·§µ¿¾È ÀýÀ» À¯Áö½ÃÄÑ¾ß ÇÑ´Ù. µû¶ó¼­ º¯¼ö¿¡ ƯÁ¤ÇÑ °ªÀ» ġȯÇÒ ¶§, ġȯÇÒ °ªÀÇ ÃÖ¼Ò°ªÀ» ±â¾ïÇÏ¿©, ½Ã½ºÅÛÀÇ Áø¸®°ªÀ» º¸Á¸½ÃÄÑ¾ß ÇÑ´Ù.

wff ¿¡ À§ÀÇ Àüü °úÁ¤À» Àû¿ëÇÔÀ¸·Î½á, ÀýÀ» ¾Ë°Ô µÇ´Âµ¥, °¢ ÀýÀº ¹®ÀÚ (literal) ¸¦ ³í¸®ÇÕÀ¸·Î ¿¬°áÇÑ °ÍÀÌ´Ù. ÀÌ ÀýµéÀº ºñ±³ Èí¼ö °úÁ¤¿¡ »ç¿ëµÇ¾î Áõ¸íÀ» ¸¸µç´Ù.

(2) ºñ±³ Èí¼ö °úÁ¤ÀÇ ±âº» ¿ø¸®

ºñ±³ Èí¼ö °úÁ¤Àº °£´ÜÇÑ ¼øȯ °úÁ¤À¸·Î½á, ¸Å ´Ü°è¸¶´Ù ºÎ¸ðÀý (parent clause) À̶ó ºÒ¸®´Â µÎ °³ÀÇ ÀýÀ» ºñ±³ÇÏ°í, À̵é·ÎºÎÅÍ »õ·Î¿î ÀýÀ» Ãß·ÐÇÏ´Â °ÍÀÌ´Ù. »õ·ÎÀÌ ¾òÀº ÀýÀº µÎ °³ÀÇ ºÎ¸ðÀýÀÌ ¼­·Î »óÈ£ ÀÛ¿ëÇÏ´Â ¹æ¹ýÀ» ³ªÅ¸³½´Ù. ´ÙÀ½ µÎ °³ÀÇ ÀýÀ» »ìÆì º¸ÀÚ :

    winter ¡ý summer
    ~winter ¡ý cold

ÀÌ°ÍÀº µÎ ÀýÀÌ ¸ðµÎ ÂüÀÓÀ» ÀǹÌÇÑ´Ù. ¾ðÁ¦³ª winter ¿Í ~winter ÁßÀÇ Çϳª´Â ÂüÀÌ´Ù. ¸¸¾à winter °¡ ÂüÀ̶ó¸é, µÎ¹ø° ÀýÀ» ÂüÀ¸·Î À¯ÁöÇϱâ À§Çؼ­´Â, cold °¡ ÂüÀ̾î¾ß ÇÑ´Ù. ¸¸¾à ~winter °¡ ÂüÀ̶ó¸é, ù¹ø° ÀýÀ» ÂüÀ¸·Î À¯ÁöÇϱâ À§ÇØ, summer °¡ ÂüÀ̾î¾ß ÇÑ´Ù. µû¶ó¼­, ÀÌ µÎ °³ÀÇ Àý·ÎºÎÅÍ

    summer ¡ý cold

¸¦ Ãß·ÐÇÒ ¼ö ÀÖ´Ù. ÀÌ°ÍÀº ºñ±³ Èí¼ö °úÁ¤¿¡ ÀÇÇØ ¸¸µé¾îÁø ¿¬¿ª Ãß·ÐÀÌ´Ù. ºñ±³ Èí¼ö ¹æ¹ýÀº °°Àº ¹®ÀÚ - ¿©±â¼­´Â winter - ¸¦ Æ÷ÇÔÇÏ°í ÀÖ´Â µÎ °³ÀÇ ÀýÀ» ÅÃÇØ ÀÌ°Í¿¡ ´ëÇØ ÀÛ¿ëÇÑ´Ù. ¹®ÀÚ´Â ¹Ýµå½Ã ÇÑ Àý¿¡¼­´Â ±àÁ¤ÀÇ ÇüÅ·Î, ´Ù¸¥ ÇÑ Àý¿¡¼±´À ºÎÁ¤ÀÇ ÇüŸ¦ ³ªÅ¸³»¾ß ÇÑ´Ù. Á¦°ÅµÇ´Â ¹®ÀÚ¸¦ Á¦¿ÜÇÏ°í µÎ °³ÀÇ ºÎ¸ðÀý¿¡ ³ªÅ¸³­ ¸ðµç ¹®ÀÚ¸¦ °áÇÕÇÏ¿© ÇϳªÀÇ ºñ±³ Èí¼öÀý (resolvent) ¸¦ ¾ò´Â´Ù.

¸¸¾à ¾ò¾îÁø ÀýÀÌ ¾î¶² ¹®ÀÚµµ °¡Áö°í ÀÖÁö ¾Ê´Â ÀýÀ̶ó¸é, ¸ð¼øÀÌ ¹ß°ßµÈ °ÍÀÌ´Ù. ¿¹¸¦ µé¾î, µÎ °³ÀÇ Àý

    winter
    ~winter

·ÎºÎÅÍ ¾ò¾îÁö´Â ºñ±³ Èí¼öÀý¿¡´Â ¾î¶² ¹®ÀÚµµ Æ÷ÇԵǾî ÀÖÁö ¾Ê´Ù. ¸¸¾à ¸ð¼øÀÌ Á¸ÀçÇÑ´Ù¸é, ÀÌ ¸ð¼øÀº ¹Ýµå½Ã ¹ß°ßµÈ´Ù. ¸¸¾à ¾î¶² ¸ð¼øµµ Á¸ÀçÇÏÁö ¾Ê´Â´Ù¸é, ºñ·Ï ÀÌ »ç½ÇÀ» ŽÁöÇÒ ¼ö ÀÖ´Â ¹æ¹ýÀÌ ÀÖ´õ¶óµµ, ¾ÕÀÇ °úÁ¤ÀÌ ¹«ÇÑÈ÷ °è¼ÓµÉ °¡´É¼ºÀÌ ÀÖ´Ù.

Áö±Ý±îÁö ¸íÁ¦ ³í¸®¿¡¼­ÀÇ ºñ±³ Èí¼ö ¹æ¹ý¿¡ ´ëÇØ ¾Ë¾Æ º¸¾Ò´Ù. ¼­¼ú ³í¸®¿¡ À־´Â, º¯¼ö¿¡ ġȯµÉ °ªµéÀÇ ¸ðµç °¡´É¼ºÀ» °í·ÁÇØ¾ß Çϱ⠶§¹®¿¡, ¸Å¿ì º¹ÀâÇÏ´Ù. ¼­¼ú ³í¸®ÀÇ ºñ±³ Èí¼ö °úÁ¤¿¡ ´ëÇÑ ÀÌ·ÐÀûÀÎ ±âº» ¿ø¸®´Â Çãºê¶õµåÀÇ Á¤¸® (Herbrand's theorem) ·Î½á, ´ÙÀ½°ú °°Àº °ÍÀ» ¾Ë·Á ÁØ´Ù :

¾î¶² °úÁ¤µµ À¯ÇÑ ½Ã°£ ³»¿¡ ¹«ÇÑ ÁýÇÕÀ» Á¶»çÇÒ ¼ö ¾ø±â ¶§¹®¿¡, ºÒ¸¸Á·¼º (unsatisfiability) À» Áõ¸íÇÏ´Â °è»ê °¡´ÉÇÑ ¾î¶² °úÁ¤ÀÌ Á¸ÀçÇØ¾ß ÇÒ °æ¿ì, À§ Á¤¸®ÀÇ µÎ¹ø° ºÎºÐÀº Áß¿äÇÑ Àǹ̸¦ °¡Áø´Ù. ü°èÀûÀ¸·Î, °¡´ÉÇÑ ¸ðµç ġȯ ´ë»óÀ» ã¾Æ °¢°¢ÀÌ ¸ð¼øÀ» À¯µµÇÏ´ÂÁö Á¶»çÇÔÀ¸·Î½á ¸ð¼øÀ» ãÀ» ¼ö ÀÖ´Ù´Â °ÍÀ» ù¹ø° »ç½Ç·ÎºÎÅÍ ¾Ë ¼ö ÀÖ´Ù. ±×·¯³ª ÀÌ°ÍÀº ¸Å¿ì ºñÈ¿À²ÀûÀÎ ¹æ¹ýÀÌ´Ù. ºñ±³ Èí¼ö ¹æ¹ýÀÇ ¿øÄ¢À¸·ÎºÎÅÍ, ÃÖ¼Ò ¼öÀÇ Ä¡È¯ ´ë»óÀ» ã¾Æ Á¶»çÇÔÀ¸·Î½á ¸ð¼øÀ» ãÀ» ¼ö ÀÖ´Ù´Â °ÍÀ» ù¹ø° »ç½Ç·ÎºÎÅÍ ¾Ë ¼ö ÀÖ´Ù. ±×·¯³ª ÀÌ°ÍÀº ¸Å¿ì ºñÈ¿À²ÀûÀÎ ¹æ¹ýÀÌ´Ù. ºñ±³ Èí¼ö ¹æ¹ýÀÇ ¿øÄ¢À¸·ÎºÎÅÍ, ÃÖ¼Ò ¼öÀÇ Ä¡È¯ ´ë»óÀ» ã¾Æ Á¶»çÇÔÀ¸·Î½á ¸ð¼øÀ» ãÀ» ¼ö ÀÖ´Ù. °¡´ÉÇÑ ÇÑ ¿À·§µ¿¾È ÀýÀ» ÀϹÝÀûÀÎ ÇüÅ·ΠÀ¯ÁöÇϸ鼭 ÇÊ¿ä¿¡ µû¶ó ƯÁ¤ÇÑ Ä¡È¯ ´ë»óÀ» ã¾Æ³»´Â °ÍÀº ºñ±³ Èí¼ö ¹æ¹ýÀÇ Áß¿äÇÑ ±âº» °³³äÀÌ´Ù.

(3) ¸íÁ¦ ³í¸®¿¡¼­ÀÇ ºñ±³ Èí¼ö ¹æ¹ý

ºñ±³ Èí¼ö °úÁ¤ÀÇ Àû¿ë ¹æ¹ýÀ» ¸í¹éÈ÷ Çϱâ À§ÇØ, ¸ÕÀú ¸íÁ¦ ³í¸®¿¡¼­ÀÇ ºñ±³ Èí¼ö °úÁ¤À» »ìÆì º» ÈÄ, ÀÌ°ÍÀ» ¼­¼ú ³í¸®±îÁö È®Àå½ÃÄÑ ¾Ë¾Æ º¸ÀÚ.

¸íÁ¦ ³í¸®¿¡¼­, °ø¸®ÀÇ ÁýÇÕ F ¿¡ ´ëÇØ ¸íÁ¦ S ¸¦ ºñ±³ Èí¼öÇÏ¿© Áõ¸íÀ» ¾ò´Â °úÁ¤Àº ´ÙÀ½°ú °°´Ù :

    1. F ÀÇ ¸ðµç ¸íÁ¦¸¦ ÀýÀÇ ÇüŸ¦ º¯È¯ÇÑ´Ù.

    2. S ÀÇ ºÎÁ¤ÇÏ°í, ÀÌ°ÍÀ» ÀýÀÇ ÇüŸ¦ º¯È¯ÇÑ´Ù. ´Ü°è 1 ·ÎºÎÅÍ ¾òÀº ÀýÀÇ ÁýÇÕ¿¡ ÀÌ°ÍÀ» ÷°¡ÇÑ´Ù.

    3. ¸ð¼øÀÌ ¹ß°ßµÇ°Å³ª, ¾î¶² Áøº¸µµ ¸¸µé¾îÁöÁö ¾ÊÀ» ¶§±îÁö ´ÙÀ½À» ¹Ýº¹Ç϶ó :
1) µÎ °³ÀÇ ÀýÀ» ¼±ÅÃÇÑ´Ù. ÀÌ°ÍÀ» ºÎ¸ðÀýÀ̶ó ºÎ¸¥´Ù.
2) À̵éÀ» ÇÔ²² ºñ±³ Èí¼öÇÑ´Ù. ºñ±³ Èí¼öÀýÀ̶ó ºÒ¸®´Â »õ·ÎÀÌ ¾òÀº ÀýÀº ´ÙÀ½ÀÇ ¿¹¿Ü¸¦ °¡Áö°í ºÎ¸ðÀý¿¡ Æ÷ÇÔµÈ ¸ðµç ¹®ÀÚµéÀ» ³í¸®ÇÕÀ¸·Î °áÇÕÇÑ °ÍÀÌ´Ù : ¸¸¾à ÇÑ ºÎ¸ðÀýÀÌ L À», ´Ù¸¥ ÇÑ ºÎ¸ðÀýÀÌ ~L À» Æ÷ÇÔÇÑ ±×·± L °ú ~L ÀÇ ½ÖÀÌ Á¸ÀçÇÑ´Ù¸é, ºñ±³ Èí¼öÀý¿¡¼­ L °ú ~L À» ¸ðµÎ Á¦°ÅÇÑ´Ù.
3) ºñ±³ Èí¼öÀýÀÌ ¾î¶² ¹®ÀÚµµ Æ÷ÇÔÇÏÁö ¾ÊÀº ÀýÀ̶ó¸é ¸ð¼øÀÌ ¹ß°ßµÈ °ÍÀÌ´Ù. ¸¸¾à ±×·¸Áö ¾Ê´Ù¸é, ÀÌ °úÁ¤¿¡¼­ ÀÌ¿ë °¡´ÉÇÑ ÀýÀÇ ÁýÇÕ¿¡ »õ·ÎÀÌ ¾òÀº ºñ±³ Èí¼öÀýÀ» ÷°¡ÇÑ´Ù.

ÁÖ¾îÁø °ø¸®

Àý ÇüÅ·ÎÀÇ º¯È¯

 

      p

      (p ¡ü q) ¡æ r

      (s ¡ý t) ¡æ q

       

      t

      p

      ~p ¡ý ~q ¡ý r

      ~s ¡ý q

      ~t ¡ý q

      t

1.

2.

3.

4.

5.

±×¸² 7

°£´ÜÇÑ ¿¹¸¦ »ìÆì º¸ÀÚ. ±×¸² 7 ÀÇ Ã¹¹ø° Çà°ú °°Àº °ø¸®°¡ ÁÖ¾îÁ³À» ¶§, r À» Áõ¸íÇÏ°íÀÚ ÇÑ´Ù. ¸ÕÀú ±×¸²ÀÇ µÎ¹ø° Çà¿¡ º¸¿©Áø °Íó·³, °ø¸®¸¦ ÀýÀÇ ÇüÅ·Πº¯È¯½ÃÄÑ¾ß ÇÑ´Ù. ±× ´ÙÀ½, ÀÌ¹Ì ÀýÀÇ ÇüÅ ¼Ó¿¡ ³ªÅ¸³­ r À» ºÎÁ¤ÇÏ¿©, ~r À» ¾òÀº ÈÄ, ºñ±³ Èí¼ö¸¦ ¼öÇàÇϱâ À§ÇØ ÇÔ²² »ç¿ëµÉ ÀýµéÀÇ ½ÖÀ» ¼±ÅÃÇÑ´Ù. ºñ·Ï ÀýÀÇ ¾î´À ½ÖÀÌ¶óµµ ºñ±³ Èí¼öµÉ ¼ö ÀÖÁö¸¸, ÀÌ ¹®ÀÚ (complementary literal) °¡ Æ÷ÇԵǾî ÀÖ´Â ½ÖÀ» ÀÌ¿ëÇÏ¿©, ¾î¶² ¹®ÀÚµµ Æ÷ÇԵǾî ÀÖÁö ¾Ê´Â ÀýÀ» À¯µµÇÒ °¡´É¼ºÀÌ ³ôÀº ºñ±³ Èí¼öÀýÀ» ¾ò´Â´Ù. ¿¹¸¦ µé¾î, ±×¸² 8 ¿¡ º¸¿©Áø ÀÏ·ÃÀÇ ºñ±³ Èí¼öÀýÀ» ¾òÀ» ¼ö ÀÖ´Ù. Àý ~r Àº ã°íÀÚ ÇÏ´Â ¸ð¼ø°ú °ü·ÃµÈ Àý ÁßÀÇ ÇϳªÀÌ´Ù. µû¶ó¼­ ÀÌ ÀýÀ» ºñ±³ Èí¼ö °úÁ¤ÀÇ ½ÃÀÛ¿¡ »ç¿ëÇÑ´Ù.

±×¸² 8  ¸íÁ¦ ³í¸®¿¡¼­ ºñ±³ Èí¼ö ¹æ¹ý

ºñ±³ Èí¼ö °úÁ¤Àº ¸ðµÎ ÂüÀ¸·Î °¡Á¤µÈ ÀýµéÀÇ ÁýÇÕÀ» »ç¿ëÇÏ´Â °úÁ¤À¸·Î º¼ ¼ö ÀÖ´Ù. ´Ù¸¥ Àý·ÎºÎÅÍ ¾òÀº Á¤º¸¸¦ ±âÃÊ·Î ÇÏ¿©, ÀÌ ¹æ¹ý¿¡ ÀÇÇØ »õ·Î¿î ÀýÀÌ ¾ò¾îÁø´Ù. »õ·ÎÀÌ ¾òÀº ÀýÀº ¿ø·¡ ÀÖ´ø ÀýµéÀ» ÂüÀ¸·Î À¯ÁöÇϱâ À§ÇØ °¡ÇØÁ®¾ß ÇÒ Á¦ÇÑ Á¶°ÇÀ» ³ªÅ¸³½´Ù. ÀýÀ» ÂüÀ¸·Î À¯ÁöÇÒ ¼ö ¾øÀ» ¸¸Å­, ÀÌ ÀýÀÌ Á¦ÇÑÀ» ¹Þ°Ô µÉ ¶§, ¸ð¼øÀÌ ¹ß»ýÇÑ °ÍÀÌ´Ù. ÀÌ°ÍÀº ¾î¶² ¹®ÀÚµµ Æ÷ÇÔÇÏÁö ¾Ê´Â ÀýÀ» ¾òÀ½À¸·Î½á ¾Ë ¼ö ÀÖ´Ù. ¾ÕÀÇ ¿¹¸¦ »ç¿ëÇÏ¿© ÀÌ°ÍÀÇ ÀÛ¿ë ¹æ¹ý¿¡ ´ëÇØ ¾Ë¾Æ º¸ÀÚ. ¸íÁ¦ 2 °¡ ÂüÀ¸·Î À¯ÁöµÇ±â À§Çؼ­´Â, ~p, ~q ȤÀº r ÁßÀÇ Çϳª°¡ ÂüÀ̾î¾ß ÇÑ´Ù. ±×·¯³ª ~r ÀÌ ÂüÀ̶ó°í °¡Á¤Ç߱⠶§¹®¿¡ ¸íÁ¦ 2 ¸¦ ÂüÀ¸·Î À¯ÁöÇϱâ À§Çؼ­´Â, ~p ³ª ~q °¡ ÂüÀ̾î¾ß ÇÑ´Ù. ù¹ø°·Î ¾òÀº ºñ±³ Èí¼öÀýÀº ÀÌ°ÍÀ» ³ªÅ¸³½´Ù. ¸íÁ¦ 1 Àº p °¡ ÂüÀ̶ó´Â °Í, Áï ~p °¡ °ÅÁþÀ̶ó´Â °ÍÀ» ³ªÅ¸³»±â ¶§¹®¿¡, ¸íÁ¦ 2 ¸¦ ÂüÀ¸·Î À¯ÁöÇϱâ À§Çؼ­´Â ~t ³ª q °¡ ÂüÀ̾î¾ß ÇÑ´Ù. ±×·¯³ª ¹Ýµå½Ã ~q °¡ ÂüÀ̾î¾ß Çϱ⠶§¹®¿¡, ¸íÁ¦ 4 ¸¦ ÂüÀ¸·Î À¯ÁöÇϱâ À§Çؼ­´Â ~t °¡ ÂüÀ̾î¾ß ÇÑ´Ù (ÀÌ°ÍÀº ¼¼¹ø° ºñ±³ Èí¼öÀý¿¡ ÀÇÇØ Ç¥±âµÇ¾ú´Ù). ¸íÁ¦ 5 ´Â t °¡ ÂüÀÓÀ» ³ªÅ¸³½´Ù. µû¶ó¼­ ¸ðµç ÀýÀ» ÂüÀ¸·Î À¯Áö½Ãų ¹æ¹ýÀº ¾ø´Ù. ¾î¶² ¹®ÀÚµµ Æ÷ÇԵǾî ÀÖÁö ¾ÊÀº ÀýÀ» ¾òÀ½À¸·Î½á, ÀÌ »ç½ÇÀ» ¾Ë ¼ö ÀÖ´Ù.

(4) ´ÜÀÏÈ­ ¾Ë°í¸®Áò (Unification Algorithm)

¸íÁ¦ ³í¸®ÀÇ °æ¿ì, µÎ °³ÀÇ ¹®ÀÚ°¡ µ¿½Ã¿¡ ÂüÀÌ µÉ ¼ö ¾ø´Ù´Â °ÍÀº ½±°Ô °áÁ¤µÈ´Ù. °£´ÜÇÑ ¿¹·Î L °ú ~L À» »ìÆì º¸ÀÚ. ¼­¼ú ³í¸®¿¡¼­´Â º¯¼öÀÇ ¹ÙÀεùÀ» °í·ÁÇØ¾ß Çϱ⠶§¹®¿¡ ÀÌ ÀÏÄ¡ °úÁ¤ÀÌ ´õ¿í º¹ÀâÇÏ´Ù. ¿¹¸¦ µé¾î man (Henry) ¿Í man (Spot) Àº ¸ð¼øÀÌ ¾Æ´Ï´Ù. ±×·¯³ª man (Henry) ¿Í ~man (Henry) ´Â ¸ð¼øÀÌ´Ù. ¸ð¼øÀ» °áÁ¤Çϱâ À§Çؼ­´Â, µÎ °³ÀÇ ¹®ÀÚ¸¦ ºñ±³ÇÏ¿© ÀÌ°ÍÀ» µ¿ÀÏÇÑ °ÍÀ¸·Î ¸¸µé ¼ö Àִ ġȯ ´ë»óÀÌ Á¸ÀçÇÏ´ÂÁö °áÁ¤ÇÏ´Â ÀÏÄ¡ °úÁ¤ÀÌ ÇÊ¿äÇÏ´Ù. ´ÜÀÏÈ­ ¾Ë°í¸®ÁòÀ̶ó ºÒ¸®´Â ¼øȯ °úÁ¤Àº À̸¦ À§ÇØ »ç¿ëµÈ´Ù.

´ÜÀÏÈ­ÀÇ ±âº» °³³äÀº ¸Å¿ì °£´ÜÇÏ´Ù. °¢ ¹®ÀÚ¸¦ ¸®½ºÆ®·Î ³ªÅ¸³½´Ù. ÀÌ ¸®½ºÆ®ÀÇ Ã¹¹ø° ¿ø¼Ò´Â ¼­¼úÇü ¸íÁ¦ÀÇ À̸§À̸ç, ³ª¸ÓÁö ¿ø¼Ò´Â ¸Å°³ º¯¼ö·Î½á, ÇϳªÀÇ ¿ø¼Ò (LISP ¿ë¾î·Î´Â ¿øÀÚ (atom)) À̰ųª, ȤÀº ¶Ç ´Ù¸¥ ¸®½ºÆ®ÀÏ ¼ö ÀÖ´Ù. ¿¹¸¦ µé¸é,

    (tryassassinate Marcus Caesar)
    (tryassassinate Marcus (rulerof Rome))

µÎ °³ÀÇ ¹®ÀÚ°¡ ¼­·Î °°Àº °ÍÀÎÁö¸¦ °áÁ¤Çϱâ À§ÇØ, ¸ÕÀú ù¹ø° ¿ø¼Ò°¡ ¼­·Î °°ÀºÁö Á¶»çÇÑ´Ù. ¸¸¾à ±×·¸´Ù¸é ¼öÇàÀ» °è¼ÓÇÏ°í, ±×·¸Áö ¾Ê´Ù¸é ³ª¸ÓÁö ¸Å°³ º¯¼öµé°ú´Â »ó°ü¾øÀÌ ÀÌ µÎ ¹®ÀÚ°¡ ¼­·Î ´Ù¸¥ °ÍÀÓÀ» ¾Ë ¼ö ÀÖ´Ù. ¿¹¸¦ µé¾î, ´ÙÀ½ µÎ °³´Â ¼­·Î °°Àº °ÍÀ̶ó°í ¸»ÇÒ ¼ö ¾ø´Ù :

    (tryassassinate Marcus Caesar)
    (hate Marcus Caesar)

¸¸¾à ù¹ø° ¿ø¼Ò°¡ ÀÏÄ¡µÈ´Ù¸é, ÇÑ ¹ø¿¡ ÇÑ ½Ö¾¿ ³ª¸ÓÁö ¿ø¼ÒµéÀ» Á¶»çÇÑ´Ù. ³²¾Æ ÀÖ´Â °¢ ¿ø¼Ò¸¦ Á¶»çÇϱâ À§ÇØ, ´ÜÀÏÈ­ °úÁ¤À» ¼øȯÀûÀ¸·Î »ç¿ëÇÑ´Ù. ÀÏÄ¡ ±ÔÄ¢Àº ´Ü¼øÇÏ´Ù. »óÀÌÇÑ »ó¼ö, ÇÔ¼ö ȤÀº ¼­¼úÇü ¸íÁ¦´Â ¼­·Î ¿ÏÀüÈ÷ ¶È°°À» °æ¿ì¸¸ ¼­·Î ÀÏÄ¡µÇ°í, ±×·¸Áö ¾ÊÀ¸¸é ¼­·Î ÀÏÄ¡µÇÁö ¸øÇÑ´Ù. º¯¼ö´Â ´Ù¸¥ º¯¼ö, ¸ðµç »ó¼ö, ÇÔ¼ö ȤÀº ¼­¼úÇü ¸íÁ¦ÀÇ ½Ä°ú ÀÏÄ¡ÇÒ ¼ö Àִµ¥, ÀÌ ¶§ ÇÔ¼ö³ª ¼­¼úÇü ¸íÁ¦ÀÇ ½Ä¿¡´Â ¾î¶² º¯¼öµµ Æ÷Ç﵃ ¼ö ¾ø´Ù.

´ÜÀÏÈ­ °úÁ¤À» ¼öÇàÇϱâ À§ÇØ, Àüü ¹®ÀÚ¿¡ ´ëÇØ ÇϳªÀÇ ¸ð¼øµµ ¾øÀÌ ÀÏ°üµÈ ġȯ´ë»óÀ» ã¾Æ¾ß ÇÑ´Ù. À̸¦ ÀÌÇØ, µÎ ¹®ÀÚ¸¦ Çϳª·Î º¼ ¼ö ÀÖ´ÂÁö Á¶»çÇϱ⿡ ¾Õ¼­, ãÀº °¢ ġȯ ´ë»óÀ» ¹®ÀÚÀÇ ³ª¸ÓÁö ºÎºÐ¿¡ Àû¿ëÇØ¾ß ÇÑ´Ù. ¿¹¸¦ µé¾î, ´ÙÀ½ ½ÄÀÌ ´ÜÀÏÈ­ µÉ ¼ö ÀÖ´ÂÁö »ìÆì º¸ÀÚ :

    (P x x)
    (P y z)

ù¹ø° p ´Â ÀÏÄ¡ÇÑ´Ù. ´ÙÀ½ x ¿Í y ¸¦ ºñ±³ÇÏ¿©, x ¸¦ y ·Î ġȯÇϸé, À̵éÀÌ ¼­·Î ÀÏÄ¡µÉ ¼ö ÀÖ´ÂÁö °áÁ¤ÇÑ´Ù. ÀÌ·¯ÇÑ Ä¡È¯À»

    y/x

·Î Ç¥±âÇÑ´Ù (¹°·Ð, x ¿Í y °¡ °¡»ó º¯¼öÀ̱⠶§¹®¿¡, y ¸¦ x ·Î ġȯÇÒ ¼ö ÀÖ´Ù). ´ÙÀ½ ´Ü¼øÈ÷ x ¿Í z ¸¦ ÀÏÄ¡½ÃÅ°·Á ÇÑ´Ù¸é, ġȯ z/x ¸¦ ¾ò´Â´Ù. ±×·¯³ª x ÀÇ Ä¡È¯À¸·Î y ¿Í z ¸¦ ¸ðµÎ ´ëÀÔ½Ãų ¼ö ¾ø±â ¶§¹®¿¡, ÀÏ°üµÈ ġȯÀ» ¾òÀ» ¼ö°¡ ¾ø´Ù. ù¹ø° ġȯ y/x ¸¦ ãÀº ÈÄ, ¹®ÀÚÀÇ ³²¾Æ ÀÖ´Â ºÎºÐÀÎ

    (y)

    (z)

¿¡ ´ëÇÑ Ä¡È¯À» ¸¸µé¾î¾ß ÇÑ´Ù. ġȯ z/y ¸¦ »ç¿ëÇÏ¿© µÎ ¹®ÀÚÀÇ ´ÜÀÏÈ­¸¦ ½ÃµµÇÒ ¼ö ÀÖ´Ù. ¹ß°ßÇÑ µÎ °³ÀÇ Ä¡È¯À» ÇÕ¼ºÇÏ¿©, Àüü ´ÜÀÏÈ­ °úÁ¤À» ¿Ï·áÇÑ´Ù. ÇÕ¼º ġȯÀº

    (z/y)(y/x)

·Î Ç¥±âµÈ´Ù. ÀϹÝÀûÀ¸·Î ġȯ ()() ´Â ¸®½ºÆ®ÀÇ °¡Àå ¿ìÃøÀÇ Ä¡È¯ºÎÅÍ Àû¿ëÇÏ°í, ġȯÀ» ¸ðµÎ Àû¿ëÇÒ ¶§±îÁö, ¾òÀº °á°ú¿¡ °è¼ÓÀûÀ¸·Î ´ÙÀ½ ¸®½ºÆ®ÀÇ Ä¡È¯À» Àû¿ëÇÑ´Ù.

µÎ °³ÀÇ ¹®ÀÚ¸¦ ÀÏÄ¡½ÃÅ°´Â ġȯÀ» Àû¾îµµ ÇÑ °³ ã´Â °ÍÀÌ ´ÜÀÏÈ­ °úÁ¤ÀÇ ¸ñÇ¥ÀÌ´Ù. ´ëºÎºÐÀÇ °æ¿ì¿¡ À־, ÀÌ·± ġȯÀÌ ÇÑ °³ Á¸ÀçÇÑ´Ù¸é, ÀÌ Ä¡È¯ ¿Ü¿¡µµ ¿©·¯ °³ÀÇ Ä¡È¯ÀÌ Á¸ÀçÇÔÀ» ¾Ë ¼ö ÀÖ´Ù. ¿¹¸¦ µé¾î, ¹®ÀÚ

    hate (x, y)
    hate (Marcus, z)

´Â ´ÙÀ½°ú °°Àº ġȯ ÁßÀÇ Çϳª¸¦ »ç¿ëÇÔÀ¸·Î½á, ´ÜÀÏÈ­µÉ ¼ö ÀÖ´Ù :

    (Marcus/x, z/y)
    (Marcus/x, y/z)
    (Marcus/x, Caesar/y, Caesar/z)
    (Marcus/x, Polonius/y, Polonius/z)

óÀ½ µÎ °³´Â ¾îÈÖ¸¸ ´Ù¸¦ »Ó ¼­·Î °°Àº °ÍÀÌ´Ù. ±×·¯³ª ´ÙÀ½ µÎ °³·ÎºÎÅÍ´Â, ÀÏÄ¡¸¦ À§ÇØ ÇÊ¿äÇÑ °Í ÀÌ»óÀÇ Á¦ÇÑÀÌ °¡ÇØÁø ġȯÀÌ ¸¸µé¾îÁø´Ù. ´ÜÀÏÈ­ °úÁ¤¿¡¼­ ¾ò¾îÁø ¸¶Áö¸· ġȯÀÌ ºñ±³ Èí¼ö °úÁ¤¿¡ »ç¿ëµÇ±â ¶§¹®¿¡, °¡´ÉÇÑ ÇÑ °¡Àå ÀϹݼºÀ» Áö´Ñ ´ÜÀÏÈ­ ±âÈ£ (the most general unifier) ¸¦ ¸¸µå´Â °ÍÀÌ È¿À²ÀûÀÌ´Ù. ¾Æ·¡ ¼Ò°³µÈ ¾Ë°í¸®ÁòÀº ÀÌ·¯ÇÑ Á¶°ÇÀ» ¸¸Á·½ÃŲ´Ù.

¾Õ¿¡¼­ ´ÜÀÏÈ­ ¾Ë°í¸®ÁòÀÇ ÀÛ¿ë¿¡ ´ëÇØ ¼³¸íÇÏ¿´±â ¶§¹®¿¡, ÀÌÁ¦ ÀÌ°ÍÀ» ÀÚ¼¼È÷ ±â¼úÇÏ·Á ÇÑ´Ù. ÀÏÄ¡ °úÁ¤ µ¿¾È ¼öÇàµÈ ġȯÀÇ ÇÕ¼ºÀ» ³ªÅ¸³»´Â ¸®½ºÆ®¸¦ °ªÀ¸·Î µ¹·ÁÁÖ´Â UNIFY (L1, L2) ¸¦ »ìÆì º¸ÀÚ. ¾î¶² ¿ø¼Òµµ Æ÷ÇÔÇÏ°í ÀÖÁö ¾Ê´Â ¸®½ºÆ®ÀÎ NIL Àº ÀÏÄ¡°¡ ¹ß°ßµÇ¾úÀ½À» ¾Ë·Á ÁØ´Ù. ÇϳªÀÇ °ªÀ¸·Î ±¸¼ºµÈ ¸®½ºÆ® F ´Â ´ÜÀÏÈ­ °úÁ¤ÀÌ ½ÇÆÐÇÏ¿´À½À» ¾Ë¸°´Ù.

        Unify (L1, L2)

    1. L1 À̳ª L2 °¡ ¿øÀÚ (atom) À̶ó¸é, ´ÙÀ½À» ¼öÇàÇÑ´Ù.
       1) ¸¸¾à L1 °ú L2 °¡ ¼­·Î °°Àº °ÍÀ̶ó¸é, NIL À» µ¹·Á ÁØ´Ù.
       2) ±×·¸Áö ¾ÊÀ» °æ¿ì, L1 ÀÌ º¯¼ö¶ó¸é,

            1. L1 ÀÌ L2 ¿¡ ³ªÅ¸³­´Ù¸é, F ¸¦ µ¹·Á ÁØ´Ù.
               ±×·¸Áö ¾Ê´Ù¸é, (L2/L1) À» µ¹·Á ÁØ´Ù.

        3) ±×·¸Áö ¾ÊÀ» °æ¿ì, L2 °¡ º¯¼ö¶ó¸é,

            1. L2 °¡ L1 ¿¡ ³ªÅ¸³­´Ù¸é, F ¸¦ µ¹·Á ÁØ´Ù.
               ±×·¸Áö ¾Ê´Ù¸é, (L1/L2) ¸¦ µ¹·Á ÁØ´Ù.

    2. ¸¸¾à Length(L1) ÀÌ Length(L2) ¿Í °°Áö ¾Ê´Ù¸é, F ¸¦ µ¹·Á ÁØ´Ù.

    3. SUBST ÀÇ °ªÀ¸·Î NIL À» ÁöÁ¤ÇÑ´Ù (ÀÌ °úÁ¤ÀÌ ³¡³¯ ¶§, SUBST ´Â L1 °ú L2 ¸¦ ´ÜÀÏÈ­ Çϱâ À§ÇØ »ç¿ëµÈ ¸ðµç ġȯÀ» Æ÷ÇÔÇÏ°í ÀÖ´Ù).

    4. for i : = 1 to number of elements in L1 do
1) L1 ÀÇ Ã¹¹ø° ¿ø¼Ò¿Í L2 ÀÇ i ¹ø° ¿ø¼Ò¸¦ ¸Å°³ º¯¼ö·Î ÇÏ¿© Unify ¸¦ È£ÃâÇÏ°í, À̷κÎÅÍ ¾òÀº °á°ú¸¦ S ¿¡ ³Ö´Â´Ù.
2) ¸¸¾à S = F À̸é, F ¸¦ µ¹·Á ÁØ´Ù.
3) ¸¸¾à S °¡ NIL ÀÌ ¾Æ´Ï¶ó¸é

            1. S ¸¦ L1 °ú L2 ÀÇ ³ª¸ÓÁö ºÎºÐ¿¡ Àû¿ëÇÑ´Ù.
    2. SUBST : = APPEND (S, SUBST)

        return SUBST

ÁÖ¾îÁø º¯¼ö¸¦ Æ÷ÇÔÇÏ°í ÀÖ´Â ½ÄÀÌ ±× º¯¼ö·Î´Â ´ÜÀÏÈ­µÉ ¼ö ¾ø´Ù´Â °ÍÀ» È®½ÅÇÒ ¹æ¹ýÀÌ À§ÀÇ ¾Ë°í¸®Áò¿¡¼­´Â ³íÀǵÇÁö ¾Ê¾Ò´Ù. ´ÙÀ½ ½ÄÀÇ ´ÜÀÏÈ­¸¦ Á¶»çÇØ º¸ÀÚ.

    (f x x)
    (f g(x) g(x))

¸¸¾à x ¸¦ g(x) ·Î ġȯÇÑ´Ù¸é, ÀÌ ½ÄÀÌ ³ª¸ÓÁö ºÎºÐ¿¡ ³ªÅ¸³­ x ¸¦ g(x) ·Î ġȯÇØ¾ß ÇÒ °ÍÀÌ´Ù. ±×·¯³ª, x ¸¦ °áÄÚ Á¦°ÅÇÒ ¼ö ¾ø±â ¶§¹®¿¡, ÀÌ·Î ÀÎÇØ ¾Ë°í¸®ÁòÀº ¹«ÇÑÈ÷ ¼øȯ ¹Ýº¹µÉ °ÍÀÌ´Ù.

(5) ¼­¼ú ³í¸®¿¡¼­ÀÇ ºñ±³ Èí¼ö ¹æ¹ý

Áö±Ý±îÁö µÎ °³ÀÇ ¹®ÀÚ°¡ Çϳª·Î ÀÏÄ¡µÇÁö ¸øÇϸé, ¼­·Î ¸ð¼øÀ̶ó°í °áÁ¤ÇÏ´Â ¹æ¹ý¿¡ ´ëÇØ ³íÀÇÇÏ¿´´Ù. ¿¹¸¦ µé¾î, man(x) ¿Í man(spot) ´Â ´ÜÀÏÈ­µÉ ¼ö Àֱ⠶§¹®¿¡, man(x) ¿Í ~man(spot) ´Â ¼­·Î ¸ð¼øÀÌ´Ù. ¼­¼ú ³í¸®¿¡ ºñ±³ Èí¼ö ¹æ¹ýÀ» »ç¿ëÇϱâ À§ÇØ, ´ÜÀÏÈ­ ¾Ë°í¸®ÁòÀ» ÀÌ¿ëÇÏ¿© »ó¼âµÉ ¹®ÀÚÀÇ ½ÖÀ» ã´Â´Ù.

¶ÇÇÑ, ´ÜÀÏÈ­ ¾Ë°í¸®ÁòÀ¸·ÎºÎÅÍ ¾òÀº ´ÜÀÏÈ­ ±âÈ£ (unifier) ¸¦ »ç¿ëÇÏ¿© ºñ±³ Èí¼öÀýÀ» ¸¸µç´Ù. ¿¹¸¦ µé¾î, ´ÙÀ½ µÎ ÀýÀ» ºñ±³ Èí¼öÇÑ´Ù°í ÇÏÀÚ :

    1. man(Marcus)
    2. ~man(x1) ¡ý mortal(x1)

ġȯ Marcus/x1 À» »ç¿ëÇÏ¿© ¹®ÀÚ man(Marcus) ¿Í man(x1) À» °°Àº Çϳª·Î º¼ ¼ö ÀÖÀ¸¸ç, ÀÌ°ÍÀº x1 = Marcus ÀÇ °æ¿ì ~man(Marcus) °¡ °ÅÁþÀÓÀ» ÀǹÌÇÑ´Ù. ±×·¯³ª ¸íÁ¦ ³í¸®¿¡¼­Ã³·³ °£´ÜÈ÷ µÎ °³ÀÇ ¹®ÀÚ man À» »ó¼âÇÏ¿© mortal(x1) À» ¾òÀ» ¼ö ÀÖ´Â °ÍÀº ¾Æ´Ï´Ù. Àý 2 ´Â ÁÖ¾îÁø x1 ¿¡ ´ëÇØ ~man(x1) À̰ųª martal(x1) ÀÓÀ» ÀǹÌÇÑ´Ù. µû¶ó¼­ Àý 2 °¡ ÂüÀ¸·Î À¯ÁöµÇ±â À§Çؼ­´Â, mortal(Marcus) °¡ ÂüÀ̾î¾ß ÇÑ´Ù. ~man(x1) À» ÂüÀ¸·Î ¸¸µé ¼ö ÀÖ´Â x1 ÀÌ Á¸ÀçÇÏ¿© Mortal(x1) ÀÇ Áø¸®°ªÀÌ Àüü ÀýÀÇ Áø¸®°ª¿¡ ¿µÇâÀ» ¹ÌÄ¡Áö ¸øÇÒ °æ¿ì°¡ Àֱ⠶§¹®¿¡, ¸ðµç x1 ¿¡ ´ëÇØ mortal(x1) ÂüÀ̾î¾ß ÇÒ ÇÊ¿ä´Â ¾ø´Ù. µû¶ó¼­ Àý 1 °ú Àý 2 ¿¡ ÀÇÇØ ¾ò¾îÁø ºñ±³ Èí¼öÀýÀº mortal(Marcus) À̾î¾ß¸¸ Çϴµ¥, ÀÌ°ÍÀº ´ÜÀÏÈ­ °úÁ¤ÀÇ °á°ú¸¦ ºñ±³ Èí¼öÀý¿¡ Àû¿ëÇÔÀ¸·Î½á ¾ò´Â´Ù. ¿©±â¼­ºÎÅÍ ºñ±³ Èí¼ö °úÁ¤ÀÌ ¼öÇàµÇ¾î mortal(Marcus) °¡ ÀÌ¿ë °¡´ÉÇÑ ´Ù¸¥ Àý°ú ¸ð¼øÀ» À¯µµÇÒÁö¿¡ ´ëÇØ Á¶»çÇÑ´Ù.

ÀÌ ¿¹·ÎºÎÅÍ, ½ÄÀ» ÀýÀÇ ÇüÅ·Πº¯È¯½ÃÅ°´Â °úÁ¤ µ¿¾È, º¯¼öµéÀ» Ç¥ÁØÈ­ÇØ¾ß ÇÏ´Â °ÍÀÌ ¾ó¸¶³ª Áß¿äÇÑÁö ¾Ë ¼ö ÀÖ´Ù. ÀÏ´Ü Ç¥ÁØÈ­°¡ ÇàÇØÁö¸é, ġȯÀ» ¼öÇàÇÏ¿© ºñ±³ Èí¼öÀýÀ» ¾ò±â À§ÇØ ´ÜÀÏÈ­ °úÁ¤ÀÌ ¾î¶»°Ô »ç¿ëµÇ¾î¾ß Çϴ°¡¸¦ °áÁ¤ÇÏ´Â °ÍÀº ¿ëÀÌÇÏ´Ù. ¸¸¾à µ¿ÀÏ º¯¼ö¸¦ »ç¿ëÇÑ µÎ °³ÀÇ ¿¹°¡ ¹ß»ýÇÑ´Ù¸é, À̵éÀ» ġȯÇÏ¿© µ¿ÀÏÇÑ °ÍÀ¸·Î ¸¸µç´Ù.

ÁÖ¾îÁø ¹®ÀåÀÇ ÁýÇÕÀ» F ·Î, Áõ¸íµÉ ¹®ÀåÀ» S ·Î °¡Á¤ÇÒ ¶§, ¼­¼ú ³í¸®¿¡¼­ÀÇ ºñ±³ Èí¼ö °úÁ¤ ¾Ë°í¸®ÁòÀº ´ÙÀ½¿¡ µû¶ó ¼öÇàµÈ´Ù.

    1. F ÀÇ ¸ðµç ¹®ÀåÀ» ÀýÀÇ ÇüÅ·Πº¯È¯ÇÑ´Ù.

    2. S ¸¦ ºÎÁ¤ÇÏ°í, ±× °á°ú¸¦ ÀýÀÇ ÇüÅ·Πº¯È¯ÇÏ¿© 1 ·ÎºÎÅÍ ¾ò¾îÁø ÀýÀÇ ÁýÇÕ¿¡ ÷°¡Ç϶ó.

    3. ¸ð¼øÀÌ ¹ß°ßµÇ°Å³ª, ¹Ì¸® Á¤ÇØÁø ¾ç ¸¸Å­ÀÇ ³ë·ÂÀÌ ¼Ò¸ðµÉ ¶§±îÁö ´ÙÀ½À» ¹Ýº¹ ¼öÇàÇÑ´Ù :
1) µÎ °³ÀÇ ÀýÀ» ¼±ÅÃÇÏ¿©, ºÎ¸ðÀýÀ̶ó ºÎ¸¥´Ù.
2) À̵éÀ» ÇÔ²² ºñ±³ Èí¼öÇÑ´Ù. ºñ±³ Èí¼öÀýÀº ´ÙÀº ¿¹¿Ü¸¦ °¡Áö°í, ÀûÀýÈ÷ ġȯµÈ ¾ç ºÎ¸ðÀýÀÇ ¸ðµç ¹®ÀÚ¸¦ ³í¸®ÇÕÀ¸·Î °áÇÕÇÏ¿© ¾ò´Â´Ù : ´ÜÀÏÈ­ ±âÈ£ T1 °ú T2 ¿¡ ´ëÇØ T1 Àº ºÎ¸ðÀý ÁßÀÇ Çϳª¿¡, T2 ´Â ³ª¸ÓÁö ´Ù¸¥ ºÎ¸ðÀý¿¡ Æ÷ÇÔµÈ ÀÌ·± T1 °ú ~T2 ÀÇ ½ÖÀÌ ÀÖÀ» ¶§, T1 µµ T2 µµ ºñ±³ Èí¼öÀý¿¡ Æ÷ÇÔµÇÁö ¸øÇÑ´Ù. T1 °ú T2 ¸¦ º¸¼ö ¹®ÀÚ (complementary literal) ¶ó ÇÑ´Ù. ´ÜÀÏÈ­ °úÁ¤À¸·ÎºÎÅÍ ¾òÀº ġȯÀ» »ç¿ëÇÏ¿© ºñ±³ Èí¼öÀýÀ» ¸¸µç´Ù.
3) ºñ±³ Èí¼öÀýÀÌ ¾î¶² ¹®ÀÚµµ Æ÷ÇÔÇÏÁö ¾Ê´Â ÀýÀ̶ó¸é, ¸ð¼øÀÌ ¹ß°ßµÈ °ÍÀÌ´Ù. ±×·¸Áö ¾Ê´Ù¸é, ¾òÀº ºñ±³ Èí¼öÀýÀ» ÀÌ °úÁ¤ÀÇ ÀÌ¿ë °¡´ÉÇÑ ÀýÀÇ ÁýÇÕ¿¡ ÷°¡ÇÑ´Ù.

¸Å ´Ü°è¿¡¼­ ÇÔ²² ºñ±³ Èí¼öµÈ ÀýÀ» ¾î¶² ü°èÀûÀÎ ¹æ¹ýÀ» »ç¿ëÇÏ¿© ¼±ÅÃÇÑ´Ù¸é, ¸¸¾à ¸ð¼øÀÌ Á¸ÀçÇÒ °æ¿ì, ºñ±³ Èí¼ö °úÁ¤¿¡ ÀÇÇØ ÀÌ ¸ð¼øÀ» ãÀ» ¼ö ÀÖ´Ù. ±×·¯³ª À̸¦ À§Çؼ­´Â ±ä ½Ã°£ÀÌ ÇÊ¿äÇÏ´Ù. ÀÌ °úÁ¤À» »ó´çÈ÷ »¡¸® ¼öÇàÇÒ ¼ö ÀÖ´Â ¼±Åà ¹æ¹ýÀÌ Á¸ÀçÇÑ´Ù :

¸¶Ä¿½ºÀÇ Åä·ÐÀ¸·Î µÇµ¹¾Æ¿Í, ±×¿¡ ´ëÇÑ »õ·Î¿î °ÍÀ» Áõ¸íÇϱâ À§ÇØ ºñ±³ Èí¼ö ¹æ¹ýÀÌ ¾î¶»°Ô »ç¿ëµÇ´ÂÁö ¾Ë¾Æ º¸ÀÚ. ¸ÕÀú 2 Àý¿¡ ¼Ò°³µÈ ¹®ÀåÀÇ ÁýÇÕÀ» »ìÆì º¸ÀÚ. ºñ±³ Èí¼ö °úÁ¤¿¡¼­ À̵éÀ» »ç¿ëÇϱâ À§Çؼ­´Â 4.1 Àý¿¡ ±â¼úµÈ ÀýÀÇ ÇüÅ·ΠÀ̵éÀ» º¯È¯½ÃÄÑ¾ß ÇÑ´Ù. ±×¸² 9(a) ¿¡´Â º¯È¯ÀÇ °á°ú°¡, ±×¸² 9(b) ¿¡´Â ¹®ÀåÀÇ ºñ±³ Èí¼ö¿¡ ÀÇÇÑ Áõ¸íÀÌ º¸¿©Áø´Ù. ¹°·Ð ±×¸²¿¡ º¸¿©Áø °Íº¸´Ù ´õ ¸¹Àº ºñ±³ Èí¼ö ÀýÀ» ¸¸µé ¼ö ÀÖÀ¸³ª, Ž»öÀ» À§ÇØ À§¿¡¼­ ±â¼úµÈ °æÇèÀû Ž»ö ¹æ¹ýÀ» »ç¿ëÇÏ¿© ºñ±³ Èí¼öÀýÀ» ¸¸µé¾ú´Ù. ¿©±â¼­ Áõ¸íÇÏ°íÀÚ ÇÏ´Â ¹®ÀåÀ¸·ÎºÎÅÍ ÈÄÁø Ãß·ÐÇϸ鼭 ¸ð¼øÀ» ¾ò¾î³»´Â °ÍÀº ÇʼöÀûÀ¸·Î ÇàÇØÁø´Ù.

±×¸² 9  ºñ±³ Èí¼ö ¹æ¹ýÀ» ÀÌ¿ëÇÑ Áõ¸í

¹®Àå

    hate(Marcus, Caesar)

¸¦ Áõ¸íÇÒ ¶§, »ç½Ç»ó ¿øÇÏ´Â ¸ñÇ¥´Â "Did Marcus hate Caesar?" (¸¶Ä¿½º´Â ½ÃÀÌÀú¸¦ ¹Ì¿öÇÏ¿´´Â°¡?) ¶ó´Â Áú¹®¿¡ ´ëÇÑ ´äÀ̶ó°í °¡Á¤ÇÏÀÚ. ÀÌ °æ¿ì, ¹®Àå

    ~hate(Marcus, Caesar)

¸¦ Áõ¸íÇÏ¸é µÈ´Ù. À̸¦ À§ÇØ

    hate(Marcus, Caesar)

¶ó´Â ¹®ÀåÀ» ÀÌ¿ë °¡´ÉÇÑ ÀýÀÇ ÁýÇÕ¿¡ ÷°¡ÇÔÀ¸·Î½á, ºñ±³ Èí¼ö °úÁ¤ÀÇ ¼öÇàÀ» ½ÃÀÛÇÒ ¼ö ÀÖÁö¸¸, ÀÌ ÀÌ¿ë °¡´ÉÇÑ ÀýÀÇ ÁýÇÕ¿¡´Â ~hate ¸¦ Æ÷ÇÔÇÏ°í ÀÖ´Â ÀýÀÌ Á¸ÀçÇÏÁö ¾ÊÀ½À» ½±°Ô ¾Ë ¼ö ÀÖ´Ù. ºñ±³ Èí¼ö °úÁ¤¿¡¼­, »õ·Î¿î ÀýÀº ÀÌ¹Ì Á¸ÀçÇÏ°í ÀÖ´Â Àý¿¡ Æ÷ÇÔµÈ ¹®ÀÚµéÀÇ °áÇÕ¿¡ ÀÇÇؼ­¸¸ ¾ò¾îÁö±â ¶§¹®¿¡, ÇöÀçÀÇ ÀÌ¿ë °¡´ÉÇÑ Àýµé·ÎºÎÅÍ ~hate ¸¦ Æ÷ÇÔÇÏ°í ÀÖ´Â ÀýÀº °áÄÚ ¸¸µé ¼ö ¾ø°í µû¶ó¼­

    hate(Marcus, Caesar)

´Â ÀÌ¹Ì ¾Ë·ÁÁø ¾î´À ¹®Àå°úµµ ¸ð¼øµÈ ¹®ÀåÀ» ¸¸µéÁö ¸øÇÑ´Ù. ÀÌ°ÍÀº ºñ±³ Èí¼ö °úÁ¤¿¡¼­, ¾î¶² ¸ð¼øµµ Á¸ÀçÇÏÁö ¾ÊÀ½ÀÌ Å½ÁöµÇ´Â »óȲÀÇ ¿¹ÀÌ´Ù. ¶§¶§·Î, ÀÌ·¯ÇÑ »óȲÀº Áõ¸íÀÇ ½ÃÀÛ¿¡¼­°¡ ¾Æ´Ï¶ó, ±×¸² 9 ¿¡ ÁÖ¾îÁø °ø¸®¸¦ Åä´ë·Î, ±×¸² 10(a) ÀÇ ¿¹¿¡ º¸¿©Áø °Íó·³, Áõ¸íÀÌ ¼öÇà µµÁß¿¡ ŽÁöµÈ´Ù.

±×¸² 10  ºñ±³ Èí¼ö ¹æ¹ý¿¡¼­ ¼º°øÀûÀÌÁö ¸øÇÑ ½Ãµµ

±×·¯³ª Áö½Ä¿¡ ´ëÇÑ µ¥ÀÌÅÍ º£À̽º¿¡ ´ÙÀ½°ú °°Àº µÎ °³ÀÇ ¾ð¸íÀÌ ´õ Æ÷ÇԵǾî ÀÖ´Ù°í °¡Á¤ÇÏÀÚ :

     (9) persecute(x, y) ¡æ hate(y, x)

    (10) hate (x, y) ¡æ persecute(y, x)

ÀÌ°ÍÀ» ÀýÀÇ ÇüÅ·Πº¯È¯ÇÏ¸é ´ÙÀ½°ú °°´Ù :

     (9) ~persecute(x5, y2) ¡ý hate(y2, x5)

    (10) ~hate(x6, y3) ¡ý persecute(y3, x6)

ÀÌ ¾ð¸íÀ» »ç¿ëÇÏ¿©, ±×¸² 10(b) ¿¡ º¸¿©Áø °Íó·³ ±×¸² 10(a) ÀÇ Áõ¸íÀ» °è¼Ó ¼öÇàÇÒ ¼ö ÀÖ´Ù. ÀÌÀü¿¡ ¸¸µé¾îÁ³´ø ºñ±³ Èí¼öÀýÀÌ ´Ù½Ã ¸¸µé¾îÁú ¶§, ¾î¶² ¸ð¼øµµ Á¸ÀçÇÏÁö ¾ÊÀ½À» ¾Ë ¼ö ÀÖ´Ù.

±×¸² 11 º¯¼öµéÀ» Ç¥ÁØÈ­½ÃÄÑ¾ß ÇÏ´Â ÀÌÀ¯

°ø½ÄÀÇ ÁýÇÕÀ» ÀýÀÇ ÇüÅ·Πº¯È¯ °úÁ¤ÀÇ Ã¹¹ø° ´Ü°è´Â ÃÖÈÄ·Î ¾òÀº Àý¿¡ ³ªÅ¸³­ º¯¼öµéÀ» Ç¥ÁØÈ­ÇÏ´Â °ÍÀÌ´Ù. ºñ±³ Èí¼ö °úÁ¤¿¡ ´ëÇØ ³íÀÇÇØ ¿À¸é¼­, ÀÌ ´Ü°èÀÇ Á߿伺À» ¾Ë ¼ö ÀÖ¾ú´Ù. ±×¸² 11 Àº º¯¼öÀÇ Ç¥ÁØÈ­°¡ ¼öÇàµÇÁö ¾ÊÀ» °æ¿ì ¹ß»ýÇÒ ¾î·Á¿î »óȲÀÇ ¿¹¸¦ º¸¿© ÁØ´Ù. Àý 1 °ú Àý 2 ¿¡ ¸ðµÎ º¯¼ö y °¡ »ç¿ëµÇ¾ú±â ¶§¹®¿¡, µÎ¹ø° ºñ±³ Èí¼ö ´Ü°èÀÇ Ä¡È¯ÀÌ ¼öÇàµÇ¸é, ¸Å¿ì Á¦ÇÑµÇ¾î °á±¹ µ¥ÀÌÅÍ º£À̽º ³»¿¡ Á¸ÀçÇÏ´Â ¸ð¼øÀ» ã¾Æ³¾ ¼ö ¾ø´Â ÀýÀÌ ¸¸µé¾îÁø´Ù. ±×·¯³ª, ¸¸¾à Àý

    ~father(Chris, y)

°¡ ¸¸µé¾îÁ³´õ¶ó¸é, Àý 4 ·ÎºÎÅÍ ¸ð¼øÀ» ¹ß°ßÇÒ ¼ö ÀÖ¾úÀ» °ÍÀÌ´Ù. Àý 2 ¸¦

    ~mother(a, b) ¡ý woman(a)

·Î Ç¥±âÇÑ´Ù¸é, ÀÌ°ÍÀÌ °¡´ÉÇÏ´Ù.

±âº»ÀûÀÎ ºñ±³ Èí¼ö °úÁ¤ÀÇ ¼öÇà¿¡´Â, ÀýÀÇ ÇüÅ·Πǥ±âµÉ ¼ö ÀÖ´Â Áö½ÄÀÌ ¸ðµÎ ÇÊ¿äÇÏ´Ù. ±×·¯³ª 3 Àý¿¡¼­ ÁöÀûÇÑ °Íó·³, ÀϺΠÁ¤º¸¸¦ °è»ê °¡´ÉÇÑ ÇÔ¼ö³ª ȤÀº °è»ê °¡´ÉÇÑ ¼­¼úÇü ¸íÁ¦¿Í µ¿Ä¡ °ü°èÀÇ ÇüÅ·Πǥ±âÇÏ´Â °ÍÀº ´õ¿í È¿°úÀûÀÌ´Ù. ºñ±³ Èí¼ö °úÁ¤À» ¼öÁ¤ÇÏ°í Çâ»ó½ÃÅ´À¸·Î½á, ÀÌ·¯ÇÑ Á¾·ùÀÇ Á¤º¸¸¦ Â÷ÁöÇÏ´Â °ÍÀº ¾î·Á¿î ÀÏÀÌ ¾Æ´Ï´Ù. ±×¸² 12 ´Â 3 Àý¿¡¼­ ÁÖ¾îÁø ¹®ÀåÀ» Åä´ë·Î, ¹®Àå

    ~alive(Marcus, now)

¿¡ ´ëÇÑ ºñ±³ Èí¼ö Áõ¸íÀ» º¸¿© ÁØ´Ù. »õ·Î¿î ÀýÀ» ¸¸µé±â À§Çؼ­, ºñ±³ Èí¼ö ±ÔÄ¢»Ó¸¸ ¾Æ´Ï¶ó, µÎ °¡Áö »õ·Î¿î ±ÔÄ¢ÀÌ »ç¿ëµÈ´Ù

±×¸² 12  µ¿Ä¡ °ü°è¿Í Ãà¼Ò¸¦ ÅëÇÑ ºñ±³ Èí¼ö ¹æ¹ý

(6) ¿©·¯ ġȯÀÇ ¼öÇà

ºñ±³ Èí¼ö °úÁ¤À» »ç¿ëÇÏ¿©, Çãºê¶õµåÀÇ Á¤¸®¿¡ ÀÇÇØ Á¦°øµÈ °¡´ÉÇÑ ¸ðµç ġȯÀ» ½ÇÁ¦·Î ¼öÇàÇÏÁö ¾Ê°í, ºÎÁ¤¿¡ ÀÇÇÑ Áõ¸íÀ» ãÀ» ¼ö ÀÖ´Ù. ±×·¯³ª, Ç×»ó Çϳª ÀÌ»óÀÇ Ä¡È¯ÀÌ ºÒÇÊ¿äÇÑ °ÍÀº ¾Æ´Ï´Ù. ¿¹¸¦ µé¾î 2 Àý¿¡ ÁÖ¾îÁø ¹®Àå ¿Ü¿¡ ´ÙÀ½°ú °°Àº ¹®ÀåÀÌ ÁÖ¾îÁ³´Ù°í °¡Á¤ÇÏÀÚ :

    hate(Marcus, Paulus)
    hate(Marcus, Julian)

¸¶Ä¿½º°¡ ¾î¶² ÅëÄ¡ÀÚ¸¦ ¹Ì¿öÇÑ´Ù´Â °ÍÀ» Áõ¸íÇÏ°íÀÚ ÇÒ ¶§, ±×¸² 13(c) ¿¡ º¸¿©Áø ¸ð¼øÀ» ¹ß°ßÇϱ⿡ ¾Õ¼­, ±×¸² 13(a) ¿Í (b) ¿¡ º¸¿©Áø ġȯÀ» °¢°¢ ¼öÇàÇÒ ¼ö ÀÖ´Â °¡´É¼ºÀÌ ÀÖ´Ù. ¶§¶§·Î ¸¹Àº ġȯÀ» ¼öÇàÇÑ ÈÄ¿¡¾ß ºñ·Î¼Ò ¿øÇÏ´Â ¸ð¼øÀ» ãÀ» ¼ö ÀÖÀ» °æ¿ì°¡ ÀÖ´Ù.

±×¸² 13  ¿©·¯ ġȯÀÇ ½Ãµµ

(7) Áú¹®¿¡ ´äÇϱâ

Áú¹®¿¡ ´äÇÏ´Â ¹®Á¦ÀÇ Á¤¸® Áõ¸í ±â¹ýÀ» Àû¿ëÇÏ´Â °ÍÀº Àΰø Áö´ÉÀÇ Ãʱ⿡ ½ÇÇöµÇ¾ú´Ù. ¿¬¿ª Ãß·Ð °úÁ¤À» »ç¿ëÇÏ¿© °ø¸®·ÎºÎÅÍ Á¤¸®¸¦ À¯ÃßÇÏ°í, ÀÌ¹Ì Á¸ÀçÇÏ´Â »ç½Ç·ÎºÎÅÍ »õ·Î¿î »ç½Ç (´ä) À» À¯ÃßÇÒ ¼ö Àֱ⠶§¹®¿¡, ÀÌ°ÍÀº ´ç¿¬ÇÏ´Ù. Áö±Ý±îÁö "Is Marcus alive?" ¿Í °°Àº ¿¹-¾Æ´Ï¿À Áú¹®¿¡ ´äÇϱâ À§ÇØ ºñ±³ Èí¼ö °úÁ¤ÀÌ ¾î¶»°Ô »ç¿ëµÇ´ÂÁö¿¡ ´ëÇØ ³íÀÇÇÏ¿´´Ù. ÀÌ Àý¿¡¼­´Â "When did Marcus die?" (¸¶Ä¿½º´Â ¾ðÁ¦ Á×¾ú´Â°¡?) ȤÀº "Who tried to assassinate a ruler?" (´©°¡ ÅëÄ¡ÀÚ¸¦ ¾Ï»ìÇÏ·Á Çߴ°¡?) ¿Í °°Àº °ø¹é ä¿ì±â Áú¹®ÀÇ ´äÀ» ã±â À§ÇØ ºñ±³ Èí¼ö °úÁ¤ÀÌ ¾î¶»°Ô »ç¿ëµÇ´ÂÁö¿¡ ´ëÇØ ³íÀÇÇÑ´Ù. ÀÌ·¯ÇÑ Áú¹®¿¡ ´äÇϱâ À§Çؼ­´Â Áú¹®¿¡ ÁÖ¾îÁø Ç×°ú ÀÏÄ¡ÇÏ´Â ÀÌ¹Ì ¾Ë·ÁÁø ¾ð¸íÀ» ã¾Æ, ÀÌ µ¿Ä¡ ¾ð¸í Áß Áú¹®¿¡ ÀÇÇØ ¿ä±¸µÈ °ø¹éÀ» ä¿ï ¼ö ÀÖ´Â ºÎºÐÀ» ÃëÇØ ÀÀ´äÀ¸·Î »ç¿ëÇÑ´Ù. ¿¹¸¦ µé¾î "When did Marcus die?" ¶ó´Â Áú¹®¿¡ ´äÇϱâ À§ÇØ,

    died(Marcus, ??)

¿Í °°Àº ÇüÅÂÀÇ ÀýÀ» »ç¿ëÇÑ´Ù. ¿©±â¼­ ?? ´Â »ç½Ç»ó ƯÁ¤ÇÑ ÇطΠä¿öÁ®¾ß ÇÑ´Ù. µû¶ó¼­, ¾ð¸í

    died(Marcus, 79)

¸¦ Áõ¸íÇÒ ¼ö Àֱ⠶§¹®¿¡, ÀÌ Áú¹®¿¡ 79 ¶ó°í ´äÇÒ ¼ö ÀÖ´Ù.

ºñ±³ Èí¼ö °úÁ¤À» »ç¿ëÇÏ¿©, ÇÊ¿äÇÑ ¾ð¸íÀ» ã¾Æ ÀÌ°Í¿¡ ´ëÇÑ Áõ¸íÀ» ½±°Ô ¾òÀ» ¼ö ÀÖÀ½ÀÌ ÆǸíµÇ¾ú´Ù. "When did Marcus die?" ¶ó´Â Áú¹®À» °è¼Ó »ìÆì º¸ÀÚ. ÀÌ Áú¹®¿¡ ´äÇϱâ À§ÇØ, ¸ÕÀú ¸¶Ä¿½º°¡ Á×¾ú´Ù´Â °ÍÀÌ ÂüÀ̾î¾ß ÇÑ´Ù. µû¶ó¼­

    ¢¤t died(Marcus, t)

°¡ ÂüÀ̾î¾ß ÇÑ´Ù. ù ´Ü°è·Î ÀÌ°ÍÀÇ Áõ¸íÀ» À§ÇØ, ºñ±³ Èí¼ö °úÁ¤À» »ç¿ëÇÏ¿©

    ~¢¤t died(Marcus, t)

¿¡ ÀÇÇØ ¸ð¼øÀÌ ¹ß»ýµÈ´Ù´Â °ÍÀ» º¸¿©¾ß ÇÑ´Ù. ÀÌ ¾ð¸íÀÌ ¸ð¼øÀ» À¯µµÇÑ´Ù´Â °ÍÀÌ ¾î¶² Àǹ̸¦ °¡Áö´ÂÁö¿¡ ´ëÇØ ¾Ë¾Æ º¸ÀÚ. ÀÌ ¾ð¸íÀº ´ÙÀ½°ú °°Àº ÇüÅÂÀÇ

    ¢£t died(Marcus, t)

¶ó´Â ¾ð¸í°ú ¸ð¼øµÈ´Ù. À§ ¾ð¸íÀÇ °æ¿ì, ¸¶Ä¿½º°¡ ¼ö Â÷·Ê Á×¾ú´Ù´Â º¸°í·Î¼­, Áú¹®¿¡ ´äÇϰųª, ȤÀº °£´ÜÈ÷ Çϳª¸¦ ÅÃÇØ, ÀÌ°ÍÀ» Áú¹®¿¡ ´ëÇÑ ´äÀ¸·Î »ç¿ëÇÒ ¼ö ÀÖ´Ù. ¶Ç ´Ù¸¥ °¡´É¼ºÀº

    died(Marcus, date)

ÇüÅÂÀÇ Æ¯Á¤ÇÑ ¾ð¸í°ú ¸ð¼øÀ» À̲ø ¼ö ÀÖ´Ù´Â Á¡ÀÌ´Ù. ¸ð¼øÀ» ¸¸µé ¶§ »ç¿ëµÈ °ªÀº ¸ðµÎ ¿øÇÏ´Â °ªÀÌ µÉ ¼ö ÀÖ´Ù.

ºñ±³ Èí¼ö ¹æ¹ýÀ» »ç¿ëÇÏ¿© ¿øÇÏ´Â ¹®ÀåÀ» ã´Â ¹æ¹ýÀÌ ±×¸² 14(a) ¿¡ º¸¿©Áø´Ù. Ãâ¹ß ÀýÀ» ÇâÇØ ÈÄÁøÇØ °¡´Â ¿¬¼âÀûÀÎ ´ÜÀÏÈ­¸¦ »ç¿ëÇÏ¿©, Áú¹®¿¡ ´ëÇÑ ´äÀ» À¯ÃßÇÒ ¼ö ÀÖ´Ù. ¸ð¼øÀ» ã´Âµ¥ »ç¿ëµÉ ½Ä¿¡ »õ·Î¿î ¾î¶² ½ÄÀ» ÷°¡ÇÔÀ¸·Î½á, ÀÌ ¸¶Áö¸· ´Ü°èÀÇ ¼öÇàÀ» »ý·«ÇÒ ¼ö ÀÖ´Ù. ¹Ù·Î ÀÌ »õ·ÎÀÌ ¾òÀº ½ÄÀÌ ÂüÀÓÀ» Áõ¸íÇÏ°íÀÚ ÇÏ´Â ½ÄÀÌ´Ù (Áï, ÀÌ°ÍÀº ºñ±³ Èí¼ö °úÁ¤¿¡¼­ ½ÇÁ¦·Î »ç¿ëµÈ ½ÄÀ» ºÎÁ¤ÇÑ °ÍÀÌ´Ù). ÀÌ ½Ä¿¡ ƯÁ¤ÇÑ Ç¥½Ã¸¦ ÇÏ¿© ºñ±³ Èí¼ö °úÁ¤ÀÇ ¼öÇàÀ» ¿øÈ°ÇÏ°Ô ÇÑ´Ù (±×¸² 14 ¿¡¼­´Â ¹ØÁٷΠǥ½ÃÇÏ¿´´Ù). ´ÜÀÏÈ­°¡ ¼öÇàµÉ ¶§¸¶´Ù ÀÌ »õ·Î¿î °¡»ó ½ÄÀÇ º¯¼öµéÀº ¸¶Ä¡ ½ÇÁ¦·Î »ç¿ëµÇ°í ÀÖ´Â ÀýÀÇ º¯¼öµéó·³ Á¦ÇÑÀ» ¹Þ´Â´Ù. ºñ±³ Èí¼ö °úÁ¤ÀÇ ÃÖÁ¾ ¼öÇà ´Ü°è¿¡¼­´Â NIL ÀýÀÌ ¾Æ´Ï¶ó °¡»ó ½ÄÀÌ ³²´Â´Ù. ÀÌ ¶§ º¯¼ö¿¡ ´ëÀÔµÈ °ªÀÌ Áú¹®¿¡ ´ëÇÑ ¿øÇÏ´Â ´äÀÌ´Ù. ±×¸² 14(b) ´Â ÀÌ °úÁ¤À» »ç¿ëÇÏ¿© Áú¹®¿¡ ´äÇÏ´Â ¹æ¹ýÀ» º¸¿© ÁØ´Ù.

±×¸² 14  ºñ±³ Èí¼ö ¹æ¹ýÀ» »ç¿ëÇÑ ´ä ÃßÃâ

±×·¯³ª, ½Ã½ºÅÛÀÇ »ç½ÇÀ» Ç¥ÇöÇϱâ À§ÇØ Æ¯Á¤ÇÑ Ç¥±â¹ýÀÌ ÁÖ¾îÁ³À» °æ¿ì, ÀÌ ±â¹ýÀ» »ç¿ëÇϸé, ´äÀ» ãÀ» ¼ö ¾ø´Â Áú¹®µéÀÌ Á¸ÀçÇÑ´Ù. ¿¹¸¦ µé¾î, 3 Àý¿¡ ÁÖ¾îÁø ¹®ÀåÀ» »ç¿ëÇÏ¿© "What happened in 79 A.D.?" (A.D. 79 ³â¿¡ ¾î¶² ÀÏÀÌ ¹ß»ýÇÏ¿´´Â°¡?) ¶ó´Â Áú¹®¿¡ ´ëÇÑ ´äÀ» ã°íÀÚ ÇÑ´Ù. ÀÌ Áú¹®¿¡ ´äÇϱâ À§ÇØ, 79 ³â¿¡ ¹ß»ýÇÑ »ç°ÇÀÌ Á¸ÀçÇÔÀ» Áõ¸íÇØ¾ß Çϱ⠶§¹®¿¡,

    ¢¤x event(x, 79)

¸¦ Áõ¸íÇÏ¿©, x ÀÇ °ªÀ» ã¾Æ¾ß ÇÑ´Ù. ±×·¯³ª [event(x, y)] ÇüÅÂÀÇ ¾î¶² ¹®Àåµµ ÁÖ¾îÁöÁú ¾Ê´Â´Ù.

±×·¯³ª, ´Ù¸¥ Ç¥±â¹ýÀ» »ç¿ëÇÏ¿© »ç½ÇÀ» Ç¥ÇöÇÑ´Ù¸é, ÀÌ Áú¹®¿¡ ´ëÇÑ ´äÀ» ãÀ» ¼ö ÀÖ´Ù.

    erupted(volcano, 79)

´ë½Å,

    event(erupted(volcano), 79)

·Î Ç¥±âÇÒ ¼ö ÀÖ´Ù. ±×¸² 15 ¿¡ º¸¿©Áø °£´ÜÇÑ Áõ¸íÀ¸·Î Áú¹®¿¡ ´ëÇÑ ´äÀ» ãÀ» ¼ö ÀÖ´Ù.

±×¸² 15  »õ·Î¿î Ç¥ÇöÀÇ »ç¿ë

ÀÌ »õ·Î¿î Ç¥±â¹ýÀº ÀÌ ÀüÀÇ Ç¥±â¹ýº¸´Ù ´õ º¹ÀâÇÏ´Ù´Â °áÁ¡À» °¡Áö°í ÀÖ´Ù. ¶ÇÇÑ ÀÌ Ç¥±â¹ýÀ» »ç¿ëÇÑ´Ù°í Çؼ­, »ý°¢ÇÒ ¼ö ÀÖ´Â ¸ðµç Áú¹®¿¡ ´ëÇÑ ´äÀ» Ç×»ó ãÀ» ¼ö ÀÖ´Â °Íµµ ¾Æ´Ï´Ù. ÀϹÝÀûÀ¸·Î ¿ä±¸µÉ Áú¹®ÀÇ Á¾·ù¸¦ °áÁ¤ÇÏ°í, ÀÌ Áú¹®À» À§ÇØ »ç¿ëµÉ ÀûÀýÇÑ Ç¥±â¹ýÀ» ÀÛ¼ºÇØ¾ß ÇÑ´Ù.

¹°·Ð, Áú¹®ÀÇ À¯ÇüÀ¸·Î ¿¹-¾Æ´Ï¿À¿Í °ø¹é ä¿ì±â Áú¹®¸¸ Á¸ÀçÇÏ´Â °ÍÀº ¾Æ´Ï´Ù. ¿¹¸¦ µé¾î, ¾î¶² ÀÏÀ» ÇÏ°íÀÚ ÇÒ ¶§ ÀÌ ÀÏÀ» ¼öÇàÇϱâ À§ÇÑ ¹æ¹ýÀ» Áú¹®ÇÒ ¼öµµ ÀÖ´Ù. µû¶ó¼­ Ç×»ó °¡´ÉÇÑ ¸ðµç ÇüÅÂÀÇ Áú¹®¿¡ ´ëÇÑ ¿ÏÀüÇÑ ´äÀ» ãÀ» ¼ö ÀÖ´Â °ÍÀº ¾Æ´Ï´Ù. ÀÌ ÈÄÀÇ Àå¿¡¼­´Â ´Ù¾çÇÑ Á¾·ùÀÇ Áú¹®¿¡ ´ëÇÑ ´äÀ» ã±â À§ÇØ »ç¿ëµÉ ¿©·¯ ¹æ¹ýµéÀÌ ´Ù·ç¾îÁø´Ù.

5. ¿¬¿ª¹ý (Natural Deduction)

¾Õ Àý¿¡¼­´Â ºñ±³ Èí¼ö °úÁ¤À», »ç¿ëµÉ ¹®ÀåÀ» ±ÕÀÏÇÏ°Ô Ç¥±âÇÔÀ¸·Î½á ½±°Ô ±¸ÇöÇÒ ¼ö ÀÖ´Â Áõ¸í °úÁ¤À¸·Î ¼³¸íÇÏ¿´´Ù. ±×·¯³ª, ÀÌ °ßÇØ¿¡¼­´Â ±ÕÀϼºÀ» À§ÇØ ¸ðµç °ÍÀ» µ¿ÀÏÇÑ °ÍÀ¸·Î º¸¾Ò±â ¶§¹®¿¡, ƯÁ¤ÇÑ ¹®Á¦ÀÇ Ç®À̸¦ °¡Àå È¿°úÀûÀ¸·Î ãÀ» ¼ö ÀÖ´Â ¾ð¸íÀ» ½±°Ô ¼±ÅÃÇÒ ¼ö ¾ø´Â °áÁ¡ÀÌ ÀÖ´Ù. ¸ðµç °ÍÀ» ÀýÀÇ ÇüÅ·Πº¯È¯ÇÏ¿© Ç¥±âÇÒ ¶§ ¿ø·¡ Ç¥±âµÈ »ç½Ç¿¡ Æ÷ÇԵǾî ÀÖ´Â ±ÍÁßÇÑ °æÇèÀû Á¤º¸´Â ´ëºÎºÐ ¼Õ½ÇµÈ´Ù. ¿¹¸¦ µé¾î Á¤Á÷ÇÑ ÆÇ»ç´Â ¸ðµÎ ÃæºÐÇÑ ±³À°À» ¹Þ¾Ò´Ù´Â »ç½ÇÀÌ ÁÖ¾îÁ³´Ù°í °¡Á¤ÇÒ ¶§, ÀÌ°ÍÀ» ´ÙÀ½°ú °°ÀÌ Ç¥±âÇÒ ¼ö ÀÖ´Ù :

    ¢£x judge(x) ¡ü ~crooked(x) ¡æ educated(x)

ÀÌ Ç¥±âµÈ ¾ð¸íÀ¸·ÎºÎÅÍ, ¾î¶² »ç¶÷ÀÌ ±³À°À» ¹Þ¾Ò´Ù´Â °ÍÀ» ¿¬¿ª Ãß·ÐÇÒ ¼ö ÀÖ´Ù. ±×·¯³ª, À§ ¾ð¸íÀ» ´ÙÀ½°ú °°Àº ÀýÀÇ ÇüÅÂ

    ~judge(x) ¡ý crooked(x) ¡ý educated(x)

·Î º¯È¯½ÃÅ°¸é, ÀÌ°ÍÀº Á¤Á÷ÇÏÁö¸¸ ±³À°À» ¹ÞÁö ¾Ê¾Ò´Ù´Â °ÍÀ» º¸ÀÓÀ¸·Î½á, ¾î¶² »ç¶÷ÀÌ Æǻ簡 ¾Æ´Ï¶ó´Â °ÍÀ» ¿¬¿ª Ãß·ÐÇÏ´Â °Íó·³ º¸ÀδÙ. ¹°·Ð ³í¸®Àû Àǹ̷Πº¼ ¶§ ÀÌ°ÍÀº »ç½ÇÀÌ´Ù. ±×·¯³ª ÀÌ°ÍÀº ¾î¶² »ç¶÷ÀÌ Æǻ簡 ¾Æ´Ï¶ó´Â °ÍÀ» º¸À̱⿡´Â ¸Å¿ì ºÎÀûÇÕÇÑ ¹æ¹ýÀÌ´Ù. ¿ø·¡ÀÇ ¾ð¸í¿¡ Æ÷ÇԵǾî ÀÖ´ø °æÇèÀû Á¤º¸°¡ ÀÌ º¯È¯À¸·Î ÀÎÇØ ¼Õ½ÇµÇ¾ú´Ù.

Á¤¸® Áõ¸í ½Ã½ºÅÛÀÇ ±âº»À¸·Î ºñ±³ Èí¼ö ¹æ¹ýÀ» »ç¿ëÇÒ ¶§ ¼ö¹ÝµÇ´Â ¶Ç ´Ù¸¥ ¹®Á¦´Â Àΰ£ÀÇ »ç°í °úÁ¤ÀÌ ºñ±³ Èí¼ö ¹æ¹ý¿¡ µû¶ó ÇàÇØÁöÁö ¾Ê´Â´Ù´Â Á¡ÀÌ´Ù. µû¶ó¼­ ºñ±³ Èí¼ö °úÁ¤À» »ç¿ëÇÑ Á¤¸® Áõ¸í °úÁ¤À¸·ÎºÎÅÍ Ãæ°í¸¦ ¹Þ°Å³ª, ȤÀº ÀÌ Á¤¸® Áõ¸í °úÁ¤¿¡ Ãæ°í¸¦ ÁÖ°íÀÚ ÇÒ ¶§, Àΰ£°ú Á¤¸® Áõ¸í °úÁ¤ÀÌ ¼­·Î »óÈ£ ÀÛ¿ëÇϱâ¶õ ¸Å¿ì ¾î·Á¿î ÀÏÀÌ´Ù. »ó´çÈ÷ ¾î·Á¿î ¹®Á¦¿¡ ´ëÇÑ Áõ¸íÀ» ¼öÇàÇϱâ À§ÇØ ÄÄÇ»Å͸¦ »ç¿ëÇÏ´Â °ÍÀº ¾ÆÁ÷ ¹Ì¼÷ÇÑ ´Ü°èÀ̱⠶§¹®¿¡ ½ÇÁúÀûÀÎ ¸é¿¡¼­ º¼ ¶§, ÀÌ·¯ÇÑ »óÈ£ ÀÛ¿ëÀÌ °¡´ÉÇÏ´Ù´Â °ÍÀº ¸Å¿ì Áß¿äÇÑ ¿ªÇÒÀ» ÇÑ´Ù. À̸¦ ½±°Ô Çϱâ À§ÇØ ÄÄÇ»ÅÍÀÇ Áõ¸í ¼öÇà °úÁ¤À» °¡´ÉÇÑ ÇÑ, Àΰ£ÀÇ Áõ¸í ¼öÇà °úÁ¤°ú À¯»çÇØÁöµµ·Ï ÇÑ´Ù. ¿¬¿ª¹ýÀÌ À̸¦ À§ÇØ »ç¿ëµÈ´Ù.

¿¬¿ª¹ýÀº Á¤È®ÇÑ ¿ë¾î¶ó±âº¸´Ù´Â ¾î¶² ÇÑ °¡Áö ¹æ¹ý¸¸À¸·Î´Â Ç® ¼ö ¾ø´Â ¹®Á¦¸¦ Ç®±â À§ÇØ ¿©·¯ ±â¹ýÀ» °áÇÕ »ç¿ëÇÑ È¥ÇÕ¹°·Î¼­ ¼³¸íµÈ´Ù. ÀϹÝÀûÀÎ ÇÑ °¡Áö ±â¹ýÀ» Áö±Ý±îÁöó·³ ¼­¼úÇü ¸íÁ¦¿¡ µû¶ó Áö½ÄÀ» ¹è¿­ÇÏ´Â °ÍÀÌ ¾Æ´Ï¶ó, ¼­¼úÇü ¸íÁ¦ ³»¿¡ Æ÷ÇÔµÈ ¹°Ã¼¿¡ µû¶ó Áö½ÄÀ» ¹è¿­ÇÏ´Â ¹æ¹ýÀÌ´Ù. Á¦ 7 Àå¿¡¼­, À̸¦ À§ÇÑ ¿©·¯ ±â¹ýµéÀÌ ´Ù·ç¾îÁø´Ù. ¶Ç ´Ù¸¥ ±â¹ýÀº ³í¸®Àû ³»Æ÷ (logical implication) ¸¦ ±â¼úÇÒ »Ó¸¸ ¾Æ´Ï¶ó, Áõ¸í °úÁ¤¿¡¼­ ÀÌ ³»Æ÷¸¦ »ç¿ëÇÒ ¼ö ÀÖ´Â ¹æ¹ýÀ» ¾Ë·Á ÁÖ´Â ÀçÇ¥±â ±ÔÄ¢ (rewrite rule) ÀÇ ÁýÇÕÀ» »ç¿ëÇÏ´Â °ÍÀÌ´Ù.

6. ¿ä¾à

ÀÌ Àå¿¡¼­´Â Áö½Ä Ç¥±â¹ýÀ» À§ÇÑ ±â¹ýÀÇ Åä´ë·Î ¼­¼ú ³í¸®¸¦ »ç¿ëÇÏ´Â ¹æ¹ýÀ» ¼³¸íÇÏ¿´´Ù. ¶ÇÇÑ, Áö½ÄÀ» ÀÌ ¹æ¹ýÀ¸·Î Ç¥±âÇÒ ¶§ Àû¿ëÇÒ ¼ö ÀÖ´Â ¹®Á¦ Ç®ÀÌ ±â¹ýÀÎ ºñ±³ Èí¼ö ¹æ¹ýÀ» ¼³¸íÇÏ¿´´Ù. ºñ±³ Èí¼ö °úÁ¤Àº Á¤¸®°¡ ¾Æ´Ñ °ÍÀ» Áõ¸íÇÏ°íÀÚ ÇÒ ¶§, ƒP³ªÁö ¾ÊÀ» ¼ö ÀÖ´Ù. ±×·¯³ª, Áõ¸íÀÌ Á¸ÀçÇÑ´Ù¸é ¸ð¼øÀ» ã¾Æ Áõ¸íÀ» ³¡³¾ ¼ö ÀÖ´Ù°í º¸ÀåÇÒ ¼ö Àִ°¡? ÀÌ°ÍÀ» ¿ÏÀü¼º ¹®Á¦ (completeness problem) ¶ó°í ÇÑ´Ù. ¾Ë°í¸®ÁòÀ» ¼Ò°³ÇÑ ÇüÅ¿¡¼­ ÀÌ Áú¹®¿¡ ´ëÇÑ ´äÀº '¾Æ´Ï¿À' ÀÌ´Ù. ¿ÏÀü¼ºÀ» º¸ÀåÇϱâ À§Çؼ­´Â ¾à°£ÀÇ ¼öÁ¤ÀÌ ÇÊ¿äÇѵ¥, ÀÌ°ÍÀº ´ëü·Î Á¤¸® Áõ¸í ½Ã½ºÅÛ¿¡¼­´Â ±¸ÇöµÇÁö ¾Ê´Â´Ù. ±×·¯³ª °è»êÀûÀÎ Ãø¸é¿¡¼­ º¼ ¶§ ¿ÏÀü¼ºÀº Áß¿äÇÏÁö ¾Ê´Ù. ´ë½Å Çã¿ëµÈ ½Ã°£ ³»¿¡ Áõ¸íÀ» ãÀ» ¼ö ÀÖ´Â ÀûÇÕÇÑ °æÇèÀû ¹æ¹ýÀÌ Á¸ÀçÇÏ´ÂÁöÀÇ ¿©ºÎ°¡ ´õ Áß¿äÇÏ´Ù.

Àΰø Áö´É ºÐ¾ß¿¡ Á¤¸® Áõ¸íÀ» ½ÃµµÇÒ ¶§ ¼ö¹ÝµÇ´Â µÎ¹ø° ³­Á¡Àº ÀϺΠÁ¤º¸´Â ¼­¼ú ³í¸®·Î ½±°Ô ³ªÅ¸³¾ ¼ö ¾ø´Ù´Â °ÍÀÌ´Ù. ÀÌ¿¡ ´ëÇÑ ¿¹°¡ ´ÙÀ½ ÀåÀÇ ¼­µÎ¿¡ ¼Ò°³µÈ´Ù. Áï ÀÌ Àå¿¡¼­ ¼Ò°³µÈ ¹æ¹ýÀº ÀϺΠºÐ¾ß¿¡¼­´Â »ó´çÈ÷ À¯¿ëÇÏÁö¸¸, ¸ðµç Àΰø Áö´É ¹®Á¦ÀÇ Ç®À̸¦ ã´Â µ¥´Â ºÎÀûÇÕÇÏ´Ù.

7. ¿¬½À¹®Á¦

1. 3 Àý¿¡¼­ ÁÖ¾îÁø »ç½Ç¿¡ ´ëÇØ

        ~alive(Marcus, now)

    °¡ µÎ °¡Áö ¹æ¹ý¿¡ ÀÇÇØ Áõ¸íµÇ´Â °ÍÀ» º¸¾Ò´Ù. ±×¸² 12 ¿¡¼­ ÀÌ µÎ °¡Áö ¹æ¹ý ÁßÀÇ Çϳª¿¡ ´ëÀÀÇÏ´Â ºñ±³ Èí¼ö °úÁ¤¿¡ ÀÇÇÑ Áõ¸íÀÌ º¸¿©Á³´Ù. ºñ±³ Èí¼ö °úÁ¤À» »ç¿ëÇÏ¿© ¾ð¸íÀÇ ¶Ç ´Ù¸¥ Áõ¸íÀ» Ãß·ÐÇ϶ó.

2. Ç×µéÀÇ ´ÙÀ½ °¢ ½Ö¿¡ ´ëÇØ ´ÜÀÏÈ­ ¾Ë°í¸®ÁòÀÌ ¾î¶»°Ô ÀÛ¿ëÇÏ´ÂÁö Á¶»çÇ϶ó :

   a. (f Marcus) (f Caesar)
b. (f x) (f g(y))
c. (f Marcus(g x y)) (f x(g(Caesar Marcus))

3. ´ÙÀ½ ¹®Àå¿¡ ´ëÇØ

        John likes all kinds of food.
    Apples are food.
    Chicken is food.
    Anything anyone eats and isn't killed by is food.
    Bill eats peanuts and is still alive.
    Sue eats everything Bill eats.

    a. À§ ¹®ÀåµéÀ» ¼­¼ú ³í¸®ÀÇ Çü½ÄÀ¸·Î °íÃĶó.
b. ÀÌ Çü½ÄÀ¸·Î Ç¥±âµÈ ¾ð¸íÀ» ÀýÀÇ ÇüÅ·Πº¯È¯Ç϶ó.
c. ºñ±³ Èí¼ö °úÁ¤À» »ç¿ëÇÏ¿©, Á¸ÀÌ ¶¥ÄáÀ» ÁÁ¾ÆÇÑ´Ù´Â °ÍÀ» Áõ¸íÇ϶ó.
d. "What food does Sue eat? (¼ö´Â ¾î¶² À½½ÄÀ» ¸Ô´Â°¡?)" ¸¦ ºñ±³ Èí¼ö °úÁ¤À» »ç¿ëÇÏ¿© ´äÇ϶ó.

4. ´ÙÀ½ »ç½Ç¿¡ ´ëÇØ

       The members of the Elm St. Bridge Club are Joe, Sally, Bill and Ellen.
   Joe is married to Sally.
   Bill is Ellen's brother.
   The spouse of every married person in the club is also in the club.
   The last meeting of the club was at Joe's house.

    a. ¼­¼ú ³í¸®·Î ÀÌ »ç½ÇÀ» Ç¥±âÇ϶ó.
b. À§¿¡ ÁÖ¾îÁø »ç½Ç·ÎºÎÅÍ ´ÙÀ½ ¾ð¸íÀÇ Áø¸®°ªÀ» °áÁ¤ ÇÒ ¼ö ÀÖ´Ù.

À§¿¡ ÁÖ¾îÁø ´Ù¼¸ °¡Áö »ç½Ç·ÎºÎÅÍ ÀÌ ¾ð¸í °¢°¢¿¡ ´ëÇÑ Áø¸®°ªÀ» ³ªÅ¸³»´Â ºñ±³ Èí¼ö Áõ¸íÀ» ãÀ» ¼ö Àִ°¡? ¸¸¾à °¡´ÉÇÏ´Ù¸é ã¾Æ¶ó. ±×·¸Áö ¾Ê´Ù¸é, ÇÊ¿äÇÑ »ç½ÇÀ» ÷°¡ÇÏ¿© Áõ¸íÀ» ã¾Æ¶ó.

6. 4.7 Àý¿¡¼­ ºñ±³ Èí¼ö ¹æ¹ýÀ» »ç¿ëÇÏ¿© "When did Marcus die?" ¿¡ ´ëÇÑ ´äÀ» ã¾Æ ¸¶Ä¿½º°¡ Á×¾ú´ø ¶§°¡ ÀÖÀ½À» º¸¿´´Ù. ±×¸² 4 ¿¡ ÁÖ¾îÁø »ç½Ç¿¡

        ¢£x¢£t1 dead (x, t1) ¡æ ¢¤t2 gt(t1, t2) ¡ü died(x, t2)

    ¶ó´Â »ç½ÇÀ» ÷°¡ÇÔÀ¸·Î½á, ´Ù¸¥ ¹æ¹ýÀ¸·Î ÀÌ Áú¹®¿¡ ´ëÇÑ ´äÀ» ãÀ» ¼ö ÀÖ´Ù.

    a. ´Ù¸¥ Ãß·ÐÀÇ ¿¬¼â¸¦ »ç¿ëÇÏ¿© ºñ±³ Èí¼ö Áõ¸íÀ» Ç϶ó.
b. "When did Marcus die?" ¶ó´Â Áú¹®¿¡ ´ëÇØ ÀÌ Áõ¸íÀº ¾î¶² ´äÀ» Áִ°¡?

8. ´ÙÀ½ »ç½ÇÀÌ ÁÖ¾îÁ³´Ù°í °¡Á¤ÇÏÀÚ :

        ¢£x, y, z gt(x, y) ¡ü gt(y, z) ¡æ gt(x, z)
    ¢£a, b succ(a, b) ¡æ gt(a, b)
    ¢£x ~gt(x, x)

    ÀÌ ¶§,

        gt(5, 2)

    ¸¦ Áõ¸íÇÏ·Á ÇÑ´Ù. ´ÙÀ½ ºñ±³ Èí¼ö Áõ¸íÀ» »ìÆì º¸ÀÚ.

 

    a. ¹«¾ùÀÌ À߸øµÇ¾ú´Â°¡?
b. ÀÌ·¯ÇÑ °ÍÀÇ ¹ß»ýÀ» ¸·±â À§ÇØ ¾î¶² °ÍÀ» ºñ±³ Èí¼ö °úÁ¤¿¡ ÷°¡ÇØ¾ß Çϴ°¡?

9. ¾Õ ¹®Á¦¿¡ ´ëÇÑ ´äÀ¸·Î x ¿Í f(x) ¸¦ ÇÔ²² ´ÜÀÏÈ­ÇÏ´Â °ÍÀÇ ¹æÁö¸¦ À§ÇØ Á¶»çÇÏ´Â °úÁ¤À» »ý·«Çؼ­  ´ÜÀÏÈ­ °úÁ¤À» ´Ü¼øÈ­ÇÒ ¼ö ÀÖÀ½À» ¾Ë ¼ö ÀÖ´Ù. ÀÌ°ÍÀº ¾î¶² µÎ Àýµµ º¯¼ö¸¦ °øÀ¯ÇÒ ¼ö ¾ø±â ¶§¹®¿¡ °¡´ÉÇÏ´Ù. ¸¸¾à x °¡ ÇÑ Àý¿¡ ³ªÅ¸³­´Ù¸é f(x) ´Â ´Ù¸¥ Àý¿¡ ³ªÅ¸³¯ ¼ö ¾ø´Ù. ´ÜÀÏÈ­ °úÁ¤¿¡ ´ÙÀ½ µÎ ÀýÀÌ ÁÖ¾îÁ³´Ù°í °¡Á¤ÇÏÀÚ :

        (p x f(x))
    (p f(a) a)

    ÀÌ °úÁ¤ÀÇ ¼öÇàÀ» Á¶»çÇ϶ó.

10. ´ÙÀ½ »ï´Ü ³í¹ý¿¡ ¹ß»ýÇÑ À߸øÀº ¹«¾ùÀΰ¡?

       Men are widely distributed over the earth.
   Socrates is a man.
   Therefore, Socrates is widely distributed over the earth.

    ÀÌ·¯ÇÑ ¹®Á¦ÀÇ ¹ß»ýÀ» ¸·±â À§ÇØ ¾î¶² ¹æ¹ýÀ¸·Î »ç½ÇÀ» Ç¥±âÇØ¾ß Çϴ°¡?

11. ´ÙÀ½°ú °°Àº ¾ð¸íÀ» ¼­¼ú ³í¸®·Î Ç¥±âÇÏ°íÀÚ ÇÑ´Ù¸é ¾î¶°ÇÑ ¹®Á¦°¡ ¹ß»ýÇϴ°¡? ¿©±â¼­´Â ¸¶Áö¸· ¾ð¸íÀ» ´Ù¸¥ ¾ð¸íÀ¸·ÎºÎÅÍ Ãß·ÐÇÒ ¼ö ÀÖ´Ù :

       John only likes seeing French movies.
   It is safe to assume a movie is American unless explicifly told otherwise.
   People don't to things that will cause them to be in situations that they don't like.
   John does not go to the Playhouse very often.