სიმართლის ცხრილი არის ცხრილი, რომელიც აღწერს ლოგიკურ ფუნქციას. ლოგიკური ფუნქცია აქ არის ფუნქცია, რომელშიც ცვლადების მნიშვნელობები და თავად ფუნქციის მნიშვნელობა გამოხატავს სიმართლეს. მაგალითად, ისინი იღებენ მნიშვნელობებს "true" ან "false" (true ან false, 1 ან 0).

სიმართლის ცხრილები გამოიყენება განცხადების მნიშვნელობის დასადგენად იმ განცხადებების სიმართლის მნიშვნელობების ყველა შესაძლო შემთხვევისთვის, რომლებიც მას ქმნიან. ცხრილის ყველა არსებული კომბინაციის რაოდენობა გვხვდება N=2*n ფორმულით; სადაც N არის შესაძლო კომბინაციების საერთო რაოდენობა, n არის შეყვანის ცვლადების რაოდენობა. სიმართლის ცხრილები ხშირად გამოიყენება ციფრულ ინჟინერიაში და ლოგიკური ალგებრაში ლოგიკური სქემების მუშაობის აღსაწერად.

სიმართლის ცხრილები ძირითადი ფუნქციებისთვის

მაგალითები: კავშირი - 1&0=0, მინიშნება - 1→0=0.

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

ინვერსია; შეერთება; დისჯუნქცია; იმპლიკაცია; ეკვივალენტობა; შეფერის ინსულტი; პირსის ისარი.

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

1. ლოგიკურ გამოსახულებაში გამოყენებული ცვლადების N რიცხვის განსაზღვრა.
2. გამოთვალეთ ცვლადი მნიშვნელობების შესაძლო კომპლექტების რაოდენობა M = 2 N, ცხრილის რიგების რაოდენობის ტოლი.
3. დაითვალეთ ლოგიკური მოქმედებების რაოდენობა ლოგიკურ გამოსახულებაში და განსაზღვრეთ ცხრილის სვეტების რაოდენობა, რომელიც უდრის ცვლადების რაოდენობას პლუს ლოგიკური ოპერაციების რაოდენობა.
4. დაასახელეთ ცხრილის სვეტები ცვლადების სახელებით და ლოგიკური ოპერაციების სახელებით.
5. შეავსეთ ლოგიკური ცვლადის სვეტები მნიშვნელობების სიმრავლით, მაგალითად, 0000-დან 1111-მდე 0001-ის მატებით ოთხი ცვლადის შემთხვევაში.
6. შეავსეთ სიმართლის ცხრილი სვეტების მიხედვით შუალედური ოპერაციების მნიშვნელობებით მარცხნიდან მარჯვნივ.
7. შეავსეთ საბოლოო მნიშვნელობის სვეტი F ფუნქციისთვის.

ამრიგად, თქვენ თავად შეგიძლიათ შეადგინოთ (აშენოთ) სიმართლის ცხრილი.

შექმენით სიმართლის ცხრილი ონლაინ

შეავსეთ შეყვანის ველი და დააჭირეთ OK. T - მართალია, F - მცდარი. ჩვენ გირჩევთ მონიშნოთ გვერდი ან შეინახოთ იგი სოციალურ ქსელში.

აღნიშვნები

1. სიმრავლეები ან გამოთქმები ლათინური ანბანის დიდი ასოებით: A, B, C, D...
2. ა" - პირველი - კომპლექტების დანამატები
3. && - კავშირი ("და")
4. || - დისიუნქცია ("ან")
5. ! - უარყოფა (მაგალითად, !A)
6. \cap - კომპლექტების გადაკვეთა \cap
7. \ჭიქა - კომპლექტების გაერთიანება (დამატება) \ჭიქა
8. A&!B - კომპლექტი განსხვავება A∖B=A-B
9. A=>B - მინიშნება "თუ... მაშინ"
10. AB - ეკვივალენტობა

ციფრულ წრეებში ციფრული სიგნალი არის სიგნალი, რომელსაც შეუძლია მიიღოს ორი მნიშვნელობა, განიხილება როგორც ლოგიკური "1" და ლოგიკური "0".

ლოგიკური სქემები ხორციელდება ლოგიკური ელემენტების გამოყენებით: "NOT", "AND", "OR", "NAND", "NOR", "XOR" და "Equivalence". პირველი სამი ლოგიკური ელემენტი საშუალებას გაძლევთ განახორციელოთ ნებისმიერი, რაოდენ რთულიც არ უნდა იყოს ლოგიკური ფუნქცია ლოგიკურ საფუძველზე. ჩვენ მოვაგვარებთ ამოცანებს ლოგიკურ სქემებზე, რომლებიც განხორციელებულია ზუსტად ლოგიკურ საფუძველზე.

ლოგიკური ელემენტების აღსანიშნავად გამოიყენება რამდენიმე სტანდარტი. ყველაზე გავრცელებულია ამერიკული (ANSI), ევროპული (DIN), საერთაშორისო (IEC) და რუსული (GOST). ქვემოთ მოყვანილი ფიგურა გვიჩვენებს ლოგიკური ელემენტების აღნიშვნას ამ სტანდარტებში (გასადიდებლად, შეგიძლიათ დააჭიროთ ფიგურას მაუსის მარცხენა ღილაკით).

ამ გაკვეთილზე ჩვენ მოვაგვარებთ პრობლემებს ლოგიკურ სქემებზე, რომლებშიც ლოგიკური ელემენტები მითითებულია GOST სტანდარტში.

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

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

• სამი ცვლადი (განხილული იქნება საანალიზო ამოცანებში და ერთ სინთეზურ პრობლემაში);
• ოთხი ცვლადი (სინთეზის ამოცანებში, ანუ ბოლო ორ აბზაცში).

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

• ლოგიკურ საფუძველზე "AND", "OR", "NOT" (წინაბოლო აბზაცში);
• ასევე გავრცელებულ ფუძეებში „AND-NOT“ და „OR-NOT“ (ბოლო აბზაცში).

ლოგიკური წრედის ანალიზის პრობლემა

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

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

მაგალითი 1.

გამოსავალი. ლოგიკურ წრეს ვყოფთ იარუსებად, რაც უკვე ნაჩვენებია ფიგურაში. მოდით ჩამოვწეროთ ყველა ფუნქცია, დაწყებული 1-ლი დონიდან:

x, წ, ზ :

x	წ	ზ					ვ
1	1	1	0	1	1	1	1
1	1	0	0	0	0	1	0
1	0	1	0	0	0	1	0
1	0	0	0	0	0	1	0
0	1	1	0	0	0	1	0
0	1	0	0	0	0	1	0
0	0	1	0	0	0	1	0
0	0	0	1	0	1	0	0

მაგალითი 2.იპოვეთ ლოგიკური წრედის ლოგიკური ფუნქცია და ააგეთ ლოგიკური წრედის სიმართლის ცხრილი.

მაგალითი 3.იპოვეთ ლოგიკური წრედის ლოგიკური ფუნქცია და ააგეთ ლოგიკური წრედის სიმართლის ცხრილი.

ჩვენ ერთად ვაგრძელებთ ლოგიკური წრედის ლოგიკური ფუნქციის ძიებას

მაგალითი 4.იპოვეთ ლოგიკური წრედის ლოგიკური ფუნქცია და ააგეთ ლოგიკური წრედის სიმართლის ცხრილი.

გამოსავალი. ჩვენ ვყოფთ ლოგიკურ დიაგრამას იარუსებად. მოდით ჩამოვწეროთ ყველა ფუნქცია, დაწყებული 1-ლი დონიდან:

ახლა მოდით ჩავწეროთ ყველა ფუნქცია შეყვანის ცვლადების ჩანაცვლებით x, წ, ზ :

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

.

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

x	წ	ზ			ვ
1	1	1	0	1	1
1	1	0	0	1	1
1	0	1	1	0	1
1	0	0	0	0	0
0	1	1	0	1	1
0	1	0	0	1	1
0	0	1	0	1	1
0	0	0	0	1	1

მაგალითი 5.იპოვეთ ლოგიკური წრედის ლოგიკური ფუნქცია და ააგეთ ლოგიკური წრედის სიმართლის ცხრილი.

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

ახლა მოდით ჩავწეროთ ყველა ფუნქცია შეყვანის ცვლადების ჩანაცვლებით x, წ, ზ :

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

.

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

x	წ	ზ			ვ
1	1	1	1	1	1
1	1	0	1	1	1
1	0	1	1	0	1
1	0	0	1	0	1
0	1	1	1	1	1
0	1	0	1	1	1
0	0	1	1	0	1
0	0	0	1	0	1

ლოგიკური სქემების სინთეზირების პრობლემა ლოგიკურ საფუძველზე

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

ყოველი დისუნქცია (ლოგიკური ჯამი) შეესაბამება „OR“ ელემენტს, რომლის შეყვანის რაოდენობა განისაზღვრება ცვლადების რაოდენობით დისუნქციაში. თითოეული კავშირი (ლოგიკური პროდუქტი) შეესაბამება "AND" ელემენტს, რომლის შეყვანის რაოდენობა განისაზღვრება კავშირის ცვლადების რაოდენობით. ყოველი უარყოფა (ინვერსია) შეესაბამება "NOT" ელემენტს.

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

მაგალითი 6.შექმენით ლოგიკური წრე, რომელიც ახორციელებს ფუნქციას მოცემული სიმართლის ცხრილით:

x	წ	ვ
1	1	0
1	0	0
0	1	1
0	0	0

გამოსავალი. გავაანალიზოთ სიმართლის ცხრილი ლოგიკური სქემისთვის. ჩვენ განვსაზღვრავთ ფუნქციას, რომელიც მიიღება მიკროსქემის გამოსავალზე და შუალედური ფუნქციები, რომლებიც არგუმენტებს იღებენ შეყვანად. xდა წ. პირველ რიგში, გამომავალი ფუნქციის განხორციელების შედეგი, იმის გათვალისწინებით, რომ შეყვანის ცვლადების მნიშვნელობები ტოლია, უნდა იყოს ლოგიკური "0", მეორე სტრიქონში - შეყვანის ცვლადების სხვადასხვა მნიშვნელობებით. , გამომავალი ასევე უნდა იყოს ლოგიკური "0". აქედან გამომდინარე, აუცილებელია, რომ გამომავალი ფუნქცია იყოს კავშირი (ლოგიკური პროდუქტი).

