§4. معادل، فرمول های TI و TL جبر منطق. معادلات اساسی (قوانین عملیات منطقی). قانون دوگانگی.

تعریف.

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

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

یک فرمول در صورتی که مقدار 0 را برای همه مقادیر متغیرهای موجود در آن بگیرد، IENTICALLY FALSE (یا CONTRADITION) نامیده می شود.

ارتباط زیر بین مفاهیم هم ارزی و هم ارزی وجود دارد: اگر فرمول های A و B معادل باشند، فرمول A"B یک توتولوژی است و بالعکس، اگر فرمول A"B یک توتولوژی باشد، فرمول A و B یک توتولوژی است. B معادل هستند.

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

1. معادلات اساسی.

قوانین ناتوانی

قانون تضاد

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

قانون حذف نفی مضاعف

قوانین جذب

2. معادل هایی که برخی از عملیات منطقی را از طریق برخی دیگر بیان می کنند.

در اینجا 3، 4، 5، 6 قوانین مورگان هستند.

واضح است که اگر از هر دو قسمت دومی نفی بگیریم و از قانون رفع نفی مضاعف استفاده کنیم، معادل های 5 و 6 به ترتیب از معادل های 3 و 4 به دست می آیند.

بنابراین، چهار معادل اول نیاز به اثبات دارند. بیایید یکی از آنها را ثابت کنیم: اولی.

از آنجایی که با مقادیر منطقی یکسان x و y فرمول https://pandia.ru/text/78/396/images/image018.gif" width="124" height="21"> درست است. بنابراین، در در این حالت هر دو بخش معادل دارای مقادیر واقعی یکسانی هستند.

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

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

معادل های 2 و 4 به روشی مشابه ثابت می شوند.

از معادل‌های این گروه چنین برمی‌آید که هر فرمول در جبر منطق را می‌توان با یک فرمول معادل که فقط شامل دو عمل منطقی است جایگزین کرد: پیوند و نفی یا تفکیک و نفی.

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

با این حال، عملیاتی وجود دارد که با آنها می توان هر یک از پنج عملیات منطقی را که استفاده می کنیم بیان کرد. چنین عملیاتی، برای مثال، عملیات "سکته مغزی شفر" است. این عملیات با نماد ½ left " style="border-collapse:collapse;border:none;margin-left:6.75pt;margin-right: 6.75pt"> نشان داده می شود.

قوانین جبر گزاره ای

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

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

قوانین جبر گزاره ای (جبر منطق) - اینها توتولوژی هستند.

گاهی به این قوانین قضیه می گویند.

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

چهار قانون اول زیر قوانین اساسی جبر گزاره ای هستند.

قانون هویت:

A=A

هر مفهوم و قضاوتی با خودش یکسان است.

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

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

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

قانون عدم تناقض :

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

1. عدد 12345 یا زوج است یا فرد، گزینه سومی وجود ندارد.

2. شرکت با زیان یا سربه سر کار می کند.

3. این مایع ممکن است اسید باشد یا نباشد.

قانون میانه حذف شده قانونی نیست که توسط همه منطق دانان به عنوان یک قانون جهانی منطق به رسمیت شناخته شده است. این قانون در جایی اعمال می‌شود که شناخت با وضعیتی سفت و سخت سروکار دارد: «یا - یا»، «درست-نادرست». در جایی که عدم قطعیت رخ می دهد (مثلاً در استدلال درباره آینده)، قانون میانه حذف شده اغلب نمی تواند اعمال شود.

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

پارادوکس (پارادوکس یونانی - غیر منتظره، عجیب) در این مثال به دلیل این واقعیت است که جمله به خود اشاره دارد. یکی دیگر از پارادوکس های معروف، مشکل آرایشگاه است: در یک شهر، یک آرایشگر موهای همه ساکنان را کوتاه می کند، به جز کسانی که موهای خود را کوتاه می کنند. چه کسی موهای آرایشگر را کوتاه می کند؟ در منطق، به دلیل صوری بودن آن، نمی توان شکل چنین اظهار خود ارجاعی را به دست آورد. این یک بار دیگر این ایده را تأیید می کند که با کمک جبر منطق نمی توان همه افکار و استدلال های ممکن را بیان کرد. اجازه دهید نشان دهیم که چگونه می توان بر اساس تعریف معادل گزاره ای، قوانین باقیمانده جبر گزاره ای را به دست آورد.

