هوش مصنوعی CS50 s1

آموزش هوش مصنوعی

دوره کامل آموزش هوش مصنوعی بر مبنای دوره CS5 دانشگاه هاروارد به عنوان معتبرترین و جامع ترین دوره آموزش مقدماتی و مفهومی هوش مصنوعی شناخته می شود.

این دوره به بررسی دقیق و عمیق مباحث هوش مصنوعی به صورت پایه ای می پردازد و شامل 7 بخش میباشد .جهت دسترسی به سایر دوره ها می توانید از لینک های زیر استفاده نمایید.

1. مقالات هوش مصنوعی CS50 s0

2. مقالات هوش مصنوعی CS50 s2

3. مقالات هوش مصنوعی CS50 s3

4. مقالات هوش مصنوعی CS50 s4

5. مقالات هوش مصنوعی CS50 s5

6. آموزش هوش مصنوعی بخش آخر CS506

و برای مشاهده لیست تمام دوره ها به بخش مقالات مراجه نمایید.

CS50’s Introduction to Artificial Intelligence with Python

Danix Ai

دانش (Knowledge)

مقالات هوش مصنوعی CS50’s1 : انسان‌ها بر اساس دانشی که از قبل دارند استدلال می‌کنند و به نتیجه می‌رسند. همین مفهومِ بازنمایی دانش و نتیجه‌گیری از آن در هوش مصنوعی نیز به کار می‌رود و در این درس بررسی می‌کنیم که چگونه می‌توان چنین رفتاری را در هوش مصنوعی ایجاد کرد.

عامل‌های مبتنی بر دانش (Knowledge-Based Agents)

این عامل‌ها با کار کردن روی بازنمایی‌های درونی دانش، استدلال می‌کنند.
اما «استدلال مبتنی بر دانش برای نتیجه‌گیری» دقیقاً یعنی چه؟

برای پاسخ به این سؤال، با یک مثال از هری پاتر شروع می‌کنیم. جملات زیر را در نظر بگیرید:

1. اگر باران نباریده باشد، هری امروز به دیدن ‌هاگرید رفته است.
2. هری امروز یا به دیدن هاگرید رفته است یا دامبلدور، اما نه هر دو.
3. هری امروز به دیدن دامبلدور رفته است.

بر اساس این سه جمله می‌توانیم به پرسش «آیا امروز باران باریده؟» پاسخ بدهیم، حتی با اینکه هیچ‌یک از جمله‌ها به‌طور مستقیم دربارهٔ باران حرفی نمی‌زنند.

در ادامه استدلال را می‌بینیم:

با توجه به جملهٔ ۳ می‌دانیم هری به دیدن دامبلدور رفته است.
با توجه به جملهٔ ۲ می‌دانیم او یا به دیدن دامبلدور رفته یا هاگرید، و چون دامبلدور را ملاقات کرده، پس نتیجه می‌گیریم:

1. هری به دیدن هاگرید نرفته است.

اکنون جملهٔ ۱ را در نظر می‌گیریم: اگر باران نباریده باشد، هری باید به هاگرید سر می‌زد. اما از جملهٔ ۴ می‌دانیم این اتفاق نیفتاده است. بنابراین نتیجه می‌گیریم:

1. امروز باران باریده است.

برای رسیدن به این نتیجه، از منطق استفاده کردیم. در این درس بررسی می‌کنیم که هوش مصنوعی چگونه از منطق برای رسیدن به اطلاعات جدید بر اساس اطلاعات موجود استفاده می‌کند.

جمله (Sentence)

یک جمله ادعایی دربارهٔ جهان است که در یک زبان نمایش دانش بیان می‌شود. جمله ابزاری است که هوش مصنوعی از آن برای ذخیرهٔ دانش و استنتاج اطلاعات جدید استفاده می‌کند. 

منطق گزاره‌ای (Propositional Logic)

منطق گزاره‌ای بر پایهٔ گزاره‌ها ساخته شده است؛ گزاره‌ها گفته‌هایی دربارهٔ جهان‌اند که می‌توانند «درست» یا «نادرست» باشند، مانند جمله‌های ۱ تا ۵ در بالا.

نمادهای گزاره‌ای (Propositional Symbols)

