Discrete Mathematics - 1.1 - Propositional Logic

Discrete Mathematics - 1.1 - Propositional Logic

Propositional Logic

লজিক কি তা আমরা গত আর্টিকেলে জেনেছি। এই আর্টিকেলে আমরা propositional logic নিয়ে আলোচনা করবো। আমরা একটু দেখে নিই আজকের আর্টিকেলে আমরা কি কি টপিক শিখবো তা দেখে নিই -

  • Propositions
    • Negation
    • Conjunction
    • Disjunction
    • Exclusive OR
    • Truth Table
  • Conditional Statements
    • Conditional Statement
    • Converse
    • Contrapositive
    • Inverse
    • Biconditionals
  • Truth Tables of Compound Propositions
  • Precedence of Logical Operators
  • Logic and Bit Operations

চলুন তাহলে আমরা শুরু করে দিই।

Propositions

Propositions কে বলা হয় basic building blocks of logic। Propositions মানে হচ্ছে হয় True নাহয় False, কিন্তু দুইটাই হতে পারবে না। অর্থাৎ যে বাক্য বা স্টেটমেন্ট এর উত্তর হয় সত্যি হবে নাহয় মিথ্যা হবে সেগুলোকে আমরা বলতে পারি Propositions. কয়েকটা উদাহরণ দিলে আপনাদের বিষয়টা ক্লিয়ার হয়ে যাবে

১. বাংলাদেশের রাজধানী ঢাকা
২. মালয়েশিয়ার রাজধানী কলম্বো
৩. ১ + ১ = ২
৪. ২ + ৩ = ৪
৫. এখন কয়টা বাজে?
৬. x + 2 = 3

এখানে ১ এবং ৩ True, ২ এবং ৪ False, ৫ এবং ৬ proposition না কারণ এগুলো সত্যি মিথ্যা কিছুই প্রকাশ করছে না।

Proposition কে প্রকাশ করার জন্য আমাদেরকে ভ্যারিয়েবল ব্যবহার করা লাগে। আমরা সাধারণত p, q, r, s দিয়ে propositional variable প্রকাশ করে থাকি। যদি একটা প্রপোজিশন true হয় তাহলে T দিয়ে প্রকাশ করা হয় আর যদি false হয় তাহলে F দিয়ে প্রকাশ করা হয়। যে প্রপোজিশনগুলো সিম্পল প্রপোজিশন দিয়ে সংজ্ঞায়িত করা যায় না তাদের বলে atomic proposition

লজিকের যে শাখা প্রোপোজিশনের সাথে ডীল করে তাকে বলা হয় propositional calculus অথবা propositional logic.

অনেক গাণিতিক স্টেটমেন্ট এক বা একাধিক প্রপোজিশনের সমন্বয়ে গঠিত হতে পারে। আমাদের কাছে যে প্রপোজিশন আছে তা থেকে লজিক্যাল অপারেটর বা লজিক্যাল কানেক্টিভ ব্যবহার করে যে নতুন প্রপোজিশন পাওয়া যায় তাকে বলে Compound Proposition

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

Negation

নেগেশন হলো কোনো একয়া প্রোপোজিশনের নেগেটিভ রূপ। অর্থাৎ কোনো স্টেটমেন্টের সাথে not লাগিয়ে দিলেই তা একটা নেগেশন। শুধুমাত্র not লাগালেই হবে না। চলুন একটু এই অপারেটর সম্পর্কে জানার চেষ্টা করি। ধরি p একটি প্রপোজিশন। এর নেগেশনকে লেখা হয় এভাবে ¬p এবং এর স্টেটমেন্ট হচ্ছে It is not the case that p। ¬p কে পড়া হয় 'not p'. p এর নেগেশনের truth value হচ্ছে p এর truth value এর বিপরীত। truth value বলতে বুঝাচ্ছে সেই প্রোপোজিশনের ভ্যালু true নাকি false। আমরা উদাহরণ দেখলে বুঝতে পারবো।

  • উদাহরণ - ১ঃ Find the negation of the proposition 'Aditya is an Engineer' and express this in simple English.