به عنوان مثال، بیایید تعیین کنیم که A معادل (معادل) چیست (نفی مضاعف A، یعنی نفی نفی A برای انجام این کار، جدول صدق می‌سازیم:

با تعریف هم ارزی، باید ستونی را پیدا کنیم که مقادیر آن با مقادیر ستون A منطبق باشد. این ستون A خواهد بود.

بنابراین، می توانیم قانون نفی مضاعف را فرموله کنیم:

اگر یک عبارت را دو بار نفی کنید، نتیجه عبارت اصلی است. به عنوان مثال، بیانیه A = Matroskin - گربهمعادل عبارت A است = این درست نیست که ماتروسکین گربه نیست.

به روشی مشابه می توان قوانین زیر را استخراج و تأیید کرد:

خواص ثابت ها:

قوانین ناتوانی:

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

قوانین جابجایی:

A v B = B v A

A & B = B & A

عملوندهای A و B را می توان در عملیات تفکیک و ربط مبادله کرد.

قوانین انجمنی:

A v(B v C) = (A v B) v C;

الف و (ب و ج) = (الف و ب) و ج.

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

قوانین توزیعی:

A v (B & C) = (A v B) & (A v C)

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

A & (B v C) = (A & B) v (A & C)

(توزیع حرف ربط
در مورد تفکیک)

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

قوانین جذب:

A v (A & B) = A

A & (A v B) = A

قوانین جذب را خودتان ثابت کنید.

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

فرمول بندی شفاهی قوانین دی مورگان:

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

نمونه هایی از اجرای قانون دی مورگان:

1) این جمله درست نیست که من عربی می دانم یا چینی با جمله من عربی نمی دانم و چینی نمی دانم یکسان است.

2) جمله درست نیست که من درس را یاد گرفتم و در آن نمره بد گرفتم با عبارت یا درس را یاد نگرفتم یا در آن نمره بد نگرفتم یکسان است.

جایگزینی عملیات ضمنی و هم ارزی

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

بنابراین، عملیات ضمنی را می توان مطابق با قانون زیر جایگزین کرد:

دو قانون برای جایگزینی عملیات هم ارزی وجود دارد:

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

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

مثال زیر را در نظر بگیرید.

بگذارید بیانیه داده شود:

ه = اینکه اگر در مسابقه برنده شوم، جایزه می گیرم درست نیست.

اجازه دهید A = من برنده مسابقه خواهم شد,

ب = من یک جایزه دریافت خواهم کرد.

سپس

از اینجا، E = من در مسابقه برنده می شوم، اما جایزه ای دریافت نمی کنم.

ریاضیات گسسته: منطق ریاضی

سخنرانی 8

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

قوانین جبر بول

که در منطق ریاضیجبر خاصی تعریف شده است، جبر بول، که شامل عملیات ضرب منطقی، جمع و نفی منطقی (، +، - ) است که امکان تبدیل یکسان عبارات منطقی را فراهم می کند. این قوانین شامل

قانون ناتوانی (یکسانی)

قانون جابجایی

a  b = b a

قانون انجمنی

a + (b + c) = (a + b) + c

a  (b  c) = (a  b)  c

قوانین توزیع

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

A  (b + c) = a  b + a  c

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

A + b  c = (a + b)  (a + c)

قانون نفی مضاعف

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

قوانین جذب

a + a  b = a

a  (a + b) = a

قوانینی که اعمال را با ثابت های منطقی 0 و 1 تعریف می کنند

a + 0 = a a  0 = 0	a+1=1 a  1 = a
1 = 0

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

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

