Tseytin transformation
سیٹین ٹرانسفارمیشن، متبادل طور پر لکھی گئی سیٹین ٹرانسفارمیشن، ایک صوابدیدی مشترکہ منطق سرکٹ کو ان پٹ کے طور پر لیتی ہے اور کنجکٹو نارمل شکل (CNF) میں ایک مساوی اطمینان بخش بولین فارمولا تیار کرتی ہے۔ فارمولے کی لمبائی سرکٹ کے سائز میں لکیری ہے۔ ان پٹ ویکٹر جو سرکٹ آؤٹ پٹ کو "سچ" بناتے ہیں وہ اسائنمنٹس کے ساتھ 1 سے 1 کے خط و کتابت میں ہوتے ہیں جو فارمولے کو پورا کرتے ہیں۔ یہ کسی بھی سرکٹ (بشمول کسی بھی فارمولے) پر سرکٹ کی اطمینان کے مسئلے کو 3-سی این ایف فارمولوں پر اطمینان کے مسئلے تک کم کر دیتا ہے۔ اسے روسی سائنسدان گریگوری سیٹین نے دریافت کیا تھا۔ محرک بے وقوف نقطہ نظر یہ ہے کہ سرکٹ کو بولین اظہار کے طور پر لکھا جائے، اور اسے سی این ایف میں تبدیل کرنے کے لیے ڈی مورگن کے قانون اور تقسیم کی خاصیت کا استعمال کیا جائے۔ تاہم، اس کے نتیجے میں مساوات کے سائز میں تیزی سے اضافہ ہو سکتا ہے۔ سیٹین ٹرانسفارمیشن ایک فارمولہ آؤٹ پٹ کرتا ہے جس کا سائز ان پٹ سرکٹ کے مقابلے میں لکیری طور پر بڑھتا ہے۔ آؤٹ پٹ مساوات ایک اظہار کے برابر مستقل 1 سیٹ ہے۔ یہ اظہار ذیلی تاثرات کا ایک مجموعہ ہے، جہاں ہر ذیلی اظہار کا اطمینان ان پٹ سرکٹ میں ایک ہی گیٹ کے مناسب عمل کو نافذ کرتا ہے۔ پورے آؤٹ پٹ اظہار کا اطمینان اس طرح نافذ کرتا ہے کہ پورا ان پٹ سرکٹ مناسب طریقے سے کام کر رہا ہے۔ ہر گیٹ کے لیے، اس کے آؤٹ پٹ کی نمائندگی کرنے والا ایک نیا متغیر متعارف کرایا جاتا ہے۔ ایک چھوٹا سا پہلے سے حساب شدہ CNF اظہار جو ان پٹ اور آؤٹ پٹ سے متعلق ہے ("اور" آپریشن کے ذریعے) آؤٹ پٹ اظہار میں شامل کیا جاتا ہے۔ نوٹ کریں کہ ان دروازوں کے لیے ان پٹ یا تو اصل لفظی ہو سکتے ہیں یا ذیلی دروازوں کے آؤٹ پٹ کی نمائندگی کرنے والے متعارف شدہ متغیر ہو سکتے ہیں۔ اگرچہ آؤٹ پٹ کے اظہار میں ان پٹ سے زیادہ متغیرات ہوتے ہیں، لیکن یہ مساوی اطمینان بخش رہتا ہے، جس کا مطلب ہے کہ یہ تب ہی تسلی بخش ہوتا ہے جب اصل ان پٹ مساوات تسلی بخش ہو۔ جب متغیرات کی تسلی بخش تفویض مل جاتی ہے، تو متعارف شدہ متغیرات کے لیے ان تفویض کو آسانی سے مسترد کیا جا سکتا ہے۔ ایک حتمی شق کو ایک واحد لفظی کے ساتھ منسلک کیا جاتا ہے: حتمی گیٹ کا آؤٹ پٹ متغیر۔ اگر اس لفظی تکمیل کی جاتی ہے، تو اس شق کا اطمینان آؤٹ پٹ کے اظہار کو غلط کرنے پر مجبور کرتا ہے ؛ بصورت دیگر اظہار کو سچ ہونے پر مجبور کیا جاتا ہے۔ مثال کے طور پر درج ذیل فارمولے پر غور کریں۔ تمام ذیلی فارمولوں پر غور کریں (سادہ متغیرات کو چھوڑ کر): ہر ذیلی فارمولہ کے لیے ایک نیا متغیر متعارف کروائیں: تمام متبادلات کو جوڑ دیں اور اس کے لیے متبادل: تمام متبادلات کو سی این ایف میں تبدیل کیا جا سکتا ہے، مثال کے طور پر۔ گیٹ کے ذیلی تاثرات کچھ ممکنہ ذیلی تاثرات ہیں جو مختلف منطق کے دروازوں کے لیے بنائے جا سکتے ہیں۔ آپریشن کے اظہار میں، سی آؤٹ پٹ کے طور پر کام کرتا ہے ؛ سی این ایف کے ذیلی اظہار میں، سی ایک نئے بولین متغیر کے طور پر کام کرتا ہے۔ ہر آپریشن کے لیے، سی این ایف کا ذیلی اظہار درست ہے اگر اور صرف اس صورت میں جب سی تمام ممکنہ ان پٹ ویلیوز کے لیے بولین آپریشن کے معاہدے پر عمل پیرا ہو۔ سادہ مشترکہ منطق مندرجہ ذیل سرکٹ اس وقت درست ہوتا ہے جب اس کے کم از کم کچھ ان پٹ درست ہوتے ہیں، لیکن ایک وقت میں دو سے زیادہ نہیں۔ یہ مساوات کو لاگو کرتا ہے۔ ہر گیٹ کی آؤٹ پٹ کے لیے ایک متغیر متعارف کرایا جاتا ہے۔ یہاں ہر ایک کو سرخ رنگ میں نشان زد کیا گیا ہے: نوٹ کریں کہ x کے ساتھ ان پٹ والے انورٹر کی آؤٹ پٹ میں دو متغیرات متعارف کرائے گئے ہیں۔ اگرچہ یہ بے کار ہے، لیکن یہ نتیجے میں آنے والی مساوات کی مساوات کو متاثر نہیں کرتا ہے۔ اب ہر گیٹ کو اس کے مناسب سی این ایف ذیلی اظہار سے تبدیل کریں: حتمی آؤٹ پٹ متغیر گیٹ 8 ہے تاکہ اس بات کو نافذ کیا جا سکے کہ اس سرکٹ کی آؤٹ پٹ درست ہو، ایک حتمی سادہ شق شامل کی گئی ہے: (گیٹ 8)۔ ان مساوات کو یکجا کرنے سے SAT کی حتمی مثال میں نتیجہ نکلتا ہے: (گیٹ 1. x1)....................................................................................... یہاں، اصل سرکٹ کے درست آؤٹ پٹ کے معیار پر پورا اترتا ہے۔ ایک مختلف جواب تلاش کرنے کے لیے، شق (x1 * x2 *) کو شامل کیا جا سکتا ہے اور SAT حل کنندہ کو دوبارہ عمل میں لایا جا سکتا ہے۔ پیش کردہ مشتق کچھ منتخب کردہ گیٹس کے لیے CNF ذیلی اظہار کا ایک ممکنہ مشتق ہے: یا دو ان پٹ A اور B اور ایک آؤٹ پٹ C کے ساتھ گیٹ A OR گیٹ درج ذیل شرائط کو پورا کرتا ہے: اگر آؤٹ پٹ C درست ہے، تو اس کے کم از کم ایک ان پٹ A یا B درست ہے، اگر آؤٹ پٹ C غلط ہے، تو اس کے دونوں ان پٹ A اور B غلط ہیں۔ ہم ان دو شرائط کو دو مضمرات کے امتزاج کے طور پر ظاہر کر سکتے ہیں: مضمرات کو مساوی تاثرات کے ساتھ تبدیل کرنا جس میں صرف امتزاج، اختلاط، اور نفی شامل ہیں جو پہلے سے ہی تقریبا مشترکہ معمول کی شکل میں ہے۔ دائیں طرف کی شق کو دو بار تقسیم کرنے اور کنجکشن کی ایسوسی ایٹیویٹی کو لاگو کرنے سے CNF فارمولا NOT گیٹ ملتا ہے جب اس کا ان پٹ اور آؤٹ پٹ ایک دوسرے کی مخالفت کرتے ہیں تو NOT گیٹ صحیح طریقے سے کام کر رہا ہوتا ہے۔ یعنی: اگر آؤٹ پٹ C درست ہے، تو ان پٹ A غلط ہے اگر آؤٹ پٹ C غلط ہے، تو ان پٹ A درست ہے ان شرائط کو ایک اظہار کے طور پر ظاہر کرتا ہے جسے پورا کرنا ضروری ہے: NOR گیٹ NOR گیٹ صحیح طریقے سے کام کر رہا ہے جب مندرجہ ذیل شرائط برقرار رہتی ہیں: اگر آؤٹ پٹ C درست ہے، تو نہ ہی A یا B درست ہیں اگر آؤٹ پٹ C غلط ہے، تو A اور B میں سے کم از کم ایک درست تھا ان شرائط کو ایک اظہار کے طور پر ظاہر کرتا ہے جسے پورا کرنا ضروری ہے: حوالہ جات G. S. سیٹین: پروپوزیشنل کیلکولس میں مشتق کی پیچیدگی پر۔ میں: سلسینکو، اے او۔ (ایڈ۔) تعمیری ریاضی اور ریاضیاتی منطق میں مطالعہ، حصہ دوم، ریاضی میں سیمینار، پی پی۔ 115-125۔ اسٹیکلوف ریاضیاتی ادارہ (1970)۔ روسی سے ترجمہ کیا گیا: Zapiski Nauchnykh Seminarov LOMI 8 (1968)، پی۔ 234-259۔ جی۔ ایس۔ سیٹین: پروپوزیشنل کیلکولس میں مشتق کی پیچیدگی پر۔ ستمبر 1966 میں منعقدہ ریاضیاتی منطق پر لینن گراڈ سیمینار میں پیش کیا گیا۔ کمپیوٹر سائنس میں منطق گیٹس منطق