আমরা আমাদের সংজ্ঞা অনুযায়ী আগে এর নেগেশনটা লিখে ফেলি এভাবে, It is not the case that Aditya is an Engineer. এবার এটাকে যদি সিম্পল ইংরেজি বাক্যে পরিণত করি তাহলে এভাবে লেখা যায়, Aditya is not an Engineer.

  • উদাহরণ - ২ঃ Find the negation of the proposition 'Stack Learner channel has at least 1300 videos' and express this in simple English.

এর নেগেশন হলো It is not the case that Stack Learner channel has at least 1300 videos বা Stack Learner channel does not have at least 1300 videos বা Stack Learner channel has less than 1300 videos

আশা করি নেগেশনের কনসেপ্টটা আপনাদের মাথায় ইতোমধ্যে ঢুকে গেছে। খুব সহজ।

আমরা truth table দেখলে বুঝতে পারবো। Truth Table হলো কম্পাউন্ড প্রপোজিশনের truth value বের করার সহজ একটা টেবিল। এখানে প্রতিটা ভ্যারিয়েবলের সম্ভাব্য Truth value যার যার কলাম অনুযায়ী বসানো হয় এবং ফাইনালি লজিক্যাল অপারেশনের রেজাল্ট বের করা হয়। নেগেশনের Truth Table নিচে দেয়া হলো।

negation

অর্থাৎ প্রোপোজিশনের truth value যদি true হয় নেগেশন হবে false এবং প্রোপোজিশন যদি false হয় নেগেশন হবে true।

Conjunction

কনজাঙ্কশনকে আপনারা ধরতে পারেন এমন একটা রীলেশনশীপ, যেখানে দুইজনই যদি হ্যাঁ বলে তাহলেই কাজটা হবে নাহয় হবে না। অর্থাৎ ধরি p এবং q দুইটা প্রপোজিশন। p ও q এর conjunction কে প্রকাশ করা হয় এভাবে p ∧ q। একে পড়া হয় p and q এভাবে। যদি দুইটা প্রপোজিশনই true হয় তাহলে এদের কনজাঙ্কশন সত্যি হবে। যদি একটাও মিথ্যা হয় তাহলে এদের কনজাঙ্কশন মিথ্যা হবে। আমরা Truth table দেখলে আরো ভালভাবে বুঝতে পারবো।

conjunction.png

কনজাঙ্কশনের ক্ষেত্রে মাঝে মাঝে and এর জায়গায় but ব্যবহার হতে পারে। যেমন The sun is shining and it is raining এটাকে The sun is shining, but it is raining এভাবেও লেখা যায়।

আমরা একটা উদাহরণ দেখি।

  • উদাহরণ - ১ঃ p is the proposition 'Rebecca's PC has more than 16 GB free hard disk space' and q is the proposition 'The processor in Rebecca's PC runs faster than 1 GHz'. Find the conjunction of p and q

এদের কনজাঙ্কশন হবে Rebecca's PC has more than 16 GB free hard disk space and the processor in Rebecca's PC runs faster than 1 GHz বা Rebecca's PC has more than 16 GB free hard disk space and its processor runs faster than 1 GHz

Disjunction

এটা হচ্ছে এমন একটা রীলেশনশীপ, যেখানে অন্ততপক্ষে যেকোনো একজনকে হ্যাঁ বলতে হবে। দুইজনও হ্যাঁ বলতে পারে, কিন্তু যদি দুইজনই না বলে তাহলে ঐ কাজটা হবে না। ধরি p ও q দুইটা প্রপোজিশন। এদের ডিসজাঙ্কশনকে লেখা হয় এভাবে, p ∨ q এবং পড়া হয় 'p or q'। যদি এই দুইটা প্রপোজিশনের যেকোনো একটাও সত্যি হয় তাহলে এদের ডিসজাঙ্কশন সত্যি হবে। মিথ্যা হতে হলে দুইটা প্রপোজিশনকেই মিথ্যা হতে হবে। আমরা Truth Table দেখি এটার।

