روشی برای حل سیستم های معادلات منطقی. حل معادلات منطقی در ریاضیات نمونه هایی از حل معادلات منطقی

حل سیستم معادلات منطقی با تغییر متغیرها

روش جایگزینی متغیرها در صورتی استفاده می شود که برخی از متغیرها فقط به صورت یک عبارت خاص در معادلات گنجانده شوند و نه چیز دیگر. سپس این عبارت را می توان با یک متغیر جدید نشان داد.

مثال 1.

چند مجموعه مختلف از مقادیر متغیرهای منطقی x1، x2، x3، x4، x5، x6، x7، x8 وجود دارد که تمام شرایط ذکر شده در زیر را برآورده می‌کند؟

(x1 → x2) → (x3 → x4) = 1

(x3 → x4) → (x5 → x6) = 1

(x5 → x6) → (x7 → x8) = 1

در پاسخ نیازی به فهرست کردن مجموعه‌های مختلف مقادیر متغیرهای x1، x2، x3، x4، x5، x6، x7، x8 نیست که این سیستم برابری‌ها برای آنها برآورده شده است. به عنوان پاسخ، باید تعداد این مجموعه ها را مشخص کنید.

راه حل:

(x1 → x2) = y1; (x3 → x4) = y2; (x5 → x6) = y3; (x7 → x8) = y4.

سپس می توانیم سیستم را به شکل یک معادله بنویسیم:

(y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) = 1. وقتی هر عملوند مقدار 1 را بگیرد، ربط 1 است (درست است). هر یک از مفاهیم باید درست باشد، و این برای همه مقادیر به جز (1 → 0) صادق است. آن ها در جدول مقادیر متغیرهای y1، y2، y3، y4، یک نباید در سمت چپ صفر باشد:

آن ها شرایط برای 5 مجموعه y1-y4 برآورده می شود.

چون y1 = x1 → x2، سپس مقدار y1 = 0 در یک مجموعه منفرد x1، x2: (1، 0) و مقدار y1 = 1 - در سه مجموعه x1, x2: (0,0) , (0) به دست می آید. ، 1)، (1.1). به همین ترتیب برای y2، y3، y4.

از آنجایی که هر مجموعه (x1,x2) برای متغیر y1 با هر مجموعه (x3,x4) برای متغیر y2 و غیره ترکیب می‌شود، تعداد مجموعه‌های متغیر x ضرب می‌شوند:

				تعداد مجموعه ها در x1…x8

بیایید تعداد مجموعه ها را جمع کنیم: 1 + 3 + 9 + 27 + 81 = 121.

پاسخ: 121

مثال 2.

چند مجموعه مختلف از مقادیر متغیرهای منطقی x1، x2، ... x9، y1، y2، ... y9 وجود دارد که تمام شرایط ذکر شده در زیر را برآورده می کند؟

(¬ (x1 ≡ y1)) ≡ (x2 ≡ y2)

(¬ (x2 ≡ y2)) ≡ (x3 ≡ y3)

(¬ (x8 ≡ y8)) ≡ (x9 ≡ y9)

در پاسخ نیازی نیستتمام مجموعه های مختلف مقادیر متغیرهای x1، x2، ... x9، y1، y2، ... y9 را فهرست کنید که سیستم برابری داده شده برای آنها برآورده شده است. به عنوان پاسخ، باید تعداد این مجموعه ها را مشخص کنید.

راه حل:

بیایید تغییری در متغیرها ایجاد کنیم:

(x1 ≡ y1) = z1، (x2 ≡ y2) = z2،…. ,(x9 ≡ y9) = z9

سیستم را می توان به صورت یک معادله نوشت:

(¬ z1 ≡ z2) ∧ (¬ z2 ≡ z3) ∧ …..∧ (¬ z8 ≡ z9)

هم ارزی تنها در صورتی صادق است که هر دو عملوند برابر باشند. دو مجموعه راه حل برای این معادله وجود دارد:

z1	z2	z3	z4	z5	z6	z7	z8	z9
0	1	0	1	0	1	0	1	0
1	0	1	0	1	0	1	0	1

چون zi = (xi ≡ yi)، سپس مقدار zi = 0 مربوط به دو مجموعه (xi,yi) است: (0,1) و (1,0) و مقدار zi = 1 مربوط به دو مجموعه (xi,yi) است. ): (0،0) و (1،1).

سپس اولین مجموعه z1, z2,…, z9 مربوط به 2 9 مجموعه (x1,y1), (x2,y2),…, (x9,y9) است.

همین عدد مربوط به مجموعه دوم z1, z2,…, z9 است. سپس در مجموع 2 9 + 2 9 = 1024 مجموعه وجود دارد.

پاسخ: 1024

حل سیستم های معادلات منطقی با تعیین بصری بازگشت.

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

مثال 3.

سیستم معادلات چند راه حل مختلف دارد؟

¬x9 ∨ x10 = 1،

که در آن x1، x2، ... x10 متغیرهای منطقی هستند؟

در پاسخ نیازی به فهرست کردن مجموعه‌های مختلف مقادیر x1، x2، ... x10 نیست که این سیستم برابری‌ها برای آنها برآورده شده است. به عنوان پاسخ، باید تعداد این مجموعه ها را مشخص کنید.

راه حل:

بیایید معادله اول را حل کنیم. اگر حداقل یکی از عملوندهای آن برابر با 1 باشد، یک تفکیک برابر با 1 است. راه حل ها مجموعه ها هستند:

برای x1=0 دو مقدار x2 (0 و 1) و برای x1=1 فقط یک مقدار x2 (1) وجود دارد، به طوری که مجموعه (x1,x2) راه حلی برای معادله است. در کل 3 ست وجود دارد.

بیایید متغیر x3 را اضافه کرده و معادله دوم را در نظر بگیریم. مشابه مورد اول است، به این معنی که برای x2=0 دو مقدار x3 (0 و 1) و برای x2=1 فقط یک مقدار x3 (1) وجود دارد، به طوری که مجموعه (x2) ,x3) جوابی برای معادله است. در کل 4 ست وجود دارد.

به راحتی می توان فهمید که هنگام اضافه کردن متغیر دیگری، یک مجموعه اضافه می شود. آن ها فرمول بازگشتی برای تعداد مجموعه متغیرهای (i+1):

N i +1 = N i + 1. سپس برای ده متغیر، 11 مجموعه می گیریم.

پاسخ: 11

حل سیستم های معادلات منطقی در انواع مختلف

مثال 4.

چند مجموعه مختلف از مقادیر متغیرهای منطقی x 1، ...، x 4، y 1،...، y 4، z 1،...، z 4 وجود دارد که تمام شرایط ذکر شده در زیر را برآورده می کند. ?

(x 1 → x 2) ∧ (x 2 → x 3) ∧ (x 3 → x 4) = 1

(y 1 → y 2) ∧ (y 2 → y 3) ∧ (y 3 → y 4) = 1

(z 1 → z 2) ∧ (z 2 → z 3) ∧ (z 3 → z 4) = 1

x 4 ∧ y 4 ∧ z 4 = 0

در پاسخ نیازی نیستتمام مجموعه های مختلف مقادیر متغیرهای x 1، ...، x 4، y 1، ...، y 4، z 1، ...، z 4 را فهرست کنید که سیستم برابری داده شده برای آنها برآورده شده است. .

به عنوان پاسخ، باید تعداد این مجموعه ها را مشخص کنید.

راه حل:

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

بیایید به معادله اول نگاه کنیم. یک ربط فقط در صورتی درست است (برابر 1). مفهوم 1 در همه تاپل ها به جز (1,0) است. این بدان معنی است که راه حل معادله اول مجموعه های زیر x1، x2، x3، x4 خواهد بود که در آنها 1 در سمت چپ 0 قرار ندارد (5 مجموعه):

به طور مشابه، جواب های معادلات دوم و سوم کاملاً همان مجموعه های y1،…،y4 و z1،…، z4 خواهند بود.

حال بیایید معادله چهارم سیستم را تجزیه و تحلیل کنیم: x 4 ∧ y 4 ∧ z 4 = 0. راه حل تمام مجموعه های x4, y4, z4 خواهد بود که حداقل یکی از متغیرها برابر با 0 است.

