მუნიციპალური საბიუჯეტო საგანმანათლებლო დაწესებულება

"მე-18 საშუალო სკოლა"

ბაშკორტოსტანის რესპუბლიკის ქალაქ სალავატის ურბანული უბანი

ლოგიკური განტოლებების სისტემები

საგამოცდო ამოცანებში ინფორმატიკაში

განყოფილება "ლოგიკის ალგებრის საფუძვლები" გამოცდის ამოცანები ითვლება ერთ-ერთ ყველაზე რთულ და ცუდად ამოხსნად. ამ თემაზე დავალების შესრულების საშუალო პროცენტი ყველაზე დაბალია და არის 43,2.

კურსის განყოფილება	დავალებების ჯგუფების მიხედვით შესრულების საშუალო პროცენტი
ინფორმაციის კოდირება და მისი რაოდენობის გაზომვა
ინფორმაციის მოდელირება
რიცხვითი სისტემები
ლოგიკის ალგებრის საფუძვლები
ალგორითმიზაცია და პროგრამირება
საინფორმაციო და საკომუნიკაციო ტექნოლოგიების საფუძვლები

KIM 2018-ის სპეციფიკაციაზე დაყრდნობით, ეს ბლოკი მოიცავს სხვადასხვა დონის სირთულის ოთხ ამოცანას.

№ დავალებები	შემოწმებული შინაარსის ელემენტები	დავალების სირთულის დონე
	სიმართლის ცხრილების და ლოგიკური სქემების აგების უნარი
	ინტერნეტში ინფორმაციის მოძიების შესაძლებლობა
	ძირითადი ცნებებისა და კანონების ცოდნა მათემატიკური ლოგიკა
	ლოგიკური გამონათქვამების აგების და გარდაქმნის უნარი

დავალება 23 არის სირთულის მაღალი დონე, შესაბამისად მას აქვს შესრულების ყველაზე დაბალი პროცენტი. მომზადებულ კურსდამთავრებულებს შორის (81-100 ქულა) 49,8%-მა დაასრულა დავალება, საშუალოდ მომზადებულებმა (61-80 ქულა) 13,7%-ით, დანარჩენი ჯგუფი ამ დავალებას ვერ ასრულებს.

ლოგიკური განტოლებათა სისტემის ამოხსნის წარმატება დამოკიდებულია ლოგიკის კანონების ცოდნაზე და სისტემის ამოხსნის მეთოდების ზუსტ გამოყენებაზე.

განვიხილოთ ლოგიკური განტოლებათა სისტემის ამოხსნა რუკის მეთოდით.

(23.154 პოლიაკოვი კ.იუ.) რამდენი განსხვავებული ამონახსნები აქვს განტოლებათა სისტემას?

((X1  წ1 )  (x2  წ2 ))  (x1  x2 )  (y1  წ2 ) =1

((X2  წ2 )  (x3  წ3 ))  (x2  x3 )  (y2  წ3 ) =1

((x7  წ7 )  (x8  წ8 ))  (x7  x8 )  (წ7  წ8 ) =1

სადაც x1 , x2 ,…, x8, ზე1 ,ი2 ,…,ი8 - ლოგიკური ცვლადები? პასუხს არ სჭირდება ცვლადის მნიშვნელობების ყველა სხვადასხვა ნაკრების ჩამოთვლა, რომლებისთვისაც ეს თანასწორობაა. პასუხად, თქვენ უნდა მიუთითოთ ასეთი კომპლექტების რაოდენობა.

გამოსავალი. სისტემაში შემავალი ყველა განტოლება ერთი და იგივე ტიპისაა და თითოეულ განტოლებაში შედის ოთხი ცვლადი. ვიცით x1 და y1, ჩვენ შეგვიძლია ვიპოვოთ x2 და y2-ის ყველა შესაძლო მნიშვნელობა, რომელიც აკმაყოფილებს პირველ განტოლებას. ანალოგიურად კამათით, ცნობილი x2 და y2-დან შეგვიძლია ვიპოვოთ x3, y3, რომელიც აკმაყოფილებს მეორე განტოლებას. ანუ წყვილის (x1 , y1) ცოდნით და წყვილის (x2 , y2) მნიშვნელობის დადგენით ვიპოვით წყვილს (x3 , y3 ), რომელიც თავის მხრივ მიგვიყვანს წყვილამდე (x4 , y4 ) და ა.შ. on.

ვიპოვოთ პირველი განტოლების ყველა ამონახსნი. ეს შეიძლება გაკეთდეს ორი გზით: ჭეშმარიტების ცხრილის აგება, მსჯელობისა და ლოგიკის კანონების გამოყენებით.

სიმართლის ცხრილი:

				x 1  y 1	x2  y2	(x 1  y1)  (x 2  y2)	(x 1  x2)	(y 1  y2)	(x 1  x2)  (y 1  y2)

სიმართლის ცხრილის აგება შრომატევადი და დროში არაეფექტურია, ამიტომ ვიყენებთ მეორე მეთოდს - ლოგიკურ მსჯელობას. პროდუქტი არის 1, თუ და მხოლოდ იმ შემთხვევაში, თუ თითოეული ფაქტორი არის 1.

(x1  წ1 )  (x2  წ2 ))=1

(x1  x2 ) =1

(წ1  წ2 ) =1