disjunction.png

ডিসজাঙ্কশনকে inclusive or ও বলা হয়। আমরা এর একটা উদাহরণ দেখি। কনজাঙ্কশনের উদাহরণের প্রোপোজিশনগুলোই রাখি আমরা। ঐ প্রোপোজিশনগুলোর ডিসজাঙ্কশন বের করবো আমরা।

প্রোপোজিশনগুলোর ডিসজাঙ্কশন হলো Rebecca's PC has more than 16 GB free hard disk space, or the processor in Rebecca's PC runs faster than 1 GHz

Exclusive or

Exclusive or হলো যেকোনো একটা সত্যি হতে পারবে, একই সাথে দুইটা সত্যি হতে পারবে না। অর্থাৎ ধরেন এমন একটা রুম যেখানে একসাথে একজনই ঢুকতে পারবে। দুইজন একসাথে ঢুকতে পারবে না। তার মানে দুইটা প্রোপোজিশনের যেকোনো একটা সত্যি হলেই কেবল Exclusive or সত্যি হবে। যদি দুইটাই true বা দুইটাই false হয় Exclusive or ফলস হবে। একে লেখা যায় p ⊕ q (p XOR q) এভাবে। এর truth টেবিলটা একটু লক্ষ্য করি আমরা।

xor.png

আমরা একটা এর বাস্তব উদাহরণ দেখি। ধরি p ও q প্রোপোজিশন দুইটি যথাক্রমে 'A student can have a salad with dinner' এবং 'A student can have soup with dinner'। এর এক্সক্লুসিভ অর হবে A student can have a salad or soup, but not both, with dinner বা আরো একটু সিম্পলভাবে A student can have a salad or soup with dinner. অর্থাৎ একজন ছাত্র কেবল সালাদ অথবা স্যুপ খেতে পারবে ডিনারে। দুইটা একসাথে খেতে পারবে না।

আবার ধরি p ও q দুইটি প্রোপোজিশন যথাক্রমে 'I will use all my savings to travel to Europe' এবং 'I will use all my savings to buy an electric car'. এর এক্সক্লুসিভ অর হবে I will use all my savings to travel to Europe or to buy an electric car.

Conditional Statements

প্রোপোজিশনের আরো কিছু অপারেশন নিয়ে আমরা আলোচনা করবো এই সেকশনে।

Conditional Statement

p, q এই দুইটা প্রোপোজিশনের কন্ডিশনাল স্টেটমেন্ট লেখা হয় এভাবে p → q এভাবে এবং পড়া হয় 'if p, then q'. এই স্টেটমেন্ট ফলস হবে শুধু যখন p true এবং q ফলস হয়, বাকি সব ক্ষেত্রে proposition true হবে। এখানে p কে বলা হয় hypothesis / antecedent / premise এবং q কে বলা হয় conclusion / consequence. আমরা এটার truth টেবিলটা দেখি এবার।

conditional.png

