عبارت هورن

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

 تعریف 
یک بند هورن یک بند است (یک فصل از لیترال‌ها است) که حداکثر یک لیترال آن مثبت (یعنی غیرنقیض) است.

به صورت معکوس، یک فصل از لیترال‌ها که حداکثر یک لیترال منفی دارد یک «بند دوگان هورن» است.

یک بند معین  یا بند هورن اکید یک بند هورن است که دقیقاً یک لیترال مثبت دارد، به بند معینی که هیچ لیترال منفی ندارد بند واحد  می‌گویند، و به بند واحدی که متغیری ندارد واقعیت  گفته می‌شود؛ و به بند هورنی که لیترال مثبت ندارد بند هدف  گفته می‌شود (توجه کنید که بند خالی که شامل هیچ لیترالی نیست هم‌بند هدف است). این سه نوع بند هورن در مثال گزاره‌ای زیر نشان داده شده‌است:
فرم فصلیفرم پیامدیخواندن بصریبند معین
Definite clause¬p ∨ ¬q ∨ … ∨ ¬t ∨ u u ← p ∧ q ∧ … ∧ t assume that,if p and q and … and t all hold, then also u holdsواقعیت
Factuuassume thatu holdsبند هدف
Goal clause ¬p ∨ ¬q ∨ … ∨ ¬t false ← p ∧ q ∧ … ∧ t show thatp and q and … and t all holdLike in resolution theorem proving, intuitive meanings "show φ" and "assume ¬φ" are synonymous (indirect proof); they both correspond to the same formula, viz. ¬φ. This way, a mechanical proving tool needs to maintain only one set of formulas (assumptions), rather than two sets (assumptions and (sub)goals).
در حالت غیرگزاره‌ای، همه متغیرهاLike in resolution theorem proving, intuitive meanings "show φ" and "assume ¬φ" are synonymous (indirect proof); they both correspond to the same formula, viz. ¬φ. This way, a mechanical proving tool needs to maintain only one set of formulas (assumptions), rather than two sets (assumptions and (sub)goals). در بند به صورت ضمنی سور عمومی دارند، که بازه آن سور، کل بند است؛ بنابراین، مثال:

¬ human(X) ∨ mortal(X)

به معنی

∀X(¬ human(X) ∨ mortal(X))

است که به صورت منطقی معادل است با:

∀X (human(X) → mortal(X))

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

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

 برنامه‌نویسی منطقی 
بندهای هورن همچنین مبنای برنامه‌نویسی منطقی هستند، که در آن نوع برنامه‌نویسی نوشتن بندهای معین به صورت فرم پیامد منطقی یک موضوع معمول است:

(p ∧ q ∧ … ∧ t) → u
در واقع رزلوشن یک بند هدف با یک بند معین برای ایجاد یک بند هدف جدید مبنای قاعده استنتاج رزلوشن SLD است، که از آن برای پیاده‌سازی برنامه‌های منطقی در زبان برنامه‌نویسی پرولوگ استفاده می‌شود.

در برنامه‌نویسی منطقی یک بند معین به صورت یک «فرایند کاهش هدف» عمل می‌کند. برای مثال، بند هورن نوشته شده در بالا به صورت فرایند زیر عمل می‌کند:

to show u, show p and show q and … and show t.

اما برای تأکید بیشتر روی استفاده معکوس از بند، معمولاً در فرم معکوس نوشته می‌شود:

u ← (p ∧ q ∧ … ∧ t)

در زبان پرولوگ، عبارت بالا به این صورت نوشته می‌شود:

u :- p, q, ..., t.

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

∃X (p ∧ q ∧ … ∧ t)

توسط نقیض مسئله (انکار اینکه یک جواب برای آن وجود دارد) نمایش می‌یابد، و سپس آن را به صورت فرم معادل منطقی از یک بند هدف نمایش می‌دهند:

∀X (false ← p ∧ q ∧ … ∧ t)

که در پرولوگ به صورت زیر نوشته می‌شود:

:- p, q, ..., t.

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

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

آقای ون آمدن و کوالسکی (۱۹۷۶) ویژگی‌های نظری مدل را برای بندهای هورن در زمینه برنامه‌نویسی منطقی وارسی کردند، و نشان دادند که هر مجموعه از بندهای معین D یک مدل حداقلی یکتا M دارد. یک فرمول اتمی A فقط و فقط موقعی توسط D پیامد منطقی دارد که A در M درست باشد. این به معنی آن است که یک مسئله P که توسط عطف سور وجودی داده شده از لیترال‌های مثبت نمایش می‌یابد فقط و فقط وقتی توسط D پیامد منطقی دارد که P در M درست باشد. معناشناسی مدل حداقلی برای بندهای هورن مبنای معناشناسی مدل ثابت برای برنامه‌های منطقی است.

 یادداشت 

 پانویس 

 منابع 

رده:منطق در علوم کامپیوتر
رده:فرم‌های نرمال (منطق)