განვიხილოთ პირველი განტოლება. შემდეგი უდრის 1-ს, როდესაც 0 0, 0 1, 1 1, მაშინ (x1 y1)=0 (01), (10), მაშინ წყვილი (x2  წ2 ) შეიძლება იყოს ნებისმიერი (00), (01), (10), (11) და (x1 y1)=1, ანუ (00) და (11) წყვილი (x2 y2)=1 იღებს ერთსა და იმავე მნიშვნელობებს (00) და (11). ამ ამონახსნებიდან გამოვრიცხავთ იმ წყვილებს, რომლებისთვისაც მეორე და მესამე განტოლებები მცდარია, ანუ x1=1, x2=0, y1=1, y2=0.

(x1 , წ1 )	(x2 , წ2 )

წყვილების საერთო რაოდენობა 1+1+1+22= 25

2) (23.160 პოლიაკოვი კ.იუ.) რამდენი განსხვავებული ამონახსნები აქვს ლოგიკურ განტოლებათა სისტემას

(x 1  (x 2  წ 2 ))  (y 1  წ 2 ) = 1

(x 2  (x 3  წ 3 ))  (y 2  წ 3 ) = 1

...

( x 6  ( x 7  წ 7 ))  ( წ 6  წ 7 ) = 1

x 7  წ 7 = 1

გამოსავალი. 1) განტოლებები ერთი ტიპისაა, ამიტომ მსჯელობის მეთოდით ვიპოვით პირველი განტოლების ყველა შესაძლო წყვილს (x1,y1), (x2,y2).

(x1  (x2  წ2 ))=1

(წ1  წ2 ) = 1

მეორე განტოლების ამონახსნი არის წყვილი (00), (01), (11).

ვიპოვოთ ამონახსნები პირველი განტოლებისთვის. თუ x1=0, მაშინ x2, y2 - ნებისმიერი, თუ x1=1, მაშინ x2, y2 იღებს მნიშვნელობას (11).

დავამყაროთ კავშირი წყვილებს შორის (x1, y1) და (x2, y2).

(x1 , წ1 )	(x2 , წ2 )

შევადგინოთ ცხრილი, რომ გამოვთვალოთ წყვილების რაოდენობა თითოეულ ეტაპზე.

							0

ბოლო განტოლების ამონახსნების გათვალისწინებით x 7  წ 7 = 1, ჩვენ აღმოვფხვრათ წყვილი (10). იპოვეთ ამონახსნების საერთო რაოდენობა 1+7+0+34=42

3)(23.180) რამდენი განსხვავებული ამონახსნები აქვს ლოგიკურ განტოლებათა სისტემას

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

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

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

(x7  x8 )  (x9  x10 ) = 1

x1  x3  x5  x7  x9 = 1

გამოსავალი. 1) განტოლებები ერთი და იგივე ტიპისაა, ამიტომ მსჯელობის მეთოდით ვიპოვით პირველი განტოლების ყველა შესაძლო წყვილს (x1,x2), (x3,x4).

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

ამონახსნებიდან გამოვრიცხავთ წყვილებს, რომლებიც 0 (1 0) იძლევა შემდეგში, ეს არის წყვილები (01, 00, 11) და (10).

შეადგინეთ ბმულები წყვილებს შორის (x1,x2), (x3,x4)

ლოგიკური განტოლებების სისტემების ამოხსნის სხვადასხვა გზა არსებობს. ეს არის შემცირება ერთ განტოლებამდე, ჭეშმარიტების ცხრილის აგება და დაშლა.

Დავალება:ამოხსენით ლოგიკური განტოლებათა სისტემა:

განიხილეთ ერთ განტოლებამდე შემცირების მეთოდი . ეს მეთოდი გულისხმობს ლოგიკური განტოლებების ტრანსფორმაციას ისე, რომ მათი მარჯვენა მხარეები ტოლი იყოს ჭეშმარიტების მნიშვნელობის (ანუ 1). ამისათვის გამოიყენეთ ლოგიკური უარყოფის ოპერაცია. შემდეგ, თუ განტოლებებში არის რთული ლოგიკური ოპერაციები, ჩვენ მათ ვცვლით ძირითადით: "AND", "OR", "NOT". შემდეგი ნაბიჯი არის განტოლებების გაერთიანება ერთ, სისტემის ეკვივალენტად, ლოგიკური ოპერაციის "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, ხოლო მეორიდან - С=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) - შეესატყვისება საწყისი განტოლების პარამეტრების ცხრა შესაძლო კომბინაციას. მაშასადამე, არსებობს ამ განტოლების 3+9=15 შესაძლო ამონახსნები.

ლოგიკური განტოლებათა სისტემის ამონახსნების რაოდენობის დასადგენად შემდეგი გზაა − ბინარული ხე. განვიხილოთ ეს მეთოდი მაგალითით.

Დავალება:რამდენი განსხვავებული ამონახსნი აქვს ლოგიკურ განტოლებათა სისტემას:

განტოლებათა მოცემული სისტემა უდრის განტოლებას:

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

მოდი ვიჩვენოთ, რომ x 1 მართალია, მაშინ პირველი განტოლებიდან ვიღებთ ამას x 2 ასევე მართალია, მეორედან - x 3 =1 და ასე შემდეგ სანამ x მ= 1. ეს ნიშნავს, რომ m ერთეულების სიმრავლე (1; 1; …; 1) არის სისტემის ამოხსნა. მოდით ახლა 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
x2
x 3
		…

