সিঁড়ি। এন্ট্রি গ্রুপ। উপকরণ। দরজা. তালা। ডিজাইন

সংজ্ঞা 1.সংযোজক একপদ (প্রাথমিক সংযোগ)ভেরিয়েবল হল এই ভেরিয়েবল বা তাদের নেগেশানের সমন্বয়।

উদাহরণ স্বরূপ, একটি প্রাথমিক সংযোজন।

সংজ্ঞা 2।বিভক্তিমূলক একপদ (প্রাথমিক বিভক্তি)ভেরিয়েবল থেকে এই ভেরিয়েবলের বিচ্ছিন্নতা বা তাদের নেতিবাচকতা।

উদাহরণ স্বরূপ, একটি প্রাথমিক বিচ্ছিন্নতা।

সংজ্ঞা 3.একটি সূত্র যা একটি প্রদত্ত প্রস্তাবিত বীজগণিত সূত্রের সমতুল্য এবং প্রাথমিক সংযোজক মনোমিয়ালগুলির একটি বিভক্তি বলা হয় বিচ্ছিন্ন স্বাভাবিক ফর্ম(DNF) এই সূত্রের।

উদাহরণ স্বরূপ,- ডিএনএফ।

সংজ্ঞা 4.একটি সূত্র যা একটি প্রদত্ত প্রস্তাবনামূলক বীজগণিত সূত্রের সমতুল্য এবং প্রাথমিক ডিসজংক্টিভ মনোমিয়ালগুলির একটি সংমিশ্রণ বলে সংযোজক স্বাভাবিক ফর্ম(CNF) এই সূত্রের।

উদাহরণ স্বরূপ, – কেএনএফ।

প্রতিটি প্রস্তাবিত বীজগণিত সূত্রের জন্য একজন বিচ্ছিন্ন এবং সংযোজক স্বাভাবিক ফর্মগুলির একটি সেট খুঁজে পেতে পারেন।

স্বাভাবিক ফর্ম নির্মাণের জন্য অ্যালগরিদম

যৌক্তিক বীজগণিতের সমতা ব্যবহার করে, সূত্রের সমস্ত মৌলিক ক্রিয়াকলাপগুলি প্রতিস্থাপন করুন: সংযোগ, বিচ্ছিন্নতা, অস্বীকার:

ডবল নেতিবাচক পরিত্রাণ পান.

প্রয়োজনে, সংযোগ এবং বিচ্ছিন্নতার ক্রিয়াকলাপে বিতরণ এবং শোষণ সূত্রের বৈশিষ্ট্যগুলি প্রয়োগ করুন।

2.6। নিখুঁত বিচ্ছিন্ন এবং নিখুঁত সংযোজক স্বাভাবিক ফর্ম

যেকোন বুলিয়ান ফাংশনের ডিএনএফ এবং সিএনএফ আকারে অনেকগুলি উপস্থাপনা থাকতে পারে। এই উপস্থাপনাগুলির মধ্যে একটি বিশেষ স্থান নিখুঁত DNF (SDNF) এবং নিখুঁত CNF (SCNF) দ্বারা দখল করা হয়েছে।

সংজ্ঞা 1. নিখুঁত বিচ্ছিন্ন স্বাভাবিক ফর্ম(SDNF) হল একটি DNF যেখানে প্রতিটি কনজেক্টিভ মনোমিয়াল সেট থেকে প্রতিটি ভেরিয়েবলকে ঠিক একবারই ধারণ করে, হয় নিজেই বা এর নেগেশান।

কাঠামোগতভাবে, প্রতিটি প্রস্তাবনামূলক বীজগণিত সূত্রের জন্য SDNF একটি DNF-তে হ্রাস করা হয়েছে নিম্নরূপ সংজ্ঞায়িত করা যেতে পারে:

সংজ্ঞা 2। নিখুঁত বিচ্ছিন্ন স্বাভাবিক ফর্মএকটি প্রস্তাবনামূলক বীজগণিত সূত্রের (SDNF) এর DNF বলা হয়, যার নিম্নলিখিত বৈশিষ্ট্য রয়েছে:

সংজ্ঞা 3. পারফেক্ট কনজেক্টিভ স্বাভাবিক ফর্ম(SCNF) হল একটি CNF যেখানে প্রতিটি বিচ্ছিন্নতামূলক মনোমিয়্যাল সেট থেকে প্রতিটি পরিবর্তনশীলকে ঠিক একবার ধারণ করে, এবং হয় নিজেই বা এর নেতিবাচকতা প্রদর্শিত হয়।

কাঠামোগতভাবে, CNF-তে হ্রাস করা প্রতিটি প্রস্তাবনা বীজগণিত সূত্রের জন্য SCNF নিম্নরূপ সংজ্ঞায়িত করা যেতে পারে।

সংজ্ঞা 4. পারফেক্ট কনজেক্টিভ স্বাভাবিক ফর্মএকটি প্রদত্ত প্রস্তাবিত বীজগণিত সূত্রের (SCNF) একটি CNF বলা হয় যা নিম্নলিখিত বৈশিষ্ট্যগুলিকে সন্তুষ্ট করে।

উপপাদ্য ঘ.ভেরিয়েবলের প্রতিটি বুলিয়ান ফাংশন যা অভিন্নভাবে মিথ্যা নয়, SDNF-এ এবং একটি অনন্য উপায়ে উপস্থাপন করা যেতে পারে।

SDNF খোঁজার পদ্ধতি

১ম পদ্ধতি

২য় পদ্ধতি

লাইনগুলি নির্বাচন করুন যেখানে সূত্রটি মান 1 নেয়;

আমরা এই শর্তে সংযোগের একটি বিভক্তি রচনা করি যে যদি একটি ভেরিয়েবল 1 এর মান সহ সংযোগে অন্তর্ভুক্ত করা হয় তবে আমরা এই চলকটি লিখে রাখি; যদি 0 এর মান দিয়ে থাকে তবে এর অস্বীকার। আমরা SDNF পাই।

উপপাদ্য 2।ভেরিয়েবলের প্রতিটি বুলিয়ান ফাংশন যা অভিন্নভাবে সত্য নয় তা SCNF-এ এবং একটি অনন্য উপায়ে উপস্থাপন করা যেতে পারে।

SCNF খোঁজার পদ্ধতি

১ম পদ্ধতি- সমতুল্য রূপান্তর ব্যবহার করে:

২য় পদ্ধতি- সত্য টেবিল ব্যবহার করে:

লাইনগুলি নির্বাচন করুন যেখানে সূত্রটি 0 মান নেয়;

আমরা এই শর্তে বিভক্তিগুলির একটি সংমিশ্রণ রচনা করি যে যদি একটি চলকটি 0 এর মানের সাথে বিচ্ছিন্নতার মধ্যে অন্তর্ভুক্ত করা হয় তবে আমরা এই চলকটি লিখে রাখি; যদি 1 এর মান সহ, তবে এর অস্বীকার। আমরা SKNF পাই।

উদাহরণ 1. CNF ফাংশন গঠন করুন।

সমাধান

চলকগুলির রূপান্তরের নিয়মগুলি ব্যবহার করে সংযোগকারী "" বাদ দেওয়া যাক:

= /ডি মরগানের আইন এবং দ্বিগুণ অস্বীকার / =

/বন্টনমূলক আইন/ =

উদাহরণ 2। DNF এর সূত্রটি দিন।

সমাধান

আসুন ব্যবহার করে লজিক্যাল অপারেশন প্রকাশ করি এবং:

= /আসুন নেগেটিভকে ভেরিয়েবল হিসেবে শ্রেণীবদ্ধ করি এবং ডবল নেগেটিভ কমিয়ে দেই/ =

=/বন্টন আইন/।

উদাহরণ 3.সূত্রটি DNF এবং SDNF-এ লিখ।

সমাধান

যুক্তির সূত্র ব্যবহার করে, আমরা এই সূত্রটিকে এমন একটি ফর্মে কমিয়ে দিই যেখানে শুধুমাত্র প্রাথমিক সংযোগের বিচ্ছিন্নতা রয়েছে। ফলস্বরূপ সূত্রটি কাঙ্খিত DNF হবে:

SDNF তৈরি করতে, আসুন এই সূত্রের জন্য একটি সত্য সারণী তৈরি করি:

আমরা টেবিলের সেই সারিগুলিকে চিহ্নিত করি যেখানে সূত্র (শেষ কলাম) মান 1 নেয়৷ এই জাতীয় প্রতিটি সারির জন্য, আমরা একটি সূত্র লিখি যা এই সারির ভেরিয়েবলের সেটে সত্য:

লাইন 1: ;

লাইন 3: ;

লাইন 5:

এই তিনটি সূত্রের বিভক্তি শুধুমাত্র 1, 3, 5 লাইনের ভেরিয়েবলের সেটে মান 1 নেবে এবং তাই হবে কাঙ্খিত নিখুঁত ডিসজংক্টিভ নরমাল ফর্ম (PDNF):

উদাহরণ 4.দুটি উপায়ে SKNF-এ সূত্রটি আনুন:

ক) সমতুল্য রূপান্তর ব্যবহার করে;

খ) একটি সত্য টেবিল ব্যবহার করে।

সমাধান:

আসুন দ্বিতীয় প্রাথমিক বিভেদকে রূপান্তর করি:

সূত্রটি এর মত দেখাচ্ছে:

খ) এই সূত্রের জন্য একটি সত্য সারণী আঁকুন:

আমরা টেবিলের সেই সারিগুলিকে চিহ্নিত করি যেখানে সূত্রটি (শেষ কলাম) 0 মান নেয়৷ এই জাতীয় প্রতিটি সারির জন্য, আমরা একটি সূত্র লিখি যা এই সারির ভেরিয়েবলের সেটে সত্য:

লাইন 2: ;

লাইন 6:

এই দুটি সূত্রের সংমিশ্রণটি শুধুমাত্র 2 এবং 6 লাইনের ভেরিয়েবলের সেটে মান 0 নেবে, এবং তাই কাঙ্ক্ষিত নিখুঁত কনজেক্টিভ নরমাল ফর্ম (PCNF):

স্বাধীন সমাধানের জন্য প্রশ্ন এবং কাজ

1. সমতুল্য রূপান্তর ব্যবহার করে, সূত্রগুলিকে DNF-তে কমিয়ে দিন:

2. সমতুল্য রূপান্তর ব্যবহার করে, সূত্রগুলিকে CNF-এ আনুন:

3. দ্বিতীয় বন্টনমূলক আইন ব্যবহার করে, DNF কে CNF এ রূপান্তর করুন:

ক) ;

4. প্রদত্ত ডিএনএফগুলিকে এসডিএনএফ-এ রূপান্তর করুন:

5. প্রদত্ত CNF কে SCNF এ রূপান্তর করুন:

6. প্রদত্ত যৌক্তিক সূত্রগুলির জন্য, SDNF এবং SCNF দুটি উপায়ে তৈরি করুন: সমতুল্য রূপান্তর ব্যবহার করে এবং একটি সত্য সারণী ব্যবহার করে।

খ) ;

আসুন একটি প্রাথমিক বিভক্তির ধারণাটি প্রবর্তন করি।

একটি প্রাথমিক বিভক্তি হল ফর্মের একটি অভিব্যক্তি

যৌক্তিক ফাংশনের কনজেক্টিভ নরমাল ফর্ম (CNF) হল পেয়ারওয়াইজ স্বতন্ত্র প্রাথমিক বিভক্তির যেকোনো সীমিত সেটের সংযোগ। উদাহরণস্বরূপ, লজিক্যাল ফাংশন

প্রাথমিক বিচ্ছিন্নতার সংযোগগুলিকে উপস্থাপন করে। অতএব, তারা conjunctive স্বাভাবিক আকারে লেখা হয়.

একটি নির্বিচারে লজিক্যাল ফাংশন, একটি বিশ্লেষণাত্মক অভিব্যক্তি দ্বারা সংজ্ঞায়িত, নির্বাহের মাধ্যমে সিএনএফ-এ হ্রাস করা যেতে পারে পরবর্তী অপারেশন:

একটি যৌক্তিক অভিব্যক্তিতে নেগেশান অপারেশন প্রয়োগ করা হলে বিপরীত নিয়ম ব্যবহার করা;

গুণের ক্ষেত্রে বন্টন স্বতঃসিদ্ধ ব্যবহার করা:

শোষণ অপারেশনের ব্যবহার:

পুনরাবৃত্ত ভেরিয়েবলের ব্যত্যয় বা তাদের অস্বীকারের ক্ষেত্রে ব্যতিক্রম;

একটি ছাড়া সমস্ত অভিন্ন প্রাথমিক বিভেদ অপসারণ;

একই সাথে একটি পরিবর্তনশীল এবং এর অস্বীকৃতি অন্তর্ভুক্ত করে এমন সমস্ত বিভেদ অপসারণ করা।

তালিকাভুক্ত ক্রিয়াকলাপগুলির বৈধতা যুক্তিবিদ্যার বীজগণিতের মৌলিক স্বতঃসিদ্ধ এবং অভিন্ন সম্পর্কগুলি থেকে অনুসরণ করে।

একটি সমন্বিত স্বাভাবিক ফর্মকে নিখুঁত বলা হয় যদি এতে অন্তর্ভুক্ত প্রতিটি প্রাথমিক বিচ্ছিন্নতা প্রত্যক্ষ বা বিপরীত আকারে, ফাংশনটি নির্ভর করে এমন সমস্ত ভেরিয়েবল থাকে।

CNF থেকে নিখুঁত CNF-তে রূপান্তর নিম্নলিখিত ক্রিয়াকলাপগুলি সম্পাদন করে সঞ্চালিত হয়:

ভেরিয়েবলের সংযোগ এবং তাদের অস্বীকারের প্রতিটি প্রাথমিক বিভক্তির সংযোজন, যদি সেগুলি এই প্রাথমিক বিভক্তিতে অন্তর্ভুক্ত না হয়;

বিতরণের স্বতঃসিদ্ধ ব্যবহার করে;

একটি ছাড়া সমস্ত অভিন্ন প্রাথমিক বিভেদ অপসারণ করা।

নিখুঁত CNF-এ যে কোনো লজিক্যাল ফাংশন ব্যতীত উপস্থাপন করা যেতে পারে

একইভাবে এক () এর সমান। স্বতন্ত্র সম্পত্তিএকটি নিখুঁত CNF হল যে এটিতে একটি লজিক্যাল ফাংশনের উপস্থাপনা অনন্য।

একটি নিখুঁত CNF ফাংশনে অন্তর্ভুক্ত প্রাথমিক ব্যবধানগুলিকে শূন্য উপাদান বলা হয়। একটি নিখুঁত CNF-এ অন্তর্ভুক্ত প্রতিটি শূন্য উপাদান পরিবর্তনশীল মানের একক সেটে অদৃশ্য হয়ে যায়, যা ফাংশনের শূন্য সেট। ফলস্বরূপ, একটি লজিক্যাল ফাংশনের শূন্য সেটের সংখ্যা তার নিখুঁত CNF-এ অন্তর্ভুক্ত শূন্য উপাদানগুলির সংখ্যার সাথে মিলে যায়।

নিখুঁত CNF-এ শূন্যের যৌক্তিক ফাংশন ধ্রুবককে শূন্যের 2nগঠক দ্বারা উপস্থাপিত করা হয়। কম্পাইল করার জন্য একটি নিয়ম প্রণয়ন করা যাক SKNF যৌক্তিকচিঠিপত্র টেবিল অনুযায়ী ফাংশন.

চিঠিপত্রের সারণীর প্রতিটি সারির জন্য যেখানে ফাংশনটি শূন্যের সমান, সমস্ত ভেরিয়েবলের একটি প্রাথমিক বিচ্ছিন্নতা সংকলিত হয়। এই ক্ষেত্রে, বিচ্ছিন্নতা পরিবর্তনশীলকে অন্তর্ভুক্ত করে যদি এর মান শূন্য হয়, অথবা যদি তার মান একের সমান হয় তাহলে অস্বীকার করা হয়। ফলস্বরূপ প্রাথমিক বিভক্তিগুলি একটি সংযোগ চিহ্ন দ্বারা একত্রিত হয়।

উদাহরণ 3.4.লজিক্যাল ফাংশন z(x), চিঠিপত্র সারণি 2.2 দ্বারা প্রদত্ত, আমরা নিখুঁত কনজেক্টিভ ফর্ম সংজ্ঞায়িত করি।

