فرم نرمال فصلی

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

در منطق بولی، یک فرم نرمال فصلی DNF یک استاندارد (یا نرمال شده) از یک فرمول منطقی است که یک جداکننده عبارات عطفی است. از سوی دیگر به صورت and وor‌هایی است که ان را به عنوان Sum of product می‌شناسید. همچنین یک فرم نرمال برای اثبات خودکار قضایا مفید است. یک فرمول منطقی درفرم DNF در نظر گرفته شده است اگر و تنها اگر به صورت یک فصل یاچند اتصال از یک یا چند عملگر باشد. اگر هر یک از متغیرهای dnf دقیقا یک بار در هر عبارت باشند، فرمول DNF به طور کامل درفرم نرمال فصلی است. مانند فرم نرمال CNF، تنها عملگرهای گزاره‌ای در not , and , or , DNF هستند. عملگر not تنها می‌تواندبه عنوان بخشی از عملگر استفاده شود به این معنی که فقط می‌تواند قبل از یک متغیر گزاره‌ای بیاید. برای مثال همه فرمول‌های زیر در فرم dnf است:

A \and B

A\!

(A \and B) \or C

(A \and \neg B \and \neg C) \or (\neg D \and E \and F)

بنابراین فرمول‌های زیر در فرم dnf نیستند

\neg(A \or B) — NOT is the outermost operator

A \or (B \and (C \or D)) — an OR is nested within an AND

تبدیل یک فرمول به DNF شامل استفاده از معادله‌های منطقی مانند حذف دو منفی، قوانین دمورگان و قانون توزیع است. تمام فرمول‌های منطقی را می‌توان به شکل نرمال فصلی تبدیل کرد. با این حال در برخی موارد تبدیل به dnf می‌تواند به انفجار نمایی از فرمول منجر شود. به عنوان مثال فرمول منطقی زیر ۲ به توان n جمله دارد

(X_1 \or Y_1) \and (X_2 \or Y_2) \and \dots \and (X_n \or Y_n)

هرتابع بولی خاص را می‌توان بایک وتنها یک فرمال نرمال کامل فصلی، یکی از دوشکل متعارف، نشان داد. در زیر یک گرامر از فرم نرمال dnf وجود دارد

  1. disjunctconjunct
  2. disjunctdisjunctconjunct
  3. conjunctliteral
  4. conjunct → (conjunctliteral)
  5. literalvariable
  6. literal → ¬variable

که در ان یک متغیر هر متغیری می‌تواند باشد

جستارهای وابسته[ویرایش]

منابع[ویرایش]

  • ویکی‌پدیای انگلیسی

پیوندهای بیرونی[ویرایش]