آن ها برای x4 = 0، تمام مجموعه های ممکن (y4، z4) مناسب هستند و برای x4 = 1، مجموعه های (y4، z4) مناسب هستند که حداقل یک صفر در آنها وجود دارد: (0، 0)، (0،1). ) ، (1، 0).

				تعداد مجموعه ها

تعداد کل مجموعه ها 25 + 4*9 = 25 + 36 = 61 است.

پاسخ: 61

حل سیستم های معادلات منطقی با ساخت فرمول های مکرر

از روش ساخت فرمول های مکرر برای حل استفاده می شود سیستم های پیچیده، که ترتیب افزایش تعداد مجموعه ها مشخص نیست و ساختن درخت به دلیل حجم غیر ممکن است.

مثال 5.

چند مجموعه مختلف از مقادیر متغیرهای منطقی x1، x2، ... x7، y1، y2، ... y7 وجود دارد که تمام شرایط ذکر شده در زیر را برآورده می کند؟

(x1 ∨ y1) ∧ ((x2 ∧ y2) → (x1 ∧ y1)) = 1

(x2 ∨ y2) ∧ ((x3 ∧ y3) → (x2 ∧ y2)) = 1

(x6 ∨ y6) ∧ ((x7 ∧ y7) → (x6 ∧ y6)) = 1

در پاسخ نیازی به فهرست کردن مجموعه‌های مختلف مقادیر متغیرهای x1، x2، ...، x7، y1، y2، ...، y7 نیست که این سیستم برابری‌ها برای آنها برآورده شده است. به عنوان پاسخ، باید تعداد این مجموعه ها را مشخص کنید.

راه حل:

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

بیایید نشان دهیم:

تعداد تاپل ها (0,0) روی متغیرهای (x1,y1) تا A 1,

تعداد تاپل ها (0،1) روی متغیرهای (x1,y1) تا B1،

تعداد تاپل ها (1,0) روی متغیرهای (x1,y1) تا C1,

تعداد تاپل ها (1،1) روی متغیرهای (x1,y1) تا D 1.

تعداد تاپل ها (0,0) روی متغیرهای (x2,y2) تا A2,

تعداد تاپل ها (0،1) روی متغیرهای (x2,y2) تا B2،

تعداد تاپل ها (1,0) روی متغیرهای (x2,y2) تا C2،

تعداد تاپل ها (1,1) روی متغیرهای (x2,y2) تا D 2 .

از درخت تصمیم می بینیم که

A 1 = 0، B 1 = 1، C 1 = 1، D 1 = 1.

توجه داشته باشید که مجموعه (0,0) روی متغیرهای (x2,y2) از مجموعه (0,1,1,0) و (1,1) روی متغیرهای (x1,y1) به دست می آید. آن ها A 2 = B 1 + C 1 + D 1.

مجموعه (0,1) روی متغیرهای (x2,y2) از مجموعه (0,1,1,0) و (1,1) روی متغیرهای (x1,y1) بدست می آید. آن ها B 2 = B 1 + C 1 + D 1.

با استدلال مشابه، توجه می کنیم که C 2 = B 1 + C 1 + D 1. D2 = D1.

بنابراین، فرمول های تکراری را به دست می آوریم:

A i+1 = B i + C i + D i

B i+1 = B i + C i + D i

C i+1 = B i + C i + D i

D i+1 = A i + B i + C i + D i

بیا یه میز درست کنیم

مجموعه ها	تعیین.	فرمول	تعداد مجموعه ها
			i=1	i=2	i=3	i=4	i=5	i=6	i=7
(0,0)	یک آی	A i+1 =B i +C i +D i	0	3	7	15	31	63	127
(0,1)	B i	B i + 1 = B i + C i + D i	1	3	7	15	31	63	127
(1,0)	C i	C i+1 =B i +C i +D i	1	3	7	15	31	63	127
(1,1)	D i	D i+1 =D i	1	1	1	1	1	1	1

آخرین معادله (x7 ∨ y7) = 1 توسط همه مجموعه ها به جز مجموعه هایی که x7=0 و y7=0 هستند ارضا می شود. در جدول ما تعداد این مجموعه ها A 7 است.

سپس تعداد کل مجموعه ها B 7 + C 7 + D 7 = 127 + 127 + 1 = 255 است.

پاسخ: 255

حل معادله 1. به شکل پیشوند نوشتن معادله بروید و علامت منفی را با ¬ 2 جایگزین کنید. عنوان جدول صدق را بسازید. نوع خاص 3. خطوط جدول صدق را برای تمام ترکیبات A و B پر کنید، به جای X 0 یا 1 را جایگزین کنید. 4. یک جدول صدق برای X = F (A, B) ایجاد کنید. نوع تابع X در صورت لزوم با استفاده از روش های ساخت SKNF و SDNF که در ادامه به آن پرداخته خواهد شد.

ساخت جدول صدق به شکل خاص ¬((A+B)·(X A·B))=¬(B+¬(X A))

جدول حقیقت X=F(A,B) ABX مربوط به نفی مفهوم B در ANSWER است:

مدارهای ترکیبی ابزارهای منطقی عناصر اساسی (GOST): 1 A B تفکیک A B معادل و A B اتصال M2 A B XOR

مدارهای ترکیبی ابزارهای منطقی عناصر پایه (GOST): 1 الف ب مفهوم و الف ب المان شفر و الف ب مشترک 1 الف ب المان وب

مدار مثال F 1 & 1 & & 1M2 B A

حل مدارها 1 گزینه - تبدیل یک مدار به یک عبارت منطقی پیچیده و سپس ساده کردن آن طبق قوانین منطق. گزینه 2 - ساخت جدول حقیقت و سپس، در صورت لزوم، ساخت از طریق SKNF یا SDNF (به زیر مراجعه کنید). بیایید گزینه دوم را در نظر بگیریم، زیرا ساده تر و قابل درک تر است.

ساخت جدول حقیقت AB A + B + · B B · A + A B A + · ·

جدول حقیقت F(A, B) ABX مربوط به نفی استلزام B در ANSWER است:

SDNF و SKNF (تعاریف) یک ربط ابتدایی ترکیبی از چندین متغیر است که با یا بدون نفی گرفته می شود و در بین متغیرها ممکن است متغییرهای یکسان وجود داشته باشد. در بین متغیرها ممکن است موارد یکسانی وجود داشته باشد.

SDNF و SCNF (تعاریف) یک فرم نرمال منفصل کامل (PDNF) DNF نامیده می شود که در آن هیچ ربط ابتدایی یکسانی وجود ندارد و همه حروف ربط از مجموعه متغیرهای یکسانی تشکیل شده اند که در آن هر متغیر فقط یک بار ظاهر می شود (احتمالاً با نفی). یک فرم نرمال ربط کامل (PCNF) یک CNF است که در آن هیچ تفکیک ابتدایی یکسانی وجود ندارد و همه تفکیک ها از مجموعه متغیرهای یکسانی تشکیل شده اند که در آن هر متغیر فقط یک بار ظاهر می شود (احتمالاً با نفی).

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

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

مثالی از ساختن SKNF XY F(X,Y) صفرها را علامت گذاری کنید 2. تفکیک: X + Y 3. ربط: (X + Y) · (X + Y) می توانید انتخاب کنیدراه های مختلف

حل سیستم معادلات منطقی این کاهش به یک معادله، ساخت جدول حقیقت و تجزیه است.وظیفه:

حل یک سیستم معادلات منطقی: در نظر بگیریم . این روش شامل تبدیل معادلات منطقی به طوری است که سمت راست آنها برابر با مقدار صدق (یعنی 1) باشد. برای این کار از عملیات نفی منطقی استفاده کنید. سپس، اگر معادلات شامل عملیات منطقی پیچیده باشد، آنها را با موارد اصلی جایگزین می کنیم: "AND"، "OR"، "NO". گام بعدی این است که با استفاده از عملیات منطقی "AND" معادلات را در یک معادل با سیستم ترکیب کنید. پس از این، شما باید معادله حاصل را بر اساس قوانین جبر منطقی تبدیل کنید و یک راه حل خاص برای سیستم به دست آورید.

راه حل 1:وارونگی را در هر دو طرف معادله اول اعمال کنید:

بیایید مفهوم را از طریق عملیات اصلی "OR" و "NOT" تصور کنیم:

از آنجایی که سمت چپ معادلات برابر با 1 است، می توانیم آنها را با استفاده از عملیات "AND" در یک معادله که معادل سیستم اصلی است ترکیب کنیم:

براکت اول را طبق قانون دی مورگان باز می کنیم و نتیجه به دست آمده را تبدیل می کنیم:

معادله به دست آمده یک راه حل دارد: A = 0، B=0 و C=1.

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

راه حل 2:بیایید یک جدول حقیقت برای سیستم ایجاد کنیم:

0	0	1	1	0	1

خطی که برای آن شرایط کار برآورده شده است با پررنگ برجسته شده است. بنابراین A=0، B=0 و C=1.

راه تجزیه . ایده این است که مقدار یکی از متغیرها را ثابت کنیم (آن را برابر 0 یا 1 قرار دهیم) و در نتیجه معادلات را ساده کنیم. سپس می توانید مقدار متغیر دوم و غیره را ثابت کنید.

راه حل 3:اجازه دهید A = 0، سپس:

از معادله اول B = 0 و از معادله دوم - C = 1 می گیریم. حل سیستم: A = 0، B = 0 و C = 1.

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

حل سیستم معادلات منطقی این کاهش به یک معادله، ساخت جدول حقیقت و تجزیه است.معادله (A → B) + (C → D) = 1 چند راه حل دارد؟ که در آن A، B، C، D متغیرهای منطقی هستند.

راه حل:بیایید متغیرهای جدیدی را معرفی کنیم: X = A → B و Y = C → D. با در نظر گرفتن جدید معادله متغیربه شکل X + Y = 1 نوشته می شود.

تفکیک در سه مورد صادق است: (0;1)، (1;0) و (1;1)، در حالی که X و Y دلالت هستند، یعنی در سه مورد صادق و در یک مورد نادرست است. بنابراین، حالت (0;1) با سه ترکیب ممکن از پارامترها مطابقت دارد. مورد (1;1) - با 9 ترکیب ممکن از پارامترهای معادله اصلی مطابقت دارد. این بدان معنی است که کل راه حل های ممکن است معادله داده شده 3+9=15.

راه بعدی برای تعیین تعداد جواب های یک سیستم معادلات منطقی است درخت دوتایی. در نظر بگیریم این روشبه عنوان مثال

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

سیستم معادلات داده شده معادل معادله است:

(x 1 → x 2 )*(x 2 → x 3 )*…*(x m -1 → x m) = 1.

بیایید این را فرض کنیم x 1 – درست است، پس از معادله اول آن را به دست می آوریم x 2 همچنین درست است، از دوم - x 3 =1 و به همین ترتیب تا زمانی که x m= 1. این بدان معنی است که مجموعه (1؛ 1؛ ...؛ 1) m واحد راه حلی برای سیستم است. بذار حالا x 1 = 0، سپس از معادله اول داریم x 2 =0 یا x 2 =1.

چه زمانی x 2 true، دریافتیم که بقیه متغیرها نیز درست هستند، یعنی مجموعه (0; 1; ...; 1) راه حلی برای سیستم است. در x 2 =0 ما آن را دریافت می کنیم x 3 =0 یا x 3 =، و غیره. با ادامه آخرین متغیر، متوجه می‌شویم که راه‌حل‌های معادله مجموعه‌ای از متغیرهای زیر هستند (محلول m +1، هر جواب حاوی m مقادیر متغیرها است):

(1; 1; 1; …; 1)

(0; 1; 1; …; 1)

(0; 0; 0; …; 0)

این رویکرد با ساخت یک درخت دودویی به خوبی نشان داده شده است. تعداد راه حل های ممکن تعداد شاخه های مختلف درخت ساخته شده است. به راحتی می توان فهمید که برابر با m +1 است.

	درخت	تعداد راه حل ها
x 1
x 2
x 3
		…

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

بیایید سیستم معادلات را به شکل زیر بازنویسی کنیم:

و بیایید یک جدول حقیقت را به طور جداگانه برای یک معادله ایجاد کنیم:

x 1	x 2	(x 1 → x 2)

بیایید یک جدول صدق برای دو معادله ایجاد کنیم:

x 1	x 2	x 3	x 1 → x 2	x 2 → x 3	(x 1 → x 2) * (x 2 → x 3)

این مطالب حاوی ارائه ای است که روش هایی را برای حل معادلات منطقی و سیستم های معادلات منطقی در کار B15 (شماره 23، 2015) آزمون دولتی واحد در علوم کامپیوتر ارائه می دهد. مشخص است که این کار یکی از دشوارترین وظایف آزمون دولتی است. این ارائه می تواند هنگام آموزش دروس در مورد موضوع "منطق" در کلاس های تخصصی و همچنین هنگام آماده شدن برای آزمون دولتی واحد مفید باشد.

دانلود کنید:

پیش نمایش:

برای استفاده پیش نمایشارائه ها، یک حساب Google ایجاد کنید و وارد آن شوید: https://accounts.google.com

شرح اسلاید:

حل کار B15 (سیستم های معادلات منطقی) Vishnevskaya M.P., MAOU "Gymnasium No. 3" 18 نوامبر 2013، ساراتوف

تسک B15 یکی از سخت ترین امتحانات دولتی واحد علوم کامپیوتر است!!! مهارت های زیر مورد آزمایش قرار می گیرند: تبدیل عبارات حاوی متغیرهای منطقی. مجموعه ای از مقادیر متغیرهای منطقی را که مجموعه ای از متغیرهای منطقی برای آنها صادق است به زبان طبیعی توصیف کنید. تعداد مجموعه های باینری را که شرایط داده شده را برآورده می کنند، بشمارید. سخت ترین چیز این است که ... هیچ قانون رسمی در مورد نحوه انجام این کار وجود ندارد، نیاز به حدس و گمان دارد.

کاری که بدون آن نمی توانید انجام دهید!

کاری که بدون آن نمی توانید انجام دهید!

پیوند نمادها: A /\ B، A  B، AB، A &B، A و B تفکیک: A \ / B، A + B، A | نفی B، A یا B:  A، A، نه معادل A: A  B، A  B، A  B اختصاصی «یا»: A  B، A xor B

روش جایگزینی متغیر چند مجموعه مختلف از مقادیر متغیرهای منطقی x1، x2، ...، x9، x10 وجود دارد که تمام شرایط ذکر شده در زیر را برآورده می کند: ((x1 ≡ x2) \/ (x3 ≡ x4)) /\ (¬(x1 ≡ x2) \/ ¬(x3 ≡ x4)) = 1 ((x3 ≡ x4) \/ (x5 ≡ x6)) /\ ​​(¬(x3 ≡ x4) \/ ¬(x5 ≡ x6)) = 1 ((x5 ≡ x6) \/ (x7 ≡ x8)) /\ ​​(¬(x5 ≡ x7) \/ ¬(x7 ≡ x8)) = 1 ((x7 ≡ x8) \/ (x9 ≡ x10)) /\ ​​¬(x7 ≡ x8) \/ ¬(x9 ≡ x10)) = 1 پاسخ نیازی به فهرست کردن تمام مجموعه های مختلف x1، x2، …، x9، x10 ندارد این نظام برابری برقرار است. به عنوان پاسخ، باید تعداد این مجموعه ها را مشخص کنید (نسخه آزمایشی 2012)

راه حل مرحله 1. با تغییر متغیرهای t1 = x1  x2 t2 = x3  x4 t3 = x5  x6 t4 = x7  x8 t5 = x9  x10 پس از ساده‌سازی: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) =1 (t2 \/ t3) /\ (¬t2 \/ ¬ t3) =1 (t3 \/ t4) /\ (¬t3 \/ ¬ t4) =1 (t4 \/ t5) /\ ( ¬ t4 \/ ¬ t5) =1 یکی از معادلات را در نظر بگیرید: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) =1 بدیهی است که فقط اگر یکی از متغیرها 0 و دیگری 1 باشد، =1 است. بیایید از فرمول برای بیان عملیات XOR از طریق پیوند و تفکیک استفاده کنیم: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) = t1  t2 = ¬(t1 ≡ t2) =1 ¬(t1 ≡ t2) =1 ¬(t2 ≡ t3) =1 ¬(t3 ≡ t4) =1 ¬(t4 ≡ t5) =1

