امروز جلسه اول LevelUp Math کوئرا برگزار شد و فکر کردم فرصت خوبیه که این چندروز، روی این موضوع تمرکز کنم تا بعدا که خواستم وارد مباحث الگوریتم و ساختمان داده بشم یه پایه اولیه داشته باشم. تو این پست به یه سری از مباحث پایه ای ریاضیات می‌پردازیم که درک اون به نوشتن کد های بهتر و به کار بردن الگوریتم های درست کمک میکنه.
می تونید از طریق این لینک گیتهاب به ریپوی تمرین ها و نکات بیشتر مراجعه کنید.
چرا به روش های استدلال کردن به عنوان برنامه نویس نیاز داریم؟ تفاوت کسی که با استدلال و منطق کار خودش رو انجام میده و تفاوت کسی که بدون استفاده از منطق خاصی برنامه اش رو می‌نویسه، چیه؟
تمام برنامه‌های کامپیوتری با منطق کار می‌کنن، پس اگه یادبگیریم که راه‌حل‌های منطقی ارائه بدیم، تبدیل این راه‌حل‌ها به کد برای ما خیلی راحت‌تر میشه.
به نظرتون بی‌منطق بودن به چه معناست؟ اهمیت اینکه یه نفر بدونه چطور یک گزاره رو اثبات منطقی کنه چیه ؟
وقتی یه نفر الگوریتم درست رو ارائه میده یعنی داره یه راه حل درست ارائه میده و میتونه راه حل خودش رو تحلیل کنه.
روش استدلال استقرایی : با استفاده از تکرار کردن یک کار، درستی یا نادرستی گزاره رو نتیجه می‌گیرن : مثلا یک اپ داریم که یک میلیون کاربر ازش استفاده کردن و خطایی رخ نداده پس نتیجه می‌گیریم که اپ درست کار میکنه. این موضوعی که درموردش صحبت کردیم، پایه استدلال در همه علوم هست .
و مدل بدتر اون هم این هست که هیچ روش علمی ای وجود نداشته باشه مثلا یه مشکلی توی کد وجود داره و روی یه مثالی خطا میده وقتی که این مشکل رو اطلاع می‌دیم ممکنه بپرسیم کجا مشکل داره؟ و خود این ایراد هست دیگه نمیشه پرسید کجای اون ایراد داره. یعنی سوال رو با سوال جواب دادن!
استدلال منطقی به صورت عمومی به چه معناست ؟
Logical reasoning is a type of problem-solving that involves working through a set of rules that govern a scenario. This set of rules or steps is referred to as an algorithm. Logical reasoning involves testing different sets of steps - or algorithms - to determine which sequence of rules leads to the correct solution.
استدلال استنتاجی: استدلال مدنظر ما به عنوان استدلال منطقی، استدلال استنتاجی هست. یعنی از روش های موجود در منطق استفاده می‌کنیم و گزاره ها رو نتیجه می‌گیریم.
مثال: همه برنامه نویسان کوئرا رو می‌شناسن، امین برنامه نویس هست، پس امین کوئرا رو می‌شناسه . به صورت خلاصه یعنی یه استدلال منطقی داریم که درسته و میخوایم از اون گزاره به درستی بقیه هم برسیم .
گزاره چیست؟ جمله ای خبری، که میتونیم ارزش درست یا نادرست بهش نسبت بدیم. و باید خبری باشه و همینطور به صورت کاملا شفاف، مشخص باشه که درست یا نادرست هست.
جمله های اول تا سوم گزاره هستن و بقیه جملات گزاره نیستن. اما دلیل؟
همه اعداد اول فرد هستن : جمله خبری هست / ارزش این جمله نادرست هست که کاری باهاش نداریم فعلا ولی اصل شفافیت و درست یا نادرست بودن رو رعایت کرده، پس گزاره هست.
هر عدد صحیح بزرگ‌تر از ۱ را می‌توان به‌صورت ضرب تعدادی عدد اول نوشت: به دلایل بالا، این هم گزاره هست.
برنامه‌ی کامپیوتری می‌توان نوشت که از ذهن باهوش‌ترین انسان‌ها هم قوی‌تر باشد: جمله خبری هست / درسته که ما دقیقا نمیدونیم منظور از برنامه و باهوش ترین چیه اما به هرحال در هر صورت ارزش اون یا درست هست یا نادرست پس میتونیم گزاره به حساب بیاریمش.
این گزاره غلط است : جمله خبری هست / اما دو تا ارزش درست و غلط رو داره. برای اینکه دقیق تر متوجه بشیم یعنی فرض کنید ارزش جمله این گزاره غلط هست، درست بشه یعنی اینو بپذیرید ولی حرف خودش میگه این جمله غلط هست پس غلط میشه و الان دو تا ارزش درست و نادرست رو داریم پس گزاره نیست.
سلام : گزاره نیست چون جمله خبری نیست.
شاید حق با تو باشه : گزاره نیست چون شفافیت لازم برای درست یا نادرست بودن رو نداره.
گزاره های ساده : ساده‌ترین شکل گزاره‌ها که دیگر نمی‌توانیم (نمی‌خواهیم) آن‌ها را به گزاره‌های کوچک‌تر تقسیم کنیم. به این گزاره‌ها اتم می‌گویند. گزاره های مستقل و ساده را گزاره های اتم میگوییم
ما به هر کدوم از این گزاره های ساده یک ارزش رو نسبت می‌دیم و با استفاده از اون ها، گزاره های مرکب رو ارزش گذاری می‌کنیم و با استفاده از رابط ها گزاره های مرکب را می‌سازیم.
رابط گزاره های ساده
نقیض : نقیض اینکه «علی پولدار است.» معادل «علی پولدار نیست.»
هر وقت یکی از گزاره ها، غلط بود اون یکی درست هست و برعکس.
نکته: گزاره باید تحت همه شرایط نقیض باشه و به صورت دقیق نقیض بشه .
و (And)
وقتی ارزش p یا q درست یا غلط باشه، چهار حالت درست میشه و ارزش گزارهای های p و q مشخص میشه. اگه همین چهارحالت رو بگیرن p , q پس ارزش گزاره های مرکب هم به صورت یکتا بدست میاد و همین چهار حالت کافیه که بدونیم چطور ارزشAnd اون ها رو بدست بیاریم.
یا (OR)
اگه حداقل یکی از اون ها درست باشه، نتیجه نهایی T میشه.
ناسازگاری با شهود: علی به سینما رفته یا به کلاس رفته این در فارسی وقتی درست هست که یکی درست باشه و اینجا هر دو تا با هم نمیتونه اتفاق بیافته اینجا از XOR استفاده میشه، در حالی که طبق جدول Or میتونن همزمان با هم وجود داشته باشن.
شرط (IF)
شهود ناسازگار: دو مورد اولی مشخص هستن، مثلا برای مورد دوم : اگر نمره ات بیست شه برات دوچرخه میخرم. که گزاره اول درست بوده اما گزاره دوم غلط پس نتیجه هم غلط شده. اما سطر سوم رو دقت کنید : اگر p غلط باشه q درست باشه،
p آنگاه q درست میشه، یعنی اگه فرض غلط باشه مهم نیست چه نتیجه ای داری میگیری. اون فرض غلط هست پس نتیجه درست میشه و اصطلاحا می‌گیم گزاره به انتفای مقدم درست هست یعنی هیچ وقت اون فرص درست نمیشه که بخوام درمورد نتبجه بگم. سطر چهارم هم مثل بالایی، وقتی اولی غلط باشه میتونیم نتیجه بگیریم که بعدی ها درست هستن.
اگر و تنها گر دوشرط (IFF)
زمانی درست هستن که هر دو هم ارزش باشن اگر هم ارزش باشن درسته و در غیر این صورت غلط میشه. دقیقا کار مساوی رو داره انجام میده.
گزاره ها رو میشه به چشم نماد و رشته در نظر گرفت و این ها رو به چشم رشته هایی نگاه کنید که مرکب های پیچیده رو میسازن و میشه بهشون ارزش های درست و نادرست داد و موارد پیچیده تر رو اثبات کرد، که با این شیوه میتونیم ختی گزاره ها رو به شکل گراف مدل کنیم که از فرض به حکم برسیم. این روش در هوش مصنوعی کاربرد زیادی داره.
بعضی اوقات، گزاره ها به تنهایی خودشون گزاره نیستن و گزاره نما هستن یعنی یکسری متغیر داره تا اون ها مقدارشون معلوم نباشه نمیشه ارزش گزاره رو مشخص کرد. مثلا n عددی اول هست .
به این گزاره ها، سورهای عمومی هم میگن.
سور عمومی
برای هر، برای همه: اگه به ازای تمام x ها، شرط برقرار باشه پس درست هست و اگه به ازای یکی هم برقرار نباشه پس درست نیست.این جمله گزاره هست.
مثال) همه‌ی اعداد اول، فرد هستند: چون مقدار x مشخص شده.
سور وجودی
عدد اولی وجود داره که فرد نباشه. اگه فقط یک حالت درست وجود داشته باشدر، برقرار هست.
سور صفر
وجود ندارد، یعنی نقیض سور وجودی هست.
سور وجود یکتا
وجود دارد به صورت یکتا : هم اون مقدار وجود داره هم دقیقا یکدونه از اون وجود داره. و کاربرد اون در وارون جمع و وارون ضرب هست.
تمرین : گزاره های زیر را اثبات کنید.
گزاره های معادل هم، خیلی پرکاربرد هستن و در مباحث or, and استفاده میشن و همچنین در طراحی مدارهای الکتریکی.
مثال کاربردی در برنامه‌نویسی:
الگوریتم Merge Sort
فرض کنید، میخوایم دو تا آرایه رو ادغام کنیم یه متغیر x در یک سمت آرایه اول و یک متغیر y در آرایه دوم دارم.برای اینکه بتونم برنامه ای بنویسم که گشتن داخل این آرایه ها رو ادامه بده از یه حلقه While استفاده می‌کنم که الگوریتم مربوط به Merge رو داخلش داره. اینجا نیاز به منطقی دارم که بتونه تا وقتی x به آخر آرایه n و y به آخر آرایه m نرسیده، الگوریتم داخل حلقه رو اجرا کنه. پس طبق مطالب بالا، باید نقیض حالتی که متوقف میشه رو بنویسیم.
استفاده از منطق ریاضی این کمک رو به ما میکنه که برای حل سوالات برنامه نویسی تا حد امکان از آزمون و خطا استفاده نکنیم. و اولین مرحله یعنی قبل اینکه دست به کد بشیم، سعی کنیم الگوریتم سوال رو روی کاغذ بیاریم و خوب درموردش فکر کنیم و مرحله بعدی کدشو بزنیم. دلیل این روش اینه که موقع کدنویسی برای تست کردن راه حل، ذهن ما درگیر سینتکس و قوائد اون زبان برنامه نویسی میشه و حل مسئله که موضوع اصلی هست، خوب انجام نمیشه.
پس تا الان باید متوجه اهمیت مفاهیم بالا شده باشید. ما نیاز داریم به فهیمدن منطق، چون نه تنها تو کامپیوتر وجود داره، بلکه کامپیوتر چیزی به جز منطق نیست.
خود فرایندی که یه کامپیوتر طی میکنه چیزی جز این منطق ها نیست. چون پردازش رو با پروسسور انجام میده و اون خودش یه تعداد زیادی ترانزیستور رو شامل میشه و ترانزیستور ها هم یه تعداد زیادی گیت And و ... هستن.
چند مثال برای تمرین نقیض :
هر گیت منطقی مثل یه عملگر منطقی، چند ورودی دریافت میکنه و یک خروجی میده.
گیت NOT
گیت AND
گیت OR
گیت XOR
اگه تعداد 1 ها فرد باشه، جواب نهایی 1 میشه . میشه گفت نقیض اگر و فقط اگر هست.
گیت NAND
همه گیت های دیگه رو با NAND میشه ساخت و با ساختن or میشه همه گیت های دیگه رو ساخت.
تو قسمت بعدی درمورد تبدیل گیت ها و تبدیل مبناها صحبت خواهیم کرد.