এটা অনেকেরই বুঝতে সমস্যা হতে পারে। একটা বাস্তব উদাহরণ দিই। এবং সেটার সাথে আমাদের ট্রুথ টেবিলটা মিলাই। ধরি p, q যথাক্রমে 'আমার ট্যাক্সেবল ইনকাম আছে' এবং 'আমি ট্যাক্স দিই'। এর কন্ডিশনাল স্টেটমেন্ট হবে যদি আমার ট্যাক্সেবল ইনকাম থাকে তবে আমি ট্যাক্স দিবো। যদি আমার ট্যাক্সেবল ইনকাম থাকে এবং আমি ট্যাক্স দিই তাহলে আইন ভঙ্গ হবে না, তার মানে ট্রু। যদি আমার ট্যাক্সেবল ইনকাম থাকে কিন্তু আমি ট্যাক্স না দিই সেক্ষেত্রে আইন ভঙ্গ করলাম, তার মানে কন্ডিশন ফলস। যদি আমার ট্যাক্সেবল ইনকাম না থাকে কিন্তু তাও আমি ট্যাক্স দিই সেক্ষেত্রে আমি যে বোকা তা প্রমাণ করলাম, কিন্তু কোনো আইন ভঙ্গ হয়নি। তার মানে কন্ডিশন ট্রু হবে। যদি আমার ট্যাক্সেবল ইনকামও না থাকে আর আমি ট্যাক্সও না দিই সেক্ষেত্রে কোনো আইন ভঙ্গ হবে না। তার মানে কন্ডিশন ট্রু। আশা করি ব্যাপারটা বুঝতে পেরেছেন আপনারা।

একটা শর্টকাট বলে দিই, যদি p ফলস হয় চোখ বন্ধ করে কন্ডিশন true হবে। আর যদি true হয় সেক্ষেত্রে q চেক করবো। যদি q true হয় তাহলে কন্ডিশন true, নাহয় ফলস। সবসময় যে if p, then q এরকম হলেই কন্ডিশনাল তা নয়। আরো অনেকভাবে p → q কে লেখা যায়। সেগুলো একটা তালিকা এখানে দিয়ে দেয়া হচ্ছে। তালিকাটা রোজেন সাহেবের বই থেকে নেয়া।

Screenshot_15.png

Converse, Contrapositive and Inverse

p → q এর converse হলো q → p, contrapositive হলো ¬q → ¬p এবং inverse হলো ¬p → ¬q. কী? সব মাথার উপর গেলো? চলুন একটা উদাহরণ দেখি। আমাদের কাছে একটা কন্ডিশনাল স্টেটমেন্ট আছে, সেটা হলো 'The home team wins whenever it is raining' . এর Converse, Contrapositive and Inverse বের করতে হবে আমাদের। চলুন চেষ্টা করি।

q whenever p = if p then q. সুতরাং এই স্টেটমেন্টকে আমরা একটু সাজিয়ে লিখলে দাঁড়াবে If it is raining, then the home team wins (p → q)।

  • Converse - If the home team wins, then it is raining (q → p).
  • Contrapositive - If the home team does not win, then it is not raining. (¬q → ¬p)
  • Inverse - If it is not raining, then the home team does not win. (¬p → ¬q)

আশা করি এবার পরিষ্কার হয়ে গেছে।

Biconditional

Biconditional এর ক্ষেত্রে স্টেটমেন্টটা হবে p ↔ q, একে পড়া হয় 'p if and only if q' এভাবে। এই স্টেটমেন্ট true হবে যদি দুইদিকে একইরকম হয় অর্থাৎ p যদি true হয় q কেও true হতে হবে আর ফলস হলে q কেও ফলস হতে হবে। দুইটা একইরকম না হলে স্টেটমেন্ট ফলস হবে। এতক্ষণে আপনাদের নিশ্চয়ই আর পড়তে ইচ্ছা করছে না। শুধু truth টেবিল দেখতে ইচ্ছা করছে। তাই না? নিন আপনার truth টেবিল।

biconditional.png

এবার নিশ্চয়ই উদাহরণের জন্য অপেক্ষা করছেন। তাই তো? দিচ্ছি দিচ্ছি। ধরি আমাদের p, q প্রোপোজিশনগুলো হলো 'You can take the flight' এবং 'You buy a ticket'. তাহলে আমাদের p ↔ q হবে 'You can take the flight if and only if you buy a ticket'.

Truth Table of Compound Propositions