نمادهای گزاره‌ای معمولاً حروفی مانند P، Q، R  هستند که برای نمایش یک گزاره استفاده می‌شوند.

اتصال‌دهنده‌های منطقی (Logical Connectives)

اتصال‌دهنده‌های منطقی نمادهایی هستند که گزاره‌ها را به هم وصل می‌کنند تا بتوانیم دربارهٔ جهان استدلال‌های پیچیده‌تری انجام دهیم.

• نفی  (¬) ارزشِ حقیقتِ گزاره را معکوس می‌کند.
  مثلاً اگر P: باران می‌بارد باشد، آنگاه ¬P یعنی: «باران نمی‌بارد.

جدول‌های حقیقت (Truth Tables) برای بررسی همهٔ حالت‌های ممکنِ درست یا نادرست بودن گزاره‌ها به‌کار می‌روند. این ابزار کمک می‌کند ارزش‌های حقیقتِ گزاره‌ها را هنگام استفاده از اتصال‌دهنده‌های مختلف بهتر درک کنیم.
برای نمونه، اولین جدول حقیقت ما به شکل زیر است:

و (∧)

علامت And  یا همان ∧ دو گزاره را به هم وصل می‌کند. هنگامی که دو گزاره P و Q با ∧ به هم متصل شوند، حاصلِ P ∧ Q فقط زمانی درست است که هر دو گزارهٔ P و Q درست باشند.

یا (∨) 

Or زمانی درست است که حداقل یکی از گزاره‌هایش درست باشد.
یعنی برای درست بودن P ∨ Q، کافی است یکی از P یا Q درست باشد.

یا فراگیر و یا انحصاری

دو نوع «یا» وجود دارد:

• یا فراگیر (Inclusive Or): اگر P یا Q درست باشد—یا هر دو—گزاره درست است.
• یا انحصاری (Exclusive Or) یا   XOR : اگر هر دو P و Q درست باشند، گزاره نادرست می‌شود. فقط یکی باید درست باشد.

مثال برای یا فراگیر:
«برای اینکه دسر بخوری، باید اتاقت را تمیز کنی یا چمن را کوتاه کنی.»
اگر هر دو کار را انجام دهی هم باز دسر را می‌گیری.

مثال برای یا انحصاری:
«برای دسر می‌توانی یا کلوچه بخوری یا بستنی.»
این‌جا نمی‌توانی هر دو را بخوری.

نماد رایج برای یا انحصاری: ⊕ است.

شرطی (→)

Implication یا «اگر … آنگاه …» رابطه‌ای بین دو گزاره است.
اگر P: باران می‌بارد و  Q: من داخل خانه هستم.
آنگاه P → Q یعنی: «اگر باران می‌بارد، پس من داخل خانه‌ام».

• P پیش‌شرط (antecedent) نامیده می‌شود
• Q نتیجه (consequent)

قواعد ارزش truth آن:

• اگر P درست باشد و Q درست باشد → جمله درست است.
• اگر P درست باشد و Q نادرست باشد → جمله نادرست است.
• اگر P نادرست باشد → جمله همیشه درست است؛ به این می‌گویند «درستِ بدیهی» (trivially true).

این بخش گاهی گیج‌کننده است:
اگر پیش‌شرط (P) نادرست باشد، جملهٔ شرطی هیچ اطلاعاتی دربارهٔ Q به ما نمی‌دهد.

دوشرطی (↔)

Biconditional یا ↔ یعنی «اگر و تنها اگر».

عبارت P ↔ Q برابر است با دو شرطی در هر دو جهت:

• P → Q
• Q → P

مثلاً اگرP  :باران می‌بارد و Q : »من داخل خانه هستم«،
آنگاه P ↔ Q یعنی:

• اگر باران می‌بارد، من داخل هستم.
• و اگر من داخل هستم، باران می‌بارد.

در این حالت، اگر P نادرست باشد (باران نبارد)، Q هم باید نادرست باشد (من داخل نیستم).

مدل (Model)

مدل ،اختصاص ارزشِ حقیقت به هر گزاره است.

مثلاً:

اگر P:  »باران می‌بارد« و Q: »امروز سه‌شنبه است. «
یک مدل می‌تواند این باشد:

{P = True, Q = False}
یعنی: باران می‌بارد، اما امروز سه‌شنبه نیست.

تعداد مدل‌های ممکن برابر است با:

در مثال بالا ۲ گزاره داریم .4 =2² مدل ممکن.

پایگاه دانش (Knowledge Base – KB)

پایگاه دانش مجموعه‌ای از جمله‌هایی است که یک عامل مبتنی بر دانش می‌داند. این جمله‌ها به صورت منطق گزاره‌ای تعریف می‌شوند و هوش مصنوعی می‌تواند بر اساس آن‌ها نتیجه‌گیری کند.

استلزام (⊨)

اگر α ⊨ β یعنی:

در هر دنیایی که α درست باشد، β نیز درست است.

مثلاً:

α :  سه‌شنبه‌ای در ماه ژانویه است.
: β ژانویه است.
پس α ⊨ β.

تفاوت مهم:

•   (→) Implication یک نماد منطقی بین دو گزاره است.
• Entailment   (⊨) یک رابطهٔ معنایی است: هرچه α بگوید درست باشد، β هم باید درست باشد.

استنتاج (Inference)

استنتاج یعنی تولید جمله‌های جدید از جمله‌های قبلی.
در مثال هری پاتر، جمله‌های ۵ و ۴ از ۳ و۲ و۱ استنتاج شدند.

یکی از روش‌های استنتاج: بررسی مدل (Model Checking).

بررسی مدل (Model Checking)

برای اینکه بفهمیم آیا KB ⊨ α است یا نه، باید:

1. همهٔ مدل‌های ممکن را فهرست کنیم.
2. اگر در هر مدلی که KB درست باشد، α نیز درست بود → آنگاه KB α را مستلزم می‌شود.

مثال هوش مصنوعی CS50 s1:

P: امروز سه‌شنبه است.
Q: باران می‌بارد.
R: هری برای دویدن بیرون می‌رود.

KB: (P ∧ ¬Q) → R
یعنی: اگر سه‌شنبه باشد و باران نبارد، هری می‌دود.

دانش KB:

• P درست است
• Q نادرست است → پس ¬Q درست است

پرسش:
آیا می‌توان نتیجه گرفت R درست است؟

(KB ⊨ R ?)

برای پاسخ باید همهٔ مدل‌های ممکن را بررسی کنیم

در مثال زیر داریم:

P: امروز سه‌شنبه است.
Q: باران می‌بارد.
R: هری برای دویدن می‌رود.

پایگاه دانش (KB):

(P∧¬Q)→R(P ∧ ¬Q) → R(P∧¬Q)→R

به عبارت دیگر: اگر P درست باشد و Q نادرست، آنگاه R برقرار است.

اطلاعاتی که داریم:
P درست است.
¬Q یعنی Q نادرست است.

پرسش:
R؟ — می‌خواهیم بدانیم آیا R درست است یا نه؛ یعنی آیا KB نتیجه می‌دهد که R برقرار است یا خیر

؟KB ⊨ R

برای پاسخ دادن به پرسش با الگوریتم بررسی مدل‌ها (Model Checking)، همهٔ مدل‌های ممکن را بررسی می‌کنیم.

سپس تمام مدل‌ها را یک‌به‌یک بررسی می‌کنیم تا ببینیم با توجه به پایگاه دانش (KB) درست هستند یا نه.
ابتدا، در پایگاه دانش می‌دانیم که P درست است.
بنابراین، می‌توانیم بگوییم در هر مدلی که P نادرست باشد، پایگاه دانش نادرست است و آن مدل را کنار می‌گذاریم.

سپس، به‌طور مشابه، در پایگاه دانش می‌دانیم که Q نادرست است.
بنابراین، می‌توانیم بگوییم در هر مدلی که Q درست باشد، پایگاه دانش نادرست است و آن مدل را کنار می‌گذاریم.

در نهایت، دو مدل برایمان باقی می‌ماند.

در هر دوی آن‌ها P درست و Q نادرست است.
در یکی از مدل‌ها R درست است و در مدل دیگر R نادرست.

