مثال.فرمول های CNF را پیدا کنید

~ ~

فرم نرمال منفصل کامل SDNF را می توان با استفاده از الگوریتم زیر ساخت:

1. = 1. الگوریتم DNF

2. = 2. الگوریتم DNF

3. = 3. الگوریتم DNF

4. = 4. الگوریتم DNF

5. اصطلاحات نادرست یکسان، یعنی اصطلاحات فرم را حذف کنید

6. عبارت های باقیمانده را با متغیرهای گمشده کامل کنید

7. نقطه 4 را تکرار کنید.

مثال.فرمول های SDNF را پیدا کنید.

~

برای ساختن SCNF می توانید از طرح زیر استفاده کنید:

مثال.فرمول های SDNF را پیدا کنید.

~

شناخته شده است (قضیه های 2.11، 2.12) که SDNF و SCNF به طور منحصر به فردی توسط فرمول تعریف می شوند و بنابراین، می توان آنها را با استفاده از جدول حقیقت فرمول ساخت.

طرح ساخت SDNF و SCNF طبق جدول حقیقت در زیر برای فرمول آورده شده است. ~ :

			~
			1 0 1 0 1 1 0 1	SDNF; SKNF.

2.2. ورزش.

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

2.2.2. با تقلیل آنها به SDNF، مسئله هم ارزی f 1 و f 2 را روشن کنید (جدول 1).

2.2.3. تابع دوگانه f 3 را با استفاده از اصل تعمیم یافته و بولی پیدا کنید (جدول 1). نتایج را مقایسه کنید.

№	f 1	f 2	f 3

2.3. کنترل سوالات

2.3.1. یک بیانیه را تعریف کنید.

2.3.2. عملیات اصلی را در یک بیانیه فهرست کنید.

2.3.3. جدول حقیقت چیست؟

2.3.4. جداول صدق را برای فرمول های زیر ایجاد کنید:

~ ~ ~ ;

2.3.5. با در نظر گرفتن قراردادهای مربوط به ترتیب عملیات، پرانتزهای "اضافی" و علامت "" را در فرمول ها حذف کنید:

;

2.3.6. با استفاده از تبدیل های معادل، صدق یکسان فرمول ها را ثابت کنید:

2.3.7. فرمول های دوگانه را پیدا کنید:

)

2.3.8. فرمول های زیر را به فرم DNF کامل (SDNF) کاهش دهید:

~

2.3.9. فرمول های زیر را به فرم CNF کامل (SCNF) کاهش دهید:

~

کار آزمایشگاهی شماره 3

موضوع:«به حداقل رساندن توابع بولی. منطق"

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

3.1. اطلاعات نظری

فرم های حداقلی

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

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

فرمول ارائه شده به شکل نرمال منفصل با استفاده مکرر از عملیات چسباندن و عمل جذب ساده شده است و (هویت های دوگانه برای فرم نرمال ربطی به شکل: و ). در اینجا، و می تواند به عنوان هر فرمول جبر بولی درک شود. در نتیجه، ما به یک بیان تحلیلی می رسیم که در آن تغییر و تحولات بیشتر امکان پذیر نیست، یعنی. ما یک فرم بن بست دریافت می کنیم.

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

به عنوان مثال، اجازه دهید تابع به شکل منفصل نرمال کامل داده شود:

گروه بندی اصطلاحات و اعمال عملیات چسباندن، داریم .

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

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

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

مکعب چند بعدی

هر رأس یک مکعب -بعدی را می توان با یک جزء تشکیل دهنده یک واحد مرتبط کرد. در نتیجه، زیرمجموعه رئوس علامت‌گذاری‌شده یک نگاشت بر روی مکعب بعدی یک تابع بولی از متغیرها به شکل نرمال منفک کامل است. در شکل 3.1 چنین نقشه برداری را برای تابع از بند 3.7 نشان می دهد.

شکل 3.1 نمایش یک تابع ارائه شده در SDNF بر روی یک مکعب سه بعدی

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

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

عناصر یک مکعب - بعدی که با ابعاد مشخص می شوند - مکعب نامیده می شوند. بنابراین، رئوس 0-مکعب، یال ها 1-مکعب، وجه ها 2-مکعب و غیره هستند. با تعمیم استدلال بالا، می‌توان فرض کرد که یکمین ترم رتبه ()ام در شکل نرمال منفک برای تابعی از متغیرها با یک مکعب نمایش داده می‌شود و هر مکعب تمام آن مکعب‌هایی با ابعاد پایین‌تر را که با رئوس آن مرتبط هستند را پوشش می‌دهد. . به عنوان مثال در شکل. 3.2 تابعی از سه متغیر را نشان می دهد. در اینجا مینی ترم ها با 1-مکعب () مطابقت دارد، و مینی ترم با یک مکعب (2) نشان داده می شود.

شکل 3.2 پوشش عملکرد

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

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

برنج. 3.3 پوشش های عملکردی.

ترک کرد – ; سمت راست –

نمایش یک تابع در یک مکعب بعدی واضح و ساده است زمانی که . یک مکعب چهار بعدی را می توان همانطور که در شکل نشان داده شده است نشان داد. 3.4 که تابعی از چهار متغیر و حداقل پوشش آن مربوط به عبارت را نشان می دهد . استفاده از این روش به ساخت و سازهای پیچیده ای نیاز دارد که تمام مزایای آن از بین می رود.

برنج. 3.4 نمایش عملکرد روی یک مکعب چهار بعدی

نقشه های کارنو