اثبات این هویت با استفاده از قانون اول توزیع انجام می شود:

اثبات این هویت با استفاده از قانون دوم توزیع انجام می شود:

قانون بلیک پورتسکی

با اعمال قوانین عمل با ثابت های منطقی، ناتوانی و چسبندگی، می توان این هویت را به شرح زیر اثبات کرد:

قانون پیچیدگی بیان منطقی

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

ساده کردن توابع منطقی

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

وظایف

SDNF را با توابع زیر ساده کنید:

1. (آ ب)  ج

2. (آ ب)  ج

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

3.

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

SDNF =

هیچ ساده سازی بیشتر امکان پذیر نیست.

4.

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

SDNF =
5.

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

روش کواین مک کلاسکی

به حداقل رساندن توابع منطقی را می توان با استفاده از روش Quine-McCluskey انجام داد که شامل چهار مرحله است:

1. 
   اجازه دهید مجموعه ها (مواد تشکیل دهنده) را که تابع در آنها صادق است به شکل معادل های دودویی نمایش دهیم.
2. 
   بیایید معادل‌های باینری را در ردیف‌ها (با توجه به تعداد واحدهای معادل‌های باینری) و مجموعه‌های چسب (اعمال قانون چسباندن به اجزای مربوطه) در ردیف‌های مجاور ترتیب دهیم و حداکثر فواصل زمانی را تا حد امکان به دست آوریم. هر مجموعه ای را که درگیر چسباندن است علامت گذاری می کنیم. فقط آن مجموعه ها یا بازه ها ادغام می شوند که تفاوت آنها فقط در مقدار یک رقم است: 001 و 000، 001- و 101- و غیره.
3. 
   بیایید یک جدول Quine بسازیم که ستون‌های آن با مجموعه‌های حقیقت دودویی تابع، و ردیف‌ها با حداکثر فواصل مطابقت دارند. اگر مجموعه i با بازه j ام پوشانده شود، در تقاطع سطر و ستون مربوطه عدد 1 را قرار می دهیم، در غیر این صورت 0 یا هیچ قرار می دهیم.
4. 
   حداقل پوشش جدول کواین را می‌یابیم که شامل حداقل تعداد بازه‌های حداکثر است که شامل (پوشش) همه تاپل‌هایی است که تابع در آنها صادق است.

تابع F1 را در نظر بگیرید که در تاپل ها (1، 3، 5، 7، 11، 13، 15) صادق است. شکل نرمال تفکیک کامل این تابع برابر است با:

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

1	0001
3	0011
5	0101
7	0111
11	1011
13	1101
15	1111

بیایید مجموعه‌های باینری را در طبقات مرتب کنیم و تا جایی که ممکن است چسب زدن را انجام دهیم

0001  	00-1 	0-1
0011  	0-01 	--11
0101  	-011 	-1-1
0111   	0-11  
1101  	-101 
1011  	01-1  
1111   	11-1 
	-111  
	1-11 

سپس جدول Quine را می سازیم:

	0001	0011	0101	0111	1011	1101	1111
0--1	1	1	1	1
--11		1		1	1	1	1
-1-1			1	1		1	1

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

MDNF = (0 - - 1، - - 1 1) =

بیایید به چند نمونه نگاه کنیم.
وظایف

1. توابع MDNF را پیدا کنیدf1 =

f1

x1 x2 x3 x4
0 0 0 0	0
0 0 0 1	1
0 0 1 0	1
0 0 1 1	1
0 1 0 0	1
0 1 0 1	0
0 1 1 0	0
0 1 1 1	1
1 0 0 0	0
1 0 0 1	1
1 0 1 0	1
1 0 1 1	1
1 1 0 0	0
1 1 0 1	1
1 1 1 0	0
1 1 1 1	1

DNF کامل تابع مورد مطالعه به شکل زیر است:

0001 	00-1 	-0-1
0010 	-001 	-01-
0100	001- 	--11
0011 	-010 	1-1
1010 	0-11 
1001 	-011 
0111 	101- 
1011 	10-1 
1101 	1-01 
1111 	-111 
	1-11 
	11-1 

ستون اول شامل مجموعه ای است که در هیچ ادغامی درگیر نشده است - این خود حداکثر بازه 0100 است. در ستون سوم چهار حداکثر بازه دیگر به آن اضافه می شود: (-0-1، -01-، -11، 1). --1).

جدول Quine را می سازیم:

	0001	0010	0100	0011	1010	1001	0111	1011	1101	1111
0100			1
-0-1	1					1		1	1
-01-		1		1	1			1
--11				1			1	1		1
1--1						1		1	1	1

بیایید هسته پوشش را تعریف کنیم که شامل فواصل اجباری است:

(0100، -0-1، -01-، -11). که در در این مورد، هسته پوشش کل جدول را به طور کلی پوشش می دهد.

شکل عادی منفصل حداقل f1 عبارت است از:

2. توابع MDNF را پیدا کنید f 2( ایکس 1, ایکس 2, ایکس 3) که مقادیر منفرد را در مجموعه های 0،2،3،6 و 7 می گیرد.

بیایید یک جدول حقیقت بسازیم f2

x1 x2 x3	F2
0 0 0	1
0 0 1	0
0 1 0	1
0 1 1	1
1 0 0	0
1 0 1	0
1 1 0	1
1 1 1	1

SDNF =
بیایید مجموعه‌های باینری را در ردیف‌ها مرتب کنیم و چسباندن را انجام دهیم:

000 	0-0 	--0
010 	-00 
100 	-10 
110 	1-0 
111 	11-

در نتیجه چسباندن، ما تنها دو فاصله حداکثر به دست آوردیم: (11-، --0). بدون ساخت جدول کواین، بدیهی است که حداقل پوشش را تشکیل می دهند، زیرا حذف هر یک از این بازه‌ها منجر به از دست رفتن مجموعه‌هایی می‌شود که تابع f2 (x1, x2, x3) ) درست است، واقعی. MDNF = x1 x2 +x3.

ادبیات

1. 
   گوسوا A.I. یادگیری علوم کامپیوتر: مسائل و روش های حل آنها - M.: DIALOG-MEPhI، 2003.
2. 
   گورباتوف V.A. مبانی ریاضیات گسسته - م.: علم. Fizmatlit، 1999.-544s

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

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

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

شاید اصطلاح اصلی در رشته مورد مطالعه بیانیه باشد. این یک جمله مشخص است که نمی تواند هم نادرست و هم درست باشد. او همیشه تنها یکی از این ویژگی ها را دارد. در این مورد، به طور متعارف پذیرفته شده است که مقدار 1 را به صدق، 0 را به نادرستی اختصاص دهیم و خود گزاره را A، B، C معینی بنامیم. به عبارت دیگر، فرمول A = 1 به این معنی است که عبارت A صادق است. شما می توانید با بیانیه ها بیشتر برخورد کنید به طرق مختلف. بیایید به طور خلاصه اقداماتی را که می توان با آنها انجام داد در نظر گرفت. همچنین توجه داریم که قوانین جبر منطقی را نمی توان بدون دانستن این قوانین آموخت.

1. تفکیکدو عبارت - نتیجه عملیات "یا". می تواند نادرست یا درست باشد. از علامت "v" استفاده شده است.

2. ربط.نتیجه چنین عملی که روی دو گزاره انجام می شود تنها در صورتی جدید خواهد بود که هر دو عبارت اصلی درست باشند. عملگر "and" استفاده می شود، نماد "^".

3. مفهوم.عملیات "اگر A پس B". نتیجه یک عبارت نادرست است فقط اگر A درست باشد و B نادرست باشد.

4. هم ارزی.عملیات A اگر و فقط اگر B وقتی. این عبارت در مواردی که هر دو متغیر امتیازات یکسانی دارند صادق است. نماد استفاده می شود "<->».

