প্রমাণ ও সিমান্টিক ট্যাবলো

1. প্রমাণ কাকে বলে

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

এই দাবি শুনতে যতটা মনে হয়, তার চেয়ে কঠোর। «বৃষ্টি হচ্ছে, তাই মাটি ভিজে» বলা যুক্তিসংগত, কিন্তু তা বৃষ্টি ও মাটি সম্পর্কে আপনার জানাশোনার উপর ভর করে আছে। আকারগত যুক্তিবিদ্যা সেসব সরিয়ে রেখে আরও সংকীর্ণ একটি প্রশ্ন করে: কেবল বাক্যগুলির আকার ধরে, আশ্রয়বাক্য সত্য আর সিদ্ধান্ত মিথ্যা হওয়ার আদৌ কোনো উপায় আছে কি? যদি না থাকে, যুক্তিটি বৈধ, আর প্রমাণ হলো কেন কোনো উপায় নেই তার নথি।

এই নির্দেশিকা সেই নথি তৈরির একটি উপায় নিয়ে - সিমান্টিক ট্যাবলোর পদ্ধতি, যাকে সত্য-বৃক্ষও বলা হয়। ক্যালকুলেটরে যখনই আপনি একটি যুক্তি লেখেন, এই সাইট এই পদ্ধতিই চালায়; আর একবার এটি অনুসরণ করলে কেবল একটি কলম দিয়েই কাগজে যুক্তি যাচাই করতে পারবেন।

2. বৈধ, এবং তা আপনি কীভাবে জানবেন

একটি যুক্তি নিঃসরণ-চিহ্ন দিয়ে লিখুন: বাঁয়ে আশ্রয়বাক্য, ডানে সিদ্ধান্ত। p → q, ¬q ⊨ ¬p দাবিটি বলে, একটি শর্তবাক্য ও তার অনুগামীর নিষেধ থেকে তার পূর্বগামীর নিষেধ নিঃসৃত হয়। নিঃসরণ-চিহ্ন আরেকটি সংযোজক নয়। এটি তার দুই পাশের সূত্র সম্পর্কে একটি দাবি, আর সেটি হয় সঠিক নয় ভুল।

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

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

3. ট্যাবলো পদ্ধতি

ট্যাবলো হলো চিহ্নিত সূত্রের একটি বৃক্ষ। প্রতিটি লাইন একটি সূত্র, যার আগে T বা F বসানো, আর এই চিহ্ন বলে শাখাটি সেই সূত্র সম্পর্কে কী ধরে নিচ্ছে - তার সত্যমান কী তা নয়, বরং যুক্তিটি ভেঙে পড়তে হলে তা কী হওয়া দরকার। গোটা পদ্ধতি চারটি ধাপ:

1. প্রতিটি আশ্রয়বাক্য T সহ লিখুন। আপনি ধরে নিচ্ছেন যুক্তির সব আশ্রয়বাক্যই টেকে।
2. সিদ্ধান্তটি F সহ লিখুন। আপনি ধরে নিচ্ছেন তবু তা ভেঙে পড়ে - এটিই সেই অনুমান যা আপনি খণ্ডন করতে চান।
3. এমন যেকোনো লাইন নিন যা এখনো পরমাণু নয়, আর তার প্রধান সংযোজক ও চিহ্নের নিয়ম প্রয়োগ করুন; নিয়মটি যা উৎপন্ন করে তা সেই লাইনের ভেতর দিয়ে যাওয়া প্রতিটি শাখার শেষে যোগ করুন।
4. একই সূত্র A-এর জন্য কোনো শাখা যেই মুহূর্তে T A ও F A দুটিই বহন করে, সেই শাখা বন্ধ করে দিন। সব শাখা বন্ধ হলে, কিংবা বিশ্লেষণ করার মতো কোনো লাইন না থাকলে থামুন।

এই চক্রে চাতুর্যও লাগে না, কৌশল বাছাইও লাগে না। প্রতিটি লাইনের জন্য ঠিক একটি নিয়ম, আর যে ক্রমেই প্রয়োগ করুন রায় একই আসে - এ কারণেই কাজটি যন্ত্র করতে পারে, আর এ কারণেই যন্ত্র করলে ফলাফলে ভরসা রাখা যায়।

4. নিয়মগুলি

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