გამოხატვისას. n ლოგიკური ცვლადისთვის დაგჭირდებათ ცხრილის 2^n რიგები სიმართლესათაურის ხაზს არ ჩავთვლით. შემდეგ დაითვალეთ ლოგიკური ოპერაციების რაოდენობა გამოსახულებაში. ცხრილში იქნება იგივე რაოდენობის სვეტები, ოპერაციები პლუს n სვეტი ცვლადებისთვის.
მიეცით სამი გამოხატულება, რომელიც დაწერილია ფიგურაში. არსებობს სამი ცვლადი, ამიტომ საჭიროა 8 სტრიქონი მაგიდადა შეავსეთ მისი სათაური.

ახლა შეავსეთ ცვლადების ეტიკეტირებული სვეტები ცვლადების ყველა შესაძლო ვარიაციით. იმისათვის, რომ არ გამოტოვოთ ერთი ვარიანტი, მოსახერხებელია წარმოიდგინოთ ნულების და ერთეულების ეს თანმიმდევრობა 0-დან 2^n-მდე სახით. სამი ცვლადისთვის ეს არის ორობითი რიცხვები 0-დან 8-მდე, ან 000-დან 111-მდე ბინარში.

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

ვიდეო თემაზე

წყაროები:

• სიმართლის ცხრილები

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

ინსტრუქციები

მაგიდა სიმართლეკომპლექსისთვის იგი აგებულია შემდეგი ალგორითმის მიხედვით:
1. რაოდენობა განისაზღვრება ფორმულით
ხაზების რაოდენობა = 2^n + ხაზი სათაურისთვის, სადაც n არის მარტივი განცხადებების რაოდენობა,
2. სვეტების რაოდენობა განისაზღვრება ფორმულით
სვეტების რაოდენობა = ცვლადების რაოდენობა + ლოგიკური ოპერაციების რაოდენობა,
3. მშენებარე და

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

ლოგიკური ცვლადები შეისწავლება მათემატიკის სპეციალურ დარგში, რომელსაც ლოგიკის ალგებრა (წინადადებები) ან ლოგიკური ალგებრა ეწოდება. ბულის ალგებრას სახელი ეწოდა ინგლისელი მათემატიკოსის ჯორჯ ბულის (1815–1864) პატივსაცემად, რომელმაც მნიშვნელოვანი წვლილი შეიტანა ლოგიკის ალგებრის განვითარებაში. ლოგიკის ალგებრის შესწავლის საგანია დებულებები და გაანალიზებულია განცხადებების ჭეშმარიტება ან მცდარი და არა მათი სემანტიკური შინაარსი. ლოგიკურ ალგებრაში მარტივი განცხადებები აღინიშნება დიდი ლათინური ასოებით: A, B, C, D,... და ა.შ ნატურალურ ენაში რთული დებულებები იქმნება კავშირების გამოყენებით. ლოგიკის ალგებრაში ეს გაერთიანებები ჩანაცვლებულია ლოგიკური ოპერაციებით. ლოგიკის ალგებრის მიხედვით, ნებისმიერი რთული დებულება შეიძლება ჩაითვალოს ლოგიკურ ფუნქციად F(A, B, C,...), რომლის არგუმენტები არის ლოგიკური ცვლადები A, B, C...(მარტივი განცხადებები). ლოგიკური ფუნქციები და ლოგიკური ცვლადები (არგუმენტები) იღებენ მხოლოდ ორ მნიშვნელობას: "true", რომელიც აღინიშნება ლოგიკური ერთით - 1 და "false", რომელიც აღინიშნება ლოგიკური ნულით - 0. ლოგიკურ ფუნქციას ასევე უწოდებენ პრედიკატს.

ლოგიკურ ცვლადებზე შესრულებულ მოქმედებებს გარკვეული ლოგიკური ფუნქციების მისაღებად ეწოდება ლოგიკური ოპერაციები. ლოგიკის ალგებრაში გამოიყენება შემდეგი ლოგიკური ოპერაციები.

1. ლოგიკური ოპერაცია INVERSION (უარყოფა). ბუნებრივ ენებში შეესაბამება სიტყვებს ცრუ, ტყუილიან ნაწილაკი არა, არალოგიკის ალგებრაში აღინიშნება

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

ამ ოპერაციის მათემატიკური აღნიშვნა ლოგიკური ცვლადისთვის აასე გამოიყურება:

2. ლოგიკური ოპერაცია CONJUNCTION (ლოგიკური გამრავლება). ბუნებრივ ენებში შეესაბამება კავშირს და,პროგრამირების ენებში აღინიშნება დალოგიკურ ალგებრაში აღინიშნება &.

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

დ B, C,... ასე გამოიყურება:

F = A & B & C & ...

3. ლოგიკური ოპერაცია DISJUNCTION (ლოგიკური დამატება). ბუნებრივ ენებში შეესაბამება კავშირს ან,პროგრამირების ენებში აღინიშნება ან,ლოგიკის ალგებრაში აღინიშნება ვ.

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

ამ ოპერაციის მათემატიკური აღნიშვნა ლოგიკური ცვლადებისთვის A, B, C,... ასე გამოიყურება:

F = AvBvC…

4. ლოგიკური ოპერაცია IMPLICATION (ლოგიკური შედეგი). ბუნებრივ ენებში ეს შეესაბამება მეტყველების ფიგურას, თუ... მაშინ..., პროგრამირების ენებში აღინიშნება თუ,

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

ამ ოპერაციის მათემატიკური აღნიშვნა ორი ლოგიკური ცვლადი ადა INასე გამოიყურება:

F = A?B.

5. ლოგიკური ოპერაცია EQUIVALENCE (ლოგიკური ეკვივალენტობა). ბუნებრივ ენებში შეესაბამება მეტყველების ფიგურას მაშინ და მხოლოდ მაშინ,ლოგიკის ალგებრაში აღინიშნება?.

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

ამ ოპერაციის მათემატიკური აღნიშვნა ლოგიკური ცვლადებისთვის A, B, C...ასე გამოიყურება:

4.2. ლოგიკის ალგებრის ძირითადი კანონები და ლოგიკური გამონათქვამების გარდაქმნის წესები

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

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

1. წინააღმდეგობის კანონი:

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

3. ორმაგი უარყოფის კანონი:

4. დე მორგანის კანონები:

5. გამეორების კანონები: A&A=A; A v A = A; B & B = B; V v V = V.

6. შთანთქმის კანონები: ა? (A & B) = A; A & (A? B) = A.

7. მუდმივების აღმოფხვრის კანონები: ა? 1 = 1; ა? 0 = A; A&1=A; A&0=0; ბ? 1 = 1; ბ? 0 = B; B&1=B; B & 0 = 0.

8. წებოვნების კანონები:

9. კონტრაპოზიციის კანონი: (A ? B) = (B ? A).

ლოგიკური ცვლადებისთვის ასევე მოქმედებს ზოგადი მათემატიკური კანონები. აღნიშვნის გასაადვილებლად, ჩვენ წარმოგიდგენთ ზოგად მათემატიკურ კანონებს სამი ლოგიკური ცვლადისთვის A, B და C:

1. კომუტაციური კანონი: A&B = B&A; ა? B = B? ა.

2. ასოციაციის კანონი: A & (B & C) = (A & B) & C; ა? (B ? C) = (A ? B) ? C.

3. გამანაწილებელი კანონი: A & (B ? C) = (A & B) ? (A&C).

როგორც უკვე აღვნიშნეთ, ლოგიკური ალგებრის კანონების გამოყენებით შესაძლებელია ლოგიკური გამონათქვამების ეკვივალენტური გარდაქმნები მათი გამარტივების მიზნით. ლოგიკის ალგებრაში, მიღებული კონვენციის საფუძველზე, დადგენილია შემდეგი წესები (პრიორიტეტები) ლოგიკური მოქმედებების შესასრულებლად: ჯერ ფრჩხილებში ჩასმული მოქმედებები სრულდება, შემდეგ შემდეგი თანმიმდევრობით: ინვერსია (უარყოფა), შეერთება (&), დისიუნქცია. (v), იმპლიკაცია (?), ეკვივალენტობა (?)

გადავცვალოთ, მაგალითად, ლოგიკური ფუნქცია

ლოგიკური ალგებრის შესაბამისი კანონების გამოყენებით.

4.3. ლოგიკური ფუნქციები და სიმართლის ცხრილები

ლოგიკურ ცვლადებსა და ლოგიკურ ფუნქციებს შორის ურთიერთობა ლოგიკის ალგებრაში ასევე შეიძლება გამოჩნდეს შესაბამისი ცხრილების გამოყენებით, რომლებსაც სიმართლის ცხრილები ეწოდება. სიმართლის ცხრილები ფართოდ გამოიყენება, რადგან ისინი ნათლად აჩვენებენ რა მნიშვნელობებს იღებს ლოგიკური ფუნქცია მისი ლოგიკური ცვლადების მნიშვნელობების ყველა კომბინაციისთვის. სიმართლის ცხრილი ორი ნაწილისგან შედგება. პირველი (მარცხნივ) ნაწილი ეხება ლოგიკურ ცვლადებს და შეიცავს ლოგიკური ცვლადების შესაძლო კომბინაციების სრულ ჩამონათვალს. A, B, C...და ა.შ. ამ ცხრილის მეორე (მარჯვნივ) ნაწილი განსაზღვრავს გამომავალ მდგომარეობებს, როგორც შეყვანის სიდიდეების კომბინაციების ლოგიკურ ფუნქციას.

