تابع f را با ستونی از مقادیر تجزیه کنید. بسط توابع بولی به متغیرها

موضوع نمایندگی را در نظر بگیرید nتابع بولین محلی f(ایکس 1 ,ایکس 2 ,…,ایکس n) چند فرمول جبر گزاره ای.

اجازه دهید نمادی را معرفی کنیم که در آن یک پارامتر برابر با 0 یا 1 است.

بدیهی است که

قضیه 1.1. هر تابع جبر منطقیf(ایکس 1 , ایکس 2 ,…, ایکس n ) برای هرچیمتر (1£ متر £ n) را می توان به شکل زیر نشان داد:

که در آن تفکیک بر روی تمام مجموعه های ممکن از مقادیر متغیر گرفته می شود.

اثبات. مجموعه ای دلخواه از مقادیر همه متغیرهای یک تابع معین را در نظر بگیرید. اجازه دهید نشان دهیم که در این مجموعه، سمت چپ و راست فرمول (1) یک مقدار را می گیرند. سمت چپ است ، درست

زیرا , if only , if , سپس عبارت منطقی مربوطه را می توان نادیده گرفت.

اظهار نظر. نمایش تابع مشخص شده در قضیه را بسط تابع در می گویند مترمتغیرها

نتیجه 1(بسط در یک متغیر).

در این مورد توابع و نامیده می شوند اجزای تجزیه.

نتیجه 2(بسط بر روی همه متغیرها).

بدیهی است، اگر ، آن

بنابراین اگر تابع f(ایکس 1 ,ایکس 2 ,…,ایکس n) یک تابع یکسان نادرست نیست، سپس می توان آن را با یک فرمول معادل بیان کرد که مجموع منطقی محصولات مختلف شکل است و چنین نمایشی منحصر به فرد است.

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

1. هر عبارت منطقی شامل تمام متغیرهای موجود در فرمول است f(ایکس 1 ,ایکس 2 ,…,ایکس n).

2. هیچ عبارت منطقی واحدی حاوی متغیر و نفی آن نیست.

3. تمام اصطلاحات منطقی در فرمول متفاوت است.

4. هیچ عبارت منطقی شامل یک متغیر دو بار نیست.

به این چهار خاصیت می گویند خواص کمال(یا خواص C).

اگر f(ایکس 1 ,ایکس 2 ,…,ایکس n) توسط جدول صدق داده می شود، سپس فرمول جبر منطقی مربوطه به سادگی بازیابی می شود. برای همه مقادیر آرگومان ایکس 1 ,ایکس 2 ,…,ایکس n، که در آن fمقدار 1 را می گیرد، شما باید ترکیب عبارات متغیر ابتدایی را بنویسید، و به عنوان عضوی از ربط در نظر بگیرید. x i، اگر x i=1 و اگر x i=0. تفکیک تمام حروف ربط نوشتاری فرمول لازم خواهد بود. درباره ارزش ها f 0 شما لازم نیست نگران باشید، زیرا ... عبارت مربوطه در فرمول برابر با 0 خواهد بود و به دلیل هم ارزی می توان آن را کنار گذاشت fÚ 0 ≡ f.

به عنوان مثال، اجازه دهید تابع f(ایکس, y, z) دارای جدول حقیقت زیر است:

ایکس	y	z	f(ایکس, y, z)

این قضیه ماهیت سازنده ای دارد، زیرا به هر تابع اجازه می دهد فرمولی بسازد که آن را در قالب یک d.n کامل پیاده سازی کند. f. برای انجام این کار، در جدول صدق هر تابع، تمام سطرهایی را که در آن قرار دارند علامت گذاری می کنیم

کار خود را در شبکه های اجتماعی به اشتراک بگذارید

اگر این کار به درد شما نمی خورد، در پایین صفحه لیستی از آثار مشابه وجود دارد. همچنین می توانید از دکمه جستجو استفاده کنید

آرانوف ویکتور پاولوویچ. ریاضی گسسته

بخش 4. سیستم های عملکردی با عملیات. جبر منطق.

سخنرانی 21. اصل دوگانگی. بسط توابع به متغیرها DNF و CNF کامل

سخنرانی 21. اصل دوگانگی. تجزیه بولی

توابع بر اساس متغیرها. PERFECT DISJUNCTIVE و

فرمهای معمولی پیوندی

طرح کلی سخنرانی:

1. اصل دوگانگی.
2. بسط توابع بولی به متغیرها. اشکال عادی منفصل و ربطی کامل.

