اعمالی که در دستگاههای الکترونیکی و یا با کامپیوترها انجام می پذیرد از یک برنامه program پیروی می کند پاسخهای که به وضعیتهای متغیر یک برنامه داده می شود از یک منطق معین تبعیت می نمایند منطق علم استدلال یا علم نتیجه گیری از مفروضات است.
در علم Logic قوانین و اصولی وجود دارد که در آنها استنتاج صحیح و اصولی از دادهها انجام می گیرد.
عبارات منطقی بصورت سمپلها و معادلات نوشته می شود و ساده ترین سمبلها در این منطق درست یا نادرست و یا به عبارتی بسته یا بار بودن یک کلید است در هر حال خروجی می تواند نشان دهنده یک وضعیت باشد.
در سال 1854 ریاضی دان انگلیسی به نام جورج بول George Bole روابط منطقی را با استفاده از سیستم باینری به صورت یک سر فرمولهای ریاضی بیان نمود که شامل یک مجموعه از الگوها و تعدادی اصول می باشد که تشابهی با اصول جبر معمولی ندارد.
در سال 1938 نیز دانشمند دیگری به نام سی.ای.
شانون یک جبر بول دو مقداری را به نام جبر سوئیچینگ معرفی نمود که در طراحی مدارات سوئیچینگ به کار گرفته می شود.
جبر بول نیز همانند هر سیستم ریاضی دارای یک فرضیات اولیه می باشد که از آنها قوانین و تئوری های مورد نظر را می توان نتیجه گرفت و به عنوان یک ساختار جبری معین بکار گرفت.
روابط و قوانین این جبر برای طراحی مدارات منطقی و سیستم های دیجیتالی مورد استفاده قرار می گیرد در جب بول فرض اصلی بر این است که دارای یک متغیر باینری هستیم که اگر x یک متغیر باینری باشد و اگر مقدار آن باشد در این صورت حتماً مقدارش برابر خواهد بود و اگر باشد حتماً خواهد بود و حالتی دیگری برای متغیر x متصور نیست این دو مقدار (1و0) به مقادیر صحت Trutr-valve و جدول مقادیر ارزشی 0 و 1 را جدول دستی می نامند.
قبل از بیان اصول و تئوری های عنوان شده در جبر بول با توجه به اصول مطرح شده بخش مجموعه ها قابل ذکر است که مجموعه S می تواند شامل عناصر مشخصی همانند A و B باشد در این صورت و میباشد یعنی A عضوی از S و B نیز عضوی از S است در این صورت می توان گفت عنصر N عضوی از S نمی باشد.
یک مجموعه با تعداد مشخصی از عناصر تشکیل شده است لذا مجموعه عناصر را با یک جفت اکولاد نشان می دهند.
مجموعه اعداد طبیعی از 1 شروع می شود و هر عضو دیگر آن با افزودن یک واحد به عدد قبلی به دست می آید.
در این صورت عملگری که می تواند در این مجموعه صحیح باشد و موجب شود عناصر بدست آمده در مجموعه اعداد طبیعی قرار گیرد عملگرهای جمع و ضرب میباشد+ و نتیجه می توان گرفت یک عملگر زمانی بر روی عناصر یک مجموعه معتبر است که عنصر جدید به دست آمده حاصل از ضرب یا جمع دو عنصر از مجموعه مورد نظر در آن مجموعه قرار گیرد.
به بیان بسیار ساده می توان گفت عملگر ضرب و عملگر جمع بر روی اعداد طبیعی نتایجی را که حاصل نموده که در سری مجموعه اعداد طبیعی قرار دارد لذا نتیجه میگیریم که مجموعه اعداد طبیعی نسبت به دو عملگر+ و بسته است.
همانگونه که می دانیم صفر در مجموعه اعداد طبیعی قرار ندارد در این صورت می توان گفت که عنصر صفر در مجموعه اعداد طبیعی قابل شناسه نمی باشد.
ولی اگر مجموعه اعداد صحیح را در نظر بگیریم می توان گفت صفر یک عنصر شناسه در مجموعه اعداد صحیح میباشد و سه عملگر جمع + ضری.
تفریق – نیز در این مجموعه معتبر میباشد.
ولی اگر مجموعه اعداد صحیح را در نظر بگیریم می توان گفت صفر یک عنصر شناسه در مجموعه اعداد صحیح میباشد و سه عملگر جمع + ضری.
تفریق – نیز در این مجموعه معتبر میباشد.
حال که تقریباً مفاهیم مجموعه، عناصر مجموعه، عملگر و نقش آن و شناسه و بسته بودن مشخص گردید.
به بیان اصول و تئوری های مطرح شده در جبر بول می پردازیم.
1)قانون عینیت:اولین تئوری که از قانون عینیت نتیجه گرفته می شود که برا جبر معمولی متفاوت است نشان دهنده عمل “0” AND , “+”OR بر روی یک متغیر یا دو متغیر یکسان از یک مجموعه دودوئی است.
همانگونه که می دانیم یک مجموعه دودوئی فقط دو عنصر دارد لذا اگر یک عنصر یا متغیر را در نظر بگیریم خواهیم داشت.
یک OR یک 1=1+1 (1 یک AND یک 1=1.1 (2 مشاهده می شود با توجه به تعاریفی که برای نوع عملگرها در سیستم دودوئی وجود دارد تفاوتی بین این جبر و جبر معمولی وجود دارد.
برای X با توجه به مجموعه اعداد دودوئی دو مقدار 0 و 1 را قائل می باشیم لذا اگر باشد (1 (2 *نتیجه می گیریم که مجموعه اعداد دودوئی نیست به دو عملگر “0” AND, “+” OR یک مجموعه بسته است.
2-مطالب گفته شده در بند یک به عنوان تئوری اول از قانون عینیت بیان می شود که دوگان آن در جبر بول بعنوان تئوری دوم بیان شده است.
(1 (1 (2 (2 با توجه به سیستم دودوئی و یک ارزش دیگر در مجموعه دودوئی یعنی صفر و دو عملگر “+” و “.” اصل دیگر با توجه به روابط روبرو حاصل می شود.
(3 (4 قانون جابجائی: در این قانون می توان نتیجه گرفت که چگونه دو متغیر A و B با دو عملگر “.” AND, “+” OR چگونه می توانند به جای یکدیگر بنشیند.
در این صورت اگر A و B دو متغیر باشد روابط ذیل با توجه به قانون جابجائی بدست می آید.
A+B=B+A(1 A.B=B.A(2 5-قانون شرکت پذیری یا قنون اتحاد: اگر مجموعه S دارای سه عضو باید وB و A عملگر “.” AND, “+”OR روی مجموعه شرکت پذیر است.
(A+B)+C=A+(B+C)(1 (A.B).C=A.(B.C) (2 6-قانون توزیع پذیری اگر دو عملگر “+” و “.” را در نظر بگیریم اصل توزیع پذیری بر روی مجموعه S با سه متغیر اینگونه بیان می گردد.
A.(B+C)=(A .
B)+(A .C) (1 A+(B .C)=(A+B) .(A+C) (2 با توجه به دو رابطه بالا در اصل توزیع پذیری مشاهده می شود که علائم منطقی جایشان را با یکدیگر عوض نموده اند.
7-قانون یکی دیگر از اصول جبر بول میباشد در این اصل دو عملگر “.
“, “+” بر روی یک متغیر و معکوس آن بیان می گردد.
(1 (2 در این صورت می توان گفت عمل DR زمانی بین A و برقرار میباشد که منطقاً یکی از آنها صفر و دیگری 1 خواهد بود و در نتیجه خروجی 1 خواهد بود.
و در صورتی که عمل AND بر روی A و صورت پذیرد نتیجه آن حتماً صفر خواهد بود.
8-قانون دمورگان: این قانون در جبر بول که در مورد نفی کردن روابط بیان می شود به عنوان یکی دیگر از تئوری مطرح در این جبر بیان می گردد.
اگر مجموعه J دارای دو متغیر A و B باشد و بخواهیم نفی تابع J را به دست آوریم لذا بر اساس این قانون مراحل ذیل را انجام می دهیم.
الف: هر یک از متغیرهای تابع را نفی می کنیم.
ب: عمل OR را به AND تبدیل می نمایم.
(الف ج: عمل AND را به OR تبدیل می نمائیم.
(ب 9-تئوری دیگری که با توجه به قانون دمورگان می توان نتیجه گرفت تئوری رجعت یا برگشت به حالت قبل از نفی است بدینصورت که اگر متغیر A را دوبار نفی کنیم همان متغیر مجدداً بدست می آید.
یا اگر بخواهیم نفی تابع را بدست آوریم با توجه به قانون دمورگان چون تابع فقط یک متغیر دارد.
10-با استفاده از موارد مطرح شده در تئوری دو و و قانون توزیع پذیری نتیجه دیگری به نام تئوری جذب مطرح می گردد که در ساده کردن روابط مورد استفاده قرار می گیرد مثال اگر مجموعه J دارای دو متغیر باشد که یکی از متغیرها نسبت به دو متغیر AND شده OR شده باشد نتیجه رابطه متغیری خواهد بود که با دو متغیر دیگر OR یا AND شده باشد که هر دو حالت نشان داده شده است.
(1 از دو حالت فوق نتیجه می گیریم که یکی از متغیر با استفاده از اصول بکار گرفته شده جذب یا حذف شده است.
با توجه به ده بند ارائه شده مشاهده می شود جبر بول دارای اصول و تئوری های مختلف میباشد که با عنایت به اصل اوزیع پذیری و دیگر اصول عنوان شده می توان گفت الف: عملگر دودوئی OR “+” جمع را تعریف میکند.
ب: عملگر دودوئی And “.” ضرب را تعریف میکند.
ج: شناسه جمع، 0 است.
د: شناسه ضرب، 1 است.
هـ : معکوس جمع: تفریق است.
و: معکوس ضرب تقسیم میباشد.
اصول هانتینگتون: جبر بول یک ساختار جبری میباشد که با توجه به عناصر یک مجموعه مانند S و عملگرهای OR و AND می توان اصول آن را بیان نمود دانشمندی به نام هانتینگتون در سال 1904 اصول فرموله شده ای را برای بیان استدلالی جبر بول ارائه نمود.
به عبارتی می توان گفت به شرطی جبر بول را می توان بصورت مستدل بیان نمود که اصول ارائه شده توسط هانتینگتون در آن معتبر باشد، این اصول ششگانه عبارتند از 1-مجموعه نسبت به عملگرد OR “+” بسته باشد.
مجموعه نسبت به عملگر AND “.” بسته باشد.
2-عنصر شناسه “1” برای AND “.” وجود داشته باشد.
عنصر شناسه 0 “ OR “+” وجود داشته باشد.
3-مجموعه نسبت به عملگر “+” دارای خاصیت جابجایی باشد.
مجموعه نسبت به عملگر “.” دارای خاصیت جابجایی باشد.
4-مجموعه نسبت به عملگر + توزیع پذیر باشد.
مجموعه نسبت به عملگر .
توزیع پذیر باشد.
5-حداقل در مجموعه S دو عنصر وجود داشته باشد به گونه ای که باشد 6-برای هر عنصر عنصر وجود داشته باشد ( متممA) با توجه به شش اصل مطرح شده در اصول هانتینگتون می توان گفت، اصول هانتینگتون فاقد اصل شرکت پذیری می باشند.
نکته دیگر در این اصول همانگونه که مشاهده می شود این اصول بصورت جفت جفت لیست شده اند که این خاصیت را در جبر بول اصل دوگانگی می نامند.
خاصیت دوگانگی یا قانون Duality با توجه به دو رابطه عنوان شده در قانون توزیع پذیری (1 (2 می توان دریافت که هر یک از روابط را می توان از رابطه دیگری بدست آورد که این موضوع با تغییر عملگرها در هر رابطه قابل استنتاج میباشد.
بنابراین هر دو جمله ایکه دارای این خاصیت باشند یعنی بتوان یکی را با تبدیل عملگرها یا متغیرها بدست آورد به خاصیت دوگانگی معروف است و هر رابطه را Dual رابطه دیگر می نماند.
توابع بول و ساده کردن آن با استفاده از قوانین بول یک تابع بولی به وسیله متغیرهای دودوئی و سمبلهای عملیاتی منطقی تشکیل شده است که به آن یک عبارت جبری منطقی می گویند در حقیقت یک تابع بول رابطهای منطقی بین متغیرها را بیان میکند یک عبارت ممکن است از جملات جبری متعدد و متغیرها تشکیل شده باشد مثلاً جمله یک عبارت سه جمله ای است که از هشت متغیر یا لیترال تشکیل شده است لیترال یک متغیر تک در یک جمله میباشد هدف از دستکاری عبارات جبری بدست آوردن عبارت ساده تر با متغیرهای کمتری باشد.
مثال: تابع روبرو را ساده کنید.
مشاهده می شود با استفاده از قوانین جبر بول عبارت ساده تری از سه جمله که فقط شش لیترال دارد به دست می آید که در نهایت از گیت های کمتری و با ورودی کمتر استفاده می شود.
فرم قانونی یا استاندارد هدف از ساده کردن عبارات منطقی بیان شد ولی در جبر بول فرم دیگری از توابع وجود دارد که به آن فرم استاندارد یا قانونی می گویند در این فرم معمولاً به گونهای عمل می شود که عبارت داده شده به دو روش بصورت استاندارد بدست آیدو 1-در روش اول توابع را بگونه ای ساده می کنیم که در نهایت بصورت عبارات حاصلضرب در آید 2-در روش دوم توابع را بگونه ای ساده می کنیم که در نهایت بصورت عبارات مجموع در آید یک متغیر که به آن حرف می گویند ممکن است بصورت معمولی A یا متمم ظاهر شود در این صورت عبارت حاصلضرب و عبارت مجموع به شکل زیر بیان میشود.
3-عبارت حاصلضرب: در این عبارت متغیرها با عملگر AND بهم مرتبط شده اند مثلاً اگر عبارت دارای سه متغیر باشد عبارت حاصلضرب آن A.B.C خواهد بود.
عبارت مجموع: در این عبارت متغیرها با عملگر OR بهم مربوط شده اند و تشکیل یک عبارت مجموع رأی دهند و A+B+C عبارت نرمال: عبارت حاصلضرب یا به عبارت مجموع است که در آن هیچ متغیری بیش از یک بار ظاهر نمی شود.
مجموع حاصلضرب: در این عبارت متغیرهائی که با عملگر AND بیان شده اند توسط عملگر OR در یک عبارت قرار گرفته اند مثلاً اگر یک تابع چهار متغیری داشته باشیم.
اگر 7-حاصلضرب مجموع: در این عبارت متغیرها که با عملگر OR بیان شده اند توسط عملگر AND در یک عبارت قرار گرفته اند.
اگر 8-فرم استاندارد (از فرم قانونی مجموع حاصلضرب) اگر تابعی دارای چهار متغیر داشته باشیم اگر تابع را به شکل مجموع حاصلضرب در آوریم که در هر عبارت حاصلضرب چهار متغیر یا نفی آنها وجود داشته باشد این عبارت را مجموع حاصلضرب یا ضرب استاندارد یا عبارات کوچک مینترم Minterms می گویند.
مثال: عبارت داده شده را به شکل مینترم بسط دهیم.
عبارت تکراری را حذف می کنیم.
9-با توجه به خاصیت دوگانگی می توان دوال مجموع حاصلضرب یک عبارت یعنی حاصلضرب مجموع آن را داشته باشیم به فرم استاندارد حاصلضرب مجموع جمع استاندارد یا ماکس ترم Maxterm یا عبارت بزرگ می گویند.