Автор | Сообщение |
|
Отправлено: 18.01.16 13:32. Заголовок: ege 18 №163
Добрый день! В № 163 обозначу P =(х&13= not 0) , Q = (x&39= not 0), A=(x&A = not 0). Выполню преобразования логического выражения: P*Q -> A*P = not(P*Q) + A*P = not P + not Q + A*P = not Q + not P + A =not(P*Q) + A = P*Q -> A Если P*Q =1 , то А =1, отсюда P=1, Q=1, A=1 13= 001101 39 =100111 Из того, что выражение х&13= not 0 истинно следует, что в числе Х среди битов с номерами 0, 2, 3 есть ненулевые. Из того, что выражение х&39= not 0 истинно следует, что в числе Х среди битов с номерами 0, 1, 2, 5 есть ненулевые. И какой вывод можно сделать относительно числа А? Я считаю, что эта задача не имеет решения.
|
|
|
Ответов - 26
, стр:
1
2
All
[только новые]
|
|
|
| Администратор
|
Сообщение: 971
|
|
Отправлено: 18.01.16 19:37. Заголовок: zvyagina пишет: И ка..
zvyagina пишет: цитата: | И какой вывод можно сделать относительно числа А? |
|
Оба условия выполняются одновременно. Поэтому точно выполняется x & 13 = 1. Поэтому минимальное значение A = 13 (минимальное из двух чисел).
|
|
|
|
Отправлено: 27.02.16 10:10. Заголовок: Это всегда так можно..
Это всегда так можно рассуждать???? если А = Q*P???? Потому что другого решения я не могу придумать, в этой задаче иначе нужно все числа перебирать....
|
|
|
|
| Администратор
|
Сообщение: 1008
|
|
Отправлено: 27.02.16 10:16. Заголовок: sooll20 пишет: Это в..
sooll20 пишет: цитата: | Это всегда так можно рассуждать???? если А = Q*P???? |
|
Для этого случая (P*Q->A) всегда выбираем минимальное из двух. Для других - рассуждаем в каждом конкретном случае. Универсального алгоритма я не знаю.
|
|
|
|
Отправлено: 19.03.16 01:27. Заголовок: 163
После упрощению получаю такое же уравнение, но не могу понять, почему берем в этом случае наименьшее из заданных чисел. Если составить таблицу истинности, получаю число 5. Если можно, поясните еще, не запоминать же этот случай. Спасибо!
|
|
|
|
| Администратор
|
Сообщение: 1035
|
|
Отправлено: 19.03.16 09:21. Заголовок: nika пишет: Если мож..
nika пишет: цитата: | Если можно, поясните еще, не запоминать же этот случай. |
|
Если есть желание серьезно разобраться в таких задачах, предлагаю почитать серьезный разбор всех случаев на сайте. Кстати, во многих случаях эта задача не имеет решений.
|
|
|
|
Отправлено: 19.03.16 09:25. Заголовок: День добрый! Побитов..
День добрый! Побитовая конъюнкция масок чисел 39 и 13 дает ответ 5. Минимальное число, которое дает P*Q= 1, является число 5. Почему получается в ответе число 13 и как объяснить это грамотно детям? В каких случаях мы используем конъюнкцию масок, а в каких просто берем минимальное из чисел? Не по данному заданию... В разборе Р-23 Вы брали исходные выражения как не равные нулю, почему? Ведь логичнее было брать равенство 0!
|
|
|
|
| Администратор
|
Сообщение: 1036
|
|
Отправлено: 19.03.16 09:32. Заголовок: alspay пишет: Почему..
alspay пишет: цитата: | Почему получается в ответе число 13 и как объяснить это грамотно детям? |
|
Читаем серьезный разбор всех случаев на сайте.
|
|
|
|
Отправлено: 19.03.16 11:05. Заголовок: Константин Юрьевич, ..
Константин Юрьевич, возник вопрос... Почему исходные выражения всегда берутся одинаковые - не равные нулю?
|
|
|
|
| Администратор
|
Сообщение: 1038
|
|
Отправлено: 19.03.16 11:10. Заголовок: alspay пишет: Почему..
alspay пишет: цитата: | Почему исходные выражения всегда берутся одинаковые - не равные нулю? |
|
Поясните, мне непонятен вопрос.
|
|
|
|
Отправлено: 19.03.16 11:26. Заголовок: (x & A = 0) -..
цитата: | (x & A = 0) -> ((x & 29 = 0) -> (x & 43 <> 0)) A(x) = (x & A <> 0) P(x) = (x & 29 <> 0) Q(x) = (x & 43 <> 0) |
| Почему мы не можем брать исходные выражения? A(x) = (x & A = 0) P(x) = (x & 29 = 0) Q(x) = (x & 43 <> 0) и работать уже с ними? Почему именно <>0? Легче для понимания =0.
|
|
|
|
| Администратор
|
Сообщение: 1039
|
|
Отправлено: 19.03.16 11:34. Заголовок: alspay пишет: Почему..
alspay пишет: цитата: | Почему именно <>0? Легче для понимания =0. |
|
Для меня логичнее, что выражение истинно, когда что-то не равно нулю. Это привычка из мира программирования. "Каждый пишет, как он дышит". Можно сделать и наоборот, результат от этого не изменится. :-)
|
|
|
|
|
Отправлено: 27.03.16 17:28. Заголовок: Константин Юрьевич, ..
Константин Юрьевич, понимаю, что достал глупыми вопросами, но остановиться не могу) В статье (статьях) Вы рассматриваете 2 случая (задачи) 1) А + В = 1 с поиском А минимального 2) неА + В = 1 с поиском А максимального почему не рассматриваются случаи А + В с поиском максимального и неА + В с поиском минимального? решений нет или бесконечно много? значит ли это, что на экзамене все задания сведутся к этим 2 вариантам?
|
|
|
|
| Администратор
|
Сообщение: 1050
|
|
Отправлено: 27.03.16 17:37. Заголовок: alspay пишет: А + В ..
alspay пишет: цитата: | А + В с поиском максимального и неА + В с поиском минимального? решений нет или бесконечно много? |
|
Там решение тривиальное. В задаче 1 (A+B=1) максимальное значение А совпадает с универсальным множеством. Аналогично в задаче неА+B=1 минимальное решение - пустое множество, так что неА совпадает с универсальным множеством. цитата: | значит ли это, что на экзамене все задания сведутся к этим 2 вариант |
|
Да. Другие задачи бессмысленны.
|
|
|
|
Отправлено: 01.04.16 12:00. Заголовок: День добрый! скажите..
День добрый! скажите, пожалуйста, у каких авторов еще встречаются разборы задач с использованием Ваших формул? существуют ли исключения, при которых Ваши формулы не работают? на сколько можно быть уверенными, что на экзамене Ваши формулы сработают на 100%?
|
|
|
|
Отправлено: 01.04.16 20:48. Заголовок: Формулы надо не зауч..
Формулы надо не заучивать, а разобраться и понять. Тогда видоизменение задач не будет пугать. Ну а использование в своих разборах методику, который предложил другой автор - это ПЛАГИАТ. Поэтому думаю, что солидный автор вряд ли будет строить разбор на методике, которая ему не принадлежит.
|
|
|
|
| Администратор
|
Сообщение: 1059
|
|
Отправлено: 01.04.16 20:58. Заголовок: user123 пишет: у как..
user123 пишет: цитата: | у каких авторов еще встречаются разборы задач с использованием Ваших формул? |
|
Нет знаю, пока не видел. :-) цитата: | существуют ли исключения, при которых Ваши формулы не работают? |
|
Если вы о моей статье, на которую я ссылаюсь, там чётко указано, когда эти формулы работают. цитата: | на сколько можно быть уверенными, что на экзамене Ваши формулы сработают на 100%? |
|
Если будут выполняться условия их применимости (будет именно та ситуация, при которой они выведены), то они сработают. Если я, конечно, нигде не ошибся. :-) Но, как совершенно верно заметил предыдущий оратор, заучивать формулы в такой ситуации бессмысленно. Если задача немного изменится, они уже не подойдут. Так что это просто игра ума. Но тут есть и "сухой остаток" - наиболее интересно не то, какие формулы получились, а то, как они выводились. Если вы поймете и освоите методику, то сможете решить любую задачу.
|
|
|
|
Отправлено: 04.04.16 21:59. Заголовок: ege 18 №163
Добрый день! В указанном задании все-таки наименьшее число 5. Коллеги! Может, стоит перерешать пример? Спасибо за помощь в нашем нелегком труде))). Буду рада любым комментариям.
|
|
|
|
Отправлено: 05.04.16 06:41. Заголовок: У меня также получае..
У меня также получается ответ 5, а на ответ 13 никак не могу выйти. Предлагаю свои рассуждения. Где ошибка или почему идут разногласия? ((X&13<>0) /\ (X&39<>0)) => ((X&A<>0) /\ (X&13<>0)) 1310=0011012 3910=1001112 Проанализируем это выражение для каждого варианта значения бита x: 0.0. Нулевой бит x=0 X&13<>0 = 0 (0&001101) X&39<>0 = 0 (0&100111) X&A<>0 = 0 (0&??????) ((X&13<>0) /\ (X&39<>0)) => ((X&A<>0) /\ (X&13<>0)) = 1 при любом значении нулевого бита A 0.1. Нулевой бит x=1 X&13<>0 = 1 (0&001101) X&39<>0 = 1 (0&100111) X&A<>0 = ? (0&??????) = значению бита A ((X&13<>0) /\ (X&39<>0)) => ((X&A<>0) /\ (X&13<>0)) = значению бита A Вывод: нулевой бит A должен быть равен 1. 1.0. Первый бит x=0 X&13<>0 = 0 (0&001101) X&39<>0 = 0 (0&100111) X&A<>0 = 0 (0&??????) ((X&13<>0) /\ (X&39<>0)) => ((X&A<>0) /\ (X&13<>0)) = 1 при любом значении первого бита A 1.1. Первый бит x=1 X&13<>0 = 0 (0&001101) X&39<>0 = 1 (0&100111) X&A<>0 = ? (0&??????) ((X&13<>0) /\ (X&39<>0)) => ((X&A<>0) /\ (X&13<>0)) = 1 при любом значении первого бита A 2.0. Второй бит x=0 X&13<>0 = 0 (0&001101) X&39<>0 = 0 (0&100111) X&A<>0 = 0 (0&??????) ((X&13<>0) /\ (X&39<>0)) => ((X&A<>0) /\ (X&13<>0)) = 1 при любом значении нулевого бита A 2.1. Второй бит x=1 X&13<>0 = 1 (0&001101) X&39<>0 = 1 (0&100111) X&A<>0 = ? (0&??????) = значению бита A ((X&13<>0) /\ (X&39<>0)) => ((X&A<>0) /\ (X&13<>0)) = значению бита A Вывод: второй бит A должен быть равен 1. 3.0. Третий бит x=0 X&13<>0 = 0 (0&001101) X&39<>0 = 0 (0&100111) X&A<>0 = 0 (0&??????) ((X&13<>0) /\ (X&39<>0)) => ((X&A<>0) /\ (X&13<>0)) = 1 при любом значении первого бита A 3.1. Третий бит x=1 X&13<>0 = 1 (0&001101) X&39<>0 = 0 (0&100111) X&A<>0 = ? (0&??????) ((X&13<>0) /\ (X&39<>0)) => ((X&A<>0) /\ (X&13<>0)) = 1 при любом значении первого бита A И т.д. - остальные бесспорные. А спор идет по поводу третьего бита: ответ 5 или 13. (510=1012 или 1310=11012). Я также считаю, что значение третьего бита может быть 0 (для случая наименьшего значения). А если я не права, то в чем отличие этого третьего бита от первого бита? Там также могут быть два варианта для бита А 0 или 1.
|
|
|
|
| Администратор
|
Сообщение: 1068
|
|
Отправлено: 05.04.16 07:42. Заголовок: Пушкина пишет: В ука..
Пушкина пишет: цитата: | В указанном задании все-таки наименьшее число 5. |
|
Контрпример - число 10. При выборе А=5 выражение ложно. Решение: 1. P = (X&13<>0), Q=(X&39<>0), A =(X&A<>0) 2. Выражение запишется в виде P* Q -> P* A 3. Упрощаем, преобразуем к виду Задачи 1: A + not P + not Q 4. Далее читаем тут про случай 3 Задачи 1. 5. Ответ: min(p,q) = 13.
|
|
|
|
Отправлено: 05.04.16 09:23. Заголовок: Контрпример
Пусть x=1010=10102 A=510=1012 1310=0011012 3910=1001112 Возьмем исходное выражение ((X&13<>0) /\ (X&39<>0)) => ((X&A<>0) /\ (X&13<>0)) X&13=1010&1101=1000 X&13<>0 = 1000 X&39<>0=1010&100111=000010 X&39<>0 = 10 (X&13<>0) /\ (X&39<>0) = 1000 /\ 10 = 0 X&A<>0=1010&101=0 X&A<>0 = 0 (X&A<>0) /\ (X&13<>0) = 0 /\ 1000 = 0 ((X&13<>0) /\ (X&39<>0)) => ((X&A<>0) /\ (X&13<>0)) = (1000 /\ 10 ) => (0 /\1000) = 0 => 0 = 1 Ваше, преобразованное выражение (проверяем для x=1010=10102) P*Q -> P*A P = (X&13<>0) = 1010&1101 = 1000 Q = (X&39<>0) = 1010&100111 = 10 A = (X&A<>0) = 1010&101 = 0 P*Q -> P*A = (1000)*(10) -> (1000)*(101) = 0 -> 0 = 1 Вывод: Для x=10 при A=5 выражение истинно. В чем же ошибка моего решения? Я своим ученикам объясняю такие задачи через побитовое решение (составляем таблицу с вариантами значений битов x и вычисления с учетом этого значения выражения). Посмотрела презентацию Филлипова В.И. Там на слайдах 11 и 12 рассмотрена аналогичная задача ((((X&A<>0) /\ (X&12=0)) => ((X&A=0) /\ (X&21<>0))) \/ ((X&21=0) /\ (X&12=0))) с табличным методом решения, похожим на мой. И все было бы хорошо, вывод у нас был одинаковый: "Из таблицы истинности, что искомое число А должно содержать двоичный разряд на второй, третьей и четвертой позиции. Поэтому искомое минимальное число 14". Но на следующем слайде зачем-то делается: "Обратим внимание на наличие в выражении дополнительного слагаемого: ((X & 21 = 0) /\ (X & 12 = 0))" - и делается другой вывод: "Из таблицы истинности, видно , что искомое число А может не содержать содержать двоичный разряд на второй позиции, так как данное слагаемое всегда истинно, если число Х содержит первую степень 2", т.е. результат вместо 14 заменяется на 2. Почему? Это "дополнительное" слагаемое уже использовалось при преобразовании выражения...
|
|
|
|
| Администратор
|
Сообщение: 1070
|
|
Отправлено: 05.04.16 09:33. Заголовок: mnk пишет: P*Q ->..
mnk пишет: цитата: | P*Q -> P*A = (1000)*(10) -> (1000)*(101) = 0 -> 0 = 1 |
|
Что это за умножения битов? Откуда Вы это взяли? Вы же сами пишете: цитата: | P = (X&13<>0) = 1010&1101 = 1000 Q = (X&39<>0) = 1010&100111 = 10 A = (X&A<>0) = 1010&101 = 0 |
|
то есть 1) P = 1 2) Q = 1 3) A = 0 Поэтому P*Q -> P*A = 1 -> 0 = 0. цитата: | Вывод: Для x=10 при A=5 выражение истинно. |
|
Неверно.
|
|
|
|
|
Отправлено: 05.04.16 10:24. Заголовок: Уточнение
Это разве не побитовые операции: P/\Q -> P/\A = ((1000)/\(10)) -> ((1000)/\(101)) = 0000 -> 0101 = 1111 ? Т.е. у меня проблема в понимании как в результате побитовой операции P = (X&13<>0) = 1010&1101 = 1000 получаем P=1.
|
|
|
|
| Администратор
|
Сообщение: 1071
|
|
Отправлено: 05.04.16 10:32. Заголовок: mnk пишет: Это разве..
mnk пишет: цитата: | Это разве не побитовые операции: P/\Q -> P/\A = ((1000)/\(10)) -> ((1000)/\(101)) = 0000 -> 0101 = 111 |
|
Ни в коем случае. Здесь P, Q, A - логические выражения, дальше просто идет логика. цитата: | как в результате побитовой операции P = (X&13<>0) = 1010&1101 = 1000 получаем P=1. |
|
У Вас получилось, что X&13<>0, поэтому логическое значение P = (X&13<>0) = True.
|
|
|
|
Отправлено: 05.04.16 10:48. Заголовок: Спасибо! Я и подозре..
Спасибо! Я и подозревала, что где-то я не так воспринимаю условие задачи. Будем теперь разбираться с учетом этого.
|
|
|
|
Отправлено: 05.04.16 11:52. Заголовок: Спасибо большое за р..
Спасибо большое за разъяснение! При х=10 действительно 5 не подходит.
|
|
|
|
| постоянный участник
|
Сообщение: 307
|
|
Отправлено: 06.04.16 10:29. Заголовок: Все приведенные зада..
Все приведенные задачи сводятся к задачам двух типов: 1. Найти наименьшее множество А, такое что В(х) + (X & A <> 0)=1, для любого х. №150 (X & 56 <> 0) -> ((X & 48 = 0) -> (X & A <> 0)) упрощаем до (X & 56 = 0) + (X & 48 <> 0) + (X & A <> 0)=1 раскладываем 56 и 48 по степеням 2 (X & 48 <> 0) равносильно (X & 32 <> 0) + (X & 16 <> 0) (X & 56 = 0) равносильно (X & 32 = 0)*(X & 16 = 0)*(X & 8 = 0) (X & 32 <> 0) + (X & 16 <> 0) + (X & 32 = 0)*(X & 16 = 0)*(X & 8 = 0) + (X & A <> 0)=1 Если (X & 32 <> 0)=1 или (X & 16 <> 0)=1 , то сумма 1, и от А ничего не зависит Если (X & 32 <> 0)=0, то (X & 32 = 0)=1 Если (X & 16 <> 0)=0 , то (X & 16 = 0)=1 Получаем (X & 8 = 0) + (X & A <> 0)=1, в А должны входить биты, делающие первое слагаемое ложным, т.е. А = 8 №162 (X & 29 <> 0) -> ((X & 9 = 0) -> (X & A <> 0)) упрощаем (X & 29 = 0) + (X & 9 <> 0) + (X & A <> 0)=1 Переходим к степеням 2 (X & 8 <> 0) + (X & 1 <> 0) + (X & 16 = 0)*(X & 8 = 0)*(X & 4 = 0)*(X & 1 = 0) + (X & A <> 0)=1 Или(после рассуждений аналогичных №150) (X & 16 = 0)*(X & 4 = 0) + (X & A <> 0)=1, у А единицы в 4 и 2 битах, А = 16+4 = 20 №166 (((X & 13 <> 0) + (X & A = 0)) -> (X & 13 <> 0)) + (X & A <> 0) + (X & 39 = 0) (X & 13 <> 0) + (X & 39 = 0)+ (X & A <> 0)=1 (X & 8 <>0) + (X & 4 <>0) + (X & 1 <>0) + (X & 32 = 0)*(X & 4 = 0)*(X & 2 = 0)*(X & 1 = 0) + (X & A <> 0)=1 Или (X & 8 <> 0)+ (X & 32 = 0)*(X & 2 = 0) + (X & A <> 0)=1 Рассмотрим отдельно сумму (X & 8 <> 0)+(X & A <> 0)=1 При разложении А по степеням 2, (X & 8 <> 0)+...+ (X & 16 <> 0)+ (X & 8 <> 0)+ (X & 4 <> 0)+(X & 2 <> 0)+ (X & 1 <> 0)=1 По правилу идемпотентности (X & 8 <> 0)+(X & A <> 0)= (X & A <> 0) В итоге (X & 32 = 0)*(X & 2 = 0) + (X & A <> 0)=1, у А единицы в 5 и 1 битах, А = 32+2 = 34 №163 ((X & 13 <> 0)*(X & 39 <>0)) -> ((X & A <> 0)*(X & 13 <>0)) (X & 13 = 0) + (X & 39 =0) + (X & A <> 0) =1 (X & 8 = 0)*(X & 4 = 0)*(X & 1 = 0) + (X & 32 =0)*(X & 4 = 0)*(X & 2 = 0)*(X & 1 = 0) + (X & A <> 0)=1 ((X & 8 = 0) + (X & 32 =0)*(X & 2= 0)) * (X & 4 = 0)*(X & 1 = 0) + (X & A <> 0) =1 1. у А в 0 и 2 битах единицы обязательны 2. обязательна единица в 3 или одновременно в 5 и 1 битах (если рассматривать их комбинации и возможные значения 0/1 для 4 бита, то получим все значения А, при которых исходное выражения истинно для любого х) Наименьшее А = 8+4+1 =13 Общее правило: В(х) включает в себя только конъюнкции вида: X & ... = 0. Если В(х) является произведением, то А - сумма соответствующих степеней 2. Если В(х) является суммой, то А наименьшая сумма соответствующих степеней 2 2. Найти наибольшее множество А, такое что В(х) + (X & A = 0)=1, для любого х. №159 (X & A <> 0) -> ((X & 14 = 0) -> (X & 75 <> 0)) или (X & A = 0) + (X & 14 <> 0) + (X & 75 <> 0)=1 (X & A = 0) + (X & 8<>0) + (X & 4<>0) + (X & 2<>0) + (X & 64<>0) + (X & 8<>0) + (X & 2<>0) + (X & 1<>0)=1 (X & A = 0) + (X & 64<>0) + (X & 8<>0) + (X & 4<>0) + (X & 2<>0) + (X & 1<>0)=1 A=64+8+4+2+1=79 №164 (((X & 13 <> 0) + (X & 39 = 0)) -> (X & 13 <>0)) + ((X & A = 0) * (X & 13 = 0)) или (X & A = 0) + (X & 13 <> 0) + (X & 39 <> 0)=1 (X & A=0)+(X & 8<>0)+(X & 4<>0)+(X & 1<>0)+(X & 32<>0)+(X & 4<>0)+(X & 2<>0)+(X & 1<>0)=1 (X & A=0)+(X & 32<>0)+(X & 8<>0)+(X & 4<>0)+(X & 2<>0)+(X & 1<>0)=1 А=32+8+4+2+1=47 №165 (((X & 13 <> 0) + (X & A <> 0)) -> (X & 13 <>0)) + ((X & A <> 0) * (X & 39 = 0)) или (X & A = 0) + (X & 13 <> 0) + (X & 39 = 0)=1 (X & A=0)+(X & 8<>0)+(X & 4<>0)+(X & 1<>0)+(X & 32=0)*(X & 4=0)*(X & 2=0)*(X & 1=0)=1 Необходимо найти наибольшее А, раскладываем А по степеням 2 и по правилу идемпотентности получаем: (X & 32=0)+...+(X & 32=0)*(X & 4=0)*(X & 2=0)*(X & 1=0) = (X & 32=0) * (1+(X & 4=0)*(X & 2=0)*(X & 1=0))+... Другими словами (X & A = 0) + (X & 39 = 0) = (X & A = 0) (X & A=0)+(X & 8<>0)+(X & 4<>0)+(X & 1<>0)=1 А=8+4+1=13 Общее правило: В(х) включает в себя только конъюнкции вида: X & ...<> 0, и А - сумма соответствующих степеней 2. решая подобным образом, мои дети стали меньше ошибаться в этом задании критика и комментарии приветствутся, в планах поэкспериментировать с заданиями 168-177 я использую запись (X & 8<>0) = (не 8) т.е. (8 и черта сверху) и (X & 39 = 0) - просто 39, соответственно А и (А и черта сверху), тогда нет такого изобилия скобочек и решение получается достаточно компактным
|
|
|
Ответов - 26
, стр:
1
2
All
[только новые]
|
|