Сколько различных решений имеют уравнения информатика 10 класс

РАЗОБРАННЫЕ ПРИМЕРЫ ЗАДАЧ:

Решение. Все “сомножители”2 имеют форму xf=xi+1, они должны быть равны 1. Это значит, что любые два соседних бита должны быть равны. Существует всего две таких цепочки:

Ответ: два решения.

Задача 2. Сколько различных решений имеет система уравнений
(x1 ˅ x2) ˄ ((x1 ˄ x2) → x3) = 1
(x2 ˅ x3) ˄ ((x2 ˄ x3) → x4) = 1
(x3 ˅ x4) ˄ ((x3 ˄ x4) → x5) = 1
(x4 ˅ x5) ˄ ((x4 ˄ x5) → x6) = 1
(x5 ˅ x6) ˄ ((x5 ˄ x6) → x7) = 1
(x6 ˅ x7) ˄ ((x6 ˄ x7) → x8) = 1
(x7 ˅ x8) = 1
где x1,x2,…,x8 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.

Решение:
Решим систему с помощью битовых цепочек. Битовая цепочка — это набор единиц и нулей для переменных x1. x8, при которых система будет истинна.

Цепочки строятся по определенным правилам, которые можно вывести из системы. Рассмотрим первое уравнение:

(x1 ˅ x2) ˄ ((x1 ˄ x2) → x3) = 1

Для получения истины выражение (x1 ˅ x2) обязательно должно быть истинно, то есть в уравнении не может быть двух подряд идущих нулей.

Кроме этого, выражение ((x1 ˄ x2) → x3) тоже должно быть истинно. Ложным оно будет в том случае, если x1 и x2 будет равны 1, а x3 — 0. То есть после двух подряд идущих единиц не может быть нуля.

Каждое следующее уравнение связано с предыдущим:

(x1 ˅ x2) ˄ ((x1 ˄ x2) → x3) = 1
(x2 ˅ x3) ˄ ((x2 ˄ x3) → x4) = 1

То есть два правила, которые мы вывели, применяются не только к каждому уравнению, но и ко всей цепочке.

Первая очевидная цепочка для набора иксов — все единицы:

Рассмотрим цепочки, в которых может быть только один нуль. По правилу нуля не может быть после двух единиц:

x1 1 0 1
x2 1 1 0
x3 1 1 1
x4 1 1 1
x5 1 1 1
x6 1 1 1
x7 1 1 1
x8 1 1 1

Рассмотрим цепочки с двумя нулями. По правилу два нуля не могут находиться рядом:

x1 1 0 1 0 1
x2 1 1 0 1 0
x3 1 1 1 0 1
x4 1 1 1 1 0
x5 1 1 1 1 1
x6 1 1 1 1 1
x7 1 1 1 1 1
x8 1 1 1 1 1

Построим оставшиеся цепочки:

x1 1 0 1 0 1 0 1 0 1
x2 1 1 0 1 0 1 0 1 0
x3 1 1 1 0 1 0 1 0 1
x4 1 1 1 1 0 1 0 1 0
x5 1 1 1 1 1 0 1 0 1
x6 1 1 1 1 1 1 0 1 0
x7 1 1 1 1 1 1 1 0 1
x8 1 1 1 1 1 1 1 1 0

Получается, что для данной системы существует 9 различных решений.

Задание: Сколько различных решений имеет система уравнений
((x1 ˄ x2) ˅ (¬x1 ˄ ¬x2)) → ((x3 ˄ x4) ˅ (¬x3 ˄ ¬x4)) = 1
((x3 ˄ x4) ˅ (¬x3 ˄ ¬x4)) → ((x5 ˄ x6) ˅ (¬x5 ˄ ¬x6)) = 1
((x5 ˄ x6) ˅ (¬x5 ˄ ¬x6)) → ((x7 ˄ x8) ˅ (¬x7 ˄ ¬x8)) = 1
((x7 ˄ x8) ˅ (¬x7 ˄ ¬x8)) → ((x9 ˄ x10) ˅ (¬x9 ˄ ¬x10)) = 1
где x1,x2,…,x10 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.

