جالب: منطق عملگرهای منطقی در برنامه نویسی [بایگانی]

salehbagheri

سه شنبه 16 شهریور 1389, 00:14 صبح

MEhdi Sobhani

سه شنبه 16 شهریور 1389, 00:21 صبح

دوستان من سالها پیش یه سؤال عجیب به ذهنم رسیده بود که امروز با دیدن پست یکی از کاربران دوباره برام زنده شد، البته هنوز جوابشو پیدا نکردم میخواستم از دوستان بپرسم که منطق این عملگرها چیه؟ اعدادی که پس میدن از چه الگوریتمی هست؟
من به این نتیجه رسیده بودم که همیشه نتیجه OR در واقع جمع نتیجه XOR و AND هست.
به مثال های زیر توجه کنید:

1 OR 0 = 1
1 XOR 0 = 1
1 AND 0 = 0
OR = XOR + AND

25 OR 15 = 31
25 XOR 15 = 22
25 AND 15 = 9
OR = XOR + AND

خب سؤال اینجاست که اعداد 31 و 22 و 9 بر چه منطقی ایجاد شدند؟ روش خاصی داره؟
باید بر اساس بیت ها ببینید چه کار میکنند .

این یعنی 2
10
این یعنی 3
11
عدد بر مبنای 2 هست .

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

1 AND 1 = 1
0 AND 1 = 0
0 AND 0 = 0

OR اگر یکیشون هم 1 باشه نتیجه 1 رو میده .
و XOR در صورتیکه یکی 0 و یکی 1 باشه این نتیجه رو میده .

حالا براین اساس مثلا 4 در مبنای دو میشه
100

و 5 میشه
101

حالا AND این دو تا میشه :

100

که همون 4 هست

4=100
5=101
------- AND
100=4

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

salehbagheri

سه شنبه 16 شهریور 1389, 00:31 صبح

مثال دوم خودم رو میتونی تشریح کنی؟

MEhdi Sobhani

سه شنبه 16 شهریور 1389, 00:37 صبح

مثال دوم خودم رو میتونی تشریح کنی؟

AND

25=11001
15=01111
---------------
9=01001

OR

25=11001
15=01111
---------------
31=11111

XOR

25=11001
15=01111
---------------
22=10110

salehbagheri

سه شنبه 16 شهریور 1389, 00:43 صبح

ها ! تازه فهمیدم!

یعنی هر عدد رو جداگانه با همتای خودش مقایسه میکنیم! جالب بود!

حالا میتونید ثابت کنید که چرا :
OR = XOR + AND

MEhdi Sobhani

سه شنبه 16 شهریور 1389, 00:46 صبح

ها ! تازه فهمیدم!

یعنی هر عدد رو جداگانه با همتای خودش مقایسه میکنیم! جالب بود!
دقیقا
کلا این عملگرهای منطقی فقط روی 0 و 1 عمل میکنن و معنی دارند .
وقتی روی عددهای دیگه عمل میکنن بازم در مبنای دو روی همون 0 و یکهاشون در جایگاهای یکسان عمل میکنن .

راستش این مورد or = and + xor رو تا بحال بهش دقت نکرده بودم . ولی فلسفش همینه خیلی جالبه که همچین موردی با این کار پیش میاد !!! .
یه جورایی OR بیشترین حالت رو بر میگردونه و AND کمترین حالت رو و XOR هم بین اینها .

میلاد قاضی پور

سه شنبه 16 شهریور 1389, 02:53 صبح

حالا میتونید ثابت کنید که چرا :
OR = XOR + AND
مجموعا چهار حالت برای تساوی ها متصور هست .

در اند اگر هر دو عملگر یک باشند جواب یک میشه و الا صفر(سه حالت باقی مانده سفر)
در اور اگر هر دو عملگر صفر نباشند جواب یک میشه و الا صفر(سه حالت باقی مانده سفر)
در اکسکلوسیو اور اگر هر دو عملگر غیر مساوی باشند جواب یک میشه و الا صفر(سه حالت باقی مانده سفر)

