بخشی از مقاله

نظریه گراف

--------------------------------------------------------------------------------

نظریه گراف دانشی است که درباره موجوداتی به نام گراف بحث می‌کند. به صورت مرئی گراف «چیزی» است شامل تعدادی رأس که با یالهایی به هم وصل شده‌اند. تعریف دقیق‌تر نظریهٔ گراف به این صورت است که گراف مجموعه‌ای از رأس‌ها است که توسط خانواده‌ای از زوج‌های مرتب که همان یال‌ها هستند به هم ربط داده شده‌اند.

آغاز نظریهٔ گراف به سدهٔ هجدهم بر می‌گردد. اویلر ریاضیدان بزرگ این نظریه را برای حل مسئله پل‌های کونیگزبرگ ابداع کرد اما رشد و پویایی اصلی این بخش بسیار زیبا از این نظریه تنها مربوط به نیم سدهٔ اخیر و با رشد علم داده‌ورزی (انفورماتیک) بوده است.

مهم‌ترین کاربرد گراف مدل‌سازی از پدیده‌های گوناگون و بررسی بر روی آنهاست. با گراف می‌توان به راحتی یک نقشه بسیار بزرگ یا شبکه‌ای عظیم را در درون یک ماتریس ذخیره کرد و یا الگوریتمهای‌ مناسب را بر روی آن اعمال نمود.

یکی از قسمت‌های پركاربرد نظریهٔ گراف، گراف‌های مسطح است که به بررسی گراف‌هایی می‌پردازد كه می‌توان آن‌ها را به‌طوری روی صفحه كشید (با گذاشتن نقطه برای رأس‌ها و گذاشتن خم‌هایی كه اين نقاط را به هم وصل می‌كنند به جای یال‌ها) كه این یال‌ها یكدیگر را قطع نكنند.

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

گراف گویند. مفهوم گراف در سال 1736 توسط اویلر و با طرح راه‌حلی برای مساله پل konigsberg ارائه شد و به تدریج توسعه یافت.گراف‌ها امروزه کاربرد زیادی در علوم دارند. از گراف‌ها در شبکه‌ها،طراحی مدارهای الکتریکی, اصلاح هندسی خیابان‌ها برای حل مشکل ترافیک،و.... استفاده میشود.


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


تعداد راس های یک گراف را مرتبه و تعداد یال های آن را اندازه گراف می نامیم.
در شکل روبرو گرافی را با شش راس و هفت یال مشاهده می کنیم
________________________________________
انواع گراف‌ها
گراف‌ها دارای انواع متعددی هستند که به برخی از آنها اشاره می‌کنیم:
• گراف همبند
• گراف ناهمبند
• گراف کامل
• گراف اویلری
• گراف همیلتونی
• گراف درختی
• گراف مسطح
• گراف دو بخشی
• گراف چندبخشی
• گراف k-مکعب
• گراف چرخ
• گراف ستاره‌ای
• گراف بازه‌ای
• گراف اشتراکی
• گراف منظم
• گراف جهت‌دار


گراف کامل

در نظریه گراف ،یک گراف کامل ،گرافی است که هر بین هر دو راس آن دقیقا یک یال وجود داشته باشد.

یک گراف کامل از مرتبه n،دارای n راس و یال است و آن را با نشان می‌دهند.
یک گراف کامل یک گراف منتظم از درجه n-1 است.

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


نظریه


اندازه در ریاضیات، به تابعی گفته می‌شود، که یک عدد یا مقدار را (به عنوان مثال اندازه، حجم یا احتمال) به هر زیرمجموعه از یک مجموعه خاص، نسبت می‌دهد. این نظریه به منظور، محاسبه انتگرالها بر روی مجموعه‌ها به جای برروی فاصله‌ها (یا همان بازه‌ها) که در معمول انجام می‌پذیرد، گسترش پیدا کرد و از این رو در آنالیز ریاضی و در نظریه احتمالات، بسیار دارای اهمیت می‌باشد.

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

برطبق تعریف، اندازه μ تابعی است (یا به عبارتی نگاشتی است)، که برروی جبر سیگمای Σ بر مجموعه X، تعریف می‌شود و مقادیر بین ، می‌پذیرد و دارای خصوصیت‌های زیر است:


در اینجا مجموعه تهی و تعداد شمارایی از مجموعه‌هایی در Σ هستند، که اشتراک هرکدام از آنها با دیگری تهی است (مجموعه‌ها مجزا هستند). در این حالت به (X,Σ,μ) فضای اندازه‌ای و به اعضای Σ، مجموعه‌های اندازه‌پذیر گفته می‌شود.
دیدکلی
چرا اندازه گیری می‌کنیم؟
قوانین و نظریات فیزیک بصورت معادلات ریاضی بیان می‌شوند. حال ما از کجا بدانیم که هر معادله خاص ، رفتار چیزی را بیان می‌کند؟ باید این قاعده امتحان شود و به مرحله آزمون گذاشته شود. بنابراین ، اندازه گیری مهارتی است که میان نظریه علمی و دنیای واقعی رابطه ایجاد می‌کند. این رابطه دو طرفه می‌باشد. هر رویداد اندازه گیری شده‌ای که قبلا پیشگویی نشده باشد، باید نظریه جدید آنرا توجیه کند.

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

دقت در اندازه گیری
در اندازه گیریها جواب کامل نداریم، هر کسی که نتیجه اندازه گیری خود را گزارش می‌کند، همواره بهترین تخمین خود را از مقدار اصلی ، همراه با خطای اندازه گیری آن ، ارائه می‌دهد. یعنی اگر طول جسمی بصورت 183±5mm نوشته شود،

منظور نویسنده این است که مقدار واقعی طول بین 178 و 188mm قرار دارد. صحت اندازه گیری از روی تطابق آن با واقعیت نتیجه می‌شود. خطای زیاد بیانگر عدم اعتماد آزمایشگر بر اندازه گیری است. اندازه گیری دقیق ، اندازه گیریی است که خطای آن ، در مقایسه با مقدار اندازه گیری شده بسیار کوچک باشد.

در مثال اخیر خطای نسبی اندازه گیری برابر است با: %100=± %2. 74 × (±5/183). دقت اندازه گیری به مهارت آزمایشگر در تخمین زنی ، مکانیزم عمل اندازه گیری ، حد تفکیک وسیله اندازه گیری ، حد تفکیک چشم و غیره بستگی دارد. البته درستی اندازه گیری به طبیعت جسمی که اندازه گیری می‌شود نیز وابسته است. بنابراین ، صحت تمامی اندازه گیریها ، به دلیل محدودیت در دقت (تکرار پذیری آزمایش) و خطای ناشی از طبیعت وسیله اندازه گیری و جسمی که اندازه گیری می‌شود، محدود است.


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

آخرین رقم با معنی در اندازه گیری همیشه تخمینی است. مثلا اگر در اثر اندازه گیری طول اتاقی 720cm باشد، مفهوم این است که اندازه گیری با سه رقم معنی دار انجام شده است که رقم آخر آن صفر می‌باشد که ممکن است درست یا غلط باشد.

صفرهای موجود در عدد گزارش شده ممکن است با معنی باشند یا محل ممیز را نشان دهند. مثلا طول 802mm که یک عدد دو رقمی است، بر حسب متر برابر 0.0082 است، چون نتیجه تغییر نکرده پس این طول بر حسب متر هم یک عدد دو رقمی است. بنابراین قاعده کلی این است که: صفرهای سمت چپ هرگز معنی دار نیستند.

صفرهای پایانی نیز ممکن است معنی دار باشند یا نباشند. اگر طول زمینی را 230m اندازه بگیرید، در این اندازه گیری عدد گزارش شده دارای 4 رقم با معنی است، البته بدون ممیز تشخیص معنی دارابودن یا نبودن رقم آخر با قطعیت مشخص نمی‌شود ، مگر اینکه از نحوه اندازه گیری اطلاعی داشته باشیم.

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

مثلا خطای اندازه گیری با دقت 0.1 به اندازه گیری با دقت 0.001 سرایت می‌کند. البته در اندازه گیریها ، پردازش داده‌های اندازه گیری ، روش گرد کردن و محاسبه خطا (نسبی و مطلق) وجود دارد که میزان اعتبار و دقت اندازه گیری را بیان می‌نماید. معیار اصلی در گزارش اندازه گیری و مقادیر حاصل از آنها ، کاربرد دقیق تعداد ارقام با معنی است.

نمادگذاری علمی
اگر تمامی فواصل در متریک SI نوشته شود، هنگام نوشتن فاصله تا نزدیکترین ستاره (عدد بزرگ) یا هنگام نوشتن قطر هسته اتم (عدد کوچک) کار مشکل خواهد بود. در مورد ستاره 15 صفر در پایان و در هسته 15 صفر در ابتدای عدد وجود دارد. تنها تکلیف این صفرها مشخص نمودن محل ممیز می‌باشد. بهترین راه برای حل مشکل استفاده از نماد گذاری علمی است

