ساده سازی عبارات منطقی (جبر مجموعه ها)

[ashoori]

باسلام
دوستان سوالی داشتم در رابطه با ساده سازی عبارات منطقی، دوستانی که با ریاضیات آشنایی دارند لطفا بنده را راهنمایی بفرمایند.
فرض کنید علامت "|" اجتماع و علامت "&" اشتراک
چه الگوریتمی پیشنهاد می کنید که برای مثال عبارت " (A|B)&(C|D) "را تبدیل به عبارت
" (A&C)|(B&C)|(A&D)|(B&D) " نماید.
به عبارتی مجموعه ای از اشتراکات که باهم اجتماع شده اند.
عبارت منطقی ممکن است به هر شکل از پیچیدگی باشد.
باتشکر

[یوسف زالی]

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

[ashoori]

باتشکر از توجه شما. بله بجای ساده سازی بهتر همون بسط درسته.

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

[یوسف زالی]

فرمول دمورگان پیاده کردن که کاری نداره.
شما یک سری متغیر دارید، یک سری عملگر که در اینجا به جای + و - می شه & و |
قوانین دمورگان:


(A1 opA1 A2 opA2 A3..) opp (B1 opB1 B2 opB2 B3..) = (A1 opp (B1 opB1 B2 opB2 B3..)) opA1 (A2 opp (B1 opB1 B2 opB2 B3..)) opA2 ..
then:
(A1 opp (B1 opB1 B2 opB2 B3..)) = (A1 opp B1) opB1 (A1 opp B2) opB2 ..

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