. متن داده‌شده را خلاصه کن

متن: شجره‌نامه یک ساختار داده شناخته شده‌است که پدر و مادر، پدربزرگ و مادربزرگ، و اجداد یک فرد را تا آنجا که شناخته‌شده باشند نشان می‌دهد و به صورت بازگشتی تعریف می‌شود: به عنوان مثال، ویژگی «یک شجره‌نامه که بیش از g نسل را گسترش می‌دهد حداکثر ۲ g- ۱ نفر را نشان می‌دهد» را می‌توان با استقرای ساختاری ثابت کرد که به شرح زیر است: پس می‌توان فرض کرد، p ≤ ۲ g – ۱ و q ≤ ۲ h – ۱، که در آن g و h نشان‌دهنده تعداد نسل‌هایی است که زیردرخت‌های پدر و مادر به ترتیب گسترش می‌دهند، و p و q نشان‌دهنده تعداد افرادی است که آن‌ها نشان می‌دهند. به عنوان مثالی رسمی‌تر، ویژگی مربوط به لیست‌های زیر را در نظر بگیرید: در اینجا ++ نشان‌دهنده عمل الحاق لیست هاست وl و m لیست می‌باشند. به منظور اثبات این ویژگی، ما تعاریف طول (length) و عمل الحاق (++) را نیاز داریم. قرار دهید (h: t) که لیستی را که سر (عنصر اول) آن h و دم (فهرست عناصر باقی‌مانده) آن t است نشان می‌دهد، و اجازه دهید [] نشان دهنده‌ی لیست خالی باشد. تعاریف طول (length) و عمل الحاق (++) عبارتند از: گزاره (p (l ما برابراست با eq برای همه لیست‌های m درست است اگر l برابر l باشد. می‌خواهیم نشان می‌دهیم که (p (l برای همه لیست‌های l درست است. ما این کار را با استقرای ساختاری بر لیست‌ها ثابت خواهیم کرد. ابتدا ثابت می‌کنیم که ([]) p درست است. که در واقع برابر است با، eq درست است برای همه لیستهای m زمانی که l برابر لیست خالی [] است. eq را به صورت زیردر نظر بگیرید: بنابراین این بخش از قضیه ثابت شد. eq برای همه mها درست است، هنگامی‌که l برابر [] است، چرا که سمت چپ و سمت راست برابرند. سپس، هر لیست مخالف تهی i را در نظر بگیرید. از آنجا که l مخالف تهی است، پس یک سر، x، و یک لیست دم، xs، دارد. بنابراین ما می‌توانیم آن را به عنوان (x: xs) بیان کنیم. فرض استقرا این است که eq برای تمام مقادیر m زمانی است که l برابر xs است درست باشد: می‌خواهیم نشان دهیم که در صورت برقراری این شرایط eq برای تمام مقادیر m هنگامی‌که (l = i = (x: xs درست است. همانند قبل ادامه می‌دهیم: بنابراین، ما بوسیله‌ی استقرای ساختاری، به دست آوردیم که (p (l برای همه لیست‌های l درست است. همانگونه که استقرای ریاضی استاندارد معادل «اصل خوش ترتیبی» است، استقرای ساختاری نیز معادل یک «اصل …
خلاصه:
استقرای ساختاری روشی است که برای اثبات کردن قضایا از آن استفاده می‌شود که در منطق ریاضی (به عنوان مثال ، در اثبات قضیه لس) ، علوم کامپیوتر ، نظریه گراف ، و برخی دیگر از زمینه‌های ریاضی کاربرد دارد . این استقرا یک تعمیم از استقراء ریاضی روی اعداد طبیعی است ، و می‌تواند به‌طور قراردادی به استقرای noetherian تعمیم داده شود . روش بازگشت ساختاری یک روش بازگشتی است که ارتباط آن با استقرای ساختاری همانند ارتباط یک رابطه بازگشتی ساده با یک رابطه استقرای ریاضی ساده است . استقرای ساختاری برای اثبات برخی گزاره‌های (p (x ، که به ازای همهٔ xهای نوعی از ساختارهای تعریف شده به صورت بازگشتی مانند لیست‌ها یا درختان صحیح است ، استفاده می‌شود .