Перечисленные статьи касаются применения Алгебры предикатов (логики 1- порядка) к задачам ЕГЭ Информатика, тем самым доводя идеи оригинальной работы
до достаточной полноты в контексте требований формальной логики к работе с множествами.
Это ни в коей мере не умаляет важности упомянутой статьи К.Ю. Полякова. В сущности, давшей толчок для разработок с применением Алгебры Предикатов. .
В обилии роликов выложенных в сети отсутствуют базовые понятия
теории множеств и их связь с математической логикой.
На мой взгляд, это делает ситуацию не более а как раз менее понятной,
чем в статье "Множества и логика в задачах ЕГЭ "
Отполированная Поляковым идея Здвижковой (Армавир),которая в свою очередь исходит из идеологии Полякова 2015 года исключительно продуктивна.
На мой взгляд Bitwise2.pdf являтся типично совместной работой.
Определение Z(k)={ x: x&k=0 } позволяет эффективно оперировать
алгеброй Z(k)-ых. В сочетании с идеей Здвижковой (стр 7,8 Bitwise2.pdf)
придают статье Bitwise2.pdf законченный характер.
Следуем
http://kpolyakov.spb.ru/download/inf-2015-10.pdf
Обозначим через D[N] множество натуральных чисел, для которых побитовая конъюнкция с числом N дает ненулевое значение
D[N] = {x: x & N != 0}
Введем множества : D(N) = (x ∈ D[N])), A = (x ∈ D[A]).
Исходная постановка :-
(x&120 != 0) => ((x&96! =0) => (x&A !=0))
Преобразуем исходное выражение,используя свойство импликации
A => B= ┐A v B
D(120) => (D(96) => A) = D(120) => (┐D(96) v A) = ┐D(120) v ┐D(96) v A
Последнее приводит к базовой задаче 1 смотри inf-2015-10.pdf, где
B = ┐D(120) v ┐D(96)
Следовательно,
D(A(min)) = ┐(┐D(120) v ┐D(96) = D(120)^D(96)
Множество D(120) определяется условием среди битов (6,5,4,3) есть ненулевые,считая крайний правый бит номером 0.
Множесто D(96) определяется условием среди битов (6,5) есть ненулевые,считая крайний правый бит номером 0.
Следовательно D(120)^D(96) определяется свойством среди битов (6,5) есть ненулевые. Для всех чисел из D(120)^D(96) найдется число А имеющие "1" в битах 6 и 5 такое что x&A != 0
Откуда следует A(min)=1100000 (binary) = 96 (decimal)
*****************************************************************************************
Решение той же задачи техникой
http://kpolyakov.spb.ru/download/bitwise2.pdf В этой работе метод существенно продвинут и формализован с точки зрения математической строгости.
*****************************************************************************************
Определим :
Z(k) = {x : x&k =0} ┐Z(k) = {x : x&k != 0}
¬Z(120) => ( ¬Z(96) => ¬A)
Z(120) + Z(96)
+ ¬A
Конвертиртируем в импликацию ( по утверждению 8 ) получим :-
A => ( Z(120) + Z(96)) =(A =>Z(120)) + (A => Z(96)) =1
A(min) = 96 утверждение 9 стр. 4 из bitwise2.pdf
***********************
Решая задачу
***********************
(x&120 != 0) => ((x&96 =0) => (x&A !=0))
D(120) => (┐D(96) => A) = D(120) => (D(96) v A) = ┐D(120) v D(96) v A
Получим D(A(min)) = ┐(┐D(120) v D(96)) = D(120)^┐D(96)
То есть 6 и 5 бит должны быть 0. Биты {4,3} содержат хотя бы одну 1.
Откуда A(min) = 11000 (binary) = 24 (decimal)
******************************************************************************************
Решение той же задачи техникой
http://kpolyakov.spb.ru/download/bitwise2.pdf
******************************************************************************************
¬Z(120) => ( Z(96) => ¬A)
Z(120) + ¬Z(96) + ¬A
Z(96) A => Z(120)
Z (96 or a) => Z(120)
Добавляем к 96 недостающие биты
120 =1111000
96 =1100000 => 11
11000
A(min) = 11000 (binary) = 24 (decimal)
******************************************************************************************
Введём выражение M & K, обозначающее поразрядную конъюнкцию M и K
(логическое «И» между соответствующими битами двоичной записи).
Определите наименьшее натуральное число А, такое что выражение
(x & 30 = 0)v((x & 57 = 0) => (x & A ≠ 0))
тождественно истинно (то есть принимает значение 1 при любом
натуральном значении переменной x)?
*******************************************************************************************
┐D(30)v(┐D(57) => A )
┐D(30)v(D(57)vA)
┐D(30)vD(57)vA
************************************
Применяем базовую задачу 1
***********************************
D(A(min)) = ┐(┐D(30)vD(57))
D(A(min)) = (D(30)^ ┐D(57))
57 = 111001 => ┐D(57) характеризуется тем, что {5,4,3,0} все равны 0
30 = 011110 => D(30) характеризуется тем, что из битов {4,3,2,1} хотя бы один
был равен 1
(D(30)^ ┐D(57)) требует,чтобы биты 5,4,3 все были равны 0.
Таким образом, нападающие (jeopardizing) {x} могут иметь
во втором и первом битах 01,10,11
Следовательно, A(min)=110 = 6 (decimal)
******************************************
Теперь, используя технику Bitwise2
******************************************
Z(30)+(Z(57) => ┐A) = 1
Z(30) + (┐Z(57) + ┐A) = 1
┐(Z(57)A) + z(30) = 1
(Z(57)A) => Z(30) = 1
57 = 111001
30 = 011
110
Следовательно (cтр.7 строка 1
http://kpolyakov.spb.ru/download/bitwise2.pdf )
А(min) =110 (binary) = 6 (decimal)
Сравни с
https://www.google.ru/url?sa=t&rct=j&q=&esrc=s&source=web&cd=10&ved=0ahUKEwikp6XmpKXVAhXlQJoKHUilBMwQFghmMAk&url=http%3A%2F%2Fpedagog.mosreg.ru%2Fmedia%2Fdownload%2FF157B6C1C2301B5A3966F829DA205CF2&usg=AFQjCNHwCKtQyR7vbsnRYTFCEkyEHELoyw&cad=rjt
стр. 10,11 ( классический подход)
*****************************
Задачи на делимость
*****************************
D[N] - множество чисел, делящихся на N
D(N) ={ x : x ∈ D[n]) A = { x: x ∈ D(A)}
******************************
Сайт К.Ю. Полякова
******************************
(№ 371) Обозначим через ДЕЛ(n, m) утверждение «натуральное
число n делится без остатка на натуральное число m».
Для какого наименьшего натурального числа А формула
ДЕЛ(x,А) → (¬ДЕЛ(x,21) ∨ ДЕЛ(x,35))
A => ( ¬D(21) v D(35 )
¬A v ¬D(21) v D(35)
Согласно базовой задаче 2
A(min) = ¬D(21) v D(35) =
¬(D(21)^¬D(35))
Либо
¬(A^ D(21)) v D(35)
A^D(21) => D(35)
Следовательно, А(min) = 5
(№ 370) Обозначим через ДЕЛ(n, m) утверждение
«натуральное число n делится без остатка на натуральное число m».
Для какого наибольшего натурального числа А формула
¬ДЕЛ(x,А) → (ДЕЛ(x,6) → ¬ДЕЛ(x,4))
тождественно истинна для всех х
A v (¬D(6) v ¬D(4))
Согласно базовой задаче 1
A(max) = ¬(¬D(6) v ¬D(4)) = D(6)^D(4)
Следовательно, А(max) = 12
Следующее сравнение
С другой стороны используем элементы теории множеств по Полякову
D(18) => (┐A => ┐D(12))
┐D(18) v (A v ┐D(12))
A v ( ┐D(18) v ┐D(12))
******************************************************
Условия соответствуют базовой Теореме 1
******************************************************
А = ┐(┐D(18) v ┐D(12)) = D(18)^D(12)
Ответ: A(min) = 36
Следующие примеры из новостной ленты ВКонтакте
(A^D(12) =>(D(42)v┐D(12))
┐Av┐D(12)vD(42)v┐D(12) = ┐Av┐D(12)vD(42) = ┐(A^D(12)vD(42) =
(A^D(12)) => D(42)
Что означает - если число делится на А и на 12 то оно должно делится
и на 42. Следовательно, A(min) = 7
(D(40) v D(64)) => A
┐(D(40) v D(64))) v A
A v (┐D(40)^┐D(64))
*****************************************************
Условия соответствуют базовой Теореме 1
****************************************************
A(max) =
┐(┐D(40)^┐D(64)) = (D(40) v D(64))
A(max) = НОД(40,64) = 8
************************************************************************
Относительно сложный пример с побитовой конъюнкцией
************************************************************************
Обозначим через D[N] множество натуральных чисел, для которых побитовая конъюнкция с числом N дает ненулевое значение
D[N] = {x: x & N != 0}
Введем множества : D(N) = (x ∈ D[N])), A = (x ∈ D[A]).
***************************************************************
Найти наименьшее А , что для любого х :-
***************************************************************
((x&28 != 0)v(x&45!=0)) => ((x&17=0) => (x&A != 0))
Конвертируем уравнение к принятому синтаксису ( по Полякову)
(D(28)vD(45)) => ( ┐D(17) => A)
(┐D(28) ^ ┐D(45))v(D(17) v A) = A v (D(17)v ((┐D(28) ^ ┐D(45)))
***********************************************
Условия соответствуют базовой Теореме 1
************************************************
D(A(min)) = ┐(D(17) v ((┐D(28) ^ ┐D(45)))
D(A(min)) = ┐D(17) ^ ┐((┐D(28) ^ ┐D(45))
D(A(min)) = ┐D(17) ^ ( D(28)vD(45))
45 = 101101 (binary) (1)
28 = 11100 (binary) (2)
17 = 10001 (binary) (3)
From (1) {5,3,2,0} bits have at least one bit equal 1
From (2) {4,3,2} bits have at least one bit equal 1
From (3) {4,0} bits are both 0
Таким образом , {5,3,2,} bits have at least one bit equal 1
Тогда A(min) = 2^5 + 2^3 + 2^2 = 44
Это гарантирует , что для любого x ∈ D(A(min)) = ┐D(17) ^ ( D(28) v D(45))
побитовая конъюнкция x&A != 0
******************************************************************************************
Решение той же задачи техникой
http://kpolyakov.spb.ru/download/bitwise2.pdf
******************************************************************************************
(┐Z(28) + ┐Z(25)) => (Z(17) => ┐A) =
Z(28)Z(45)
+ ┐Z(17)
+ ┐A =
Z(28)Z(45)
+ ┐(Z(17)A) =
(Z(17)A) => Z(28)Z(45)
Z(17 or a) => Z(28)Z(45)
Побитная дизъюнкция 28 и 45
45 = 101101 (binary)
v
28 = 011100 (binary)
----------------------
61 = 111101
Недостающие биты в 17
61 =
11
1101
17 = 010001
=>{5,3,2 }
Согласно утверждению 2 статьи bitwise2.pdf
A(min) =
10
1100 = 2^5 + 2^3 +2^2 =44 (decimal)
***************************************************************
Найти наибольшее А , что для любого х :-
***************************************************************
(x&A !=0) => ((x&37=0) =>(x&6 !=0))
┐Av( ┐D(37) => (x&6 != 0))
┐Av( D(37)vD(6) )
***************************************************
Условия соответствуют базовой Теореме 2
***************************************************
D(A(max)) = D(37)vD(6)
37 = 100101 (binary)
6 = 110 (binary)
A(max) есть побитовая дизъюнкция 100011 и 110
A(max) = 100111 = 2^5 + 2^2 + 2^1 + 1 = 32 + 4 +2 +1 = 39
********************
Альтернативно
********************
┐A => (Z(37) => ┐Z(6)) =1
┐A => (┐Z(37) + ┐Z(6)) = 1
A + ┐Z(37) + ┐Z(6) = 1
┐((Z(37)Z(6)) + A = 1
Z(37)Z(6) => A = 1
37 = 100101
v
6 = 000110
-----------------
39 = 100111
A(max) = 2^5 + 2^2 +2^1 + 1 = 32 + 4 + 2 + 1 = 39
Метод существенно продвинут и формализован с точки зрения математической строгости и формулировки алгоритмов в полностью
законченной форме в работе 2016 года
http://kpolyakov.spb.ru/download/bitwise2.pdf
*********************************************************************************
Решение примера 5 (А.Г. Гильдин) отличное от предложенного в
оригинальной статье
********************************************************************************
(x&19 = 0)^(x&38 !=0) v ((x&43 =0) => ((x&A =0) ^(x&43 =0))) = 1
Z(19) ^ ┐Z(38) + (Z(43) => A ^ Z(43))
Z(19) ^ ┐Z(38) + (Z(43) => A) ^ (Z(43) => Z(43))
Z(19) ^ ┐Z(38) + (Z(43) => A)
Z(19) ^ ┐Z(38) + ┐Z(43) + A
z(43) => ( A + Z(19) ^ ┐Z(38))
((z(43) => A ) + (Z(43) => Z(19) ^ ┐Z(38))
Z(43) => A is True due to (Z(43) => Z(19) ^ ┐Z(38)) is False
Thus A(max) = 43
Рассмотрим примеры, которых либо нет в последней статье
либо они содержат другие данные. Это не суть. Просто демонстрация
метода и ничего более того. Раньше или позже они появятся на VK's
news wire. Примеры взяты из
http://информатика23.рф/
Z(k) = {x : x&k =0} ┐Z(k) = {x : x&k != 0}
(x&26) v ( x&13) => ((x&78 != 0) =>(x&A = 0))
(Z(26) + Z(13)) => ( ┐Z(78) => A )
Z(26&13) => (Z(78) + A)
26 = 11010
&
13 = 01101
Получаем 1000(binary) = 8 (decimal)
Z(8) => (Z(78) + A) = (Z(8) => Z(78)) + (Z(8) => A)
Ответ: A(max) = 8
(x&A !=0) => ((x&56 = 0) => (x&20 != 0)
┐A => (Z(56) => ┐Z(20))
┐A => ( ┐Z(56)
+ ┐Z(20))
A
+ ┐Z(56)
+ ┐Z(20)
┐( ┐Z(56)
+ ┐Z(20)) => A
Z(56)Z(20) => A
Побитная дизъюнкция
56 = 111000
v
20 = 010100
-----------------------------
60 = 111100
Овет: A(max) = 60
((x&13 !=0) ^ (x&39 !=0)) => ((x&A !=0) ^ (x&13 != 0)
(┐Z(13) ^ ┐Z(39)) =>(┐A ^ ┐Z(13))
Z(13) + Z(39)
+ ┐A ^ ┐Z(13) =
Z(13) + ┐A ^ ┐Z(13) + Z(39)
*****************************************************************************
Используем
(A1 v B1) & (A1 v C1) = A1 v (B1 & C1)
Z(13) =A1 , ┐A=B1, ┐Z(13)=C1
Следовательно,
Z(13) + ┐A&┐Z(13) = (Z(13) + ┐A) & (Z(13) + ┐Z(13)) = (Z(13) + ┐A)
*****************************************************************************
(Z(13)
+ ┐A)^(Z(13)
+ ┐Z(13)) + Z(39) = (Z(13)
+ ┐A)^1 + Z(39)
(Z(13)
+ ┐A) + Z(39) = ┐A + Z(13) + Z(39) = A => Z(13) + Z(39)
(A => Z(13)) + (A => Z(39))
Ответ: A(min) = 13
****************************************************************************
На мой взгляд одни из наиболее сложных примеров в Информатика23.рф.
Решения нет в оригинальном документе ( в Bitwise2.pdf решение 165 есть,
виноват 01.08.17 )
Информатика23.рф задача 165,163 (детальный разбор)
****************************************************************************
Определите наибольшее натуральное число A, такое что выражение
(X & 56 <> 0) -> ((X & 24 <> 0) -> (X & A <> 0))
тождественно истинно (то есть принимает значение 1 при
любом натуральном значении переменной X)? (Сборник Евич задача 18)
Конвертируем к Z(k) - ым
┐Z(56) => ((┐Z(24) => ┐A)
┐Z(56) => (Z(24) + ┐A)
Z(56) + Z(24) + ┐A
A => (Z(24) + Z(56))
(A => Z(24)) + (A => Z(56))
Thus A(max) = 56
*******************************************
Another sample
with line segments :-
*******************************************
https://vk.com/informatics_100?z=video-40390768_456239963%2F9c2fa5c518b46912ba%2Fpl_wall_-40390768
Wouldn't the rest to be a fair enough, that Set Theory and Boolean Algebra
do work in concert as noticed here
http://kpolyakov.spb.ru/download/inf-2015-10.pdf
P => ((Q^┐A) => ┐P) = 1
P => ((┐QvA)v┐P) = 1
┐Pv ((┐QvA)v┐P) = 1
┐QvAv┐P = 1
Thus condition of Base Theorem 1 from
http://kpolyakov.spb.ru/download/inf-2015-10.pdf are satisfied :-
A(min) = ┐(┐Qv┐P) = Q^P = [150,171]
Answer is 21
References
1.
http://kpolyakov.spb.ru/download/bitwise2.pdf
2.
http://информатика23.рф/
3.
https://vk.com/doc274136_438160388?hash=73a282e68021a356fd&dl=e038bf74bee1c54811