টেবিলের প্রথম সারির জন্য, যা ফাংশন 000 এর শূন্য সেটের সাথে মিলে যায়, আমরা শূন্যের উপাদান খুঁজে পাই। দ্বিতীয়, তৃতীয় এবং পঞ্চম লাইনের জন্য অনুরূপ ক্রিয়াকলাপ সম্পাদন করার পরে, আমরা প্রয়োজনীয় নিখুঁত CNF ফাংশন নির্ধারণ করি:

এটি লক্ষ করা উচিত যে যে ফাংশনগুলির ইউনিট সেটের সংখ্যা শূন্য সেটের সংখ্যা অতিক্রম করে, সেগুলিকে SCNF আকারে লিখতে এবং এর বিপরীতে এটি আরও কমপ্যাক্ট।

উদাহরণ। CNF সূত্র খুঁজুন

~ ~

নিম্নলিখিত অ্যালগরিদম ব্যবহার করে SDNF-এর নিখুঁত বিচ্ছিন্ন স্বাভাবিক ফর্ম তৈরি করা যেতে পারে:

1. = 1. DNF অ্যালগরিদম

2. = 2. DNF অ্যালগরিদম

3. = 3. DNF অ্যালগরিদম

4. = 4. DNF অ্যালগরিদম

5. অভিন্নভাবে মিথ্যা পদগুলি বাদ দিন, যেমন ফর্মের শর্তাবলী৷

6. অনুপস্থিত ভেরিয়েবল দিয়ে অবশিষ্ট পদগুলি সম্পূর্ণ করুন

7. পয়েন্ট 4 পুনরাবৃত্তি করুন।

উদাহরণ। SDNF সূত্র খুঁজুন।

~

SCNF তৈরি করতে, আপনি নিম্নলিখিত স্কিমটি ব্যবহার করতে পারেন:

উদাহরণ। SDNF সূত্র খুঁজুন।

~

এটি পরিচিত (উপাদ্য 2.11, 2.12) যে SDNF এবং SCNF সূত্র দ্বারা স্বতন্ত্রভাবে সংজ্ঞায়িত করা হয়েছে এবং তাই, সূত্রের সত্য সারণী ব্যবহার করে এগুলি তৈরি করা যেতে পারে।

সত্য সারণী অনুসারে SDNF এবং SCNF গঠনের স্কিমটি নীচে দেওয়া হল, সূত্রের জন্য ~ :

			~
			1 0 1 0 1 1 0 1	SDNF; এসকেএনএফ।

2.2। ব্যায়াম।

2.2.1 নীচে বুলিয়ান এক্সপ্রেশনগুলি রয়েছে৷ বুলের যুক্তিবিদ্যার সূত্র ব্যবহার করে যতটা সম্ভব আপনার বৈকল্পিক অভিব্যক্তিগুলিকে সরল করুন। তারপর আসলটির সাথে আপনার সরলীকৃত অভিব্যক্তির তুলনা করতে সত্য সারণী ব্যবহার করুন।

2.2.2। SDNF (সারণী 1) এ হ্রাস করে f 1 এবং f 2 এর সমতুল্যতার প্রশ্নটি স্পষ্ট করুন।

2.2.3। সাধারণীকৃত এবং বুলিয়ান নীতি (সারণী 1) ব্যবহার করে f 3 এর জন্য দ্বৈত ফাংশন খুঁজুন। ফলাফল তুলনা করুন.

№	চ 1	চ 2	চ 3

2.3। প্রশ্ন নিয়ন্ত্রণ করুন।

2.3.1। একটি বিবৃতি সংজ্ঞায়িত করুন।

2.3.2। একটি বিবৃতিতে প্রধান ক্রিয়াকলাপ তালিকাভুক্ত করুন।

2.3.3। একটি সত্য টেবিল কি?

2.3.4। নিম্নলিখিত সূত্রের জন্য সত্য সারণী তৈরি করুন:

~ ~ ~ ;

2.3.5। ক্রিয়াকলাপের ক্রম সম্পর্কিত নিয়মগুলি বিবেচনায় নিয়ে, সূত্রগুলিতে "অতিরিক্ত" বন্ধনী এবং "" চিহ্নটি বাদ দিন:

;

2.3.6। সমতুল্য রূপান্তর ব্যবহার করে, সূত্রগুলির অভিন্ন সত্য প্রমাণ করুন:

2.3.7. দ্বৈত সূত্র খুঁজুন:

)

2.3.8। নিখুঁত DNF (SDNF) ফর্মে নিম্নলিখিত সূত্রগুলি হ্রাস করুন:

~

2.3.9। নিখুঁত CNF (SCNF) ফর্মে নিম্নলিখিত সূত্রগুলি হ্রাস করুন:

~

পরীক্ষাগারের কাজ № 3

বিষয়:বুলিয়ান ফাংশন মিনিমাইজেশন। যুক্তি"

লক্ষ্য:বুলিয়ান ফাংশন ন্যূনতম করার পদ্ধতিগুলির সাথে কাজ করার ক্ষেত্রে ব্যবহারিক দক্ষতা অর্জন করা।

3.1। তাত্ত্বিক তথ্য।

ন্যূনতম ফর্ম

যেমন দেখানো হয়েছে, যেকোন বুলিয়ান ফাংশন নিখুঁত স্বাভাবিক আকারে উপস্থাপিত হতে পারে (বিচ্ছিন্ন বা সংযোজক)। তদুপরি, এই জাতীয় উপস্থাপনা একটি ফাংশনের সারণী স্পেসিফিকেশন থেকে তার বিশ্লেষণাত্মক অভিব্যক্তিতে রূপান্তরের প্রথম ধাপ। নিম্নলিখিতটিতে, আমরা বিচ্ছিন্ন রূপ থেকে এগিয়ে যাব, এবং দ্বৈততার নীতির উপর ভিত্তি করে সংযোজক ফর্মের জন্য সংশ্লিষ্ট ফলাফলগুলি পাওয়া যায়।

বুলিয়ান ভিত্তিতে লজিক্যাল সার্কিট সংশ্লেষণের ক্যানোনিকাল সমস্যাটি বুলিয়ান ফাংশনগুলিকে মিনিমাইজ করার জন্য নেমে আসে, যেমন অব্যবস্থাপক স্বাভাবিক আকারে তাদের প্রতিনিধিত্ব করার জন্য, যাতে ক্ষুদ্রতম সংখ্যক অক্ষর (ভেরিয়েবল এবং তাদের অস্বীকার) থাকে। এই ধরনের ফর্মগুলিকে ন্যূনতম বলা হয়। ক্যানোনিকাল সংশ্লেষণে, এটি অনুমান করা হয় যে উভয় সংকেত এবং তাদের বিপরীতগুলি সার্কিটের ইনপুটগুলিতে সরবরাহ করা হয়।

বিচ্ছিন্ন স্বাভাবিক আকারে উপস্থাপিত সূত্রটি গ্লুইং অপারেশন এবং শোষণ অপারেশনের বারবার ব্যবহার দ্বারা সরলীকৃত হয় এবং (কঞ্জেক্টিভ স্বাভাবিক ফর্মের দ্বৈত পরিচয়ের ফর্ম রয়েছে: এবং)। এখানে, এবং কোন বুলিয়ান বীজগণিত সূত্র হিসাবে বোঝা যায়। ফলস্বরূপ, আমরা একটি বিশ্লেষণাত্মক অভিব্যক্তিতে পৌঁছেছি যেখানে আরও রূপান্তর আর সম্ভব নয়, যেমন আমরা একটি মৃত শেষ ফর্ম পেতে.

ডেড-এন্ড ফর্মগুলির মধ্যে একটি ন্যূনতম বিচ্ছিন্ন রূপও রয়েছে এবং এটি অনন্য নাও হতে পারে। একটি প্রদত্ত ডেড-এন্ড ফর্ম ন্যূনতম তা নিশ্চিত করতে, আপনাকে সমস্ত ডেড-এন্ড ফর্মগুলি খুঁজে বের করতে হবে এবং তাদের মধ্যে থাকা অক্ষরের সংখ্যার সাথে তুলনা করতে হবে।

উদাহরণস্বরূপ, ফাংশনটি নিখুঁত স্বাভাবিক বিচ্ছিন্ন আকারে দেওয়া যাক:

শর্তাবলী গ্রুপিং এবং gluing অপারেশন প্রয়োগ, আমরা আছে.

অন্য গ্রুপিং পদ্ধতির সাথে আমরা পাই:

উভয় ডেড-এন্ড ফর্ম ন্যূনতম নয়। ন্যূনতম ফর্ম পেতে, আপনাকে মূল সূত্রে একটি শব্দ পুনরাবৃত্তি করতে অনুমান করতে হবে (এটি সর্বদা করা যেতে পারে, যেহেতু )। প্রথম ক্ষেত্রে এমন একজন সদস্য হতে পারে। তারপর শব্দটি যোগ করে, আমরা পাই: সবকিছুর মধ্য দিয়ে গেছে সম্ভাব্য বিকল্প, আমরা যাচাই করতে পারি যে শেষ দুটি ফর্ম ন্যূনতম।

এই স্তরে সূত্র নিয়ে কাজ করা অন্ধকারে ঘুরে বেড়ানোর মতো। আপনি যদি এই উদ্দেশ্যে বিশেষভাবে তৈরি করা কিছু গ্রাফিক এবং বিশ্লেষণাত্মক উপস্থাপনা এবং প্রতীক ব্যবহার করেন তবে ন্যূনতম ফর্মগুলির জন্য অনুসন্ধানের প্রক্রিয়াটি আরও দৃশ্যমান এবং উদ্দেশ্যপূর্ণ হয়ে ওঠে।

বহুমাত্রিক ঘনক

একটি -মাত্রিক ঘনকের প্রতিটি শীর্ষবিন্দু একটি ইউনিটের একটি উপাদানের সাথে যুক্ত হতে পারে। ফলস্বরূপ, চিহ্নিত শীর্ষবিন্দুর উপসেটটি নিখুঁত বিচ্ছিন্ন স্বাভাবিক আকারে ভেরিয়েবলের একটি বুলিয়ান ফাংশনের -মাত্রিক ঘনক্ষেত্রের একটি ম্যাপিং। চিত্রে। 3.1 দফা 3.7 থেকে ফাংশনের জন্য এমন একটি ম্যাপিং দেখায়।

চিত্র 3.1 একটি ত্রিমাত্রিক ঘনক্ষেত্রে SDNF-এ উপস্থাপিত একটি ফাংশনের প্রদর্শন

যেকোনো বিচ্ছিন্ন স্বাভাবিক আকারে উপস্থাপিত ভেরিয়েবলের একটি ফাংশন প্রদর্শন করার জন্য, এটির মিনিটার্ম এবং -ডাইমেনশনাল কিউবের উপাদানগুলির মধ্যে একটি চিঠিপত্র স্থাপন করা প্রয়োজন।

ন্যূনতম (-1) র‌্যাঙ্ককে দুইটি মিনিটর্ম অব র‌্যাঙ্ক (ঐক্যের উপাদান) একত্রিত করার ফল হিসেবে বিবেচনা করা যেতে পারে, যেমন , একটি -মাত্রিক ঘনক্ষেত্রে, এটি দুটি শীর্ষবিন্দু প্রতিস্থাপনের সাথে মিলে যায় যা কেবলমাত্র এই শীর্ষবিন্দুগুলিকে একটি প্রান্তের সাথে সংযুক্ত করার স্থানাঙ্কের মানগুলির মধ্যে পার্থক্য করে (প্রান্তকে বলা হয় এটির সাথে শীর্ষবিন্দুগুলিকে কভার করে)। এইভাবে, (-1)তম ক্রম মিনিটর্মগুলি -মাত্রিক ঘনকের প্রান্তের সাথে মিলে যায়। একইভাবে, (-2)তম ক্রমটির মিনিটর্মের সঙ্গতি একটি -মাত্রিক ঘনকের মুখের সাথে প্রতিষ্ঠিত হয়, যার প্রতিটি চারটি শীর্ষবিন্দু (এবং চারটি প্রান্ত) জুড়ে থাকে।

মাত্রা দ্বারা চিহ্নিত একটি -মাত্রিক ঘনকের উপাদানগুলিকে -কিউব বলে। এইভাবে, শীর্ষবিন্দুগুলি 0-কিউবস, প্রান্তগুলি 1-কিউবস, মুখগুলি 2-কিউব, ইত্যাদি। উপরের যুক্তিটিকে সাধারণীকরণ করে, আমরা ধরে নিতে পারি যে ভেরিয়েবলের একটি ফাংশনের জন্য বিচ্ছিন্ন স্বাভাবিক আকারে ()ম র্যাঙ্কের একটি মিনিটর্ম একটি -কিউব দ্বারা প্রতিনিধিত্ব করা হয় এবং প্রতিটি -কিউব তার শীর্ষবিন্দুগুলির সাথে যুক্ত নিম্ন মাত্রার সমস্ত -কিউবকে কভার করে। . চিত্রে একটি উদাহরণ হিসাবে। 3.2 তিনটি ভেরিয়েবলের একটি ফাংশন দেখায়। এখানে মিনিটর্মগুলি 1-কিউব () এর সাথে মিলে যায় এবং মিনিটর্মটি 2-কিউব () দ্বারা প্রতিনিধিত্ব করা হয়।

Fig.3.2 ফাংশন কভারেজ

সুতরাং, যেকোন বিচ্ছিন্ন স্বাভাবিক ফর্মকে একটি -মাত্রিক ঘনক্ষেত্রের উপর একটি -কিউবসের একটি সেট দ্বারা ম্যাপ করা হয় যা ঐক্যের উপাদান (0-কিউব) এর সাথে সম্পর্কিত সমস্ত শীর্ষবিন্দুকে আবৃত করে। কথোপকথন বিবৃতিটিও সত্য: যদি -কিউবের একটি নির্দিষ্ট সেট একটি ফাংশনের একক মানের সাথে সম্পর্কিত সমস্ত শীর্ষবিন্দুর সেটকে আচ্ছাদিত করে, তবে এই -কিউবগুলির সাথে সম্পর্কিত মিনিটর্মগুলির বিভক্তিটি বিচ্ছিন্ন স্বাভাবিক অবস্থায় এই ফাংশনের একটি অভিব্যক্তি। ফর্ম এই ধরনের -কিউব (অথবা তাদের সংশ্লিষ্ট মিনিটর্ম) এর সংগ্রহকে একটি ফাংশনের আবরণ গঠন বলে।

একটি ন্যূনতম ফর্মের আকাঙ্ক্ষা এমন একটি আবরণের অনুসন্ধান হিসাবে স্বজ্ঞাতভাবে বোঝা যায়, যার ঘনক্ষেত্রের সংখ্যা ছোট হবে এবং তাদের মাত্রা বড় হবে। ন্যূনতম ফর্মের সাথে সামঞ্জস্যপূর্ণ কভারেজকে ন্যূনতম কভারেজ বলা হয়। উদাহরণস্বরূপ, চিত্রে কভারিং ফাংশনের জন্য। 3.3 ন্যূনতম ফর্ম পূরণ করে এবং .

ভাত। 3.3 ফাংশন কভারেজ।

বাম – ; ডানে –

একটি -মাত্রিক ঘনক্ষেত্রে একটি ফাংশনের প্রদর্শন পরিষ্কার এবং সহজ হয় যখন। একটি চার-মাত্রিক ঘনক চিত্রে দেখানো হিসাবে চিত্রিত করা যেতে পারে। 3.4, যা চারটি ভেরিয়েবলের একটি ফাংশন এবং অভিব্যক্তির সাথে তার ন্যূনতম কভারেজ দেখায় . এই পদ্ধতিটি ব্যবহার করার জন্য এমন জটিল নির্মাণের প্রয়োজন যে এর সমস্ত সুবিধা হারিয়ে গেছে।

ভাত। 3.4 ফাংশন ডিসপ্লে একটি চার-মাত্রিক ঘনক্ষেত্রে

কার্নোট মানচিত্র