. در این روش در هر عدد ممیز را بعد از اولین رقم غیر صفر نوشته و سپس آنرا در توانی از 10 ضرب می‌کنند تا محل ممیز را نشان دهند. مثلا عدد 142000 در نماد گذاری علمی بصورت زیر در می‌آید:

105×100000 = 1.42 × 142000 = 1.42

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

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

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

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


نظریه بازی در ریاضی
یک برداشت پیچیده از یک رابطه ساده
مسئله آشنایی است: n شئی متمایز داریم , می خواهیم r تا از آنها را کنار هم قرار دهیم . یعنی p(n,r) یک ترتیب.
P(n,r)=n!/(n-r)!


فرض کنید 5 شئی متمایز داریم و r تای آنها را می خواهیم کنار هم قرار بدهیم ( ترتیب مهم است) داریم:
P(5,3)=5*4*3
تا اینجا نگرش تعداد انتخابهای ممکن بر اساس فاکتورهای محتمل از فضای قابل انتخاب برای هر سهم از r می باشد. در اینجا اگر بخواهیم مسئله فوق را به یک فضای تصمیم سازی گسترش بدهیم با برداشت زیر مواجه خواهیم شد که از کل گزینه های ممکن ( 5!) تعداد حالاتی که توان تامین مطلوبیت ما را دارا هستند در 5*4*3 گزینه خلاصه می شوند. در اینجا یک نکته وجود دارد :
آیا حالتی وجود دارد که در انتخابها نا دیده گرفته شده باشد. به عبارتی در 120 حالت ممکن که 60 حالت آن تامین کننده مطلوبیت است , 60 حالت دیگر در نظر گرفته نشده باشد؟


قاعدتا بنا بر اصول تصمیم سازیهای استراتژیک , وقوع پیشامد فوق (ینی توجه به 60 گزینه از بین 120 گزینه ممکن) یک فاجعه است و درایت استراتژیست را به چالش می طلبد. پس 60 انتخاب مستتر دیگر کجاست؟
می خواهم مسئله فوق را با نگرشی دیگر مورد بررسی قرار بدهم. به تعدا حالتهای ممکن توجه کنید:
1 2 3 4 5

زمانیکه شما گزینه منتخب خود را تشکیل داده اید و 3 عنصر ( در بلوک خاکستری) از 5 عنصر را بکار گرفته اید, نحوه چیدمان دو عنصر دیگر برای شما زیاد اهمیتی ندارد. زیرا انتخاب نشده اند و نحوه قرار گیری آنها در بلوکهای مجازی ( بلوکهای سفید) مهم نیستند. اما واقعیت این است که اگر فقط بر اساس منطق صفر و یک آن را تحلیل نکنیم , برای هر انتخاب در این مثال دو حالت تبهگن داریم که از نظر تامین مطلوبیت دارای ارزش یکسانی هستند.

همچون چیدمان فرضی زیر :
s o f d a
o s f d a

اما اگر در یک مسئله تصمیم سازی و بر اساس منطق فازی این دو حالت تبهگن را تحلیل کنیم , شاید به پتانسیلهایی بر خورد کنیم که جدول استراتژیک را دستخوش دگرگونی نمایند یا برای تامین مطلوبیت هزینه های متفاوتی را ایجاد کنند , شاید سرمایه گذاریی پنهان , یا امتیازی ویژه بوده و یا تمامی این حالات تبهگن تکرار های میسری از یک انتخاب در دوره های مختلف زمانی باشند .

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


اشغال در رد ریاضی

خلاصه

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


1- مقدمه

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

. منطق محاسباتی به صورت کلی به منطق از دید محاسباتی آن مینگرد. این که در یک دستگاه منطقی انجام یک محاسبه (به طور مثال چک کردن درستی یک گزاره) امکان پذیر هست یا نه و اگر امکان پذیر است این کار چه هزینه ای دارد. از آنجا که حقایق علمی ما با منطق پیوند عمیقی دارند، برای بررسی این حقایق استفاده از زبان منطقی، یکی از بهترین راه های ممکن است.

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

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

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

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


2. پایه‌ی منطق محاسباتی

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

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

چرچ در 1936 ثابت کرد که منطق مرتبه اول برای زبانی که فقط یک نماد رابطه‌ای دو موضعی داشته باشد تصمیم ناپذیر است. بنا بر قضیه چرچ روشی متناهی برای پاسخ به این سوال که آیا جمله A در منطق مرتبه اول معتبر است، به صورت "آری" یا "نه" نداریم، اما نیمه ای از پاسخ را میتوان مهیا کرد. به عبارت بهتر روشی متناهی وجود دارد که اگر A معتبر باشد، پاسخ روش "آری" است.

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