მაგალითად, ლოგიკური ფუნქციისთვის F=Aვ B v Cსამი ლოგიკური ცვლადის (დისუნქციები). A, B,და თანსიმართლის ცხრილს ექნება ფორმა, რომელიც ნაჩვენებია ნახ. 4.1. ლოგიკური ცვლადების და ლოგიკური ფუნქციების მნიშვნელობების ჩასაწერად, ეს სიმართლის ცხრილი შეიცავს 8 სტრიქონს და 4 სვეტს, ანუ ნებისმიერი სიმართლის ცხრილის არგუმენტების და ფუნქციების ჩასაწერი ხაზების რაოდენობა ტოლი იქნება. 2n,სად p –ლოგიკური ფუნქციის არგუმენტების რაოდენობა და სვეტების რაოდენობა არის n + 1.

ბრინჯი. 4.1. სიმართლის ცხრილი ლოგიკური ფუნქციისთვის F=Aვ IN v C

სიმართლის ცხრილი შეიძლება შედგეს ნებისმიერი ლოგიკური ფუნქციისთვის, მაგალითად, ნახ. 4.2 გვიჩვენებს ლოგიკური ფუნქციის სიმართლის ცხრილს F=A? ბ? C(ეკვივალენტები).

ლოგიკურ ფუნქციებს აქვთ შესაბამისი სახელები. ორი ბინარული ცვლადისთვის არის თექვსმეტი ლოგიკური ფუნქცია, რომელთა სახელები მოცემულია ქვემოთ. ნახ. 4.3 წარმოგიდგენთ ცხრილს, სადაც ნაჩვენებია ლოგიკური ფუნქციები F 1, F 2, F 3, … , F 16ორი ლოგიკური ცვლადი ადა IN.

ფუნქცია F 1 = 0და ეწოდება ნულოვანი მუდმივი ფუნქცია, ან ნულოვანი გენერატორი.

ბრინჯი. 4.2. სიმართლის ცხრილი ლოგიკური ფუნქციისთვის F=A? ბ? C

ბრინჯი. 4.3. ლოგიკური ფუნქციები F 1, F 2, F 3,… F 16 ორი არგუმენტიდან ადა IN

ფუნქცია F 2 = A & Bშეერთების ფუნქციას უწოდებენ.

ა.

ფუნქცია F 4 = A ა.

ეწოდება აკრძალვის ფუნქცია ლოგიკურ ცვლადზე IN.

ფუნქცია F 6 = Bლოგიკური ცვლადის მიერ გამეორების ფუნქციას უწოდებენ IN.

ეწოდება ექსკლუზიური OR ფუნქცია.

ფუნქცია F 8 = A v Bდისიუქციის ფუნქციას უწოდებენ.

პირსის ფუნქციას უწოდებენ.

ექვივალენტობის ფუნქციას უწოდებენ.

IN.

ფუნქცია F 12 = B? ა ბ? ა.

ლოგიკური ცვლადის უარყოფის (ინვერსიის) ფუნქციას უწოდებენ ა.

ფუნქცია F 14 = A? ბიმპლიკაციურ ფუნქციას უწოდებენ ა? ბ.

შაფერის ფუნქციას უწოდებენ.

ფუნქცია F 16 = 1-ს ეწოდება გენერატორის ფუნქცია 1.

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

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

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

ბრინჯი. 4.4. Function Wizard - ნაბიჯი 1 / 2 დიალოგი

როგორც ჩანს ნახ. 4.4, როგორც პროგრამის ლოგიკური ფუნქციების ნაწილი MS Excelმოიცავს ლოგიკური ფუნქციების ფუნქციურად სრულ კომპლექტს, რომელიც შედგება შემდეგი ლოგიკური ფუნქციებისაგან: AND (შეერთება), OR (განშორება), NOT (უარყოფა). ამრიგად, პროგრამის ლოგიკური ფუნქციების ფუნქციურად სრული ნაკრების გამოყენებით MS Excelსხვა ფუნქციების განხორციელება შესაძლებელია. ლოგიკური IF ფუნქცია (იმპლიკამენტი), ასევე შედის ლოგიკურ ფუნქციებში MS Excel,ახორციელებს ლოგიკურ შემოწმებას და, შემოწმების შედეგიდან გამომდინარე, ასრულებს ორი შესაძლო მოქმედებიდან ერთ-ერთს. ამ პროგრამაში მას აქვს შემდეგი ფორმატი: = IF (arg1;arg2;arg3), სადაც arg1 არის ლოგიკური პირობა; arg2 – დაბრუნების მნიშვნელობა იმ პირობით, რომ არგუმენტის arg1 მნიშვნელობა არის true (TRUE); arg3 არის დაბრუნებული მნიშვნელობა იმ პირობით, რომ arg1 მნიშვნელობა არ არის true (FALSE). მაგალითად, თუ პროგრამის ფურცლის თვითნებურ უჯრედში MS Excelშეიყვანეთ გამოთქმა "=IF (A1 = 5; "ხუთი"; "არა ხუთი")", შემდეგ A1 უჯრაში 5-ის შეყვანისას და ღილაკზე "Enter" დაჭერისას, სიტყვა "ხუთი" ავტომატურად ჩაიწერება უჯრედში. A1, A1 უჯრედში ნებისმიერი სხვა ნომრის შეყვანისას მასში ჩაიწერება სიტყვა "არა ხუთი". როგორც უკვე აღვნიშნეთ, პროგრამის ლოგიკური ფუნქციების გამოყენებით შესაძლებელია MS Excelწარმოადგინოს სხვა ლოგიკური ფუნქციები და მათი შესაბამისი ჭეშმარიტების ცხრილები.

IF და AND ლოგიკური ფუნქციების გამოყენებით ჩვენ ვახორციელებთ ლოგიკური ფუნქციის შეცვლილ სიმართლის ცხრილს F = A & B(შეერთება), რომელიც შედგება ორი მწკრივისა და სამი სვეტისგან, რაც საშუალებას გაძლევთ შეცვალოთ ლოგიკური ცვლადების მნიშვნელობები (0 ან 1). A და Bავტომატურად დააყენეთ, მაგალითად, E6 უჯრედში ფუნქციის მნიშვნელობა F = A & B,შეესაბამება ამ ლოგიკური ცვლადების მნიშვნელობებს. ამისათვის შეიყვანეთ შემდეგი გამონათქვამი E6 უჯრედში: „=IF(AND(C6;D6);1;0)“, შემდეგ როდესაც C6 და D6 უჯრედებში შეიყვანთ მნიშვნელობებს 0 ან 1, იქნება ლოგიკური ფუნქცია. შესრულდეს E6 უჯრედში F = A & B.ამ მოქმედებების შედეგი ნაჩვენებია ნახ. 4.5.

ბრინჯი. 4.5. ლოგიკური ფუნქციის შეცვლილი სიმართლის ცხრილის დანერგვა F = A & B

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

რთული ციფრული ლოგიკური მოწყობილობები, რომლებიც ქმნიან კომპიუტერს, შედგება ელექტრონული აღჭურვილობის საფუძველზე აგებული რიგი ელემენტარული ლოგიკური ელემენტებისაგან. ამ ელექტრონული ლოგიკური ელემენტების წარმოებაში გამოიყენება სხვადასხვა ტექნოლოგიები და მიკროსქემის გადაწყვეტილებები, როგორიცაა: DTL (დიოდ-ტრანზისტორი ლოგიკა), TTL (ტრანზისტორი-ტრანზისტორი ლოგიკა), ECL (ემიტერ-დაწყვილებული ლოგიკა), ტექნოლოგიები, რომლებიც დაფუძნებულია გამოყენებაზე. საველე ეფექტის ტრანზისტორები და ა.შ. ლოგიკური ელემენტები საშუალებას გაძლევთ განახორციელოთ ნებისმიერი ლოგიკური ფუნქცია. ლოგიკური ელემენტების შემავალი და გამომავალი სიგნალები, რომლებიც შეესაბამება ორ ლოგიკურ მდგომარეობას 1 და 0, შეიძლება ჰქონდეს ორი დაყენებული ელექტრული ძაბვის დონეებიდან ერთ-ერთი, რაც დამოკიდებულია ლოგიკური ელემენტის მიკროსქემის დიზაინზე. მაგალითად, TTL ტექნოლოგიაზე დაფუძნებული ლოგიკური ელემენტებისთვის, ელექტრული ძაბვის მაღალი დონე (2.4 × 5 ვ) შეესაბამება ერთის ლოგიკურ მნიშვნელობას (true), ხოლო დაბალი დონე (0 × 0.4 V) შეესაბამება ლოგიკურ ნულს ( ყალბი).

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

1. NOT ლოგიკური ელემენტი, რომელსაც ასევე უწოდებენ ინვერტორს, ასრულებს უარყოფის (ინვერსიის) ლოგიკურ ოპერაციას.

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

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

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

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

Minterm არის ლოგიკური ფუნქცია, რომელიც იღებს ლოგიკური ერთის მნიშვნელობას ლოგიკური ცვლადების მხოლოდ ერთი მნიშვნელობისთვის და ლოგიკური ნულის მნიშვნელობას ლოგიკური ცვლადების სხვა მნიშვნელობებისთვის. მაგალითად, მინტერმები ლოგიკური ფუნქციებია F 2, F 3, F 5და F 9(იხ. სურ. 4.3).

maxtern არის ლოგიკური ფუნქცია, რომელიც იღებს ლოგიკური ნულის მნიშვნელობას ლოგიკური ცვლადების მხოლოდ ერთი მნიშვნელობისთვის და ლოგიკური ერთის მნიშვნელობას ლოგიკური ცვლადების სხვა მნიშვნელობებისთვის. მაგალითად, ოსტატები ლოგიკური ფუნქციებია F 8, F 12, F 14და F 15(იხ. სურ. 4.3).

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

განვიხილოთ სინთეზის პრობლემა შეცვლილი სიმართლის ცხრილის მაგალითის გამოყენებით, რომელიც ნაჩვენებია ნახ. 4.6. მოცემული სიმართლის ცხრილისთვის, თქვენ უნდა დაწეროთ გამოხატულება გამომავალი ფუნქციისთვის F,განახორციელეთ მისი ტრანსფორმაცია (მინიმიზაცია) ლოგიკური ალგებრის კანონების საფუძველზე და ძირითადი ლოგიკური ელემენტების - NOT, AND და OR გამოყენებით, შეიმუშავეთ ლოგიკური წრე გამომავალი ფუნქციის განსახორციელებლად. ფ.