روش دیگری برای نمایش گرافیکی توابع بولی استفاده می کند نقشه های کارنو، که جداول مکاتبات ویژه سازماندهی شده اند. ستون‌ها و ردیف‌های جدول مربوط به تمام مجموعه‌های ممکن مقادیر حداکثر دو متغیر است و این مجموعه‌ها به گونه‌ای مرتب شده‌اند که هر یک از مجموعه‌های بعدی تنها در مقدار یکی از متغیرها با قبلی متفاوت است. . با تشکر از این، سلول های همسایه جدول به صورت افقی و عمودی در مقدار تنها یک متغیر متفاوت است. سلول هایی که در لبه های جدول قرار دارند نیز مجاور در نظر گرفته می شوند و این خاصیت را دارند. در شکل شکل 3.5 نقشه های کارناو را برای دو، سه، چهار متغیر نشان می دهد.

برنج. 3.5 نقشه های Carnaugh برای دو، سه و چهار متغیر

مانند جداول صدق معمولی، سلول‌های مجموعه‌هایی که در آنها تابع مقدار 1 را می‌گیرد، با یک‌ها پر می‌شوند (صفرها معمولاً در آن جا نمی‌شوند، آنها با سلول‌های خالی مطابقت دارند). به عنوان مثال، در شکل. 3.6، آنقشه کارناو را برای تابعی نشان می دهد که نمایش آن بر روی یک مکعب چهار بعدی در شکل 1 آورده شده است. 3.4. برای ساده کردن چیزها، ردیف‌ها و ستون‌های مربوط به مقادیر 1 برای یک متغیر با یک پرانتز مجعد که آن متغیر را نشان می‌دهد برجسته می‌شوند.

برنج. 3.6 نمایش تابعی از چهار متغیر بر روی نقشه Carnaugh

(الف) و حداقل پوشش آن (ب)

بین نگاشت تابع به nمکعب بعدی و نقشه کارنو مطابقت یک به یک دارد. در نقشه کارنو سیک مکعب مربوط به مجموعه ای از 2 سلول همسایه است که در یک ردیف، ستون، مربع یا مستطیل قرار گرفته اند (با در نظر گرفتن نزدیکی لبه های مخالف نقشه). بنابراین، تمام مقررات ذکر شده در بالا (به پاراگراف مراجعه کنید. مکعب چند بعدی)، برای نقشه های کارناگ معتبر هستند. بنابراین، در شکل. 3.6، بپوشش واحدهای نقشه مربوط به فرم منفصل حداقل را نشان می دهد تابع مورد نظر

خواندن مینی ترم ها از نقشه کارنا از یک قانون ساده پیروی می کند. تشکیل سلول ها س-مکعب، مینیتر بده (n–s)رتبه -ام که شامل آن ها می شود (n–s)متغیرهایی که مقادیر یکسانی را در این مورد حفظ می کنند س-cube، که در آن مقدار 1 مربوط به خود متغیرها و مقدار 0 مربوط به نفی آنها است. متغیرهایی که مقادیر خود را برای آنها حفظ نمی کنند س-مکعب، در مینی ترم وجود ندارند. روش‌های مختلف خواندن منجر به نمایش‌های متفاوتی از تابع به شکل عادی منفک می‌شوند (یکی در سمت راست حداقل است) (شکل 3.7).

استفاده از نقشه های کارناو در مقایسه با نقشه برداری نیاز به ساختارهای ساده تری دارد n-مکعب بعدی، به خصوص در مورد چهار متغیر. برای نمایش توابع پنج متغیر از دو نقشه کارناو برای چهار متغیر و برای تابع شش متغیر از چهار نقشه از این قبیل استفاده می شود. با افزایش بیشتر در تعداد متغیرها، نقشه های کارنو عملا غیر قابل استفاده می شوند.

در ادبیات مشهور است کارت های ویچآنها فقط در ترتیب مختلف مجموعه مقادیر متغیر متفاوت هستند و دارای ویژگی های مشابه نقشه های Karnaugh هستند.

مجموعه ای از مکعب ها

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

). 0-مکعب های مربوط به اجزای وحدت با مجموعه ای از مقادیر متغیر نشان داده می شوند که در آنها تابع برابر با وحدت است. واضح است که در ضبط

برنج. 3.8 مجموعه مکعب های تابعی از سه متغیر ( آ) و بازنمایی نمادین آن ( ب)

مجموعه مکعب ها تشکیل می شود حداکثر پوشش عملکرد. به استثنای آن همه س-مکعب هایی که توسط مکعب هایی با ابعاد بالاتر پوشانده شده اند، پوشش های مربوط به فرم های بن بست را بدست می آوریم. بنابراین، برای مثال مورد بررسی (شکل 3.8) ما یک پوشش بن بست داریم

,

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

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

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

به حداقل رساندن توابع بولی

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

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

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

یک مکعب پوشش کاهش‌یافته که رئوس یک تابع معین را که توسط هیچ مکعب دیگری پوشانده نشده است، می‌پوشاند، نمی‌تواند اضافی باشد و همیشه در حداقل پوشش گنجانده می‌شود. چنین مکعبی مانند ایمپلینت متناظر آن Extremal (Essential Implicant) نامیده می‌شود و رئوس آن را رئوس لغو می‌گویند. مجموعه اکستریمال ها هسته پوشش را تشکیل می دهد؛ واضح است که هنگام انتقال از یک پوشش کاهش یافته به پوشش حداقلی، اول از همه، همه اکستریمال ها باید ایزوله شوند. اگر مجموعه اکستریمال ها پوششی تشکیل ندهند، برای پوشش با مکعب هایی از پوشش کاهش یافته تکمیل می شود.

تعاریف داده شده در شکل 1 نشان داده شده است. 3.9، که در آن پوشش کاهش یافته است (به شکل 3.9a مراجعه کنید، ) و حداقل پوشش ها (شکل 3.9b) و (نگاه کنید به شکل 3.9، b) به صورت زیر بیان می شوند.