با یه حساب سر انگشتی میشه فهمید در اور که سه تا از حالات یک و یکی صفر هست در واقع نتایج عملگرهای اند و ایکس اور تلفیق شده . چون نتیجه اولین حالت یعنی 0 و 0 در هر دو عملگرهای اند و ایکس اور صفر هست و همچین در اور هم صفر هست اور برابر با (اند + ایکس اور شده ) در غیر اینصورت یعنی اگر نتیجه اولین حالت در دو عملگر اند و ایکس اور با هم دیگه متفاوت بود حاصل محاسبه ی اند + ایکس اور صفر نمیشد و جواب به جای اور چیز دیگری میشد(در هیچ یک از عملگرها تمام حالا با هم برابر نیست) .

میلاد قاضی پور

سه شنبه 16 شهریور 1389, 03:04 صبح

and: xor: or:
0 0= 0 0= 0 0=
0 + 0 0
0 1= 0 1= 0 1
0 + 1 1
1 0= 1 0= 1 0
0 + 1 1
1 1= 1 1= 1 1
1 + 0 1

حامد مصافی

سه شنبه 16 شهریور 1389, 10:54 صبح

چون xor فرمول ندارد (يعني در رياضيات تعريف نشده بود تا اينكه در برنامه نويسي به آن نياز پيدا شد و ايجاد گشت) نمي توان براي اين قضيه اثبات فرمولي ارائه كرد. فقط مي توانيم با بررسي تمامي حالت به صحت آن پي ببريم كه از ابتدا آن را مي دانشتيم!

v1 v2 | xor and or
----------+---------------------
0 0 | 0 0 0
1 0 | 1 0 1
0 1 | 1 0 1
1 1 | 0 1 1

حامد مصافی

سه شنبه 16 شهریور 1389, 11:01 صبح

يه چيز ديگه، رياضيات بولي در سال 1840 توسط جورج بول رياضي دان معروف پايه گذاري شد، به همين دليل ما همچنان در برنامه نويسي اين عملگر ها و انواع رو به نام اون ميشناسيم. خود and و or هم در واقع ضرب و جمع معمولي روي صفر و يك هستند كه فقط 1+1 به به استثنا (مسئله overflow) برابر با يك فرض مي كنيم.
در رياضيات and را با نمادي مانند 8 فارسي و or را با نمادي مانند 7 فارسي (يا همان v) و not را با چيزي مانند ¬ نمايش مي دهند

Salar Ashgi

سه شنبه 16 شهریور 1389, 22:41 عصر

چون xor فرمول ندارد

چرا دارد !
در عالم ریاضیات هیچ چیز بی قانون نیست ، میشه اثبات زیر رو واسش ارائه کرد !

Sajjad.Aghapour

سه شنبه 16 شهریور 1389, 23:13 عصر

در این موارد بحث زیاد است.من کلا علاقه خاصی به معماری ندارم اما گیت های AND و OR در کامپیوتر بیشتر مورد استفاده قرار میگیرند و عملیات بیتی Add, Sub و ... توسط سخت افزار به طور مستقیم پشتیبانی میشه.برای همین لزومی به پیاده سازی الگوریتم ها و کدنویسی پیچیده اسمبلی توسط کامپایلرها برای این منظور نیست.

گیت Xor هم وجود دارد و در IC ها پیاده سازی میشود.نمیدونم زبان برنامه نویسی هست که این عملگرها رو پشتیبانی نکنه یا نه.ولی به نظر من تمام زبانها باید این عملگرها را پشتیبانی کنند...

برادران IC، اگه اشتباه میکنم بگید.خیلی وقته با این مسائل در معماری سروکار نداشتم...:چشمک:

salehbagheri

سه شنبه 16 شهریور 1389, 23:53 عصر

چرا دارد !
در عالم ریاضیات هیچ چیز بی قانون نیست ، میشه اثبات زیر رو واسش ارائه کرد !

میشه در مورد علائمی که استفاده کردی شرح بدی؟

اصل شبه جذب دیگه چیه؟ اون علامت ' به معنای مشتق هست یا معکوس مجموعه؟

Salar Ashgi

چهارشنبه 17 شهریور 1389, 00:01 صبح

میشه در مورد علائمی که استفاده کردی شرح بدی؟