ბრინჯი. 4.6. ლოგიკური ცვლადების სიმართლის ცხრილი A, Bდა თან

ლოგიკური ცვლადი მნიშვნელობები A, Bდა თანდა შესაბამისი ფუნქციის მნიშვნელობები ფმოცემულია ჭეშმარიტების ცხრილში (იხ. სურ. 4.6), სადაც სვეტი No. მიუთითებს ლოგიკური ცვლადების კომბინაციის რაოდენობაზე. A, B და C.

ამ პრობლემის გადასაჭრელად წარმოგიდგენთ ლოგიკურ ფუნქციას F inჩამოაყალიბეთ SDNF და შემდეგ SKNF-ში. ვიპოვოთ დამხმარე ფუნქციები minterm და maxterm. მოცემულ ჭეშმარიტების ცხრილში გამომავალი ფუნქცია ფიღებს ლოგიკურ მნიშვნელობას, რომელიც ტოლია ლოგიკური ცვლადების კომბინაციისთვის A, Bდა თან, მითითებულია 3, 6, 8 ნომრებში და მნიშვნელობა ტოლია ლოგიკური ნულის - 1, 2, 4, 5,7 ნომრებში მითითებული კომბინაციებისთვის.

ჩვენ ვწერთ მინტერმებს შემდეგი ფორმით:

მინტერმები არის ლოგიკური ცვლადების ლოგიკური პროდუქტები (კავშირები). A, B,და თან F,ტოლი ლოგიკური (კომბინაციები 3, 6, 8). ფაქტორები (ლოგიკური ცვლადები A, Bდა თანმინტერმში შედის პირდაპირი ფორმით (უარყოფის გარეშე), თუ მათი მნიშვნელობები ტოლია ლოგიკური ერთის და შებრუნებული ფორმით (უარყოფით), თუ მათი მნიშვნელობები ტოლია ლოგიკურ ნულს. ლოგიკური ფუნქცია ფ SDNF-ში ტოლი იქნება მინტერმების ლოგიკური ჯამი:

ლოგიკური ფუნქციის მინიმიზაციის შემდეგ Fcლოგიკის ალგებრის კანონების გამოყენებით ვიღებთ მის სასურველ გამონათქვამს:

ჩვენ ვწერთ მაქსტერმებს შემდეგი ფორმით:

მაქსტერმები არის ლოგიკური ცვლადების ლოგიკური ჯამები (განშორებები). A, B,და თანლოგიკური ფუნქციის მნიშვნელობებზე F,ტოლია ლოგიკური ნულის (კომბინაციები 1, 2, 4, 5, 7). დამატებები (ლოგიკური ცვლადები A, B და C)მაქსიმუმში შედის პირდაპირი ფორმით (უარყოფის გარეშე), თუ მათი მნიშვნელობები ტოლია ლოგიკური ნულის ტოლია და ინვერსიული ფორმით (უარყოფით), თუ მათი მნიშვნელობები ტოლია ლოგიკური ერთის. ლოგიკური ფუნქცია ფვ თან CNF ტოლი იქნება მაქსტერმების ლოგიკური ნამრავლის:

იმის გამო, რომ F-ის გამოთქმა SCNF-ის სახით უფრო რთულია, ვიდრე წარმოდგენა ფ SDNF-ის სახით, შემდეგ, როგორც საბოლოო გამოხატულება ფავიღოთ მისი გამოხატულება SDNF-ის სახით, ე.ი.

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

ჩვენ ვიყენებთ შედეგად მიღებული ლოგიკური ფუნქციის გამოხატვას ფ NOT, AND და OR ლოგიკური სქემის შემუშავება (აშენება) ლოგიკური ელემენტების ფუნქციურად სრული ნაკრების საფუძველზე. ლოგიკური სქემის აგებისას აუცილებელია ლოგიკურ ალგებრაში დადგენილი წესების (პრიორიტეტების) გათვალისწინება ლოგიკური ოპერაციების შესასრულებლად, რომლებიც ამ შემთხვევაში ხორციელდება ლოგიკური ელემენტების NOT, AND და OR გამოყენებით. შესრულებული ლოგიკური მოქმედებების თანმიმდევრობა შემდეგი იქნება: ინვერსიის (უარყოფის), ლოგიკური გამრავლების (შეერთების) და შემდეგ ლოგიკური შეკრების (დისუნქციის) ოპერაცია. ფუნქციის განხორციელება ფლოგიკური დიაგრამის სახით, რომელიც ნაჩვენებია ნახ. 4.7.

ბრინჯი. 4.7. ფუნქციის განხორციელება ფლოგიკური დიაგრამის სახით

ლოგიკური სქემების გრაფიკულად საჩვენებლად, არსებობს სხვადასხვა კომპიუტერული პროგრამა, რომელსაც ეწოდება გრაფიკული რედაქტორები. ეს პროგრამები შეიძლება შევიდეს სხვა კომპიუტერულ პროგრამებში, მაგალითად პროგრამებში Microsoft Wordდა Microsoft Excelასეთი რედაქტორები განხორციელებულია Drawing ინსტრუმენტთა ზოლების გამოყენებით, ან შეიძლება იყოს ცალკე პროგრამები, მაგალითად Paint, Microsoft Visioდა ა.შ. გამოვიყენოთ პროგრამის ჩაშენებული გრაფიკული რედაქტორი (Drawing panel). MS Excelფუნქციის ლოგიკური დიაგრამის გრაფიკულად ჩვენება ფ.ეს ლოგიკური დიაგრამა ნაჩვენებია ნახ. 4.8.

ბრინჯი. 4.8. ლოგიკური ფუნქციის გრაფიკული ჩვენება ფპროგრამის გამოყენებით MS Excel

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

ზემოთ განხილული ლოგიკური ელემენტების სიმართლის ცხრილები აჩვენებს ლოგიკური ცვლადების სტაბილური მდგომარეობის მნიშვნელობებს. თუმცა, როდესაც ლოგიკური ცვლადები წარმოდგენილია როგორც ელექტრული სიგნალები, გარკვეული დრო სჭირდება ლოგიკური ფუნქციის მნიშვნელობას, რათა მიაღწიოს სტაბილურ მდგომარეობას ელექტრონულ ლოგიკურ კარიბჭეებში შიდა დროის შეფერხებების გამო. საშუალოდ, ასეთი ელემენტის ელექტრული სიგნალის დაყოვნება არის 10 -9 წმ. კომპიუტერში ორობითი სიგნალები გადის ბევრ ელექტრონულ წრეში და დროის შეფერხება შეიძლება მნიშვნელოვანი გახდეს. ამ შემთხვევაში, ლოგიკური ოპერაციის თითოეულ საფეხურზე გამოყოფილია დროის მონაკვეთი (ციკლი). თუ ოპერაცია მთავრდება საათის დროის დასრულებამდე, მაშინ კომპიუტერში შემავალი მოწყობილობა ელოდება მის დასრულებას. შედეგად, ოპერაციების სიჩქარე გარკვეულწილად მცირდება, მაგრამ მიღწეულია მაღალი საიმედოობა, რადგან უზრუნველყოფილია სინქრონიზაცია კომპიუტერზე მრავალ პარალელურ ოპერაციას შორის. კომპიუტერში მოწყობილობების სინქრონიზაცია უზრუნველყოფილია სპეციალური გენერატორის - საათის სიხშირის გენერატორის გამოყენებით, რომელიც წარმოქმნის სტაბილური სიხშირის ელექტრულ იმპულსებს.

სავარჯიშოები, რომლებიც უნდა გააკეთოთ დამოუკიდებლად

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

ა) 101 და 110; ბ) 10101 და 11100; გ) 110011 და 111100.

2. გადააკეთეთ შემდეგი ლოგიკური გამონათქვამები:

3. დაამტკიცეთ, რომ ორი ლოგიკური ცვლადის ლოგიკური ფუნქციის რაოდენობაა 16.

4. პროგრამის გამოყენებით NOT, OR, NAND, NOR ლოგიკური სქემების შეცვლილი სიმართლის ცხრილების დანერგვა (იხ. სურ. 4.5). MS Excel.

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

6. დაწერეთ გამოთქმები ლოგიკური ფუნქციებისთვის F 1და F 2 SDNF და SKNF სახით. ლოგიკური ფუნქციები F 1და F 2ქვემოთ წარმოდგენილია შესაბამისად სიმართლის ცხრილებით.

7. მასწავლებლის მიერ მითითებული ცხრილის ვერსიის მიხედვით ნშექმენით სიმართლის ცხრილი ლოგიკური ფუნქციისთვის F,მაგიდის გამოყენებით მ.იპოვნეთ გამოხატულება ლოგიკური ფუნქციისთვის F,განახორციელეთ მისი ტრანსფორმაცია ლოგიკური ალგებრის ძირითადი კანონების შესაბამისად და შეიმუშავეთ მიღებული ფუნქციის ლოგიკური წრე NOT, AND, OR ლოგიკური სქემების გამოყენებით. განვითარებული ლოგიკური სქემის გრაფიკულად საჩვენებლად გამოიყენეთ ნებისმიერი გრაფიკული რედაქტორი.

ცხრილი M
ცხრილი N

ლოგიკის ალგებრა

ლოგიკის ალგებრა

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

ლოგიკის ალგებრის ფუძემდებელია ინგლისელი მათემატიკოსი და ლოგიკოსი ჯ.ბული (1815-1864), რომელმაც თავისი ლოგიკური სწავლება ალგებრასა და ლოგიკას შორის ანალოგიაზე დააფუძნა. მან დაწერა ნებისმიერი განცხადება მის მიერ შემუშავებული ენის სიმბოლოების გამოყენებით და მიიღო „განტოლებები“, რომელთა ჭეშმარიტება ან სიცრუე შეიძლება დადასტურდეს გარკვეული ლოგიკური კანონების საფუძველზე, როგორიცაა ურთიერთობის, განაწილების, ასოციაციურობის კანონები და ა.შ.

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

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

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

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