বুলিয়ান ফাংশন ব্যবহার করে গ্রাফিলি প্রদর্শনের জন্য আরেকটি পদ্ধতি কার্নোট মানচিত্র, যা বিশেষভাবে সংগঠিত চিঠিপত্রের টেবিল। টেবিলের কলাম এবং সারিগুলি দুটির বেশি ভেরিয়েবলের মানগুলির সমস্ত সম্ভাব্য সেটের সাথে সামঞ্জস্যপূর্ণ এবং এই সেটগুলি এমনভাবে সাজানো হয়েছে যে প্রতিটি পরবর্তী একটি ভেরিয়েবলগুলির একটির মানের সাথে পূর্ববর্তীটির থেকে আলাদা। . এর জন্য ধন্যবাদ, টেবিলের প্রতিবেশী কক্ষগুলি অনুভূমিকভাবে এবং উল্লম্বভাবে শুধুমাত্র একটি পরিবর্তনশীলের মানের মধ্যে পৃথক। টেবিলের প্রান্তে অবস্থিত কোষগুলিকেও সংলগ্ন বলে মনে করা হয় এবং এই সম্পত্তি রয়েছে। চিত্রে। চিত্র 3.5 দুই, তিন, চার ভেরিয়েবলের জন্য Karnaugh মানচিত্র দেখায়।

ভাত। 3.5 দুই, তিন এবং চার ভেরিয়েবলের জন্য Carnaugh মানচিত্র

সাধারণ ট্রুথ টেবিলের মতো, যে সেটগুলিতে ফাংশনটি 1 মান নেয় সেগুলির কোষগুলি একটি দিয়ে পূর্ণ হয় (শূন্য সাধারণত ফিট হয় না, তারা খালি কোষের সাথে মিলে যায়)। উদাহরণস্বরূপ, চিত্রে। 3.6, কএকটি ফাংশনের জন্য একটি Karnaugh মানচিত্র দেখায়, যার প্রদর্শন একটি চার-মাত্রিক ঘনক্ষেত্রে চিত্রে দেওয়া হয়েছে। 3.4। জিনিসগুলিকে সহজ করার জন্য, একটি ভেরিয়েবলের জন্য 1 এর মানের সাথে সম্পর্কিত সারি এবং কলামগুলি একটি কোঁকড়া বন্ধনী দিয়ে হাইলাইট করা হয় যা সেই পরিবর্তনশীলটিকে নির্দেশ করে।

ভাত। 3.6 একটি Carnaugh মানচিত্রে চারটি ভেরিয়েবলের একটি ফাংশন প্রদর্শন করা

(a) এবং এর ন্যূনতম কভারেজ (b)

ফাংশন ম্যাপিং এর মধ্যে n-মাত্রিক ঘনক এবং কার্নোট মানচিত্র এক-এক চিঠিপত্র আছে। কার্নোট মানচিত্রে s-একটি ঘনকটি সারি, কলাম, বর্গক্ষেত্র বা আয়তক্ষেত্রে স্থাপিত 2টি প্রতিবেশী কোষের একটি সেটের সাথে মিলে যায় (মানচিত্রের বিপরীত প্রান্তগুলির নৈকট্য বিবেচনা করে)। অতএব, উপরে সেট করা সমস্ত বিধান (অনুচ্ছেদ দেখুন। বহুমাত্রিক ঘনক), Karnaugh মানচিত্রের জন্য বৈধ। সুতরাং, চিত্রে। 3.6, খন্যূনতম বিচ্ছিন্ন ফর্মের সাথে সম্পর্কিত মানচিত্র ইউনিটগুলির কভারেজ দেখায় প্রশ্নবিদ্ধ ফাংশন.

Karnaugh মানচিত্র থেকে miniterms পড়া ব্যবহার করে বাহিত হয় সহজ নিয়ম. কোষ গঠন s-কিউব, মিনিটার দাও (n-s)-ম পদমর্যাদা, যা অন্তর্ভুক্ত করে (n-s)সেভ করে এমন ভেরিয়েবল একই মানইহার উপর s-কিউব, যেখানে মান 1 ভেরিয়েবলের সাথে মিলে যায় এবং মান 0 তাদের অস্বীকারের সাথে মিলে যায়। ভেরিয়েবল যেগুলির জন্য তাদের মান ধরে রাখে না s-কিউব, মিনিটারমে অনুপস্থিত। বিভিন্ন উপায়রিডিংয়ের ফলে ফাংশনের বিভিন্ন উপস্থাপনা বিচ্ছিন্ন স্বাভাবিক আকারে হয় (ডানদিকের একটি ন্যূনতম) (চিত্র 3.7)।

Karnaugh মানচিত্রের ব্যবহারের জন্য ম্যাপিংয়ের তুলনায় সহজ নির্মাণের প্রয়োজন n-মাত্রিক ঘনক, বিশেষ করে চারটি ভেরিয়েবলের ক্ষেত্রে। পাঁচটি ভেরিয়েবলের ফাংশন প্রদর্শনের জন্য, চারটি ভেরিয়েবলের জন্য দুটি কার্নাউ মানচিত্র ব্যবহার করা হয় এবং ছয়টি ভেরিয়েবলের ফাংশনের জন্য, এই ধরনের চারটি মানচিত্র ব্যবহার করা হয়। ভেরিয়েবলের সংখ্যা আরও বৃদ্ধির সাথে, কার্নাফ মানচিত্রগুলি কার্যত অব্যবহারযোগ্য হয়ে পড়ে।

সাহিত্যে বিখ্যাত Veitch কার্ডতারা শুধুমাত্র পরিবর্তনশীল মানের সেটের বিভিন্ন ক্রমানুসারে পৃথক এবং কার্নাফ মানচিত্রের মতো একই বৈশিষ্ট্য রয়েছে।

কিউব জটিল

প্রচুর সংখ্যক ভেরিয়েবল সহ গ্রাফিকাল পদ্ধতির অসঙ্গতি বিভিন্ন দ্বারা ক্ষতিপূরণ দেওয়া হয় বিশ্লেষণী পদ্ধতিবুলিয়ান ফাংশনের উপস্থাপনা। এমনই একটি প্রতিনিধিত্ব কিউব জটিল, বিশেষভাবে বিকশিত প্রতীকবাদের সাথে সংমিশ্রণে একটি বহুমাত্রিক যৌক্তিক স্থানের পরিভাষা ব্যবহার করে।

) একতার উপাদানগুলির সাথে সম্পর্কিত 0-কিউবগুলি পরিবর্তনশীল মানের সেট দ্বারা উপস্থাপিত হয় যার উপর ফাংশনটি ঐক্যের সমান। স্পষ্টতই রেকর্ডিংয়ে

ভাত। 3.8 তিনটি ভেরিয়েবলের একটি ফাংশনের ঘনক্ষেত্রের জটিল ( ক) এবং এর প্রতীকী উপস্থাপনা ( খ)

কিউব ফর্ম জটিল সর্বাধিক ফাংশন কভারেজ. এটা থেকে বাদ দিয়ে ঐ সব s-উচ্চ মাত্রার কিউব দ্বারা আচ্ছাদিত কিউব, আমরা ডেড-এন্ড ফর্মের সাথে মিল রেখে কভারিং পাই। সুতরাং, বিবেচনাধীন উদাহরণের জন্য (চিত্র 3.8) আমাদের একটি মৃত-শেষ আবরণ রয়েছে

,

যা ফাংশনের সাথে মিলে যায় . ভিতরে এক্ষেত্রেএই কভারেজও ন্যূনতম।

দুটি বুলিয়ান ফাংশনের জন্য, ডিসজেকশন অপারেশনটি তাদের কিউব কমপ্লেক্সের মিলনের সাথে মিলে যায় এবং কনজেকশন অপারেশনটি তাদের কিউব কমপ্লেক্সের ছেদটির সাথে মিলে যায়। একটি ফাংশনের নেতিবাচক ঘনক্ষেত্রের একটি কমপ্লেক্সের পরিপূরকের সাথে সামঞ্জস্যপূর্ণ, অর্থাৎ, এবং সমস্ত শীর্ষবিন্দু দ্বারা নির্ধারিত হয় যেখানে ফাংশনটি 0 মান নেয়। এইভাবে, বীজগণিতের মধ্যে একটি এক থেকে এক চিঠিপত্র (আইসোমরফিজম) রয়েছে বুলিয়ান ফাংশন এবং বুলিয়ান সেট কিউবের কমপ্লেক্স প্রতিনিধিত্ব করে।

কিউব কমপ্লেক্স আকারে একটি ফাংশন প্রতিনিধিত্ব কম দৃশ্যমান, কিন্তু এর সবচেয়ে গুরুত্বপূর্ণ সুবিধা হল যে ভেরিয়েবলের সংখ্যার উপর বিধিনিষেধ সরানো হয় এবং কম্পিউটার ব্যবহার করার সময় তথ্যের এনকোডিং সহজতর হয়।

বুলিয়ান ফাংশন মিনিমাইজ করা