به دلیل وجود جملهٔ (P ∧ ¬Q) → R در پایگاه دانش، می‌دانیم هرگاه P درست و Q نادرست باشد، R باید درست باشد.
بنابراین، می‌گوییم مدلِی که در آن R نادرست است با پایگاه دانش سازگار نیست و پایگاه دانش در آن مدل نادرست است.

و مدلِی که در آن R درست است با پایگاه دانش سازگار است و پایگاه دانش در آن مدل درست است.

با نگاه کردن به این جدول، فقط یک مدل وجود دارد که در آن پایگاه دانش ما درست است.
در آن مدل، می‌بینیم که R نیز درست است.

بر اساس تعریف نتیجه‌گیری (entailment)، اگر R در تمام مدل‌هایی که KB در آن‌ها درست است، درست باشد، آنگاه
KB ⊨ R برقرار است.

حال، بیایید ببینیم دانش و منطق چگونه می‌توانند در قالب کد نمایش داده شوند.

from logic import *
# Create new classes, each having a name, or a symbol, representing each proposition.
rain = Symbol("rain")  # It is raining.
hagrid = Symbol("hagrid")  # Harry visited Hagrid
 dumbledore = Symbol("dumbledore")  # هری به دامبلدور سر زده است
# ذخیرهٔ گزاره‌ها در پایگاه دانش (KB)
knowledge = And(   # از عملگر «و» (And) استفاده می‌کنیم چون هر گزاره یک جمله‌ی مستقل در KB است
    Implication(Not(rain), hagrid),     # اگر باران نبارد → هری به هاگرید سر می‌زند
    Or(hagrid, dumbledore),             # هری یا به هاگرید رفته یا به دامبلدور
    Not(And(hagrid, dumbledore)),       # هری نمی‌تواند همزمان به هر دو رفته باشد
    dumbledore                          # هری به دامبلدور سر زده است
)

برای اجرای الگوریتم بررسی مدل‌ها (Model Checking)، اطلاعات زیر لازم است:

1. پایگاه دانش (Knowledge Base): که برای نتیجه‌گیری استفاده می‌شود.
2. پرسش (Query): گزاره‌ای که می‌خواهیم ببینیم آیا از پایگاه دانش استنتاج می‌شود یا خیر.
3. نمادها (Symbols): لیستی از تمام نمادها یا گزاره‌های اتمی که استفاده شده‌اند (در مثال ما، این‌ها hagride وDumbledore هستند)
4. مدل (Model): تخصیص مقادیر درست و نادرست به نمادها.

def check_all(knowledge, query, symbols, model):
    """
    الگوریتم بررسی مدل‌ها:
    بررسی می‌کند که آیا query در تمام مدل‌هایی که knowledge درست است،
    نیز درست است یا خیر.
    
    knowledge: پایگاه دانش (KB)
    query: گزاره‌ای که می‌خواهیم بررسی کنیم
    symbols: لیست نمادهای باقی‌مانده
    model: مدل فعلی (تخصیص درست/نادرست به نمادها)
    """

    # اگر همه نمادها در مدل تخصیص داده شده‌اند
    if not symbols:
        # اگر پایگاه دانش در این مدل درست باشد، باید query هم درست باشد
        if knowledge.evaluate(model):
            return query.evaluate(model)
        # اگر پایگاه دانش در این مدل درست نباشد، تاثیری بر نتیجه entailment ندارد
        return True
    else:
        # انتخاب یکی از نمادهای باقی‌مانده
        remaining = symbols.copy()
        p = remaining.pop()
        # ایجاد مدلی که نماد p درست باشد
        model_true = model.copy()
        model_true[p] = True
        # ایجاد مدلی که نماد p نادرست باشد
        model_false = model.copy()
        model_false[p] = False

        # بررسی بازگشتی برای هر دو حالت و اطمینان از صحت entailment
        return (check_all(knowledge, query, remaining, model_true) and
                check_all(knowledge, query, remaining, model_false))

توجه داشته باشید که ما تنها به مدل‌هایی علاقه‌مندیم که در آن‌ها پایگاه دانش (KB) درست است. اگر KB نادرست باشد، شرایطی که می‌دانیم درست هستند در این مدل‌ها برقرار نیستند و بنابراین برای ما بی‌اهمیت هستند.

هوش مصنوعی CS50 s1 — مثالی خارج از درس:
فرض کنید:

• P: هری نقش جستجوگر (seeker) را بازی می‌کند
• Q: اولیور نقش دروازه‌بان (keeper) را بازی می‌کند
• R: گریفیندور برنده می‌شود

پایگاه دانش ما مشخص می‌کند که R→ (P ∧ Q)  به عبارت دیگر:

• می‌دانیم P درست است، یعنی هری جستجوگر بازی می‌کند.
• می‌دانیم Q درست است، یعنی اولیور دروازه‌بان بازی می‌کند.
• و اگر هر دو P و Q درست باشند، آنگاه R درست است، یعنی گریفیندور برنده مسابقه می‌شود.

حالا فرض کنید مدلی وجود دارد که هری به جای جستجوگر، نقش ضربه‌زننده (beater) را بازی کرده باشد (پس P نادرست است ¬P )
در این حالت، برای ما اهمیتی ندارد که آیا گریفیندور برنده شد یا نه )R درست است یا نادرست(، چون پایگاه دانش ما می‌گوید هری جستجوگر بازی کرده است و نه ضربه ‌زننده. ما تنها به مدل‌هایی علاقه‌مندیم که در آن‌ها P و Q درست هستند.

علاوه بر این، تابع  check all به صورت بازگشتی عمل می‌کند.

یعنی:

• یک نماد را انتخاب می‌کند.
• دو مدل ایجاد می‌کند: در یکی این نماد درست است و در دیگری نادرست.
• سپس دوباره خودش را با این دو مدل فراخوانی می‌کند، که فقط با تخصیص درست/نادرست این نماد متفاوت هستند.
• این فرآیند ادامه می‌یابد تا تمام نمادها در مدل‌ها تخصیص داده شوند و لیست symbols خالی شود.
• وقتی لیست خالی شد (خط if not symbols)، در هر نمونه از تابع (که هر کدام یک مدل متفاوت دارند)، بررسی می‌شود که آیا KB در آن مدل درست است یا خیر. اگر KB درست باشد، بررسی می‌شود که query هم درست باشد یا خیر، همان‌طور که قبلاً توضیح داده شد.

مهندسی دانش (Knowledge Engineering)

مهندسی دانش فرآیندی است برای تعیین اینکه چگونه گزاره‌ها و منطق را در هوش مصنوعی نمایش دهیم.

بیایید مهندسی دانش را با بازی Clue تمرین کنیم.
در این بازی، یک قتل توسط یک نفر با یک ابزار در یک مکان انجام شده است. افراد، ابزارها و مکان‌ها با کارت‌ها نمایش داده می‌شوند. یک کارت از هر دسته به صورت تصادفی انتخاب شده و در پاکتی قرار می‌گیرد و هدف بازیکنان این است که بفهمند چه کسی قاتل است. بازیکنان با دیدن کارت‌ها و استنتاج از آن‌ها، تلاش می‌کنند محتوای پاکت را حدس بزنند.

ما از الگوریتم Model Checking که پیش‌تر معرفی شد برای کشف این راز استفاده می‌کنیم.

• در مدل ما، آیتم‌هایی که می‌دانیم با قتل مرتبط هستند True و سایر موارد False علامت‌گذاری می‌شوند.

برای مثال، فرض کنید:

• سه نفر: Mustard، Plum و Scarlet

• سه ابزار: چاقو (knife)، هفت‌تیر (revolver) و آچار (wrench)

• سه مکان: سالن رقص (ballroom)، آشپزخانه (kitchen) و کتابخانه (library)

می‌توانیم پایگاه دانش خود را با افزودن قوانین بازی بسازیم:

• می‌دانیم یک نفر قاتل است، یک ابزار استفاده شده و قتل در یک مکان رخ داده است.
• این موضوع در منطق گزاره‌ای به شکل زیر نمایش داده می‌شود:

(Mustard ∨ Plum ∨ Scarlet)

(knife ∨ revolver ∨ wrench)

(ballroom ∨ kitchen ∨ library)

• بازی با این شروع می‌شود که هر بازیکن یک نفر، یک ابزار و یک مکان را می‌بیند و بنابراین می‌داند که این‌ها با قتل مرتبط نیستند. بازیکنان این اطلاعات را با دیگران به اشتراک نمی‌گذارند.

فرض کنید بازیکن ما کارت‌های Mustard، kitchen و revolver را دارد.

• پس ما می‌دانیم این‌ها با قتل مرتبط نیستند و می‌توانیم به پایگاه دانش خود اضافه کنیم:

¬Mustard

¬kitchen

• در سایر وضعیت‌ها در بازی، بازیکن می‌تواند حدس بزند و یک ترکیب از فرد، ابزار و مکان را پیشنهاد دهد.
• فرض کنید حدس زده شود که Scarlet با آچار (wrench) قتل را در کتابخانه (library) انجام داده است.

اگر این حدس اشتباه باشد، می‌توان استنتاج زیر را انجام داد و به پایگاه دانش اضافه کرد:

(¬Scarlet ∨ ¬library ∨ ¬wrench)

حالا فرض کنید کسی به ما کارت Plum را نشان دهد.

در این صورت می‌توانیم این را به KB اضافه کنیم:

¬Plum

در این مرحله، می‌توان نتیجه گرفت که قاتل Scarlet است، زیرا باید یکی از Mustard، Plum یا Scarlet باشد و شواهد نشان می‌دهد که دو نفر اول نیستند.

اگر تنها یک قطعه اطلاعات دیگر اضافه کنیم، برای مثال قتل در سالن رقص (ballroom) نبوده است، می‌توانیم اطلاعات بیشتری به دست آوریم:

¬ballroom

حالا با استفاده از داده‌های قبلی می‌توان استنتاج کرد که Scarlet با چاقو (knife) در کتابخانه قتل را انجام داده است.

می‌دانیم مکان باید یکی از سالن رقص، آشپزخانه یا کتابخانه باشد و دو مکان اول رد شده‌اند، پس مکان کتابخانه است.

حدس قبلی Scarlet، library، wrench اشتباه بوده است، پس حداقل یکی از این سه عنصر نادرست است.

چون می‌دانیم Scarlet و library درست هستند، بنابراین ابزار اشتباه آچار (wrench) بوده است.

از آنجا که یکی از سه ابزار باید درست باشد و نه آچار و نه هفت‌تیر (revolver)، نتیجه می‌گیریم ابزار چاقو (knife) است.

مقالات هوش مصنوعی CS50’s1:نحوه اضافه کردن این اطلاعات به پایگاه دانش در پایتون:

# اضافه کردن اطلاعات مشاهده شده
knowledge.add(Not(Mustard))   # Mustard قاتل نیست
knowledge.add(Not(Plum))      # Plum قاتل نیست
knowledge.add(Not(ballroom))  # قتل در سالن رقص نبوده است
knowledge.add(Or(Not(Scarlet), Not(library), Not(wrench)))  # حدس اشتباه است

# نتیجه‌گیری نهایی با Model Checking:
# قاتل: Scarlet
# مکان: library
# ابزار: knife

نمونه کد:  
# افزودن سرنخ‌ها به پایگاه دانش (KB)
knowledge = And(
    # شرایط اولیه بازی: باید یکی از آیتم‌ها در هر دسته درست باشد
    Or(mustard, plum, scarlet),    # یک نفر قاتل است
    Or(ballroom, kitchen, library), # یک مکان قتل وجود دارد
    Or(knife, revolver, wrench),    # یک ابزار استفاده شده است
    # اطلاعات کارت‌های اولیه که دیده‌ایم
    Not(mustard),  # Mustard قاتل نیست
    Not(kitchen),  # قتل در آشپزخانه رخ نداده است
    Not(revolver), # ابزار قتل هفت‌تیر نبوده است
    # حدسی که کسی زده: Scarlet با آچار در کتابخانه
    Or(Not(scarlet), Not(library), Not(wrench)),
    # کارت‌هایی که به ما نشان داده شده‌اند
    Not(plum),     # Plum قاتل نیست
    Not(ballroom)  # قتل در سالن رقص رخ نداده است)

می‌توانیم سایر معماهای منطقی را نیز بررسی کنیم.

هوش مصنوعی CS50 s1 – مثال:

• چهار نفر مختلف، Gil Deroy، Pomona، Minerva و Horace، به چهار خانهٔ متفاوت یعنی Gryffindor، Hufflepuff، Ravenclaw و Slytherin اختصاص داده شده‌اند. هر خانه دقیقاً یک نفر دارد.

نمایش شرایط این معما در منطق گزاره‌ای (propositional logic) کمی پیچیده است:

هر تخصیص ممکن باید یک گزاره مستقل باشد:

Minerva Gryffindor, Minerva Hufflepuff, Minerva Ravenclaw, Minerva Slytherin, Pomona Gryffindor, …

• برای نمایش اینکه هر نفر به یکی از خانه‌ها تعلق دارد، باید از یک عبارت OR(یا)، استفاده کنیم که همهٔ تخصیص‌های ممکن برای هر نفر را شامل شود:

(Minerva Gryffindor ∨ Minerva Hufflepuff ∨ Minerva Ravenclaw ∨ Minerva Slytherin)

این کار برای هر نفر تکرار می‌شود.

• برای نمایش اینکه اگر یک نفر به یک خانه اختصاص داده شود، نمی‌تواند به خانه‌های دیگر تعلق داشته باشد، باید عباراتی مانند زیر بنویسیم:

(Minerva Gryffindor → ¬Minerva Hufflepuff) ∧ (Minerva Gryffindor → ¬Minerva Ravenclaw) ∧ (Minerva Gryffindor → ¬Minerva Slytherin) ∧(Minerva Hufflepuff → ¬Minerva Gryffindor) ∧ …

و این کار برای همهٔ خانه‌ها و همهٔ افراد انجام می‌شود.

• راه‌حل بهینه‌تر برای این پیچیدگی در بخش منطق مرتبه اول (first-order logic) ارائه شده است.

با این حال، این نوع معما همچنان با منطق گزاره‌ای نیز قابل حل است، به شرط اینکه سرنخ‌های کافی موجود باشد.

هوش مصنوعی CS50 s1 – مثال دیگر:

نوع دیگری از معما که با منطق گزاره‌ای قابل حل است، بازی Mastermind است.

در این بازی، بازیکن اول رنگ‌ها را به ترتیب خاصی قرار می‌دهد.

بازیکن دوم باید ترتیب درست را حدس بزند.

در هر دور، بازیکن دوم یک حدس می‌زند و بازیکن اول یک عدد برمی‌گرداند که نشان می‌دهد چند رنگ در حدس درست بوده است.

فرض کنید یک بازی با چهار رنگ شبیه‌سازی کنیم و بازیکن دوم ترتیب زیر را پیشنهاد دهد:

• بازیکن اول پاسخ می‌دهد «دو». بنابراین می‌دانیم که دو تا از رنگ‌ها در جای درست قرار دارند و دو رنگ دیگر در جای نادرست هستند. بر اساس این اطلاعات، بازیکن دوم تلاش می‌کند جای دو رنگ را با هم عوض کند.

• اکنون بازیکن اول پاسخ می‌دهد «صفر». بنابراین بازیکن دوم می‌فهمد که رنگ‌هایی که جابه‌جا کرده بود، در ابتدا در جای درست قرار داشتند. این یعنی دو رنگی که دست‌نخورده باقی مانده بودند، در جای نادرست بوده‌اند. پس بازیکن دوم آن دو رنگ را جابه‌جا می‌کند.

بازیکن اول می‌گوید «چهار» و بازی تمام می‌شود.

• برای بازنمایی این وضعیت در منطق گزاره‌ای، لازم است به تعداد، ² (تعداد رنگ‌ها) گزارهٔ اتمیک داشته باشیم. پس در حالتی که چهار رنگ داریم، گزاره‌هایی مانند red0، red1، red2، red3، blue0… خواهیم داشت که هر یک نشان‌دهندهٔ یک رنگ و یک موقعیت هستند.
• گام بعدی این است که قوانین بازی را در منطق گزاره‌ای بازنمایی کنیم (این‌که در هر موقعیت فقط یک رنگ وجود دارد و هیچ رنگی تکرار نمی‌شود) و آن‌ها را به پایگاه دانش (KB) اضافه کنیم. گام پایانی این است که سرنخ‌ها را نیز به پایگاه دانش بیفزاییم. در مثال ما، اضافه می‌کنیم که در حدس اول، دو موقعیت اشتباه و دو موقعیت درست بوده‌اند و در حدس دوم هیچ موقعیتی درست نبوده است. با استفاده از این اطلاعات، یک الگوریتم «بررسی مدل» (Model Checking) می‌تواند پاسخ معما را به دست آورد.

قواعد استنتاج

• الگوریتم Model Checking کارآمد نیست، زیرا باید تمام مدل‌های ممکن را پیش از ارائهٔ پاسخ بررسی کند. (یادآوری: یک پرسش R زمانی درست است که در تمام مدل‌هایی که KB در آن‌ها درست است، R نیز درست باشد.)
  قواعد استنتاج به ما اجازه می‌دهند بدون بررسی تک‌تک مدل‌ها، از دانش موجود اطلاعات جدید به‌دست آوریم.
• قواعد استنتاج معمولاً با یک خط افقی نمایش داده می‌شوند که بخش بالایی آن مقدمه (premise) و بخش پایینی آن نتیجه (conclusion) است. مقدمه دانشی است که در اختیار داریم، و نتیجه دانشی است که بر اساس مقدمه می‌توان تولید کرد.

کمیت‌گذاری کلی (Universal Quantification)

کمیت‌گذاری ابزاری در منطق مرتبه اول است که به ما اجازه می‌دهد جمله‌هایی را بدون استفاده از نماد ثابت خاص بیان کنیم.

کمیت‌گذاری کلی با نماد ∀ نمایش داده می‌شود و معنای آن «برای همه» است.

برای مثال، جمله‌ی زیر:

∀x. BelongsTo(x, Gryffindor) → ¬BelongsTo(x, Hufflepuff)

بیان می‌کند که برای هر نماد x، اگر x متعلق به گریفیندور باشد، آنگاه متعلق به هافلپاف نیست.

توضیح ساده

این یعنی قانون کلی: هیچ فردی نمی‌تواند همزمان عضو گریفیندور و هافلپاف باشد.

کمیت‌گذاری وجودی (Existential Quantification)

کمیت‌گذاری وجودی مفهومی موازی با کمیت‌گذاری کلی است.

• در حالی که کمیت‌گذاری کلی (∀) جمله‌هایی را بیان می‌کند که برای همه‌ی x درست هستند،
• کمیت‌گذاری وجودی (∃) جمله‌هایی را بیان می‌کند که برای حداقل یک x درست باشند.

نماد

کمیت‌گذاری وجودی با نماد ∃ نمایش داده می‌شود.

ترکیب کمیت‌گذاری کلی و وجودی

کمیت‌گذاری کلی (∀) و وجودی (∃) می‌توانند در یک جمله با هم استفاده شوند.

هوش مصنوعی CS50 s1 مثال:

جمله‌ی زیر:

∀x.Person(x)→(∃y.House(y)∧BelongsTo(x,y))∀x. Person(x) → (∃y. House(y) ∧ BelongsTo(x, y))

این جمله بیان می‌کند: برای هر x، اگر x یک شخص باشد، آنگاه دست‌کم یک y وجود دارد که یک خانه است و آن شخص به آن خانه تعلق دارد.

توضیح ساده

به زبان ساده: هر شخصی به یک خانه تعلق دارد.

این ترکیب قدرت منطق مرتبه اول را نشان می‌دهد، چون می‌توانیم قوانین کلی (برای همه) و وجودی (برای دست‌کم یک مورد) را در یک جمله‌ی واحد بیان کنیم.

هوش مصنوعی CS50 s1 مثال: دانش‌آموزان و کتابخانه

فرض کنید می‌خواهیم بگوییم: «هر دانش‌آموزی دست‌کم یک کتاب در کتابخانه دارد.»

به زبان منطق مرتبه اول:

∀x.Student(x)→(∃y.Book(y)∧Has(x,y))

توضیح ساده

• ∀x برای همه‌ی افراد x
• اگرx  یک دانش‌آموز باشد،
• آنگاه دست‌کم یک y وجود دارد که هم کتاب است و هم آن دانش‌آموز آن را دارد.

نتیجه

این جمله یک قانون کلی بیان می‌کند: همه‌ی دانش‌آموزان حداقل یک کتاب دارند.