مرحله 2. تحلیل سیستم ¬(t1 ≡ t2) =1 ¬(t2 ≡ t3) =1 ¬(t3 ≡ t4) =1 ¬(t4 ≡ t5) =1 t1 t2 t3 t4 t5 0 1 0 1 0 1 0 1 0 1 T .به. tk = x2k-1 ≡ x2k (t1 = x1  x2،….)، سپس هر مقدار tk مربوط به دو جفت مقدار x2k-1 و x2k است، به عنوان مثال: tk = 0 مربوط به دو جفت است - (0 ,1) و (1, 0) و tk =1 - جفت (0,0) و (1,1).

مرحله 3. شمارش تعداد راه حل ها هر t 2 راه حل دارد، تعداد ts 5 است. بنابراین. برای متغیرهای t 2 5 = 32 راه حل وجود دارد. اما برای هر t یک جفت راه حل x وجود دارد، یعنی. سیستم اصلی 2*32 = 64 راه حل دارد. جواب: 64

روش حذف بخشی از راه حل ها چند مجموعه مختلف از مقادیر متغیرهای منطقی x1، x2، ...، x5، y1، y2،...، y5 وجود دارد که تمام شرایط ذکر شده در زیر را برآورده می کند: (x1→ x2 )∧(x2→ x3)∧(x3→ x4 )∧(x4→x5) =1; (y1→ y2)∧(y2→y3)∧(y3→y4) ∧(y4→y5) =1; y5→ x5 =1. پاسخ نیازی به فهرست کردن تمام مجموعه‌های مختلف x1، x2، ...، x5، y 1، y2، ...، y5 نیست که این سیستم برابری‌ها برای آنها صادق است. پاسخ باید تعداد این مجموعه ها را نشان دهد.

راه حل. مرحله 1. راه حل متوالیمعادلات x1 1 0 x2 1 0 1 x3 1 0 1 1 x5 1 0 1 1 1 x5 1 0 1 1 1 1 اولین معادله ترکیب چند عمل استلزامی است که برابر با 1 است. هر یک از مفاهیم درست است. مفهوم فقط در یک مورد نادرست است، زمانی که 1  0 باشد، در همه موارد دیگر (0  0، 0  1، 1  1) عملیات 1 را برمی گرداند. اجازه دهید این را به شکل جدول بنویسیم:

مرحله 1. حل ترتیبی معادلات T.o. 6 مجموعه راه حل برای x1، x2، x3، x4، x5 به دست آمد: (00000)، (00001)، (00011)، (00111)، (01111)، (11111). با استدلال مشابه، به این نتیجه می رسیم که برای y1، y2، y3، y4، y5 مجموعه ای از راه حل ها وجود دارد. چون این معادلات مستقل هستند، یعنی. آنها متغیرهای مشترکی ندارند، سپس راه حل این سیستم معادلات (بدون در نظر گرفتن معادله سوم) 6 * 6 = 36 جفت "X" و "Y" خواهد بود. معادله سوم را در نظر بگیرید: y5→ x5 =1 راه حل جفت است: 0 0 0 1 1 1 جفت راه حل نیست: 1 0

بیایید راه حل های به دست آمده را با هم مقایسه کنیم که در آن y5 = 1، x5 = 0 مناسب نیست. 5 جفت از این قبیل برای سیستم وجود دارد: 36-5 = 31. پاسخ: 31 ترکیبی لازم بود!!!

روش برنامه نویسی پویا معادله منطقی x 1 → x 2 → x 3 → x 4 → x 5 → x 6 = 1 چند راه حل مختلف دارد که x 1، x 2، ...، x 6 متغیرهای منطقی هستند؟ پاسخ نیازی به فهرست کردن تمام مجموعه‌های مختلف مقادیر متغیری که این برابری برای آنها وجود دارد ندارد. به عنوان پاسخ، شما باید مقادیر چنین مجموعه هایی را مشخص کنید.

راه حل مرحله 1. تجزیه و تحلیل شرط در سمت چپ در معادله، عملیات استلزام به ترتیب نوشته شده است، اولویت یکسان است. بیایید بازنویسی کنیم: ((((X 1 → X 2) → X 3) → X 4) → X 5) → X 6 = 1 NB! هر متغیر بعدی نه به متغیر قبلی، بلکه به نتیجه مفهوم قبلی بستگی دارد!

مرحله 2. آشکار کردن الگو بیایید مفهوم اول را در نظر بگیریم، X 1 → X 2. جدول حقیقت: X 1 X 2 X 1 → X 2 0 0 1 0 1 1 1 0 0 1 1 1 از یک 0 2 واحد گرفتیم و از 1 ما یک 0 و یک 1 گرفتیم. فقط یک 0 و سه 1 وجود دارد، این نتیجه عملیات اول است.

مرحله 2. آشکار کردن یک الگو با اتصال x 3 به نتیجه عملیات اول، به دست می آید: F(x 1 ,x 2) x 3 F(x 1 ,x 2)  x 3 0 0 1 0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 از دو 0 – دو 1، از هر 1 (3 عدد وجود دارد) یکی 0 و یکی 1 (3+3)

مرحله 3. استخراج فرمول T.o. می توانید فرمول هایی برای محاسبه تعداد صفرهای N i و تعداد یک ها E i برای معادله ای با متغیرهای i ایجاد کنید:

مرحله 4. پر کردن جدول جدول را از چپ به راست برای i = 6 پر کنید و تعداد صفرها و یک ها را با استفاده از فرمول های بالا محاسبه کنید. جدول نشان می دهد که چگونه ستون بعدی از ستون قبلی ساخته شده است: تعداد متغیرها 1 2 3 4 5 6 تعداد صفرها N i 1 1 3 5 11 21 تعداد واحدها E i 1 2*1+1= 3 2*1 +3= 5 11 21 43 پاسخ: 43

روش با استفاده از ساده سازی عبارات منطقی معادله چند راه حل مختلف دارد ((J → K) → (M  N  L))  ((M  N  L) → (¬ J  K))  (M → J) = 1 که در آن J، K، L، M، N متغیرهای منطقی هستند؟ پاسخ نیازی به فهرست کردن مجموعه‌های مختلف مقادیر J، K، L، M و N ندارد که این برابری برای آنها برقرار است. به عنوان پاسخ، باید تعداد این مجموعه ها را مشخص کنید.

راه حل توجه داشته باشید که J → K = ¬ J  K تغییر متغیرها را معرفی می کنیم: J → K=A, M  N  L =B بیایید با در نظر گرفتن تغییر معادله را بازنویسی کنیم: (A → B)  (B → الف)  (M → J)=1 4. (A  B)  (M → J)= 1 5. بدیهی است که A  B برای مقادیر یکسان A و B 6. آخرین مفهوم M → را در نظر بگیرید. J = 1 این ممکن است اگر: M= J=0 M=0، J=1 M=J=1

راه حل چون A  B، سپس وقتی M=J=0 1 + K=0 می گیریم. بدون راه حل هنگامی که M=0، J=1، 0 + K=0، K=0، و N و L هر کدام هستند، 4 راه حل می گیریم: ¬ J  K = M  N  L K N L 0 0 0 0 0 1 0 1 0 0 1 1

راه حل 10. وقتی M=J=1 0+K=1 *N * L یا K=N*L به دست می آید، 4 راه حل: 11. مجموع 4+4=8 راه حل دارد پاسخ: 8 K N L 0 0 0 0 0 1 0 1 0 1 1 1

منابع اطلاعاتی: O.B. بوگومولوا، دی.یو. یوسنکوف B15: وظایف جدید و راه حل های جدید // انفورماتیک، شماره 6، 2012، ص. 35 – 39. K.Yu. پولیاکوف. معادلات منطقی // انفورماتیک، شماره 14، 1390، ص. 30-35. http://ege-go.ru/zadania/grb/b15/، [منبع الکترونیکی]. http://kpolyakov.narod.ru/school/ege.htm، [منبع الکترونیکی].

UDC 004.023

سمنوف سرگئی ماکسیموویچ