1. اصل دوگانگی

تابعی برابر فراخوانی می شوددوگانه تابع به عملکرد.

بدیهی است که جدول صدق تابع دوگانه از جدول صدق تابع با معکوس کردن (یعنی جایگزینی 0 با 1 و 1 با 0) مقادیر متغیرها و تابع به دست می آید. مثلا، .

تنظیم برای توابع 0، 1 آسان است

1. تابع 0 دوتایی به 1 است.
2. تابع 1 دوتایی به 0 است.
3. تابع دوگانه است.
4. تابع دوگانه است.
5. تابع دوگانه است.
6. عملکرد دوگانه است.

از تعریف دوگانگی چنین بر می آید که

یعنی تابع دوگانه به (ویژگی متقابل) است.

اصل دوگانگی.اگر یک فرمول تابعی را تحقق بخشد، فرمول، یعنی فرمول به دست آمده از جایگزینی توابع به ترتیب، تابع را تحقق می بخشد.

ما فرمول را فرمول dual to می نامیم.

برای اثبات این گزاره باید اعتبار آن را برای مراحل ابتدایی برهم نهی و.

به عنوان مثال، اجازه دهید یک تابع از یک تابع در نتیجه جایگزینی متغیرهای زیر بدست آید:

سپس

یعنی تابع در نتیجه جایگزینی یکسان متغیرها به دست می آید.

ما اعتبار اصل دوگانگی را برای یک مرحله با استفاده از یک مثال اثبات خواهیم کرد. اجازه دهید

سپس

یعنی تابعی از و به همان ترتیبی که تابعی از و به دست می آید.

اصل دوگانگی به ما اجازه می دهد تا استخراج توتولوژی های اساسی را ساده کنیم و تعدادی کاربرد مفید دارد که در زیر مورد بحث قرار خواهد گرفت.

مثال 1. از هویت به دنبال هویت است.

واقعا،

;; .

مثال 2. ساخت فرمول برای نفی تابع.

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

ما قانون زیر را دریافت می کنیم:اجازه دهید فرمول تابع را پیاده سازی می کند. برای به دست آوردن فرمول برای یک تابع، باید همه متغیرهای موجود در فرمول را با نفی آنها جایگزین کنید.

بیایید نفی تابع را پیدا کنیم.

از آن به بعد.

1. بسط توابع بولی به متغیرها. کامل

اشکال عادی منفصل و ربطی

اجازه دهید نماد را معرفی کنیم

که در آن یک پارامتر برابر با 0 یا 1 است. بدیهی است،

به راحتی می توان فهمید که 1 اگر و فقط اگر باشد.

قضیه بسط توابع در متغیرها. هر تابع از جبر منطق برای هر () را می توان به شکل زیر نشان داد:

, (1)

که در آن تفکیک بر روی تمام مجموعه های ممکن از مقادیر متغیر گرفته می شود.

این دیدگاه نامیده می شودبسط یک تابع در متغیرها.

اثبات اجازه دهید مجموعه دلخواه از مقادیر متغیر را در نظر بگیریم و نشان دهیم که سمت چپ و راست رابطه (1) یک مقدار را به خود می گیرند. سمت چپ می دهد. درست

به عنوان پیامدهای قضیه، دو مورد خاص از بسط را در نظر می گیریم.

1. بسط متغیر:

توابع فراخوانی می شونداجزای تجزیهاین تجزیه زمانی مفید است که برخی از خواص توسط القاء ایجاد شود.

1. بسط برای همه متغیرها:

اگر به طور یکسان برابر 0 نباشد، می توان آن را تبدیل کرد:

در نتیجه بالاخره به دست می آوریم

. (2)

این تجزیه نامیده می شودفرم نرمال منفک کامل(d.n.f کامل).

مستقیماً به مفهوم کامل d.n. f. قضیه زیر مجاور است.

قضیه. هر تابع از جبر منطق را می توان با یک فرمول در پایه نشان داد.

اثبات.1) اجازه دهید. سپس به وضوح

1. اجازه دهید به طور یکسان برابر با 0 نباشد. سپس می توان آن را با فرمول (2) نشان داد.

این قضیه ماهیت سازنده ای دارد، زیرا به هر تابع اجازه می دهد فرمولی بسازد که آن را به شکل یک d.n کامل اجرا کند. f. برای انجام این کار، در جدول صدق هر تابع، تمام سطرهایی را که در آن قرار دارند علامت گذاری می کنیم. برای هر خط یک محصول منطقی تشکیل می دهیم و سپس تمام پیوندهای حاصل را با یک علامت تفکیک به هم وصل می کنیم.

