Tseytin transformation
সেয়টিন রূপান্তর, বিকল্পভাবে লিখিত সেয়টিন রূপান্তর, একটি নির্বিচারে সমন্বিত লজিক সার্কিট ইনপুট হিসাবে গ্রহণ করে এবং কনজাংক্টিভ নরমাল আকারে (সি. এন. এফ) একটি সম-সন্তোষজনক বুলিয়ান সূত্র তৈরি করে। সূত্রের দৈর্ঘ্য বর্তনীর আকারে রৈখিক। যে ইনপুট ভেক্টরগুলি সার্কিট আউটপুটকে "সত্য" করে তোলে সেগুলি সূত্রকে সন্তুষ্ট করে এমন অ্যাসাইনমেন্টের সাথে 1-থেকে-1 মিল রয়েছে। এটি যে কোনও বর্তনীতে (যে কোনও সূত্র সহ) বর্তনী সন্তোষজনকতার সমস্যাকে 3-সি. এন. এফ সূত্রের সন্তোষজনকতার সমস্যায় পরিণত করে। এটি আবিষ্কার করেন রাশিয়ান বিজ্ঞানী গ্রিগরি সাইটিন। সরল পদ্ধতি হল সার্কিটটিকে বুলিয়ান অভিব্যক্তি হিসাবে লেখা, এবং ডি মরগানের আইন এবং বিতরণমূলক বৈশিষ্ট্য ব্যবহার করে এটিকে সি. এন. এফ-এ রূপান্তর করা। তবে, এর ফলে সমীকরণের আকারের সূচকীয় বৃদ্ধি হতে পারে। সেয়টিন রূপান্তর একটি সূত্র বের করে যার আকার ইনপুট সার্কিটের তুলনায় রৈখিকভাবে বৃদ্ধি পায়। আউটপুট সমীকরণ হল একটি অভিব্যক্তি সমান ধ্রুবক 1 সেট। এই অভিব্যক্তিটি উপ-অভিব্যক্তিগুলির একটি সংমিশ্রণ, যেখানে প্রতিটি উপ-অভিব্যক্তিটির সন্তুষ্টি ইনপুট সার্কিটে একটি একক গেটের যথাযথ ক্রিয়াকলাপকে প্রয়োগ করে। সমগ্র আউটপুট এক্সপ্রেশনের সন্তুষ্টি এইভাবে বোঝায় যে সমগ্র ইনপুট সার্কিট সঠিকভাবে কাজ করছে। প্রতিটি গেটের জন্য, তার আউটপুট প্রতিনিধিত্বকারী একটি নতুন পরিবর্তনশীল চালু করা হয়। একটি ছোট প্রাক-গণনা করা সি. এন. এফ এক্সপ্রেশন যা ইনপুট এবং আউটপুট সম্পর্কিত আউটপুট এক্সপ্রেশনটিতে ("এবং" অপারেশনের মাধ্যমে) সংযুক্ত করা হয়। মনে রাখবেন যে এই গেটগুলিতে ইনপুটগুলি মূল আক্ষরিক বা সাব-গেটের আউটপুটগুলির প্রতিনিধিত্বকারী প্রবর্তিত ভেরিয়েবল হতে পারে। যদিও আউটপুট এক্সপ্রেশনটিতে ইনপুটের চেয়ে বেশি ভেরিয়েবল থাকে, তবে এটি সমান সন্তোষজনক থাকে, যার অর্থ এটি সন্তোষজনক যদি, এবং শুধুমাত্র যদি, মূল ইনপুট সমীকরণ সন্তোষজনক হয়। যখন ভেরিয়েবলগুলির একটি সন্তোষজনক অ্যাসাইনমেন্ট পাওয়া যায়, তখন প্রবর্তিত ভেরিয়েবলগুলির জন্য সেই অ্যাসাইনমেন্টগুলি কেবল বাতিল করা যেতে পারে। একটি চূড়ান্ত ধারা একটি একক আক্ষরিক সঙ্গে সংযুক্ত করা হয়ঃ চূড়ান্ত গেটের আউটপুট পরিবর্তনশীল। যদি এই আক্ষরিকটি পরিপূরক হয়, তবে এই ধারার সন্তুষ্টি আউটপুট অভিব্যক্তিটিকে মিথ্যা করতে বাধ্য করে; অন্যথায় অভিব্যক্তিটি সত্য হতে বাধ্য করা হয়। উদাহরণস্বরূপ নিম্নলিখিত সূত্রটি বিবেচনা করুন। সমস্ত উপ-সূত্র বিবেচনা করুন (সাধারণ পরিবর্তনশীল ব্যতীত): প্রতিটি উপ-সূত্রের জন্য একটি নতুন পরিবর্তনশীল প্রবর্তন করুনঃ সমস্ত প্রতিস্থাপন এবং প্রতিস্থাপনের জন্য সংযোগ করুনঃ সমস্ত প্রতিস্থাপনকে সি. এন. এফ-এ রূপান্তরিত করা যেতে পারে, যেমন। তালিকাভুক্ত গেট উপ-অভিব্যক্তিগুলি কয়েকটি সম্ভাব্য উপ-অভিব্যক্তি যা বিভিন্ন লজিক গেটের জন্য তৈরি করা যেতে পারে। একটি অপারেশন এক্সপ্রেশন-এ, সি একটি আউটপুট হিসাবে কাজ করে; একটি সিএনএফ সাব-এক্সপ্রেশন-এ, সি একটি নতুন বুলিয়ান পরিবর্তনশীল হিসাবে কাজ করে। প্রতিটি ক্রিয়াকলাপের জন্য, সি. এন. এফ উপ-অভিব্যক্তিটি তখনই সত্য হয় যখন সি সমস্ত সম্ভাব্য ইনপুট মানের জন্য বুলিয়ান ক্রিয়াকলাপের চুক্তি মেনে চলে। সহজ কম্বিনেটোরিয়াল লজিক নিম্নলিখিত সার্কিটটি তখনই সত্য বলে প্রমাণিত হয় যখন এর কিছু ইনপুট সত্য হয়, তবে একবারে দুটির বেশি নয়। এটি সমীকরণ প্রয়োগ করে। প্রতিটি গেটের আউটপুটের জন্য একটি পরিবর্তনশীল প্রবর্তন করা হয়; এখানে প্রতিটি লাল রঙে চিহ্নিত করা হয়েছেঃ লক্ষ্য করুন যে ইনপুট হিসাবে x সহ ইনভার্টারের আউটপুটে দুটি পরিবর্তনশীল প্রবর্তন করা হয়েছে। যদিও এটি অপ্রয়োজনীয়, এটি ফলস্বরূপ সমীকরণের সমতাপূর্ণতাকে প্রভাবিত করে না। এখন প্রতিটি গেটকে তার উপযুক্ত সি. এন. এফ সাব-এক্সপ্রেশন দিয়ে প্রতিস্থাপন করুনঃ চূড়ান্ত আউটপুট ভেরিয়েবল হল গেট8 যাতে এই সার্কিটের আউটপুট সত্য হয়, একটি চূড়ান্ত সহজ ধারা সংযুক্ত করা হয়ঃ (গেট8)। এই সমীকরণগুলির সংমিশ্রণের ফলে SAT-এর চূড়ান্ত দৃষ্টান্ত পাওয়া যায়ঃ (গেট1 * x1) * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * এখানে, প্রকৃতপক্ষে আসল সার্কিটের আউটপুট সত্য হওয়ার মানদণ্ড পূরণ করে। একটি ভিন্ন উত্তর খুঁজে পেতে, ধারাটি (x1 * x2 *) সংযুক্ত করা যেতে পারে এবং SAT সমাধানকারী আবার কার্যকর করা যেতে পারে। কিছু নির্বাচিত গেটের জন্য সিএনএফ সাব-এক্সপ্রেশনের একটি সম্ভাব্য ব্যুৎপত্তি হল উপস্থাপিত ডেরিভেশনঃ অথবা দুটি ইনপুট এ এবং বি এবং একটি আউটপুট সি সহ গেট এন ওআর গেট নিম্নলিখিত শর্তগুলি সন্তুষ্ট করেঃ যদি আউটপুট সি সত্য হয়, তবে এর ইনপুট এ বা বি এর মধ্যে কমপক্ষে একটি সত্য হয়, যদি আউটপুট সি মিথ্যা হয়, তবে এর ইনপুট এ এবং বি উভয়ই মিথ্যা হয়। আমরা এই দুটি শর্তকে দুটি প্রভাবের সংমিশ্রণ হিসাবে প্রকাশ করতে পারিঃ কেবল সংযোগ, বিচ্ছিন্নতা এবং নেতিবাচক ফলাফলের সাথে জড়িত সমতুল্য অভিব্যক্তিগুলির সাথে প্রভাবগুলি প্রতিস্থাপন করা যা ইতিমধ্যে প্রায় স্বাভাবিক আকারে রয়েছে। ডানদিকের ধারাটি দুইবার বিতরণ করলে ফল পাওয়া যায় এবং সংযোগের সহযোগীতা প্রয়োগ করলে সি. এন. এফ সূত্র 'নট গেট' পাওয়া যায়, যখন এর ইনপুট এবং আউটপুট একে অপরের বিরোধিতা করে তখন 'নট গেট' সঠিকভাবে কাজ করে। অর্থাৎঃ যদি আউটপুট সি সত্য হয়, ইনপুট এ মিথ্যা হয় যদি আউটপুট সি মিথ্যা হয়, ইনপুট এ সত্য হয় এই শর্তগুলিকে একটি অভিব্যক্তি হিসাবে প্রকাশ করুন যা অবশ্যই সন্তুষ্ট হতে হবেঃ এনওআর গেট এনওআর গেট সঠিকভাবে কাজ করছে যখন নিম্নলিখিত শর্তগুলি থাকেঃ যদি আউটপুট সি সত্য হয়, তবে এ বা বি উভয়ই সত্য নয় যদি আউটপুট সি মিথ্যা হয়, তবে এ এবং বি এর মধ্যে অন্তত একটি সত্য হয় এই শর্তগুলিকে একটি অভিব্যক্তি হিসাবে প্রকাশ করুন যা অবশ্যই সন্তুষ্ট হতে হবেঃ রেফারেন্স জিএস। সেয়টিনঃ প্রপোসিশনাল ক্যালকুলাসে ব্যুৎপত্তির জটিলতা সম্পর্কে। মধ্যেঃ স্লিসেঙ্কো, এ. ও। (এড।) স্টাডিজ ইন কনস্ট্রাকটিভ ম্যাথমেটিক্স অ্যান্ড ম্যাথমেটিকাল লজিক, পার্ট 2, গণিতের সেমিনার, পৃ. 115-125। স্টেক্লভ ম্যাথমেটিকাল ইনস্টিটিউট (1970)। রাশিয়ান থেকে অনুবাদঃ জাপিস্কি নওচনিক সেমিনারোভ লোমি 8 (1968), পৃ. 234-259। জি. এস সেয়টিনঃ প্রপোসিশনাল ক্যালকুলাসে ব্যুৎপত্তির জটিলতা সম্পর্কে। 1966 সালের সেপ্টেম্বরে অনুষ্ঠিত গাণিতিক যুক্তির উপর লেনিনগ্রাদ সেমিনারে উপস্থাপিত। কম্পিউটার বিজ্ঞানে লজিক গেটস লজিক