ولادی وستوک دانشگاه دولتیاقتصاد و خدمات روسیه ولادی وستوک

در مورد یک راه برای حل سیستم های معادلات منطقی

روشی برای تعیین تعداد راه حل های یک سیستم معادلات منطقی در نظر گرفته شده است. این روش مبتنی بر ساخت یک درخت تصمیم و تعیین روابط عود برای سطح N است. استفاده از روش توسعه‌یافته یک رویکرد سازنده برای حل مسئله B15 آزمون دولتی واحد ارائه می‌کند.

کلمات کلیدیو عبارات: سیستم های معادلات منطقی، درخت تصمیم، روابط تکراری، B15، آزمون دولت واحد.

در عمل، سیستم های معادلات منطقی در طراحی دستگاه های منطق دیجیتال مفید هستند. یکی از مسائل آزمون یکپارچه در علوم کامپیوتر به حل سیستم های معادلات منطقی اختصاص دارد. متأسفانه روش های مختلف شناخته شده برای حل این مشکل به ما اجازه نمی دهد یک رویکرد واحد برای حل این مشکل تدوین کنیم. در نتیجه حل مشکل مشکلات زیادی را برای فارغ التحصیلان ایجاد می کند. ما روشی را برای حل سیستم های معادلات منطقی ارائه می دهیم که به فارغ التحصیل اجازه می دهد از یک الگوریتم بسیار خاص پیروی کند. ایده این روش در ارائه شده است. ما این ایده (ساخت درخت تصمیم) را تقریباً بدون استفاده از جداول صدق برای کل درخت اعمال و توسعه دادیم. هنگام تصمیم گیری وظایف مختلفمعلوم شد که تعداد راه حل های بسیاری از سیستم های معادلات منطقی از روابط عود، مانند اعداد فیبوناچی و غیره تبعیت می کند.

سیستم های معادلات منطقی ما به نمادهای زیر پایبند خواهیم بود: تفکیک (+)، ربط ()، OR انحصاری (©)، مفهوم (->■)، معادل (=)، نفی (-■). در شکل ها، دایره تاریک نشان دهنده 1 و دایره روشن نشان دهنده 0 است. Fl تعداد راه حل های با X1 برابر با 1 است. Fo تعداد راه حل های با X1 برابر با 0 است. N تعداد متغیرهای سیستم است. از معادلات F(N) = F1(N) + F0(N) - تعداد کل راه حل ها.

وظیفه 1. باید تعداد جواب های سیستم معادلات را پیدا کنید (تست شماره 2)

ابتدا X1 = 1 را فرض می کنیم. سپس برای معادله اول مقادیر X2 و X3 می توانند هر کدام باشند. بنابراین، درخت تا سطح سوم ساخته می شود. بعد، با در نظر گرفتن X2 و X3، X4 را انتخاب کنید. پس از این، الگوریتم برای هر سه متغیر تکرار می شود (شکل 1). با شروع از سطح چهارم، می توانید متوجه شوید که Fl(4)=Fl(3)+Fl(1)، Fl(5)=Fl(4)+Fl(2). بنابراین، Fl(N) = Fl(N-1) + Fl(N-3) (1) را بدست می آوریم.

برنج. 1. وظیفه 1

از رابطه (1) چنین می شود:

Bx(8) = 16 + 7 = 23،

Fl(9) = 23 + 11 = 34.

برای ساختن یک درخت از ابتدا، می توانید از شاخه پایینی شکل 1 استفاده کنید. 1. به راحتی می توان دید که درخت اصلی را تکرار می کند، اما با تغییر 2 به راست، یعنی

مجموع، F(9) = Fl(9) + Fo(9) = 34 + 16 = 50.

هنگام ساخت یک درخت تصمیم، می توانید به صورت بصری روابط تکراری را برای تعیین تعداد راه حل ها در سطح N ایجاد کنید.

اصل استقراء ریاضی می گوید: بگذارید دنباله ای از گزاره های Fl، F2، Fз وجود داشته باشد و گزاره اول Fl درست باشد. می‌توانیم ثابت کنیم که صدق عبارت FN بر صدق FN+l دلالت دارد. سپس تمام عبارات این دنباله درست هستند.

بیایید به شکل نگاه کنیم. 2 برای کار 1.

k2 > 3 x5 xb x7

برنج. 2. تجزیه و تحلیل درخت تصمیم

شکل 2 شکل هایی را نشان می دهد که دارای یک راس مشترک (ترکیب مقادیر متغیر) برای پنج معادله اول سیستم هستند. هر معادله شامل سه متغیر است، بنابراین ارقام از مقادیر سه متغیر (سه سطح درخت) تشکیل شده اند. به منظور شناسایی ارقام، نمادها می توانند معرفی شوند. با این حال، ما به صورت زیر عمل می کنیم: برای هر شکل تعداد دایره هایی که آن را تشکیل می دهند (مقادیر متغیر) اختصاص می دهیم. سپس معادلات زیر را برای دنباله بدست می آوریم:

4. 7, 4, 4, 1, 7

5. 7, 4, 4, 1, 7, 7, 4.

از معادله 4 می بینید که شکل های معادله N از شکل های معادله N-1 و شکل های معادله N-3 تشکیل شده است. مهم این است که هیچ رقم دیگری برای این نوع معادلات وجود نداشته باشد و نمی تواند باشد، یعنی انتقال از یک معادله به معادله دیگر با افزایش تعداد ارقام از یک مجموعه محدود با توجه به شدت انجام می شود. قوانین خاص. این واقعیت اصلی برای بیان استقرا است که برای معادله N+1 مجموعه ارقام از شکل های معادله N و شکل های معادله N-2 تشکیل شده است.

راه دیگر برای شناسایی ارقام، تعیین تعداد مقادیر متغیر در آخرین سطح برای یک معادله معین است، یعنی باید از شماره معادله به عدد سطح درخت بروید، زیرا باید تعداد راه حل ها را تعیین کنیم. برای سیستم معادلات سپس برای درخت ساخته شده دنباله ای بدست می آوریم: 1، 2، 4، 5، 7، 11، 16. برای این دنباله، فرمول معتبر است: FN = FN-1 + FN-3.

مطابق با استدلال ما، این فرمول برای N+1 و با استقرا برای هر N صادق خواهد بود.

روش اثبات فوق را می توان برای هر سیستمی از این نوع استفاده کرد. در عمل، تعیین رابطه عود برای سطح N کافی است زیرا بر اساس مجموعه محدودی از ارقام و روش های تبدیل آنها هنگام حرکت از یک معادله مربوط به سطح N به یک معادله مربوط به سطح N+1 است.

وظیفه 2. ما باید تعداد راه حل های سیستم معادلات را پیدا کنیم (4.16)

(X1=X2) + (X1 = X3) = 1 (X2=X3) + (X2 = X4) = 1 (X3=X4) + (X3 = X5) = 1 (X4=X5) + (X4 = X6) =1 (X5 = X6) + (X5 = X7) = 1

XI Х2 ХЗ >:1 Х5 Хб Х7

برنج. 3. وظیفه 2

برای به دست آوردن تعداد راه حل های کار 2، نمی توان یک درخت تصمیم کامل ساخت (شکل 3)، زیرا بدیهی است که Fl(N) = N. به طور مشابه، Fo(N) = N. مجموع F( 7) = 7 + 7 = 14.

وظیفه 3. باید تعداد جواب های سیستم معادلات را پیدا کنید (تست شماره 1)

(Х1 ^ Х2) ■ (Х2 ^ Хз) ■ (Хз ^ Х4) ■ (Х4 ^ Х5) = 1

(Yl ^ Y2) ■ (Y2 ^ Yz) ■ (Yz ^ Y4) ■ (Y4 ^ Y5) = 1

(Yl ^ X1) ■ (Y2 ^ X2) ■ (Yz ^ X3) ■ (Y4 ^ X4) ■ (Y5 ^ X5) = 1

شکل 4 درخت های تصمیم X و Y و جداول صدق مربوطه را نشان می دهد.

برنج. 4. وظیفه 3

