به نام خدا
تقديم به استاد گرامي جناب آقاي مشتاق نظم
|
Q:1
به نام يگانه خالق آسمان و زمين، خداوند متعال كه آفرينش او از جنس قانون و روابط رياضي بيانگر، زيبايي آفرينش خداوند است. جواب :
(
|
|
Q:2
علامت نفي را توضيح دهيد ؟ جواب :
(
علامت نفي يا ┐ به معني نقيض مي باشد
|
|
Q:3
نماد عطفي را توضيح دهيد ؟ جواب :
(
به صورت AND است ( اولش ع دارد كه ا تلفظ مي شود، مثل اند) كه به صورت \/ مانند : A /\ b آنرا نمايش مي دهند.
|
|
Q:4
نماد فصلي را بگوييد ؟ جواب :
(
نماد OR همان نماد فصل است كه به صورت /\ آنرا نمايش مي دهند مانند : A \/ B نمايش مي دهند.
|
|
Q:5
نماد شرطي را بگوييد ؟ جواب :
(
با → آنرا نمايش مي دهند
|
|
Q:6
نماد دو شرطي را بگوييد ؟ جواب :
(
با ↔ آنرا نمايش مي دهند.
|
|
Q:7
منظور از n امين نماد جمله اي يا n امين نماد گزاره اي چه است ؟ جواب :
(
مانند An يا Bn
|
|
Q:8
5 نماد رابط جمله اي را بگوييد ؟ جواب :
(
┐ → ↔ /\ \/
|
|
Q:9
نمادهاي منطقي را نام ببريد ؟ جواب :
(
نمادهاي رابط جمله اي (5 نمادي كه در سوال قبل بررسي شدند )، و پرانتزها را نمادهاي منطقي مي ناميم.
|
|
Q:10
نمادهاي غير منطقي چه هستند ؟ و نام ديگر آنها چه است ؟ جواب :
(
نمادهاي جمله اي يا گزاره اي نمادهاي غير منطقي يا پارامترها هستند.
|
|
Q:11
آيا نمادها دنباله اي متناهي از نمادهاي ديگرند ؟ و اين موضوع به چه معني است ؟ جواب :
(
هيچ نمادي دنباله اي متناهي از ديگر نمادها نمي باشد. منظورمان اين است كه نتنها نمادها از يكديگر متمايزند، ( مثلا A برابر نمي باشد با ↔ ) بلكه هيچ يك از آنها دنباله اي متناهي از دو يا بيشتر از دو نماد ديگر نمي باشد.
|
|
Q:12
منظور از يك عبارت چه است ؟ جواب :
(
به دنباله اي متناهي از نمادها يك عبارت مي گوييم.
|
|
Q:13
يك عبارت را چگونه مشخص مي كنيم ؟ جواب :
(
با زنجيره ي اسمهاي نمادهايش
|
|
Q:14
تعريف يك فرمول درست ساخت بر اساس استقرا چه است ؟ جواب :
(
يك عبارت فرمول درست ساخت يا ف.د.س است اگر و تنها اگر عضو هر مجموعه ي استقرايي باشد.
|
|
Q:15
5 عمل فرمول ساز را نام ببريد ؟ جواب :
(
مطابق مطالب صفحه ي 26 كتاب درسي براي: ┐₤ و →₤ و ↔₤ و ^₤ و V₤
|
|
Q:16
اصل استقرا را در ف.د.س ها توضيح دهيد ؟ جواب :
(
هر مجموعه ي استقرايي از ف.د.س ها در واقع مجموعه ي همه ي ف.د.س ها است، اين مطلب اصل استقرا ناميده مي شود.
|
|
Q:17
ثابت كنيد هر عبارتي كه تعداد پرانتزهاي چپ آن از تعداد پرانتزهاي راست آن بيشتر باشد، يك ف.د.س نيست ؟ جواب :
(
ابتدا با يك نماد جمله اي كه صفر پرانتز راست و صفر پرانتز چپ دارد، شروع مي كنيم، و سپس عملهاي فرمول ساز را كه پرانتزها را به صورت جفتي اضافه مي كنند بر روي آن به كار مي بريم. در اين صورت يك مجموعه ي ف.د.س متعادل ( داراي تعداد پرانتز چپ و راست برابر ) بدست مي آيد. اين مجموعه را مي دانيم كه استقرايي است، چون فرمول درست ساخت است و از اينرو طبق اصل استقرا، اين مطلب براي همه ي ف.د.س ها صادق است.
|
|
Q:18
نشان دهيد ف.د.س با طولهاي 2 و 3و 6 امكان پذير نمي باشد ؟ جواب :
(
ابتدا با يك نماد جمله اي به طول 1 شروع مي كنيم و پنج عمل فرمول ساز را به ترتيب بر روي آن به كار مي بريم، و از اينرو مي بينيم كه با به كار بردن ┐₤ طول ف.د.س ما 4 مي شود ( دو پرانتز چپ و راست و عبارت A┐ )، و سپس با عمل فرمول ساز →₤ مي بينيم كه طول ف.د.س ما برابر 5 مي شود و الي آخر، از اينرو از آنجا كه هر كدام از ف.د.س هاي بدست آمده با اعمال هر يك از عملهاي فرمول ساز استقرايي است، از اينرو طبق اصل استقرا ف.د.س با طولهاي 2و3و6 امكان پذير نمي باشد اما با هر طول ديگر امكان پذير است.
|
|
Q:19
رابطهاي دوتايي را نام ببريد ؟ جواب :
(
→ و ↔ و ^ و V ( دقت شود كه ┐ رابط يكتايي است و نه دوتايي ).
|
|
Q:20
ثابت كنيد كه اگر تعداد رابطهاي دوتايي برابر با c باشد، و تعداد نمادهاي جمله اي برابر با s باشد، آنگاه s=c+1 .
جواب :
(
فرض مي كنيم كه در ف.د.س ما تنها يك رابط دوتايي به كار رفته باشد از اينرو داريم c=1 ، و از آنجايي كه طبق اصل استقرا ف.د.س ها نسبت به پنج عمل فرمول ساز بسته اند، و چهار رابط دوتايي نيز جزوه پنج عمل فرمول ساز مي باشند، از اينرو عمل فرمول ساز متناظر با رابط دوتايي موجود در ف.د.س را اضافه مي كنيم، در اينصورت مشاهده مي شود كه طبق اصل استقرا s=c+1 برقرار است.
|
|
Q:21
اينكه مي گويند S استقرايي است يعني چه ؟ جواب :
(
S استقرايي است اگر و تنها اگر زير مجموعه اي از B باشد و S تحت عملهاي f و g بسته باشد. نماد S زير مجموعه اي است از B را در صفحه ي 28 كتاب درسي نگاه كنيد.
|
|
Q:22
اينكه مي گويند g(f(a,f(b,b))) 1 در c5 و يا c_* 1 است يعني چه ؟ منظور از c_* 1 يعني علامت ستاره در پايين c است. جواب :
(
از آنجايي كه g كلا" يكتايي است ( يعني يك ورودي و يك خروجي دارد) و f درون آن دوتايي است، يعني دو ورودي و يك خروجي دارد، و مجددا" f داخلي دوتايي است، پس در مجموع ما يك عمل 5 تايي داريم كه با c_5 آنرا نمايش مي دهيم و هرچيزي كه در c_n باشد در c_* 1 نيز است. به علامت 1 توجه نشود، براي جمله بندي است.
|
|
Q:23
در چه صورت مي گوييم زير مجموعه ي S از U تحت f و g بسته است ؟ جواب :
(
زير مجموعه ي S از U تحت f و g بسته است اگر و تنها اگر هر گاه اعضاي xوy متعلق به S باشند آنگاه f(x,y) 1 و g(x) 1 نيز متعلق به S باشند.
|
|
Q:24
منظور از c^* 1 چه است ؟ ( يعني علامت ستاره بالاي C است ) ؟ جواب :
(
تمامي زير مجموعه هاي استقرايي U .
|
|
Q:25
منظور از C_* 1 چه است ( يعني علامت ستاره پايين c است ) ؟ جواب :
(
تمامي مجموعه هايي كه مي توان از U تحت اعمال فرمول ساز ساخت
|
|
Q:26
وقتي مي گوييم c_* 1 استقرايي است يعني چه ؟ جواب :
(
يعني براي مثال زير مجموعه اي از B است و تحت توابعي بسته است.
|
|
Q:27
c^* 1 براي اعداد حقيقي و توابع هماني و ثابت چه است ؟ جواب :
(
رده ي توابع جبري است.
|
|
Q:28
ثابت كنيد كه c^* = c_* 1 ؟ جواب :
(
براي اثبات اين مطلب كافي است كه نشان دهيم c_* 1 زير مجموعه ي C^* 1 است ( به علامت زير مجموعه در صفحه ي 29 كتاب دقت شود )، و مي دانيم كه C^* 1 درواقع تمامي زير مجموعه هاي استقرايي U است، از اينرو كافي است نشان دهيم كه C_* 1 استقرايي است. كه با توجه به آنكه مي دانيم C_* 1 تحت توابعي بسته است و زير مجموعه اي از U را نيز توليد مي كند، از اينرو استقرايي است.
|
|
Q:29
اصل استقرا در مجموعه ها را بگوييد ؟ جواب :
(
فرض كنيم كه C مجموعه ي پديد آمده از B به وسيله ي توابع متعلق به t است، اگر S زير مجموعه اي از C باشد كه شامل B و تحت توابع متعلق به t بسته باشد، از اينرو داريم S=C .
|
|
Q:30
اصل استقراي مجموعه ها را اثبات كنيد ؟ جواب :
(
مي دانيم كه S استقرايي است، پس داريم كه S زير مجموعه ي C^* 1 مي باشد، و چون C^* 1 برابر است با C_* 1 از اينرو مي دانيم كه S زير مجموعه اي استقرايي از C و در نتيجه از U است.
|
|
Q:31
C از B به وسيله ي f و g به طور آزاد پديد آمده است يعني چه ؟ جواب :
(
1.fc و gc يك به يك باشند 2.برد fc و برد gc و مجموعه ي B دو به دو مجزا باشند
|
|
Q:32
منظور از تحديدهاي f و g به C چه است ؟ جواب :
(
وقتي c از B به وسيله ي f و g به طور آزاد پديد آمده باشد، مطمئن هستيم كه fc و gc يك به يكند و بردهاي آنها دو به دو مجزا هستند كه مورد دوم مي شود fc و gc تحديدهاي f و g به C هستند.
|
|
Q:33
طريقه ي محاسبه ي ┐ را بگوييد ؟ جواب :
(
مخالف هر ارزشي كه پارامتر داشته باشد را بر مي گرداند، براي مثال اگر ارزش پارامتر T = true باشد، مقدار F=false را بر مي گرداند و بلعكس.
|
|
Q:34
طريقه ي محاسبه ي نماد عطفي ^ مانند (a^b) را بگوييد ؟ جواب :
(
مانند عمل ضرب عمل مي كند، براي مثال اگر ارزش a برابر T و ارزش b برابر F باشد و براي T عدد 1 را در نظر بگيريم و براي F عدد 0 را در نتيجه حاصل A^B مي شود 1x0 برابر با 0 كه مي شود F .
|
|
Q:35
طريقه ي محاسبه ي نماد فصلي يا V را مانند (A V B) بگوييد ؟ جواب :
(
مانند عمل جمع عمل مي كند، اگر T=1 و F=0 باشد، آنگاه حاصل A V B مي شود 1+0 برابر با 1 . اين عمل را اصطلاحا" OR مي ناميم.
|
|
Q:36
طريقه ي محاسبه ي انتفاي مقدم صادق يا → را مانند A → B بگوييد ؟ جواب :
(
فقط در صورتي F مي شود كه T بخواهد F شود در رابطه اي مانند A → B كه A برابر T و B برابر F است.
|
|
Q:37
طريقه ي محاسبه ي دو شرطي ↔ را بگوييد ؟ مانند A ↔ B ؟ جواب :
(
تنها وقتي كه هر دو كفه با هم برابر هستند، مقدار آن T مي شود، يعني در رابطه ي A ↔ B تنها وقتي جواب T است كه هر دوي A و B يا T باشند و يا F در غير اينصورت جواب F است.
|
|
Q:38
منظور از v(A1) 1 و ΰ(φ) 1 چه است ؟ اولي v و دومي v با يك خط بر روي آن. جواب :
(
v(A1) 1 ارزشي است كه به يك پارامتر داده شده است، و ΰ(φ)1 ارزش كل رابطه φ بعد از جاگذاري ارزش A1 مي باشد
|
|
Q:39
در چه صورت مي گوييم يك ارزش v كل فرمول φ را ارضا مي كند ؟ جواب :
(
اگر كل ارزش φ كه با v(φ) 1 (درواقع بالاي اين v يك خط است و وي وار خوانده مي شود )، برابر با T شود، مي گوييم يك ارزش v فرمول φ را ارضا كرده است.
|
|
Q:40
اينكه مي گويند t نتيجه ي توتولوژيك ∑ است يعني چه ؟ و چگونه آنرا نمايش مي دهند ؟ جواب :
(
اگر تمام ارزشدهي هاي ارضا كننده ي ∑ فرمول t را نيز ارضا كند و به صورت : t╒∑ آنرا نمايش مي دهند، درواقع قسمت باز مساوي به طرف نتيجه ي توتولوژيك است.
|
|
Q:41
چه ارزش دهي هايي مجموعه ي تهي يا Ǿ را ارضا مي كند ؟ جواب :
(
تمام ارزش دهي هاي موجود مجموعه ي تهي يا Ǿ را ارضا مي كند.
|
|
Q:42
در چه صورت مي نويسيم t╒ و آنرا چه مي خوانيم ؟ جواب :
(
مي خوانيم t توتولوژيك است اگر همه ي ارزش دهي ها آنرا ارضا كند مانند: Ǿ╒t و مي نويسيم : t╒
|
|
Q:43
قضيه ي فشردگي را بيان كنيد ؟ جواب :
(
اگر ∑ نا متناهي باشد و .∑ متناهي باشد و .∑ زير مجموعه ي ∑ باشد و ∑ شامل فرمول درست ساختها باشد، و آنگاه حداقل يك ارزش دهي v بتواند .∑ را ارضا كند، آنگاه همان ارزشدهي ∑ را نيز ارضا مي كند.
|
|
Q:44
در حالت عادي براي مجموعه اي از n نماد جمله اي چند ارزشدهي وجود دارد ؟ جواب :
(
دو به توان n ارزشدهي وجود دارد. براي مثال مجموعه اي مانند (A V B ) داراي 2 نماد جمله اي A و B است پس 2 به توان 2 برابر با 4 ارزشدهي براي آنها وجود دارد، كه براي A مي شود : T,T,F,F و براي B مي شود T,F,T,F مطابق صفحه ي 41 كتاب درسي.
|
|
Q:45
كاربرد جدول ارزش را بگوييد ؟ جواب :
(
به راحتي مشخص مي كند كه آيا فرمول داده شده توتولوژي است يا خير.
|
|
Q:46
منظور از R و R- ( يعني R با يك خط بالاي آن ) چه است ؟ جواب :
(
يعني داراي ارزشهاي مخالف يكديگرند.
|
|
Q:47
در چه صورت تريك شرطي ضعيف تر است ؟ جواب :
(
هر اندازه فرض قوي تر باشد، تركيب شرطي ضعيف تر است.
|
|
Q:48
معادل توتولوژيك قوانين پخشي ذيل را بگوييد ؟ ((A ^ ( B V C )) و ((A V ( B ^ C )) جواب :
(
1. ((A ^ B ) V ( A ^ C ))) و ((A V B ) ^ ( A V C )))
|
|
Q:49
معادل توتولوژيك ))A┐(┐( را بگوييد ؟ جواب :
(
براي معادل توتولوژيك در روابع از علامت ↔ استفاده مي شود. براي چواب تمرين به صفحه ي 43 كتاب مراجعه شود.
|
|
Q:50
معادل قوانين نفي ذيل را بگوييد ؟ صفحه ي 42 كتاب درسي جواب :
(
صفحه ي 42 كتاب درسي
|
|
Q:51
معادل قوانين دمورگان را بگوييد ؟ جواب :
(
صفحه ي 43 كتاب درسي
|
|
Q:52
طرد شق ثالث را بگوييد ؟ جواب :
(
مطابق صفحه ي 44 كتاب درسي در خصوص طرد شق ثالث داريم: A و ( OR ) و A┐
|
|
Q:53
تناقض را بگوييد ؟
جواب :
(
مطابق صفحه ي 44 كتاب درسي داريم: A و (AND ) و A┐ و سپس ┐ كل جمله
|
|
Q:54
عكس نقيض و صدور را بگوييد ؟ جواب :
(
صفحه ي 44 كتاب درسي
|
|
Q:55
اصل دوگاني را توضيح دهيد ؟ جواب :
(
فرض كنيد a يك ف.د.س باشد كه تنها نمادهاي ربطي آن ^ و V و ┐ باشند، و فرض كنيد *a نتيجه ي تعويض ^ و V و جايگزيني هرنماد جمله اي با نفي آن باشد. در اين صورت داريم كه *a معادل توتولوژيك با a┐ است.
|
|
Q:56
در چه صورت مي گوييم مجموعه ي 1∑ با مجموعه ي 2∑ از ف.د.س ها هم ارز هستند؟ جواب :
(
در صورتيكه اگر a╒∑ اگر و تنها اگر a╒∑ بالايي 1∑ است و پاييني 2∑
|
|
Q:57
در چه صورت مي گويند مجموعه ي ∑ مستقل است ؟ جواب :
(
مجموعه ي ∑ مستقل است اگر و تنها اگر هيچ عضو ∑ نتيجه ي توتولوژيك بقيه ي عضوهاي ∑ نباشند.
|
|
Q:58
مجموعه هاي هم ارز مستقل از كجا بدست مي آيند ؟ جواب :
(
هر مجموعه ي متناهي از ف.د.س ها داراي يك زير مجموعه ي هم ارز مستقل است.
|
|
Q:59
در چه صورت ما زير مجموعه ي هم ارز مستقل نداريم ؟ جواب :
(
هر مجموعه ي نا متناهي، لزوما"، داراي يك زير مجموعه ي هم ارز مستقل نمي باشد.
|
|
Q:60
طبق اصل يگانه خواني وضعيت تعداد پرانتزها در ف.د.س ها چگونه است ؟ جواب :
(
در هر ف.د.س تعداد پرانتزهاي چپ و راست با هم برابرند.
|
|
Q:61
چرا هيچ قطعه ي اوليه از سره از يك ف.د.س نمي تواند ف.د.س باشد ؟ جواب :
(
در هر قطعه ي اوليه سره از يك ف.د.س تعداد پرانتزهاي چپ بيشتر از تعداد پرانتزهاي راست است، بنابراين هيچ قطعه ي اوليه ي سره از يك ف.د.س نمي تواند يك ف.د.س باشد.
|
|
Q:62
اثبات كنيد كه تعداد پرانتزهاي سمت چپ قطعه ي اوليه ي يك سره بيشتر از راست آن است؟ جواب :
(
با توجه به بسته بودن ف.د.س ها به اعمال فرمول ساز، يكي از 5 عمل فرمول ساز ^₤ را در نظر مي گيريم، به ترتيب داريم كه : 1.) 2.a) و 3.^a) و الي آخر تا به (a^b) برسد با توجه به اصل استقرا قطعات اوليه ي سره ها استقرايي نيستند پس فرض ثابت شده است.
|
|
Q:63
قضيه ي يگانه خواني را توضيح دهيد ؟ جواب :
(
همان پديد آمدن آزاد متغيرها مي باشد كه به صورت ذيل براي پنج عمل فرمول ساز تعريف شده است : پنج عمل فرمول ساز وقتي كه به مجموعه ي ف.د.س ها محدود شوند: الف.بردهايي دارند كه از يكديگر و از مجموعه نمادهاي جمله اي مجزا هستند ب.يك به يك هستند
|
|
Q:64
با توجه به قضيه ي يگانه خواني مجموعه ي S- ( منظور S وار است، يعني يك خط بالاي S )، از S با پنج عمل فرمول ساز چگونه به وجود آمده است ؟ جواب :
(
به صورت آزاد
|
|
Q:65
شيوه ي علامتگذاري لهستاني را براي كوتاه نوشت كردن ف.د.س ها بگوييد ؟ جواب :
(
پايين صفحه ي 49 كتاب درسي
|
|
Q:66
توافق نامگذاري لاتين علامات لهستاني را بگوييد ؟ جواب :
(
N همان نفي است K همان عطفي است = AND A همان فصلي است = OR C همان شرطي است يعني → E همان دو شرطي است يعني ↔
|
|
Q:67
4 مرحله ي عمومي حذف پرانتزها را بگوييد ؟ جواب :
(
مطابق صفحه ي 50 كتاب درسي : 1.پرانتزهاي بيروني دو طرف فرمول را حذف مي كنيم 2.نماد نفي در كوتاه ترين ف.د.س پس از خود عمل مي كند 3.نمادهاي عطف و فصل در كوتاه ترين ف.د.س هاي دو طرف خود عمل مي كنند، مشروط بر اينكه قرار داد 2 رعايت شود. 4.وقتي يك نماد ربطي مكررا" به كار رود، در اينصورت دسته بندي از طرف راست صورت مي گيرد.
|
|
Q:68
رابط جمله اي # چه نام دارد؟ و بر اساس قانون حذف پرانتزها آنرا چگونه نمايش مي دهند؟ و ارزش آن چه است ؟ جواب :
(
يك رابط سه موضعي است كه نماد اكثريت ناميده مي شود. بر اساس قانون حذف پرانتزها به صورت acb# به كار مي رود، و ارزش آن يعني v(#abc) 1 برابر است با اكثريت ارزش هر يك از پارامترهاي درون آن.
|
|
Q:69
معادل توتولوژيك ABC# چه است ؟ جواب :
(
مطابق وسط صفحه ي 52 كتاب درسي داريم: A AND B OR A AND C OR B AND C
|
|
Q:70
يك تابع بولي K موضعي را تعريف كنيد ؟ جواب :
(
مي گوييم يك تابع بولي K موضعي تابعي است از {T,F} به توان k (مطابق صفحه ي 52 كتاب ) به{T,F} . براي مثال N لهستاني = not يك تابع بولي يك موضعي است و K لهستاني ( همان AND )يك تابع بولي دو موضعي است.
|
|
Q:71
با استفاده از نماد I تابع بولي لهستاني A را باز سازي نماييد؟ جواب :
(
بالاي صفحه ي 54 كتاب درسي
|
|
Q:72
بر اساس فلسفه ي تابع بولي در چه صورت گزاره هاي ذيل بر قرار هستند ؟ a╒b و a ╒ ╕b و a╒ جواب :
(
الف. مطابق صفحه ي 54 در صورتيكه تابع بولي منسوب به a كوچكتر مساوي تابع بولي منسوب به b باشد. ب.اگر و تنها اگر توابع بولي a و b با هم برابر ( مساوي ) باشند. پ.اگر و تنها اگر برد تابع بولي a برابر T باشد.
|
|
Q:73
تشخيص پذيري تابع بولي را توضيح دهيد ؟ جواب :
(
فرض كنيم G يك تابع بولي n موضعي با شرايط n ≥ 1 باشد، مي توانيم يك ف.د.س مانند a بدست آوريم به طوريكه G=B^n_a ( در اينجا B تابع بولي است كه در بالاي آن n و در پايين آن a قرار دارد و n به معني تعداد موضع آن است )، يعني به طوريكه a تابع G را مشخص مي سازد ( تشخيص پذير است ).
|
|
Q:74
a به صورت فصلي نرمال است يعني چه ؟ جواب :
(
يعني بين نمادهاي آن تماما" رابط فصلي OR قرار دارد.
|
|
Q:75
مزيت نمايش ف.د.س به صورت فصلي نرمال چه است ؟ جواب :
(
مزيتش آن است كه ارزشدهي هايي را كه اين فرمول را ارضال مي كنند، به وضوح بدست مي آيند.
|
|
Q:76
اگر معادل فصلي نرمال يك ف.د.س را بدست بياوريم براي ما چه مزيتي دارد ؟ جواب :
(
به ازاي هر ف.د.س a مي توان يك ف.د.س به صورت فصلي نرمال كه معادل توتولوژيك a باشد بدست آورد.
|
|
Q:77
منظور از تمام بودن مجموعه ي سه نماد ┐ و ^ و V چه است ؟ جواب :
(
يعني مي توان هر ف.د.س اي را با اين سه نماد مشخص نمود.
|
|
Q:78
تمام بودن چه نوع خاصيتي است ؟ جواب :
(
يك خاصيت از توابع بولي K و A و N است.
|
|
Q:79
تمام بودن هر يك از دو مجموعه ي ذيل را بگوييد : {┐ , V } و { ┐ , ^ } و چرا ؟ جواب :
(
هر دو مجموعه تمام هستند، زيرا كافي است نشان دهيم كه هر تابع بولي G را مي توان با يك ف.د.س و فقط با به كاربردن ^ و ┐ در حالت اول بدست آورد. براي اين منظور با يك ف.د.س كه از هر سه نماد ^ و ┐ و V استفاده مي كند شروع مي كنيم و بر اساس قوانيني مثل دمورگان و پخشي و ... آنرا به حالتي مي بريم كه فقط از V و ┐ و يا فقط از ^ و ┐ ساخته شده باشد، و اثبات مي كنيم كه هر دو باهم معادل توتولوژيكند.
|
|
Q:80
به ازاي هر n چند تابع n موضعي بولي وجود دارد ؟ جواب :
(
دو به توان دو به توان n : 2^2^n
|
|
Q:81
ثابت كنيد كه مجموعه ي ذيل تمام نيست : {^ , →} جواب :
(
ايده آن است كه نشان دهيم با اين رابطها اگر به نمادهاي جمله اي ارزش T بدهيم آنگاه همه ي فرمول ارزش T پيدا مي كند، در نتيجه چيزي كه معادل توتولوژيك a┐ باشد، وجود نخواهد داشت. مثال صفحه ي 58 كتاب درسي.
|
|
Q:82
ارزش ┴ و ┬ را بگوييد ؟ جواب :
(
ارزش ┬ برابر T و ارزش ┴ برابر F است.
|
|
Q:83
معادل ┴→A چه است ؟ جواب :
(
اين رابطه معادل است با A┐
|
|
Q:84
آيا { ↓ } و { | } تمام هستند ؟ جواب :
(
از آنجا كه NOT و OR تمام هستند و NOT و OR را فقط مي توان با بكار بردن | همانند سازي كرد، لذا | تمام است و همچنين براي ↓ نيز صادق است.
|
|
Q:85
منظور از 3aby+ چه است ؟ جواب :
(
يعني جواب اين رابطه T است اگر و تنها اگر تعداد فردي از a و b و y ارزش T داشته باشند. اين فرمول معادل a+b+y و a↔b↔y مي باشد.
|
|
Q:86
معادل نمادهاي ↓ و > و < و | و + را بگوييد و كدام نماد همان ياي مانعه الجمع است ؟ جواب :
(
جدول صفحه ي 60 كتاب درسي
|
|
Q:87
چه تركيباتي از → و ┐ و ┴ تمام هستند ؟ جواب :
(
{ → , ┐ } و { → , ┴ }
|
|
Q:88
اضافه كردن ┐ به كدام نمادها آنها را تمام مي كند و كدامها را نمي تواند تمام كند؟ جواب :
(
اضافه كردن ┐ به + و ↔ و # آنها را تمام نمي كند، اما اضافه كردنش به → و ^ و V و ┴ آنها را تمام مي كند.
|
|
Q:89
مثالهايي از مجموعه هاي تمام و نا تمام در صفحه ي 61 كتاب درسي آمده است. جواب :
(
|
|
Q:90
قوانين محاسبه ي تاخير يك مدار را بگوييد؟ جواب :
(
1.تاخير هر نماد جمله اي صفر است 2.تاخير a┐ يك واحد از تاخير a بيشتر است. براي مثال اگر a يك نماد جمله باشد، تاخير a┐ يك واحد بيشتر از آن يعني يك است. 3.تاخير a^b و aVb يك واحد از بيشينه ي تاخير a و b بيشتر است. براي مثال اگر تاخير a برابر 1 و تاخير b برابر 2 باشد، تاخير a^b برابر با 3 مي شود، و يا اگر a و b هر دو تاخير صفر داشته باشند، تاخير aVb برابر 1 است.
|
|
Q:91
منظور از يك سازه چه است ؟ جواب :
(
يك نماد جمله اي يا << نفي آنرا يك سازه مي ناميم.
|
|
Q:92
منظور از يك ضرب Φ را توضيح دهيد؟ جواب :
(
يك ضرب Φ تركيبي عطفي مانند a از سازه ها است ( با به كاربردن نمادهاي جمله اي متمايز )، به طوريكه a╒Φ
|
|
Q:93
يك ضرب مانند Φ چگونه اول است ؟ جواب :
(
يك ضرب Φ مانند a اول است، اگر و تنها اگر حذف هريك از سازه هاي آن ويژگي ضرب بودن را از a بگيرد.
|
|
Q:94
مجموعه ي ∑ از ف.د.س ها را در چه صورت ارضا شونده مي ناميم ؟ جواب :
(
در صورتيكه يك ارزشدهي وجود داشته باشد كه هر عضو ∑ را ارضا نمايد.
|
|
Q:95
طبق قضيه ي فشردگي در چه صورت يك مجموعه ي ف.د.س ارضا شونده است ؟ جواب :
(
در صورتيكه هر زير مجموعه ي متناهي آن ارضا شونده باشد.
|
|
Q:96
در چه صورت مجموعه ي ∑ را ارضا شونده ي متناهي مي نماميم؟ جواب :
(
اگر و تنها اگر هر زير مجموعه ي متناهي ∑ ارضا شونده باشد.
|
|
Q:97
در چه ضورت ∑ به صورت خود به خود ارضا شونده ي متناهي نيز است ؟ جواب :
(
اگر ∑ ارضا شونده باشد، در آن صورت خود به خود ارضا شونده ي متناهي نيز است.
|
|
Q:98
در چه صورت مي توان نتيجه گرفت كه ∑ ارضا شونده نيز است ؟ جواب :
(
اگر ∑ متناهي باشد در اين صورت اگر ارضا شونده ي متناهي باشد، بديهي است كه ارضا شونده نيز است.
|
|
Q:99
ارضا شوندگي يك مجموعه ي نامتناهي چگونه است ؟ جواب :
(
اگر يك مجموعه ي نامتناهي ارضا شونده ي متناهي باشد، آنگاه ارضا شونده است.
|
|
Q:100
وظيفه ي يك روش كارآمد در خصوص € چه است ؟ جواب :
(
روشي كارآمد وجود دارد كه به ازاي هر عبارت داده شده ي € درباره ي ف.د.س بودن يا نبودن آن تصميم مي گيرد.
|
|
Q:101
در چه صورت مجموعه ي ∑ از عبارتها تصميم پذير است ؟ جواب :
(
اگر و تنها اگر يك روش كارآمد وجود داشته باشد كه به ازاي هر عبارت a داده شده تصميم بگيرد كه ∑€a است يا خير ؟ پايين صفحه ي 70 كتاب درسي
|
|
Q:102
درباره ي تصميم پذير بودن يا نبودن نتايج توتولوژيك يك مجموعه ي تصميم پذير نا متناهي چه مي توان گفت ؟ جواب :
(
اگر ∑ يك مجموعه ي تصميم پذير نامتناهي باشد، در اين صورت ممكن است مجموعه نتايج توتولوژيك آن تصميم پذير نباشد.
|
|
Q:103
اگر A شمارش پذير كارآمد باشد چه اتفاقي مي افتد ؟ جواب :
(
اگر A شمارش پذير كارآمد باشد، در اين صورت به ازاي هر ₤ مي توان فهرست A را در جستجوي ₤ بررسي كرد.
|
|
Q:104
در چه صورت يك مجموعه از عبارتها تصميم پذير است ؟ جواب :
(
يك مجموعه از عبارتها تصميم پذير است اگر و تنها اگر آن مجموعه و متمم آن ( نسبت به همه ي عبارتها ) هر دو شماره پذير كارآمد باشند.
|
|
Q:105
اگر مجموعه هاي A و B شماره پذير كارآمد باشند، آنگاه تصميم پذيري و شمارش پذيري AUB و A∩B چگونه است ؟ جواب :
(
AUB و A∩B نيز شماره پذير كارآمدند، با توجه به اين موضوع كه رده ي مجموعه هاي تصميم پذير نيز تحت اعمال اجتماع و اشتراك بسته است، و علاوه بر آن تحت عمل متمم گيري نيز بسته مي باشد.
|
|
Q:106
در چه صورت مجموعه نتايج توتولوژيك ∑ از ف.د.س ها شماره پذير كارآمد خواهند بود؟ جواب :
(
اگر مجموعه ي ∑ مجموعه اي تصميم پذير از ف.د.س ها باشد.
|
|
Q:107
اگر A=modB چه نتيجه اي در بر دارد ؟ جواب :
(
مجموعه ي A از عبارتها شماره پذير كارآمد است.
|
|
Q:108
نتيجه ي وجود a╒∑ و a┐ ╒∑ چه است ؟
جواب :
(
نتيجه مي گيريم كه مجموعه نتايج توتولوژيك ∑ تصميم پذير است. پايان فصل اول
|
|
Q:109
شروع فصل دوم چند نكته در شروع اين فصل : З همان نماد سور وجودي نمايش داده شده در صفحه 77 كتاب درسي است ▼ همان نماد سور عمومي ( A برعكس ) اشاره شده در صفحه ي 76 كتاب درسي است. جواب :
(
|
|
Q:110
نماد ▼ به چه معني است و نمونه اي از كاربرد آنرا بگوييد ؟ جواب :
(
سور عمومي نام دارد، براي مثال مي توان آنرا اينچنين ترجمه كرد : به ازاي هر عدد طبيعي براي مثال، v1>0v1▼ به اين معني است : به ازاري هر عدد طبيعي v1 ، صفر از v1 كوچكتر است.
|
|
Q:111
نماد З به چه معني است و نمونه اي از كاربرد آنرا بگوييد ؟ جواب :
(
سور وجودي نام دارد، ترجمه ي آن به صورت : عضوي از عالم سخن وجود دارد كه، است. براي مثال З v به معني "عدد طبيعي مانند v وجود دارد كه " است.
|
|
Q:112
نماد ≈ را توضيح دهيد، و خلاصه شده ي آنرا نيز بگوييد ؟ جواب :
(
براي مثال در x ≈ y به معني "x مساوي y" است، و صورت خلاصه شده ي آن به صورت xy≈ مي باشد.
|
|
Q:113
جايگزين سور وجودي Зx چه است ؟ جواب :
(
⌐x▼⌐ مي باشد.
|
|
Q:114
شكل جايگزين شده ي سور وجودي را در فرمول ذيل بنويسيد : Зv1 ▼ V2v1 ≈ V2 جواب :
(
جواب وسط صفحه ي 77 كتاب درسي
|
|
Q:115
ترجمه ي هيچ مجموعه اي وجود ندارد كه هر مجموعه اي عضو آن باشد، را به زبان مرتبه ي اول بگوييد و مراحل آنرا نيز بنويسيد ؟ جواب :
(
مثال اول صفحه ي 80
|
|
Q:116
اصل زوج سازي را بگوييد و ترجمه ي آن به زبان مرتبه ي اول را بنويسيد ؟ جواب :
(
اصل زوج سازي : به ازاي هر دو مجموعه، مجموعه اي وجود دارد كه اعضايش دقيقا" همان دو مجموعه ي داده شده است. مثال دوم صفحه 80 طريقه ي ترجمه را شرح داده است.
|
|
Q:117
ترم عدد طبيعي 2 و ترم جمع عدد طبيعي 2+2 و محاسبه ي پاسخ آن در زبان مرتبه ي اول چگونه است ؟ جواب :
(
ترم عدد طبيعي 2 به صورت SS0 است و ترم جمع عدد 2 با 2 يعني 2+2 به صورت : SS0SS0SSSS0 + ≈ مي باشد.
|
|
Q:118
ترجمه ي هر عدد طبيعي غير صفر، تالي يك عدد است را به زبان مرتبه ي اول بنويسيد و مراحل آنرا نيز بگوييد ؟ جواب :
(
مثال دوم صفحه ي 81
|
|
Q:119
يك ترم را در زبان مرتبه ي اول تعريف كنيد ؟ جواب :
(
مجموعه ي ترمها، مجموعه ي عبارتهايي است كه از نمادهاي ثابت و متغيرها با عملهاي Tf توليد مي شوند.
|
|
Q:120
نماد گذاري ترمها در زبانهاي مرتبه ي اول چگونه است ؟ جواب :
(
با قرار دادن نماد تابعي در سمت چپ، علامتگذاري لهستاني را به كار مي بريم. ترمها پرانتز و يا ويلگول ندارند. مثالهايي از ترمها در صفحه ي 83 كتاب درسي آورده شده است.
|
|
Q:121
مثالي از يك فرمول بسيط در زبان مرتبه ي اول و مثالي از آن در زبان نظريه مجموعه ها بياوريد ؟ جواب :
(
v1 v2≈ مثالي از فرمول بسيط در زبان مرتبه ي اول ( زبان نظريه اعداد )، و v5v6 € نمونه اي از فرمول بسيط در زبان نظريه ي مجموعه ها است.
|
|
Q:122
نحوه ي توليد فرمولهاي درست ساخت در زبانهاي مرتبه ي اول ( نظريه اعداد ) چگونه است ؟ جواب :
(
فرمولهاي درست ساخت يا ف.د.س عبارتهايي هستند كه از فرمولهاي بسيط با استفاده از نمادهاي ربطي و نمادهاي سوري ساخته مي شوند.
|
|
Q:123
سه عمل فرمول ساز زبانهاي مرتبه ي اول ( نظريه ي اعداد ) را بگوييد ؟ جواب :
(
Not ⌐ و شرطي يك طرفه → و سور عمومي ▼ مي باشد. اطلاعات كاملتر و تعداد پرانتزهاي آنها در بالاي صفحه ي 84 كتاب درسي.
|
|
Q:124
ف.د.س هاي زبان مرتبه ي اول ( نظريه ي اعداد ) را تعريف كنيد ؟ جواب :
(
مجموعه ي فرمولهاي درست ساخت ( ف.د.س ها ) يا فقط فرمولها، مجموعه ي عبارتهاي پديد آمده از فرمولهاي بسيط با استفاده از سه عمل فرمول ساز عبارتهاي نظريه اعداد مي باشد.
|
|
Q:125
چرا در زبان نظريه ي اعداد v3⌐ يك ف.د.س نمي باشد؟ جواب :
(
چون مطابق سه عمل فرمول ساز، پرانتز ندارد.
|
|
Q:126
در چه صورت مي گوييم v1 در ف.د.س ذيل آزاد است ؟ v2▼ € متعلق به: v2v1 جواب :
(
چون اين جمله را بدون اطلاع از اينكه V1 چيست نمي توان كامل كرد، در حالتهايي نظير اين مي گوييم V1 در ف.د.س داده شده آزاد است، يا يك رخداد آزاد است.
|
|
Q:127
در چه صورت متغير X در a⌐ آزاد است ؟ جواب :
(
اگر و تنها اگر x در a آزاد باشد
|
|
Q:128
متغير x در فرمول بسيط a چه وقت آزاد است ؟ جواب :
(
اگر و تنها اگر x در a رخ دهد ( درواقع x نمادي از a باشد ).
|
|
Q:129
متغير x در a→b ( درون پرانتز هستند ) چخ وقت آزاد است ؟ جواب :
(
اگر و تنها اگر x در a يا b آزاد باشد
|
|
Q:130
متغير x در via▼ چه وقت آزاد است ( قسمت چهارم، صفحه ي 85 ) ؟ جواب :
(
اگر و تنها اگر x در a آزاد باشد، و x≠vi .
|
|
Q:131
طبق اصل بازگشت اگر h(x) 1 با جواب 1 در صورت بودن x در فرمول بسيط a و 0 براي در غير اينصورت تعريف كنيم، در اينصورت چگونه مي توانيم آزاد بودن x در a را بررسي كنيم؟ جواب :
(
براي اين منظور h را به h- منظور از - يعني بالاي h است، بر روي عمل فرمول ساز زبان مرتبه ي اول تعريف مي كنيم، سپس مي گوييم x در a آزاد است اگر و تنها اگر h- برابر 1 شود.
|
|
Q:132
در چه صورت در زبان مرتبه ي اول به اين نتيجه مي رسيم كه a يك جمله است ؟ جواب :
(
اگر هيچ متغيري در a آزاد نباشد، در آن صورت a يك جمله است.
|
|
Q:133
7 قانون كوتاه نويسي زبان مرتبه ي اول را بگوييد ؟ جواب :
(
وسط صفحه ي 87
|
|
Q:134
4 قانون حذف پرانتز و خلاصه نويسي علامات زبان مرتبه ي اول را بگوييد ؟ جواب :
(
1.بيروني ترين پرانتزها را مي توان حذف كرد. 2. نمادهاي ⌐ و ▼ و З كمترين برد را دارند. 3.^ و V نيز كمترين برد را دارند. 4.وقتي كه يك رابط مكررا" به كار برده مي شود، عبارات را از سمت راست دسته بندي مي كنيم. توضيح كامل، پايين صفحه ي 87
|