We intend to solve Problem 211 from ege18.doc via Technique of calculating basic predicates developed by E.A. Mironchick in manuscript http://kpolyakov.spb.ru/download/mea18bit.pdf
Graphics using circles and a universal set in the original article allows you to implement alternative solutions quite effectively. The example below shows this very well. See also http://mapping-metod.blogspot.com/2017/08/bitwise2-18.html
for solution of same problem via Bitwise2.
See Problem 211 from ege18.doc itself
Determine the number of positive integers A such that ((x&17¬ = 0)=>((x&A¬ =0)=>(x&58¬ =0)))=>((x&8 = 0)^(x&A¬ = 0 )^(x&58 = 0)) is identically false (that is, it takes the value 0 for any natural value of the variable x)?
Original source of problem 211
(E(17) => (E(A) => E(58))) => (¬E(8)*E(A)*¬E(58)) = 0
¬(E(17) => (E(A) => E(58))) + (¬E(8)*E(A)*¬E(58)) = 0
(¬E(17) + ¬E(A) + E(58)) * ¬(¬E(8)*E(A)*¬E(58)) = 1
(¬E(17) + ¬E(A) + E(58)) * (E(8) + ¬E(A) + E(58)) = 1
Hence getting system
¬E(17) + ¬E(A) + E(58) = 1 (1)
E(8) + ¬E(A) + E(58) = 1 (2)
E(A) => E(58) + ¬E(17) = 1 (1)
E(A) => E(58) + E(8) = 1 (2)
(E(A) => E(58)) + (E(A) => ¬E(17)) = 1 (1)
(E(A) => E(58)) + (E(A) => E(8)) = 1 (2)
Thus A(max) = 58
Now we address the question been asked in the body of problem 211
via techique of calculating basic predicates
E(58) = E(32) + E(16) + E(8) + E(2)
1. E(2) defines 2
2. E(8) defines 8
3. E(2)⋃E(8) defines 10
4. E(16) defines 16
5. E(16)⋃E(2) defines 18
6. E(16)⋃E(8) defines 24
7. E(16)⋃E(8)⋃E(2) defines 26
8. E(32) defines 32
9. E(32)⋃E(2) defines 34
10.E(32)⋃E(8) defines 40
11.E(32)⋃E(8)⋃E(2) defines 42
12.E(32)⋃E(16) defines 48
13.E(32)⋃E(16)⋃E(2) defines 50
14.E(32)⋃E(16)⋃E(8) defines 56
15.E(32)⋃E(16)⋃E(8)⋃E(2) defines 58
Answer = {2,8.10,16,18,24,26,32,34,40,42,48,50,56,58}
Let us call number of combinations of n by m C(n,m)
Then we get C(4,1)+C(4,2)+C(4,3)+C(4,4) = 4+6+4+1 = 15
References
1. Множества в задачах с анализом битовых цепочек /Л.Л.Босова, Е.А. Мирончик//Информатика в школе /2017. No 7(130). С. 45-48.
No comments:
Post a Comment