از دو معادله اول، چون X و Y مستقل هستند، نتیجه می شود که تعداد کل جواب ها F(5) = 6 * 6 = 36. برای در نظر گرفتن معادله سوم، لازم است که هر متغیر Y به محاسبه کنید که چند مجموعه از جدول X معادله را برآورده نمی کند. در صورتی که Yi = 1 و Xi = 0 باشد، مفهوم Yi ^ Xi = 0 است. 5. برای Y2 = 1 چنین خطوط - 4، و غیره. تعداد کلردیف هایی که معادله سوم را برآورده نمی کنند 5 + 4 + 3 + 2 + 1 = 15 هستند.

بنابراین، تعداد کل راه حل های امکان پذیر 36 - 15 = 21 است. وظیفه 4. ما باید تعداد راه حل های سیستم معادلات را پیدا کنیم (, 4.17.a)

(X1=X2) + (X1 = X3) = (X2 = X3) + (X2 = X4) = (X4 = X5) + (X4 = X6) = (X5 = X6) + (X5 = X7) = (Xb =X7) + (Xb = X8) = (X5=X6) = 0

برنج. 5. وظیفه 4

برای این مثال، تعیین فرمول نهایی F(N) دشوار است، ساختن درخت تصمیم تا انتها (یا حداقل X6) آسان تر است. شکل 5 درخت تصمیم ساخته شده را نشان می دهد. در نتیجه F(8) = Fl(8) + Fo(8) = 5 + 5 = 10 بدست می آوریم.

وظیفه 5. یافتن تعداد جواب های سیستم معادلات ضروری است (, 4.17.b)

(X1 = X2) + (X1 = X3) = 1 (X2 = X3) + (X2 = X4) = 1 (X3 = X4) + (X3 = X5) = 1 (X4 = X5) + (X4 = X6) =1 (X5 = X6) + (X5 = X7) = 1 (X6 = X8) = 1

برای این مثال، و همچنین برای مثال قبلی، ساختن درخت تصمیم تا انتها آسانتر است (شکل 6). در نتیجه، F(8) = Fl(8) + Fo(8) = 7 + 7 = 14 را دریافت می کنیم.

وظیفه 6. شما باید تعداد جواب های سیستم معادلات را پیدا کنید ([!]> 4.17.c)

(Х!8"Х2) + (Х2ЭХз) = 1 (Х2фХз) + (Хз = Х4) = 1 (Хз8"Х4) + (Х4 = Х5) = 1 (Х4©Х5) + (Х5 = Хб) = 1 (X5fXb) + (Xb = X7) = 1 (Xb©X7) + (X7 = X8) = 1 درخت تصمیم در شکل نشان داده شده است. 7.

XI X2 X3 X4 X5 X6 X7 X8 XI X2 X3 X4 X5 X6 X7 X8

برنج. 6. وظیفه 5 شکل. 7. وظیفه 6

برای این سیستم معادلات امکان ساخت درخت تصمیم کامل وجود نداشت، زیرا قبلاً از سوم - مرحله چهارمواضح است که F1(N) = N. به راحتی می توان دریافت که Fo(N) را می توان از درختی بدست آورد که در سطح دوم از صفر شروع می شود. سپس Fo(N) = N. مجموع، F(8) = Fl(8) + Fo(8) = 8 + 8 = 16.

وظیفه 7. ما باید تعداد راه حل های سیستم معادلات را پیدا کنیم

(Х4ЭХ5) + (Х4 ©Х6) = 1 (Х5©Хб) + (Х5 ©Х7) = 1

توجه داشته باشید که اگر X! = X2 = 1، سپس اولین معادله برای Xз = 0 برآورده می شود. اجازه دهید ابتدا یک درخت برای Xl = X2 = 1 بسازیم (شکل 8). سپس تعداد محلول ها Fl(N) = Fll(N) + Flo(N) است.

XI X2 X3 X4 X5 X6 X7 X8

برنج. 8. وظیفه 7

از شکل 8 مشخص است که تعداد محلول ها F11(N) = F11(N-1) + F11(N-2) است. به عبارت دیگر، تعداد راه حل ها با اعداد فیبوناچی توصیف می شود. شاخه دوم درخت برای F10 نیازی به ساخت ندارد، زیرا از شکل 1 به دست آمده است. 1، از سطح دوم شروع کنید. سپس F10(N) = F11(N+1). در نهایت دریافتیم که Fll(8) = 1з و Flo(8) = Fll(9) = 1з + 8 = 21. سپس Fl(8) = Fll(8) + Flo(8) = 1з + 21 = З4.

برای به دست آوردن F0(N)، ساخت درخت تصمیم نیز ضروری نیست، زیرا از شکل 2 به دست آمده است. 1 شروع از سطح سوم. سپس Fo(N) = Fll(N+2). از اینجا دریافت می کنیم که Fo(8) = Fll(10) = Fll(9) + Fll(8) = 21 + 1з = z4. بنابراین، تعداد کل راه حل ها F(8) = F1(8) + F0(8) = z4 + z4 = 68 است.

وظیفه 8. شما باید تعداد راه حل های سیستم معادلات را پیدا کنید ([z]، وظیفه 2)

(X1 + X2) ^ (X3 + X4) = 1 (X3 + X4) ^ (X5 + X6) = 1 (X5 + X6) ^ (X7 + X8) = 1 (X7 + X8) ^ (X9 + X10) = 1

بیایید جایگزینی (X1 + X2) = Yl و غیره را انجام دهیم. و ما یک سیستم معادلات بدست می آوریم:

^ ^ Y2 = 1 Y2 ^ Yz = 1 Yz ^ Y4 = 1 Y4 ^ Y5 = 1

درخت تصمیم و جدول حقیقت برای این سیستم دقیقاً مشابه درخت و جدول نشان داده شده در شکل است. 4. با در نظر گرفتن جایگزینی، توجه می کنیم که عبارت (X1 + X2) در سه حالت برابر با یک است (به استثنای گزینه ای که هر دو متغیر برابر با صفر هستند).

از آنجایی که متغیرهای Y مستقل هستند، پس برای ردیف اول جدول صدق نشان داده شده در شکل. 4، تعداد ترکیب های مختلف 35، برای خط دوم - 34 و غیره است. تعداد کل ترکیب های مختلف 35 + 34 + 33 + 32 + 31 + 30 = 364 است.

وظیفه 9. شما باید تعداد راه حل های سیستم معادلات را پیدا کنید (، وظیفه 4)

(^ ^ ب) ■ (-X ^ Xз) ■ № ^ X) ■ (-X ^ Кз) = 1 № ^ Y2) ■ (У1 ^ Yz) ■ (-Г1 ^ Y4) ■ (У1 ^ Y5) = 1 (-X + Y 1) ■ (-X + Y5) = 1

برای X و Y درخت های تصمیم زیر را داریم

برنج. 9. وظیفه 8

با در نظر گرفتن معادله سوم، چهار مجموعه ترکیب زیر را بدست می آوریم:

A - C: 4 * 4 = 16 ((-£ 1 + Y 1) ■ (-X + Y5) = (0 + 1) ■ (0 + 1) = 1) B - C: 4 * 4 = 16 ( (-X + Y 1) ■ (-X + Y5) = (1 + 1) ■ (1 + 1) = 1) A - D: = 0 (0 + 0) ■ (-X + Y5) = 0) ب - د: 4 * 4 = 16 (1 + 0) ■ (1 + Y5) = 1) در مجموع 48 مجموعه راه حل وجود دارد.

وظیفه 10. ما باید تعداد جواب های سیستم معادلات را پیدا کنیم (^1 = b) + (Xz = X)) ■ = b) + -фз = X4)) =1 ((Xz = X4) + ( X5 = X6)) ■ (-(X = X) + -(X = X6)) =1 ((X5 = X6) + ^7 = X«)) ■ (-(X = X6) + -(^7 = X8)) = 1

((X7 = X8) + (X9 = Xlo)) ■ (-^7 = X8) + = Xlo)) =1 بیایید جایگزین را انجام دهیم: (Xl = b) = Yl (Xz = X4) = Y2

(X5 = X) = Yz (X7 = X8) = Y4 (X9 = X10) = Y5

(U^2) ■ (-Ъ + ^)=1

(Y2+Yz) ■ شماره + -Тз)=1

(Yz+Y4) ■ № + ^)=1

