۲۰. برهان غیر مستقیم

۲. برهان غیر مستقیم  « برهان خلف » :

 در برهان خلف، نقیض نتیجه را به مفروضات می افزاییم و با استفاده از قواعد، به یک تناقض می رسیم. با رسیدن به تناقض برهان کامل می شود.

 مثال ۴ : حکم زیر را با استفاده از برهان خلف ثابت کنید .

اگر من در این درس شرکت کنم و زیاد درس بخوانم، آنگاه نمرات خوبی می گیرم .

اگر نمرات خوبی بگیرم ،اآنگاه خوشحال می شوم.

من خوشحال نیستم.

بنابراین یا من  در این درس شرکت نکرده ام یا زیاد درس نخوانده ام.

حل :  گزاره های زیر را در نظر می گیریم :

من در این درس شرکت می کنم : p

من زیاد درس می خوانم : q

من نمرات خوبی می گیرم  : r

من خوشحال هستم : s

بنابراین

۱.  

۲.

۳. s~

۴.      برهان خلف

۵.  p q                 از ۴- دمورگان

۶.  r                        از ۱و ۵  قیاس استثنایی

۷.  s                       از ۲ و ۶ قیاس استثنایی

۸.               از ۳و ۷ عطف

شماره ۸ یک تناقض است. بنابراین حکم به برهان خلف برقرار است .

که شماره ۸ یک تناقض است . پس حکم به برهان خلف برقرار است.

این مثال را می توان با استفاده از برهان مستقیم نیز حل نمود‌:

۴.                 از ۲ و نکته ۱

۵.                      از ۴ و قانون دمورگان

۶. r~                              از ۵ و رفع مؤلفه

۷.       از ۱ و عکس نقیض

۸.                  از ۶و ۷ و قیاس استثنایی

۹.                  از  ۸ و قانون دمورگان.

انتخاب روش حل ِ یک حکم، به سلیقه و تجربه فرد بستگی دارد. اما همه سوال ها را نمی توان با برهان خلف ثابت کرد و همچنین همه سوال ها را نمی توان به روش مستقیم ثابت کرد. باید توجه کرد که در روش مستقیم، با استفاده از فرض ها و قواعد استنتاج به نتیجه دست می یابیم  اما در روش غیر مستقیم، نشان می دهیم که با درست فرض کردن ِ نقیض نتیجه، به یک گزاره ی نادرست « تناقض »  می رسیم ، که نشان می دهد نتیجه خود گزاره ای درست است.

  - ۲۰ -

---

 صفحه های قبل : « ۱۹ » ، « ۱۸ » ،  « ۱۷ » ،   « ۱۶ »  ،  « ۱۵ »  ، « ۱۴ » ، « ۱۳ » ،  « ۱۲ » ،  « ۱۱ » ، « ۱۰ » ،  « ۹ » ، « ۸ » ، « ۷ » ،  « ۶ » ،  « ۵ » ،  « ۴ » ،  « ۳ » ،  « ۲ »  ،  « ۱ »

۱۳. قضیه ۴

قضیه ۴: اگر p و q وr سه گزاره باشند آنگاه :

الف  : p q     q p

ب  : 

برهان :  قسمت الف به راحتی اثبات می شود. اما اثبات قسمت ب :

( r		q )		p		r		( q		p )
T F T F T F T F	F T T F F T T F	T T F F T T F F	T F F T F T T F	T T T T F F F F	T T T T T T T T	T F T F T F T F	T F F T F T T F	T T F F T T F F	F F T T T T F F	T T T T F F F F

 جدول ۲۳ 

  - ۱۳ -

---

 صفحه های قبل :  « ۱۲ » ،  « ۱۱ » ، « ۱۰ » ،  « ۹ » ، « ۸ » ، « ۷ » ،  « ۶ » ،  « ۵ » ،  « ۴ » ،  « ۳ » ،  « ۲ » ،  « ۱ » 

۱۹. برهان های درستی ۱. برهان مستقیم

برهان های درستی

۱. برهان مستقیم « Direct Proof »

۲. برهان غیرمستقیم « برهان خلف Reductio ad absurdum  »

۳. استقرای ریاضی « Mathematical induction »

۱. برهان مستقیم « Direct Proof »

در این نوع برهان ، گزاره ای به نام نتیجه، از ترکیب عطفی گزاره های مفروضات بدست می آید. مرسوم است که مفروضات و نتیجه را در سمت جپ زیر هم می نویسند و با یک خط نتیجه را از مفروضات جدا می کنند. برای راحتی هر سطر را شماره گذاری کرده و در هر مرحله، نام قانونی را که از آن استفاده شده و شماره سطرهایی را که در قانون استفاده شده اند ، در سمت راست گزاره می نویسند.