تحقیقات در بخش پایه‌ی منطق محاسباتی به طور گسترده‌ای بر دیگر بخشهای این علم تاثیر دارند. این تحقیقات عموما به دو بخش تقسیم میشوند:

تحقیقات در زمینه‌های روشهای استنتاج از قبیل Resolution و ...
تحقیقات در زمینه‌ی پیدا کردن پایه3 های مناسب ریاضی برای انجام به صرفه‌ی (از نظر زمانی و حافظه) محاسبات مربوط به منطق محاسباتی.

2-1 پایه‌های منطق محاسباتی

روش کلی برای فهمیدن درستی یک جمله این است که از فرضها شروع کرده و در هر مرحله یک جمله درست جدید را با توجه به جملات قبلی و استفاده از قواعد استنتاج تولید کنیم. (یعنی جملات درست را لیست میکنیم.) این کار ادامه پیدا میکند تا وقتی که به جمله مورد سوال یا نقیض آن برسیم.

قسمت دیگری که مورد توجه است، یکی سازی4 است. به طور مثال دو جمله ∃x:f(x) و ∃y:f(y) را در نظر بگیرید. واضح است که درستی این دو جمله یکسان است. به طور کلی هر جمله را به طریقه های ظاهرا متفاوت بسیار زیادی میتوان نوشت که همگی یک معنای واحد داشته باشند.

(در همین مثال به جای x از تمام متغیرها میتوان استفاده کرد. به صورت معمولی لااقل 0N متغیر داریم.) بدین منظور تحقیقات زیادی بر روی روشهای کارا برای یکی سازی جملات منطقی انجام شده است.


برای تولید جملات جدید با توجه به قواعد استنتاج راههای زیادی پیشنهاد شده اند. یکی از محبوبترین راههای پیشنهاد شده به Resolution موسوم است. این روش برای منطق مرتبه اول کمی پیچیدگی دارد اما با بررسی آن برای منطق گزاره ها کلیت آن آشکار میشود.


Resolution Propositional

در این روش تمام جمله ها به صورت clausal form هستند. برای تبدیل یک جمله به این فرم ابتدا جمله را به صورت نرمال عطفی CNF تبدیل میکنیم.

¬(g ∧ ( r → f)) ──CNFà (¬g ∨ r) ∧ (¬g ∧ ¬f)

و سپس نتیجه را به تعدادی مجموعه تبدیل میکنیم، مجموعه ای از مجموعه ها که هر عضو آن اعضای یکی از پرانتزهاست:

(¬g ∨ r) ∧ (¬g ∧ ¬f) ──Clausal Formà {¬g, r}, {¬g, ¬f}


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

میدانیم که

(p ∨ q) ∧ (¬p ∨ r) ⇒ (q ∨ r)


میتوان نشان داد که استفاده از این رابطه به عنوان تنها قاعده استنتاج برای استنتاج کافی است. این رابطه در clausal form به این شکل تبدیل میشود:


{p, q}

{¬p, r}

————

{q, r}


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


{¬p, q}

{p}

————

{q}

(این معادل با قاعده Modus Ponens است.)


{p}

{¬p}

————

{}

(تناقض!)


2-2 پایه‌ی ریاضی

دسته دیگری از کارهایی که به عنوان بخشهای پایه منطق محاسباتی شناخته میشوند، کار بر روی پایه های منطقی ریاضیات است. اگرچه دستگاه های کلاسیک شناخته شده ای برای توصیف ریاضی در بوسیله منطق وجود دارند اما کارهایی برای پیدا کردن دستگاه‌هایی که برای استنتاج خودکار در ریاضی عملکرد بهتری داشته باشند در حال انجام است. به عنوان یک مثال میتوانید به [Beli01] مراجعه کنید.


3 کاربردهای منطق محاسباتی

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

Database Systems
با استفاده از سیستمهای مبتنی بر منطق محاسباتی میتوان Database ها را از محل ذخیره‌ی اطلاعات خام به پایگاههای هوشمند داده‌ها تبدیل نمود، به این ترتیب شاهد منابع هوشمندی از اطلاعات خواهیم بود که استفاده از آنها به مراتب ساده‌تر از موارد مشابه فعلی است.

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

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

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

Hardware Engineering
امروزه در طراحی سخت‌افزار هم به مانند طراحی نرم‌افزار پیشرفتهای عمده‌ای به وجود آمده است، قانون مور بیان میکند که تعداد ترانزیستورهای یک تراشه در هر سال دو برابر خواهد شد (از نظر تکنولوژی ساخت).

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

