نویسنده : mohammad
Thursday, April 23, 2009
0
comments
ضرب بولی در ساختمان های گسسته
با سلام
از اینکه این مطلب رو با الگوریتم وارشال نذاشتم و یه کم با تاخیر بعد از اون گذاشتم هدف داشتم و الان که می ذارم مطمئن هستم که همه می فهمند و برای همه جا میفته.
ضرب بولی در ساختمان های گسسته
روشی که استاد انوری برای این کار پیشنهاد کردند همان روش ضرب ماتریس هاست که در دبیرستان یاد گرفتیم. به این صورت:
ابتدا سطر اول را باستون اول ضرب می کنیم و حاصل جمع را در درایه اول ماتریس حاصل ضرب قرار می دهیم.این کار را آنقدر ادامه می دهیم تا به آخرین درایه آرایه حاصل ضرب برسیم.
همان طور که می دانید ماترسی بولی ماتریسی است که همه عناصر آن صفر و یکه و ضرب و جمع بولی رو هم در زیر براتون میارم:
1=1*1
0=0*1
0=1*0
0=0*0
***********
1=1+1
1=1+0
1=0+1
0=0+0
0=0*1
0=1*0
0=0*0
***********
1=1+1
1=1+0
1=0+1
0=0+0
روشی جدید برای ضرب بولی دو ماتریس
برای به دست آوردن ضرب بولی دو ماتریس M1 و M2 به صورت زیر عمل می کنیم:
سطر اول از ماتریس M1 و ستون اول ماتریس M2 را در نظر می گیریم.
موقعیت های نظیر این سطر و ستون را بررسی می کنیم.اگر در یک موقعیت خاص هر دو دارای ارزش یک(1) بودند آن موقعیت ماتریس ضرب بولی آنها هم یک(1) است.
یعنی اگر موقعیتی خاص هم هم در سطر مورد نظر و هم در ستون مورد نظر دارای ارزش یک(1) بود آنگاه در ماتریس حاصلضرب هم همان موقعیت ارزش یک(1) می گیرد و در غیر اینصورت دارای ارزش صفر می شود.
برای مثال دو ماتریس زیر را در نظر بگیرید:
برای به دست آوردن ضرب بولی دو ماتریس M1 و M2 به صورت زیر عمل می کنیم:
سطر اول از ماتریس M1 و ستون اول ماتریس M2 را در نظر می گیریم.
موقعیت های نظیر این سطر و ستون را بررسی می کنیم.اگر در یک موقعیت خاص هر دو دارای ارزش یک(1) بودند آن موقعیت ماتریس ضرب بولی آنها هم یک(1) است.
یعنی اگر موقعیتی خاص هم هم در سطر مورد نظر و هم در ستون مورد نظر دارای ارزش یک(1) بود آنگاه در ماتریس حاصلضرب هم همان موقعیت ارزش یک(1) می گیرد و در غیر اینصورت دارای ارزش صفر می شود.
برای مثال دو ماتریس زیر را در نظر بگیرید:
0 0 0 1 0 1 1
0 1 1 0 0 1 0
1 1 0 1 0 1 1
1 0 0
0 1 1 0 0 1 0
1 1 0 1 0 1 1
1 0 0
سطر اول ماتریس سمت راست را که بولد شده با ستون اول ماتریس سمت چپ که به صورت ساده نوشته شده در نظر بگیرید.(هر دو با رنگ قرمز مشخص شده)
حالا موقعیت ها را تک تک بررسی می کنیم:
هر دو ماتریس در موقعیت های یک مساویند یعنی هر دو آنها دارای عنصر اولی هستند که ارزش یک(1) دارد پس عنصر اول ماتریس حاصلضرب دارای ارزش یک(1) می شود.(این عناصر با رنگ آبی مشخص شده)
حالا موقعیت ها را تک تک بررسی می کنیم:
هر دو ماتریس در موقعیت های یک مساویند یعنی هر دو آنها دارای عنصر اولی هستند که ارزش یک(1) دارد پس عنصر اول ماتریس حاصلضرب دارای ارزش یک(1) می شود.(این عناصر با رنگ آبی مشخص شده)
موفق باشید.
