На этом форуме отвечают на конкретные вопросы. Фраза «я не понимаю, как решать» — это не вопрос. На вопрос «как решить задачу №X» вас отошлют к материалам сайта kpolyakov.spb.ru. За бессвязный поток слов и неспособность формулировать свои мысли — бан.

Если у вас не сходится ответ на какую-то задачу, пожалуйста сразу представляйте свое «правильное» решение.

Для регистрации на форуме щелкните по ссылке «Вход-регистрация» вверху страницы. В открывшееся окошко «ник» введите свою фамилию на русском языке (например, Иванов). В окошко «пароль» введите придуманный вами пароль, состоящий из латинских букв и цифр. Поставьте галочку в окошке «зарегистрироваться, я новый участник» и нажмите кнопку «ОК».

АвторСообщение



Сообщение: 1
ссылка на сообщение  Отправлено: 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 есть ненулевые.
И какой вывод можно сделать относительно числа А?
Я считаю, что эта задача не имеет решения.

Спасибо: 0 
ПрофильЦитата Ответить
Ответов - 26 , стр: 1 2 All [только новые]


Администратор




Сообщение: 1059
ссылка на сообщение  Отправлено: 01.04.16 20:58. Заголовок: user123 пишет: у как..


user123 пишет:
 цитата:
у каких авторов еще встречаются разборы задач с использованием Ваших формул?

Нет знаю, пока не видел. :-)

 цитата:
существуют ли исключения, при которых Ваши формулы не работают?

Если вы о моей статье, на которую я ссылаюсь, там чётко указано, когда эти формулы работают.
 цитата:
на сколько можно быть уверенными, что на экзамене Ваши формулы сработают на 100%?

Если будут выполняться условия их применимости (будет именно та ситуация, при которой они выведены), то они сработают. Если я, конечно, нигде не ошибся. :-)

Но, как совершенно верно заметил предыдущий оратор, заучивать формулы в такой ситуации бессмысленно. Если задача немного изменится, они уже не подойдут. Так что это просто игра ума. Но тут есть и "сухой остаток" - наиболее интересно не то, какие формулы получились, а то, как они выводились. Если вы поймете и освоите методику, то сможете решить любую задачу.

___________________________________________________
Имей мужество пользоваться собственным умом. (И. Кант)
Спасибо: 0 
ПрофильЦитата Ответить



Сообщение: 2
ссылка на сообщение  Отправлено: 04.04.16 21:59. Заголовок: ege 18 №163


Добрый день! В указанном задании все-таки наименьшее число 5. Коллеги! Может, стоит перерешать пример? Спасибо за помощь в нашем нелегком труде))). Буду рада любым комментариям.

Спасибо: 0 
ПрофильЦитата Ответить



Сообщение: 1
ссылка на сообщение  Отправлено: 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.


Спасибо: 0 
ПрофильЦитата Ответить
Администратор




Сообщение: 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.



___________________________________________________
Имей мужество пользоваться собственным умом. (И. Кант)
Спасибо: 0 
ПрофильЦитата Ответить



Сообщение: 2
ссылка на сообщение  Отправлено: 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.
Почему? Это "дополнительное" слагаемое уже использовалось при преобразовании выражения...

Спасибо: 0 
ПрофильЦитата Ответить
Администратор




Сообщение: 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 выражение истинно.

Неверно.

___________________________________________________
Имей мужество пользоваться собственным умом. (И. Кант)
Спасибо: 0 
ПрофильЦитата Ответить



Сообщение: 3
ссылка на сообщение  Отправлено: 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.

Спасибо: 0 
ПрофильЦитата Ответить
Администратор




Сообщение: 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.

___________________________________________________
Имей мужество пользоваться собственным умом. (И. Кант)
Спасибо: 0 
ПрофильЦитата Ответить



Сообщение: 4
ссылка на сообщение  Отправлено: 05.04.16 10:48. Заголовок: Спасибо! Я и подозре..


Спасибо! Я и подозревала, что где-то я не так воспринимаю условие задачи. Будем теперь разбираться с учетом этого.

Спасибо: 0 
ПрофильЦитата Ответить



Сообщение: 3
ссылка на сообщение  Отправлено: 05.04.16 11:52. Заголовок: Спасибо большое за р..


Спасибо большое за разъяснение! При х=10 действительно 5 не подходит.

Спасибо: 0 
ПрофильЦитата Ответить
постоянный участник


Сообщение: 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, соответственно А и (А и черта сверху), тогда нет такого изобилия скобочек и решение получается достаточно компактным


Спасибо: 0 
ПрофильЦитата Ответить
Ответов - 26 , стр: 1 2 All [только новые]
Ответ:
1 2 3 4 5 6 7 8 9
видео с youtube.com картинка из интернета картинка с компьютера ссылка файл с компьютера русская клавиатура транслитератор  цитата  кавычки оффтопик свернутый текст

показывать это сообщение только модераторам
не делать ссылки активными
Имя, пароль:      зарегистрироваться    
Тему читают:
- участник сейчас на форуме
- участник вне форума
Все даты в формате GMT  3 час. Хитов сегодня: 84
Права: смайлы да, картинки да, шрифты нет, голосования нет
аватары да, автозамена ссылок вкл, премодерация откл, правка нет