مثال 3. یک d.n کامل پیدا کنید. f. برای عملکرد

دکترای عالی علوم f. یک عبارت از نوع P است. اجازه دهید نشان دهیم که وقتی برابر با 1 نباشد، می توان آن را به شکل نمایش داد. اجازه دهید بسط برای تابع دوگانه (بدیهی است که برابر با 0 نیست) را به شکل یک d.n کامل بنویسیم. f.:

از اصل دوگانگی بر می آید

بنابراین، ما تجزیه ای به نام به دست می آوریمفرم طبیعی ربطی کامل(دکتری عالی):

. (3)

مثال 4. یک دکتری کامل بسازید. f. برای عملکرد

ما داریم.

کارهای مشابه دیگری که ممکن است مورد توجه شما قرار گیرد.vshm>
200.		اشکال عادی توابع منطقی	63.53 کیلوبایت
	اشکال نرمال توابع منطقی نمایش یک تابع بولی به صورت تفکیک عبارات ربطی اجزای واحد Ki 2.7، شکل نرمال منفصل DNF این تابع نامیده می شود. دقیقاً شامل یکی از همه متغیرهای منطقی است که با یا بدون نفی گرفته شده است، سپس این شکل از نمایش یک تابع، فرم نرمال منفک کامل SDNF این تابع نامیده می شود. همانطور که می بینید، هنگام نوشتن یک تابع SDNF، باید یک تفکیک از تمام مینترم ها ایجاد کنید که تابع مقدار 1 را می گیرد.
9015.		روش‌هایی برای به حداقل رساندن توابع بولی	81.74 کیلوبایت
	مدارهای DNF و FE. به حداقل رساندن توابع بولی بر اساس ساخت DNFهای بن بست. به حداقل رساندن توابع بولی بر اساس ساخت DNF های بن بست، بن بست کاهش یافته و حداقل DNF در رابطه زیر هستند. یک DNF بن بست از یک کاهش یافته با حذف برخی اصطلاحات به دست می آید.
9017.		مشکل به حداقل رساندن توابع بولی. تفسیر هندسی	109.86 کیلوبایت
	مدارهای DNF و FE. تفسیر هندسی طرح کلی سخنرانی: مفهوم شکل عادی منفصل DNF. مفهوم DNF. عبارت Where is یک ربط ابتدایی رتبه است، شکل نرمال منفصل DNF نامیده می شود.
14731.		تجزیه سیگنال ها به یک سری فوریه تعمیم یافته در سیستم های توابع متعامد. توابع والش	38.95 کیلوبایت
	تجزیه سیگنال ها به یک سری فوریه تعمیم یافته در سیستم های توابع متعامد. با ویژگی های اولیه سیگنال ها و تداخل آشنا شوید. بررسی نمایش سیگنال ها در قالب یک سری فوریه تعمیم یافته در سیستم های توابع متعامد. تجزیه سیگنال ها به یک سری فوریه تعمیم یافته در سیستم های توابع متعامد.
6707.		طراحی پایگاه داده های رابطه ای مشکلات طراحی در رویکرد کلاسیک اصول نرمال سازی، اشکال عادی	70.48 کیلوبایت
	پروژه پایگاه داده رابطه ای چیست؟این مجموعه ای از روابط به هم پیوسته است که در آن همه ویژگی ها تعریف می شوند، کلیدهای اولیه روابط مشخص می شوند و برخی ویژگی های اضافی روابط مشخص می شوند که به اصول حفظ یکپارچگی مربوط می شوند. بنابراین طراحی پایگاه داده باید بسیار دقیق و تایید شده باشد. در واقع، یک پروژه پایگاه داده پایه و اساس یک بسته نرم افزاری آینده است که برای مدت طولانی و توسط بسیاری از کاربران استفاده خواهد شد.
4849.		فرم ها و روش های اجرای توابع حالت	197.3 کیلوبایت
	اصطلاح «عملکرد» در ادبیات علمی داخلی و خارجی به دور از معنای مشابه است. در اصطلاح فلسفی و جامعه‌شناسی عام، آن را «تجلی بیرونی ویژگی‌های یک شی در یک نظام روابط معین» می‌دانند. به عنوان مجموعه ای از اعمال عادی یا خاص افراد یا ارگان ها