Automated Theorem Proving
از منطق محاسباتی میتوان به صورت گسترده‌ای جهت اثبات خودکار قضایای ریاضی استفتده کرد.


3-1 STRIPS

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

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

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

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

STRIPS عضو یک رده از حل‌کننده‌های مسایل6 است که در فضای مدلهای جهان7 برای یافتن مدلی که در آن یک هدف داده شده یافت شود، جستجو میکنند. برای هر مدل جهان فرض میکنیم یک مجموعه از عملگرهای قابل اعمال به جهان وجود دارند. هر عملگر مدل جهان را عوض میکند، به این ترتیب با استفاده از عملگرهای مختلف میتوانیم از یک مدل به مدلهای مختلفی برویم. وظیفه‌ی حل‌کننده مساله این است که دنباله‌ای از عملگرها را پیدا کند که توسط آنها بتوان از یک مدل ابتدایی به مدلی انتهایی رسید که هدف داده شده را ارضا کند.

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

اما در مورد یک ربات مدل ما از جهان شامل حجم بزرگی از اطلاعات مثل مکان ربات، مکان و خصوصیات اشیا، فضاهای باز و دیوارها و ... میباشد. بدین ترتیب یکی از بزرگترین مسایل دراین مورد نحوه نگه داری مدل جهان است. در STRIPS مدل جهان در یک مجموعه از فرمولهای خوش شکل ریخت(wff)8 در زبان منطق مرتبه اول، نگه داری میشود.

عملگر9ها عناصر اصلی برای پیدا کردن جواب هستند. هر عملگر متناظر با یک روال کاری10 است. فرق این دو این است که عملگرها هنگام برنامه ریزی استفاده میشوند ولی روالهای کاری وقتی استفاده میشوند که ربات میخواهد جواب پیدا شده را به صورت فیزیکی انجام دهد. (یعنی یک عملگر در جهان منطقی معادل با یک روال کلری در جهان واقعی است.)

سوال بعدی این است که یک عملگر مدل جهان را چگونه تغییر میدهد؟ در STRIPS این کار از طریق یک لیست اضافه11 و یک لیست حذف 12 انجام میشود. همچنین هر عملگر تعدادی شرط مقدماتی 13 برای انجام شدن دارد.

مثلا عملگر push(k,m,n) را برای هل دادن شی k از مکان m به n به صورت زیر تعریف میشود:

push(k, m, n)

precondition:

ATR14(m)

At(k, m)


delete list:

ATR(m)

AT(k, m)


add list:

ATR(n)

AT(k, n)


پس برای بدست آوردن جهان جدید از جهان قبلی تحت تاثیر یک عملگر تنها کافی است که ابتدا با چک کردن شرطهای مقدماتی بفهمیم که آیا عملگر قابل اعمال به جهان هست یا نه؟ اگر بود، جملات لیست حذف را از جهان حذف کرده و جملات مربوط به لیست اضافه را به جهان اضافه کنیم.

مثال

مثال زیر را در نظر بگیرید:


فرض کنید که این شکل نقشه‌ی یک ساختمان است که روبات در آن قرار دارد و همچنین تعداد جعبه و ... در این ساختمان است.

 

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

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

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

. ساده‌ترین راه برای این کار انجام یک جستجوی اول عمق15 بر روی گراف با شروع از راس آغازین است، جستجو در گراف تا وقتی ادامه پیدا میکند که یک راس پیدا شود که هدف مورد نظر را ارضا کند. اما این روش نمیتواند به عنوان یک روش کاربردی مورد استفاده قرار گیرد، چون حتی در ساده‌ترین مسایل اندازه‌ی گراف به قدری بزرگ است که نمیتوان امیدوار بود در زمان معقولی به جواب رسید. پس به طریقی باید بین راههایی که برای پیمایش داریم اولویت بندی کنیم. این اولویت بندی معمولا به کمک یک تابع هیوریستیک16 انجام میشود. این تابع به هر راس گراف عددی نسبت میدهد

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

با تمام این اوصاف به نظر میرسد که انتخاب هوشمندانه یک تابع هیوریستیک مساله را کاملا حل میکند اما قضیه‌ای به نام no-fee-lunch وجود دارد که میگوید هیچ شیوه‌ای برای جستجو در یک گراف وجود ندارد که در تمام موارد بهتر از جستجوی اول عمق (به نمایندگی از یک جستجوی کلی و بدون هوش) کار کند. این مطلب در شکل زیر نشان داده شده است:


شکل به نقل از ویکی‌پدیا17

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