მსჯელობის სირთულეების შემთხვევაში ნიახ და სამშენებლო დეგადაწყვეტილებების ღრიალი, თქვენ შეგიძლიათ მოძებნოთ გამოსავალიგამოყენებით სიმართლის ცხრილები, ერთი ან ორი განტოლებისთვის.

ჩვენ ხელახლა ვწერთ განტოლებათა სისტემას სახით:

და მოდით გავაკეთოთ ჭეშმარიტების ცხრილი ცალკე ერთი განტოლებისთვის:

x 1	x2	(x 1 → x 2)

მოდით გავაკეთოთ ჭეშმარიტების ცხრილი ორი განტოლებისთვის:

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

გაკვეთილის თემა: ლოგიკური განტოლებების ამოხსნა

საგანმანათლებლო - ლოგიკური განტოლებების ამოხსნის გზების შესწავლა, ლოგიკური განტოლებების ამოხსნის უნარებისა და შესაძლებლობების ჩამოყალიბება და სიმართლის ცხრილის მიხედვით ლოგიკური გამონათქვამის აგება;

საგანმანათლებლო - შექმნას პირობები მოსწავლეთა შემეცნებითი ინტერესის განვითარებისათვის, ხელი შეუწყოს მეხსიერების, ყურადღების, ლოგიკური აზროვნების განვითარებას;

საგანმანათლებლო : წვლილი შეიტანოს სხვისი აზრის მოსმენის უნარის აღზრდაში,ნებისყოფისა და გამძლეობის განათლება საბოლოო შედეგების მისაღწევად.

გაკვეთილის ტიპი: კომბინირებული გაკვეთილი

აღჭურვილობა: კომპიუტერი, მულტიმედიური პროექტორი, პრეზენტაცია 6.

გაკვეთილების დროს

საბაზისო ცოდნის გამეორება და განახლება. საშინაო დავალების შემოწმება (10 წუთი)

წინა გაკვეთილებზე გავეცანით ლოგიკის ალგებრის ძირითად კანონებს, ვისწავლეთ როგორ გამოვიყენოთ ეს კანონები ლოგიკური გამონათქვამების გასამარტივებლად.

მოდით შევამოწმოთ საშინაო დავალება ლოგიკური გამონათქვამების გამარტივებაზე:

1. ჩამოთვლილი სიტყვებიდან რომელი აკმაყოფილებს ლოგიკურ პირობას:

(პირველი თანხმოვანი → მეორე თანხმოვანი)٨ (ბოლო ასო ხმოვანი → ბოლო ასო ხმოვანი)? თუ რამდენიმე ასეთი სიტყვაა, მიუთითეთ მათგან ყველაზე პატარა.

1) ანა 2) მარია 3) ოლეგი 4) სტეპანი

შემოვიღოთ აღნიშვნა:

A არის თანხმოვანის პირველი ასო

B არის თანხმოვანის მეორე ასო

S არის ბოლო ხმოვანი

D - ბოლო ხმოვანი

მოდით გამოვხატოთ:

მოდით გავაკეთოთ ცხრილი:

2. მიუთითეთ რომელი ლოგიკური გამოხატულებაა გამოთქმის ტოლფასი

მოდით გავამარტივოთ ორიგინალური გამოხატვის წერა და შემოთავაზებული ვარიანტები:

3. მოცემულია F გამოთქმის ჭეშმარიტების ცხრილის ფრაგმენტი:

რა გამოთქმა შეესაბამება F-ს?

მოდით განვსაზღვროთ ამ გამონათქვამების მნიშვნელობები არგუმენტების მითითებული მნიშვნელობებისთვის:

გაკვეთილის თემის გაცნობა, ახალი მასალის პრეზენტაცია (30 წუთი)

ვაგრძელებთ ლოგიკის საფუძვლების შესწავლას და ჩვენი დღევანდელი გაკვეთილის თემას „ლოგიკური განტოლებების ამოხსნა“. ამ თემის შესწავლის შემდეგ შეისწავლით ლოგიკური განტოლებების ამოხსნის ძირითად გზებს, მიიღებთ ამ განტოლებების ამოხსნის უნარებს ლოგიკური ალგებრის ენის გამოყენებით და სიმართლის ცხრილში ლოგიკური გამოხატვის შედგენის უნარს.

1. ამოხსენით ლოგიკური განტოლება

(¬K M) → (¬L მ N)=0

ჩაწერეთ თქვენი პასუხი ოთხი სიმბოლოს სტრიქონში: K, L, M და N ცვლადების მნიშვნელობები (ამ თანმიმდევრობით). ასე, მაგალითად, 1101 სტრიქონს შეესაბამება K=1, L=1, M=0, N=1.

გამოსავალი:

მოდით გარდაქმნას გამოხატულება(¬K  M) → (¬L  მ  ნ)

გამოთქმა მცდარია, როდესაც ორივე ტერმინი მცდარია. მეორე წევრი უდრის 0-ს, თუ M=0, N=0, L=1. პირველ ტერმინში K = 0, ვინაიდან M = 0 და
.

პასუხი: 0100