تعریف 1.ربط ربط (ربط ابتدایی)متغیرها ترکیب این متغیرها یا نفی آنهاست.

مثلا، یک ربط ابتدایی است.

تعریف 2.منفصل منفصل (تجزیه ابتدایی)از متغیرها تفکیک این متغیرها یا نفی آنها است.

مثلا، یک تفکیک ابتدایی است.

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

مثلا،– DNF

تعریف 4.فرمولی که معادل یک فرمول جبر گزاره ای معین و ترکیبی از تک جمله های منفصل ابتدایی است نامیده می شود. فرم نرمال پیوندی(CNF) از این فرمول.

مثلا، – KNF.

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

الگوریتم ساخت فرم های معمولی

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

از شر منفی های مضاعف خلاص شوید.

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

2.6. اشکال متعارف کامل و ربط کامل

هر تابع بولی می تواند نمایش های زیادی به شکل DNF و CNF داشته باشد. جایگاه ویژه ای در بین این نمایش ها توسط DNF کامل (SDNF) و CNF کامل (SCNF) اشغال شده است.

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

از نظر ساختاری، SDNF برای هر فرمول جبر گزاره ای کاهش یافته به DNF را می توان به صورت زیر تعریف کرد:

تعریف 2. فرم نرمال منفک کامل(SDNF) یک فرمول جبر گزاره ای DNF آن نامیده می شود که دارای ویژگی های زیر است:

تعریف 3. فرم نرمال پیوندی کامل(SCNF) یک CNF است که در آن هر تک جمله منفصل هر متغیر از مجموعه را دقیقاً یک بار شامل می شود و یا خودش یا نفی آن ظاهر می شود.

از نظر ساختاری، SCNF برای هر فرمول جبر گزاره ای کاهش یافته به CNF را می توان به صورت زیر تعریف کرد.

تعریف 4. فرم نرمال پیوندی کامل(SCNF) یک فرمول جبر گزاره ای داده شده CNF نامیده می شود که ویژگی های زیر را برآورده می کند.

قضیه 1.هر تابع بولی از متغیرها که به طور یکسان نادرست نیستند، می توانند در SDNF و به روشی منحصر به فرد نمایش داده شوند.

روش های یافتن SDNF

روش 1

روش دوم

خطوطی را انتخاب کنید که در آن فرمول مقدار 1 را می گیرد.

ما یک تفکیک از حروف ربط را با این شرط می سازیم که اگر متغیری با مقدار 1 در رابطه ربط گنجانده شود، آن متغیر را یادداشت می کنیم و اگر با مقدار 0 باشد، نفی آن. ما SDNF دریافت می کنیم.

قضیه 2.هر تابع بولی از متغیرها که به طور یکسان درست نیست را می توان در SCNF و به روشی منحصر به فرد نمایش داد.

روش های یافتن SCNF

روش 1- استفاده از تبدیل های معادل:

روش دوم- استفاده از جداول صدق:

خطوطی را انتخاب کنید که در آن فرمول مقدار 0 را می گیرد.

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

مثال 1.توابع CNF را بسازید.

راه حل

بیایید پیوند "" را با استفاده از قوانین تبدیل متغیرها حذف کنیم:

= /قوانین دو مورگان و نفی مضاعف/ =

/قوانین توزیعی/ =

مثال 2.فرمول را به DNF بدهید.

راه حل

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

= /بیایید نفی را به عنوان متغیر طبقه بندی کنیم و منفی های دوگانه را کاهش دهیم/ =

= /قانون توزیع/ .

مثال 3.فرمول را در DNF و SDNF بنویسید.

راه حل

با استفاده از قوانین منطق، ما این فرمول را به شکلی تقلیل می دهیم که فقط شامل انفصال ربط های ابتدایی باشد. فرمول حاصل DNF مورد نظر خواهد بود:

برای ساخت SDNF، بیایید یک جدول حقیقت برای این فرمول ایجاد کنیم:

آن ردیف‌هایی از جدول را علامت‌گذاری می‌کنیم که در آن فرمول (ستون آخر) مقدار 1 را می‌گیرد. برای هر یک از این ردیف‌ها، فرمولی را می‌نویسیم که روی مجموعه متغیرهای این سطر صادق است:

خط 1: ؛

خط 3:

خط 5: .

تفکیک این سه فرمول مقدار 1 را فقط روی مجموعه متغیرهای خطوط 1، 3، 5 خواهد گرفت و بنابراین شکل نرمال منفک کامل (PDNF) خواهد بود:

مثال 4.فرمول را به دو روش به SKNF بیاورید:

الف) استفاده از تبدیل های معادل؛

ب) استفاده از جدول حقیقت.

راه حل:

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

فرمول به نظر می رسد:

ب) جدول صدق را برای این فرمول ترسیم کنید:

آن ردیف‌هایی از جدول را علامت‌گذاری می‌کنیم که در آن فرمول (ستون آخر) مقدار 0 را می‌گیرد. برای هر یک از این ردیف‌ها، یک فرمول درست روی مجموعه متغیرهای این ردیف می‌نویسیم:

خط 2: ؛

خط 6: .

پیوند این دو فرمول فقط در مجموعه متغیرهای خطوط 2 و 6 مقدار 0 را می گیرد و بنابراین فرم نرمال پیوندی کامل مورد نظر (PCNF) خواهد بود:

سوالات و وظایف برای راه حل مستقل

1. با استفاده از تبدیل های معادل، فرمول ها را به DNF کاهش دهید:

2. با استفاده از تبدیل های معادل، فرمول ها را به CNF بیاورید:

3. با استفاده از قانون توزیع دوم، DNF را به CNF تبدیل کنید:

آ) ;

4. DNF های داده شده را به SDNF تبدیل کنید:

5. CNF داده شده را به SCNF تبدیل کنید:

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

