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

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

یوتیوب دانشگاهی

• 1 / 5

  فرمول ها در KNF:

  ¬ A ∧ (B ∨ C) ، (\ displaystyle \ neg A \ wedge (B \ vee C) ،) (A ∨ B) ∧ (¬ B ∨ C ∨ ¬ D) ∧ (D ∨ ¬ E)، (\ سبک نمایش (A \ vee B) \ wedge (\ neg B \ vee C \ vee \ neg D) \ wedge ( D \ vee \ neg E)) A ∧ B. (\ displaystyle A \ wedge B.)

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

  ¬ (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)، (\ سبک نمایش (A \ vee C) \ گوه (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) \ گوه ((\ neg Y \ فلش راست Z) \ فلش راست \ neg X).)

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

  F = (¬ X ∨ Y) ∧ (¬ (¬ Y → Z) ∨ ¬ X) = (¬ X ∨ Y) ∧ (¬ (¬ ¬ Y ∨ Z) ​​∨ ¬ X). (\ صفحه نمایش F = (\ neg X \ vee Y) \ گوه (\ 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 معتبر است. در اینجا فرمولاسیون دقیق وجود دارد.

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

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

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

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

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

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

  الگوریتم این انتقال به این صورت است: ما دو نفی را بالای DNF قرار می دهیم و با استفاده از قواعد دی مورگان (بدون لمس نفی بالایی)، نفی 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، عبارت را در آن قرار دهید و سپس پرانتزها را گسترش دهید (در این مورد، ما اصطلاحات متمایز مکرر نمی نویسیم). مثلا:

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

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

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

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

  تفکیک ساده(انفصال شامل) یا منفصل(انگلیسی disjunct) تفکیک یک یا چند متغیر یا نفی آنها است و هر متغیر بیش از یک بار اتفاق نمی افتد.

  تفکیک ساده

  • کاملاگر هر متغیر (یا نفی آن) دقیقاً یکبار در آن ظاهر شود ؛
  • یکنواختاگر حاوی متغیرهای منفی نباشد.

  فرم نرمال پیوندی، CNF(eng. conjunctive normal form, CNF) فرم نرمال که در آن یک تابع بولی به شکل ترکیبی از چند جمله ساده است.

  مثال CNF: $ f (x, y) = (x \ lor y) \ land (y \ lor \ neg (z)) $

  SKNF

  فرم نرمال پیوندی کامل، SKNF(شکل نرمال پیوندی کامل، PCNF) یک CNF است که شرایط زیر را برآورده می کند:

  • همان تفکیک های ساده را ندارد
  • هر تفکیک ساده کامل است

  مثال SKNF:$ f (x, y, z) = (x \ lor \ neg (y) \ lor z) \ land (x \ lor y \ lor \ neg (z)) $

  قضیه:برای هرچی تابع بولی$ f (\ vec (x)) $، برابر با واحد هویت نیست، یک SKNF وجود دارد که آن را تعریف می کند.

  اثبات:از آنجایی که معکوس تابع $ \ neg (f) (\ vec x) $ برابر است با یک عدد در آن چندتایی که $ f (\ vec x) $ برابر با صفر است ، SDNF برای $ \ neg (f) (\ vec x) $ را می توان به صورت زیر نوشت:

  $ \ neg (f) (\ vec x) = \ bigvee \ limits_ (f (x ^ (\ sigma_ (1)), x ^ (\ sigma_ (2)), ..., x ^ (\ sigma_ (n ))) = 0) (x_ (1) ^ (\ sigma_ (1)) \ wedge x_ (2) ^ (\ sigma_ (2)) \ wedge ... \ wedge x_ (n) ^ (\ sigma_ (n ))) $، که $ \ sigma_ (i) $ نشان دهنده وجود یا عدم وجود نفی برای $ x_ (i) $ است.

  بیایید معکوس سمت چپ و راست عبارت را پیدا کنیم:

  $ f (\ vec x) = \ neg ((\ bigvee \ limits_ (f (x ^ (\ sigma_ (1)), x ^ (\ sigma_ (2)), ..., x ^ (\ sigma_ (n ))) = 0) (x_ (1) ^ (\ sigma_ (1)) \ wedge x_ (2) ^ (\ sigma_ (2)) \ wedge ... \ wedge x_ (n) ^ (\ sigma_ (n ))))) $

  با اعمال دوبار قاعده د مورگان بر عبارت بدست آمده در سمت راست ، بدست می آوریم: $ f (\ vec x) = \ bigwedge \ limit_ (f (x ^ (\ sigma_1) ، x ^ (\ sigma_2) ، \ نقطه , x ^ (\ sigma_n)) = 0) $ $ (\ neg (x_1 ^ (\ sigma_1)) \ vee \ neg (x_2 ^ (\ sigma_2)) \ vee \ dots \ vee \ neg (x_n ^ (\ sigma_n ))) دلار

  آخرین عبارت SKNF است. از آنجا که SKNF از SDNF بدست می آید ، که می تواند برای هر تابعی که به طور یکسان صفر نیست ساخته شود ، قضیه ثابت می شود.

  الگوریتم ساخت SKNF بر اساس جدول حقیقت

  • در جدول صدق، مجموعه‌ای از متغیرها را علامت‌گذاری می‌کنیم که مقدار تابع در آنها برابر با $ 0 است.
  • برای هر مجموعه علامت گذاری شده، تفکیک همه متغیرها را طبق قانون زیر می نویسیم: اگر مقدار یک متغیر 0 $ باشد، خود متغیر را در تفکیک قرار می دهیم، در غیر این صورت نفی آن.
  • ما تمام تفکیک های حاصل را با عملیات ربط به هم وصل می کنیم.

  نمونه ای از ساخت SKNF برای میانه

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

  ایکس	y	z	$ \ langle x، y، z \ rangle $
  0	0	0	0
  0	0	1	0
  0	1	0	0
  0	1	1	1
  1	0	0	0
  1	0	1	1
  1	1	0	1
  1	1	1	1

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

  ایکس	y	z	$ \ langle x، y، z \ rangle $
  0	0	0	0	$ (x \ lor y \ lor z) $
  0	0	1	0	$ (x \ lor y \ lor \ neg (z)) $
  0	1	0	0	$ (x \ lor \ منفی (y) \ lor z) $
  0	1	1	1
  1	0	0	0	$ (\ منفی (x) \ lor y \ lor z) $
  1	0	1	1
  1	1	0	1
  1	1	1	1

  3). ما تمام انفصال های حاصل را با عملیات ربط به هم وصل می کنیم.

  $ \ langle x, y, z \ rangle = (x \ lor y \ lor z) \ land (\ neg (x) \ lor y \ lor z) \ land (x \ lor \ neg (y) \ lor z) \ land (x \ lor y \ lor \ neg (z)) $

  نمونه های SKNF برای برخی از توابع

  پیکان پیرس: $ x \ پایین y = (\ neg (x) \ lor (y)) \ land ((x) \ lor \ neg (y)) \ land (\ neg (x) \ lor \ neg (y) ) دلار

  انحصاری یا: $ x \ oplus y \ oplus z = (\ neg (x) \ lor \ neg (y) \ lor z) \ land (\ neg (x) \ lor y \ lor \ neg (z)) \ land (x \ lor \ neg (y) \ lor \ neg (z)) \ land (x \ lor y \ lor z) $

  تعریف 1.ربط ربط (ربط ابتدایی)از متغیرها، پیوند این متغیرها یا نفی آنها نامیده می شود.

  مثلا، یک پیوند ابتدایی است.

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

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

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

  مثلا،- DNF.

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

  مثلا، - CNF.

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

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

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

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

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

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

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

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

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

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

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

  از نظر ساختاری ، SKNF برای هر فرمول از جبر پیشنهادی که به CNF تقلیل می یابد را می توان به شرح زیر تعریف کرد.

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

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

  راه های پیدا کردن SDNF

  راه 1

  راه دوم

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

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

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

  راه های پیدا کردن SKNF

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

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

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

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

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

  راه حل

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

  = / de Morgan و قوانین نفی مضاعف / =

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

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

  راه حل

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

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

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

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

  راه حل

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

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

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

  خط 1:؛

  خط 3 :؛

  خط 5:.

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

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

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

  ب) استفاده از جدول صدق

  راه حل:

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

  فرمول این است:

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

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

  خط 2:؛

  خط 6:.

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

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

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

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

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

  آ) ;

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

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

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

  ب) ;

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

  ربط های ابتدایی (ربط)ربط متغیرها یا نفی آنها نامیده می شوند که هر متغیر حداکثر در آنها رخ می دهد

  یک بار.

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

  بندهای ابتدایی (بند)تفکیک متغیرها با یا بدون نفی نامیده می شوند.

  فرم طبیعی ربطی(CNF) فرمولی است که به شکل ترکیبی از تفکیک های ابتدایی است.

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

  الگوریتم ساخت DNF:

  1. با استفاده از فرمول های تبدیل معادل به عملیات بولی بروید.

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

  3. براکت ها را گسترش دهید - قوانین توزیع را اعمال کنید.

  4. اصطلاحات تکراری را یک بار در نظر بگیرید - قانون ناتوانی.

  5. قوانین جذب و نیمه جذب را اعمال کنید.

  مثال 6.فرمول های DNF را پیدا کنید:

  جبر بولی برقرار است اصل دوگانگی... به شرح زیر می باشد.

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

  مثال 7.تابع دوگانه را پیدا کنید.

  از توابع ابتدایی جبر منطق 1 دوتایی به 0 و بالعکس، x دوگانه به x، دوگانه، دوگانه و بالعکس است.

  اگر در فرمول F 1 که تابع را نشان می دهد، همه حروف ربط جایگزین شوند

  در تفکیک، تفکیک در رابطه، 1 در 0، 0 در 1، سپس فرمول F * را به دست می آوریم که نشان دهنده تابع * دوگانه است.

  فرم نرمال ربطی (CNF) یک مفهوم دوگانه برای DNF است، بنابراین ساخت آن بر اساس این طرح آسان است:

  مثال 8فرمول CNF را پیدا کنید:

  با استفاده از نتیجه مثال 6، داریم

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

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

  هر DNF را می توان با تقسیم حروف ربط که شامل همه متغیرها نیستند، به SDNF کاهش داد. جمع برای متغیر گمشده x i با استفاده از قانون توزیع ضرب می شود

  مثال 9.مثال 6 SDNF را برای DNF پیدا کنید

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

  هر CNF را می توان با افزودن یک اصطلاح ربطی که حاوی هیچ گونه ربط X i متغیر نیست و اعمال قانون توزیعی به SKNF کاهش داد.

  مثال 10. CNF را به SKNF بیاورید:

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

  مثال 11. SKNF را برای فرمول در مثال 6 پیدا کنید.

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

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

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

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

  مثال 12. SDNF و SKNF را با استفاده از جدول حقیقت برای فرمول مثال 6 پیدا کنید.

  جدول 14 فقط مقدار نهایی F = 10101101 را نشان می دهد. شما باید خودتان با ساختن یک جدول حقیقت گسترده از صحت این جمله مطمئن شوید.

  جدول 14

  ایکس	y	z