(Y4+Y5) ■ (^4 + ^)=1

شکل 10 درخت تصمیم را نشان می دهد

U1 U2 UZ U4 U5

برنج. 10. وظیفه 10

وظیفه 11. ما باید تعداد راه حل های سیستم معادلات را پیدا کنیم (مثال 2)

X1 + X2 = 1 -X2 + Xs = 1

شکل 11 درخت تصمیم را نشان می دهد. ما خودمان را به جای ده به چهار سطح محدود کردیم، زیرا واضح است که F1(N) = 1 و F0(N) = N. سپس P(L) = P1(L) + BoSY) = 1 + N. در مورد ما ، P(10) = 1 + 10 = 11.

برنج. 11. وظیفه 11

تکلیف 12. باید تعداد جواب های سیستم معادلات را پیدا کنیم (مثال h)

(X1 = X2) + (X2 = X3) = 1

(X1 = X3) + (X3 = X4) (X1 = X4) + (X4 = X5) (X1 = X5) + (X5 = X6) (X1 = X6) + (X6 = X7) (X1 = X7) + (X7 = X8) (X1 = X) + (X8 = X9) (X1 = X9) + (X9 = X10) (X1 = X10) = 0

برنج. 12. وظیفه 12

پس از ساختن یک درخت تصمیم از "1" (خودمان را به پنج سطح محدود می کنیم)، توجه می کنیم که Fl(N) = N. علاوه بر این، مقادیر Xn شامل مقادیر N-1 "0" و یک مقدار "1". با این حال، آخرین معادله در سیستم ما مقدار "1" را برای X10 ممنوع می کند. بنابراین، تعداد جواب های Fl(10) = 10 - 1. به راحتی می توان دید که درخت تصمیم از "0" متقارن خواهد بود (به جای صفر، یک وجود خواهد داشت). بنابراین F0 = 10 - 1. در نهایت

F(N) = 2 x 9 = 18.

وظیفه 13. باید تعداد جواب های سیستم معادلات را پیدا کنیم (مثال 4)

- (X1 = X2) + (X3 = X4) = 1

- (Xs = X4) + (X5 = X) = 1

- (X = X) + (X7 = X) = 1

- (X7 = X8) + (X9 = X10) = 1

بیایید جایگزین کنیم:

(X1 = X2) = Yl

(H5 = Х) = Yz

(X7 = X8) = Y4

(X9 = X10) = Y5

اجازه دهید سیستم معادلات را با در نظر گرفتن جایگزینی بازنویسی کنیم:

از کار 11 مشخص است که F(5) = 5 + 1 = 6. جدول صدق در شکل نشان داده شده است. 13.

U1 U2 UZ U4 U5

برنج. 13. وظیفه 13

با در نظر گرفتن جایگزینی، توجه می کنیم که عبارت ^ = X2 در دو مورد (زمانی که مقادیر متغیرها مطابقت دارند) برابر با یک (یا صفر) است. با در نظر گرفتن استقلال متغیرها برای هر ردیف از جدول، متوجه می شویم که تعداد مجموعه های حل 25 = 32 است. تعداد کل مجموعه های حل 6 * 32 = 192 است.

وظیفه 14. ما باید تعداد راه حل های سیستم معادلات را پیدا کنیم (، کار 1)

((X = b) ■ (Xz = X4)) + (4X1 = b) ■ -(X = X)) =0 ((Xz = X4) ■ (X5 = X6)) + (4X3 = X4) ■ - (X = X6)) = 0

((X5 = X) ■ (X7 = X8)) + (-(X = X6) ■ 4X7 = X8)) =0 ((X7 = X8) ■ (X9 = X«،)) + (-(^7 = X8) ■ ^9 = Xlo)) =0 بیایید جایگزین را انجام دهیم:

ب) = Yl (X = ^4) = Y2

(X5 = X6) = Yz ^7 = X8) = Y4 ^9 = Xlo) = Y5

اجازه دهید سیستم معادلات را با در نظر گرفتن جایگزینی بازنویسی کنیم:

(UL) + (-U« ■ -U2)=0

(Y2 Yz) + (-У2 ■ -У3)=0 (У3-У4) + (-У3 ■ -У4)=0 (У4-У5) + (-У4 ■ -У5)=0

(U2 = Yz) = 0 (Uz = U4) = 0 (U4 = U5) = 0

شکل 14 درخت تصمیم را نشان می دهد

U1 U2 UZ U4 U5

برنج. 14. وظیفه 14

با در نظر گرفتن جایگزینی، توجه می کنیم که عبارت (X1 = X2) در دو مورد (زمانی که مقادیر متغیرها با هم مطابقت دارند) برابر با یک (یا صفر) است. با در نظر گرفتن استقلال متغیرها برای هر درخت، به این نتیجه می رسیم که تعداد مجموعه راه حل ها 25 = 32 است. تعداد کل مجموعه راه حل ها 64 عدد است.

کار 15. باید تعداد راه حل های سیستم معادلات را بیابید (، وظیفه 2)

(X4 X5) + (-X4 -X5) + (X4 = X) = 1

(X5 X) + (-X -X6) + (X5 = X7) = 1

(X X7) + (-X -X7) + (X = X8) = 1

(X7 X) + (-X7 -X8) + (X7 = X9) = 1

(X8 X9) + (-X -X9) + (X8 = X10) = 1

(X1 = X2) + (X1 = X3) = 1

(X = Xs) + (X2 = X4) = 1

(Xs = X4) + (Xs = X5) = 1

(X4 = X5) + (X4 = X) = 1

(X5 = X6) + (X5 = X7) = 1

(X = X7) + (X6 = X8) = 1

(X7 = X8) + (X7 = X9) = 1

(X = X9) + (X8 = X10) = 1

اما این سیستم سیستم را از کار 5، فقط بدون شرط محدودیت و برای N = 10 تکرار می کند. سپس تعداد راه حل ها برابر است با F(N) = F1(N) + F0(N) = N + N. برای N. = 10 ما F(N) = 20 را بدست می آوریم.

تکلیف 16. باید تعداد جواب های سیستم معادلات را پیدا کنیم (تکلیف 3)

(X1 X2) + (-X1 -X2) + (X1 = X3) = 1

(X2 Xs) + (-X -Xs) + (X2 = X4) = 1

(Xs X4) + (-Xs -X4) + (Xs = X5) = 1

(X4 X5) + (-X -X5) + (X4 = Xb) = 1

(X5 Xb) + (-X -Xb) + (X5 = X7) = 1

(Xb X7) + (-Xb -X7) + (Xb = X8) = 1

(X7 X8) + (-X7 -X8) + (X7 = X9) = 1

(X8 X9) + (-X8 -X9) + (X8 = X10) = 0

این سیستم معادلات، مانند کار قبلی، می تواند به صورت زیر بازنویسی شود:

(XI = X2) + (XI = X3) = 1 (X = X3) + (X2 = X) = 1 (X3 = X) + (X3 = X5) = 1 (X = X5) + (X4 = Xb) = 1 (X5 = Xb) + (X5 = X7) = 1 (Xb = X7) + (Xb = X8) = 1 (X = X8) + (X7 = X9) = 1 (X = X9) + (X8 = Xxc) = 0

از آخرین معادله به راحتی می توان بررسی کرد که پس از N = 8، تعداد راه حل ها متوقف می شود. سپس F(10) = F(8) = 8 + 8 = 16.

وظیفه 17. ما باید تعداد راه حل های سیستم معادلات را پیدا کنیم (تکلیف 4)

(X1 X2) + (-X1 -X2) + (X2 Xs) + (-X2 -Xs) = 1

(Х2 Хз) + (-Х2 -Хз) + (Хз Х) + (-Хз ■ -Х4) = 1

(Хз Х) + (-Хз -Х4) + (Х4 Х5) + (-Х4 -Х5) = 1

(X4 X) + (-X -X5) + (X5 Xb) + (-X5 -Xb) = 1

(X5 Xb) + (-X -Xb) + (Xb X7) + (-Xb ■ -X7) = 1

(Xb X7) + (-Xb -X7) + (X7 X8) + (-X7 -X8) = 1

(X7 X) + (-X7 -X8) + (X8 X9) + (-X8 -X9) = 1