اصل شبه جذب دیگه چیه؟ اون علامت ' به معنای مشتق هست یا معکوس مجموعه؟

صالح جون مگه رشتت کامپیوتر نیست ، چون اینا به وفور تو کتابای منطقی و معماری یافت میشن !

با این حال برات توضیح میدم :

پریم علامت Not یک متغیر منطقیست !
دایره تو پر با علامت جمع ، نشانگر عملگر XOR است !
+ یعنی OR
. یعنی AND
شبه جذب هم یه اصلیه توی مجموعه ها و منطق ، که اگه بخوای بیشتر برات توضیح میدم !

salehbagheri

چهارشنبه 17 شهریور 1389, 00:44 صبح

صالح جون مگه رشتت کامپیوتر نیست ، چون اینا به وفور تو کتابای منطقی و معماری یافت میشن !

نه کامپیوتر نیست خدارا شکر! ما فعلاً سرمون تو مشتق و انتگرال و قوانین چندگانه نیوتنه ...

در کل ممنون.

میلاد قاضی پور

چهارشنبه 17 شهریور 1389, 02:55 صبح

چرا دارد !
در عالم ریاضیات هیچ چیز بی قانون نیست ، میشه اثبات زیر رو واسش ارائه کرد !

منم اینجوری حساب کردم اما شک کردم درست باشه برای همین نذاشتم .

Salar Ashgi

چهارشنبه 17 شهریور 1389, 13:34 عصر

منم اینجوری حساب کردم اما شک کردم درست باشه برای همین نذاشتم .

گر معما حل شود ، آسان شود ! :لبخند:

حامد مصافی

پنج شنبه 18 شهریور 1389, 09:41 صبح

چرا دارد !
در عالم ریاضیات هیچ چیز بی قانون نیست ، میشه اثبات زیر رو واسش ارائه کرد !
بله دوست عزيز، اينو مي دونم، روش شما هم درسته، البته اثبات ساده تري هم وجود داره.

x xor y = x + y - xy

xy + (x xor y) = xy + x + y - xy

.: xy + (x xor y) = x + y

اما منظور من اين بود كه از ابتدا اين اوپراتور توسط جورج بول وارد رياضيات نشده بود و بعداً از علوم كامپيوتر وارد شده (شايد هم اينطور نبوده) اما در كل جمله من اشتباه بود و حق باش شماست

Salar Ashgi

پنج شنبه 18 شهریور 1389, 12:15 عصر

البته اثبات ساده تري هم وجود داره.

ببینید دوست عزیز ، اولا ما در بحث منطق و اپراتورهای منطقی ، عملگری بشکل - (تفاضل) نداریم !
ثانیا اثبات شما ، در حالت کلی قابل قبول نیست ، چرا که همیشه باید از فرض به حکم رسید ، در صورتیکه
شما از درستی حکم ، مساله را اثبات کرده اید ، که این نمیتواند درست باشد !

Web.Designer01

پنج شنبه 18 شهریور 1389, 14:03 عصر

نه کامپیوتر نیست خدارا شکر!

خدا رو شکرش دیگه چی بود؟!:لبخند:
یه چیزی که در مورد XORها متوجه شدم اینه که هر موقع تعداد یکها زوج باشه حاصل صفر میشه،درسته؟
پ.ن:آقا صالح الان دیگه باید مفهوم امضای جناب اوج بلند رو متوجه شید!

salehbagheri

پنج شنبه 18 شهریور 1389, 14:44 عصر

ه چیزی که در مورد XORها متوجه شدم اینه که هر موقع تعداد یکها زوج باشه حاصل صفر میشه،درسته؟

شما در عملگر XOR عدد 1 رو منفی و عدد 0 رو مثبت در نظر بگیرید و با ضرب علامتهای (+ -) میتونید حاصل رو تشخیص بدید.

مثلاً در ریاضیات به این صورت هست:

(+) * (-) = (-)
0 Xor 1 = 1

(+) * (+) = (+)
0 Xor 0 = 0

(-) * (-) = (+)
1 Xor 1 = 0

(-) * (+) = (-)
1 Xor 0 = 1