قانون هایی که استفاده می شوند بایستی قبلا ً درستی آنها اثبات شده باشد و ابهامی در درستی آن نباشد.

 مثال ۳: حکم زیر را با برهان مستقیم ثابت کنید.

عددی بر ۲ بخش پذیر است اگر و تنها اگر رقم یکان آن زوج باشد. عددی بر ۳ بخش پذیر است اگر و تنها اگر مجموع ارقام  آن بر ۳  بخش پذیر باشد. عددی بر ۶ بخش پذیر است که بر ۲ و ۳ بخش پذیر باشد. عدد بر ۶ بخش پذیر نیست و رقم یکان آن زوج است. بنابراین عدد بر ۳ بخش پذیر نیست .

حل: ابتدا حکم بالا را به صورت گزاره ای می نویسیم . اگر گزاره های  

d : عدد بر ۲ بخش پذیر است

z : رقم یکان عدد زوج است

c :  : عدد بر ۳ بخش پذیر است

m : مجموع ارقام عدد بر ۳ بخش پذیر است.

s :  : عدد بر ۶ بخش پذیر است

را در نظر بگیریم، آنگاه داریم :

1.  عددی بر ۲ بخش پذیر است اگر و تنها اگر رقم یکان آن زوج باشد :    
2. عددی بر ۳ بخش پذیر است اگر و تنها اگر مجموع ارقام  آن بر ۳  بخش پذیر باشد : 
3. عددی بر ۶ بخش پذیر است که بر ۲ و ۳ بخش پذیر باشد : 
4.  عدد بر ۶ بخش پذیر نیست و رقم یکان آن زوج است : 

-----------------------------------------------------------------------

نتیجه عدد بر ۳ بخش پذیر نیست .           c~

۱. 

۲.

۳.

۴.    c~

۵.                                                  ۱ و اختصار

۶.                                                  ۱ و اختصار

۷.                                                ۲ و اختصار

۸.                                               ۲ و اختصار

۹.        ۶ و ۸  قیاس ذوالوجهین موجب

۱۰.                                      ۹ و ۳ تعدی

۱۱. s ~                                                 و ۴و  اختصار

۱۲. z                                                   و ۴و  اختصار

۱۳. ( )                              ۱۰و۱۱ - قیاس دفع

۱۴.                                   ۱۳ و دمورگان

۱۵. m~                                   و ۱۴و۱۲ - رفع مؤلفه

۱۶.                            ۷- عکس نقیض

۱۷. c~                                و۱۵و۱۶ قیاس استثنایی

 که به این ترتیب به نتیجه مطلوب رسیدیم.

  - ۱۹ -

---

 صفحه های قبل : « ۱۸ » ،  « ۱۷ » ،   « ۱۶ »  ،  « ۱۵ »  ، « ۱۴ » ، « ۱۳ » ،  « ۱۲ » ،  « ۱۱ » ، « ۱۰ » ،  « ۹ » ، « ۸ » ، « ۷ » ،  « ۶ » ،  « ۵ » ،  « ۴ » ،  « ۳ » ،  « ۲ »  ،  « ۱ »

۱۸. سور وجودی و نقیض سور ها

۲. سور وجودی« Existential quantifier »  : در ریاضیات سور وجودی در یک عالم سخن ، جهت نشان دادن ِ صحت گزاره ای برای بعضی از عناصر عالم سخن به کار می رود و در فارسی جای « بعضی از » یا « وجود دارد » را می گیرد. مثلا ْ اگر گزاره ی پیشین را به گزاره ی «  بعضی از خودرو های ساخت ایران ، بنزین سوز هستند » تغییر دهیم، به این معناست که «  حداقل یک  خودرو ساخت ایران وجود دارد که بنزین سوز است » . این گونه جمله ها با سور وجودی بیان می شوند. در ریاضیات سور وجودی را با نماد « » نشان می دهند. پس با استفاده از سور وجودی ، گزاره به صورت « » نوشته می شود.

قاعده ی نقیض سورها :

نقیض گزاره ی «  تمام ِ خودرو های ساخت ایران ، بنزین سوز هستند » چیست؟ بله نقیض آن به صورت «  حداقل یک  خودرو ساخت ایران وجود دارد که بنزین سوز نیست » می باشد.

نقیض گزاره ی «  بعضی از خودرو های ساخت ایران ، بنزین سوز هستند » چیست؟ بله نقیض آن به صورت «  تمام خودروهای ساخت ایران، بنزین سوز نیستند » می باشد.

در حالت کلی اگر « » یک گزاره نما درباره ی متغیر x باشد، بنا بر تعریف داریم :

 