همچنین تعدادی عملیات نزدیک به مفهوم وجود دارد، اما در این مقاله مورد توجه قرار نخواهند گرفت.

حال بیایید قوانین اساسی جبر منطقی را با جزئیات در نظر بگیریم:

1. جابجایی یا جابجایی بیان می کند که تغییر مکان اصطلاحات منطقی در عملیات ربط یا منفصل تأثیری در نتیجه ندارد.

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

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

4. قانون دی مورگان ( وارونگی یا نفی ). نفی عمل ربط معادل تفکیک نفی متغیرهای اصلی است. نفی یک تفکیک به نوبه خود برابر است با نفی همان متغیرها.

5. دو برابر منفی. نفی یک گزاره معین دو بار منجر به گزاره اصلی می شود و سه بار - نفی آن.

6. قانون ناتوانی برای جمع منطقی به این صورت است: x v x v x v x = x; برای ضرب: x^x^x^=x.

7. قانون عدم تناقض می گوید: دو گزاره اگر متضاد باشند، نمی توانند همزمان صادق باشند.

8. قانون طرد ثالث. از میان دو گزاره متناقض، یکی همیشه درست، دیگری نادرست است و سومی داده نشده است.

9. قانون جذب را می توان برای جمع منطقی به این صورت نوشت: x v (x^y)=x، برای ضرب: x^ (x v y)=x.

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

(x^y) v (-x^y)=y.

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

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

پنج قانون جبر منطقی وجود دارد:

1. قانون عناصر منفرد

1 * X = X
0 * X = 0
1 + X = 1
0 + X = X

این قانون جبر منطق مستقیماً از عبارات فوق در مورد بدیهیات جبر منطق پیروی می کند.

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

گزینه دوم برای استفاده از این عبارات امکان صفر کردن انتخابی ارقام خاصی از یک عدد چند رقمی است. هنگامی که عملیات "AND" را بیت به بیت اعمال می کنید، می توانید مقدار قبلی بیت را رها کنید یا با اعمال یک واحد یا پتانسیل صفر به بیت های مربوطه، آن را صفر کنید. برای مثال، باید ارقام 6، 3 و 1 را بازنشانی کنید. سپس:

در مثال ارائه شده از استفاده از قوانین جبر منطقی، به وضوح قابل مشاهده است که برای تنظیم مجدد ارقام لازم در ماسک (عدد پایین)، به جای ارقام مربوطه، صفر و در ارقام باقی مانده یک نوشته می شود. در عدد اصلی (شماره بالایی) به جای رقم های 6 و 1 یک عدد وجود دارد. پس از انجام عملیات «AND» صفرها در این مکان ها ظاهر می شوند. به جای سومین رقم در عدد اصلی یک عدد صفر وجود دارد. عدد به دست آمده نیز حاوی یک صفر در این مکان است. ارقام باقیمانده، مطابق با شرایط مشکل، تغییر نمی کنند.

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

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

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

شکل 1. مدار "2I-NOT"، پیاده سازی شده بر روی یک عنصر منطقی "3I-NOT"

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

شکل 2. مدار "NOT" اجرا شده بر روی عنصر "2I-NOT".

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

2. قوانین نفی

آ. قانون عناصر اضافی

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

یکی دیگر از قوانین پرکاربرد جبر منطقی، قانون نفی مضاعف است.

ب دو بار نه

قانون نفی مضاعف هم برای ساده کردن عبارات منطقی (و در نتیجه برای ساده سازی و کاهش هزینه مدارهای ترکیبی دیجیتال) و هم برای حذف وارونگی سیگنال پس از عناصر منطقی مانند "2AND-NOT" و "2OR-NOT" استفاده می شود. . در این مورد، قوانین جبر منطقی امکان پیاده سازی مدارهای دیجیتال داده شده را با استفاده از مجموعه محدودی از عناصر منطقی فراهم می کند.

ج قانون منطق منفی