Для начала давайте рассмотрим одну из частей нашей системы:

Данное выражение будет истинно, если переменные x1 и x2 будут одновременно равны либо единице, либо нулю, что, фактически, совпадает с таблицей истинности для эквиваленции (тождества). То есть мы его можем записать так:

Упростим так всю нашу систему:
(x1 ≡ x2) → (x3 ≡ x4) = 1
(x3 ≡ x4) → (x5 ≡ x6) = 1
(x5 ≡ x6) → (x7 ≡ x8) = 1
(x7 ≡ x8) → (x9 ≡ x10) = 1

Теперь все стало проще. Обратите внимание, что каждая часть следования вполне самостоятельна, например (x1 ≡ x2) никак не связана переменными с (x3 ≡ x4). То есть мы можем упростить нашу систему еще раз:

A → B = 1
B → C = 1
C → D = 1
D → E = 1

Теперь давайте найдем все возможные комбинации переменных А-Е для этой системы. В импликации (следовании) ложь может быть только в одном случае, если первое выражение истинно, а второе — ложно. То есть при построении цепочек мы должны избежать комбинации 1,0:

A | 1 | 0 | 0 | 0 | 0 | 0
B | 1 | 1 | 0 | 0 | 0 | 0
C | 1 | 1 | 1 | 0 | 0 | 0
D | 1 | 1 | 1 | 1 | 0 | 0
E | 1 | 1 | 1 | 1 | 1 | 0

Переменные A-E в основной системе являются эквиваленцией, то есть на каждую истину или ложь принимают по два различных варианта. То есть для каждого столбца в нашей таблице предусмотрено 25 = 32 варианта.

Например, первый столбец — 1 1 1 1 1, то есть в каждое тождество системы должно давать 1, а это возможно в двух вариантах иксов: 0 ≡ 0 или 1 ≡ 1, то есть на каждую единицу таблицы приходится два варианта. То же самое и с нулями.

Всего в таблице у нас получилось 6 различных цепочек, каждая принимает по 32 варианта, то есть общее количество комбинаций: 6*32=192 комбинации.

Видео:Урок 27. Логические уравнения. ИКТ 10 класс по ПоляковуСкачать

Задача №23. Решение систем логических уравнений.

Решение систем логических уравнений методом замены переменных

Метод замены переменных применяется, если некоторые переменные входят в состав уравнений только в виде конкретного выражения, и никак иначе. Тогда это выражение можно обозначить новой переменной.

Сколь­ко су­ще­ству­ет раз­лич­ных на­бо­ров зна­че­ний ло­ги­че­ских пе­ре­мен­ных x1, х2, х3, х4, х5, х6, х7, х8, ко­то­рые удо­вле­тво­ря­ют всем пе­ре­чис­лен­ным ниже усло­ви­ям?

(x1 → х2) → (х3→ х4) = 1

(х3 → х4) → (х5 → х6) = 1

(х5 → х6) → (х7 → х8) = 1

В от­ве­те не нужно пе­ре­чис­лять все раз­лич­ные на­бо­ры зна­че­ний пе­ре­мен­ных x1, х2, х3, х4, х5, х6, х7, х8, при ко­то­рых вы­пол­не­на дан­ная си­сте­ма ра­венств. В ка­че­стве от­ве­та Вам нужно ука­зать ко­ли­че­ство таких на­бо­ров.

Сде­ла­ем за­ме­ну пе­ре­мен­ных:

(x1 → х2) = y1; (х3 → х4) = y2; (х5 → х6) = y3; (х7 → х8) = y4.

Тогда можно за­пи­сать си­сте­му в виде од­но­го урав­не­ния:

(y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) = 1. Конъюнкция равна 1 (истинна), когда каждый операнд принимает значение 1. Т.е. каждая из импликаций должна быть истинна, а это выполняется при всех значениях, кроме (1 → 0). Т.е. в таблице значений переменных y1, y2, y3, y4 единица не должна стоять левее нуля:

Т.е. условия выполняются для 5 наборов y1-y4.