প্রতিটি নিয়ম আসলে তার সংযোজকের সত্য-শর্তকে উল্টো দিক থেকে পড়া বৈ কিছু নয়। সংযোজন কেবল তখনই সত্য যখন দুই দিকই সত্য, তাই T (A ∧ B) থাক দেয় T A ও T B. সংযোজন মিথ্যা হয় যখন অন্তত এক দিক মিথ্যা, কিন্তু সূত্র বলে না কোন দিক, তাই F (A ∧ B)-কে দুটিই চেখে দেখতে হয়: সে শাখা ছাড়ে। বিয়োজনে একই অসাম্য উল্টো দিকে চলে, আর শর্তবাক্য মিথ্যা হওয়ার মানে পূর্বগামী টিকেছে আর অনুগামী পড়েছে - নিহিতার্থ ভাঙার একমাত্র ক্ষেত্র।

লক্ষ করুন নিয়মগুলি কখনো যা করে না: তারা কখনো কোনো সূত্র বানায় না। নিয়ম যা কিছু উৎপন্ন করে, তা যে লাইন থেকে এসেছে তারই একটি টুকরো। এই বৈশিষ্ট্য - উপসূত্র-বৈশিষ্ট্য - পদ্ধতিটিকে সসীম করে, আর নিচে আমরা এতে ফিরে আসব।

5. শাখা বন্ধ করা

শাখা হলো একটিমাত্র যুক্তিসূত্র: মূল থেকে পাতা পর্যন্ত পড়ুন, পেয়ে যাবেন অনুমানের একটি পূর্ণ সেট। শাখা বন্ধ হয় যখন সেই অনুমানগুলি সরাসরি একে অপরের বিরোধী হয়, অর্থাৎ যখন এক ও একই সূত্রের জন্য সে T A ও F A দুটিই বহন করে। A কত জটিল, কিংবা দুটি লাইন কত দূরে, তাতে কিছু যায়-আসে না - কোনো শাখা যদি চায় একটি সূত্র একই সঙ্গে সত্য ও মিথ্যা হোক, তবে কিছুই তাকে তৃপ্ত করে না।

বন্ধ শাখায় × চিহ্ন দিন, যে দুটি লাইন তা বন্ধ করেছে তাদের উল্লেখ করুন, আর সেই শাখায় আর কাজ করবেন না। যে অনুমান আগে থেকেই অসম্ভব ছিল, তা থেকে আর শেখার কিছু নেই।

যখন প্রতিটি শাখা বন্ধ হয়, ট্যাবলোটি বন্ধ, আর সেটিই প্রমাণ। এটি দেখায় যে আপনি যে অনুমান দিয়ে শুরু করেছিলেন - সব আশ্রয়বাক্য সত্য, সিদ্ধান্ত মিথ্যা - তা তার নেওয়া সম্ভব প্রতিটি পথেই স্ববিরোধে পৌঁছয়। যেহেতু কোনো পথ আর অবশিষ্ট নেই, তেমন কোনো নির্ধারণ নেই, আর যুক্তিটি বৈধ। এটি অসম্ভবতার দ্বারা প্রমাণ, এমনভাবে বিছানো যাতে কোনো ক্ষেত্র বাদ না পড়ে।

6. একটি প্রমাণ, লাইন ধরে ধরে

মোডাস টলেন্স নিন: p → q, ¬q ⊨ ¬p. ১ ও ২ নম্বর লাইন হলো আশ্রয়বাক্য, সত্য ধরে নেওয়া। ৩ নম্বর লাইন হলো সিদ্ধান্ত, মিথ্যা ধরে নেওয়া - আর সিদ্ধান্ত যেহেতু ¬p, তাকে মিথ্যা ধরা মানে p-কে সত্য ধরা, যা ৫ নম্বর লাইনে লেখা হয়েছে। ৪ নম্বর লাইন আসে ২ নম্বর লাইনে নিষেধ নিয়ম প্রয়োগ করে: ¬q সত্য হলে q মিথ্যা। ১ নম্বর লাইনের শর্তবাক্যই একমাত্র বাকি লাইন যাতে সংযোজক আছে, আর সেটি β নিয়ম, তাই বৃক্ষটি দুই ভাগ হয়:

বাঁ শাখা ধরে নেয় শর্তবাক্যটি টিকেছিল কারণ তার পূর্বগামী পড়ে গিয়েছিল - কিন্তু ৫ নম্বর লাইনে p ইতিমধ্যেই সত্য, তাই শাখাটি নিজের সঙ্গেই বিরোধে জড়িয়ে বন্ধ হয়ে যায়। ডান শাখা ধরে নেয় তা টিকেছিল কারণ তার অনুগামী সত্য ছিল - কিন্তু ৪ নম্বর লাইনে q ইতিমধ্যেই মিথ্যা, তাই সেটিও বন্ধ হয়ে যায়।