(X8 X9) + (-X8 -X9) + (X9 X10) + (-X9 ■ -X10) = 1

توجه داشته باشید که سیستم معادلات را می توان به صورت زیر بازنویسی کرد:

(X= X2) + (X = Xs) = 1 (X= Xs) + (X = X) = 1 (Xs= X4) + (X4 = X5) = 1 (X = X5) + (X5 = Xb) = 1 (X5 = Xb) + (Xb = X7) = 1

(Xb = X7) + (X7 = X) = 1 (X7 = X8) + (X8 = X9) = 1 (Xb = X 9) + (X9 = X10) = 1

در شکل 15، درخت تا سطح پنجم ساخته شده است و مشخص است که تعداد راه حل ها با اعداد فیبوناچی، یعنی Fl(N) = Fl(N-1) + Fl(N-2) توصیف شده است. سپس Fl(10) = 89. به راحتی می توان بررسی کرد که برای F0(N) درخت متقارن باشد. بنابراین Fo(10) = 89. B(10) = p1(10) + Po(10) = 89 + 89 =178.

برنج. 15. وظیفه 17

وظیفه 18. ما باید تعداد راه حل های سیستم معادلات را پیدا کنیم (، کار 5)

(X1 X2) + (-X1 -X2) + (X2 Xs) + (-X2 ■ -Xs) = 1

(Х2 Хз) + (-Х -Хз) + (Хз Х4) + (-Хз -Х4) = 1

(Хз Х4) + (-Хз -Х4) + (Х4 Х5) + (-Х4 ■ -Х5) = 1

(X4 X5) + (-X4 -X5) + (X Xb) + (-X5 ■ -Xb) = 1

(X5 Xb) + (-X5 -Xb) + (Xb X7) + (-Xb ■ -X7) = 1

(Xb X7) + (-Xb -X7) + (X7 X8) + (-X7 ■ -X8) = 1

(X7 X8) + (-X7 -X8) + (X8 X9) + (-X8 -X9) = 1

(X8 X9) + (-X8 -X9) + (X9 X10) + (-X9 ■ -X10) = 0

توجه داشته باشید که سیستم معادلات را می توان به صورت زیر بازنویسی کرد:

(X= X2) + (X2 = X3) = 1 (X2 = X3) + (X3 = X4) = 1

(Xs = X) + (X4 = X5) = 1 (X = X5) + (X5 = Xb) = 1 (X = Xb) + (Xb = X7) = 1 (Xb = X7) + (X7 = X8) = 1 (X7 = X8) + (X8 = X9) = 1 (X8 = X 9) + (X = X10) = 0

وظیفه 18 شبیه به کار 17 است، با این حال، آخرین معادله منجر به این واقعیت می شود که با شروع از سطح هفتم، تعداد راه حل ها افزایش نمی یابد. در نتیجه، F(10) = Fl(10) + Fo(10) = Fl(7) + Fo(7) = 21 + 21 = 42.

وظیفه 19. ما باید تعداد راه حل های سیستم معادلات را پیدا کنیم (، وظیفه ب)

(X= X2) + (X = X10) = 1 (X= X3) + (X2 = X10) = 1 (X3= X4) + (X = X10) = 1 (X = X5) + (X = X10) = 1 (X = Xb) + (X5 = X10) = 1 (Xb = X7) + (Xb = X10) = 1 (X7 = X) + (X = X10) = 1 (X8 = X9) + (X = X10) = 1 (X9 = X10) + (X9 = X10) = 1 (X = X10) = 0

- - - -*- - - -*-O

برنج. 1b. وظیفه 19

درخت های تصمیم گیری برای به دست آوردن F1(N) و F0(N) در شکل نشان داده شده اند. 1b. با این حال، معادله (X9 = X10) = 1 را نمی توان برآورده کرد. بنابراین، سیستم معادلات هیچ راه حلی ندارد.

وظیفه 20. شما باید تعداد راه حل های سیستم معادلات را پیدا کنید (، وظیفه 7)

(X ^ X2) + (X ^ Xs) = 1 (X2 ^ Xs) + (X2 * X4) = 1 (Xs ^ X4) + (Xs ^ X5) = 1 (X ^ X5) + (X4 ^ Xb) = 1 (X5 ^ Xb) + (X5 ^ X7) = 1 (Xb ^ X7) + (Xb ^ X8) = 1

(X7 ^ Xs) + (X7 ^ X9) = 1 (Xs ^ X9) + (Xs ^ X10) = 1

شکل 17 درخت تصمیم گیری از "1" را نشان می دهد.

برنج. 17. وظیفه 20 شکل. 18. وظیفه 20

به جای ده سطح، ما خودمان را به پنج سطح محدود کردیم، زیرا وظیفه مشابه کار 17 است. با این حال، از "0" درخت متفاوت به نظر می رسد (شکل 18).

توجه داشته باشید که F0(N) = Fx(N+1) - 1. سپس Fx(10) = 89، و F0(10) = Fx(11) - 1 = 144 - 1. مجموع، F(10) = F1 ( 10) + F0(10) = 89 + 143 = 232.

در پایان، ما برنامه ای را در BASIC VBA ارائه می دهیم که با آن می توانید سیستم های معادلات منطقی را حل کنید. این برنامه ممکن است هنگام ایجاد سیستم های جدید معادلات مورد نیاز باشد. شکل 19 برنامه مورد استفاده برای حل سیستم معادلات وظیفه 7 را نشان می دهد.

در برنامه نشان داده شده در شکل. 19، آرایه m و متغیر c حاوی مقادیر متغیرهایی هستند که سیستم معادلات را از کار 7 راضی می کند. برنامه پاسخ 68 را تولید می کند. برنامه از این واقعیت استفاده می کند که تعداد مجموعه های مختلف مقادیر n متغیر منطقی 2n است. برای به دست آوردن همه مجموعه ها، باید از 0 به 2n-1 حلقه بزنید. در هر مرحله، متغیر حلقه به سیستم باینری تبدیل می شود، نتیجه در آرایه m نوشته می شود و سپس شرایط از سیستم معادلات بررسی می شود. برای حل یک سیستم معادلات دیگر کافی است بعد آرایه m را تغییر دهید، مقدار متغیر vg (برابر بعد) را تغییر دهید و شرایط آزمون را تغییر دهید.

Dim m(S) به عنوان عدد صحیح، k به عنوان عدد صحیح، j. به عنوان عدد صحیح. _ j به عنوان عدد صحیح. N به عنوان عدد صحیح، vg به عنوان عدد صحیح Dim با رشته به عنوان vg=S j-0

برای 1 به 2 ■""■ vg "از 1 تا 2n حلقه بزنید. جایی که n=,.g برای k = 1 به vg

N = ).- 1: باینری e pr e c put e n از صفر k= 1 شروع نمی شود

آیا "^Tiils N > 0 "ترجمه سیستم باینری m(k) = N Mod 2 K = N ■ 2 k=k+ ! حلقه

Ifim(l) O m(2) or m(l)0- ni(3)) And_ "شرایط معادله (m(2)

c= "" "متغیر c در هر مرحله حاوی جواب سیستم برای k= 1 سپس vg خواهد بود

с = с - Foimat(m(k)j بعدی k j-j-1 پایان اگر بعدی I.

Ms^Eox i "تعداد راه حل

VvVvVlVvVvv- -1 i

برنج. 19. برنامه برای کار 7

1. کریلوف اس.اس. آزمون یکپارچه دولتی 2014. علوم کامپیوتر. وظایف آزمون موضوعی / S.S. کریلوف، دی.ام. اوشاکوف. - م.: انتشارات "امتحان". - 245 ثانیه

2. وب سایت K.Yu. پولیاکوا. حالت دسترسی: http://kpolyakov.namd.-ru/download/inf-2011-14.pdf

3. دوره گواهی متدولوژیک شرکت "1C" "آمادگی برای آزمون دولتی واحد در علوم کامپیوتر". ماژول 1" - M.: انتشارات "1C". - 218 ص.

4. آزمون یکپارچه دولتی در علوم کامپیوتر را با موفقیت بگذرانید. حالت دسترسی: http://infoegehelp.ru/index.php?Itemid=77&id=103&option=com_con-