1790.		تجزیه	180.15 کیلوبایت
	کلمه الگوریتم به خودی خود شبیه الگوریتمی است - شکل لاتین نوشتن نام ریاضیدان بزرگ قرن نهم. الخوارزم که قواعد عملیات حسابی را تدوین کرد. در ابتدا، تحت الگوریتم‌ها، تنها قوانینی برای کشف چندین عملیات حسابی بر روی اعداد دیجیتال غنی درک می‌شد.
2690.		بررسی عملکرد مته‌های با گام مارپیچ متغیر	18.85 کیلوبایت
	مدل‌های فرآیند برش را می‌توان با یک سیستم معادلات ریاضی نشان داد که در هر مورد خاص، عملکرد ارزیابی یا معیارهای عملکرد ابزارهای برش و همچنین محدودیت‌های فنی در سینماتیک ماشین، سختی ابزارهای برش را تعیین می‌کند. و سیستم فناوری به عنوان یک کل
17088.		مسئولیت کیفری برای جرایم ارتکاب یافته به عنوان اعضای یک گروه جنایی سازمان یافته	50.97 کیلوبایت
	Lomtev ویژگی های کلی کار ارتباط موضوع تحقیق با نیاز به توسعه و بهبود بیشتر تئوری و عمل اجرای مسئولیت کیفری برای جرایم ارتکابی به عنوان بخشی از یک گروه جنایی سازمان یافته تعیین می شود. تحقیقات در زمینه مبارزه با جرایم سازمان‌یافته نشان می‌دهد که در درون گروه‌های جنایتکار سازمان‌یافته است که خطرناک‌ترین و دشوارترین جرایم قابل حل است. به عنوان بخشی از حل مشکل افزایش اثربخشی قوانین کیفری در زمینه مبارزه با...
11576.		مفهوم، انواع و اشکال معاملات. عواقب عدم رعایت فرم مورد نیاز معاملات	49.82 کیلوبایت
	تشخیص یک معامله به عنوان نامعتبر؛ انواع معاملات نامعتبر. ارزش کاربردی کار دوره در ساده کردن مفهوم تراکنش است، یعنی ارائه عمومی آن به شکلی در دسترس تر.

تنظیم توابع بولی متغیرها با استفاده از جدول صدق، تعریف فرمول، انواع مهم ترین هم ارزی ها (قوانین) جبر منطق. فرمول های معادل، قوانین هم ارزی، معادلات منطقی. بسط توابع بولی به متغیرها.

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

برای دانلود آرشیو با سند، یک عدد پنج رقمی را در فیلد زیر وارد کنید و روی دکمه "دانلود بایگانی" کلیک کنید.

اسناد مشابه

بدیهیات و هویت های اساسی جبر منطق. شکل تحلیلی نمایش توابع بولی. توابع ابتدایی جبر منطقی. توابع جبر منطقی تک استدلالی و اشکال اجرای آن. ویژگی ها، ویژگی ها و انواع عملیات منطقی.

چکیده، اضافه شده در 1389/06/12


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

آموزش، اضافه شده در 2009/04/29


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

کار دوره، اضافه شده 05/12/2009


عملیات روی گزاره های منطقی: توابع بولی و بیان برخی از این وابستگی ها از طریق دیگران. فرمول های گزاره ای و برخی قوانین منطق گزاره ای. ترجمه عبارات زبان طبیعی به گفتار نمادین جبر منطق.

تست، اضافه شده در 2011/04/26


منطق علم قوانین و اشکال تفکر است و مفهوم اصلی جبر منطق بیانیه است. مفاهیم و هویت های اساسی جبر بولی. مطالعه روش های کمینه سازی توابع بولی. روش کواین، بر اساس کاربرد دو رابطه اساسی.

تست، اضافه شده در 2011/01/20


مفاهیم اساسی جبر منطق. اشکال عادی منفصل و ربطی. جوهر قضیه شانون. توابع بولی دو متغیر. اتصال سری و موازی دو کلید. ویژگی های توابع ابتدایی جبر منطقی.

تست، اضافه شده در 2010/11/29


متغیر منطقی در جبر منطق. عملیات منطقی: نفی، ربط، تفکیک، دلالت، معادل. قوانین اساسی جبر منطق. قوانینی برای به حداقل رساندن یک تابع منطقی (رهایی از عملیات دلالت و هم ارزی).

کار دوره، اضافه شده در 2012/01/16

مجموعه B که بر روی آن دو عمل باینری (اتصال و تفکیک) و یک عملیات واحد (نفی) تعریف شده و دو عنصر 0 و 1 انتخاب شده اند، جبر بولی نامیده می شود.

