فرم نرمال جبری

در جبر بولی، فرم نرمال جبری ()، فرم نرمال ژگالکین () و بسط رید-مولر () ابزارهای نوشتن فرمولهای منطقی در یکی از ۳ فرم زیر هستند:
کل فرمول به صورت ملطق درست یا غلط است
۰
۱
یک یا چند متغیر با AND به صورت یک ترم درآمده باشند. یک یا چند ترم با XOR به صورت یک فرم نرمال جبری درآمده باشند. استفاده از نقیض مجاز نمی‌باشد.
a ⊕ b ⊕ ab ⊕ abc
متشکل از علامت‌های استاندارد منطق گزاره‌ها
فرم قبلی با ارزش درستی مطلق
1 ⊕ a ⊕ b ⊕ ab ⊕ abc
فرمولهای نوشته شده به صورت فرم نرمال جبری به نام فرم نرمال ژگالکین و قطب مثبت بسط رید-مولر هم شناخته می‌شوند.
استفاده‌های معمول
فرم نرمال جبری یک فرم نرمال متعارف () است.
فرم نرمال در فرم نرم جبری بدین معناست که دو فرمول معادل به یک فرم نرمال جبری تبدیل می‌شوند، به راحتی نشان داده می‌شود که آیا دو فرمول برای اثبات خودکار قضیه یکسان هستند یا خیر. برخلاف دیگر فرمهای نرمال، فرم نرمال جبری می‌تواند نمایانگر لیست ساده‌ای از فهرست نام متغیرها باشد. همچنین فرم نرمال اشتراکی و فرم نرمال فصلی نیاز دارند تا اینکه متغیر نفی شده است یا خیر را ذخیره کنند. از آنجایی که فرم نرمال منفی از رابطه هم ارزی به عنوان برابری استفاده نمی‌کند، لذا a ∨ a و 1 به عبارت یکسانی کاهش پیدا نمی‌کنند، حتی اگر فکر کنیم معادل هستند.
قرار دادن فرمول در فرم نرمال جبری حتی باعث شناسایی راحت‌تر توابع خطی (که به عنوان مثال در ثبات تغییر بازخورد خطی () استفاده می‌شوند) می‌شود، همانند تابع خطی که جمع لیترال‌های تک است. همچنین خواص بازخورد غیرخطی انتقال ثبات‌ها می‌تواند از خواص اصلی تابع بازخورد در فرم نرمال جبری استنباط شود.
انجام عملیات در فرم نرمال جبری
راه‌های ساده و مستقیمی برای انجام عملیات بولی استاندارد بر روی ورودی‌های فرم نرمال جبری به منظور رسیدن به نتایج فرم نرمال جبری وجود دارد.
XOR (یای انحصاری) به صورت مستقیم اعمال می‌شود:
\begin{array{rl
- (1 \oplus x) \oplus (1 \oplus x \oplus y) \\
- 1 \oplus x \oplus 1 \oplus x \oplus y \\
- 1 \oplus 1 \oplus x \oplus x \oplus y \\
- y \\
\end{array
NOT (نقیض) به xOR تبدیل می‌شود:
\begin{array{rl
- \neg(1 \oplus x \oplus y) \\
- 1 \oplus (1 \oplus x \oplus y) \\
- 1 \oplus 1 \oplus x \oplus y \\
- x \oplus y \\
\end{array
AND (عطف منطقی) از قانون توزیع‌پذیری تبعیت می‌کند:
\begin{array{rl
- (1 \oplus x)(1 \oplus x \oplus y) \\
- 1(1 \oplus x \oplus y) \oplus x(1 \oplus x \oplus y) \\
- (1 \oplus x \oplus y) \oplus (x \oplus x \oplus xy) \\
- 1 \oplus x \oplus x \oplus x \oplus y \oplus xy \\
- 1 \oplus x \oplus y \oplus xy \\
\end{array
OR (یای منطقی) از (هرگاه هر دو عملوند ترم‌های مثبت داشته باشند) یا (در بقیه موارد) استفاده می‌کند:
\begin{array{rl
- (1 \oplus x)+(1 \oplus x \oplus y) \\
- 1 \oplus (1 \oplus 1 \oplus x)(1 \oplus 1 \oplus x \oplus y) \\
- 1 \oplus x(x \oplus y) \\
- 1 \oplus x \oplus xy \\
\end{array
تبدیل به فرم نرمال جبری
هر متغیر در فرمول به شخصه به صورت فرم نرمال جبری است، بنابراین تنها لازم است عملیات بولی همان‌طور که در بالا توضیح داده شده است اعمال شوند تا کل فرمول به صورت فرم نرمال جبری درآید. به عنون مثال:
\begin{array{rl
- x + (y \cdot \neg z) \\
- x+(y(1 \oplus z)) \\
- x+(y \oplus yz) \\
- x \oplus (y \oplus yz) \oplus x(y \oplus yz) \\
- x \oplus y \oplus xy \oplus yz \oplus xyz \\
\end{array
تعریف مشابه
فرم نرمال جبری گاهی به روش مشابهی توصیف می‌شود:
\begin{array{rl
f(x_1, x_2, \ldots, x_n) = - a_0 \oplus \\
- a_1x_1 \oplus a_2x_2 \oplus \cdots \oplus a_nx_n \oplus \\
- a_{1,2x_1x_2 \oplus \cdots \oplus a_{n-1,nx_{n-1x_n \oplus \\
- \cdots \oplus \\
- a_{1,2,\ldots,nx_1x_2\ldots x_n \\
\end{array
به طوریکه به طور کامل را توصیف می‌کنند.
به دست آوردن فرم نرمال جبری توابع بولی چند آرگومانه به صورت بازگشتی
تنها چهار تابع با یک آرگومان موجود است:
\begin{array{rl
- f(x)=0 \\
- f(x)=1 \\
- f(x)=x \\
- f(x)=1 \oplus x \\
\end{array
برای نشان دادن یک تابع با آرگومان‌های متعدد می‌توان از برابری زیر استفاده کرد:
\begin{array{rl
* - g(x_2,\ldots,x_n) = f(0,x_2,\ldots,x_n) \\
** - h(x_2,\ldots,x_n) = f(0,x_2,\ldots,x_n) \oplus f(1,x_2,\ldots,x_n) \\
\end{array
در واقع،
اگر آنگاه و در نتیجه
اگر آنگاه و در نتیجه
از آنجایی که و تعداد آرگومانهای کمتری نسبت به دارند، به این نتیجه می‌رسیم که با تکرار بازگشتی این پروسه در انتها به توابعی با یک آرگومان می‌رسیم. به عنوان مثال فرم نرمال جبری را بدست می‌آوریم:
با توجه به رابطه بالا داریم
از آنجایی که و
نتیجه می‌گیریم
و در انتها به فرم نرمال جبری می‌رسیم.
مطالب مرتبط
تابع بولی
گراف منطقی
چندجمله‌ای‌های ژگالکین
فرم نرمال نفی
فرم نرمال اشتراکی
فرم نرمال فصلی