Т.к. y1 = x1 → x2, то значение y1 = 0 достигается на единственном наборе x1, x2: (1, 0), а значение y1 = 1 – на трех наборах x1, x2: (0,0) , (0,1), (1,1). Аналогично для y2, y3, y4.

Поскольку каждый набор (x1,x2) для переменной y1 сочетается с каждым набором (x3,x4) для переменной y2 и т.д., то количества наборов переменных x перемножаются:

Кол-во наборов на x1…x8

Сло­жим ко­ли­че­ство наборов: 1 + 3 + 9 + 27 + 81 = 121.

Сколько существует различных наборов значений логических переменных x1, x2, . x9, y1, y2, . y9, которые удовлетворяют всем перечисленным ниже условиям?

В ответе не нужно перечислять все различные наборы значений переменных x1, x2, . x9, y1, y2, . y9, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.

Сде­ла­ем за­ме­ну пе­ре­мен­ных:

(x1 ≡ y1) = z1, (x2 ≡ y2) = z2,…. ,(x9 ≡ y9) = z9

Систему можно записать в виде одного уравнения:

(¬ z1 ≡ z2) ∧ (¬ z2 ≡ z3) ∧ …..∧ (¬ z8 ≡ z9)

Эквивалентность истинна, только если оба операнда равны. Решениями этого уравнения будут два набора:

Т.к. zi = (xi ≡ yi), то значению zi = 0 соответствуют два набора (xi,yi): (0,1) и (1,0), а значению zi = 1 — два набора (xi,yi): (0,0) и (1,1).

Тогда первому набору z1, z2,…, z9 соответствует 2 9 наборов (x1,y1), (x2,y2),…, (x9,y9).

Столько же соответствует второму набору z1, z2,…, z9. Тогда всего 2 9 +2 9 = 1024 наборов.

Решение систем логических уравнений методом визуального определения рекурсии.

Этот метод применяется, если система уравнений достаточно проста и порядок увеличения количества наборов при добавлении переменных очевиден.

Сколь­ко раз­лич­ных ре­ше­ний имеет си­сте­ма урав­не­ний

где x1, x2, … x10 — ло­ги­че­ские пе­ре­мен­ные?

В от­ве­те не нужно пе­ре­чис­лять все раз­лич­ные на­бо­ры зна­че­ний x1, x2, … x10, при ко­то­рых вы­пол­не­на дан­ная си­сте­ма ра­венств. В ка­че­стве от­ве­та Вам нужно ука­зать ко­ли­че­ство таких на­бо­ров.

Решим первое уравнение. Дизъюнкция равна 1, если хотя бы один из ее операндов равен 1. Т.е. решениями являются наборы:

Для x1=0 существуют два значения x2 ( 0 и 1), а для x1=1 только одно значение x2 (1), такие, что набор (x1,x2) является решением уравнения. Всего 3 набора.

Добавим переменную x3 и рассмотрим второе уравнение. Оно аналогично первому, значит для x2=0 существуют два значения x3 ( 0 и 1), а для x2=1 только одно значение x3 (1), такие, что набор (x2,x3) является решением уравнения. Всего 4 набора.

Несложно заметить, что при добавлении очередной переменной добавляется один набор. Т.е. рекурсивная формула количества наборов на (i+1) переменных:

N_i+1 = N_i + 1. Тогда для десяти переменных получим 11 наборов.

Решение систем логических уравнений различного типа

Сколь­ко су­ще­ству­ет раз­лич­ных на­бо­ров зна­че­ний ло­ги­че­ских пе­ре­мен­ных x₁, . x₄, y₁. y₄, z₁. z₄, ко­то­рые удо­вле­тво­ря­ют всем пе­ре­чис­лен­ным ниже усло­ви­ям?

В от­ве­те не нужно пе­ре­чис­лять все раз­лич­ные на­бо­ры зна­че­ний пе­ре­мен­ных x₁, . x₄, y₁, . y₄, z₁, . z₄, при ко­то­рых вы­пол­не­на дан­ная си­сте­ма ра­венств.

В ка­че­стве от­ве­та Вам нужно ука­зать ко­ли­че­ство таких на­бо­ров.