علاوه بر این، برای این عملیات لازم است که ویژگی های زیر را برآورده کنید:

انجمنی

جابجایی

توزیع پیوند نسبت به تفکیک

توزیع یک تفکیک نسبت به یک ربط

ناتوانی

دو بار نه

خواص ثابت ها

قوانین دی مورگان

قانون تضاد

قانون وسط حذف شده

در جبر منطق به این قوانین هم ارزی می گویند.

فرم های نرمال کامل

فرم نرمال منفک کامل

اجازه دهید نماد زیر را معرفی کنیم:

; A = 1; X A = 1 اگر X = A، X A = 0 اگر XA.

فرمول X A 1…… X A n، که در آن A = هر مجموعه باینری است، و در میان متغیرهای Xi ممکن است متغیرهایی منطبق وجود داشته باشد، یک ربط ابتدایی نامیده می شود.

هر گونه تفکیک حروف ربط ابتدایی را شکل عادی منفصل (DNF) می گویند.

اگر هر متغیر بیش از یک بار (از جمله وقوع آن در زیر علامت نفی) در آن ظاهر شود، یک ربط ابتدایی صحیح نامیده می شود.

به عنوان مثال: 1) (آیکون ربط در این مورد حذف شده است).

1)، 4) - حروف ربط ابتدایی منظم؛

2) - متغیر x یک بار به خودی خود و بار دوم در زیر علامت نفی ظاهر می شود.

متغیر y سه بار ظاهر می شود: یک بار به تنهایی و دو بار در زیر علامت منفی.

یک ربط ابتدایی صحیح با توجه به متغیرهای x 1 .....x n کامل نامیده می شود اگر هر یک از این متغیرها را فقط یک بار شامل شود (جنس ممکن است علامت نفی نیز باشد).

به عنوان مثال: از حروف ربط ذکر شده در مثال قبلی، فقط 4) با توجه به متغیرهای x,y,z,t کامل است. و با توجه به متغیرهای x,y,z فقط 1) کامل است.

یک فرم نرمال منفصل کامل (PDNF) با توجه به متغیرهای x 1 .....x n یک فرم عادی منفصل است که در آن هیچ حرف ربط ابتدایی یکسانی وجود ندارد و همه ربط های ابتدایی نسبت به متغیرهای x 1 صحیح و کامل هستند. ....x n

تجزیه متغیر

قضیه 1. هر تابع منطقی را می توان در SDNF نشان داد:

که در آن m، و تفکیک بر روی تمام مجموعه‌های 2 متری متغیرهای x 1،...x m گرفته می‌شود. تابع f به n متغیر اول گسترش می یابد. این برابری را بسط در متغیرها می گویند. x 1، … x m. برای مثال، با n=4، m=2، بسط به شکل زیر است:

این قضیه با جایگزین کردن دو طرف برابری (1) یک مجموعه دلخواه (b 1 ,…,b m , b m+1 ,…,b n) از همه n متغیر اثبات می شود.

برای m = 1، از (1) بسط تابع را در یک متغیر به دست می آوریم:

بدیهی است که یک بسط مشابه برای هر یک از متغیرهای n معتبر است.

مورد مهم دیگر زمانی است که n=m. در این حالت، همه متغیرهای سمت راست (1) مقادیر ثابتی دریافت می‌کنند و توابع در پیوند سمت راست برابر با 0 یا 1 می‌شوند که به دست می‌آید:

که در آن تفکیک بر روی همه مجموعه ها (b 1 ...b n) گرفته می شود، که در آنها f=1. برای f=0، مجموعه حروف ربط در سمت راست خالی است. به این تجزیه فرم نرمال منفصل کامل می گویند. SDNF یک تابع f دقیقاً به تعداد واحدهای موجود در جدول صدق f حاوی پیوندهای ربط است. هر مجموعه واحد (b 1،...، b n) مربوط به ترکیبی از همه متغیرها است، که در آن x i با نفی اگر b i = 0 b، و بدون نفی اگر b i = 1 گرفته می شود. بنابراین، یک مطابقت یک به یک بین جدول صدق تابع f و SDNF آن وجود دارد، و در نتیجه، SDNF برای هر تابع منطقی منحصر به فرد است. تنها تابعی که SDNF ندارد ثابت 0 است.

قضیه 2. هر تابع منطقی را می توان به عنوان یک فرمول بولی نشان داد.

در واقع، برای هر تابعی غیر از ثابت 0، SDNF آن می تواند به عنوان چنین نمایشی عمل کند. ثابت 0 را می توان با فرمول بولی نشان داد.