2. რამდენი ამონახსნი აქვს განტოლებას (პასუხში მიუთითეთ მხოლოდ რიცხვი)?

გამოსავალი: გამოთქმის გარდაქმნა

(A+B)*(C+D)=1

A+B=1 და C+D=1

მეთოდი 2: სიმართლის ცხრილის შედგენა

3 გზა: SDNF-ის კონსტრუქცია - სრულყოფილი დისიუნგციური ნორმალური ფორმა ფუნქციისთვის - სრული რეგულარული ელემენტარული კავშირების დისუნქცია.

გადავცვალოთ ორიგინალური გამონათქვამი, გავხსნათ ფრჩხილები, რათა მივიღოთ კავშირების დისუნქცია:

(A+B)*(C+D)=A*C+B*C+A*D+B*D=

შევავსოთ კავშირები სრულ კავშირებს (ყველა არგუმენტის პროდუქტი), გავხსნათ ფრჩხილები:

განვიხილოთ იგივე კავშირები:

შედეგად, ჩვენ ვიღებთ SDNF-ს, რომელიც შეიცავს 9 კავშირს. მაშასადამე, ამ ფუნქციის სიმართლის ცხრილს აქვს 1 მნიშვნელობა 9 მწკრივზე ცვლადის მნიშვნელობების 2 4 =16 კომპლექტიდან.

3. რამდენი ამონახსნი აქვს განტოლებას (პასუხში მიუთითეთ მხოლოდ რიცხვი)?

მოდით გავამარტივოთ გამოთქმა:

,

3 გზა: SDNF-ის მშენებლობა

განვიხილოთ იგივე კავშირები:

შედეგად, ჩვენ ვიღებთ SDNF-ს, რომელიც შეიცავს 5 კავშირს. მაშასადამე, ამ ფუნქციის სიმართლის ცხრილს აქვს 1 მნიშვნელობა 2 4 =16 ცვლადის მნიშვნელობების 5 მწკრივზე.

ლოგიკური გამოხატვის აგება სიმართლის ცხრილის მიხედვით:

სიმართლის ცხრილის თითოეული მწკრივისთვის, რომელიც შეიცავს 1-ს, ჩვენ ვადგენთ არგუმენტების ნამრავლს და 0-ის ტოლი ცვლადები ნამრავლში შედის უარყოფით, ხოლო 1-ის ტოლი ცვლადები არ არის უარყოფილი. სასურველი გამოხატულება F შედგება მიღებული პროდუქციის ჯამისაგან. შემდეგ, თუ შესაძლებელია, ეს გამოთქმა უნდა გამარტივდეს.

მაგალითი: მოცემულია გამოხატვის სიმართლის ცხრილი. შექმენით ლოგიკური გამოხატულება.

გამოსავალი:

3. საშინაო დავალება (5 წუთი)

ამოხსენით განტოლება:

რამდენი ამონახსნი აქვს განტოლებას (უპასუხეთ მხოლოდ რიცხვს)?

მოცემული სიმართლის ცხრილის მიხედვით გააკეთეთ ლოგიკური გამოთქმა და

გაამარტივებს მას.

ლოგიკური განტოლებათა სისტემების ამოხსნის გზები

კირგიზოვა ე.ვ., ნემკოვა ა.ე.

ლესოსიბირსკის პედაგოგიური ინსტიტუტი -

ციმბირის ფედერალური უნივერსიტეტის ფილიალი, რუსეთი

თანმიმდევრული აზროვნების, საბოლოო კამათის, ჰიპოთეზების აგების, უარყოფითი დასკვნების უარყოფის უნარი თავისთავად არ მოდის, ამ უნარს ავითარებს ლოგიკის მეცნიერება. ლოგიკა არის მეცნიერება, რომელიც სწავლობს ზოგიერთი განცხადების სიმართლის ან სიცრუის დადგენის მეთოდებს სხვა განცხადებების ჭეშმარიტების ან მცდარი საფუძველზე.

ამ მეცნიერების საფუძვლების დაუფლება შეუძლებელია ლოგიკური პრობლემების გადაჭრის გარეშე. მათი ცოდნის ახალ სიტუაციაში გამოყენების უნარების ჩამოყალიბების შემოწმება ხდება ჩაბარებით. კერძოდ, ეს არის ლოგიკური პრობლემების გადაჭრის უნარი. გამოცდაში B15 ამოცანები გაზრდილი სირთულის ამოცანებია, რადგან ისინი შეიცავს ლოგიკური განტოლებების სისტემებს. ლოგიკური განტოლებების სისტემების ამოხსნის სხვადასხვა გზა არსებობს. ეს არის ერთ განტოლებამდე შემცირება, სიმართლის ცხრილის აგება, დაშლა, განტოლებების თანმიმდევრული ამოხსნა და ა.შ.

Დავალება:ამოხსენით ლოგიკური განტოლებათა სისტემა:

განიხილეთ ერთ განტოლებამდე შემცირების მეთოდი . ეს მეთოდი გულისხმობს ლოგიკური განტოლებების ტრანსფორმაციას ისე, რომ მათი მარჯვენა მხარეები ტოლი იყოს ჭეშმარიტების მნიშვნელობის (ანუ 1). ამისათვის გამოიყენეთ ლოგიკური უარყოფის ოპერაცია. შემდეგ, თუ განტოლებებში არის რთული ლოგიკური ოპერაციები, ჩვენ მათ ვცვლით ძირითადით: "AND", "OR", "NOT". შემდეგი ნაბიჯი არის განტოლებების გაერთიანება ერთ, სისტემის ეკვივალენტად, ლოგიკური ოპერაციის "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, შემდეგ:

პირველი განტოლებიდან ვიღებთბ =0, ხოლო მეორედან - С=1. სისტემის ამოხსნა: A = 0 , B = 0 და C = 1 .

თქვენ ასევე შეგიძლიათ გამოიყენოთ მეთოდი განტოლებების თანმიმდევრული ამოხსნა , თითოეულ საფეხურზე განსახილველ ნაკრებს ერთი ცვლადის დამატება. ამისათვის აუცილებელია განტოლებების ისე გარდაქმნა, რომ ცვლადები შეყვანილი იყოს ანბანური თანმიმდევრობით. შემდეგი, ჩვენ ვაშენებთ გადაწყვეტილების ხეს, თანმიმდევრულად ვამატებთ მას ცვლადებს.

სისტემის პირველი განტოლება დამოკიდებულია მხოლოდ A-ზე და B-ზე, ხოლო მეორე განტოლება A-ზე და C-ზე. ცვლად A-ს შეუძლია მიიღოს 2 მნიშვნელობა 0 და 1:

პირველი განტოლებიდან გამომდინარეობს, რომ მაშ, როდის A = 0 ვიღებთ B = 0 , ხოლო A = 1 -სთვის გვაქვს B = 1 . ასე რომ, პირველ განტოლებას აქვს ორი ამონახსნი A და B ცვლადებთან მიმართებაში.

ჩვენ ვხატავთ მეორე განტოლებას, საიდანაც ვადგენთ C-ის მნიშვნელობებს თითოეული ვარიანტისთვის. A =1-სთვის მნიშვნელობა არ შეიძლება იყოს მცდარი, ანუ ხის მეორე ტოტს გამოსავალი არ აქვს. ზე A= 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) - შეესატყვისება საწყისი განტოლების პარამეტრების ცხრა შესაძლო კომბინაციას. მაშასადამე, არსებობს ამ განტოლების 3+9=15 შესაძლო ამონახსნები.

ლოგიკური განტოლებათა სისტემის ამონახსნების რაოდენობის დასადგენად შემდეგი გზაა − ბინარული ხე. განვიხილოთ ეს მეთოდი მაგალითით.

Დავალება:რამდენი განსხვავებული ამონახსნი აქვს ლოგიკურ განტოლებათა სისტემას:

განტოლებათა მოცემული სისტემა უდრის განტოლებას:

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

მოდი ვიჩვენოთ, რომx 1 მართალია, მაშინ პირველი განტოლებიდან ვიღებთ ამასx 2 ასევე მართალია, მეორედან -x 3 =1 და ასე შემდეგ სანამ x მ= 1. აქედან გამომდინარეობს ნაკრები (1; 1; …; 1)-დანმ ერთეული არის სისტემის გამოსავალი. მოდით ახლაx 1 =0, მაშინ პირველი განტოლებიდან გვაქვსx 2 =0 ან x 2 =1.

Როდესაც x 2 true, მივიღებთ, რომ სხვა ცვლადებიც ჭეშმარიტია, ანუ სიმრავლე (0; 1; ...; 1) არის სისტემის ამონახსნი. ზეx 2 =0 ჩვენ ამას მივიღებთ x 3 =0 ან x 3 = და ასე შემდეგ. გავაგრძელოთ ბოლო ცვლადი, ჩვენ აღმოვაჩენთ, რომ განტოლების ამონახსნები არის ცვლადების შემდეგი ნაკრები (მ +1 ხსნარი, თითოეულ ხსნარშიმ ცვლადი მნიშვნელობები):

(1; 1; 1; …; 1)

(0; 1; 1; …; 1)

(0; 0; 0; …; 0)

ეს მიდგომა კარგად არის ილუსტრირებული ბინარული ხის აგებით. შესაძლო გადაწყვეტილებების რაოდენობა არის აგებული ხის სხვადასხვა ტოტების რაოდენობა. ადვილი მისახვედრია, რომ ასეა m+1.

ცვლადები	Ტყე	გადაწყვეტილებების რაოდენობა
x 1
x2
x 3

მსჯელობისა და გადაწყვეტილების ხის აგების სირთულეების შემთხვევაში, შეგიძლიათ მოძებნოთ გამოსავალი გამოყენებით სიმართლის ცხრილები, ერთი ან ორი განტოლებისთვის.

ჩვენ ხელახლა ვწერთ განტოლებათა სისტემას სახით:

და მოდით გავაკეთოთ ჭეშმარიტების ცხრილი ცალკე ერთი განტოლებისთვის:

x 1	x2	(x 1 → x 2)

მოდით გავაკეთოთ ჭეშმარიტების ცხრილი ორი განტოლებისთვის:

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