Заметим, что три уравнения системы одинаковы на различных независимых наборах переменных.

Рассмотрим первое уравнение. Конъюнкция истинна (равна 1) только тогда, когда все ее операнды истинны (равны 1). Импликация равна 1 на всех наборах, кроме (1,0). Значит, решением первого уравнения будут такие наборы x1, x2, x3, x4, в которых 1 не стоит левее 0 (5 наборов):

Видео:Сколько решений имеет логическое уравнение: (A импликация В) ИЛИ (C импликация D). ЕГЭ(информатика)Скачать

Урок №6 Решение логических уравнений (10 класс)

Обращаем Ваше внимание, что в соответствии с Федеральным законом N 273-ФЗ «Об образовании в Российской Федерации» в организациях, осуществляющих образовательную деятельность, организовывается обучение и воспитание обучающихся с ОВЗ как совместно с другими обучающимися, так и в отдельных классах или группах.

Выберите документ из архива для просмотра:

Выбранный для просмотра документ Урок 6 Решение логических уравнений.doc

Тема урока: Решение логических уравнений

Образовательная – изучение способов решения логических уравнений, формирование умений и навыков решения логических уравнений и построения логического выражения по таблице истинности;

Развивающая — создать условия для развития познавательного интереса учащихся, способствовать развитию памяти, внимания, логического мышления;

Воспитательная : способствовать воспитанию умения выслушивать мнение других, воспитание воли и настойчивости для достижения конечных результатов.

Тип урока: комбинированный урок

Оборудование: компьютер, мультимедийный проектор, презентация 6.

Повторение и актуализацию опорных знаний. Проверка домашнего задания (10 минут)

На предыдущих уроках мы познакомились с основными законами алгебры логики, научились использовать эти законы для упрощения логических выражений.

Выполним проверку домашнего задания по упрощению логических выражений:

1. Какое из приведенных слов удовлетворяет логическому условию:

(первая буква согласная→вторая буква согласная) ٨ (последняя буква гласная → предпоследняя буква гласная)? Если таких слов несколько, укажите наименьшее из них.

1) АННА 2) МАРИЯ 3) ОЛЕГ 4) СТЕПАН

А – первая буква согласная

В – вторая буква согласная

С – последняя буква гласная

D – предпоследняя буква гласная

Составим выражение:

2. Укажите, какое логическое выражение равносильно выражению

Упростим запись исходного выражения и предложенных вариантов:

3. Дан фрагмент таблицы истинности выражения F:

Какое выражение соответствует F?

Определим значения этих выражений при указанных значениях аргументов:

Ознакомление с темой урока, изложение нового материала (30 минут)

Мы продолжаем изучать основы логики и тема нашего сегодняшнего урока «Решение логических уравнений». Изучив данную тему, вы узнаете основные способы решения логических уравнений, получите навыки решения этих уравнений путем использования языка алгебры логики и умения составления логического выражения по таблице истинности.

1. Решить логическое уравнение

Ответ запишите в виде строки из четырех символов: значений переменных K, L, M и N (в указанном порядке). Так, например, строка 1101 соответствует тому, что K=1, L=1, M=0, N=1.

Преобразуем выражение (¬K  M) → (¬L  M  N)

Выражение ложно, когда оба слагаемые ложны. Второе слагаемое равно 0, если M =0, N =0, L =1. В первом слагаемом K =0, так как М=0, а .

2. Сколько решений имеет уравнение (в ответе укажите только число)?

Решение: преобразуем выражение

A + B =1 и C + D =1

2 способ: составление таблицы истинности

3 способ: построение СДНФ – совершенной дизъюнктивной нормальной формы для функции – дизъюнкции полных правильных элементарных конъюнкций.

Преобразуем исходное выражение, раскроем скобки для того, чтобы получить дизъюнкцию конъюнкций:

Дополним конъюнкции до полных конъюнкций (произведение всех аргументов), раскроем скобки:

Учтем одинаковые конъюнкции:

В итоге получаем СДНФ, содержащую 9 конъюнкций. Следовательно, таблица истинности для данной функции имеет значение 1 на 9 строках из 2 4 =16 наборов значений переменных.

