Несмотря на то что булевы операции и операции с множествами - понятия разные, между ними действительно можно построить аналогию: операции И (AND) соответствует операция пересечения множеств, ИЛИ (OR) - объединение, ИСКЛЮЧАЮЩЕЕ ИЛИ (XOR) - симметрическая разность. Принцип построения соответствия следующий. Каждому элементу m из рассматриваемого универсального множества ставятся в соответствие 2 булевы величины X и Y: если m принадлежит множеству A, то X = 1, иначе 0. Если m принадлежит множеству B, то Y = 1, иначе 0. Тогда, пересечение множеств A и B будет состоять из таких и только таких элементов, у которых для соответствующих X и Y выполняется X AND Y = 1. Аналогично для других операций. В случае операции симметрической разности A и B результирующее множество будет состоять из всех элементов A, которых нет в B и из всех элементов B, которых нет в A. В приведенном примере множества A и B совпадают, поэтому их симметрическая разность равна пустому множеству. Аналогично, для двух совпадающих булевых переменных X XOR X = 0 тождественно. Никакого подвоха тут нет. Только операция симметрической разности обозначается не A\B, а A Δ B.
Формально можно уточнить условие "Импликация первой переменной и второй переменной равна дизъюнкции второй переменной и отрицания первой переменной". Но обычно в импликации подразумевалось, что из первой переменной следует вторая, как в порядке записи x=>y.
Для всех обновленных заданий и вопросов добавлено по +1 попытке. Дедлайны вопросов и заданий 10 недели перенесены до конца этой недели - 15 апреля 23:30, чтобы все имели возможность исправить ответы.
Вместе с тем прошу еще раз заняться вопросом № 4. Ранее в своем комментарии по этому вопросу я даже привел числовой пример. Обратите внимание - булевы функции от 0 переменных... таки существуют! Это - тождественные константы и таких функций будет всего 2. Переменных - 0, строчек в таблице истинности - 1.
Ваш предыдущий комментарий заставил меня отложить решение этого вопроса, хотя до этого я был вполне уверен в правильности ответа на него. И вот, представьте, вчера я вспомнил про нульарные функции... Не знаю, каким был "правильный" ответ до этого, но после обновления ответа нульарные функции, вероятно, просто не учитываются.
На мой взгляд, некорректно прокомментирован ответ на задание 10, о первой строке написано, о еще двух тоже, а ещё об одной ничего не известно, а ведь строк четыре!
здравствуйте, в 10 неделе курса , в 6 проверочном задании я поменяла местами варианты ответа, допустим не 6 7, а 7 6 и мне ответ не зачли , хотя варианты правильные, в задании не написан порядок вариантов ответов, еще вопрос, выполнила задания 10 недели, а прогресс поднялся только на 1 процент, это что за техническая неполадка?Заранее спасибо
Здесь, на форуме курса, уже ранее затрагивался вопрос с неоднозначностью записи ответа в некоторых случаях. И отвечали, что есть ограничения, связанные с возможностями этой платформы. Могу совершенно точно заявить, так как проходил здесь же и другие курсы, что платформа позволяет задавать и засчитывать различные варианты правильного ответа. Призываю технический персонал заняться этой проблемой в данном курсе поглубже.
По поводу процентов - за задания на весь курс (14 недель) всего выделено 30% итогового результата. С учетом того, что процент за каждую неделю плавает немного (зависит от баллов), 1% за 10-ю неделю вполне может быть.
К сожалению, пока знаю только про возможность засчитывать +1 вариант ответа. Вторую такую функцию ввести не получается. И пока сподручнее всё же прописывать условия так, чтобы формат представления ответа был единственным.
Но будем работать над улучшением качества. Многие тестовые задания можно представить в лучшей форме, чем они представлены сейчас.
Здравствуйте, юыть не может, когда я частично прошла курс было 48 процентов, а потом опять 44. Задания пройдены на 80 процентов вопросы на 70 и это 1 процент?
Неделя 11, вопрос 10. В этом вопросе нужно проверить зависимость между количеством ненулевых значений булевой функции от трёх переменных и количеством множителей в её СКНФ. При чем тут количество ненулевых строк таблицы истинности этой функции? Под нулевой строкой я подразумеваю f(0, 0, 0) = 0.
вопрос 3: "СДНФ булевой функции от трёх переменных содержит хотя бы одно слагаемое." Константа не является слагаемым наряду с переменной?
вопрос 7: " Для построения таблицы истинности достаточно вычислить значения булевой функции на всех наборах и расположить их в лексикографическом порядке." Из формулировки задания не ясно однозначно, что расположить - наборы или значения функции. Выходит, что следует вычислить значения булевой функции и расположить их в лексикографическом порядке.
вопрос 8: "В СДНФ булевой функции от трёх переменных хотя бы два слагаемых. Тогда в её СКНФ хотя бы два множителя. " Но если слагаемых и множителей вместе 8, то данное утверждение должно быть верно всегда, а не иногда, как утверждает ответ.
Поясните, пожалуйста, ситуацию по данным вопросам.
Вопрос 3. Есть теорема: "Любая булева формула, не являющаяся тождественно ложной, может быть приведена к СДНФ, причем единственным образом". С одной стороны, тождественная константа (0) действительно не является слагаемым наряду с конъюнктивным одночленом от переменных. С другой стороны, говоря в вопросе об "СДНФ булевой функции", тем самым автоматически отбирается лишь подмножество функций, по теореме СДНФ имеющих. Поэтому ответ в любом случае должен быть "Всегда верно".
Вопрос 8. Формализуем утверждения. Обозначим количество слагаемых - x, количество множителей - y. При условии, что функция отлична от тождественной константы 0 или 1, действительно справедливо x + y = 8. По условию, "в СДНФ хотя бы два слагаемых" <=> x >= 2. Тогда, почленно складывая
y = 8 - x
0 <= x - 2
получаем
у <= 6, т.е. это утверждение тождественно (эквивалентно) первой части (посылке) импликации вопроса.
Вторая часть (следствие) импликации ("в её СКНФ хотя бы два множителя") <=> у >= 2.
Возможное количество множителей в СКНФ булевой функции от трёх переменных 1 <= у <= 7, поэтому импликация истинна при 2 <= у <= 7 и ложна при у = 1. И ответ "Иногда верно" корректен.
Вопрос 3. Слагаемые СДНФ состоят только из произведений переменных x, y, z (возможно, с отрицаниями).
Вопрос 7. Формулировку можно уточнить: "расположить наборы в лексикографическом порядке"
Вопрос 8. Если в СДНФ хотя бы два слагаемых - значит, их количество может быть 2, 3, 4, 5, 6, 7 или 8. Затем посмотрите на сумму количества слагаемых и множителей.
Неделя 14. Из всех проверок свойств бинарных отношений, пожалуй, только определение транзитивности вызывает трудности. Например, есть множество M = {a, b, c, d, e}, матрица отношений R для такого множества выглядит так:
Свойство aij = 1 и ajk = 1 => aik = 1 – не выполняется. На графе нет петель, стрелки односторонние, транзитных маршрутов нет. Вроде бы как данное отношение не транзитивно. Однако, если умножим матрицу R на себя, то получим нулевую матрицу, и по выполненному свойству R2 ⊆ R отношение будет транзитивно(?).
Возьмем другой пример. Матрица отношений R множества N = {q, w, e, r, t} выглядит следующим образом:
Свойство aij = 1 и ajk = 1 => aik = 1 – не выполняется. На графе петли у каждой вершины (т.к. рефлексивно), одна односторонняя стрелка, транзитных маршрутов нет. R2 выглядит так:
Отношение не транзитивно, т.к. не выполняется свойство R2 ⊆ R. Однако, в ответе предполагается обратное.
Каким еще образом можно проверить, является ли отношение транзитивным, используя матрицу или граф этого отношения? Для множества из трех элементов все очевидно (определение есть и в курсе, и в литературе). Но если мощность множества больше 3, то как быть в этом случае? Должны ли все элементы удовлетворять xRy и yRz => xRz или достаточно рассмотреть подмножество? Надо ли рассматривать транзитивное замыкание?
Неделя 14: в 9 задании 71R67=1, 56R95=1, 55R95=1, все остальные отношения 0. На графе отсутствует транзитивный треугольник. В ответе указана транзитивность. Подскажите, пожалуйста, где неточность.
Здравствуйте, подскажите, пожалуйста, а вот такое преобразование верно или нет. Если верно, то по какому правилу это преобразование производится? Когда решала одну из задач в итоговом тесте, то хотела функцию упростить, чтобы легче было строить её таблицу истинности и не знаю, так можно упрощать или нет: z(не x) v y(не x) v y(не z) = (не x)z v y(не z)?
Несмотря на то что булевы операции и операции с множествами - понятия разные, между ними действительно можно построить аналогию: операции И (AND) соответствует операция пересечения множеств, ИЛИ (OR) - объединение, ИСКЛЮЧАЮЩЕЕ ИЛИ (XOR) - симметрическая разность. Принцип построения соответствия следующий. Каждому элементу m из рассматриваемого универсального множества ставятся в соответствие 2 булевы величины X и Y: если m принадлежит множеству A, то X = 1, иначе 0. Если m принадлежит множеству B, то Y = 1, иначе 0. Тогда, пересечение множеств A и B будет состоять из таких и только таких элементов, у которых для соответствующих X и Y выполняется X AND Y = 1. Аналогично для других операций. В случае операции симметрической разности A и B результирующее множество будет состоять из всех элементов A, которых нет в B и из всех элементов B, которых нет в A. В приведенном примере множества A и B совпадают, поэтому их симметрическая разность равна пустому множеству. Аналогично, для двух совпадающих булевых переменных X XOR X = 0 тождественно. Никакого подвоха тут нет. Только операция симметрической разности обозначается не A\B, а A Δ B.
В формулировке вопроса 10 действительно лучше написать XOR, это и имелось в виду.
10 неделя, 7 вопрос
импликация = not x1 or x2 , тоесть если x1, то x2
Но и верна также запись
импликация = x1 or not x2 , тоесть если x2, то x1
Корректен вариант ответа всегда верно ?
Формально можно уточнить условие "Импликация первой переменной и второй переменной равна дизъюнкции второй переменной и отрицания первой переменной". Но обычно в импликации подразумевалось, что из первой переменной следует вторая, как в порядке записи x=>y.
Уважаемые слушатели!
Для недели 10 внесены следующие правки:
Для всех обновленных заданий и вопросов добавлено по +1 попытке. Дедлайны вопросов и заданий 10 недели перенесены до конца этой недели - 15 апреля 23:30, чтобы все имели возможность исправить ответы.
С уважением, команда курса
Большое спасибо за проделанную работу!
Вместе с тем прошу еще раз заняться вопросом № 4. Ранее в своем комментарии по этому вопросу я даже привел числовой пример. Обратите внимание - булевы функции от 0 переменных... таки существуют! Это - тождественные константы и таких функций будет всего 2. Переменных - 0, строчек в таблице истинности - 1.
Ваш предыдущий комментарий заставил меня отложить решение этого вопроса, хотя до этого я был вполне уверен в правильности ответа на него. И вот, представьте, вчера я вспомнил про нульарные функции... Не знаю, каким был "правильный" ответ до этого, но после обновления ответа нульарные функции, вероятно, просто не учитываются.
Да, спасибо вам, этот крайний случай следует учесть.
Вопрос 4 - исправлены ответ и пояснение к нему. Добавлена +1 попытка.
На мой взгляд, некорректно прокомментирован ответ на задание 10, о первой строке написано, о еще двух тоже, а ещё об одной ничего не известно, а ведь строк четыре!
Да, согласен, неточность исправим. Имелось в виду "в первых двух строках".
Спасибо, пояснение к ответу исправлено!
здравствуйте, в 10 неделе курса , в 6 проверочном задании я поменяла местами варианты ответа, допустим не 6 7, а 7 6 и мне ответ не зачли , хотя варианты правильные, в задании не написан порядок вариантов ответов, еще вопрос, выполнила задания 10 недели, а прогресс поднялся только на 1 процент, это что за техническая неполадка?Заранее спасибо
Здесь, на форуме курса, уже ранее затрагивался вопрос с неоднозначностью записи ответа в некоторых случаях. И отвечали, что есть ограничения, связанные с возможностями этой платформы. Могу совершенно точно заявить, так как проходил здесь же и другие курсы, что платформа позволяет задавать и засчитывать различные варианты правильного ответа. Призываю технический персонал заняться этой проблемой в данном курсе поглубже.
По поводу процентов - за задания на весь курс (14 недель) всего выделено 30% итогового результата. С учетом того, что процент за каждую неделю плавает немного (зависит от баллов), 1% за 10-ю неделю вполне может быть.
Здравствуйте!
К сожалению, пока знаю только про возможность засчитывать +1 вариант ответа. Вторую такую функцию ввести не получается. И пока сподручнее всё же прописывать условия так, чтобы формат представления ответа был единственным.
Но будем работать над улучшением качества. Многие тестовые задания можно представить в лучшей форме, чем они представлены сейчас.
Посмотрите документацию, пожалуйста. Возможно, там найдутся необходимые сведения:
http://docs.lms.tpu.ru/projects/edx-partner-course-staff/ru/latest/exerc...
Спасибо, но я и так уже её изучаю :)
Она довольно обширна для того, чтобы все навыки сразу применить.
Здравствуйте, юыть не может, когда я частично прошла курс было 48 процентов, а потом опять 44. Задания пройдены на 80 процентов вопросы на 70 и это 1 процент?
Здравствуйте!
Добавила условие про то, что ответ нужно вводить в порядке возрастания. И увеличила количество попыток, чтобы Вы могли исправить своё решение.
Большое спасибо
Неделя 11, вопрос 10. В этом вопросе нужно проверить зависимость между количеством ненулевых значений булевой функции от трёх переменных и количеством множителей в её СКНФ. При чем тут количество ненулевых строк таблицы истинности этой функции? Под нулевой строкой я подразумеваю f(0, 0, 0) = 0.
День добрый.
Под нулевой строкой подразумевается строка, в которой f(x, y, z)=0, то есть строка с нулевым значением.
Добрый вечер!
Неделя 11
вопрос 3: "СДНФ булевой функции от трёх переменных содержит хотя бы одно слагаемое." Константа не является слагаемым наряду с переменной?
вопрос 7: " Для построения таблицы истинности достаточно вычислить значения булевой функции на всех наборах и расположить их в лексикографическом порядке." Из формулировки задания не ясно однозначно, что расположить - наборы или значения функции. Выходит, что следует вычислить значения булевой функции и расположить их в лексикографическом порядке.
вопрос 8: "В СДНФ булевой функции от трёх переменных хотя бы два слагаемых. Тогда в её СКНФ хотя бы два множителя. " Но если слагаемых и множителей вместе 8, то данное утверждение должно быть верно всегда, а не иногда, как утверждает ответ.
Поясните, пожалуйста, ситуацию по данным вопросам.
Вопрос 3. Есть теорема: "Любая булева формула, не являющаяся тождественно ложной, может быть приведена к СДНФ, причем единственным образом". С одной стороны, тождественная константа (0) действительно не является слагаемым наряду с конъюнктивным одночленом от переменных. С другой стороны, говоря в вопросе об "СДНФ булевой функции", тем самым автоматически отбирается лишь подмножество функций, по теореме СДНФ имеющих. Поэтому ответ в любом случае должен быть "Всегда верно".
Вопрос 8. Формализуем утверждения. Обозначим количество слагаемых - x, количество множителей - y. При условии, что функция отлична от тождественной константы 0 или 1, действительно справедливо x + y = 8. По условию, "в СДНФ хотя бы два слагаемых" <=> x >= 2. Тогда, почленно складывая
y = 8 - x
0 <= x - 2
получаем
у <= 6, т.е. это утверждение тождественно (эквивалентно) первой части (посылке) импликации вопроса.
Вторая часть (следствие) импликации ("в её СКНФ хотя бы два множителя") <=> у >= 2.
Возможное количество множителей в СКНФ булевой функции от трёх переменных 1 <= у <= 7, поэтому импликация истинна при 2 <= у <= 7 и ложна при у = 1. И ответ "Иногда верно" корректен.
Спасибо за подробные разъяснения. Теперь все встало на свои места)).
Здравствуйте! Передаю ответ от преподавателя:
Спасибо за внимательное прочтение вопросов.
Вопрос 3. Слагаемые СДНФ состоят только из произведений переменных x, y, z (возможно, с отрицаниями).
Вопрос 7. Формулировку можно уточнить: "расположить наборы в лексикографическом порядке"
Вопрос 8. Если в СДНФ хотя бы два слагаемых - значит, их количество может быть 2, 3, 4, 5, 6, 7 или 8. Затем посмотрите на сумму количества слагаемых и множителей.
Спасибо за ответ.
Неделя 13, вопрос 3. Функция линейна. Тогда она монотонна. Ожидается "Иногда верно" Но неверно, например, для x XOR y. Разве XOR монотонна?
Утверждение неверно для x XOR y из-за того, что x XOR y не монотонна.
Неделя 14, проверочное задание 1. Из перечисленных отношений для натуральных чисел выберите все рефлексивные.
Почему НОД(х,у) = 1 - рефлексивно? Если х = у, то НОД = х.
Здравствуйте!
В ответе ошибка. Исправили её и добавили пояснение к ответу.
Неделя 14. Из всех проверок свойств бинарных отношений, пожалуй, только определение транзитивности вызывает трудности. Например, есть множество M = {a, b, c, d, e}, матрица отношений R для такого множества выглядит так:
R = ( {
{0, 0, 0, 0, 1},
{0, 0, 0, 0, 0},
{0, 1, 0, 0, 0},
{0, 1, 0, 0, 0},
{0, 0, 0, 0, 0}
} )
Свойство aij = 1 и ajk = 1 => aik = 1 – не выполняется. На графе нет петель, стрелки односторонние, транзитных маршрутов нет. Вроде бы как данное отношение не транзитивно. Однако, если умножим матрицу R на себя, то получим нулевую матрицу, и по выполненному свойству R2 ⊆ R отношение будет транзитивно(?).
Возьмем другой пример. Матрица отношений R множества N = {q, w, e, r, t} выглядит следующим образом:
R = ( {
{1, 1, 0, 0, 0},
{0, 1, 0, 0, 0},
{0, 0, 1, 0, 0},
{0, 0, 0, 1, 0},
{0, 0, 0, 0, 1}
} )
Свойство aij = 1 и ajk = 1 => aik = 1 – не выполняется. На графе петли у каждой вершины (т.к. рефлексивно), одна односторонняя стрелка, транзитных маршрутов нет. R2 выглядит так:
R2 = ( {
{1, 2, 0, 0, 0},
{0, 1, 0, 0, 0},
{0, 0, 1, 0, 0},
{0, 0, 0, 1, 0},
{0, 0, 0, 0, 1}
} )
Отношение не транзитивно, т.к. не выполняется свойство R2 ⊆ R. Однако, в ответе предполагается обратное.
Каким еще образом можно проверить, является ли отношение транзитивным, используя матрицу или граф этого отношения? Для множества из трех элементов все очевидно (определение есть и в курсе, и в литературе). Но если мощность множества больше 3, то как быть в этом случае? Должны ли все элементы удовлетворять xRy и yRz => xRz или достаточно рассмотреть подмножество? Надо ли рассматривать транзитивное замыкание?
Неделя 14: в 9 задании 71R67=1, 56R95=1, 55R95=1, все остальные отношения 0. На графе отсутствует транзитивный треугольник. В ответе указана транзитивность. Подскажите, пожалуйста, где неточность.
Тоже самое касается 10-го задания: граф с петлями в вершинах, только 1 ориентированное ребро. В ответе указана транзитивность.
См. внимательно лекцию с 16:00
Уточнение к определению: eсли предпосылка не выполнена, то импликация верна.
Здравствуйте, подскажите, пожалуйста, а вот такое преобразование верно или нет. Если верно, то по какому правилу это преобразование производится? Когда решала одну из задач в итоговом тесте, то хотела функцию упростить, чтобы легче было строить её таблицу истинности и не знаю, так можно упрощать или нет: z(не x) v y(не x) v y(не z) = (не x)z v y(не z)?
Здравствуйте. Функции совпали, это несложно проверить.
Страницы