გარდა ორფასიანი წინადადების ალგებრა, რომელშიც მხოლოდ ორი მნიშვნელობაა მიღებული - "true" და "false", არის მრავალმნიშვნელოვანი წინადადების ალგებრა.ასეთ ალგებრაში, გარდა მნიშვნელობებისა "ჭეშმარიტი" და "მცდარი", გამოიყენება ჭეშმარიტების ისეთი მნიშვნელობები, როგორიცაა "სავარაუდო", "შესაძლებელია", "შეუძლებელი" და ა.შ.

ალგებრაში ლოგიკა განსხვავებულია მარტივი(დაწყებითი) განცხადებები, აღინიშნება ლათინური ასოებით (A, B, C, D, ...) და კომპლექსი(კომპოზიტური), შედგება რამდენიმე მარტივისაგან ლოგიკური დამაკავშირებლების გამოყენებით, მაგალითად, მაგ "არა", "და", "ან", "თუ და მხოლოდ მაშინ", "თუ... მაშინ". ამ გზით მიღებული რთული დებულებების ჭეშმარიტება-მცდარობა განისაზღვრება მარტივი განცხადებების მნიშვნელობით.

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

შემდეგ რთული დებულება „ლოგიკის ალგებრა წარმატებით გამოიყენება ელექტრული სქემების თეორიაში და სარელეო სქემების სინთეზში“ შეიძლება მოკლედ დაიწეროს როგორც A და B; აქ "და" არის ლოგიკური დამაკავშირებელი. აშკარაა, რომ ელემენტარული განცხადებებიდან A და Bმართალია, მაშინ რთული დებულება მართალია A და B.

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

არსებობს მხოლოდ ორი ლოგიკური მნიშვნელობა: მართალია (TRUE)და ყალბი (FALSE). ეს შეესაბამება ციფრულ წარმოდგენას − 1 და 0 . თითოეული ლოგიკური ოპერაციის შედეგები შეიძლება დაიწეროს ცხრილის სახით. ასეთ ცხრილებს სიმართლის ცხრილებს უწოდებენ.

ალგებრის ლოგიკის ძირითადი ოპერაციები

1. ლოგიკური უარყოფა, ინვერსია(ლათ. ინვერსია- ინვერსია) არის ლოგიკური ოპერაცია, რის შედეგადაც მიიღება ახალი განცხადება მოცემული განცხადებიდან (მაგალითად, A) არა ა), რომელსაც ე.წ ორიგინალური განცხადების უარყოფა, სიმბოლურად მითითებულია ზედა ზოლით ($A↖(-)$) ან ისეთი კონვენციებით, როგორიცაა ¬, "არა"და კითხულობს: "არა A", "A არის მცდარი", "მართალი არ არის, რომ A", "A-ს უარყოფა". მაგალითად, „მარსი მზის სისტემის პლანეტაა“ (განცხადება A); „მარსი არ არის პლანეტა მზის სისტემაში“ ($A↖(-)$); განცხადება „10 არის მარტივი რიცხვი“ (განცხადება B) მცდარია; დებულება „10 არ არის მარტივი რიცხვი“ (განცხადება B) მართალია.

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

დებულება $A↖(-)$ მცდარია, როცა A არის ჭეშმარიტი და მართალია, როცა A მცდარია.

გეომეტრიულად, უარყოფა შეიძლება წარმოდგენილი იყოს შემდეგნაირად: თუ A არის წერტილების გარკვეული ნაკრები, მაშინ $A↖(-)$ არის A სიმრავლის შევსება, ანუ ყველა წერტილი, რომელიც არ მიეკუთვნება A სიმრავლეს.

2.შეერთება(ლათ. კონიუნქტიო- კავშირი) - ლოგიკური გამრავლება, ოპერაცია, რომელიც მოითხოვს მინიმუმ ორ ლოგიკურ რაოდენობას (ოპერანდებს) და აკავშირებს ორ ან მეტ განცხადებას შემაერთებელის გამოყენებით. "და"(მაგალითად, "A და B"), რომელიც სიმბოლურად აღინიშნება ∧ (A ∧ B) ნიშნით და იკითხება: „A და B“. შემდეგი ნიშნები ასევე გამოიყენება კავშირის აღსანიშნავად: A ∙ B; A & B, A და B, და ზოგჯერ არ არის ნიშანი განცხადებებს შორის: AB. ლოგიკური გამრავლების მაგალითი: „ეს სამკუთხედი არის ტოლკუთხედი და მართკუთხა“. მოცემული განცხადება შეიძლება იყოს ჭეშმარიტი მხოლოდ იმ შემთხვევაში, თუ ორივე პირობა დაკმაყოფილებულია, წინააღმდეგ შემთხვევაში განცხადება მცდარია.

ა	ბ	A∧B
1	0	0
0	1	0
0	0	0
1	1	1

განცხადება ა ∧ INმართალია მხოლოდ იმ შემთხვევაში, თუ ორივე განცხადება არის ადა INმართალია.

გეომეტრიულად შეერთება შეიძლება წარმოდგენილი იყოს შემდეგნაირად: თუ A, B ა ∧ INარის კომპლექტების გადაკვეთა ადა IN.

3. დისჯუნქცია(ლათ. დისუნქცია- დაყოფა) - ლოგიკური დამატება, ოპერაცია, რომელიც აკავშირებს ორ ან მეტ განცხადებას შემაერთებელის გამოყენებით "ან"(მაგალითად, "A ან B"), რომელიც სიმბოლურად აღინიშნება ∨ ნიშნით (ა∨ IN)და კითხულობს: "A ან B". შემდეგი ნიშნები ასევე გამოიყენება განცალკევების აღსანიშნავად: A + B; A ან B; A | ბ. ლოგიკური მიმატების მაგალითი: "რიცხვი x იყოფა 3-ზე ან 5-ზე." ეს განცხადება იქნება ჭეშმარიტი, თუ ორივე პირობა ან ერთი პირობა მაინც დაკმაყოფილდება.

ოპერაციის სიმართლის ცხრილს აქვს ფორმა

ა	ბ	ა ∨ ბ
1	0	1
0	1	1
0	0	0
1	1	1

განცხადება ა∨ INმცდარია მხოლოდ მაშინ, როდესაც ორივე განცხადება არის ადა INყალბი.

გეომეტრიულად ლოგიკური შეკრება შეიძლება წარმოდგენილი იყოს შემდეგნაირად: თუ A, Bარის ქულების რამდენიმე ნაკრები, მაშინ ა ∨ INარის კომპლექტების გაერთიანება ადა IN, ანუ ფიგურა, რომელიც აერთიანებს კვადრატსაც და წრესაც.

4. მკაცრად განცალკევებული განცალკევება, მოდულის ორი დამატება- ლოგიკური ოპერაცია, რომელიც აკავშირებს ორ განცხადებას შემაერთებელის გამოყენებით "ან", გამოიყენება ექსკლუზიური მნიშვნელობით, რომელიც სიმბოლურად აღინიშნება ნიშნებით ∨ ∨ ან ⊕ ( ა ∨ ∨ ბ, ა ⊕ IN) და კითხულობს: "ან A ან B". მოდულის ორი მიმატების მაგალითია დებულება „ეს სამკუთხედი არის ბლაგვი ან მახვილი“. განცხადება მართალია, თუ რომელიმე პირობა დაკმაყოფილებულია.

ოპერაციის სიმართლის ცხრილს აქვს ფორმა

ა	IN	ა⊕ ბ
1	0	1
0	1	1
0	0	0
1	1	0

დებულება A ⊕ B მართალია მხოლოდ იმ შემთხვევაში, თუ A და B განცხადებებს განსხვავებული მნიშვნელობა აქვთ.

5. იმპლიკაცია(ლათ. იმპლიზიტო- მჭიდრო დაკავშირება) - ლოგიკური ოპერაცია, რომელიც აკავშირებს ორ განცხადებას შემაერთებელის გამოყენებით "თუ... მაშინ"რთულ დებულებაში, რომელიც სიმბოლურად აღინიშნება ნიშნით → ( ა → IN) და კითხულობს: "თუ A, მაშინ B", "A ნიშნავს B", "A-დან მოდის B", "A ნიშნავს B". ნიშანი ⊃ (A ⊃ B) ასევე გამოიყენება იმპლიკაციის აღსანიშნავად. იმპლიკაციის მაგალითი: „თუ მიღებული ოთხკუთხედი არის კვადრატი, მაშინ წრე შეიძლება აღწეროს მის გარშემო“. ეს ოპერაცია აკავშირებს ორ მარტივ ლოგიკურ გამონათქვამს, რომელთაგან პირველი პირობაა, მეორე კი შედეგი. ოპერაციის შედეგი მცდარია მხოლოდ მაშინ, როდესაც წინაპირობა არის ჭეშმარიტი და შედეგი მცდარი. მაგალითად, ”თუ 3 * 3 = 9 (A), მაშინ მზე არის პლანეტა (B),” შედეგი A → B არის მცდარი.

ოპერაციის სიმართლის ცხრილს აქვს ფორმა

ა	IN	ა→IN
1	0	0
0	1	1
0	0	1
1	1	1

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

6. ეკვივალენტობა, ორმაგი ჩანაფიქრი, ეკვივალენტობა(ლათ. aequalis- თანაბარი და ვალენტისი- ძალის მქონე) - ლოგიკური ოპერაცია, რომელიც საშუალებას იძლევა ორი განცხადებიდან ადა INმიიღეთ ახალი გამოხატულება A ≡ Bრომელიც წერია: "A უდრის B". ეკვივალენტობის აღსანიშნავად გამოიყენება აგრეთვე შემდეგი ნიშნები: ⇔, ∼. ეს ოპერაცია შეიძლება გამოიხატოს შემაერთებლებით "მაშინ და მხოლოდ მაშინ", "აუცილებელი და საკმარისი", "ექვივალენტი". ეკვივალენტობის მაგალითია განცხადება: „სამკუთხედი მართკუთხაა, თუ და მხოლოდ იმ შემთხვევაში, თუ რომელიმე კუთხე 90 გრადუსია“.

ეკვივალენტობის ოპერაციის ჭეშმარიტების ცხრილს აქვს ფორმა

ა	IN	ა∼ IN
1	0	0
0	1	0
0	0	1
1	1	1

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

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