3. Сколько решений имеет уравнение (в ответе укажите только число)?

,

3 способ: построение СДНФ

Учтем одинаковые конъюнкции:

1

В итоге получаем СДНФ, содержащую 5 конъюнкций. Следовательно таблица истинности для данной функции имеет значение 1 на 5 строках из 2 4 =16 наборов значений переменных.

Построение логического выражения по таблице истинности:

для каждой строки таблицы истинности, содержащей 1 составляем произведение аргументов, причем, переменные, равные 0, входят в произведение с отрицанием, а переменные, равные 1 – без отрицания. Искомое выражение F будет составляется из суммы полученных произведений. Затем, если возможно, это выражение необходимо упростить.

Пример: дана таблица истинности выражения. Построить логическое выражение.

3. Задание на дом (5 минут)

Сколько решений имеет уравнение (в ответе укажите только число)?

По заданной таблице истинности составить логическое выражение и

Выбранный для просмотра документ Урок 6 Решение логических уравнений.ppt

Описание презентации по отдельным слайдам:

Проверка домашнего задания: Какое из приведенных слов удовлетворяет логическому условию: (первая буква согласная→вторая буква согласная) ٨ (последняя буква гласная → предпоследняя буква гласная)? Если таких слов несколько, укажите наименьшее. 1) АННА 2) МАРИЯ 3) ОЛЕГ 4) СТЕПАН 2. Укажите, какое логическое выражение равносильно выражению 3. Дан фрагмент таблицы истинности выражения F: Какое выражение соответствует F? xyzF 0001 0111 1100

Тема урока: Решение логических уравнений

1. Решить логическое уравнение (¬K  M) → (¬L  M  N) =0 Ответ запишите в виде строки из четырех символов: значений переменных K, L, M и N (в указанном порядке). Так, например, строка 1101 соответствует тому, что K=1, L=1, M=0, N=1.

3. Сколько решений имеет уравнение (в ответе укажите только число)? 1 способ: рассуждения Ответ: 9 2 способ: составление таблицы истинности ABCD АВСDA+BC+DF

3 способ: построение СДНФ – совершенной дизъюнктивной нормальной формы для функции – дизъюнкции полных конъюнкций. Преобразуем исходное выражение, раскроем скобки для того, чтобы получить дизъюнкцию конъюнкций: (A+B)*(C+D)=A*C+B*C+A*D+B*D= Дополним конъюнкции до полных конъюнкций (произведение всех аргументов), раскроем скобки:

4. Сколько решений имеет уравнение (в ответе укажите только число)?

Построение логического выражения по таблице истинности: для каждой строки таблицы истинности, содержащей 1 составляем произведение аргументов, причем, переменные, равные 0, входят в произведение с отрицанием, а переменные, равные 1 – без отрицания. Искомое выражение F будет составляется из суммы полученных произведений. Затем, если возможно, это выражение необходимо упростить. Пример: дана таблица истинности выражения. Построить логическое выражение. аbcF 0000 0010 0100 0110 1001 1011 1101 1110

Задание на дом: По заданной таблице истинности составить логическое выражение и упростить его. 2. Решить уравнение: 3. Сколько решений имеет уравнение? аbcF 0000 0010 0100 0111 1001 1011 1100 1111

Курс повышения квалификации

Дистанционное обучение как современный формат преподавания

• Сейчас обучается 925 человек из 80 регионов

Курс повышения квалификации

Педагогическая деятельность в контексте профессионального стандарта педагога и ФГОС

• Курс добавлен 23.11.2021
• Сейчас обучается 35 человек из 23 регионов

Курс повышения квалификации

Инструменты онлайн-обучения на примере программ Zoom, Skype, Microsoft Teams, Bandicam

• Курс добавлен 31.01.2022
• Сейчас обучается 24 человека из 14 регионов

Ищем педагогов в команду «Инфоурок»

Видео:Сколько решений имеет лог. уравнение (!(A *B) + C) IMP (!A * !B + D) = 1. Информатика, ЕГЭ, логикаСкачать

Дистанционные курсы для педагогов