შემდეგი, თქვენ ხედავთ, რომ ერთი განტოლება მართალია შემდეგ სამ შემთხვევაში: (0; 0), (0; 1), (1; 1). ორი განტოლების სისტემა მართებულია ოთხ შემთხვევაში (0; 0; 0), (0; 0; 1), (0; 1; 1), (1; 1; 1). ამ შემთხვევაში, მაშინვე ნათელია, რომ არსებობს გამოსავალი, რომელიც შედგება მხოლოდ ნულებისაგან და მეტისგან მგადაწყვეტილებები, რომლებშიც ემატება ერთი ერთეული, ბოლო პოზიციიდან დაწყებული ყველა შესაძლო ადგილის შევსებამდე. შეიძლება ვივარაუდოთ, რომ ზოგად ამოხსნას ექნება იგივე ფორმა, მაგრამ იმისთვის, რომ ასეთი მიდგომა გადაწყვეტად იქცეს, საჭიროა მტკიცებულება, რომ ვარაუდი ჭეშმარიტია.

ყოველივე ზემოთქმულის შეჯამებით, მინდა გავამახვილო ყურადღება იმ ფაქტზე, რომ ყველა განხილული მეთოდი არ არის უნივერსალური. ლოგიკური განტოლებების თითოეული სისტემის ამოხსნისას მხედველობაში უნდა იქნას მიღებული მისი მახასიათებლები, რის საფუძველზეც უნდა შეირჩეს ამოხსნის მეთოდი.

ლიტერატურა:

1. ლოგიკური ამოცანები / O.B. ბოგომოლოვი - მე-2 გამოცემა. – M.: BINOM. ცოდნის ლაბორატორია, 2006. - 271გვ.: ილ.

2. პოლიაკოვი კ.იუ. ლოგიკური განტოლებათა სისტემები / საგანმანათლებლო და მეთოდური გაზეთი კომპიუტერული მეცნიერების მასწავლებლებისთვის: ინფორმატიკა No14, 2011 წ.

ლოგიკური განტოლებათა სისტემების ამოხსნის მეთოდები

თქვენ შეგიძლიათ ამოხსნათ ლოგიკური განტოლებათა სისტემა, მაგალითად, სიმართლის ცხრილის გამოყენებით (თუ ცვლადების რაოდენობა არ არის ძალიან დიდი) ან გადაწყვეტილების ხის გამოყენებით, თითოეული განტოლების გამარტივების შემდეგ.

1. ცვლადების ცვლილების მეთოდი.

ახალი ცვლადების დანერგვა შესაძლებელს ხდის განტოლებათა სისტემის გამარტივებას უცნობის რაოდენობის შემცირებით.ახალი ცვლადები ერთმანეთისგან დამოუკიდებელი უნდა იყოს. გამარტივებული სისტემის ამოხსნის შემდეგ საჭიროა ისევ თავდაპირველ ცვლადებზე დაბრუნება.

განვიხილოთ ამ მეთოდის გამოყენება კონკრეტულ მაგალითზე.

მაგალითი.

((X1 ≡ X2) ∧ (X3 ≡ X4)) ∨ (¬(X1 ≡ X2) ∧ ¬(X3 ≡ X4)) = 0

((X3 ≡ X4) ∧ (X5 ≡ X6)) ∨ (¬(X3 ≡ X4) ∧ ¬(X5 ≡ X6)) = 0

((X5 ≡ X6) ∧ (X7 ≡ X8)) ∨ (¬(X5 ≡ X6) ∧ ¬(X7 ≡ X8)) = 0

((X7 ≡ X8) ∧ (X9 ≡ X10)) ∨ (¬(X7 ≡ X8) ∧ ¬(X9 ≡ X10)) = 0

გამოსავალი:

შემოვიტანოთ ახალი ცვლადები: А=(X1≡X2); B=(X3 ≡ X4); С=(X5 ≡ X6); D=(X7 ≡ X8); E=(X9 ≡ X10).

(ყურადღება! მათი თითოეული ცვლადი x1, x2, ..., x10 უნდა იყოს შეტანილი მხოლოდ ერთ ახალ ცვლადში A, B, C, D, E, ანუ ახალი ცვლადები ერთმანეთისგან დამოუკიდებელია).

მაშინ განტოლებათა სისტემა ასე გამოიყურება:

(A ∧ B) ∨ (¬A ∧ ¬B)=0

(B ∧ C) ∨ (¬B ∧ ¬C)=0

(C ∧ D) ∨ (¬C ∧ ¬D)=0

(D ∧ E) ∨ (¬D ∧ ¬E)=0

მოდით ავაშენოთ მიღებული სისტემის გადაწყვეტილების ხე:

განვიხილოთ განტოლება A=0, ე.ი. (X1≡ X2)=0. მას აქვს 2 ფესვი:

		X1 ≡ X2

იმავე ცხრილიდან ჩანს, რომ განტოლებას A \u003d 1 ასევე აქვს 2 ფესვი. მოდით მოვაწყოთ ფესვების რაოდენობა გადაწყვეტილების ხეზე:

ერთი ფილიალისთვის გადაწყვეტილებების რაოდენობის მოსაძებნად, თქვენ უნდა გაამრავლოთ ამონახსნების რაოდენობა თითოეულ დონეზე. მარცხენა ტოტს აქვს 2⋅ 2 ⋅ 2 ⋅ 2 ⋅ 2=32 ხსნარი; მარჯვენა ფილიალს ასევე აქვს 32 გამოსავალი. იმათ. მთელ სისტემას აქვს 32+32=64 ამონახსნი.

პასუხი: 64.