সমস্যা প্রণয়ন.একটি বুলিয়ান ভিত্তিতে একটি সার্কিট মিনিমাইজ করা ন্যূনতম কভারেজের সাথে সামঞ্জস্যপূর্ণ ন্যূনতম ডিসজংক্টিভ ফর্ম খুঁজে বের করার জন্য নেমে আসে। সাধারণ আকারে অন্তর্ভুক্ত অক্ষরের মোট সংখ্যা কভারেজের খরচ দ্বারা প্রকাশ করা হয় , n ভেরিয়েবলের একটি প্রদত্ত ফাংশনের আচ্ছাদন গঠন করে এমন ঘনক্ষেত্রের সংখ্যা কোথায়। ন্যূনতম কভারেজ চিহ্নিত করা হয় সর্বনিম্ন মানএর দাম

সাধারণত, মিনিমাইজেশন সমস্যা দুটি ধাপে সমাধান করা হয়। প্রথমত, আমরা একটি সংক্ষিপ্ত কভার সন্ধান করি যাতে সর্বাধিক মাত্রার সমস্ত -কিউব অন্তর্ভুক্ত থাকে, তবে এই কভারের যেকোন ঘনক্ষেত্র দ্বারা আচ্ছাদিত একটি একক ঘনক থাকে না। সংশ্লিষ্ট ডিসজংক্টিভ নরমাল ফর্মকে রিসড বলা হয় এবং এর মিনিটার্মগুলিকে বলা হয় সিম্পল ইমপ্লিক্যান্ট। একটি প্রদত্ত ফাংশনের জন্য, হ্রাসকৃত কভারেজটি অনন্য, তবে এটি অপ্রয়োজনীয় হতে পারে কারণ কিছু কিউব অন্যান্য কিউবের সংগ্রহ দ্বারা আচ্ছাদিত।

দ্বিতীয় ধাপে, একটি ট্রানজিশন করা হয় হ্রাসকৃত থেকে মৃত-শেষ বিচ্ছিন্ন স্বাভাবিক ফর্মে, যেখান থেকে ন্যূনতম ফর্মগুলি নির্বাচন করা হয়। সমস্ত অপ্রয়োজনীয় কিউবগুলিকে হ্রাস করা আবরণ থেকে বাদ দিয়ে ডেড-এন্ড ফর্মগুলি গঠিত হয়, যা ছাড়া বাকি কিউবগুলি এখনও একটি প্রদত্ত ফাংশনের আচ্ছাদন তৈরি করে, তবে কিউবগুলির আরও বাদ দিয়ে, এটি আর সমস্ত সেটকে কভার করে না। ফাংশনের একক মানের সাথে সম্পর্কিত শীর্ষবিন্দু, অর্থাৎ এটি একটি আচ্ছাদন হওয়া বন্ধ করে দেয়।

একটি হ্রাসকৃত কভারেজ কিউব যা একটি প্রদত্ত ফাংশনের শীর্ষবিন্দুগুলিকে কভার করে যা অন্য কোনও কিউব দ্বারা আচ্ছাদিত নয় অপ্রয়োজনীয় হতে পারে না এবং সর্বদা সর্বনিম্ন কভারেজের মধ্যে অন্তর্ভুক্ত করা হবে। এই ধরনের কিউব, এর সংশ্লিষ্ট ইমপ্লিক্যান্টের মতো, তাকে বলা হয় এক্সট্রিমাল (অত্যাবশ্যক ইমপ্লিক্যান্ট), এবং এটি যে শীর্ষবিন্দুগুলিকে ঢেকে রাখে তাকে বাতিল শীর্ষবিন্দু বলা হয়। এক্সট্রিমালের সেট কভারের মূল গঠন করে; এটি স্পষ্ট যে যখন একটি হ্রাসকৃত আবরণ থেকে একটি ন্যূনতম একটিতে সরানো হয়, প্রথমত, সমস্ত চরমগুলিকে বিচ্ছিন্ন করা উচিত। যদি extremals সেট একটি আচ্ছাদন গঠন না, তারপর এটি হ্রাস কভার থেকে কিউব সঙ্গে আবরণ সম্পূরক হয়।

প্রদত্ত সংজ্ঞাগুলি চিত্রে চিত্রিত করা হয়েছে। 3.9, যেখানে কভারেজ হ্রাস করা হয়েছে (চিত্র 3.9a দেখুন, ) এবং ন্যূনতম কভারেজ (চিত্র 3.9b) এবং (চিত্র 3.9, b দেখুন) নিম্নরূপ প্রকাশ করা হয়েছে।

প্রোপোজিশনাল বীজগণিতের ডিসজংক্টিভ এবং কনজেক্টিভ স্বাভাবিক ফর্ম।প্রতিটি প্রস্তাবমূলক লজিক ফাংশনের জন্য, একটি সত্য সারণী তৈরি করা যেতে পারে। বিপরীত সমস্যাটিও সর্বদা সমাধানযোগ্য। আসুন কয়েকটি সংজ্ঞা উপস্থাপন করি।

প্রাথমিক সংযোজন (সংযোজন)ভেরিয়েবলের কনজেকশন বা তাদের নেগেশান বলা হয় যেখানে প্রতিটি পরিবর্তনশীল সর্বাধিক ঘটে

একদা.

বিচ্ছিন্ন স্বাভাবিক ফর্ম(DNF) হল একটি সূত্র যা প্রাথমিক সংযোজনগুলির একটি বিচ্ছিন্নতার ফর্ম রয়েছে।

প্রাথমিক বিচ্ছিন্নতা (বিচ্ছিন্নতা)নেগেশান সহ বা ছাড়া চলকের বিভক্তি বলা হয়।

কনজেক্টিভ স্বাভাবিক ফর্ম(CNF) হল একটি সূত্র যা প্রাথমিক বিভক্তিগুলির সংমিশ্রণের ফর্ম রয়েছে।

প্রতিটি প্রস্তাবনামূলক বীজগণিত ফাংশনের জন্য একজন বিচ্ছিন্ন এবং সংযোজক স্বাভাবিক ফর্মের একটি সেট খুঁজে পেতে পারেন।

DNF নির্মাণের জন্য অ্যালগরিদম:

1. সমতুল্য রূপান্তর সূত্র ব্যবহার করে বুলিয়ান অপারেশনে যান।

2. ঘনিষ্ঠ নিতিকরণ সহ সূত্রগুলিতে যান, অর্থাৎ, এমন একটি সূত্রে যান যেখানে ভেরিয়েবলের উপরে নেতিকরণগুলি অবস্থিত নয় - ডি মরগানের আইন প্রয়োগ করুন।

3. বন্ধনী খুলুন - বিতরণের আইন প্রয়োগ করুন।

4. একবারে একবার পুনরাবৃত্তি করা পদগুলি নিন - অদম্যতা আইন।

5. শোষণ এবং অর্ধ-শোষণের আইন প্রয়োগ করুন।

উদাহরণ 6. DNF সূত্র খুঁজুন:

বুলিয়ান বীজগণিতে এটা সত্য দ্বৈততার নীতি. এটি নিম্নরূপ।

ফাংশন বলা হয় দ্বৈতফাংশন যদি. সেগুলো. একটি প্রদত্ত একটি ফাংশন দ্বৈত খুঁজে পেতে, আর্গুমেন্টের অস্বীকার থেকে ফাংশনের নেতিবাচকতা নির্মাণ করা প্রয়োজন।

উদাহরণ 7।দ্বৈত থেকে ফাংশন খুঁজুন।

মধ্যে প্রাথমিক ফাংশনলজিক 1 এর বীজগণিত দ্বৈত থেকে 0 এবং তদ্বিপরীত, x দ্বৈত থেকে x, দ্বৈত থেকে , দ্বৈত এবং তদ্বিপরীত।

যদি সূত্র F 1 ফাংশন প্রতিনিধিত্ব করে আমরা সমস্ত সংযোগ প্রতিস্থাপন করি

বিচ্ছিন্নতার উপর, সংযোগের উপর বিচ্ছিন্নতা, 0 এর উপর 1, 0 এর উপর 1, তারপরে আমরা ফর্মুলা F * পাই যে ফাংশনটি * ডুয়াল থেকে প্রতিনিধিত্ব করে।