«Взбодрись! Нейрогимнастика для успешной учёбы и комфортной жизни»

Свидетельство и скидка на обучение каждому участнику

Найдите материал к любому уроку, указав свой предмет (категорию), класс, учебник и тему:

5 576 021 материал в базе

Материал подходит для УМК

«Информатика (углублённый уровень) (в 2 частях)», Семакин И.Г., Шеина Т.Ю., Шестакова Л.В.

1.6.2. Логические формулы и функции

Самые массовые международные дистанционные

Школьные Инфоконкурсы 2022

33 конкурса для учеников 1–11 классов и дошкольников от проекта «Инфоурок»

Другие материалы

• 12.11.2017
• 1998
• 237

• 12.11.2017
• 707
• 1

• 12.11.2017
• 274
• 0

• 12.11.2017
• 977
• 8

• 12.11.2017
• 972
• 0

• 12.11.2017
• 376
• 0

• 12.11.2017
• 705
• 0

• 12.11.2017
• 792
• 0

Вам будут интересны эти курсы:

Оставьте свой комментарий

Авторизуйтесь, чтобы задавать вопросы.

Добавить в избранное

• 12.11.2017 16095
• RAR 112.9 кбайт
• 269 скачиваний
• Рейтинг: 5 из 5
• Оцените материал:

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

Если Вы считаете, что материал нарушает авторские права либо по каким-то другим причинам должен быть удален с сайта, Вы можете оставить жалобу на материал.

Автор материала

• На сайте: 4 года и 10 месяцев
• Подписчики: 0
• Всего просмотров: 95896
• Всего материалов: 15

Московский институт профессиональной
переподготовки и повышения
квалификации педагогов

Видео:Информатика 10 класс (Урок№12 - Преобразование логических выражений.)Скачать

Дистанционные курсы
для педагогов

663 курса от 690 рублей

Выбрать курс со скидкой

Выдаём документы
установленного образца!

Учителя о ЕГЭ: секреты успешной подготовки

Время чтения: 11 минут

Приемная кампания в вузах начнется 20 июня

Время чтения: 1 минута

Тринадцатилетняя школьница из Индии разработала приложение против буллинга

Время чтения: 1 минута

Полный перевод школ на дистанционное обучение не планируется

Время чтения: 1 минута

Инфоурок стал резидентом Сколково

Время чтения: 2 минуты

Онлайн-конференция о создании школьных служб примирения

Время чтения: 3 минуты

Рособрнадзор не планирует переносить досрочный период ЕГЭ

Время чтения: 0 минут

Подарочные сертификаты

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

Все материалы, размещенные на сайте, созданы авторами сайта либо размещены пользователями сайта и представлены на сайте исключительно для ознакомления. Авторские права на материалы принадлежат их законным авторам. Частичное или полное копирование материалов сайта без письменного разрешения администрации сайта запрещено! Мнение администрации может не совпадать с точкой зрения авторов.

🌟 Видео

Информатика 10 класс. Алгебра логики (УМК БОСОВА Л.Л., БОСОВА А.Ю.)Скачать

КАК РЕШАТЬ СИСТЕМЫ ЛОГИЧЕСКИХ УРАВНЕНИЙ. ЕГЭ по информатике. Задание 23Скачать

Информатика 10 класс (Урок№11 - Алгебра логики. Таблицы истинности.)Скачать

23 задание Информатика ЕГЭ Система логических уравнений Часть 10Скачать

Информатика 10 класс (Урок№2 - Подходы к измерению информации.)Скачать

Преобразование логических выражений / Упрощение выражений (практика) [Алгебра логики] #6Скачать

Информатика 10 класс: Алгоритм вычисления адреса компьютераСкачать

Алфавитный подход к определению количества информацииСкачать

Упрощение логических выраженийСкачать

Построение таблиц истинностиСкачать

Конъюнкция, дизъюнкция, импликация, эквиваленция, отрицание. На примерах из жизни. Логика.Скачать

Информатика 10 класс. Законы алгебры логики (УМК БОСОВА Л.Л., БОСОВА А.Ю.)Скачать