علیرضا مداح

پنج شنبه 18 شهریور 1389, 15:06 عصر

سلام،
XOR یعنی "یا" ی انحصاری؛ خروجی "تنها" زمانی برای 1 هست که دقیقا" یکی از Operand ها برابر 1 باشند،
بدیهیست خروحی زمانی برابر 1 هست که تعداد 1 ها فرد باشد،/

Web.Designer01

پنج شنبه 18 شهریور 1389, 15:33 عصر

یه چیزی که در مورد XORها متوجه شدم اینه که هر موقع تعداد یکها زوج باشه حاصل صفر میشه،درسته؟

شما در عملگر XOR عدد 1 رو منفی و عدد 0 رو مثبت در نظر بگیرید و با ضرب علامتهای (+ -) میتونید حاصل رو تشخیص بدید.

این دو جمله معادل همه و هر در درسته.

اشتباه است، بدیهیست خروحی زمانی برابر 1 هست که تعداد 1 ها فرد باشد،/

اینم همون چیزیه که ما میگیم دیگه،چیش اشتباهه؟!
ما میگیم خروجی زمانی صفره که تعداد یکا زوجه شما میگی زمانی یکه که تعداد یکا فرده!
همه جملات فوق درسته:لبخند:

حامد مصافی

پنج شنبه 18 شهریور 1389, 15:34 عصر

ببینید دوست عزیز ، اولا ما در بحث منطق و اپراتورهای منطقی ، عملگری بشکل - (تفاضل) نداریم !عبارت زير بديهيست:

x - y = x + (not y)همينطور اين عبارت:

x xor y = x + y - xy

salehbagheri

پنج شنبه 18 شهریور 1389, 15:42 عصر

ما میگیم خروجی زمانی صفره که تعداد یکا زوجه شما میگی زمانی یکه که تعداد یکا فرده!

وقتی آقای مداح میگن اشتباهه اشتباه هست دیگه!

وقتی هر دو Operand صفر هم باشند خروجی صفر میشه ...

Web.Designer01

پنج شنبه 18 شهریور 1389, 15:46 عصر

وقتی هر دو Operand صفر هم باشند خروجی صفر میشه ...
در محاسبه xor فقط به تعداد یکها توجه کنید،صفر ها مهم نیستن.

علیرضا مداح

پنج شنبه 18 شهریور 1389, 15:50 عصر

Mehr_iman (http://barnamenevis.org/forum/member.php?u=152122)@
کمی بیان های دو طرف متفاوت بود،:) پست را اصلاح می کنم،/

PC2st

پنج شنبه 18 شهریور 1389, 19:24 عصر

عبارت زير بديهيست:

x - y = x + (not y)
سمت راست تساوی باید بعلاوهٔ یک هم بشود، چون:

-y = ~y + 1

PC2st

پنج شنبه 18 شهریور 1389, 19:43 عصر

سمت راست تساوی باید بعلاوهٔ یک هم بشود، چون:

-y = ~y + 1
البته این چیزی هم که من نوشتم یک اصل نیست، زیرا به نحوهٔ پیاده‌سازی y- توسط سیستم وابسته است. در اکثر سیستم‌ها 11111111 برابر با منفی ۱ است اما در بعضی سیستم‌ها برابر با منفی صفر بود!
در سیستم‌هایی که 11111111 برابر با منفی صفر است، عبارت شما صحیح است (بنابراین به عنوان یک اصل نمی‌توان y- را برابر با یک عدد دودوئی مشخص در نظر گرفت).

eshpilen

پنج شنبه 18 شهریور 1389, 19:55 عصر

XOR یکی از اجزای اصلی بسیاری از الگوریتم های رمزنگاری هست.
چون اگر یه چیزی رو با یک کلید XOR کنید به یک عبارت نامفهوم تبدیل میشه (بخاطر تصادفی بودن کلید) و دوباره اون عبارت نامفهوم رو اگر با کلید رمزگذاری XOR کنید، دیتای اولیه بدست میاد. البته این روش به تنهایی ضعف های بزرگ و جزیی داره و بنابراین با روشهای مکمل ترکیبش میکنن.