ლოგიკური მოქმედებების პრიორიტეტი შემდეგია: უარყოფა ( "არა") აქვს უმაღლესი პრიორიტეტი, შემდეგ კავშირს ( "და"), შეერთების შემდეგ - დისიუნქცია ( "ან").

ლოგიკური ცვლადების და ლოგიკური ოპერაციების დახმარებით ნებისმიერი ლოგიკური დებულება შეიძლება ფორმალიზდეს, ანუ შეიცვალოს ლოგიკური ფორმულით. ამ შემთხვევაში, ელემენტარული დებულებები, რომლებიც ქმნიან შედგენილ დებულებას, შეიძლება აბსოლუტურად არ იყოს დაკავშირებული მნიშვნელობით, მაგრამ ეს ხელს არ უშლის რთული განცხადების ჭეშმარიტების ან მცდარობის დადგენას. მაგალითად, განცხადება „თუ ხუთი მეტია ორზე ( ა), შემდეგ სამშაბათი ყოველთვის მოდის ორშაბათის შემდეგ ( IN)“ - მინიშნება ა→ IN, და ოპერაციის შედეგი ამ შემთხვევაში არის "მართალი". ლოგიკურ ოპერაციებში განცხადებების მნიშვნელობა არ არის გათვალისწინებული, განიხილება მხოლოდ მათი სიმართლე ან სიცრუე.

განვიხილოთ, მაგალითად, რთული განცხადების აგება განცხადებებიდან ადა IN, რომელიც მცდარი იქნება, თუ და მხოლოდ იმ შემთხვევაში, თუ ორივე განცხადება ჭეშმარიტია. შეკრების მოდულის ორი მოქმედების ჭეშმარიტების ცხრილში ვპოულობთ: 1 ⊕ 1 = 0. და განცხადება შეიძლება იყოს, მაგალითად, ასეთი: „ეს ბურთი მთლიანად წითელია ან მთლიანად ლურჯი“. ამიტომ თუ განცხადება ა"ეს ბურთი მთლიანად წითელია" არის სიმართლე და განცხადება IN"ეს ბურთი მთლიანად ლურჯია" მართალია, მაშინ რთული წინადადება მცდარია, რადგან ბურთი არ შეიძლება იყოს ერთდროულად წითელი და ლურჯი.

პრობლემის გადაჭრის მაგალითები

მაგალითი 1. X-ის მითითებული მნიშვნელობებისთვის განსაზღვრეთ ლოგიკური განცხადების მნიშვნელობა ((X > 3) ∨ (X< 3)) → (X < 4) :

1) X = 1; 2) X = 12; 3) X = 3.

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

ა	ბ	A → B
1	0	0
0	1	1
0	0	1
1	1	1

აქედან ვიღებთ:

1) X = 1-ისთვის:

((1 > 3) ∨ (1 < 3)) → (1 < 4) = ложь ∨ истина → истина = истина → истина = истина;

2) X = 12-ისთვის:

((12 > 3) ∨ (12 < 3) → (12 < 4) = истина ∨ ложь → ложь = истина → ложь = ложь;

3) X = 3-ისთვის:

((3 > 3) ∨ (3 < 3)) → (3<4) = ложь ∨ ложь → истина = ложь → истина = истина.

მაგალითი 2.მიუთითეთ X-ის მთელი მნიშვნელობების სიმრავლე, რომლისთვისაც გამოთქმა ¬((X > 2) → (X > 5)) მართალია.

გამოსავალი.უარყოფის ოპერაცია გამოიყენება მთელ გამოსახულებაზე ((X > 2) → (X > 5)), ამიტომ, როდესაც გამონათქვამი ¬((X > 2) → (X > 5)) მართალია, გამოსახულება ((X > 2) →(X > 5)) მცდარია. ამიტომ, აუცილებელია განვსაზღვროთ X-ის რომელი მნიშვნელობებისთვის გამოთქმა ((X > 2) → (X > 5)) არის მცდარი. იმპლიკაციის ოპერაცია ღებულობს მნიშვნელობას „false“ მხოლოდ ერთ შემთხვევაში: როდესაც სიცრუე გამომდინარეობს ჭეშმარიტებიდან. და ეს მართალია მხოლოდ X = 3-ისთვის; X = 4; X = 5.

მაგალითი 3.ქვემოთ ჩამოთვლილი სიტყვებიდან რომელზეა წინადადება ¬(პირველი ასო ხმოვანია ∧ მესამე ასო ხმოვანი) ⇔ 4 სიმბოლოსგან შემდგარი სტრიქონი მცდარია? 1) ასსა; 2) კუკუ; 3) სიმინდი; 4) შეცდომა; 5) ძლიერი კაცი.

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

1) სიტყვისთვის assa ვიღებთ: ¬(1 ∧ 0) ⇔ 1, 1 ⇔ 1 - დებულება მართალია;

2) სიტყვა კუკუსთვის ვიღებთ: ¬ (0 ∧ 0) ⇔ 1, 1 ⇔ 1 - დებულება მართალია;

3) სიტყვა სიმინდისთვის ვიღებთ: ¬ (0 ∧ 0) ⇔ 0, 1 ⇔ 0 - განცხადება მცდარია;

4) სიტყვის შეცდომაზე ვიღებთ: ¬ (1 ∧ 1) ⇔ 0, 0 ⇔ 0 - დებულება მართალია;

5) სიტყვისთვის ძლიერი ადამიანი ვიღებთ: ¬ (0 ∧ 0) ⇔ 1, 1 ⇔ 0 - განცხადება მცდარია.

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

ქვეშ ლოგიკური გამოხატულებაუნდა გავიგოთ, როგორც ჩანაწერი, რომელსაც შეუძლია მიიღოს ლოგიკური მნიშვნელობა "true" ან "false". ამ განმარტებით, ლოგიკურ გამონათქვამებს შორის უნდა განვასხვავოთ:

• გამონათქვამები, რომლებიც იყენებენ შედარების ოპერაციებს ("უფრო მეტი", "ნაკლები", "ტოლია", "არა ტოლი" და ა.შ.) და იღებენ ლოგიკურ მნიშვნელობებს (მაგალითად, გამოხატულება a > b, სადაც a = 5 და b = 7, უდრის მნიშვნელობას "false");
• პირდაპირი ლოგიკური გამონათქვამები, რომლებიც დაკავშირებულია ლოგიკურ სიდიდეებთან და ლოგიკურ ოპერაციებთან (მაგალითად, A ∨ B ∧ C, სადაც A = true, B = false და C = true).

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

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

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

მაგალითი.იპოვნეთ გამოთქმის მნიშვნელობა:

$1 ≤ a ∨ A ∨ sin(π/a - π/b)< 1 ∧ ¬B ∧ ¬(b^a + a^b >a + b ∨ A ∧ B)$ a = 2-ისთვის, b = 3, A = მართალია, B = მცდარი.

გამოსავალი.მნიშვნელობების დათვლის თანმიმდევრობა:

1) b a + a b > a + b, ჩანაცვლების შემდეგ მივიღებთ: 3 2 + 2 3 > 2 + 3, ანუ 17 > 2 + 3 = ჭეშმარიტი;

2) A ∧ B = მართალია ∧ მცდარი = მცდარი.

ამიტომ, ფრჩხილებში გამოსახული არის (b a + a b > a + b ∨ A ∧ B) = true ∨ false = true;

3) 1≤ a = 1 ≤ 2 = ჭეშმარიტი;

4) sin (π/a - π/ბ)< 1 = sin(π/2 - π/3) < 1 = истина.

ამ გამოთვლების შემდეგ საბოლოოდ მივიღებთ: true ∨ A ∧ true ∧ ¬B ∧ ¬ true.

ახლა უნდა შესრულდეს უარყოფის ოპერაციები, შემდეგ ლოგიკური გამრავლება და შეკრება:

5) ¬B = ¬ მცდარი = მართალია; ¬true = მცდარი;

6) A ∧ true ∧ true ∧ false = true ∧ true ∧ true ∧ false = false;

7) true ∨ false = true.

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

შენიშვნა.თუ გავითვალისწინებთ, რომ თავდაპირველი გამოხატულება არის, საბოლოო ჯამში, ორი წევრის ჯამი და ერთი მათგანის მნიშვნელობა არის 1 ≤ a = 1 ≤ 2 = ჭეშმარიტი, შემდგომი გამოთვლების გარეშე შეგვიძლია ვთქვათ, რომ შედეგი მთელი გამოხატვისთვის არის ასევე „მართალი“. “.

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

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

სამართალი	∨-სთვის	∧-სთვის
მოგზაურობა	A ∨ B = B ∨ A	A ∧ B = B ∧ A
კავშირებითი	A ∨ (B ∨ C) = (B ∨ A) ∨ C	A ∧ (B ∧ C) = (A ∧ B) ∧ C
დისტრიბუცია	A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C)	A ∨ B ∧ C = (A ∨ B) ∧ (A ∨ C)
დე მორგანის წესები	$(A ∨ B)↖(-)$ = $A↖(-) ∧ B↖(-)$	$(A ∧ B)↖(-)$ = $A↖(-) ∨ B↖(-)$
იმპოტენცია	A ∨ A = A	A ∧ A = A
აღება	A ∨ A ∧ B = A	A ∧ (A ∨ B) = A
შემაკავშირებელი	(A ∧ B) ∨ (A↖(-) ∧ B) = B	(A ∨ B) ∧ (A↖(-) ∨ B) = B
ცვლადის მოქმედება მისი ინვერსიით	$A ∨ A↖(-)$ = 1	$A ∧ A↖(-)$ = 0
მუშაობა მუდმივებთან	A ∨ 0 = A A ∨ 1 = 1	A ∧ 1 = A A ∧ 0 = 0
ორმაგი უარყოფითი	$A↖(=)$ = ა

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

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

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

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

1) X1 ∧ X2 ∨ X1 ∧ X2 ∪ ¬X1 ∧ X2 = X1 ∧ X2 ∨ ¬X1 ∧ X2 = (X1 ∨ ¬X1) ∧ X2 = 1 ∧ X2 = X2 .

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