قانون منطق منفی برای هر تعداد متغیر معتبر است. این قانون جبر منطقی به شما امکان می دهد "OR" را با استفاده از عناصر منطقی پیاده سازی کنید و بالعکس: برای پیاده سازی تابع منطقی "OR" با استفاده از عناصر منطقی "AND". این به ویژه در مدارهای TTL مفید است، زیرا پیاده‌سازی گیت‌های منطقی «AND» آسان است، اما پیاده‌سازی گیت‌های منطقی «OR» بسیار دشوار است. به لطف قانون منطق منفی، می توان عناصر "OR" را روی عناصر منطقی "AND" پیاده سازی کرد. شکل 3 اجرای یک عنصر منطقی "2OR" را بر روی یک عنصر " " و دو اینورتر نشان می دهد.

شکل 3. عنصر منطقی "2OR"، پیاده سازی شده بر روی عنصر "2I-NOT" و دو اینورتر

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

3. قوانین ترکیبی

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

آ. قانون توتولوژی (تکرار چندگانه)

X + X + X + X = X
X * X * X * X = X

این قانون جبر منطقی اجازه می دهد تا از دروازه های منطقی با ورودی های بیشتر به عنوان دروازه های منطقی با ورودی های کمتر استفاده شود. به عنوان مثال، همانطور که در شکل 4 نشان داده شده است، می توانید یک مدار دو ورودی "2I" را بر روی یک عنصر منطقی "3I" پیاده سازی کنید:

شکل 4. مدار "2I-NOT"، پیاده سازی شده بر روی یک عنصر منطقی "3I-NOT"

یا از مدار "2AND-NOT" به عنوان یک اینورتر معمولی استفاده کنید، همانطور که در شکل 5 نشان داده شده است:

شکل 5. مدار "NOT" پیاده سازی شده بر روی یک عنصر منطقی "2I-NOT"

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

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

اجازه دهید بررسی خود را در مورد قوانین جبر منطقی ادامه دهیم:

ب قانون تحرک

A + B + C + D = A + C + B + D

ج قانون ترکیب

A + B + C + D = A + (B + C) + D = A + B + (C + D)

د قانون توزیعی

X1 (X2 + X3) = X1X2 + X1X3 X1 + X2X3 = (X1 + X2) (X1 + X3) = /با باز کردن پرانتز این را ثابت خواهیم کرد/ =
= X1X1 + X1X3 + X1X2 + X2X3 = X1 (1 + X3 + X2) + X2X3 = X1 + X2X3

4. قانون جذب (یک متغیر متغیر دیگر را جذب می کند)

X1 + X1X2X3 =X1(1 + X2X3) = X1

5. قانون چسباندن (فقط یک متغیر را انجام می دهد)

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

1. عمل داخل پرانتز
2. عملیات با یک عملوند (عملیات تک مکان) - "NOT"
3. ربط - "و"
4. تفکیک - "OR"
5. مجموع مدول دو.

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

ادبیات:

همراه با مقاله “قوانین جبر منطق” را بخوانید:

هر مدار منطقی بدون حافظه به طور کامل توسط جدول صدق توصیف می شود... برای پیاده سازی جدول صدق کافی است فقط آن ردیف ها را در نظر بگیرید...
http://site/digital/SintSxem.php

رمزگشاها (رمزگشاها) به شما امکان می دهند برخی از انواع کدهای باینری را به انواع دیگر تبدیل کنید. مثلا...
http://site/digital/DC.php

اغلب، توسعه دهندگان تجهیزات دیجیتال با مشکل معکوس مواجه می شوند. شما باید کد خطی اکتال یا اعشاری را به...
http://site/digital/Coder.php

مولتی پلکسرها دستگاه هایی هستند که به شما اجازه می دهند چندین ورودی را به یک خروجی متصل کنید...
http://site/digital/MS.php

دی مولتی پلکسرها وسایلی هستند... تفاوت قابل توجهی با مالتی پلکسر در...
http://site/digital/DMS.php