1)დაასაბუთეთ, რომ ყველაფერი, რაც მოიცემა and, or და not ოპერაციებით შეიძლებას მოიცეს მხოლოდ and და not ოპერაციებით (ან მხოლოდ or და not ოპერაციებით). მითითება: not (A and B) = (not A) or (not B). აქედან: (A and B) = not ((not A) or (not B)).
მითითებაში წერია ყველაფერი:
A and B = not((notA) or (notB))
A or B = not((notA) and (notB))
2)თვითონ ამოცანა ადვილია, მთავარია იცოდე რას ნიშნავს ∃x და ∀x.
∃x ნიშნავს: არსებობს x, რომლისთვისაც.....
∀x ნიშნავს: ყოველი x-ისთვის....
მაგალითად,
∀x≠ 0 ∃y. (x*y = 1) ნიჭნავს: ყოველი x-ისთვის, რომელიც არ უდრის 0-ს, არსებობს ისეთი y, რომ x*y = 1 ჭეშმარიტია.
3) დაწერეთ წინა ამოცანაში მოცემული მტკიცებების უარყოფა. -- lol whut?
4)კონტრმაგალითის მოყვანით აჩვენეთ, რომ (∀x∃y. P(x,y)) → ∀z P(z,z). არ არის სამართლიანი.
დავუშვათ, P(a,b) ჭეშმარიტია, როცა a + b = 0. მაშინ ყოველი x-ისთვის არსებობს შესაბამისი y (-x-ის ტოლი), მაგრამ ყოველი z-ისთვის z + z = 0 არაა ჭეშმარიტი.
5) ა) არის თუ არა სამართლიანი შემდეგი მტკიცება: ∃x∀y.P(x,y) → ∀y∃x.P(x,y)
ბ) არის თუ არა სამართლიანი შებრუნებული მტკიცება: ∃x∀y.P(x,y) ← ∀y∃x.P(x,y)
ა) სამართლიანია. წარმოიდგინეთ ვერტიკალური ხაზი საკოორდინატო სიბრტყეზე.
ბ)არაა სამართლიანი. წარმოიდგინეთ დახრილი ხაზი საკოორდინატო სიბრტყეზე.
6)გოიმობაა, დავიკიდოთ :)
problem 5.7
გვაქვს არაუარყოფითი მთელი რიცხვების სიმრავლე N და მისი ყველა ქვესიმრავლის სიმრავლე - P(N) - და ამ უკანასკნელის ყველა ქვესიმრავლის სიმრავლე - P(P(N)) - და ასე შემდეგ. ყველა ასეთი სიმრავლის გაერთიანება იყოს U. ჩვენ უნდა დავამტკიცოთ, რომ U მკაცრად დიდია მასში შემავალ ნებისმიერ ქვესიმრავლეზე (ეგ წერია, ოღონდ რთულად).
დავუშვათ, არის U-ს რაღაც ქვესიმრავლე P^n(N) სახის (ხარისხად n ნიშნავს რომ n-ჯერაა N-იდან ყველა ქვესიმრავლის სიმრავლე აღებული, ანუ P^n(N) = P(P.....P(N)) სადაც P n-ჯერ წერია), რომელიც არაა U-ზე მკაცრად ნაკლები. ჩვენ ვიცით, რომ P^(n+1)(N) მკაცრად დიდია P^n(N) (პირობაშიც წერია და თეორემაც გვაქვს შესაბამისი). ასევე ვიცით, რომ P^(n+1)(N) შედის U-ში. გამოდის, რომ U შეიცავს უფრო მეტ ქვესიმრავლეს, ვიდრე P^n(N).
problem 5.10
[N →{1, 2, 3}] იყოს ყველა იმ sequence-ის (ქართულად თუ იცით როგორაა, მითხარით) სიმრავლე, რომლებიც იწერებიან 1-ით, 2-ით და 3-ით. დაამტკიცეთ, რომ ეს სიმრავლე უთვლადია.
დავუშვათ საწინააღმდეგო. მაშინ შემიძლია ჩამოვწერო ყველა ეს სიმრავლე სიის სახით:
მითითებაში წერია ყველაფერი:
A and B = not((notA) or (notB))
A or B = not((notA) and (notB))
2)თვითონ ამოცანა ადვილია, მთავარია იცოდე რას ნიშნავს ∃x და ∀x.
∃x ნიშნავს: არსებობს x, რომლისთვისაც.....
∀x ნიშნავს: ყოველი x-ისთვის....
მაგალითად,
∀x≠ 0 ∃y. (x*y = 1) ნიჭნავს: ყოველი x-ისთვის, რომელიც არ უდრის 0-ს, არსებობს ისეთი y, რომ x*y = 1 ჭეშმარიტია.
3) დაწერეთ წინა ამოცანაში მოცემული მტკიცებების უარყოფა. -- lol whut?
4)კონტრმაგალითის მოყვანით აჩვენეთ, რომ (∀x∃y. P(x,y)) → ∀z P(z,z). არ არის სამართლიანი.
დავუშვათ, P(a,b) ჭეშმარიტია, როცა a + b = 0. მაშინ ყოველი x-ისთვის არსებობს შესაბამისი y (-x-ის ტოლი), მაგრამ ყოველი z-ისთვის z + z = 0 არაა ჭეშმარიტი.
5) ა) არის თუ არა სამართლიანი შემდეგი მტკიცება: ∃x∀y.P(x,y) → ∀y∃x.P(x,y)
ბ) არის თუ არა სამართლიანი შებრუნებული მტკიცება: ∃x∀y.P(x,y) ← ∀y∃x.P(x,y)
ა) სამართლიანია. წარმოიდგინეთ ვერტიკალური ხაზი საკოორდინატო სიბრტყეზე.
ბ)არაა სამართლიანი. წარმოიდგინეთ დახრილი ხაზი საკოორდინატო სიბრტყეზე.
6)გოიმობაა, დავიკიდოთ :)
problem 5.7
გვაქვს არაუარყოფითი მთელი რიცხვების სიმრავლე N და მისი ყველა ქვესიმრავლის სიმრავლე - P(N) - და ამ უკანასკნელის ყველა ქვესიმრავლის სიმრავლე - P(P(N)) - და ასე შემდეგ. ყველა ასეთი სიმრავლის გაერთიანება იყოს U. ჩვენ უნდა დავამტკიცოთ, რომ U მკაცრად დიდია მასში შემავალ ნებისმიერ ქვესიმრავლეზე (ეგ წერია, ოღონდ რთულად).
დავუშვათ, არის U-ს რაღაც ქვესიმრავლე P^n(N) სახის (ხარისხად n ნიშნავს რომ n-ჯერაა N-იდან ყველა ქვესიმრავლის სიმრავლე აღებული, ანუ P^n(N) = P(P.....P(N)) სადაც P n-ჯერ წერია), რომელიც არაა U-ზე მკაცრად ნაკლები. ჩვენ ვიცით, რომ P^(n+1)(N) მკაცრად დიდია P^n(N) (პირობაშიც წერია და თეორემაც გვაქვს შესაბამისი). ასევე ვიცით, რომ P^(n+1)(N) შედის U-ში. გამოდის, რომ U შეიცავს უფრო მეტ ქვესიმრავლეს, ვიდრე P^n(N).
problem 5.10
[N →{1, 2, 3}] იყოს ყველა იმ sequence-ის (ქართულად თუ იცით როგორაა, მითხარით) სიმრავლე, რომლებიც იწერებიან 1-ით, 2-ით და 3-ით. დაამტკიცეთ, რომ ეს სიმრავლე უთვლადია.
დავუშვათ საწინააღმდეგო. მაშინ შემიძლია ჩამოვწერო ყველა ეს სიმრავლე სიის სახით:
(1, 1, 1, 1...),
(2, 2, 2, 2...),
(3, 2, 1, 3...).
და ასე შემდეგ. ახლა უნდა ვიპოვოთ ისეთი რიცხვთა sequence, რომელიც ამ სიაში არ გვაქვს, რაც მოგვცემს წინააღმდეგობას.
ამ რიცხვთა sequence-ში, პირველი წევრი არ უნდა უდრიდეს პირველ სტრიქონის პირველ წევრს, რაც იმას ნიშნავს, რომ ჩვენი ახალი sequence პირველ სტრიქონში დაწერილი არაა.
მეორე წევრი არ უნდა უდრიდეს მეორე სტრიქონში მყოფი sequence-ის მეორე წევრს, რაც ანალოგიურად იმას ნიშნავს, რომ ახალი sequence და მეორე სტრიქონში მყოფი სხვადასხვაა.
მე-n-ე წევრი არ უნდა უდრიდეს მე-n-ე სტრიქონის მე-n-ე ელემენტს და ა.შ.
მივიღებთ ახალ სიმრავლეს, რომელიც არც ერთ სტრიქონში არ გვიწერია, ანუ sequence-ები სრულყოფილად არ დაგვითვლია - ეს ერთი (მაინც) გამოგვრჩა.
No comments:
Post a Comment