দুটি শাখাই বন্ধ হলো, তাই ¬p মিথ্যা রেখে p → q ও ¬q সত্য করার কোনো উপায় নেই। যুক্তিটি বৈধ, আর বৃক্ষটিই তার কারণ। লক্ষ করুন, প্রমাণটি একবারও বৃষ্টির কথা বলেনি, মাটির কথাও নয়, p আর q কী বোঝায় তাও নয়। তার দরকারই পড়েনি।

7. যখন একটি শাখা খোলা থেকে যায়

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

খোলা শাখা «অবৈধ» রায়ের চেয়ে বেশি কিছু। তার পরমাণুগুলির চিহ্ন পড়ে নিন, পেয়ে যাবেন একটি নির্ধারণ: T চিহ্নিত প্রতিটি পরমাণু সত্য, F চিহ্নিত প্রতিটি মিথ্যা। এই নির্ধারণ প্রতিটি আশ্রয়বাক্যকে সত্য আর সিদ্ধান্তকে মিথ্যা করে, আর প্রতি-উদাহরণ বলতে ঠিক এটাই বোঝায়। যুক্তিবিদেরা একে প্রতি-মডেল বলেন, আর এটি «কেন নয়?» প্রশ্নের একটি বাস্তব উত্তর, প্রত্যাখ্যান নয়।

অনুগামীর স্বীকৃতি, p → q, q ⊨ p, হলো পাঠ্যবইয়ের উদাহরণ। তার ট্যাবলো p মিথ্যা আর q সত্য রেখে একটি শাখা খোলা রেখে দেয় - এমন এক অবস্থা যেখানে শর্তবাক্য টেকে, তার অনুগামীও টেকে, তবু পূর্বগামী টেকে না। এই একটিমাত্র নির্ধারণই যুক্তিটিকে খণ্ডন করে দেয়।

8. কেন এটি সবসময় শেষ হয়

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

এটি সত্যিকারের নিশ্চয়তা, আশা নয়। এর মানে পদ্ধতিটি প্রতিজ্ঞা-যুক্তিবিদ্যার জন্য একটি নির্ণয়-প্রক্রিয়া: যেকোনো যুক্তির উপর চালান, তা থামবেই - হয় বন্ধ বৃক্ষ নিয়ে, নয় খোলা শাখা নিয়ে, কাঁধ ঝাঁকিয়ে কখনো নয়। এই সাইটের প্রমাণক তার উপরে নোডের একটি সীমাও মানে, তবে তা কেবল কোনো বিকৃত সূত্র যেন ব্রাউজার ট্যাব নিঃশেষ না করে তার আগলা হিসেবে - গণিতের নিজের এমন কোনো সীমা লাগে না।

9. অন্যান্য প্রমাণ-ব্যবস্থা

ট্যাবলো বহু প্রমাণ-ব্যবস্থার একটি, আর এটিই খণ্ডন-আকৃতির: ব্যর্থতাকে বাদ দিয়ে সে কাজ করে। স্বাভাবিক নিগমন উল্টো পথে চলে এবং মোডাস পোনেন্স ও শর্তাধীন প্রমাণের মতো নিয়ম দিয়ে আশ্রয়বাক্য থেকে সামনের দিকে সিদ্ধান্ত গড়ে তোলে, আর একজন গণিতজ্ঞ গদ্যে যেভাবে যুক্তি সাজান তার সঙ্গে তা অনেক বেশি মেলে। স্বাভাবিক নিগমনের প্রমাণ সাধারণত খাটো হয়; তা খুঁজে বার করতে সাধারণত বেশি উদ্ভাবনী শক্তি লাগে।

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

কোন প্রতিজ্ঞা-যুক্তি বৈধ, সে বিষয়ে সবগুলিই একমত; পার্থক্য কেবল প্রমাণ দেখতে কেমন আর কী খুঁজে পাওয়া সহজ, তাতে। শেখার জন্য ট্যাবলোই সবচেয়ে বন্ধুবৎসল, কারণ এখানে ব্যর্থ প্রমাণ কানাগলি নয় - সে আপনার হাতে প্রতি-উদাহরণটি তুলে দেয়।

10. অনুশীলন

পদ্ধতিটি শেখার দ্রুততম উপায় হলো তা চালিয়ে দেখা। ক্যালকুলেটরে ⊨, ⊢ বা |= দিয়ে একটি যুক্তি লিখুন, ট্যাবলোটি সত্যক সারণির পাশেই আঁকা হবে, যাতে আপনি বৃক্ষের সঙ্গে সারিগুলি মিলিয়ে দেখতে পারেন। তারপর দেখে নেওয়ার আগে কয়েকটি প্রমাণ কাগজে করে ফেলুন।