2) X1 ∨ X1 ∧ X2 = X1 ∨ (1 ∨ 1 ∧ X2) = X1 ∨ (1 ∨ X2) = X1.

აქ, სიმარტივისთვის, გამოიყენება შთანთქმის კანონი.

3) ¬(X1 ∧ X2) ∨ X2 = (¬X1 ∨ ¬X2) ∨ X2 = ¬X1 ∨ ¬X2 ∨ X2 = ¬X1 ∨ 1 = 1 .

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

პრობლემის გადაჭრის მაგალითები

მაგალითი 1.იპოვეთ A ∧ ¬(¬B ∨ C) გამოხატვის ექვივალენტური ლოგიკური გამოხატულება.

გამოსავალი.ჩვენ ვიყენებთ დე მორგანის წესს B და C-სთვის: ¬(¬B ∨ C) = B ∧ ¬C.

ჩვენ ვიღებთ ორიგინალის ექვივალენტურ გამონათქვამს: A ∧ ¬(¬B ∨ C) = A ∧ B ∧ ¬C .

პასუხი: A ∧ B ∧ ¬C.

მაგალითი 2.მიუთითეთ A, B, C ლოგიკური ცვლადების მნიშვნელობა, რომლებისთვისაც ლოგიკური გამოხატვის (A ∨ B) → (B ∨ ¬C ∨ B) მნიშვნელობა არის მცდარი.

გამოსავალი.იმპლიკაციის მოქმედება მცდარია მხოლოდ იმ შემთხვევაში, თუ მცდარი წინაპირობა გამომდინარეობს ჭეშმარიტი წინაპირობიდან. მაშასადამე, მოცემული გამონათქვამისთვის A ∨ B წინაპირობა უნდა იყოს „ჭეშმარიტი“, ხოლო შედეგი, ანუ გამოთქმა B ∨ ¬C ∨ B უნდა იყოს „მცდარი“.

1) A ∨ B — დისიუნქციის შედეგი არის „true“ თუ ოპერანდებიდან ერთი მაინც არის „true“;

2) B ∨ ¬C ∨ B - გამოთქმა მცდარია, თუ ყველა ტერმინს აქვს მნიშვნელობა "false", ანუ B არის "false"; ¬C არის „false“ და, შესაბამისად, C ცვლადს აქვს მნიშვნელობა „true“;

3) თუ გავითვალისწინებთ წინაპირობას და გავითვალისწინებთ, რომ B არის „მცდარი“, მივიღებთ, რომ A-ს მნიშვნელობა არის „ჭეშმარიტი“.

პასუხი: A არის ჭეშმარიტი, B არის მცდარი, C არის ჭეშმარიტი.

მაგალითი 3.რა არის უდიდესი X მთელი რიცხვი, რომლისთვისაც არის დებულება (35

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

ა	ბ	A → B
1	0	0
0	1	1
0	0	1
1	1	1

გამოხატვა X< (X - 3) ложно при любых положительных значениях X. Следовательно, для того чтобы результатом импликации была «истина», необходимо и достаточно, чтобы выражение 35 < X · X также было ложно. Максимальное целое значение X, для которого 35 < X · X ложно, равно 5.

პასუხი: X = 5.

ლოგიკური გამონათქვამების გამოყენება გეომეტრიული რეგიონების აღსაწერად

ლოგიკური გამონათქვამები შეიძლება გამოყენებულ იქნას გეომეტრიული რეგიონების აღსაწერად. ამ შემთხვევაში, დავალება ჩამოყალიბებულია შემდეგნაირად: ჩაწერეთ მოცემული გეომეტრიული რეგიონისთვის ლოგიკური გამონათქვამი, რომელიც იღებს მნიშვნელობას „true“ x, y მნიშვნელობებისთვის, თუ და მხოლოდ იმ შემთხვევაში, თუ რომელიმე წერტილი კოორდინატებით (x; y) ეკუთვნის. გეომეტრიულ რეგიონამდე.

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

მაგალითი 1.მითითებულია გეომეტრიული რეგიონის გამოსახულება. დაწერეთ ლოგიკური გამონათქვამი, რომელიც აღწერს მის კუთვნილ წერტილთა სიმრავლეს.

1) .

გამოსავალი.მოცემული გეომეტრიული რეგიონი შეიძლება წარმოდგენილი იყოს შემდეგი რეგიონების სიმრავლის სახით: პირველი რეგიონი - D1 - ნახევრად სიბრტყე $(x)/(-1) +(y)/(1) ≤ 1$, მეორე - D2 - წრე, რომლის ცენტრი საწყისზეა $x ^2 + y^2 ≤ 1$. მათი გადაკვეთა D1 $∩$ D2 წარმოადგენს სასურველ რეგიონს.

შედეგი:ლოგიკური გამოხატულება $(x)/(-1)+(y)/(1) ≤ 1 ∧ x^2 + y^2 ≤ 1$.

2)

ეს ტერიტორია შეიძლება დაიწეროს შემდეგნაირად: |x| ≤ 1 ∧ y ≤ 0 ∧ y ≥ -1 .

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

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

მაგალითი 2.დახაზეთ და დაჩრდილეთ ფართობი იმ წერტილებისთვის, რომელთა ლოგიკური პირობა y ≥ x ∧ y + x ≥ 0 ∧ y დაკმაყოფილებულია< 2 .

გამოსავალი.საძიებო ტერიტორია არის სამი ნახევარსიბრტყის კვეთა. სიბრტყეზე ვაშენებთ სწორ ხაზებს (x, y) y = x; y = -x; y = 2. ეს არის რეგიონის საზღვრები და ბოლო საზღვარი y = 2 არ ეკუთვნის რეგიონს, ამიტომ ვხატავთ მას წერტილოვანი ხაზით. y ≥ x უტოლობის დასაკმაყოფილებლად, წერტილები უნდა იყოს y = x წრფის მარცხნივ, ხოლო y = -x უტოლობა დაკმაყოფილებულია იმ წერტილებისთვის, რომლებიც მდებარეობენ y = -x წრფის მარჯვნივ. მდგომარეობა y< 2 выполняется для точек, лежащих ниже прямой y = 2. В результате получим область, которая изображена на рис.:

ლოგიკური ფუნქციების გამოყენება ელექტრული წრეების აღსაწერად

ლოგიკური ფუნქციები ძალიან სასარგებლოა ელექტრული სქემების მუშაობის აღწერისთვის. ასე რომ, ნახატზე ნაჩვენები წრედისთვის, სადაც X ცვლადის მნიშვნელობა არის გადამრთველის მდგომარეობა (თუ ის ჩართულია, X-ის მნიშვნელობა არის „true“ და თუ ის გამორთულია, მნიშვნელობა არის „false“ ), Y-ის ეს მნიშვნელობა არის ნათურის მდგომარეობა (თუ ჩართულია - მნიშვნელობა არის "true", ხოლო თუ არა - "false"), ლოგიკური ფუნქცია ჩაიწერება ასე: Y = X. ფუნქცია Y ეწოდება გამტარობის ფუნქცია.

ნახაზზე ნაჩვენები სქემისთვის Y ლოგიკურ ფუნქციას აქვს ფორმა: Y = X1 ∪ X2, ვინაიდან ერთი ჩამრთველი საკმარისია ნათურის გასანათებლად. ნახ. წრეში, ნათურა რომ აანთოს, ორივე ჩამრთველი უნდა იყოს ჩართული, შესაბამისად, გამტარობის ფუნქციას აქვს ფორმა: Y = X1 ∧ X2.

უფრო რთული წრედისთვის გამტარობის ფუნქციას ექნება ფორმა: Y = (X11 ∨ (X12 ∧ X13)) ∧ X2 ∧ (X31 ∨ X32).

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

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

ლოგიკური ალგებრის აპარატის გამოყენება ლოგიკური სქემების დიზაინში

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

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

ტექნიკურად, კომპიუტერული ლოგიკური ელემენტი დანერგილია ელექტრული წრედის სახით, რომელიც წარმოადგენს სხვადასხვა ნაწილების: დიოდების, ტრანზისტორების, რეზისტორების, კონდენსატორების შეერთებას. ლოგიკური ელემენტის შეყვანა, რომელსაც ასევე უწოდებენ კარიბჭეს, იღებს მაღალი და დაბალი ძაბვის დონის ელექტრულ სიგნალებს და ერთი გამომავალი სიგნალი ასევე გაიცემა მაღალ ან დაბალ დონეზე. ეს დონეები შეესაბამება ბინარული სისტემის ერთ-ერთ მდგომარეობას: 1 - 0; სიმართლე მცდარია. თითოეულ ლოგიკურ ელემენტს აქვს თავისი სიმბოლო, რომელიც გამოხატავს მის ლოგიკურ ფუნქციას, მაგრამ არ მიუთითებს, თუ რა სახის ელექტრონული წრეა მასში დანერგილი. ეს აადვილებს რთული ლოგიკური სქემების დაწერას და გაგებას. ლოგიკური სქემების მოქმედება აღწერილია ჭეშმარიტების ცხრილების გამოყენებით. OR დიაგრამაში სიმბოლოა ნიშანი „1“ - დისიუნქციის მოძველებული აღნიშვნიდან „>=1“ (დისიუნქციის მნიშვნელობა არის 1, თუ ორი ოპერანდის ჯამი 1-ზე მეტი ან ტოლია). "&" ნიშანი AND დიაგრამაში არის ინგლისური სიტყვის შემოკლება და.

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

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

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

ფუნქციის მნიშვნელობების პოვნისას ჩაწერის მოსახერხებელი ფორმაა ცხრილი, რომელიც შეიცავს, გარდა ცვლადების და ფუნქციის მნიშვნელობებისა, ასევე შუალედური გამოთვლების მნიშვნელობებს. განვიხილოთ სიმართლის ცხრილის აგების მაგალითი $(X1)↖(-) ∧ X2 ∨ (X1 ∨ X2)↖(-) ∨ X1$ ფორმულისთვის.