ب) ;

شکل عادی ربطی برای اثبات خودکار قضایا مناسب است. هر فرمول بولی را می توان به CNF کاهش داد. برای این می توانید از: قانون نفی مضاعف، قانون دو مورگان، توزیع استفاده کنید.

یوتیوب دایره المعارفی

• 1 / 5

  فرمول ها در KNF:

  ¬ A ∧ (B ∨ C)، (\displaystyle \neg A\wedge (B\vee C)) (A ∨ B) ∧ (¬ B ∨ C ∨ ¬ D) ∧ (D ∨ ¬ E) , (\displaystyle (A\vee B)\wedge (\neg B\vee C\vee \neg D)\wedge ( D\vee\neg E)) A∧B. (\displaystyle A\wedge B.)

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

  ¬ (B ∨ C)، (\displaystyle \neg (B\vee C)،) (A ∧ B) ∨ C , (\displaystyle (A\wedge B)\vee C,) A ∧ (B ∨ (D ∧ E)) . (\displaystyle A\wedge (B\vee (D\wedge E)).)

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

  ¬ B ∧ ¬ C , (\displaystyle \neg B\wedge \neg C,) (A ∨ C) ∧ (B ∨ C) , (\displaystyle (A\vee C)\wedge (B\vee C)،) A ∧ (B ∨ D) ∧ (B ∨ E) . (\displaystyle A\wedge (B\vee D)\wedge (B\vee E).)

  ساخت CNF

  الگوریتم ساخت CNF

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

  A → B = ¬ A ∨ B، (\displaystyle A\ فلش سمت راست B=\neg A\vee B،) A ↔ B = (¬ A ∨ B) ∧ (A ∨ ¬ B) . (\displaystyle A\فلش راست چپ B=(\neg A\vee B)\wedge (A\vee \neg B).)

  2) علامت نفی مربوط به کل عبارت را با علائم نفی مربوط به گزاره های متغیر جداگانه بر اساس فرمول ها جایگزین کنید:

  ¬ (A ∨ B) = ¬ A ∧ ¬ B , (\displaystyle \neg (A\vee B)=\neg A\wedge \neg B,) ¬ (A ∧ B) = ¬ A ∨ ¬ B . (\displaystyle \neg (A\wedge B)=\neg A\vee \neg B.)

  3) از شر منفی های مضاعف خلاص شوید.

  4) در صورت لزوم، خواص فرمول های توزیع و جذب را در عملیات اتصال و تفکیک اعمال کنید.

  نمونه ای از ساخت CNF

  اجازه دهید فرمول را به CNF بیاوریم

  F = (X → Y) ∧ ((¬ Y → Z) → ¬ X) . (\displaystyle F=(X\فلش سمت راست Y)\wedge ((\neg Y\راست فلش Z)\arrow سمت راست \neg X).)

  بیایید فرمول را تبدیل کنیم F (\displaystyle F)به فرمولی که شامل نمی شود → (\displaystyle \پیکان راست):

  F = (¬ X ∨ Y) ∧ (¬ (¬ Y → Z) ∨ ¬ X) = (¬ X ∨ Y) ∧ (¬ (¬ Y ∨ Z) ​​∨ ¬ X) . (\displaystyle F=(\neg X\vee Y)\wedge (\neg (\neg Y\ فلش سمت راست Z)\vee \neg X)=(\neg X\vee Y)\wedge (\neg (\neg \ neg Y\vee Z)\vee \neg X).)

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

  F = (¬ X ∨ Y) ∧ ((¬ Y ∧ ¬ Z) ∨ ¬ X) . (\displaystyle F=(\neg X\vee Y)\wedge ((\neg Y\wedge \neg Z)\vee \neg X).)

  به عنوان مثال، فرمول زیر در 2-CNF نوشته شده است:

  (A ∨ B) ∧ (¬ B ∨ C) ∧ (B ∨ ¬ C) . (\displaystyle (A\lor B)\land (\neg B\lor C)\land (B\lor \neg C).)

  ساده پیوستگی تماس گرفت پیوستگی یکی یا چندین متغیرها, در این هر یک متغیر ملاقات می کند نه بیشتر یکی بار (یا خودش, یا او نفی).

  به عنوان مثال، یک ربط ساده است،

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

  به عنوان مثال، عبارت DNF است.

  کامل منفصل طبیعی شکل(SDNF) تماس گرفت مثل این منفصل طبیعی فرم, در که V هر پیوستگی مشمول همه متغیرها داده شده فهرست (یا خودشان, یا آنها انکار), و V یکی و جلد یکسانخوب.

  به عنوان مثال، عبارت DNF است، اما SDNF نیست. اصطلاح SDNF است.

  تعاریف مشابه (با جایگزینی ربط با تفکیک و بالعکس) برای CNF و SKNF صادق است. اجازه دهید عبارت دقیق را بیان کنیم.

  ساده تفکیک تماس گرفت تفکیک یکی یا چندین متغیرها, در این هر یک متغیر مشمول نه بیشتر یکی بار (یا خودش, یا او نفیبرای مثال، عبارت یک تفکیک ساده است،

  ربط طبیعی شکل(KNF) تماس گرفت پیوستگی ساده جدایی ها(به عنوان مثال، عبارت CNF است).

  یک فرم نرمال ربط کامل (PCNF) یک CNF است که در آن هر تفکیک ساده شامل همه متغیرهای یک لیست معین (چه خودشان یا نفی آنها) و به همان ترتیب است.

  مثلاً عبارت SKNF است.

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

  الف) انتقال از DNF به CNF

  الگوریتم این انتقال به این صورت است: ما دو نفی را بالاتر از DNF قرار می دهیم و با استفاده از قوانین De Morgan (بدون لمس کردن رد بالا)، نفی DNF را به DNF کاهش می دهیم. در این حالت باید براکت ها را با استفاده از قانون جذب (یا قانون بلیک) باز کنید. نفی (بالایی) DNF حاصل (باز هم طبق قانون دو مورگان) بلافاصله CNF را به ما می دهد:

  توجه داشته باشید که اگر از عبارت اصلی خارج کنیم، CNF را نیز می توان به دست آورد درفراتر از پرانتز؛

  ب) انتقال از CNF به DNF

  این انتقال به سادگی با باز کردن براکت ها انجام می شود (قانون جذب دوباره استفاده می شود)

  بنابراین، ما DNF دریافت کردیم.

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

  ج) مخفف DNF (یا SDNF) توسط قانون بلیک

  کاربرد این قانون شامل دو بخش است:

  در صورتی که در بین اصطلاحات متمایز در DNF اصطلاحاتی وجود داشته باشد ، سپس به کل تفکیک عبارت را اضافه می کنیم به 1 به 2. ما این عملیات را چندین بار (احتمالاً به صورت متوالی یا همزمان) برای همه جفت‌های ممکن انجام می‌دهیم و سپس جذب عادی را اعمال می‌کنیم.

  اگر عبارت اضافه شده قبلاً در DNF وجود داشته باشد، می توان آن را به طور کامل کنار گذاشت، برای مثال،

  یا

  البته DNF مخفف شده به طور یکتا تعریف نشده است، اما همه آنها دارای تعداد حروف یکسانی هستند (مثلاً DNF وجود دارد ، پس از اعمال قانون بلیک بر روی آن، می توان به DNF معادل این رسید:

  ج) انتقال از DNF به SDNF

  برای مثال، اگر یک عدد ربط ساده یک متغیر را از دست بدهد، z، عبارت را در آن قرار دهید و سپس پرانتز را باز کنید (ما تکرار عبارات منفصل را نمی نویسیم). مثلا:

  د) انتقال از KNF به SKNF

  این انتقال به روشی مشابه مورد قبلی انجام می شود: اگر یک تفکیک ساده، متغیری را از دست داده باشد (به عنوان مثال، z، سپس یک عبارت به آن اضافه می کنیم (این خود تفکیک را تغییر نمی دهد) پس از آن با استفاده از قانون توزیع براکت ها را باز می کنیم:

  بنابراین، SKNF از CNF به دست آمد.

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

  اشکال نرمال توابع منطقی نمایش یک تابع بولی به صورت تفکیک عبارات ربطی اجزای واحد Ki 2.7، شکل نرمال منفصل DNF این تابع نامیده می شود. دقیقاً شامل یکی از همه متغیرهای منطقی است که با یا بدون نفی گرفته شده است، سپس این شکل از نمایش یک تابع، فرم نرمال منفک کامل SDNF این تابع نامیده می شود. همانطور که می بینید، هنگام نوشتن یک تابع SDNF، باید یک تفکیک از تمام مینترم ها ایجاد کنید که تابع مقدار 1 را می گیرد.

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

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

  
  

  سخنرانی 1.xx

  اشکال عادی توابع منطقی

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

  , (2.7)

  تماس گرفت فرم نرمال منفصل(DNF) این تابع.

  اگر همه اصطلاحات ربط در DNF باشند minterms ، یعنی دقیقاً حاوی یکی از همه متغیرهای منطقی باشد که با یا بدون نفی گرفته شده است، سپس این شکل از نمایش تابع نامیده می شود.فرم نرمال منفک کامل(SDNF ) این تابع. به آن SDNF می گویندکامل ، زیرا هر عبارت در تفکیک شامل همه متغیرها می شود.منفصل ، زیرا عملیات اصلی در فرمول تفکیک است. مفهوم "شکل معمولی” به معنای روشی بدون ابهام برای نوشتن یک فرمول است که یک تابع معین را پیاده سازی می کند.

  با در نظر گرفتن موارد فوق، قضیه زیر از قضیه 2.1 به دست می آید.

  قضیه 2. هر تابع بولی(نه یکسان 0) را می توان در SDNF ارائه کرد, .

  مثال 3. اجازه دهید یک تابع داده شده جدول داشته باشیم f (x 1 , x 2 , x 3 ) (جدول 10).

  جدول 10

  			f (x 1 , x 2 , x 3 )

  بر اساس فرمول (2.6) به دست می آوریم:

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

  نمایش تابع بولی به صورت ترکیبی از جمله های منفصل (جزء صفر) D i

  , (2.8)

  تماس گرفت فرم نرمال پیوندی(CNF) این تابع.

  اگر همه اصطلاحات CNF منفصل باشندحداکثر ، یعنی دقیقاً شامل یکی از همه متغیرهای منطقی تابع باشد که با یا بدون نفی گرفته شده است، سپس چنین CNF نامیده می شود.فرم طبیعی ربطی کامل(SKNF) این تابع.

  قضیه 3. هر تابع بولی(با 1 یکسان نیست) ممکن است به SKNF ارسال شود, و چنین نمایندگی تنها است.

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

  لمای شانون . هر تابع بولی f (x 1، x 2، ...، x m) از m متغیرها را می توان به این صورت نشان داد:

  . (2.9)

  لازم به ذکر است که هر دو شکل نمایش یک تابع منطقی (DNF و CNF) از نظر تئوری با قابلیت های خود برابر هستند: هر فرمول منطقی را می توان هم در DNF (به جز صفر یکسان) و هم در CNF (به جز فرمول یکسان) نشان داد. ). بسته به موقعیت، نمایش یک تابع در یک شکل ممکن است کوتاهتر باشد.

  در عمل، DNF اغلب استفاده می شود، زیرا این شکل برای شخص آشناتر است: از دوران کودکی ، او بیشتر به اضافه کردن محصولات نسبت به ضرب مبالغ عادت دارد (در مورد دوم ، او به طور شهودی تمایل دارد پرانتزها را باز کند و در نتیجه به DNF برود).

  مثال 4. برای تابع f (x 1 , x 2 , x 3 ) ارائه شده توسط جدول. 10، آن را در SKNF بنویسید.

  بر خلاف SDNF، هنگام کامپایل SCNF در جدول صدق یک تابع منطقی، باید به ترکیب متغیرهایی که در آن تابع مقدار 0 را می گیرد نگاه کنید و ترکیبی از حداکثر ترم های مربوطه را ایجاد کنید.اما متغیرها باید با وارونگی معکوس گرفته شوند:

  لازم به ذکر است که انتقال مستقیم از SDNF یک تابع به SCNF آن یا برعکس غیرممکن است. هنگام تلاش برای چنین تبدیل‌هایی، نتایج توابعی هستند که برعکس توابع مورد نظر هستند. عبارات توابع SDNF و SCNF را می توان مستقیماً فقط از جدول صدق آن به دست آورد.

  مثال 5. برای تابع f (x 1، x 2، x 3 ) ارائه شده توسط جدول. 10، سعی کنید از SDNF به SKNF سوئیچ کنید.

  با استفاده از نتیجه مثال 2.3 دریافت می کنیم:

  همانطور که می بینید، تحت وارونگی کلی ما SCNF یک تابع منطقی را به دست آوردیم که معکوس تابع به دست آمده در مثال 2.4 است:

  زیرا شامل تمام maxterm هایی است که در عبارت SCNF تابع مورد بررسی وجود ندارد.

  1. با استفاده از ویژگی های عملیات (به جدول 9 مراجعه کنید) هویت ()، مجموع مدول 2 ()، مفهوم ()، به عملیات AND، OR، NOT (در مبنای بولی) می رویم.

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

  3. با استفاده از ویژگی های عملیات منطقی AND و OR (به جدول 9 مراجعه کنید)، شکل عادی (DNF یا CNF) را به دست می آوریم.

  4. در صورت لزوم، به سراغ فرم های کامل (SDNF یا SKNF) بروید. به عنوان مثال، برای به دست آوردن SCNF اغلب باید از ویژگی: .

  مثال 6. یک تابع منطقی را به SKNF تبدیل کنید

  با انجام مراحل الگوریتم بالا به ترتیب، به دست می‌آییم:

  با استفاده از خاصیت جذب به دست می آوریم:

  بنابراین، تابع CNF را به دست آورده ایم f (x 1، x 2، x 3 ). برای به دست آوردن SCNF آن، باید هر تفکیک را که هر متغیری در آن وجود ندارد، دو بار با این متغیر و با نفی آن تکرار کنید:

  2.2.6. به حداقل رساندن توابع منطقی

  از آنجایی که همان تابع منطقی را می توان به عنوان نشان دادساعت فرمول های شخصی و سپس یافتن ساده ترین شکلآر مول که یک تابع بولی را تعریف می کند، مدار منطقی را که تابع بولی را پیاده سازی می کند، ساده می کندبه tion. حداقل فرم l O عملکرد منطقیدر برخی موارد می توانیم یکی را در نظر بگیریم که دارای حداقل تعداد برهم نهی های سرگرم کننده باشدبه پایه، اجازه دادن پرانتز. با این حال، ساختن یک اثر موثر دشوار استل الگوریتم برای چنین کمینه سازی برای به دست آوردن حداقل پرانتزما.

  بیایید یک مسئله کوچک‌سازی ساده‌تر را در سنتز مدارهای ترکیبی در نظر بگیریم، که در آن ما به دنبال حداقل شکل پرانتزی یک تابع نیستیم، بلکه به دنبال حداقل DNF آن هستیم. الگوریتم های ساده و کارآمدی برای این کار وجود دارد.

  روش کواین

  تابعی که باید به حداقل برسد در SDNF نشان داده می شود و تمام عملیات چسباندن ناقص ممکن روی آن اعمال می شود.

  , (2.10)

  و سپس جذب

  , (2.11)

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

  توجه داشته باشید که سمت چپ معادله (2.10) می تواند بلافاصله به روشی ساده تر و واضح تر به حداقل برسد:

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

  لازم به ذکر است که روش کواین کاملاً کار بر است، بنابراین احتمال اشتباه در هنگام تبدیل بسیار زیاد است. اما مزیت آن این است که از نظر تئوری می توان از آن برای هر تعداد آرگومان استفاده کرد و با افزایش تعداد متغیرها، تبدیل ها کمتر پیچیده می شوند.

  روش نقشه کارناو

  روش نقشه های کارنو (جدول) روشی بصری تر، کم کارتر و قابل اعتمادتر برای به حداقل رساندن توابع منطقی است، اما استفاده از آن عملا به توابع 3-4 متغیر، حداکثر 5-6 متغیر محدود می شود.

  نقشه کارنو این یک شکل دو بعدی جدولی برای نمایش جدول صدق یک تابع بولی است که به شما امکان می دهد به راحتی حداقل DNF توابع منطقی را در یک فرم بصری گرافیکی پیدا کنید. هر سلول جدول با مین ترم SDNF تابع در حال مینیمم شدن همراه است، و به گونه ای که هر محور تقارن جدول مربوط به مناطقی است که نسبت به یک متغیر متقابلا معکوس هستند. این ترتیب سلول ها در جدول تعیین شرایط چسبندگی SDNF را آسان می کند (تفاوت در علامت وارونگی تنها یک متغیر): آنها به طور متقارن در جدول قرار دارند.

  جداول حقیقت و نقشه های کارنو برای توابع AND و OR دو خطه متغیرها در شکل نشان داده شده اند. 8. در هر سلول کارت یک مقدار نوشته شده استآ مقدار یک تابع در مجموعه مقادیر آرگومان مربوط به این سلول N رفیق

  الف) و ب) OR

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

  در نقشه کارنو فقط یک عدد 1 برای تابع And وجود دارد، بنابراین نمی توان آن را به چیزی چسباند. عبارت تابع حداقل فقط شامل عبارت مربوط به این 1 خواهد بود:

  f = x y.

  در نقشه کارنو برای تابع OR از قبل سه 1 وجود دارد و می توانید دو جفت چسبنده بسازید که 1 مربوط به عبارت است. xy ، دو بار استفاده می شود. در عبارت تابع minimal، شما باید عبارت‌های مربوط به جفت‌هایی که به هم چسبیده‌اند را یادداشت کنید، همه متغیرهایی که برای این جفت تغییر نمی‌کنند را در آن‌ها بگذارید و متغیرهایی را که مقدار آنها را تغییر می‌دهند حذف کنید. برای چسب افقی می گیریمایکس و برای عمودی y ، در نتیجه ما عبارت را دریافت می کنیم

  f = x + y.

  در شکل شکل 9 جداول صدق دو تابع از سه متغیر را نشان می دهد (آ ) و نقشه های کارنو آنها (ب و ج). تابع f 2 با اولی تفاوت دارد زیرا در سه مجموعه متغیر تعریف نشده است (در جدول این با یک خط تیره نشان داده شده است).

  هنگام تعیین حداقل تابع DNF، از قوانین زیر استفاده می شود. تمام سلول های حاوی 1 در مناطق مستطیلی بسته به نام ترکیب می شوند k-cubes، که در آن k = log 2 K, K مقدار 1 در یک منطقه مستطیل شکل. در این حالت، هر ناحیه باید یک مستطیل به تعداد خانه های 2 باشد k، که در آن k = 0، 1، 2، 3، …. برای k = 1 مستطیل نامیده می شودیکی یک مکعب است و شامل 2 1 = 2 واحد است. برای k = 2 مستطیل شامل 2 است 2 = 4 واحد و نامیده می شوددو مکعبی؛ برای k = 3 منطقه 2 3 = 8 واحد نامیده می شودسه مکعبی ; و غیره واحدهایی که نمی توانند به مستطیل ترکیب شوند را می توان فراخوانی کردصفر مکعب ، که فقط یک واحد دارند (2 0 = 1). همانطور که مشاهده می شود، برای حتیک نواحی می توانند شکل مربع داشته باشند (اما نه لزوما) و اگر فرد باشندک فقط مستطیل ها

  						قبل از میلاد مسیح

  برنج. 9. نمونه ای از نقشه های کارناو برای توابع سه متغیر

  این مناطق می توانند همپوشانی داشته باشند، یعنی سلول های یکسان می توانند وارد مناطق مختلف شوند. سپس تابع DNF حداقل به صورت تفکیک تمام عبارات ربط مربوط به آن نوشته می شود k - مکعب.

  هر یک از مناطق نشان داده شده در نقشه کارنو در یک DNF حداقل با یک ربط نشان داده شده است، تعداد آرگومان هایی که در آن عبارتند ازک کمتر از تعداد کل آرگومان های تابعمتر ، یعنی این عدد برابر است mk . هر پیوند از یک DNF حداقل فقط از آن آرگومان هایی تشکیل شده است که برای منطقه مربوطه نقشه دارای مقادیری هستند یا بدون وارونگی یا فقط با وارونگی، یعنی معنای آنها را تغییر نمی دهند.

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

  برای تابع مطابق نقشه کارناو در شکل. 9،ب ما پیدا می کنیم

  از آنجایی که برای ناحیه بسته بالایی متغیرها x 1 و x 2 دارای مقادیر بدون وارونگی، برای پایین تر x 1 مسائل با وارونگی، و x 3 بدون وارونگی.

  مقادیر تعریف نشده در نقشه در شکل. 9، V را می توان با جایگزینی آن با صفر یا یک بیشتر تعریف کرد. برای این تابع، واضح است که جایگزین کردن هر دو مقدار تعریف نشده با 1 سود بیشتری دارد. در این حالت، دو ناحیه تشکیل می شود که انواع مختلف 2 مکعبی هستند. سپس عبارت حداقل تابع DNF به صورت زیر خواهد بود:

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

  نقشه های Carnaugh را می توان به روش های مختلف ترسیم کرد (شکل 10).

  									x 2 x 3

  a ب

  برنج. 10. روش های مختلف برای به تصویر کشیدن نقشه های Carnaugh
  برای تابعی از 3 متغیر

  اما راحت ترین گزینه برای نقشه های کارناو برای توابع 2-4 متغیر، مواردی هستند که در شکل 1 نشان داده شده اند. 11 جدول، زیرا برای هر سلول نشان داده می شودآ ما همه متغیرها را به صورت مستقیم یا معکوس داریم.

  a ب

  برنج. یازده راحت ترین تصویر از نقشه های Carnaugh
  برای توابع 3 (الف) و 4 (ب) متغیرها

  برای توابع 5 و 6 متغیر، روش نشان داده شده در شکل. 10، V .

  برنج. 12. تصویر نقشه کارناو برای تابعی از 5 متغیر

  برنج. 13. تصویر نقشه کارناو برای تابعی از 6 متغیر

  کارهای مشابه دیگری که ممکن است مورد توجه شما قرار گیرد.vshm>
  9020.		اصل دوگانگی. بسط توابع بولی به متغیرها. فرم‌های عادی متمایز و پیوندی کامل	96.34 کیلوبایت
  	این قضیه ماهیت سازنده ای دارد، زیرا به هر تابع اجازه می دهد فرمولی بسازد که آن را در قالب یک d.n کامل پیاده سازی کند. f. برای انجام این کار، در جدول صدق هر تابع، تمام سطرهایی را که در آن قرار دارند علامت گذاری می کنیم
  6490.		توصیف و به حداقل رساندن توابع منطقی	187.21 کیلوبایت
  	رابطه بین آرگومان های یک تابع و مقادیر آن به صورت کلامی بیان می شود. مثال: یک تابع سه آرگومان وقتی مقداری می گیرد که هر دو یا چند آرگومان تابع برابر باشند. شامل ساخت یک جدول حقیقت حاوی مقادیر تابع برای همه مجموعه‌های مقادیر آرگومان است. در این مثال با استفاده از جدول صدق، ورودی زیر را در قالب DNF به دست می آوریم...
  6707.		طراحی پایگاه داده های رابطه ای مشکلات طراحی در رویکرد کلاسیک اصول نرمال سازی، اشکال عادی	70.48 کیلوبایت
  	پروژه پایگاه داده رابطه ای چیست؟این مجموعه ای از روابط به هم پیوسته است که در آن همه ویژگی ها تعریف می شوند، کلیدهای اولیه روابط مشخص می شوند و برخی ویژگی های اضافی روابط مشخص می شوند که به اصول حفظ یکپارچگی مربوط می شوند. بنابراین طراحی پایگاه داده باید بسیار دقیق و تایید شده باشد. در واقع، یک پروژه پایگاه داده پایه و اساس یک بسته نرم افزاری آینده است که برای مدت طولانی و توسط بسیاری از کاربران استفاده خواهد شد.
  4849.		فرم ها و روش های اجرای توابع حالت	197.3 کیلوبایت
  	اصطلاح «عملکرد» در ادبیات علمی داخلی و خارجی به دور از معنای مشابه است. در اصطلاح فلسفی و جامعه‌شناسی عام، آن را «تجلی بیرونی ویژگی‌های یک شی در یک نظام روابط معین» می‌دانند. به عنوان مجموعه ای از اعمال عادی یا خاص افراد یا ارگان ها
  17873.		تشکیل UUD منطقی برای دانش آموزان کلاس سوم	846.71 کیلوبایت
  	جنبه‌های روان‌شناختی و آموزشی مشکل شکل‌گیری کنش‌های جهانی منطقی در دانش‌آموزان دبستانی روش‌هایی برای ارزیابی شکل‌گیری UUD‌های منطقی. توسعه یک مفهوم برای توسعه فعالیت های آموزشی جهانی در سیستم آموزش عمومی نیازهای اجتماعی جدید را برآورده می کند. مهمترین وظیفه سیستم آموزشی مدرن، شکل گیری فعالیت های آموزشی جهانی UUD است. شکل گیری فعالیت های آموزشی همگانی کلید پیشگیری از مشکلات مدرسه است.
  2638.		پیاده سازی فنی اتصالات منطقی در سیستم های مسدود کننده خودکار	1.04 مگابایت
  	اجرای فنی اتصالات منطقی در سیستم های مسدود کننده خودکار اجرای فنی الگوریتم های کنترل باتری های سه رقمی و چهار رقمی با استفاده از تماس رله و عناصر منطقی گسسته و انتگرال بدون تماس...
  10203.		کاربرد مفهوم رویکرد ریسک گرا در ساخت مدل های ساختاری و منطقی وقوع و توسعه اضطراری	70.8 کیلوبایت
  	تجزیه و تحلیل ریسک عمومی محیط تولید در حال اشباع شدن با سیستم‌ها و فناوری‌های قدرتمند فن‌آوری است که کار انسان را مولد و از نظر فیزیکی دشوارتر، اما خطرناک‌تر می‌کند. ریسک با غیرمنتظره بودن و ناگهانی شروع یک موقعیت خطرناک مشخص می شود. هر روز ما با خطرات متعددی روبرو هستیم، اما بیشتر آنها بالقوه باقی می مانند.تئوری ریسک ارزیابی کمی از تأثیر منفی بر یک فرد و همچنین آسیب به سلامت و زندگی او را ارائه می دهد.
  11576.		مفهوم، انواع و اشکال معاملات. عواقب عدم رعایت فرم مورد نیاز معاملات	49.82 کیلوبایت
  	تشخیص یک معامله به عنوان نامعتبر؛ انواع معاملات نامعتبر. ارزش کاربردی کار دوره در ساده کردن مفهوم تراکنش است، یعنی ارائه عمومی آن به شکلی در دسترس تر.
  6213.		تقریب تابع	3.08 مگابایت
  	اولین مورد شامل جایگزینی یک تابع خاص است که به صورت تحلیلی یا جدولی مشخص شده است با تابع دیگری نزدیک به تابع اصلی اما ساده تر و راحت تر برای محاسبات. به عنوان مثال، جایگزینی یک تابع با یک چند جمله ای به شما امکان می دهد فرمول های ساده ای را برای ادغام و تمایز عددی بدست آورید. جایگزین کردن جدول با یک تابع تقریبی به شما امکان می دهد مقادیر را در نقاط میانی آن به دست آورید. مشکل دوم نیز ایجاد می شود: بازیابی یک تابع در یک بخش خاص از مقادیر تابع داده شده در این بخش در مجموعه ای از نقاط گسسته. پاسخ به این سوال ...
  14058.		تکامل توابع دولت	29.99 کیلوبایت
  	دولت روسیه به عنوان یک پدیده حقوقی قبل از هر چیز باید اجرای هدف دولت و همچنین ویژگی های اصلی قانون اساسی آن را به عنوان یک دولت سکولار اجتماعی فدرال دموکراتیک با شکل حکومت جمهوری جمهوری تضمین کند. هدف اصلی دولت توسط هنر تعیین می شود.