موضوع مقاله: عبارت هورن | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # عبارت هورن | مقدمه: عبارت یا بند هورن در منطق ریاضی و برنامه‌نویسی منطقی، یک فرمول منطقی دارای «فرم قاعده‌ای به‌خصوص» است، که این فرم به‌خصوص موجب ویژگی‌های مفیدی برای استفاده آن بندها در برنامه‌نویسی منطقی، مشخصات صوری، و نظریه مدل می‌شود. | ## بخش 1: عبارت هورن | واژه «بند هورن» از اسم یک منطق‌دان به نام آلفرد هورن گرفته شده‌است، که اولین بار در سال ۱۹۵۱ به اهمیت این بندها اشاره کرد. تعریف یک بند هورن یک بند است (یک فصل از لیترال‌ها است) که حداکثر یک لیترال آن مثبت (یعنی غیرنقیض) است. به صورت معکوس، یک فصل از لیترال‌ها که حداکثر یک لیترال منفی دارد یک «بند دوگان هورن» است. یک بند معین یا بند هورن اکید یک بند هورن است که دقیقاً یک لیترال مثبت دارد، به بند معینی که هیچ لیترال منفی ندارد بند واحد می‌گویند، و به بند واحدی که متغیری ندارد واقعیت گفته می‌شود؛ و به بند هورنی که لیترال مثبت ندارد بند هدف گفته می‌شود (توجه کنید که بند خالی که شامل هیچ لیترالی نیست هم‌بند هدف است). این بندها در اثبات قضیه خودکار هم مهم اند زیرا در رزلوشن مرتبه اول از آن‌ها استفاده می‌شود، زیرا حل‌مسئله (ناشی از رزلوشن) دو بند هورن خودش یک بند هورن است، و حل‌مسئله یک بند هدف و یک بند معین، یک بند هدف است. این ویژگی‌های بندهای هورن، منجر به کارایی بالاتر در اثبات یک قضیه می‌شود (که به صورت نقیض یک بند هدف نمایش می‌یابد). | ## بخش 2: عبارت هورن | مسئله یافتن انتساب مقدار درستی برای درست ساختن یک عطف از بندهای هورن گزاره‌ای، در واقع یک مسئله p-کامل است، که در زمان خطی قابل حل است، و گاهی HORNSAT نامیده می‌شود (اما مسئله صدق‌پذیری بولی بدون محدودیت یک مسئله NP-کامل است). برنامه‌نویسی منطقی بندهای هورن همچنین مبنای برنامه‌نویسی منطقی هستند، که در آن نوع برنامه‌نویسی نوشتن بندهای معین به صورت فرم پیامد منطقی یک موضوع معمول است: (p ∧ q ∧ … ∧ t) → u در واقع رزلوشن یک بند هدف با یک بند معین برای ایجاد یک بند هدف جدید مبنای قاعده استنتاج رزلوشن SLD است، که از آن برای پیاده‌سازی برنامه‌های منطقی در زبان برنامه‌نویسی پرولوگ استفاده می‌شود. اما برای تأکید بیشتر روی استفاده معکوس از بند، معمولاً در فرم معکوس نوشته می‌شود: u ← (p ∧ q ∧ … ∧ t) در زبان پرولوگ، عبارت بالا به این صورت نوشته می‌شود: u :- p, q, ..., t. در برنامه‌نویسی منطقی و دیتالاگ، محاسبه و ارزیابی پرسمان به وسیله نمایش نقیض مسئله‌ای که می‌خواهد حل شود، به صورت یک بند هدف انجام می‌شود. برای مثال، مسئله حل عطف سور وجودی برای لیترال‌های مثبت زیر: ∃X (p ∧ q ∧ … ∧ t) توسط نقیض مسئله (انکار اینکه یک جواب برای آن وجود دارد) نمایش می‌یابد، و سپس آن را به صورت فرم معادل منطقی از یک بند هدف نمایش می‌دهند: ∀X (false ← p ∧ q ∧ … ∧ t) که در پرولوگ به صورت زیر نوشته می‌شود: :- p, q, ..., t. حل مسئله تا زمان یافتن یک تناقض ادامه می‌یابد، که آن تناقض به صورت بند خالی (یا «false») نمایش می‌یابد. | ## بخش 3: عبارت هورن | راه‌حل مسئله همان «جایگزینی ترم‌ها» برای متغیرهای موجود در بند هدف است، که این موضوع از «اثبات آن تناقض» قابل استخراج است. در این روش، بندهای هدف مشابه پرسمان‌های عطفی در پایگاه‌داده‌های رابطه‌ای هستند، و منطق بند هورن از نظر قدرت محاسباتی با ماشین تورینگ جهانی معادل است. در واقع نمادگذاری پرولوگ ابهام دارد، و عبارت «بند هدف» گاهی به صورت مبهم استفاده می‌شود. متغیرهای موجود در بند هدف را هم به صورت سور عمومی و هم سور وجودی داده شده می‌توان خواند، و به دست آوردن «false» را می‌توان یا به صورت اشتقاق یک تناقض یا به صورت اشتقاق یک جواب موفق از مسئله‌ای که قصد حل آن را داریم، قابل تفسیر است. آقای ون آمدن و کوالسکی (۱۹۷۶) ویژگی‌های نظری مدل را برای بندهای هورن در زمینه برنامه‌نویسی منطقی وارسی کردند، و نشان دادند که هر مجموعه از بندهای معین D یک مدل حداقلی یکتا M دارد. این به معنی آن است که یک مسئله P که توسط عطف سور وجودی داده شده از لیترال‌های مثبت نمایش می‌یابد فقط و فقط وقتی توسط D پیامد منطقی دارد که P در M درست باشد. | ## جمع‌بندی | معناشناسی مدل حداقلی برای بندهای هورن مبنای معناشناسی مدل ثابت برای برنامه‌های منطقی است.