এবার এতক্ষণ আমরা যা যা শিখলাম সব কিছু নিয়ে একটা কম্পাউন্ড প্রোপোজিশনের truth টেবিল বানাই চলুন। কম্পাউন্ড প্রোপোজিশন হলো একাধিক প্রোপোজিশনকে লজিক্যাল অপারেটরের মাধ্যমে কানেক্ট করে যে প্রোপোজিশন পাই সেটা। আমাদের কাছে একটা কম্পাউন্ড প্রোপোজিশন দেয়া আছে সেটা হলো, (p ∨ ¬q) → (p ∧ q). চলুন এর truth টেবিল বানাই।

compound.png

truth টেবিল সম্পর্কে একটা ইনফরমেশন শেয়ার করি। truth টেবিলের রো (row) সংখ্যা নির্ভর করে কয়টা ভ্যারিয়েবল নিচ্ছি তার উপর। ধরেন আমাদের x সংখ্যক ভ্যারিয়েবল আছে। তাহলে আমাদের রো হবে 2 to the power x সংখ্যক। অর্থাৎ যদি ২টা ভ্যারিয়েবল হয় তাহলে রো হবে ৪টা, ৩টা হলে ৮টা ইত্যাদি।

Precedence of Logical Operators

একটা কম্পাউন্ড প্রোপোজিশনে কোন অপারেটরের কাজ আগে হবে কোন অপারেটরের পরে হবে তার জন্য একটা Precedence Table আছে। সেটা নিচে দেয়া হলো। ক্রম অনুসারে আগে পরে কাজ হবে।

precedence.png

এখানে দেখা যাচ্ছে প্রথমে নেগেশনের কাজ হবে, এরপর কনজাঙ্কশন, এরপর ডিসজাঙ্কশন, এরপর কন্ডিশনাল এবং সব শেষে বাইকন্ডিশনালের কাজ।

Logic and Bit Operations

Bits ব্যবহার করে কম্পিউটার ইনফরমেশন রিপ্রেজেন্ট করে। বিটের দুইটা ভ্যালু থাকে, 0 and 1। 0 কে ফলস এবং 1 কে true ধরা হয়। আমরা এতক্ষণ যে যে লজিক্যাল অপারেশনগুলো করলাম লজিক্যাল অপারেটর দিয়ে, বিট অপারেটর দিয়ে বিট অপারেশনও আমরা করতে পারি। আমরা একটু truth টেবিলের মাধ্যমে বিট অপারেটরের কাজগুলো দেখি।

bit.png

কোনো পার্থক্য নেই শুরু true এর জায়গায় ১ এবং ফলসের জায়গায় ০।

Bit String

Bit String হলো 0 and 1 এর একটা সিকোয়েন্স আর এর লেংথ হবে যতটা ডিজিট থাকবে ঠিক ততো। যেমন 10101010000 is a bit string of length 11.

আমরা এবার দুইটা বিট স্ট্রিং 01 1011 0110 এবং 11 0001 1101 এর bitwise OR, bitwise AND এবং bitwise XOR বের করবো।

bitwise.png

Conclusion

আশা করি আপনারা এই আর্টিকেলে যা যা আলোচনা করা হয়েছে সবই বুঝেছেন। এটা পড়ার পর অবশ্যই অবশ্যই বই পড়বেন। বই পড়ার পর চাপটার শেষে এক্সারসাইজ আছে অনেক, সেগুলো করবেন। নাহয় শুধু ব্লগ পড়ে কখনই ডিসক্রিট ম্যাথ শিখতে পারবেন না। ম্যাথ প্র্যাক্টিসের বিষয়। তাই প্রচুর প্র্যাক্টিস করুন। আমরা নেক্সট আর্টিকেলে প্রোপোজিশনাল লজিকের অ্যাপ্লিকেশন নিয়ে আলোচনা করবো। আজকের মতো এখানেই সমাপ্ত। হ্যাপি লার্নিং 😊