3.1 گسترش توابع بولی به متغیرها

3.2 جبر ژگالکین

ما در بالا نشان دادیم که هر تابع بولی را می توان با استفاده از جدول صدق مشخص کرد. این بخش انتقال از یک انتقال جدولی برای تعیین یک تابع به یک انتقال تحلیلی را نشان می دهد.

3.1 گسترش توابع بولی به متغیرها.

فرض کنید G پارامتری برابر با 0 یا 1 باشد. اجازه دهید نماد را معرفی کنیم:

بررسی آن آسان است ایکس G = 1، اگر و فقط اگر ایکس = جی. از آن نتیجه می شود که ربط
برابر 1 (در اینجا G برابر 0 یا 1 است) اگر و فقط اگر
. مثلاً ربط
(که در آن G 2 =G 1 = 0،G 3 =G 4 = 1) برابر با 1 است فقط اگر ایکس 1 =ایکس 2 = 0,ایکس 3 =ایکس 4 = 1.

قضیه 1هر تابع بولیf(ایکس 1 , ایکس 2 ,…, ایکس n ) را می توان به شکل زیر ارائه کرد:

جایی که 1 ≤ک ≤ n، در تفکیک تمام مجموعه های مقادیر متغیر گرفته می شود.

به این نمایش، بسط یک تابع به متغیرها گفته می شود
. به عنوان مثال، زمانی که n= 4، k= 2، بسط (3.1) به شکل زیر است:

.

اجازه دهید اعتبار بسط (3.1) را اثبات کنیم. برای انجام این کار، مجموعه دلخواه از مقادیر متغیر را بگیرید
. اجازه دهید نشان دهیم که سمت چپ و راست رابطه (3.1) مقدار یکسانی دارند. در واقع، از آن زمان ایکس G = 1 اگر و فقط اگر ایکس =G، سپس در میان 2 K حرف ربط
در سمت راست (3.1) تنها یکی به وحدت می رود که در آن
. همه ربط های دیگر
برابر با صفر هستند.

از همین رو . در نتیجه گسترش (3.1)، دو بسط ویژه زیر را بدست می آوریم.

بسط متغیرایکس n :

اگر تابع بولی ثابت 0 نباشد، بسط درست است

بسط برای همه متغیرها:

,
(3.3)

که در آن تفکیک در تمام مجموعه ها گرفته می شود
، که برای آن مقدار تابع است
برابر 1.

بسط (3.3) فرم نرمال منفصل کامل (شکل کوتاه SDNF) تابع نامیده می شود.

بسط (3.3) راهی برای ساخت SDNF فراهم می کند. برای انجام این کار، تمام ردیف ها را در جدول حقیقت علامت گذاری کنید
، که در آن
. برای هر یک از این خط ها یک ربط تشکیل می دهیم
و سپس تمام حروف ربط حاصل را با علامت تفکیک به هم وصل می کنیم.

بنابراین، یک مطابقت یک به یک بین جدول صدق تابع وجود دارد
و SDNF او. این بدان معنی است که SDNF برای یک تابع بولی منحصر به فرد است.

یک تابع بولی منفرد که SDNF ندارد ثابت 0 است.

مثال 1یک فرم تفکیک کامل برای یک تابع پیدا کنید
.

بیایید یک جدول حقیقت برای این تابع ایجاد کنیم:

از اینجا دریافت می کنیم:
==.

بسط زیر توابع بولی نقش مهمی در جبر منطق دارد.

قضیه 2هر تابع بولی
را می توان به شکل زیر ارائه کرد:

که در آن 1≤k≤n، و ربط گرفته شده است برای همه 2 ک مجموعه ای از مقادیر متغیر

در واقع، اجازه دهید
- مجموعه دلخواه از مقادیر متغیر. اجازه دهید نشان دهیم که سمت چپ و راست رابطه (3.4) مقدار یکسانی دارند. زیرا
فقط زمانی که
، سپس در میان 2 k جدایی
در سمت راست (3.4) تنها یک به 0 می رود که در آن
. همه تفکیک های دیگر برابر با 1 هستند.

از همین رو
==
.

بسط توابع بولی مستقیماً از بسط (3.4) پیروی می کند:

آخرین تجزیه فرم نرمال پیوندی کامل (PCNF) نامیده می شود. بسط (3.6) روشی را برای ساختن SCNF ارائه می دهد. برای انجام این کار، تمام ردیف ها را در جدول حقیقت علامت گذاری کنید
، که در آن. برای هر یک از این خطوط ما یک جدایی تشکیل می دهیم
و سپس تمام حروف ربط به دست آمده را با یک علامت ربط به هم وصل می کنیم. بنابراین، یک مطابقت یک به یک بین جدول صدق تابع وجود دارد
و SKNF آن. این بدان معنی است که SCNF برای یک تابع بولی منحصر به فرد است.

تنها تابع بولی که SCNF ندارد ثابت 1 است.

مثال 2شکل نرمال ربطی کامل را برای تابع پیدا کنید
.

بیایید یک جدول حقیقت برای این تابع ایجاد کنیم.

از اینجا ما SKNF را دریافت می کنیم

فرمول فرم (نماد کوتاه
)، جایی که
- حروف ربط
تماس گرفت فرم نرمال منفصل (DNF).

با توجه به تعریف فوق از DNF، به عنوان مثال، عبارات زیر وجود خواهد داشت:
,
.

همانطور که در بند 2.2 ذکر شد، تمام عملیات منطقی را می توان به سه کاهش داد: پیوند، تفکیک و نفی. علاوه بر این، با توجه به قانون دی مورگان، علامت نفی را می توان تنها برای متغیرها اعمال کرد.

حال با استفاده از قانون توزیع، پرانتزها را باز می کنیم و شکل نرمال منفصل را می گیریم. بنابراین، قضیه زیر درست است.

قضیه3 برای هر فرمول در جبر منطق، یک شکل عادی منفصل معادل آن وجود دارد.

اثبات این قضیه راهی برای ساختن یک فرم نرمال منفک برای هر فرمول در جبر منطق فراهم می کند.

مثال 3شکل نرمال منفصل را برای فرمول زیر پیدا کنید:
.

علامت استثناء
در قانون
و با اعمال قوانین دی مورگان و نفی مضاعف، دریافت می کنیم:

سپس با اعمال قانون توزیع، براکت ها را باز می کنیم

آخرین عبارت یک شکل عادی منفصل است.

مشاهده فرم
(یادداشت کوتاه )، جایی که
- گسست ها
تماس گرفت فرم نرمال پیوندی (CNF).

چنین عباراتی برای مثال عبارتند از:

,
.

همانطور که در بالا نشان داده شد، برای هر فرمول در جبر منطق یک شکل منفصل معادل وجود دارد. با استفاده از قانون توزیع، بدست آوردن CNF از یک DNF معین آسان است.

بنابراین، قضیه زیر درست است.

قضیه 4برای هر فرمول در جبر منطق، یک شکل عادی ربطی معادل آن وجود دارد.

اثبات این قضیه راهی برای ساختن یک فرم نرمال ربطی برای هر فرمول در جبر منطق فراهم می کند.

مثال4 برای فرمول زیر فرمول متفرقه و ربط را پیدا کنید:
.

با استفاده از قانون
، علامت را حذف کنید
. ما فرمول را دریافت می کنیم
.

با استفاده از قانون دی مورگان فرمول را بدست می آوریم
. با باز کردن پرانتز، شکل نرمال منفصل را به دست می آوریم

.

برای به دست آوردن شکل نرمال ربطی، روی فرمول اعمال کنید
قانون توزیع، دریافت می کنیم:

آخرین عبارت، شکل عادی ربطی است. زیرا
و
، سپس CNF حاصل معادل CNF زیر است:

در میان تمام فرمول های نرمال این فرمول، فرم نرمال کامل، هم منفصل و هم ربط را برجسته می کنیم. با در نظر گرفتن تجزیه (3)، به راحتی می توان دریافت که شکل نرمال منفک کامل یک فرمول جبر منطقی که دقیقاً حاوی n متغیر مختلف است، شکل عادی منفصل آن است که در آن:

1) همه حروف ربط به صورت زوجی متمایز هستند.

2) هر حرف ربط دقیقاً حاوی n متغیر است.

3) در هر پیوند، تمام n متغیر رخ می دهد.

با استفاده از مثال 1، ما به یکی از راه‌های ساخت SDNF بر اساس گردآوری جدول حقیقت نگاه کردیم. روش بعدی ساخت SDNF بر اساس اعمال قوانین جبر منطقی است.

مثال 5شکل تفکیک کامل فرمول را پیدا کنید
.

با استفاده از آن
، ما گرفتیم
. با توجه به قوانین دی مورگان و نفی مضاعف، یک شکل عادی منفصل داریم
. این DNF معادل فرمول است.