و

 

 قاعده ی نقیض سورها را می توان از تعمیم قانون دمورگان  بدست آورد. اگر فرض کنیم عالم سخن تنها شامل عناصر باشد، و « » گزاره ای درباره ی متغیر x باشد، آنگاه « » یعنی درست باشد . اگر از این گزاره طبق قانون دمورگان ، نقیض بگیریم داریم :

 

که در گزاره ی اخیر ، کافی است یکی از ها درست باشد که این یعنی xی موجود باشد که ~ درست باشد، یا  .

به همین نحو می توان نشان داد که

.

  - ۱۸ -

---

 صفحه های قبل :  « ۱۷ »  ، « ۱۶ »  ،  « ۱۵ »  ، « ۱۴ » ، « ۱۳ » ،  « ۱۲ » ،  « ۱۱ » ، « ۱۰ » ،  « ۹ » ، « ۸ » ، « ۷ » ،  « ۶ » ،  « ۵ » ،  « ۴ » ،  « ۳ » ،  « ۲ »  ،  « ۱ »

۱۷. سورها و قواعد آن

سورها و قواعد آن

تعاریف :

به گزاره ی « تمام اعداد اول ، فرد هستند » دقت کنید. در این گزاره ، بحث در مورد اعداد اول است و از اعداد اول سخن گفته می شود. یا در گزاره ی « اعداد حقیقی، یا مثبت اند، یا منفی، یا صفر » عالم سخن اعداد حقیقی است. پس عالم سخن یا دامنه سخن به صورت زیر تعریف می شود‌ :

 « عالم سخن Universe of discourse : مجموعه تمام عناصر مورد بحث در یک موضوع مشخص »

به هریک از اعضای عالم سخن یک اسم خاص گفته می شود .

به عبارت « x عدد حقیقی است » دقت کنید. در این جا x نمادی است که برای نشان دادن عدد حقیقی استفاده شده است. یا در عبارت « اگر x عدد حقیقی باشد،آنگاه x یا فرد است یا زوج » x برای نشان دادن عدد حقیقی بکار می رود. به چنین نمادها یا عباراتی که برای نشان دادن اسم خاص بکار می روند ، اسم نما گفته می شود. اسم نماها در عبارات به طور یکنواخت به اسم خاص تبدیل می شوند، مثلا ً در عبارت  « اگر x عدد حقیقی باشد،آنگاه x یا فرد است یا زوج » با قرار دادن عدد حقیقی ۲ (اسم خاص ) به عبارت ِ « اگر۲عدد حقیقی باشد،آنگاه ۲ یا فرد است یا زوج » می رسیم . دقت کنید در یک عبارت، در آن واحد ، نمی توان به جای یک اسم نمای معین ، بیش از یک اسم خاص قرار داد. منظور از تبدیل یکنواخت، همین است.

از آن جا که اسم نما می تواند بین عناصر دامنه ی سخن تغییر کند (هر عضوی از دامنه ی سخن را شامل شود)، به متغیر نیز تعبیر می شود.

گزاره نما : عبارتی شامل یک یا چند متغیر که با جایگزاری یکنواخت متغیرها به اسم خاص ، به گزاره ( درست یا نادرست ) تبدیل می شود.

سور ها « quantifier »  : برای خلاصه نویسی و به عبارتی ریاضی نویسی ِ جملات ، از سور ها کمک گرفته می شود. سورها دو نوع اند:

  ۱.   سور عمومی  « Universal quantifier » : سور عمومی در یک عالم سخن، جهت نشان دادن صحت گزاره ای برای تمام عناصر عالم سخن بکار می رود.  در فارسی جای « برای تمام ِ »  یا « برای هر »  را می گیرد. مثلا ً در گزاره ی «  تمام ِ خودرو های ساخت ایران ، بنزین سوز هستند »  دامنه ی سخن « خودروهای ساخت ایران » است. اگر x را « خودرو ساخت ایران » در نظر بگیریم ، گزاره بالا به گزاره ی « برای تمام xها ، x بنزین سوز است » تبدیل می شود.

در ریاضیات سورعمومی را با نماد «  » نشان می دهند. اگر گزاره ی « x بنزین سوز است » را با « » نشان دهیم، با استفاده از سورعمومی، گزاره ی بالا به صورت خلاصه ی « » می باشد.

  - ۱۷ -

---

 صفحه های قبل : « ۱۶ »  ،   « ۱۵ »  ، « ۱۴ » ، « ۱۳ » ،  « ۱۲ » ،  « ۱۱ » ، « ۱۰ » ،  « ۹ » ، « ۸ » ، « ۷ » ،  « ۶ » ،  « ۵ » ،  « ۴ » ،  « ۳ » ،  « ۲ »  ،  « ۱ »