কনজেক্টিভ নরমাল ফর্ম (CNF) হল DNF-এর জন্য একটি দ্বৈত ধারণা, তাই এটি নিম্নলিখিত স্কিম অনুযায়ী সহজেই তৈরি করা যেতে পারে:

উদাহরণ 8। CNF সূত্র খুঁজুন: .

উদাহরণ 6 এর ফলাফল ব্যবহার করে, আমাদের আছে

নিখুঁত বিচ্ছিন্ন এবং নিখুঁত সংযোজক স্বাভাবিক ফর্ম।স্বাভাবিক ফর্মের প্রতিটি প্রকারে (বিচ্ছিন্ন এবং সংযোজক), কেউ নিখুঁত ফর্মগুলির SDNF এবং SCNF এর একটি শ্রেণিকে আলাদা করতে পারে।

একটি নিখুঁত প্রাথমিক সংমিশ্রণ হল সমস্ত ভেরিয়েবলের যৌক্তিক গুণফল নেতিকরণ সহ বা ছাড়াই, এবং প্রতিটি ভেরিয়েবল শুধুমাত্র একবার গুণমানে উপস্থিত হয়।

যেকোন DNF-কে SDNF-এ কমানো যেতে পারে এমন সংযোগগুলিকে বিভক্ত করে যাতে সমস্ত ভেরিয়েবল থাকে না, যেমন অনুপস্থিত ভেরিয়েবলের জন্য যোগ করে x i বন্টনমূলক আইন ব্যবহার করে গুণ করা হয়

উদাহরণ 9।উদাহরণ 6-এর DNF-এর জন্য SDNF খুঁজুন

নিখুঁত প্রাথমিক বিচ্ছিন্নতাসমস্ত ভেরিয়েবলের যৌক্তিক যোগফল নেগেশান সহ বা ছাড়াই, এবং প্রতিটি ভেরিয়েবল শুধুমাত্র একবার যোগফলের মধ্যে অন্তর্ভুক্ত করা হয়।

যেকোন CNF-কে SCNF-এ কমানো যেতে পারে একটি কনজাংশন টার্ম যোগ করে যাতে কোনো পরিবর্তনশীল X i থাকে না কনজাঙ্কশনের মাধ্যমে এবং ডিস্ট্রিবিউটিভ আইন প্রয়োগ করে।

উদাহরণ 10। KNF কে SKNF এ আনুন:

SCNF তৈরি করতে, আপনি চিত্রটি ব্যবহার করতে পারেন

উদাহরণ 11।উদাহরণ 6 এর সূত্রের জন্য SCNF খুঁজুন।

প্রতিটি ফাংশনের একটি SDNF আছে এবং তদ্ব্যতীত, একটি অনন্য। প্রতিটি ফাংশনের একটি SCNF রয়েছে এবং উপরন্তু, একটি অনন্য।

কারণ SDNF এবং SKNF সূত্র দ্বারা স্বতন্ত্রভাবে সংজ্ঞায়িত করা হয়; এগুলি সূত্রের সত্য সারণী ব্যবহার করে তৈরি করা যেতে পারে।

একটি SDNF তৈরি করতে, যে সারিগুলিতে F মান 1 নেয় সেই সারিগুলি নির্বাচন করতে হবে এবং তাদের জন্য নিখুঁত প্রাথমিক সংযোগগুলি লিখতে হবে৷ সত্য সারণির কাঙ্খিত সারিতে একটি চলকের মান যদি একের সমান হয়, তবে একটি নিখুঁত সংমিশ্রণে এটি নেতিবাচক ব্যতীত নেওয়া হয়, যদি শূন্য হয়, তবে নেতিকরণ সহ। তারপর নিখুঁত সংযোগগুলি (তাদের সংখ্যা টেবিলের এককের সংখ্যার সমান) বিভক্তি চিহ্ন দ্বারা সংযুক্ত হয়।

একটি সত্য সারণী ব্যবহার করে একটি SCNF তৈরি করতে, এটির সারিগুলি নির্বাচন করা প্রয়োজন যেখানে F = 0, এবং নিখুঁত প্রাথমিক বিভক্তিগুলি লিখুন, এবং তারপরে সংযোগ চিহ্নগুলির সাথে সংযুক্ত করুন৷ যদি সত্য সারণির প্রয়োজনীয় সারিতে (F=0) চলকের মান শূন্যের সাথে মিলে যায়, তাহলে নিখুঁত ধারায় এটি নেতিবাচকতা ছাড়াই নেওয়া হয়, যদি এটি এক হয়, তাহলে নেগেশান সহ।

উদাহরণ 12।উদাহরণ 6-এর সূত্রের জন্য সত্য সারণী ব্যবহার করে SDNF এবং SCNF খুঁজুন।

টেবিল 14 শুধুমাত্র দেখায় চূড়ান্ত মান F=10101101। একটি বিশদ সত্য সারণী তৈরি করে আপনি নিজেই এই বিবৃতির বৈধতা যাচাই করুন৷

টেবিল 14

এক্স	y	z

স্ট্যান্ডার্ড ভিত্তি। প্রাথমিক সূত্রগুলি আক্ষরিক। প্রাথমিক সংযোগ (বিচ্ছেদ)। বিচ্ছিন্ন (সংযোজক) স্বাভাবিক ফর্ম এবং নিখুঁত ফর্ম। উপপাদ্য: 0 থেকে ভিন্ন যেকোন বুলিয়ান ফাংশন (1 থেকে) SDNF (SCNF) আকারে উপস্থাপন করা যেতে পারে। স্ট্যান্ডার্ড ভিত্তিতে সম্পূর্ণতা। সম্পূর্ণ ঘাঁটিগুলির উদাহরণ: ঝেগালকিন ভিত্তি, শেফার স্ট্রোক, পিয়ার্স তীর।

স্ট্যান্ডার্ড ভিত্তি বুলিয়ান বীজগণিতের তিনটি মৌলিক ক্রিয়াকলাপের একটি সেট: যোগ (ইউনিয়ন), গুণ (ছেদ) এবং নেতিকরণ।

এখানে আমরা কল করব আক্ষরিক চলক x বা এর নেগেশান x এবং বোঝায় xˆ। বিভিন্ন ভেরিয়েবল দ্বারা সংজ্ঞায়িত বেশ কয়েকটি লিটারেলের বুলিয়ান ইন্টারসেকশন, যেমন X = x 1 x 2 ফর্মের অভিব্যক্তি। . . xˆl, বলা হয় প্রাথমিক সংযোগ . সমস্ত ভেরিয়েবল আলাদা হওয়ার প্রয়োজনীয়তা নিম্নলিখিত দ্বারা নির্ধারিত হয়। যদি সংমিশ্রণটিতে বেশ কয়েকটি অভিন্ন আক্ষরিক অন্তর্ভুক্ত থাকে, তবে সংযোগের commutativity, associativity এবং idempotency এর কারণে, সমতুল্য সূত্রে পাস করে শুধুমাত্র একটি আক্ষরিক (উদাহরণস্বরূপ, x 1 x 1 = x 1) ছেড়ে দেওয়া সম্ভব। যদি সংযোজনটি একটি পরিবর্তনশীল এবং এর অস্বীকার অন্তর্ভুক্ত করে, তাহলে সূত্রটি ধ্রুবক 0 এর সমতুল্য, যেহেতু x x = 0 এবং যে কোনো সূত্র Y এর জন্য আমাদের কাছে Y x x = 0 আছে।

কয়েকটি প্রাথমিক সংযোগের বিভক্তিকে বলা হয় বিচ্ছিন্ন স্বাভাবিক ফর্ম , বা ডিএনএফ . উদাহরণ স্বরূপ,

x 1 x 3 + x 2 x 3 x 4 + x 1 x 2 x 3 x 5।

প্রদত্ত DNF-এর প্রতিটি প্রাথমিক সংযোজনে ভেরিয়েবলের গঠন যদি একই হয়, তাহলে DNF বলা হয় নিখুঁত . প্রদত্ত উদাহরণ হল একটি DNF যা নিখুঁত নয়। বিপরীতে, সূত্র

x 1 x 2 x 3 x 4 + x 1 x 2 x 3 x 4 + x 1 x 2 x 3 x 4

একটি নিখুঁত ফর্ম আছে।