با گسترش براکت ها به این موارد می رسیم: .

با استفاده از قانون ناتوانی، SDNF مورد نیاز را بدست می آوریم:

با در نظر گرفتن تجزیه (3.6)، به راحتی می توان دریافت که شکل نرمال ربطی کامل یک فرمول جبر منطقی دقیقاً حاوی nمتغیرهای مختلف، شکل نرمال ربطی آن وجود دارد که در آن:

1) همه تفکیک ها به صورت زوجی مجزا هستند.

2) هر تفکیک دقیقاً شامل n عبارت است.

3) در هر تفکیک تمام n متغیر رخ می دهد.

با استفاده از مثال 2، ما به یکی از راه‌های ساخت SCNF بر اساس گردآوری جدول صدق نگاه کردیم. روش بعدی ساخت SCNF بر اساس اعمال قوانین جبر منطقی است.

مثال 6شکل نرمال ربطی کامل فرمول را پیدا کنید
.

استفاده كردن،
، ما گرفتیم
.

این فرمول شکل نرمال ربطی است. معادل فرمول است.

با استفاده از قانون توزیع، به دست می آوریم:

با اعمال قانون ناتوانی، شکل نرمال ربط کامل مورد نیاز را به دست می آوریم

یکسان با درست، اگر برای تمام مقادیر متغیرهای موجود در آن مقدار را بگیرد درست است، واقعی.

نمونه هایی از فرمول های یکسان درست فرمول های زیر هستند:

فرمول جبر منطقی نامیده می شود یکسان نادرست، اگر برای تمام مقادیر متغیرهای موجود در آن، مقدار را بگیرد دروغ.

نمونه هایی از فرمول های یکسان نادرست فرمول های زیر هستند:

,

فرمول جبر منطقی نامیده می شود شدنی، اگر برای برخی از مقادیر متغیرهای موجود در آن، مقدار را بگیرد درست است، واقعی.

نمونه هایی از فرمول های اجرایی فرمول های زیر هستند:

,
.

در جبر منطق، می توانید کار زیر را تعیین کنید: یک روش (الگوریتم) را نشان دهید که به شما امکان می دهد برای هر فرمول در جبر منطق متوجه شوید که آیا دقیقاً یکسان است یا خیر. وظیفه نامیده می شود حل مشکلات

بیایید دو راه زیر را برای حل این مشکل در نظر بگیریم.

روش 1 (جدولی)برای تعیین اینکه آیا فرمول داده شده دقیقاً یکسان است یا خیر، کافی است جدول صدق آن را تهیه کنید.

با این حال، این روش، اگرچه راه حلی اساسی برای مسئله حل پذیری ارائه می دهد، اما نسبتاً دست و پا گیر است.

روش 2مبتنی بر کاهش فرمول ها به فرم معمولی است.

قضیه 4یک فرمول در جبر منطق به طور یکسان صادق است اگر و تنها در صورتی که هر تفکیک در شکل عادی ربطی خود حاوی متغیری همراه با نفی آن باشد.

در واقع، اگر هر تفکیک به صورت عادی ربطی شامل یک متغیر همراه با نفی آن باشد، آنگاه همه تفکیک ها برابر با 1 هستند، زیرا
,
. نتیجه این است که CNF یکسان درست است.

بگذارید اکنون این فرمول به طور یکسان درست باشد و اجازه دهید
مقداری تفکیک در CNF این فرمول وجود دارد. فرض کنیم این تفکیک شامل متغیری همراه با نفی آن نباشد. در این صورت می توانیم به هر متغیری که زیر علامت نفی نیست، مقدار 0 و به هر متغیری که زیر علامت نفی قرار دارد، مقدار 1 بدهیم، پس از این جایگزینی، همه تفکیک ها برابر با 0 می شوند، بنابراین مقدار فرمول یکسان درست نیست ما دچار تناقض شدیم.

مثال 7دریابید که آیا فرمول یکسان درست است یا خیر

.

با استفاده از آن
، ما گرفتیم
.

با اعمال قانون توزیع، CNF را بدست می آوریم:

از آنجایی که هر تفکیک شامل یک متغیر خاص همراه با نفی آن است، فرمول یکسان درست است.

مانند قضیه قبل، قضیه ثابت می شود:

قضیه 5 یک فرمول جبر منطقی یکسان نادرست است اگر و تنها در صورتی که هر حرف ربط در شکل منفصل خود حاوی متغیری همراه با نفی آن باشد..