X1	X2	$(X1)↖(-)$	$(X1)↖(-)$ \ X2	X1 ∧ X2	$(X1 ∨ X2)↖(-)$	$(X1)↖(-)$ ∧ X2 ∨ $(X1 ∨ X2)↖(-)$	$(X1)↖(-)$ ∧ X2 ∨ $(X1 ∨ X2)↖(-)$ ∨ X1
1	1	0	0	1	0	0	1
1	0	0	0	1	0	0	1
0	1	1	1	1	0	1	1
0	0	1	0	0	1	1	1

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

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

1. დისჯუნქციური ნორმალური ფორმა (DNF)- ცვლადებისაგან წარმოქმნილი პროდუქციის ჯამი და მათი უარყოფა ცრუ მნიშვნელობებისთვის.

DNF-ის აგების ალგორითმი შემდეგია:

1. ჭეშმარიტების ცხრილში ფუნქციები ირჩევენ არგუმენტების ერთობლიობას, რომლის ლოგიკური ფორმები უდრის 1-ს („true“);
2. ყველა შერჩეული ლოგიკური სიმრავლე იწერება, როგორც არგუმენტების ლოგიკური პროდუქტი, თანმიმდევრულად აკავშირებს მათ ერთმანეთთან ლოგიკური ჯამის (დისუნქციის) მოქმედების გამოყენებით;
3. არგუმენტებისთვის, რომლებიც მცდარია, ჩანაწერში ჩასმულია უარყოფის ოპერაცია.

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

X1	X2	F(X1, X2)
1	1	1
0	1	0
1	0	0
0	0	1

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

ჩვენ ვწერთ ამ სიმრავლების არგუმენტების ლოგიკურ პროდუქტებს, ვათავსებთ მათ ლოგიკურ ჯამს: X1 ∧ X2 ∨ X1 ∧ X2.

ჩვენ ვწერთ არგუმენტების უარყოფას შერჩეული სიმრავლეების, რომლებსაც აქვთ მცდარი მნიშვნელობა (ცხრილის მეოთხე მწკრივი; მეორე ნაკრები ფორმულაში; პირველი და მეორე ელემენტები): X1 ∧ X2 ∨ $(X1)↖(- )$ ∧ $(X2)↖(-)$.

პასუხი: F(X1, X2) = X1 ∧ X2 ∨ $(X1)↖(-)$ ∧ $(X2)↖(-)$.

2. შემაერთებელი ნორმალური ფორმა (CNF)- ცვლადებისაგან წარმოქმნილი ჯამების ნამრავლი და მათი უარყოფა ჭეშმარიტ მნიშვნელობებზე.

CNF-ის აგების ალგორითმი შემდეგია:

1. ჭეშმარიტების ცხრილში არგუმენტების კომპლექტები არჩეულია, რომელთა ლოგიკური ფორმები ტოლია 0-ის („მცდარი“);
2. ყველა შერჩეული ლოგიკური სიმრავლე, როგორც არგუმენტების ლოგიკური ჯამები, იწერება თანმიმდევრობით, აკავშირებს მათ ერთმანეთთან ლოგიკური პროდუქტის (შეერთების) მოქმედების გამოყენებით;
3. არგუმენტებისთვის, რომლებიც შეესაბამება სიმართლეს, შედგენილ ჩანაწერში შეიტანება უარყოფის ოპერაცია.

პრობლემის გადაჭრის მაგალითები

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

X1	X2	F(X1, X2)
1	1	1
0	1	0
1	0	0
0	0	1

გამოსავალი.ჩვენ ვირჩევთ არგუმენტების მნიშვნელობების კომპლექტს, რომლებშიც ფუნქცია 0-ის ტოლია. ეს არის მეორე და მესამე სტრიქონები (ნუმერაციისას არ ვითვალისწინებთ სათაურის ხაზს).

ჩვენ ვწერთ ამ სიმრავლეთა არგუმენტების ლოგიკურ ჯამებს, ვაკავშირებთ მათ ლოგიკურ ნამრავლთან: X1 ∨ X2 ∧ X1 ∨ X2.

ჩვენ ვწერთ არგუმენტების უარყოფას არჩეული სიმრავლეების, რომლებსაც აქვთ ნამდვილი მნიშვნელობა (ცხრილის მეორე რიგი, ფორმულის პირველი ნაკრები, მეორე ელემენტი; მესამე სტრიქონისთვის და ეს არის ფორმულის მეორე ნაკრები. , პირველი ელემენტი): X1 ∨ $(X2)↖(-)$ ∧ $( X1)↖(-)$ ∨ X2.

ამრიგად, მიღებულია CNF-ში ლოგიკური ფუნქციის ჩანაწერი.

პასუხი: X1 ∨ $(X2)↖(-)$ ∧ $(X1)↖(-)$ ∨ X2.

ორი მეთოდით მიღებული ფუნქციის მნიშვნელობები ექვივალენტურია. ამ განცხადების დასამტკიცებლად ვიყენებთ ლოგიკის წესებს: F(X1, X2) = X1 ∨ $(X2)↖(-)$ ∧ $(X1)↖(-)$ ∨ X2 = X1 ∧ $(X1)↖ (-)$ ∨ X1 ∧ X2 ∨ $(X2)↖(-)$ ∧ $(X1)↖(-)$ ∨ $(X2)↖(-)$ ∧ X2 = 0 ∨ X1 ∨ X2 ∨ $(X2 )↖(- )$ ∧ $(X1)↖(-)$ ∨ 0 = X1 ∧ X2 ∨ $(X1)↖(-)$ ∧ $(X2)↖(-)$.

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

საჭირო ფორმულა: X1 ∧ X2 ∨ $(X1)↖(-)$ ∧ X2 .

ის შეიძლება გამარტივდეს: X1 ∧ X2 ∨ $(X1)↖(-)$ ∧ X2 = X2 ∧ (X1 ∨ $(X1)↖(-)$) = X2 ∧ 1 = X2.

მაგალითი 3.მოცემული სიმართლის ცხრილისთვის შექმენით ლოგიკური ფუნქცია DNF მეთოდის გამოყენებით.

X1	X2	X3	F(X1, X2, X3)
1	1	1	1		X1 ∧ X2 ∧ X3
1	0	1	0
0	1	1	1		$(X1)↖(-)$ ∧ X2 ∧ X3
0	0	1	0
1	1	0	1		X1 ∧ X2 ∧ $(X3)↖(-)$
1	0	0	1		X1 ∧ $(X2)↖(-)$ ∧ $(X3)↖(-)$
0	1	0	0
0	0	0	0

საჭირო ფორმულა: X1 ∧ X2 ∧ X ∨ $(X1)↖(-)$ ∧ X2 ∧ X3 ∨ X1 ∧ X2 ∧ $(X3)↖(-)$ ∪ X1 ∧ $(X2)ↈ(-)$ $ (X3)↖(-)$.

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

X1 ∧ X2 ∧ X3 ∨ $(X1)↖(-)$ ∧ X2 ∧ X3 ∨ X1 ∧ X2 ∧ $(X3)↖(-)$ ∨ X1 ∧ $(X2)↖(-)(X3)$ ∧ $ ↖(-)$ = X2 ∧ X3 ∧ (X1 ∨ $(X1)↖(-)$) ∨ X1 ∧ $(X3)↖(-)$ ∧ (X2 ∨ $(X2)↖(-)$) = X2 ∧ X3 ∨ X1 ∧ $(X3)↖(-)$.

სიმართლის ცხრილები ლოგიკური პრობლემების გადასაჭრელად

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

პრობლემის გადაჭრის მაგალითები

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

გამოსავალი.ცხადია, ამოხსნის შედეგი იქნება ცხრილი, რომელშიც სასურველ ფუნქციას Y(X1, X2, X3) ექნება მნიშვნელობა „true“ თუ რომელიმე ორ ცვლადს აქვს მნიშვნელობა „true“.

X1	X2	X3	Y(X1, X2, X3)
1	1	1	0
1	1	0	1
1	0	1	1
1	0	0	0
0	1	1	1
0	1	0	0
0	0	1	0
0	0	0	0

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

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

	1 გაკვეთილი	გაკვეთილი 2	გაკვეთილი 3
ინფორმატიკა	1	1	0
მათემატიკა	1	0	1
ფიზიკა	0	1	1

ცხრილი აჩვენებს, რომ სასურველი გრაფიკის ორი ვარიანტია:

1. მათემატიკა, კომპიუტერული მეცნიერება, ფიზიკა;
2. კომპიუტერული მეცნიერება, ფიზიკა, მათემატიკა.

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

1. ბორისი უფროსია;
2. ჰოკეის მოთამაშეზე უმცროსი ფეხბურთელი;
3. ფეხბურთსა და ჰოკეის თამაშობენ და პიტერი ერთ სახლში ცხოვრობენ;
4. როდესაც მოთხილამურესა და ჩოგბურთელს შორის ჩხუბი წარმოიქმნება, ბორისი შეარიგებს მათ;
5. პიტერს არ შეუძლია ჩოგბურთის ან ბადმინტონის თამაში.

რა სპორტი უყვარს თითოეულ ბიჭს?

გამოსავალი.შევადგინოთ ცხრილი და ასახოთ მასში პრობლემის პირობები, შევავსოთ შესაბამისი უჯრები 0 და 1 რიცხვებით, იმისდა მიხედვით, მცდარია თუ ჭეშმარიტი შესაბამისი განცხადება.

ვინაიდან სპორტის ექვსი სახეობა არსებობს, გამოდის, რომ ყველა ბიჭი დაინტერესებულია სპორტის სხვადასხვა სახეობით.

მე-4 პირობიდან გამომდინარეობს, რომ ბორისს არ აინტერესებს თხილამურები ან ჩოგბურთი, ხოლო მე-3 და მე-5 პირობებიდან, რომ პიტერმა არ იცის ფეხბურთის, ჰოკეის, ჩოგბურთის და ბადმინტონის თამაში. შესაბამისად, პეტრეს საყვარელი სპორტი არის თხილამურები და ცურვა. მოდით ჩავდოთ ეს ცხრილში და შეავსოთ "თხილამურებით" და "ცურვის" სვეტების დარჩენილი უჯრები ნულებით.

ცხრილიდან ჩანს, რომ მხოლოდ ალექსის შეუძლია ჩოგბურთის თამაში.

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

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

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