যেহেতু বুলিয়ান বীজগণিতে যোগ এবং গুণন হল প্রতিসম ক্রিয়াকলাপ এবং আপনি সর্বদা যোগকে গুণ হিসাবে এবং গুণকে যোগ হিসাবে ব্যাখ্যা করতে পারেন, একটি দ্বৈত ধারণা রয়েছে - সংযোজক স্বাভাবিক ফর্ম (কেএনএফ ), যা প্রাথমিক বিভক্তির সংমিশ্রণ, এবং নিখুঁত সংযোজক ফর্ম (এসকেএনএফ ) সিমেট্রিক সেমিরিংসের জন্য দ্বৈততার নীতি থেকে এটি অনুসরণ করে যে DNF সম্পর্কিত যে কোনও বিবৃতির উত্তর CNF সম্পর্কিত একটি দ্বৈত বিবৃতি দ্বারা দেওয়া হয়, যা যোগ (বিচ্ছেদ) গুণের সাথে প্রতিস্থাপন করে, গুণ (সংযোগ) যোগ করে, ধ্রুবক 0 এর সাথে ধ্রুবক 1, ধ্রুবক। ধ্রুবক 0 সহ 1, ক্রমানুসারে দ্বৈত (বিপরীত) এর সাথে ক্রম সম্পর্ক। অতএব, আরও আমরা শুধুমাত্র DNF অধ্যয়নের উপর ফোকাস করব।

উপপাদ্য 1.4।ধ্রুবক 0 ছাড়া অন্য যেকোন বুলিয়ান ফাংশনকে SDNF হিসাবে উপস্থাপন করা যেতে পারে।

◀আসুন আমরা সম্মত হই যে x σ দ্বারা আমরা সূত্র x যদি σ = 1 বোঝায়, এবং সূত্র x যদি σ = 0। 1 , ... , t n ) (এ ধরনের ভেক্টর বলা হয় উপাদান ইউনিট ) তারপর প্রাথমিক সংযোজনটিও এই সেটে মান 1 নেয়, কিন্তু অন্য সমস্ত এন-ডাইমেনশনাল বুলিয়ান ভেক্টরে অদৃশ্য হয়ে যায়। সূত্রটি বিবেচনা করুন

যেখানে যোগফল (ইউনিয়ন) আর্গুমেন্ট মানের সমস্ত সেট (t 1, ... , t n) পর্যন্ত প্রসারিত হয় যার উপর প্রদত্ত ফাংশনমান 1 নেয়। মনে রাখবেন যে এই ধরনের সেটগুলির সেট খালি নয়, তাই যোগফলটিতে কমপক্ষে একটি পদ থাকে।

এটা দেখা সহজ যে সূত্র Φ তাদের জন্য 1 হয়ে যায় এবং শুধুমাত্র ভেরিয়েবলের সেই মানগুলির জন্য যার জন্য প্রশ্নে ফাংশনটি 1 হয়ে যায়। এর মানে হল সূত্র Ψ ফাংশন f প্রতিনিধিত্ব করে।

ফলাফল 1.1.আদর্শ ভিত্তি সম্পূর্ণ।

◀ প্রকৃতপক্ষে, যদি একটি ফাংশন একটি ধ্রুবক 0 না হয়, তাহলে এটি একটি SDNF আকারে উপস্থাপন করা যেতে পারে, যা একটি আদর্শ ভিত্তিতে একটি সূত্র। ধ্রুবক 0 প্রতিনিধিত্ব করা যেতে পারে, উদাহরণস্বরূপ, সূত্র f(x 1, x 2, ... , x n) = x 1 x 1 দ্বারা।

উদাহরণ 1.2।তিনটি ভেরিয়েবল m(x 1, x 2, x 3) (সারণী 1.4) এর একটি ফাংশন বিবেচনা করুন, বলা হয় সংখ্যাগরিষ্ঠ ফাংশন ̆ এই ফাংশনটি 1 এ মূল্যায়ন করে যদি এর অর্ধেকের বেশি আর্গুমেন্টের মান 1 থাকে। তাই, এটিকে প্রায়ই ভোটিং ফাংশন বলা হয়। এর জন্য একটি SDNF তৈরি করা যাক।

আদর্শ ভিত্তিতে সম্পূর্ণতা আপনি অন্য নির্বাচন করতে পারবেন সম্পূর্ণ সিস্টেমফাংশন সেট F এর সম্পূর্ণতা নিম্নলিখিত বিবেচনা থেকে প্রতিষ্ঠিত করা যেতে পারে। ধরুন তিনটি স্ট্যান্ডার্ড বিজিস ফাংশনের প্রতিটি F এর উপর একটি সূত্র দ্বারা উপস্থাপনযোগ্য। তারপর, উপপাদ্য 1.3 দ্বারা, পরিচয় F সম্পূর্ণ হবে।

উদাহরণ 1.3।অপারেশন মডিউল 2 যোগ, গুণ এবং ধ্রুবক 1 বলা হয় Zhegalkin ভিত্তি . সংযোজন মডুলো 2 এবং গুণন হল Z2 রিংয়ের মৌলিক ক্রিয়াকলাপ; তাদের সাহায্যে গঠিত অভিব্যক্তিগুলি Z2 রিংয়ের উপর বহুপদ। এই ক্ষেত্রে ধ্রুবক 1 মুক্ত শব্দ লিখতে প্রয়োজনীয়। যেহেতু xx = x, তাহলে বহুপদীর সব ফ্যাক্টরের ডিগ্রী 1 আছে। অতএব, একটি বহুপদী লেখার সময়, আপনি ডিগ্রির ধারণা ছাড়াই করতে পারেন। Zhegalkin ভিত্তিতে সূত্রের উদাহরণ:

xy⊕x⊕y, x⊕1, xyz⊕xz⊕x⊕y⊕1.

এই জাতীয় যেকোন সূত্রকে ঝেগালকিন বহুপদী বলা হয়। প্রকৃতপক্ষে, Zhegalkin বহুপদ হল Z2 রিং এর উপর একটি বহুপদী।

ঢেগালকিনের ভিত্তিতে সূত্রগুলি তৈরি করা কঠিন নয়, যা স্ট্যান্ডার্ড ভিত্তির সংযোজন এবং প্রত্যাখ্যানের ক্রিয়াকলাপকে প্রতিনিধিত্ব করে (দুটি ভিত্তির গুণন সাধারণ):

x+y=x⊕y⊕xy, x =x⊕1।

অতএব, Zhegalkin ভিত্তি একটি সম্পূর্ণ সেট।
এটা দেখানো যেতে পারে যে কোনো বুলিয়ান ফাংশনের জন্য Zhegalkin বহুপদীকে স্বতন্ত্রভাবে সংজ্ঞায়িত করা হয়

(আরো সুনির্দিষ্টভাবে, শর্তাবলীর ক্রম পর্যন্ত)। Zhegalkin বহুপদীর সহগ-এ ছোট পরিমাণভেরিয়েবলগুলি অনির্দিষ্ট সহগ পদ্ধতির দ্বারা পাওয়া যেতে পারে।

উদাহরণ 1.4।আসুন একটি একক ফাংশনের একটি সেট বিবেচনা করি - শেফার স্ট্রোক*। এই সেটটি সম্পূর্ণ, নিম্নোক্ত সহজে যাচাইযোগ্য পরিচয় থেকে নিম্নরূপ:

x =x|x, xy=x|y =(x|y)|(x|y), x+y=x |y =(x|x)|(y|y)।

উদাহরণ 1.5।একটি একক ফাংশন নিয়ে গঠিত একটি ভিত্তি, পিয়ার্স তীর, এছাড়াও সম্পূর্ণ। এর জন্য পরীক্ষাটি শেফার স্ট্রোকের মতোই। যাইহোক, এই উপসংহারটি প্রতিসম সেমিরিংসের জন্য দ্বৈততার নীতির ভিত্তিতেও করা যেতে পারে।

*শেফারের স্ট্রোক একটি বাইনারি, কিন্তু সহযোগী নয়, অপারেশন। অতএব, ইনফিক্স ফর্ম ব্যবহার করার সময়, আপনার সতর্কতা অবলম্বন করা উচিত: ফলাফল অপারেশনের ক্রম উপর নির্ভর করে। এই ক্ষেত্রে, বন্ধনী ব্যবহার করে অপারেশনের ক্রম স্পষ্টভাবে নির্দেশ করার পরামর্শ দেওয়া হয়, উদাহরণস্বরূপ, লিখুন (x | y) | z, x নয় | y | z, যদিও উভয় ফর্মই সমান।