مفهوم "مهندسی-سازنده" زیر را می توان به نمایش توابع بولی با فرمول ها داد. ما فرمول Ф (x 1، ...، xn) را روی برخی از مجموعه‌های ثابت خودسرانه F به عنوان یک "جعبه سیاه"، یک دستگاه خاص، در نظر خواهیم گرفت که تمام مجموعه‌های ممکن از مقادیر متغیرها به ورودی آن وارد می‌شوند. و خروجی مربوط به این مجموعه مقادیر تابع f که با فرمول Ф نشان داده شده است (شکل 6.22).
برای اینکه بفهمیم "جعبه سیاه" چگونه کار می کند، باید فرآیند ساخت فرمول را از زیر فرمول ها جدا کنیم. رسیدن به زیرفرمول های "پایه"، یعنی. عناصر مجموعه F، به "بلوک های ساختمانی" می رسیم، عناصر ساختاری که "جعبه سیاه" از آنها مونتاژ می شود، که تابع f را محاسبه می کند. هر تابع از "پایه" F توسط "گره" مربوطه محاسبه می شود، که به عنوان کوچکترین واحد ساختاری "جعبه سیاه" ما در نظر گرفته می شود و ساختار داخلی آن دیگر تجزیه و تحلیل نمی شود.
مثال 6.22.اجازه دهید یک پایه استاندارد برای مجموعه F انتخاب کنیم. سپس فرمول بر اساس استاندارد، که تابع ~ (معادل) را نشان می دهد، به صورت زیر ساخته می شود:
محاسبه طبق این فرمول (و فرآیند ساخت آن از عناصر پایه استاندارد) را می توان به صورت شماتیک همانطور که در شکل نشان داده شده است نشان داد. 6.23.
متغیر x 1 (به طور دقیق تر، مقدار این متغیر) به ورودی یک عنصر ساختاری به نام اینورتر (شکل 6.24، a) و محاسبه نفی تغذیه می شود. منفی x 1 از خروجی اینورتر حذف می شود، یعنی. تابع x 1، به یکی از ورودی های رابط (شکل 6.24، b)، به ورودی دوم که متغیر x 2 از آن تغذیه می شود، تغذیه می شود. تابع x 1 x 2 در خروجی ربط ظاهر می شود. محاسبه تابع x 1 x 2 را می توان به روشی مشابه ردیابی کرد، هر دوی این توابع به ورودی های جداکننده تغذیه می شوند (شکل 6.24، c)، که از خروجی آن تابع x 1 x 2 ∨ x است. 1 x 2 حذف می شود (این چیزی بیش از مجموع مدول 2: x 1 ⊕ x 2 نیست). و در نهایت این تابع به ورودی اینورتر تغذیه می شود که در خروجی آن تابع ~ (معادل) قبلاً بدست آمده است. #
بنابراین، ما به ایده یک "مدار" می رسیم - یک مدل ریاضی از ماشین حساب یک تابع بولی، که با فرمول خاصی که از عناصر ساختاری مونتاژ شده است، نشان داده شده است، که هر یک از آنها یکی از توابع "اساسی" بولی را محاسبه می کند. در حالت کلی، "مدار" یک عملگر بولی را محاسبه می کند و هر تابع مختصات این عملگر از یکی از خروجی های مدار حذف می شود.
از نظر ریاضی، "طرحواره" به عنوان یک گراف جهت دار از نوع خاصی تعریف می شود که در آن هر دو راس و کمان برچسب گذاری می شوند.
اجازه دهید این نماد را معرفی کنیم: اگر F مجموعه ای از توابع بولی است، آنگاه با F (n) زیرمجموعه F را نشان می دهیم که از همه توابع n متغیر (n≥0) تشکیل شده است.
تعریف 6.14.بگذارید مجموعه ها ثابت شوند: F (توابع بولی) و X (متغیرهای بولی).
نموداری از عناصر عملکردی بر اساس F ∪ X (C Φ E)، یا به سادگی بر اساس F ∪ X منقبض شده است، همچنین یک طرح (F, X) - یک گراف جهت دار با انتهای باز (یعنی یک شبکه) نامیده می شود که هر رأس آن برچسب گذاری شده است. توسط یکی از عناصر مجموعه FU X به طوری که شرایط زیر برآورده شود:
- هر ورودی شبکه با یک متغیر از X یا با مقداری ثابت از F (0) برچسب گذاری می شود.
- اگر یک راس v شبکه با تابع f از n متغیر برچسب گذاری شده باشد (یعنی f∈ F (n))، آنگاه نیم درجه ورودی آن برابر با n است و در مجموعه کمان هایی که وارد راس v می شوند، یک شماره گذاری (یک به یک) به گونه ای داده می شود که هر کمان از 1 تا n شماره گذاری می شود.
اگر مبنای ضمنی باشد، به سادگی می گوییم "طرح". علاوه بر این، اگر مجموعه متغیرها "یک بار برای همیشه" ثابت باشد و هنگام در نظر گرفتن طرح‌های مختلف، فقط مجموعه توابع F را تغییر دهیم، همانطور که انجام دادیم، مفاهیم یک فرمول و برهم نهی را بر روی یک مبنای معین معرفی می‌کنیم. در مورد SFE بر اساس F صحبت خواهد کرد، با فرض هر بار، که به معنی یک بار مجموعه ثابتی از متغیرهای X است، که (اگر این به دقت آسیب نرساند) ذکر نشده است.
اکنون این مفهوم را با استقرا تعریف می کنیم تابع بولی که توسط بالای مدار محاسبه می شود .
تعریف 6.15.بگذارید CFE داده شود اس بر مبنای F ∪ X که مجموعه رئوس آن V است.
- فرض بر این است که هر ورودی CFE تابع بولی را که با آن برچسب گذاری شده است محاسبه می کند (یعنی مقداری متغیر یا ثابت).
- اگر یک راس v ∈ V با یک تابع f ∈ F (n) برچسب گذاری شده باشد، قوس با عدد i (1≤i≤n) که وارد آن می شود از راس ui ∈ V می آید که تابع gi را محاسبه می کند، سپس راس v برهم نهی f (g 1، ...، gn) را محاسبه می کند.
بنابراین، اگر هر راس CFE روی F مقداری تابع را محاسبه کند، ترتیبی که در آن توابع g 1، ...، gn در جای متغیرهای تابع f جایگزین می شوند، در حالت کلی ضروری است. . طبیعی است که یک تابع بولی f در n متغیر را جابجایی بنامیم اگر مقدار خود را تحت یک جایگشت دلخواه متغیرهایش حفظ کند. در این مورد، لازم نیست نگران شماره گذاری کمان های وارد شده به بالای مدار باشیم که با چنین عملکردی مشخص شده اند.
مثال 6.23. SPE را در شکل در نظر بگیرید. 6.25. رئوس v 1 و v 2 ورودی SFE هستند. این رئوس به ترتیب توابع x و y را محاسبه می کنند. سپس راس v 3، و همچنین راس v 4، طبق تعریف 6.15، تابع x | y (سکته مغزی شفر) را محاسبه می کند، و راس v 5 (خروجی شبکه) تابع (x | y) l را محاسبه می کند. (x | y)، که مساوی با حرف ربط x y شناخته می شود.
SPE نشان داده شده در شکل. 6.26 دو خروجی دارد که توابع (x | x) | (y | y) = x ∨ y و (x | y) | (x | y) = x y را محاسبه می کنند.
تعریف 6.16. تابع بولی که توسط CFE محاسبه می شود بر اساس F ∪ X، تابعی است که با هر یک از خروجی های آن محاسبه می شود.
بنابراین، CFE دقیقاً چند تابع بولی، چند خروجی را محاسبه می کند. SFE در شکل. 6.25 یک تابع را محاسبه می کند و SPE در شکل 1. 6.26 - دو.
در حالت کلی، اگر (x 1, ..., x n) مجموعه همه متغیرهایی است که به عنوان برچسب برای ورودی های مدار عمل می کنند. اس بر اساس F ∪ X با m خروجی، CFE اس نمایش یک مکعب بولی را تعریف می کند ب n به مکعب بولی ب m، یعنی عملگر بولی
تبصره 6.10.در برخی موارد، تابع محاسبه شده توسط یک SFE معین تا حدودی متفاوت تعریف می شود، با این فرض که تابعی است که توسط هر رأسی از زیر مجموعه رئوس SFE انتخاب شده محاسبه می شود. به طور خاص، می تواند خروجی باشد. در هر صورت، اجازه دهید ما موافقت کنیم که یک فلش "خروجی" را از رئوس انتخاب شده (به معنای مشخص شده) مدار بکشیم. #
بنابراین، هر مدار از گیت ها تعدادی عملگر بولی را محاسبه می کند، به ویژه اگر تعداد خروجی های مدار برابر با 1 باشد، مقداری تابع بولی را محاسبه می کند.
عکس آن را نیز می توان ثابت کرد: برای هر عملگر بولی، یک SFE را می توان بر اساس F ساخت، که در آن F مجموعه کاملی است که عملگر داده شده را محاسبه می کند.
ما تابع y 1 را در اساس Zhegalkin نشان می دهیم. با استفاده از قوانین دو مورگان، ما دریافت می کنیم
(به یاد بیاورید که مجموع مدول 2 هر تعداد زوج از جمله های مساوی برابر با 0 است).
y 1 = x 1 x 2 ⊕ x 1 x 3 ⊕ x 2 x 3 = x 1 x 2 ⊕ x 3 (x 1 ⊕ x 2).
SFE برای عملگر بولی که در جدول آورده شده است. 6.9، بر اساس Zhegalkin در شکل نشان داده شده است. 6.27.
هنگام طراحی یک SFE، در نظر گرفتن یک پارامتر عددی به نام پیچیدگی آن مفید است.
پیچیدگی SFE تعداد رئوس آن است که ورودی نیستند.
در شکل نشان داده شده است. 6.27 CFE بر اساس Zhegalkin دارای پیچیدگی 5 است.
حال اجازه دهید CFE را برای همان اپراتور بر اساس استاندارد در نظر بگیریم.
طبق جدول (جدول 6.9 را ببینید)، ما SDNF را برای تابع y 2 می سازیم:
y 2 = x 1 x 2 x 3 ∨ x 1 x 2 x 3 ∨ x 1 x 2 x 3 ∨ x 1 x 2 x 3.
نقشه کارنو برای این تابع که در شکل 1 نشان داده شده است. 6.28 نشان می دهد که نمی توان آن را به حداقل رساند (به طور دقیق تر، SDNF نوشته شده در بالا حداقل DNF برای این تابع است). اما شما می توانید از راه دیگری بروید. می توانیم جدول را در نظر بگیریم. 6.9 به عنوان جدولی که تابع بولی جزئی را تعریف می کند y 2 = y 2 (x 1 x 2 x 3 y 1). با به حداقل رساندن این تابع توسط
نقشه کارنو * نشان داده شده در شکل. 6.29، دریافت می کنیم
* در این نقشه، مجموعه هایی را که تابع در آنها مقدار 0 را می گیرد، علامت گذاری کردیم و در سلول های مربوطه صفر قرار دادیم. بنابراین، ما می خواهیم یک بار دیگر توجه را به این واقعیت جلب کنیم که نباید صفرها را با خط تیره اشتباه گرفت: یک خط تیره در سلول نقشه که یک تابع جزئی را مشخص می کند به این معنی است که مقدار تابع در این مجموعه تعریف نشده است. نه 0 است و نه 1
y 2 = x 1 x 2 x 3 ∨ y 1 (x 1 ∨ x 2 ∨ x 3).
CFE بر اساس استاندارد برای عملگر بولی در نظر گرفته شده در شکل نشان داده شده است. 6.30 پیچیدگی این SFE 11 است. توجه داشته باشید که راس محاسبه کننده تابع y 1 یک خروجی نیست.
عملگر بولی در این مثال مجموع دو رقمی (مدول 2) سه جمله یک رقمی را محاسبه می کند. همچنین می توان آن را به عنوان یک جمع کننده باینری یک بیتی - یک بلوک عملکردی یک جمع کننده باینری چند بیتی - برای دو ترم در نظر گرفت. سپس تابع y 1 به عنوان "سیگنال حمل" در مهم ترین بیت تفسیر می شود. در شکل 6.31 "اتصال" سه SFE را نشان می دهد (مانند شکل 6.30) که با کمک آنها مجموع دو عدد باینری سه رقمی محاسبه می شود. ثابت 0 به سومین ورودی جمع کننده برای کم اهمیت ترین بیت داده می شود و "سیگنال حمل" مهم ترین بیت مهم ترین بیت حاصل جمع است که در حالت کلی یک عدد چهار رقمی خواهد بود. .
تبصره 6.11.اگر SFE را بر اساس استاندارد طراحی کنیم و بخواهیم پیچیدگی آن را به حداقل برسانیم، ابتدا باید حداقل DNF مربوطه را بسازیم. در این مورد، می توانیم یک معیار دیگر را در نظر بگیریم که توسط آن خود DNF به حداقل می رسد - تعداد نفی ها. از بین تمام DNF های حداقل (به معنای تعریف 6.6)، باید آنهایی را انتخاب کرد که تعداد وقوع متغیرها در زیر علامت منفی کمترین است. از نقطه نظر پیچیدگی SFE، که بر اساس حداقل DNF ساخته خواهد شد، این بدان معنی است که تعداد "اینورترها" را به حداقل می رساند - رئوس SFE که با تابع نفی برچسب گذاری شده اند.
به عنوان مثال، برای تابع داده شده توسط نقشه کارنو (شکل 6.32)، به هسته متشکل از ایمپلینت های ساده x 1 x 2 x 4 و x 1 x 3 x 4، باید یک ایمپلیکت ساده x 2 x 3 x 4 اضافه کنید. و نه x 1 x 2 x 3 زیرا حاوی نگاتیو نیست.
در فناوری مدرن دستگاه های کنترلی و محاسباتی، مبدل های گسسته، یعنی دستگاه هایی که تعداد مشخصی ورودی و خروجی دارند، جایگاه مهمی را اشغال می کنند. مجموعه سیگنال هایی که به ورودی ها می رسند و از خروجی ها می آیند به مجموعه های محدود شناخته شده تعلق دارند.
کار خود را در شبکه های اجتماعی به اشتراک بگذارید
اگر این کار به درد شما نمی خورد در انتهای صفحه لیستی از کارهای مشابه وجود دارد. همچنین می توانید از دکمه جستجو استفاده کنید
آرانوف ویکتور پاولوویچ. ریاضی گسسته بخش 5. مدارهای DNF و FE.
سخنرانی 28. نمودارهای عناصر عملکردی. مشکلات تجزیه و تحلیل و سنتز
سخنرانی 28. نمودارها از عناصر عملکردی.
مشکلات تجزیه و تحلیل و سنتز
طرح سخنرانی:
1. مفهوم مداری از عناصر عملکردی(FE).
2. مسائل تجزیه و تحلیل و سنتز مدارها از PV.
- مفهوم مدار از PV
در تکنولوژی مدرن، دستگاه های کنترلی و محاسباتی جایگاه مهمی را اشغال می کنندمبدل های گسستهیعنی دستگاه هایی که دارای تعداد مشخصی ورودی و خروجی هستند. مجموعه سیگنال هایی که به ورودی ها می رسند و از خروجی ها می آیند به مجموعه های محدود شناخته شده تعلق دارند. دستگاه ها مجموعه سیگنال های ورودی را به خروجی تبدیل می کنند. مدل ریاضی این گونه وسایل به اصطلاح می باشدنمودارهای عناصر عملکردی(SFE).
به عنوان مثال، مدار الکتریکی سه دیود و مقاومت را که در شکل نشان داده شده است در نظر بگیرید. یکی
برنج. 1. نمودار الکتریکی و نماد آن
در نقاط مدار نشان داده شده در یک دایره، در زمان های مختلف، ممکن است سطح بالا، تقریباً برابر با 5 ولت، یا سطح پایین، تقریباً برابر با صفر، ظاهر شود. در نقطه ای از مدار که با خط تیره مشخص شده است، سطح ولتاژ به طور مداوم پایین نگه داشته می شود.
نقاط علامت گذاری شده به عنوان ورودی و نقطه به عنوان خروجی تفسیر می شوند. عملکرد مدار را می توان به صورت زیر توصیف کرد: اگر همه ورودی ها سطح ولتاژ پایینی داشته باشند، خروجی نیز پایین است، اگر حداقل یکی از ورودی ها دارای سطح ولتاژ بالا باشد، خروجی بالا است. اگر حالتی را با سطح ولتاژ بالا به عنوان یک و با سطح ولتاژ پایین - صفر تعیین کنید، وابستگی خروجی به ورودی ها را می توان با استفاده از یک تابع بولی تنظیم کرد.
بر این اساس مدار فوق را عنصر منطقی «OR» می نامند.
چنین مدارهایی را می توان از لوله های الکترونیکی، سوئیچ های الکترومکانیکی، عناصر پنوماتیکی و غیره ساخت. وابستگی خروجی به ورودی ها را می توان نه تنها به عنوان یک تفکیک، بلکه با استفاده از اتصال، نفی و توابع بولی پیچیده تر توصیف کرد.
ما گیت های منطقی را با وابستگی های متفاوت خروجی به ورودی ها در نظر خواهیم گرفت. این عناصر می توانند به یکدیگر متصل شوند و خروجی برخی از عناصر را به ورودی برخی دیگر تغذیه کنند. در نتیجه، ما SFE را دریافت می کنیم.
تعریف مفهوم SFE را می توان به دو مرحله تقسیم کرد. در مرحله اول، بخش ساختاری این مفهوم آشکار می شود، در مرحله دوم - عملکردی.
من صحنه. اجازه دهید این مرحله را به چند نکته تقسیم کنیم.
1 ... مجموعه محدودی از اشیاء () به نام وجود داردعناصر منطقیهر عنصر دارای ورودی و یک خروجی است. عنصر به صورت گرافیکی همانطور که در شکل نشان داده شده است نشان داده شده است. 2.
2 ... با استقرا، مفهوم را تعریف می کنیمشبکه منطقی به عنوان یک شی که در آن تعداد مشخصی ورودی و تعداد مشخصی خروجی وجود دارد (شکل 3).
الف) مبنای استقرا. یک راس جدا شده را یک شبکه منطقی بی اهمیت می نامند. طبق تعریف، هم ورودی و هم خروجی است (شکل 4).
… …
…
برنج. شکل 2 شکل 3 4
ب) انتقال القایی. این قسمت بر اساس استفاده از سه عملیات است.
من ... عملیات ترکیب شبکه های منفصل. بگذارید و دو شبکه مجزا (بدون عناصر مشترک، ورودی و خروجی) باشند که به ترتیب دارای ورودی و خروجی هستند. اتصال شبکه تئوری مجموعه ها یک شبکه منطقی است که ورودی و خروجی دارد.
II ... عملیات اتصال یک عنصر. اجازه دهید شبکه و عنصر به گونه ای باشد که در خروجی های انتخاب شده متفاوت با اعداد باشد. سپس شکل را شبکه منطقی می نامند که حاصل اتصال عنصر به شبکه است. ورودی ها همه ورودی هستند، خروجی ها همه خروجی های شبکه هستند، به جز خروجی های دارای اعداد و همچنین خروجی یک عنصر. شبکه ورودی و خروجی دارد (شکل 5).
… …
برنج. 6.
برنج. 5
III ... تقسیم عملیات خروجی اجازه دهید یک خروجی با یک شماره در شبکه برجسته شود. سپس شکل را شبکه منطقی می گویند که از تقسیم خروجی به دست می آید. ورودی ها همه ورودی هستند، خروجی ها همه خروجی های شبکه با اعداد 1،...،... و دو خروجی دیگر هستند که از خروجی با شماره شبکه به وجود آمده اند (شکل 6). از این رو دارای ورودی و خروجی است.
3 ... بگذارید حروف الفبا و داده شود.
نمودار عناصر عملکردییک شبکه منطقی با ورودی از حروف الفبا و خروجی از حروف الفبا نامیده می شود که نشان داده می شود.
. (1)
در اینجا چند نمونه از مدارها آورده شده است.
1. اجازه دهید مجموعه از سه عنصر AND (هم ربط)، OR (جداکننده) و NOT (اینورتر) تشکیل شده باشد.
سپس شکل (شکل 6) یک نمودار خواهد بود، زیرا می توان آن را با استفاده از عملیات ساخت I - III .
برنج. 6 شکل 7
2. شکل نشان داده شده در شکل. 7 نیز یک شماتیک است.
II صحنه. تعیین عملکرد مدار.
4 ... اجازه دهید CFE (1) را با سیستم توابع جبر بولی مقایسه کنیم
(2)
همچنین به نامرسانایی این مدار.
مثال. الف) برای طرح، سیستمی داریم که از یک معادله تشکیل شده است
یا.
ب) برای مدار نیز به طور مشابه بدست می آوریم
- اجرای توابع بولی توسط مدارهای FE. مشکلات تجزیه و تحلیل و سنتز
مدارهای PV
کار تجزیه و تحلیل: برای یک SFE معین (1) برای به دست آوردن یک سیستم از معادلات بولی (2).
الگوریتم حل مسئله: دنبال کردن عملیات ساخت شبکه I - III ، توابع خروجی عناصر شبکه را به صورت متوالی محاسبه می کنیم.
مسئله سنتز: برای یک مبنای معین از عناصر عملکردی و یک سیستم دلخواه از معادلات بولی (2)، یک مدار (1) از FE داده شده بسازید که این سیستم معادلات را پیاده سازی می کند.
وجود یک راه حل برای مسئله سنتز توسط قضیه پست تعیین می شود که بر اساس آن سیستم توابعی که FE های اساسی را پیاده سازی می کنند باید کامل باشد. توابع را می توان به عنوان برهم نهی توابع نشان داد و هر مرحله از برهم نهی با ترکیب خاصی از عناصر مطابقت دارد.
مثال. برای عملکرد
(3)
نمودار مربوط به برهم نهی در سمت راست فرمول (3) در شکل نشان داده شده است. هشت
برنج. هشت
مشکل سنتز در این واقعیت نهفته است که برای یک سیستم معین از معادلات بولی، می توان مدارهای FE زیادی را ساخت که این سیستم را پیاده سازی کنند. در این رابطه، مشکل سنتز بهینه مطرح می شود: از بین انواع طرح هایی که یک تابع معین را اجرا می کنند، بهترین را با توجه به یک یا معیار دیگری انتخاب کنید، به عنوان مثال، با کمترین تعداد عناصر. چنین طرح هایی نامیده می شودحداقل
عبارت زیر درست است.
قضیه. الگوریتمی وجود دارد که یک مدار حداقل برای هر سیستم توابع بولی ایجاد می کند.
این الگوریتم برای ساخت مدارهای حداقلی متعلق به کلاس الگوریتم های نوع "بروت فورس" است، زیرا مبتنی بر مشاهده تمام مدارها تا پیچیدگی خاصی است. الگوریتم های جستجوی جامع، به عنوان یک قاعده، بسیار پر زحمت و برای اهداف عملی نامناسب هستند. بنابراین، در زیر یک مسئله ساده‌تر را در نظر می‌گیریم که سیستم معادلات اصلی شامل یک معادله است
و بنابراین مدار مورد نظر یک خروجی دارد.
پیچیدگی مدار حداقل با نشان داده می شود. ما مسئله سنتز را نه برای یک تابع جداگانه، بلکه برای کل کلاس توابع متغیرها در نظر خواهیم گرفت. کیفیت الگوریتم های سنتز با مقایسه توابع به اصطلاح شانون مقایسه می شود. اجازه دهید
- حداقل پیچیدگی طرح هایی که پیاده سازی می کنند، که با استفاده از الگوریتم به دست می آیند.
توابع را توابع شانون می نامند و بدیهی است که
مشکل سنتز یافتن الگوریتمی است که تا حد امکان به آن نزدیک باشد، و به طوری که پیچیدگی الگوریتم به طور قابل توجهی کمتر از پیچیدگی الگوریتم جستجوی جامع باشد. با این فرمول مسئله، نیازی نیست که الگوریتم حداقل مدار را برای هر تابع بیابد، فقط لازم است که ساده ترین مداری که با کمک به دست می آید دارای پیچیدگی باشد که خیلی بیشتر از آن نباشد.
سایر آثار مشابه که ممکن است مورد توجه شما قرار گیرد |
|||
| 9013. | روشها برای سنتز طرحها از FE. دیاگرام های رسیور و جمع کننده باینری | 153.07 کیلوبایت | |
| تئوری کلی سنتز CFE به این نتیجه می رسد که اکثر توابع بولی برای مقادیر بزرگ دارای مدارهای کمینه پیچیده هستند. این بدان معنی است که یک کلاس بسیار باریک از توابع بولی از نقطه نظر سنتز ارزش عملی دارد. | |||
| 5321. | انواع و مقادیر پارامترهای حفاظت خودکار برای عناصر مختلف یک طرح طراحی معین | 526.7 کیلوبایت | |
| برای اطمینان از عملکرد عادی سیستم برق و مصرف کنندگان برق، لازم است در اسرع وقت محل آسیب را از شبکه بدون آسیب شناسایی و جدا کرده و شرایط عملکرد عادی را برای سیستم برق و مصرف کنندگان بازگرداند. | |||
| 5384. | توسعه مدار الکتریکی پایه برای تجزیه و تحلیل عملکرد رمزگشای کلاک برای 4 ورودی و 16 خروجی | 626.63 کیلوبایت | |
| برای بهبود عملکرد انبار نورد ATP، ساختار سازمانی سیستم تعمیر و نگهداری و تعمیر انبار نورد ATP توسعه یافته است و مجموعه ای از تجهیزات برای تشخیص و نگهداری پیشنهاد شده است. وظیفه اصلی عملکرد تاسیسات تعمیر شرکت اطمینان از عملکرد بدون وقفه تجهیزات است. این شامل: پایگاه تعمیر و بازسازی شرکت، انبارها، مغازه ها و بخش های عمومی تاسیسات تعمیر، تجهیزات فن آوری، اعزام. سازمان... | |||
| 1886. | مراحل تجزیه و تحلیل سیستم، اهداف اصلی، اهداف | 27.44 کیلوبایت | |
| تئوری سیستم های بهینه به ما امکان می دهد حدی را که می توان در سیستم بهینه به دست آورد، تخمین زد، آن را با شاخص های سیستم غیربهینه فعلی مقایسه کرد و دریابیم که آیا در مورد مورد بررسی توسعه یک سیستم بهینه توصیه می شود یا خیر. برای فرآیند کنترل خودکار یک سیستم کنترل خودکار، دو مرحله بهینه سازی متمایز می شود: استاتیک و پویا. بهینه سازی استاتیک مسائل ایجاد و پیاده سازی یک مدل فرآیند بهینه و پویا را حل می کند. | |||
| 5123. | توسعه استراتژی های عملکردی | 35.44 کیلوبایت | |
| استراتژی منابع انسانی توابع و ساختار مدیریت کارکردهای مدیریت و نقش آنها در شکل گیری ساختارهای مدیریتی. نوع سلسله مراتبی ساختار مدیریت. | |||
| 20368. | تأثیر ترکیب اجزای دستور العمل و فن آوری ها بر خواص مصرف کننده محصولات کاربردی | 742.05 کیلوبایت | |
| مفهوم تغذیه بهینه توسط علم پزشکی مدرن پذیرفته شده است. این بدان معنی است که از مفهوم تغذیه کافی، زمانی که درشت مغذی ها عمدتاً تنظیم و عادی می شوند - منابع چربی، منابع انرژی، مواد پلاستیکی (لیپیدها، پروتئین ها، چربی ها) به مفهوم تغذیه بهینه، زمانی که طیف مواد مغذی لازم برای فعالیت حیاتی بدن و سایر اجزای جزئی که قبلا نادیده گرفته شده بودند به شدت گسترش می یابد. | |||
| 4706. | روشهای سنتز کربوکسیلات‌های Me | 9.26 مگابایت | |
| ماهیت روش حل کردن اکسید فلزی، هیدروکسید یا کربنات در محلول آبی اسید مربوطه است. محصول با تبخیر محلول قبل از کریستالیزاسیون یا با فیلتر کردن رسوب در صورتی که کربوکسیلات نامحلول یا به طور محدود در آب باشد، جدا می شود. | |||
| 15923. | روش های اساسی برای سنتز پیرازالودیازپین ها | 263.39 کیلوبایت | |
| روش های جدید برای سنتز مشتقات پیرازولودیازپین توسعه استراتژی های سنتز جدید از علاقه قابل توجهی است. مطالعات سیستماتیک و کلی در مورد سنتز مشتقات پیرازولودیازپین انجام نشده است، برخی از مسائل تحت تأثیر بحث و جدل قرار نگرفته یا کاملاً حل نشده باقی می مانند. | |||
| 11978. | تاسیسات فناوری انرژی مبتنی بر اکسیداسیون هیدروترمال آلومینیوم برای تولید برق، گرما، هیدروژن و نانومواد کاربردی | 49.89 کیلوبایت | |
| توسعه بر اساس واکنش اکسیداسیون هیدروترمال آلومینیوم است که در طی آن مقدار زیادی انرژی حرارتی آزاد می شود و اکسیدهای آلومینیوم و هیدروژن تشکیل می شود: l2H2O → lOOH boehmite15H2415. از آب مقطر و پودرهای آلومینیوم در ابعاد میکرون به عنوان معرف اولیه استفاده می شود. نصب KEU10 نصب ETK100 مشخصات فنی نصب ETK100: مقدار پارامتر مصرف آلومینیوم کیلوگرم ساعت 101 مصرف آب در ورودی دستگاه تصفیه آب کیلوگرم ساعت 484 بهره وری برای هیدروژن nm3 110 توان حرارتی ... | |||
| 6605. | سیستم های خبره. طراحی TP به روش سنتز | 11.67 کیلوبایت | |
| بازنمایی انباشت دانش و به روز نگه داشتن آن کار پیچیده ای است که در بخش انفورماتیک به نام مهندسی دانش بررسی می شود. مهندس دانش در توسعه پایگاه دانش - هسته سیستم هایی که هوشمند نامیده می شود - شرکت می کند. اغلب از سیستم های هوشمند برای حل مسائل پیچیده استفاده می شود که پیچیدگی اصلی راه حل ... | |||
اندازه: px
شروع نمایش از صفحه:
رونوشت
1 سخنرانی 2. طرح های عناصر عملکردی (SFE) در یک مبنای خاص. پیچیدگی و عمق طرح. مثال ها. روش برای سنتز SFE از DNP. مدرس - دانشیار Svetlana Nikolaevna Selezneva Lectures on Discrete Mathematics 2. سال اول، گروه 141، دانشکده ریاضیات محاسباتی و سایبرنتیک، دانشگاه دولتی مسکو به نام M.V. سخنرانی های لومونوسوف در سایت
2 نمودار عناصر عملکردی اجازه دهید نمودارهای عناصر عملکردی را بر اساس مشخصی تعریف کنیم. اجازه دهید مجموعه ای از توابع بولی B = (g 1 (x 1، ...، x n1)، ...، gs (x 1، ...، x ns)) P 2، که در آن n 1، به ما داده شود. .. ., ns 0. اجازه دهید این مجموعه را یک پایه بنامیم. توجه داشته باشید که این مفهوم مبنا هیچ ربطی به مفهوم پایه P 2 که در جبر منطق مورد توجه قرار گرفت، ندارد. به عنوان یک قاعده، ما مبنای استاندارد B 0 = (x & y، x y، x) را در نظر خواهیم گرفت.
3 تعریف مداری از عناصر عملکردی مداری از عناصر عملکردی (CFE) در پایه B 0 = (x & y, xy, x) است 1) یک گراف غیر چرخه جهت دار G = (V, E)، هر رأس v V که دارای نیم درجه ورودی d (v ) از دو (d (v) 2) نیست. 2) هر رأس v با نیم درجه ورودی برابر با 0 (d (v) = 0) ورودی (یا ورودی مدار) نامیده می شود و مقداری متغیر بولی x i به آن اختصاص داده می شود. 3) تمام گره های دیگر (به جز ورودی ها) گره های داخلی مدار نامیده می شوند.
4 تعریف مداری از عناصر عملکردی (ادامه) 4) به هر راس v با نیم درجه ورودی برابر با 1 (d (v) = 1) یک عنصر نفی (عملکردی) اختصاص داده می شود. همه این رئوس اینورتر نامیده می شوند. 5) به هر رأس v با نیم درجه ورودی برابر با 2 (d (v) = 2) یک عنصر پیوندی (عملکردی) & یا یک عنصر جدایی (عملکردی) اختصاص داده می شود. تمام رئوسی که عناصر رابط به آنها نسبت داده می شود، رابط نامیده می شوند، تمام رئوس که عناصر جداکننده به آنها اختصاص داده می شوند، منفصل نامیده می شوند.
5 تعریف مداری از عناصر عملکردی (ادامه) 6) علاوه بر این، متغیرهای خروجی مختلف جفتی y 1, ..., y m به برخی از رئوس اختصاص داده شده است. اگر SPE S داده شود که ورودی های آن فقط به متغیرهای x 1, ..., xn و با متغیرهای خروجی y 1, ..., ym اختصاص داده شده باشد، این SPE را با S (x1) نشان می دهیم. ، ...، xn؛ y 1، ...، ym).
6 مثال SFE مثال 1. SFE S (x 1, x 2, x 3; y 1, y 2, y 3):
7 مثال SFE مثال 1. به عنوان یک قاعده، SFEها به صورت S نشان داده می شوند (x 1، x 2، x 3؛ y 1، y 2، y 3):
8 تعیین پیچیدگی SFE پیچیدگی L (S) SFE S تعداد رئوس داخلی این SFE است، یعنی. تعداد عناصر عملکردی در SFE S.
9 پیچیدگی SFE مثال 2. پیچیدگی SFE S:
10 تعیین عمق راس CFE با القاء، عمق d (v) راس v را در CFE S تعیین می کنیم. 1. اساس القاء. هر ورودی v SFE S دارای عمقی برابر با 0 است: d (v) = انتقال القایی. 1) اگر یک قوس از راس v 1 به اینورتر v از CFE S منتهی شود، آنگاه d (v) = d (v 1)) اگر کمان های راس v 1 و v 2 به رابط یا جداکننده v منتهی شوند. از CFE S، سپس d (v) = max (d (v 1)، d (v 2)) + 1. عمق D (S) SFE S حداکثر عمق رئوس آن نامیده می شود.
11 عمق SFE مثال 3. عمق بالای SFE S و عمق SFE S:
12 تعریف عملکرد SFE در هر راس SFE، یک تابع بولی مشخص تحقق می یابد (یا محاسبه می شود). با استقرا، یک تابع بولی تعریف می کنیم که در راس v در CFE S تحقق می یابد. . 2) اگر یک قوس از راس v 1 به اینورتر v منتهی شود و تابع f v1 در راس v 1 تحقق یابد، تابع f v = f v1 در راس v تحقق می یابد. 3) اگر کمان هایی از رئوس v 1 و v 2 به ربط (یا منفصل) v منتهی شوند و توابع f v1 و f v2 به ترتیب در رئوس v 1 و v 2 محقق شوند، در رأس v تابع fv = f v1 و f v2 (به ترتیب fv = f v1 f v2).
13 عملکرد CFE اعتقاد بر این است که CFE S (x 1, ..., xn; y 1, ..., ym) سیستم توابع بولی FS = (f 1, ..., fm) را پیاده سازی می کند. که در رئوس خروجی آن y 1, ..., y m تحقق می یابد.
14 عملکرد SFE مثال 4. توابع بولی که در راس SFE S تحقق می یابند: F S = (x 3, x 1 x 2, x 1 x 2 x 3).
15 برنامه خطی یک برنامه خطی با ورودی های x 1، ...، xn بر اساس B 0 = (x & y، xy، x) دنباله ای است z 1، z 2، ...، zt، که در آن برای هر عدد j، j = 1، ...، t، به این صورت است که 1) یا zj = xi; 2) یا z j = z k برای k< j; 3) либо z j = z k &z l при k, l < j; 4) либо z j = z k z l при k, l < j. Линейная программа последовательно вычисляет значения z 1,..., z t как функции булевых переменных x 1,..., x n.
16 SFE و برنامه های خطی واضح است که محاسبه در SFE را می توان به صورت یک برنامه خطی بازنویسی کرد. برعکس، هر برنامه خطی را می توان در قالب مقداری SFE نشان داد.
17 CFE و برنامه های خطی مثال 5. CFE S مربوط به برنامه خطی z 1 = x 1 & x 2، z 2 = x 3، z 3 = z 1 z 2 است.
18 SFE و ویژگی های آنها طرح های عناصر عملکردی یک مدل محاسباتی هستند. ویژگی های CFE که ما معرفی کرده ایم، جنبه های مختلف کارایی محاسباتی را نشان می دهد. پیچیدگی CFE با زمان محاسبه متوالی مطابقت دارد. عمق CFE مربوط به زمان محاسبات موازی است. حداکثر تعداد رئوس با عمق یکسان در SFE مربوط به تعداد پردازشگرها در محاسبات موازی است.
19 مثال: مجموع دو بیت مثال 6. یک SPE را به صورت استاندارد بسازید که مجموع دو بیت x و y را پیاده سازی کند (محاسبه کند). راه حل. بیایید جدولی از مجموع دو بیت x و y بنویسیم. این مجموع می تواند یک عدد با دو رقم باینری باشد، بنابراین دو متغیر بولی z 0، z 1 را معرفی می کنیم، به طوری که x + y = 2z 1 + z 0: x y z 1 z
20 مثال: مجموع دو بیت راه حل (ادامه دارد). سپس z 0 = x y، z 1 = xy. با در نظر گرفتن x y = (x y) (x y)، SPE را به دست می آوریم: واضح است که L (S 1) = 3 و D (S 1) = 3.
21 SFE در یک مبنای دلخواه مفهوم SFE در یک مبنای دلخواه B P 2 به روشی مشابه معرفی شده است.
22 مثال: مجموع سه بیت مثال 7. CFE را در پایه P2 2 (یعنی از تمام توابع بولی بسته به دو متغیر) بسازید، مجموع سه بیت x، y و z را (محاسبه کنید).
23 مثال: مجموع سه بیت راه حل. مانند مثال 6، جدولی از مجموع سه بیت x، y و z می نویسیم. این مجموع همچنین می تواند عددی با دو رقم باینری باشد، بنابراین دو متغیر بولی u 0، u 1 را معرفی می کنیم، به طوری که x + y + z = 2u 1 + u 0: x y z u 1 u
24 مثال: مجموع سه بیت راه حل (ادامه دارد). سپس u 0 = x y z، u 1 = xy xz yz. با در نظر گرفتن xy xz yz = xy z (x y)، CFE را بدست می آوریم: می بینیم که L (S) = 5 و D (S) = 3.
25 اجرای تابع بولی CFE آیا می توان یک تابع بولی دلخواه (یا سیستمی از توابع بولی) را در پایه B 0 = (x & y, x y, x) پیاده سازی کرد؟ می توان. چگونه می توان این را توجیه کرد؟ مثلا اینجوری زیرا (x & y, x y, x) یک سیستم کامل در P 2 است، یک تابع بولی دلخواه f را می توان با یک فرمول تنها از طریق پیوند، تفکیک و نفی نشان داد. به عنوان مثال، به صورت یک DNF کامل، اگر f 0، و به شکل x & x، اگر f = 0. و سپس، با استفاده از این DNF (فرمول)، SFE مربوطه را بسازید. این روش ساخت CFE برای توابع بولی، روش سنتز DNF نامیده می شود.
26 سنتز SFEها از DNF و بسته به n متغیر، چه پیچیدگی از SFE S از DNF برای تابع بولی f (x 1، ...، x n) بدست می آید؟ یک DNF کامل برای تابع f حداکثر دارای 2 n حرف ربط ابتدایی خواهد بود. هر پیوند ابتدایی پیوند n متغیر یا نفی آنها است.
27 سنتز SFE بر اساس DNF بنابراین، مدار حاوی: n اینورتر برای پیاده سازی تمام نفی متغیرهای x 1, ..., x n خواهد بود. توسط (n 1) ربط برای اجرای هر یک از حداکثر 2 n پیوند ابتدایی در یک DNF کامل. حداکثر (2 n 1) جداکننده برای پیاده سازی تفکیک پیوندهای ابتدایی DNF. دریافت می کنیم که L (S) n + (n 1) 2 n + (2 n 1) n 2 n + n.
28 پیچیدگی یک تابع بولی پیچیدگی L (f) یک تابع بولی f (x 1, ..., x n) در کلاس CFEها حداقل پیچیدگی در بین تمام CFEهایی است که تابع f را اجرا می کنند. بنابراین، قضیه را ثابت کردیم: قضیه 1. برای یک تابع دلخواه f (x 1، ...، x n) P 2، L (f) n 2 n + n درست است.
29 مسائل برای حل مستقل 1. برای یک تابع بولی f (x 1، x 2، x 3) = ()، یک SPE را بر اساس استاندارد پیچیدگی بسازید. برای یک تابع بولی f (x 1، x 2، x 3 ) = ()، یک SPE بر اساس استاندارد پیچیدگی بسازید برای یک تابع بولی f (x 1, x 2, x 3, x 4) = x 1 x 2 x 3 x 4، CFE را در مبنای استاندارد عمق بسازید. ثابت کنید که در مبنای استاندارد L (xy) = 4.
30 ادبیات برای سخنرانی 4 1. Yablonskiy S.V. مقدمه ای بر ریاضیات گسسته. M .: دبیرستان، قسمت پنجم، چ. 2، با Gavrilov G.P.، Sapozhenko A.A. مسائل و تمرینات در ریاضیات گسسته. مسکو: فیزمتلیت، چ. X 1.1، 1.5، 1.7، 1.17، 1.18.
31 پایان سخنرانی 4
سخنرانی: طرح‌های عناصر عملکردی با تأخیر (SPEZ)، خودکارسازی نگاشت‌های انجام‌شده توسط آنها. نمایندگی KAV SFEZ. ساده سازی KAV. تمایز و غیر قابل تشخیص بودن حالات CAV. قضیه مور
سخنرانی: قضیه انسل در مورد تقسیم یک مکعب n بعدی به زنجیره. قضیه ای در مورد تعداد توابع یکنواخت در جبر منطق. قضیه ای در رمزگشایی توابع یکنواخت جبر منطق. مدرس - دانشیار سوتلانا سلزنوا
سخنرانی: ماشین های حالت محدود با خروجی (KAV). توابع خودکار، روش های انتساب آنها. قضیه ای در مورد تبدیل دنباله های تناوبی توسط توابع خودکار. مدرس - دانشیار سوتلانا نیکولائونا سلزنوا
سخنرانی: مجموعه های جزئی مرتب شده (PNS). نمودار CHUM. حداکثر، حداقل، بزرگترین و کوچکترین اقلام. زنجیر و آنتی زنجیره، طول و عرض PLS نهایی. قضیه ای در مورد تجزیه PN به آنتی زنجیره ها.
سخنرانی 2. خواص ضرایب دو جمله ای. محاسبه مجموع و روش تولید توابع (مورد نهایی). ضرایب چند جمله ای برآورد ضرایب دو جمله ای و چند جمله ای. برآورد جمع
سخنرانی: الگوریتم تشخیص کامل بودن در P k. کلاس های تعطیل طبقات توابع حفظ مجموعه ها و حفظ پارتیشن ها، بسته بودن آنها. قضیه کوزنتسوف در مورد کامل بودن تابعی. کلاس ها را از قبل تکمیل کنید.
سخنرانی 2. ترکیبیات. ویژگی های ضرایب دو جمله ای. محاسبه مجموع و روش تولید توابع. ضرایب چند جمله ای برآورد ضرایب دو جمله ای و چند جمله ای. تقریبی
سخنرانی: توابع با ارزش محدود. توابع با مقدار k اولیه. روشهای تعیین توابع با مقدار k: جداول، فرمول‌ها، شکل‌های 1 و 2، چند جمله‌ای. کامل بودن. قضیه کامل بودن سیستم پست. تابع وب.
سخنرانی 3. توالی های تعریف شده توسط روابط عود. معادلات بازگشتی خطی همگن و ناهمگن (LORU و LNRU). راه حل های کلی LORU و LNRU. مدرس - دانشیار سوتلانا سلزنوا
سخنرانی 15. توابع منطق های با ارزش محدود. توابع ابتدایی منطق k-value. روشهای تعیین توابع منطقی با مقدار k: جداول، فرمول‌ها، اشکال I و II، چند جمله‌ای. کامل بودن. مدرس - دانشیار سلزنوا
سخنرانی: توابع منطق های با ارزش محدود. توابع ابتدایی منطق k-value. روشهای تعیین توابع منطقی با مقدار k: جداول، فرمول‌ها، اشکال I و II، چند جمله‌ای. کامل بودن. مدرس - دانشیار سوتلانا سلزنوا
سخنرانی: تابع موبیوس در PLM. تابع موبیوس روی مکعب n بعدی. فرمول وارونگی موبیوس اصل شمول-حذف. مشکل محاسبه تعداد جایگشت-اختلال ها. مدرس - دانشیار سوتلانا سلزنوا
سخنرانی 2. خواص ضرایب دو جمله ای. روش تولید توابع، محاسبه مجموع و اثبات هویت. ضرایب چند جمله ای اصل شمول-حذف. مدرس - دانشیار سوتلانا سلزنوا
سخنرانی: کارکردهای ضروری. سه لم در مورد توابع ضروری. معیار کامل بودن یابلونسکی. معیار کامل بودن اسلوپکی توابع شفر مدرس دانشیار سوتلانا نیکولائونا سلزنوا [ایمیل محافظت شده]
سخنرانی: اعداد ترکیبی پایه. تخمین ها و مجانبی برای اعداد ترکیبی. مدرس - دانشیار سوتلانا نیکولاونا سلزنوا، دانشکده ریاضیات محاسباتی و سایبرنتیک، دانشگاه دولتی مسکو به نام M.V. سخنرانی های لومونوسوف در وب سایت http://mk.cs.msu.su
سخنرانی: ویژگی های ضرایب دو جمله ای. محاسبه مجموع و روش تولید توابع (مورد نهایی). ضرایب چند جمله ای برآورد ضرایب دو جمله ای و چند جمله ای. تخمین برای مجموع دوجمله ای
سخنرانی: ماشین های حالت محدود با خروجی. تبدیل دنباله های تناوبی توسط ماشین های حالت محدود با خروجی. تمایز حالت ها در ماشین های حالت محدود با خروجی. ساده سازی ماشین آلات مدرس سلزنوا
سخنرانی: پوشش مجموعه و پوشش ماتریسی. پوشش گرادیان. لم پوشش گرادیان. تخمین‌هایی برای کاردینالیته مجموعه سایه‌زنی یک مکعب n بعدی. تخمین طول توابع چند جمله ای نرمال
سخنرانی 5. پوشش یک مجموعه و پوشش یک ماتریس. پوشش گرادیان. لم پوشش گرادیان. تخمین‌هایی برای کاردینالیته مجموعه سایه‌زنی مکعب بولی. کران طول برای اشکال عادی چند جمله ای بولی
سخنرانی 3. توالی های تعریف شده توسط روابط عود. معادلات بازگشتی خطی همگن و ناهمگن (LORU و LNRU). راه حل های کلی LORU و LNRU. نمونه مدرس - دانشیار Selezneva
سخنرانی 3. روابط در مجموعه ها. خواص. فرمول شمول-حذف. رابطه هم ارزی رابطه سفارش جزئی مدرس - دانشیار Svetlana Nikolaevna Selezneva سخنرانی هایی در مورد مدل های گسسته.
سخنرانی 4. ویژگی های منطق های چند ارزشی. کلاس تعطیل، پایه کلاس بسته. قضایای یانوف و موچنیک در مورد وجود در منطق های چند ارزشی طبقات بسته بدون پایه و طبقات بسته با قابل شمارش
سخنرانی. توابع استدلال طبیعی (توالی). معادلات بازگشتی خطی همگن و ناهمگن (LORU و LNRU). راه حل های کلی LORU و LNRU. نمونه مدرس - دانشیار سوتلانا سلزنوا
سخنرانی: عدد رنگی یک نمودار. معیار نمودار دو رنگ قضایای کرانهای بالا و پایین برای عدد رنگی یک نمودار. مدرس - دانشیار Svetlana Nikolaevna Selezneva سخنرانی هایی در مورد مدل های گسسته.
سخنرانی: نمودارها و شبکه ها. تخمین تعداد شبه نگارهای با یال q. تخمین تعداد درختان با لبه های q. نمودارهای مسطح فرمول اویلر برای نمودارهای مسطح. بیشترین تعداد یال در نمودارهای مسطح. غیر مسطح بودن
سخنرانی 1. ترکیبیات. جایگذاری، جایگشت، قرارگیری با تکرار، ترکیب، ترکیب با تکرار. تعداد آنها مدرس - دانشیار سوتلانا نیکولائونا سلزنووا گروه سایبرنرتیک ریاضی
سخنرانی: توالی. معادلات بازگشتی خطی همگن و ناهمگن. راه حل های کلی معادلات همگن و ناهمگن بازگشتی خطی. مدرس - دانشیار سوتلانا نیکولائونا سلزنوا
سخنرانی 8. رنگ آمیزی. هم ارزی رنگ ها نسبت به گروه. توابع تولیدی یک سری شمارش برای اشکال و یک سری شمارش برای توابع. قضیه پولیا مدرس سلزنوا سوتلانا نیکولایونا
سخنرانی: رنگ آمیزی. هم ارزی رنگ ها با توجه به یک گروه جایگشت. قضیه پولیا (مورد خاص). توابع تولیدی یک سری شمارش برای اشکال و یک سری شمارش برای توابع. قضیه
سخنرانی 2. اشکال عادی ربطی. ضمنی، ضمنی ساده یک تابع. تابع CNF مخفف جبر منطق. روش های ساخت یک CNF مخفف. مدرس سلزنوا سوتلانا نیکولایونا [ایمیل محافظت شده]
مدل‌های ریاضی و روشهای سنتز منطقی VLSI پاییز 2015 سخنرانی 4 طرح سخنرانی بهینه‌سازی منطقی مدارهای منطق ترکیبی روشهای مختلف نمایش توابع جبر منطقی (FAL)
سخنرانی: اتوماتای محدود غیر قطعی (NFA) بدون خروج. قضیه ای در مورد انطباق طبقات مجموعه کلمات پذیرفته شده توسط خودکارهای قطعی محدود و غیر قطعی متناهی. روش
سخنرانی 1. نمونه. جایگذاری، جایگشت، قرارگیری با تکرار، ترکیب، ترکیب با تکرار، تعداد آنها. مثال ها. مدرس - دانشیار سوتلانا نیکولائونا سلزنوا سخنرانی در مورد دوره گسسته
سخنرانی 1. اشیاء ترکیبی: انتخاب، ترتیب، جایگشت، ترتیب با تکرار، ترکیب، ترکیب با تکرار، تعداد آنها. اعداد ترکیبی: فاکتوریل، فاکتوریل کاهنده، دو جمله ای
سخنرانی 4 طرح هایی از عناصر عملکردی 1. تعاریف اساسی اول از همه، لازم است ترکیب را در نظر بگیرید. یک تابع را می توان به عنوان یک "جعبه سیاه" در نظر گرفت که یک ورودی و یک خروجی دارد. اجازه دهید
سخنرانی 2. الگوریتم تشخیص کامل بودن در P k. قضیه کوزنتسوف. کلاس های تعطیل کلاس های توابع حفظ مجموعه کلاس های توابع حفظ تقسیم کلاس ها را از قبل تکمیل کنید. مدرس دکترای علوم فیزیک و ریاضی سلزنوا
سخنرانی 3. چند جمله ای Zhegalkin. روشهای ساخت چند جمله‌ای ژگالکین برای یک تابع. مفهوم خطی تابع. فرم نرمال پیوندی خطی (LCNF). یافتن تمام مفاهیم خطی تابع. معاینه
سخنرانی 2. تولید توابع: محاسبه مجموع ترکیبی و اثبات هویت ها، شمارش اشیاء ترکیبی. اصل شمول-حذف. شمارش تعداد جایگشت-اختلال ها. مدرس -
سخنرانی 5. نمودارها. رنگ آمیزی نمودار عدد رنگی نمودار. معیار نمودار دو رنگ کران های بالایی برای عدد کروماتیک یک نمودار. مدرس دکترای علوم فیزیک و ریاضی سلزنوا سوتلانا نیکولاونا [ایمیل محافظت شده]سخنرانی ها
سخنرانی: اتوماتای محدود (KA) بدون خروج (تشخیص دهنده های خودکار محدود). نمودارهای انتقال مجموعه های خودکار (زبان). لغت در مورد ویژگی های مجموعه های خودکار. نمونه ای از مجموعه غیر اتوماتیک. مدرس
سخنرانی 1. توابع با مقدار محدود. توابع با مقدار k اولیه. روشهای تعیین توابع با مقدار k: جداول، فرمول‌ها، شکل‌های 1 و 2، چند جمله‌ای. کامل بودن. قضیه کامل بودن سیستم پست. تابع وب.
سخنرانی 7. مشکل انتخاب مسیرها و مورد خاص آن مشکل توزیع پروازها در روز است. مدل نموداری برای مسئله توزیع پرواز عدد رنگی نمودار. معیار دو رنگ بودن نمودار
دوره "مبانی سایبرنتیک" ویژه دانشجویان رشته تخصصی 02/01/09/01 (ریاضی و نرم افزار کامپیوتر) 1. اطلاعات عمومی (بار مطالعه، اشکال کنترل و ...). دوره است
سخنرانی 6. نمودارها. ویژگی های ارثی گراف ها تخمین تعداد یال ها در نمودارهای دارای ویژگی ارثی. نمودارهای افراطی بیشترین تعداد یال در نمودارهای مسطح و بدون مثلث با یک داده شده
Math-Net.Ru پرتال ریاضی همه روسی D. S. Romanov، روشی برای سنتز مدارهایی که به راحتی قابل آزمایش هستند و آزمایش‌های تک بررسی با طول ثابت را می‌پذیرند، Diskr. مت، 1393، جلد 26، شماره 2،
سخنرانی: ماشین های حالت محدود بدون خروجی، قطعی و غیر قطعی. قضیه ای در مورد همزمانی طبقات مجموعه کلمات پذیرفته شده توسط خودکارهای قطعی و غیر قطعی محدود. روش
کار عملی 2 ساخت اشکال عادی یک تابع منطقی هدف کار: یادگیری ساختن فرم های ربطی، منفصل، نرمال کامل یک تابع منطقی محتوای کار: پایه
سمینار پیچیدگی توابع بولی سخنرانی 1: مقدمه A. Kulikov Computer Science Club در POMI http://compsciclub.ru 09/25/2011 09/25/2011 1/26 طرح سخنرانی 1 توابع بولی 2 مدارهای بولی 3 تقریبا
کار عملی 1 تجزیه و تحلیل و سنتز سیستم‌های کنترل منطقی و رله‌ای مقدمه دستگاه‌های اثر گسسته ساخته شده بر روی عناصر ریزپردازنده‌های هیدرو، پنومو و الکترواتوماتیک و کنترل
سخنرانی: عبارات منظم و مجموعه های منظم. قضیه کلین در مورد همزمانی طبقات مجموعه های خودکار و مجموعه های منظم. مدرس - دانشیار Svetlana Nikolaevna Selezneva سخنرانی در مورد ریاضیات گسسته
سخنرانی 3 جبرهای بولی و توابع بولی جبرهای بولی مفهوم سیستم های جبری سیستم جبری یا ساختار جبری مجموعه ای از نمادهای یک الفبای خاص (پشتیبانی) با یک معین
سخنرانی 5. نمودارها. نمونه هایی از کاربرد نمودارها مشکل حمل و نقل جریان شبکه، قضیه فورد و فولکرسون در مورد حداکثر جریان شبکه. الگوریتم ساخت حداکثر جریان در شبکه. مدرس
سخنرانی: نمودارها نمونه هایی از کاربرد نمودارها مشکل حمل و نقل جریان شبکه، قضیه فورد و فولکرسون در مورد حداکثر جریان شبکه. الگوریتم ساخت حداکثر جریان در شبکه. مدرس -
درس 8 به یاد بیاورید که برای مجموعه های دلخواه A و B مجموعه های A B = (x x A و x B) وجود دارد. (تقاطع A و B) A B = (x x A یا x B); (اتحاد A و B) A \ B = (x x A و x / B) (تفاوت A و B).
سخنرانی 7. اعداد رمزی. کران بالایی برای عدد رمزی. کران پایین برای عدد رمزی. مدرس سلزنوا سوتلانا نیکولایونا [ایمیل محافظت شده]دانشکده CMC، دانشگاه دولتی مسکو به نام M.V. سخنرانی های لومونوسوف در وب سایت http://mk.cs.msu.ru
سخنرانی: نمودارها مفاهیم اساسی. نمودارهای متصل درختان. درخت پوشا. تعداد رئوس آویزان در درخت پوشا. مدرس - دانشیار Svetlana Nikolaevna Selezneva سخنرانی هایی در مورد مدل های گسسته. استاد،
سخنرانی 11. طرح های بولی. ریاضیات گسسته، HSE، دانشکده علوم کامپیوتر (پاییز 2014 بهار 2015) منظور ما از یک مدار بولی در متغیرهای x 1, ..., x n دنباله ای از توابع بولی g است.
تایید شده معاون رئیس در امور علمی Yu. A. Samarskiy 10 ژوئن 2008 برنامه و وظایف برای دوره ساختارهای گسسته در جهت 010600 دانشکده FIET گروه تجزیه و تحلیل داده ها دوره دوم ترم 4 دو
لومونوسوف دانشگاه دولتی مسکو دانشکده ریاضیات محاسباتی و سایبرنتیک S. A. Lozhkin عناصر نظریه سنتز سیستم های کنترل گسسته مسکو 2016 فهرست مطالب
سخنرانی: ویژگی های ارثی نمودارها. نمودارهای افراطی اعداد رمزی مدرس - دانشیار سوتلانا نیکولاونا سلزنوا، دانشکده ریاضیات محاسباتی و سایبرنتیک، دانشگاه دولتی مسکو به نام M.V. سخنرانی های لومونوسوف در وب سایت http://mk.cs.msu.su ارثی
سخنرانی: عملیات روی مجموعه های خودکار محدود. مکمل، اتحاد، تقاطع، محصول و تکرار مجموعه های خودکار، خودکار بودن آنها. مدرس - استادیار سوتلانا نیکولاونا سلزنوا سخنرانی ها
وزارت ارتباطات و اطلاع رسانی فدراسیون روسیه آکادمی دولتی مخابرات و انفورماتیک پوولژسکایا گروه ریاضیات عالی تایید شده توسط شورای روشی PSATI در 29 مارس 2002
سخنرانی 5. رنگ آمیزی لبه های نمودار. شاخص رنگی نمودار. شاخص رنگی نمودارهای دوبخشی. مرزهای بالا و پایین برای شاخص رنگی یک نمودار. مدرس سلزنوا سوتلانا نیکولایونا [ایمیل محافظت شده]
Math-Net.Ru پورتال ریاضی همه روسی NP Red'kin، در مدارهایی که آزمایش‌های کوتاه تشخیصی تکی را می‌پذیرند، Diskr. Mat., 1989, جلد 1, شماره 3, 71 76 استفاده از همه روسی
منطق ریاضی (1) وظایف تمرین های عملی 1. جبر گزاره ها یک گزاره کمیتی است که می تواند به دو معنا باشد: درست و نادرست. جملات به زبان لاتین بزرگ نشان داده شده است
نمودارهای عملکردی (FS) برای تبدیل اطلاعات منطقی طراحی شده اند. اطلاعات اولیه که به صورت سیگنال های گسسته کدگذاری می شوند، به ورودی های مدار وارد می شوند. `x n... سپس این اطلاعات پردازش شده و به صورت گسسته از خروجی های مدار خوانده می شود در متر(n، m- تعداد ورودی ها و خروجی های آن). FS هایی را در نظر بگیرید که در منطق دو مقداری عمل می کنند و یک خروجی دارند ( متر= 1). تبدیل اطلاعات در آنها را می توان به عنوان تابعی از جبر منطق مشخص کرد در=f(x n). به جای عناصر رله در FS، از عناصر عملکردی (FE) استفاده می شود که به عنوان یک قاعده، توابع منطقی ابتدایی را اجرا می کنند.
تعریف.تحلیل و بررسیساخت فرمولی برای جبر منطق (در صورت لزوم جدول صدق آن) برای یک FS معین نامیده می شود.
برای ساخت یک فرمول طبق یک طرح داده شده، لازم است که رابطه بین FE در FS به شکل جایگزینی در توابع ابتدایی مربوطه نشان داده شود. فرض بر این است که پردازش اطلاعات در مراحلی از ورودی تا خروجی انجام می شود. در مدارهای واقعی، از عناصر اضافی برای اطمینان از هماهنگی زمانی عملکرد همه FS استفاده می شود.
تجزیه و تحلیل FS را می توان به دو روش انجام داد - از ورودی به خروجی و از خروجی به ورودی. بیایید روش اول را با استفاده از نامگذاری های اضافی برای اتصالات مدار میانی در نظر بگیریم.
مثال 1.(&، Ú، Ø) به عنوان FE در نظر گرفته می شوند. FE را تجزیه و تحلیل کنید، ساختار فیزیکی آن در شکل 1.19 آورده شده است.
راه حل.با تعیین اتصالات میانی PV همانطور که در شکل نشان داده شده است، سیگنال های مربوط به آنها را مرحله به مرحله تعیین می کنیم. . در این حالت از ورودی های مدار به خروجی آن می رویم.
شکل 1.19
مرحله 1. آر=`y، Q = z.
گام 2. ایکس=ایکس&آر= ایکس&y، P=ایکس& y، W=پ&س= ایکس&y&`z.
مرحله 3. Y=ایکس&z=ایکس&y& z, U=پ&z = ایکس&y&z.
مرحله 4. ز = YÚ U=ایکس&y&zÚ ایکس&y&z.
مرحله 5. اف = زÚ دبلیو=ایکس&y& zÚ ایکس&y&zÚ ایکس&y&z.
بنابراین، FS در نظر گرفته شده فرمول زیر را از جبر منطق پیاده سازی می کند:
اف(ایکس,y,z) = ایکس&y&zÚ ایکس&y&zÚ ایکس&y&z.
فرمول یافت شده SDNF است. بردار مقادیر صدق آن به شکل (00000111) است. .
بسته به داده های اولیه، از جمله وظایف سنتز (طراحی) FS را می توان تشخیص داد:
1) سنتز مدارها طبق فرمول های داده شده،
2) سنتز مدارها برای توابع داده شده.
تعریف.با سنتز PS طبق فرمول داده شدهساخت ساختار FS مربوط به یک فرمول معین از جبر منطق نامیده می شود.
حل چنین مسائلی بر اساس الگوریتم معکوس روش تجزیه و تحلیل انجام می شود. همانطور که در بخش 1.7 ذکر شد، ساختار فرمول های بولی تنها به سیستم هایی با اتصالات موازی و متوالی عناصر اجازه می دهد که به صورت هم شکل نگاشت شوند. بنابراین، FS که با فرمول مربوطه هم شکل است، باید فقط حاوی ترکیباتی از این نوع باشد.
تعریف.با سنتز یک PS برای یک تابع معینساختن یک نمودار ساختاری نامیده می شود که تابع معینی از جبر منطق را اجرا می کند.
از آنجایی که نمایش توابع توسط فرمول ها مبهم است، این مشکل یک راه حل غیر منحصر به فرد دارد. همانطور که در مورد مدارهای رله، مدارهای بهینه FS هستند که از حداقل تعداد PV و اتصالات بین آنها تشکیل شده است. چنین FS را می توان با استفاده از فرمول هایی با حداقل تعداد متغیر به دست آورد.
در مورد PC، ما به طور جداگانه فرمول هایی را در نظر می گیریم که در کلاس فرم های نرمال بهینه هستند (که برابر با حداقل اشکال مربوطه هستند)، و همچنین فرمول های کاملاً بهینه به دست آمده از حداقل اشکال نرمال با کاهش بیشتر آنها با استفاده از قوانین جبر منطقی. . روش های بدست آوردن فرمول های بهینه مانند مدارهای رله است. مثال 1 FS را در نظر می گیرد که تابع (00000111) را پیاده سازی می کند. . این FS بهینه نیست، زیرا فرمول مربوطه SDNF را توصیف می کند اف = x`y z Ú x y zÚ x y`zکه حداقل نیست. با به حداقل رساندن آن، یک MDNF به شکل زیر دریافت می کنیم: اف = x yÚ x z.با FS در شکل 1.20 مطابقت دارد.
شکل 1.20
اگر قانون توزیع را برای MDNF اعمال کنیم، فرمولی با متغیرهای حتی کمتر بدست می آوریم: f = ایکس(yÚ z). برای این تابع، با MCNF مصادف شد. یک طرح کاملاً بهینه با آن مطابقت دارد.
شکل 1.21
بدیهی است که این طرح بسیار ساده تر از طرح اصلی است (شکل 1.19). از آنجایی که سنتز FS بهینه به ساخت فرمول های حداقل کاهش می یابد، طرح های بهینه در سایر پایه ها نیز به روشی مشابه ساخته می شوند. مشابه قوانین توزیعی اول و دوم جبر منطق برای اشکال شفر و وب را می توان با جایگزین کردن در این قوانین به دست آورد:
&(ایکس,y)= Ø ½ ( ایکس,y) = ¯ (Ø ایکس,Ø y);
Ú ( ایکس,y)= ½ (Ø ایکس, Ø y) =Ø ¯ ( ایکس,y).
مثال 2.یک FS بسازید که یک جمع کننده باینری یک بیتی از دو عدد را با استفاده از FE مربوط به پایه (Ø, ¯) و همچنین در پایه (¯) پیاده سازی کند.
راه حل.اجازه دهید اعداد باینری یک بیتی را که از طریق (( ایکس,در). خروجی باید مجموع آنها در سیستم باینری باشد. اگر x = 1، y = 1، سپس S = 2 10 = 10 2 بنابراین برای نمایش آن در حالت کلی باید از دو علامت باینری استفاده کرد و FS باید دو خروجی داشته باشد. بیایید آنها را نشان دهیم f(مهمترین رقم حاصل جمع) و g(کم اهمیت ترین جزء). جداول حقیقت توابع f (ایکس,در),g(ایکس,در):
| ایکس | y | f(ایکس,y) | g(ایکس,y) |
ما SVNF توابع را در پایه (Ø, ¯) می سازیم. fدارای یک واحد در بردار صدق است، بنابراین شکل آن از یک مؤلفه تشکیل شده است: f= ¯ (Ø x، Ø در). کارکرد g SVNF به شکل زیر است: g=د(¯( ایکس,Ø در),¯(Ø ایکس,در)). این فرم ها حداقل هستند. هنگام ترکیب ورودی عناصر، نمودار عملکردی را می توان به صورت زیر نشان داد:
شکل 1.22
در مثال مورد بررسی، ساده کردن اشکال عادی وب با استفاده از قوانین جبر منطقی غیرممکن است. در یک تابع تک تابعی (¯) FS، با استفاده از جایگزینی Ø به دست می آوریم ایکس= ¯ ( ایکس,ایکس). مدار مربوطه در شکل 1.23 نشان داده شده است.
شکل 1.23
وظایف
1. با استفاده از FE (&, Ú, Ø) بهینه در کلاس فرم‌های معمولی و FS کاملاً بهینه که توابع زیر را اجرا می‌کنند بسازید:
آ) ( ایکس® y)Å zy؛ ب) ( ایکسÅ y)|z، v) xy® yz;G) ایکس|(yÚ z)؛ ه) ایکس®( y® z) ;
f) (10011101)؛ g) (01101011)؛ h) (111010111111110) .
2. با استفاده از توابع FE (Ú, Ø) FS 1.a) -g) بسازید.
3. با استفاده از توابع FE (&, Ø) FS 1.a) -g) بسازید.
4. یک FS بسازید که یک جمع کننده باینری یک بیتی را با استفاده از یک FE به شکل زیر پیاده سازی کند (مثال 2):
الف) (&، Ú، Ø)، ب) (Ú، Ø) , ج) (&، Ø)، د) ( x | y} .
5. با کمک FE (&, Ú, Ø) FS دستگاه های زیر را بسازید:
الف) یک مبدل با ورودی های باینری ( ایکس,در) و خارج شوید fکه به این صورت عمل می کند: هنگام تغذیه x = 0 در خروجی f =در، و هنگام سرو x = 1 در ورودی f =`y;
ب) یک دستگاه انتخابی با ورودی های باینری ( ایکس,در) و خروجی ها f 0 , f 1 , f 2 , f 3، که در ورودی ترکیبی از مقادیر را می پذیرد ( x y) به عنوان یک عدد باینری من، در محدوده 0 تا 3 قرار دارد. مقادیر خروجی ها برای هر کدام منبه شرح زیر: f i= 1 و بقیه f j= 0، (0 £ j 3 پوند، j¹ من).
6. آیا می توان مجموعه توابع زیر را مبنای ساخت FS قرار داد:
الف) (1001)، (10001110)،
ب) (0101)، (1011)، (1101)،
ج) (1010)، (01110001)؟
پاسخ را توجیه کنید.
7. نمونه هایی از توابع کنترلی را ذکر کنید که FS آن را نمی توان تنها از FE از نوع (®) ساخت.
8. مثال هایی از توابع کنترلی که FS آن ها را نمی توان تنها از FE از نوع (M, º) ساخت.
9. Dana FS از FE (&, Ú, Ø).
شکل 1.24
آیا می توان با تبدیل های معادل از آن حذف شد:
الف) همه عناصر (Ø)؟
ب) همه عناصر (&)؟
ج) همه عناصر (Ú)؟
10. FS را از FE (&, Ú, Ø)، نشان داده شده در شکل 1.25 بهینه کنید.
شکل 1.25
ساخت FS:
الف) بهینه در کلاس اشکال عادی و
ب) کاملا بهینه
31. نمودار عناصر عملکردی، قوانین ساخت و عملکرد، روش سنتز SFE، بر اساس SDNF و SKNF.
تعریفتعریف.یک عنصر تابعی یک مدل ریاضی از مبدل گسسته ابتدایی است که طبق یک قانون خاص، سیگنال هایی را که در ورودی به آن می رسد به سیگنال در خروجی مبدل تبدیل می کند. از عناصر عملکردی، با کمک برخی قوانین، می توان مدل هایی ساخت که از نظر ساختار و عملکرد پیچیده تر هستند - نمودارهایی از عناصر عملکردی. در این مدل ها سیگنال های ورودی و خروجی با کاراکترهای 0 و 1 کدگذاری می شوند.
قوانین ساخت و سازبرای بدست آوردن SFEهای پیچیده از نمونه های ساده تر، عملیات تقسیم ورودی یا خروجی مدار، اتصال عنصر عملکردی به مدار و اتصال عنصر عملکردی به ورودی یا خروجی مدار به صورت متوالی اعمال می شود. این عملیات شبیه قوانین به دست آوردن یک فرمول پیچیده از موارد ساده تر با استفاده از برهم نهی است.
سنتز SFE.از آنجایی که تفکیک، ربط و نفی یک سیستم کامل را در کلاس تشکیل می دهند آر 2، سپس هر تابع بولی از nآرگومان ها را می توان توسط مداری از عناصر عملکردی - جداکننده ها، اتصال دهنده ها و اینورترها - با nورودی و یک خروجی برای انجام این کار، می‌توانید به عنوان مثال، این تابع بولی را از طریق SDNF یا SKNF بیان کنید و سپس فرمول حاصل را به شکل مداری از عناصر عملکردی «سنتز» کنید و به‌طور متوالی عملیات تقسیم، اتصال و اتصال بالا را اعمال کنید.
32. روش سنتز SFE، بر اساس اجرای فشرده همه اتصالات با استفاده از یک چند قطبی جهانی، پیچیدگی مدارهای حاصل.
تعریف... تابع آرگومان اگر به هر مجموعه عددی اختصاص دهد، تابع بولی (یا تابع بولی) نامیده می شود.
برای تعریف توابع بولی، از جداول، بردارها، فرمول ها و نمودارها استفاده می کنیم. اجازه دهید نماد زیر را در نظر بگیریم: مجموعه ای از همه مجموعه ها، جایی است که.
تعریف.یک عنصر تابعی یک مدل ریاضی از مبدل گسسته ابتدایی است که طبق یک قانون خاص، سیگنال هایی را که در ورودی به آن می رسد به سیگنال در خروجی مبدل تبدیل می کند. از عناصر عملکردی، با کمک برخی قوانین، می توان مدل هایی ساخت که از نظر ساختار و عملکرد پیچیده تر هستند - نمودارهایی از عناصر عملکردی. در این مدل ها سیگنال های ورودی و خروجی با کاراکترهای 0 و 1 کدگذاری می شوند.
روشی برای سنتز SFE، بر اساس اجرای فشرده همه پیوندها با استفاده از یک چند قطبی جهانی. این روش همچنین مبتنی بر نمایش یک تابع در قالب SDNF است، اما به دلیل اجرای فشرده تر اتصالات، به فرد اجازه می دهد مدارهای پیچیده تری بسازد. تجزیه یک تابع در SDNF می تواند شامل ربط هایی باشد که فاکتورهای مشترکی دارند. اگر دو چنین پیوندهای ربط با یک مدار فرعی در یک بلوک پیاده سازی شوند، آنگاه به حداقل یک ربط کمتر از قبل نیاز دارد، با اجرای مستقل همه ربط ها با اولین روش سنتز. اجرای فشرده از تمام پیوندهای ممکن طول nرا می توان با استفاده از یک چند قطبی جهانی ساخته شده استقرایی، که دارای nورودی ها و 2 n خروجی که در آن n = 1،2،3، ... مزایای روش به ویژه زمانی قابل توجه است که یک مدار نیاز به پیاده سازی سیستمی از چندین تابع بولی دارد. در این حالت، می توان آن خروجی های چندقطبی جهانی را که با پیوندهای موجود در SDNF توابع سیستم داده شده مطابقت دارند، تقسیم کرد و سپس از میان جداکننده ها عبور داد. این امر باعث می‌شود که با اتصال‌دهنده‌های کمتری نسبت به زمانی که هر یک از عملکردهای یک سیستم به‌طور مستقل توسط زیرمدار خودش پیاده‌سازی می‌شد، به نتیجه برسیم.
پیچیدگی چنین چند قطبی است L() =.
اگر مدار دروازه ای Σ دقیقاً حاوی rعناصر عملکردی، سپس می گویند که پیچیدگی دارد rو آن را به صورت مساوات بنویسید L(Σ) = r.
| " |
