صورت بهنجار جبری

در جبر بولی، صورت بهنجار جبری یا فرم نرمال جبری (انگلیسی: Algebraic Normal Form)، فرم نرمال ژگالکین (انگلیسی: Zhegalkin Normal Form) و بسط رید-مولر (انگلیسی: Reed–Muller Expansion) ابزارهای نوشتن فرمولهای منطقی در یکی از ۳ فرم زیر هستند:

کل فرمول به صورت مطلق درست یا غلط است
۰

۱
یک یا چند متغیر با AND به صورت یک ترم درآمده باشند. یک یا چند ترم با XOR به صورت یک صورت بهنجار جبری درآمده باشند. استفاده از نقیض مجاز نمی‌باشد.
a ⊕ b ⊕ ab ⊕ abc
متشکل از علامت‌های استاندارد منطق گزاره‌ها
$a\veebar b\veebar \left(a\wedge b\right)\veebar \left(a\wedge b\wedge c\right)$
فرم قبلی با ارزش درستی مطلق
1 ⊕ a ⊕ b ⊕ ab ⊕ abc

فرمولهای نوشته شده به صورت صورت بهنجار جبری به نام صورت بهنجار ژگالکین و قطب مثبت بسط رید-مولر هم شناخته می‌شوند.

استفاده‌های معمول

صورت بهنجار جبری یک صورت بهنجار متعارف (انگلیسی: Canonical Normal Form) است. صورت بهنجار در فرم نرم جبری بدین معناست که دو فرمول معادل به یک صورت بهنجار جبری تبدیل می‌شوند، به راحتی نشان داده می‌شود که آیا دو فرمول برای اثبات خودکار قضیه یکسان هستند یا خیر. برخلاف دیگر فرمهای نرمال، صورت بهنجار جبری می‌تواند نمایانگر لیست ساده‌ای از فهرست نام متغیرها باشد. همچنین صورت بهنجار اشتراکی و صورت بهنجار فصلی نیاز دارند تا اینکه متغیر نفی شده‌است یا خیر را ذخیره کنند. از آنجایی که صورت بهنجار منفی از رابطه هم‌ارزی به عنوان برابری استفاده نمی‌کند، لذا a ∨ ¬a و ۱ به عبارت یکسانی کاهش پیدا نمی‌کنند، حتی اگر فکر کنیم معادل هستند.

قرار دادن فرمول در صورت بهنجار جبری حتی باعث شناسایی راحت‌تر توابع خطی (که به عنوان مثال در ثبات تغییر بازخورد خطی (انگلیسی: Linear Feedback Shift Registers) استفاده می‌شوند) می‌شود، همانند تابع خطی که جمع لیترال‌های تک است. همچنین خواص بازخورد غیرخطی انتقال ثبات‌ها می‌تواند از خواص اصلی تابع بازخورد در صورت بهنجار جبری استنباط شود.

انجام عملیات در صورت بهنجار جبری

راه‌های ساده و مستقیمی برای انجام عملیات بولی استاندارد بر روی ورودی‌های صورت بهنجار جبری به منظور رسیدن به نتایج صورت بهنجار جبری وجود دارد.

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 (یای منطقی) از $1\oplus (1\oplus a)(1\oplus b)$ (هرگاه هر دو عملوند ترم‌های مثبت داشته باشند) یا $a\oplus b\oplus ab$ (در بقیه موارد) استفاده می‌کند:

{\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_{1}x_{1}\oplus a_{2}x_{2}\oplus \cdots \oplus a_{n}x_{n}\oplus \\&a_{1,2}x_{1}x_{2}\oplus \cdots \oplus a_{n-1,n}x_{n-1}x_{n}\oplus \\&\cdots \oplus \\&a_{1,2,\ldots ,n}x_{1}x_{2}\ldots x_{n}\\\end{array}}

به طوریکه $a_{0},a_{1},\ldots ,a_{1,2,\ldots ,n}\in \{0,1\}^{*}$ به‌طور کامل $f$ را توصیف می‌کنند.

به دست آوردن صورت بهنجار جبری توابع بولی چند آرگومانی به صورت بازگشتی

تنها چهار تابع با یک آرگومان موجود است:

{\begin{array}{rl}&f(x)=0\\&f(x)=1\\&f(x)=x\\&f(x)=1\oplus x\\\end{array}}

برای نشان دادن یک تابع با آرگومان‌های متعدد می‌توان از برابری زیر استفاده کرد:

$f(x_{1},x_{2},\ldots ,x_{n})=g(x_{2},\ldots ,x_{n})\oplus x_{1}h(x_{2},\ldots ,x_{n})$

{\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}}

در واقع،

اگر $x_{1}=0$ آنگاه $x_{1}h=0$ و در نتیجه $f(0,\ldots )=f(0,\ldots )$
اگر $x_{1}=1$ آنگاه $x_{1}h=h$ و در نتیجه $f(1,\ldots )=f(0,\ldots )\oplus f(0,\ldots )\oplus f(1,\ldots )$

از آنجایی که $g$ و $h$ تعداد آرگومان‌های کمتری نسبت به $f$ دارند، به این نتیجه می‌رسیم که با تکرار بازگشتی این پروسه در انتها به توابعی با یک آرگومان می‌رسیم. به عنوان مثال صورت بهنجار جبری $f(x,y)=x\lor y$ را بدست می‌آوریم:

با توجه به رابطه بالا داریم $f(x,y)=f(0,y)\oplus x(f(0,y)\oplus f(1,y))$
از آنجایی که $f(0,y)=0\lor y=y$ و $f(1,y)=1\lor y=1$
نتیجه می‌گیریم $f(x,y)=y\oplus x(y\oplus 1)$
و در انتها به صورت بهنجار جبری $f(x,y)=y\oplus xy\oplus x=x\oplus y\oplus xy$ می‌رسیم.

جستارهای وابسته

منابع

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