2. მსჯელობის მეთოდი.

ლოგიკური განტოლებების სისტემების ამოხსნის სირთულე მდგომარეობს გადაწყვეტილების სრული ხის სიდიდეში. მსჯელობის მეთოდი საშუალებას გაძლევთ მთლიანად არ ააგოთ მთელი ხე, მაგრამ ამავე დროს გაიგოთ რამდენი ტოტი ექნება მას. მოდით განვიხილოთ ეს მეთოდი კონკრეტულ მაგალითებზე.

მაგალითი 1 ლოგიკური ცვლადების მნიშვნელობების რამდენი განსხვავებული კომპლექტია x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, რომლებიც აკმაყოფილებს ყველა ქვემოთ მოცემულ პირობას?

(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1

(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1

x1\/y1 =1

პასუხს არ სჭირდება x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 ცვლადების მნიშვნელობების ყველა სხვადასხვა ნაკრების ჩამოთვლა, რომლის მიხედვითაც დაკმაყოფილებულია ტოლობების მოცემული სისტემა. პასუხად, თქვენ უნდა მიუთითოთ ასეთი კომპლექტების რაოდენობა.

გამოსავალი:

პირველი და მეორე განტოლებები შეიცავს დამოუკიდებელ ცვლადებს, რომლებიც დაკავშირებულია მესამე პირობით. მოდით ავაშენოთ გადაწყვეტილების ხე პირველი და მეორე განტოლებისთვის.

სისტემის გადაწყვეტილების ხის წარმოსადგენად პირველი და მეორე განტოლებიდან, აუცილებელია პირველი ხის თითოეული ტოტი გავაგრძელოთ ცვლადების ხის საშუალებით.ზე . ამ გზით აშენებული ხე 36 ტოტს შეიცავს. ზოგიერთი ეს განშტოება არ აკმაყოფილებს სისტემის მესამე განტოლებას. პირველ ხეზე შენიშნეთ ხის ტოტების რაოდენობა"ზე" , რომელიც აკმაყოფილებს მესამე განტოლებას:

განვმარტოთ: x1=0-ზე მესამე პირობის შესასრულებლად უნდა იყოს y1=1, ანუ ხის ყველა ტოტი."X" , სადაც x1=0 შეიძლება გაგრძელდეს ხიდან მხოლოდ ერთი ტოტით"ზე" . და მხოლოდ ხის ერთი ტოტისთვის"X" (მარჯვნივ) ერგება ხის ყველა ტოტს"ზე". ამრიგად, მთელი სისტემის სრული ხე შეიცავს 11 ტოტს. თითოეული ტოტი წარმოადგენს განტოლებათა თავდაპირველი სისტემის ერთ ამოხსნას. ასე რომ, მთელ სისტემას აქვს 11 გამოსავალი.

პასუხი: 11.

მაგალითი 2 რამდენი განსხვავებული ამონახსნები აქვს განტოლებათა სისტემას

(X1 ≡ X2) ∨ (X1 ∧ X10) ∨ (¬X1 ∧ ¬X10)= 1

(X2 ≡ X3) ∨ (X2 ∧ X10) ∨ (¬X2 ∧ ¬X10)= 1.

………………

(X9 ≡ X10) ∨ (X9 ∧ X10) ∨ (¬X9 ∧ ¬X10)= 1

(X1 ≡ X10) = 0

სადაც x1, x2, ..., x10 არის ლოგიკური ცვლადები? პასუხს არ სჭირდება ცვლადის მნიშვნელობების ყველა სხვადასხვა ნაკრების ჩამოთვლა, რომლებისთვისაც ეს თანასწორობაა. პასუხად, თქვენ უნდა მიუთითოთ ასეთი კომპლექტების რაოდენობა.

გამოსავალი: მოდით გავამარტივოთ სისტემა. მოდით ავაშენოთ პირველი განტოლების ნაწილის ჭეშმარიტების ცხრილი:

		X1 ∧ X10	¬X1 ∧ ¬X10	(X1 ∧ X10) ∨ (¬X1 ∧ ¬X10)

ყურადღება მიაქციეთ ბოლო სვეტს, ის ემთხვევა მოქმედების შედეგს X1 ≡ X10.

X1 ≡ X10

გამარტივების შემდეგ ვიღებთ:

(X1 ≡ X2) ∨ (X1 ≡ X10)=1

(X2 ≡ X3) ∨ (X2 ≡ X10)=1

(X3 ≡ X4) ∨ (X3 ≡ X10)=1

……

(X9 ≡ X10) ∨ (X9 ≡ X10)=1

(X1 ≡ X10) = 0

განვიხილოთ ბოლო განტოლება:(X1 ≡ X10) = 0, ე.ი. x1 არ უნდა იყოს იგივე, რაც x10. იმისათვის, რომ პირველი განტოლება იყოს 1-ის ტოლი, ტოლობა უნდა იყოს(X1 ≡ X2)=1, ე.ი. x1 უნდა ემთხვეოდეს x2-ს.

მოდით ავაშენოთ გადაწყვეტილების ხე პირველი განტოლებისთვის:

განვიხილოთ მეორე განტოლება: x10=1-ისთვის და x2=0-ისთვის ფრჩხილიუნდა იყოს 1-ის ტოლი (ანუ x2 იგივეა, რაც x3); x10=0-ზე და x2=1 ფრჩხილზე(X2 ≡ X10)=0, ამიტომ ფრჩხილები (X2 ≡ X3) უნდა იყოს 1-ის ტოლი (ანუ x2 იგივეა რაც x3):

ამ გზით კამათით, ჩვენ ვაშენებთ გადაწყვეტილების ხეს ყველა განტოლებისთვის:

ამრიგად, განტოლებათა სისტემას აქვს მხოლოდ 2 ამონახსნი.

პასუხი: 2.

მაგალითი 3

ლოგიკური ცვლადების მნიშვნელობების რამდენი განსხვავებული კომპლექტია x1, x2, x3, x4, y1, y2, y3, y4, z1, z2, z3, z4, რომლებიც აკმაყოფილებს ყველა შემდეგ პირობას?

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

(¬x1 /\ y1 /\ z1) \/ (x1 /\ ¬y1 /\ z1) \/ (x1 /\ y1 /\ ¬z1) = 1

(¬x2 /\ y2 /\ z2) \/ (x2 /\ ¬y2 /\ z2) \/ (x2 /\ y2 /\ ¬z2) = 1

(¬x3 /\ y3 /\ z3) \/ (x3 /\ ¬y3 /\ z3) \/ (x3 /\ y3 /\ ¬z3) = 1

(¬x4 /\ y4 /\ z4) \/ (x4 /\ ¬y4 /\ z4) \/ (x4 /\ y4 /\ ¬z4) = 1

გამოსავალი:

მოდით ავაშენოთ პირველი განტოლების გადაწყვეტილების ხე:

განვიხილოთ მეორე განტოლება:

• როცა x1=0 : მეორე და მესამე ფრჩხილები იქნება 0; პირველი ფრჩხილი რომ იყოს 1-ის ტოლი, უნდა y1=1 , z1=1 (ანუ ამ შემთხვევაში - 1 ამონახსნი)
• x1=1-ით : პირველი ფრჩხილები იქნება 0; მეორეან მესამე ფრჩხილი უნდა იყოს 1-ის ტოლი; მეორე ფრჩხილი 1-ის ტოლი იქნება, როცა y1=0 და z1=1; მესამე ფრჩხილი იქნება 1-ის ტოლი y1=1-ისთვის და z1=0 (ანუ ამ შემთხვევაში - 2 ამონახსნები).

ანალოგიურად დანარჩენი განტოლებისთვის. გაითვალისწინეთ ხის თითოეული კვანძისთვის მიღებული გადაწყვეტილებების რაოდენობა:

თითოეული ტოტის ამონახსნების რაოდენობის გასარკვევად, მიღებულ რიცხვებს ვამრავლებთ თითოეულ ტოტზე ცალ-ცალკე (მარცხნიდან მარჯვნივ).

1 ტოტი: 1 ⋅ 1 ⋅ 1 ⋅ 1 = 1 ხსნარი

2 ტოტი: 1 ⋅ 1 ⋅ 1 ⋅ 2 = 2 ხსნარი

მე-3 ტოტი: 1 ⋅ 1 ⋅ 2 ⋅ 2 = 4 ხსნარი

4 ტოტი: 1 ⋅ 2 ⋅ 2 ⋅ 2 = 8 ხსნარი

5 ტოტი: 2 ⋅ 2 ⋅ 2 ⋅ 2=16 ხსნარი

დავამატოთ მიღებული რიცხვები: სულ 31 ამონახსნი.

პასუხი: 31.

3. ფესვების რაოდენობის რეგულარული ზრდა

ზოგიერთ სისტემაში შემდეგი განტოლების ფესვების რაოდენობა დამოკიდებულია წინა განტოლების ფესვების რაოდენობაზე.

მაგალითი 1 ლოგიკური ცვლადების მნიშვნელობების რამდენი განსხვავებული კომპლექტია x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, რომლებიც აკმაყოფილებს ყველა ქვემოთ მოცემულ პირობას?

¬(x1 ≡ x2) ∧ ((x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)) = 0

¬(x2 ≡ x3) ∧ ((x2 ∧ ¬x4) ∨ (¬x2 ∧ x4)) = 0

¬(x8 ≡ x9) ∧ ((x8 ∧ ¬x10) ∨ (¬x8 ∧ x10)) = 0

გამარტივება პირველი განტოლება:(x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)=x1 ⊕ x3=¬(x1 ≡ x3). შემდეგ სისტემა მიიღებს ფორმას:

¬(x1 ≡ x2) ∧ ¬(x1 ≡ x3) = 0

¬(x2 ≡ x3) ∧ ¬(x2 ≡ x4)= 0

¬(x8 ≡ x9) ∧ ¬(x8 ≡ x10) = 0

და ა.შ.

თითოეულ შემდეგ განტოლებას აქვს 2 ძირი მეტი ვიდრე წინა.

4 განტოლებას აქვს 12 ფესვი;

მე-5 განტოლებას აქვს 14 ფესვი

8 განტოლებას აქვს 20 ფესვი.

პასუხი: 20 ძირი.

ზოგჯერ ფესვების რაოდენობა იზრდება ფიბონაჩის რიცხვების კანონის მიხედვით.

ლოგიკური განტოლებათა სისტემის ამოხსნა შემოქმედებით მიდგომას მოითხოვს.