Решение логических уравнений и систем логических уравнений
методическая разработка по информатике и икт (11 класс) по теме
Предварительный просмотр:
Подписи к слайдам:
Задача 1. ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © Каково наибольшее целое число X, при котором истинно высказывание (10 < X·(X+1)) → (10 > (X+1)·(X+2))? Переведём следствие и раскроем скобки. ( X·(X+1 ) ≤ 10 ) V ( (X+1)·(X+2) < 1 0)=1 X должно быть целым и наибольшим, поэтому отрицательные числа даже не будем рассматривать. Данное выражение истинно если хотя бы одна его часть истинна, очевидно Х будет иметь большее значение в левой части выражения. Максимальный целый Х, удовлетворяющий левому неравенству, находим методом научного тыка , предполагая что Х=2. Ответ 2
Задача 2. ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © Укажите значения переменных K, L, M, N, при которых логическое выражение (K → M) ∨ (L ∧ K) ∨ ¬N ложно. Ответ запишите в виде строки из четырех символов: значений переменных K, L, M и N (в указанном порядке). Так, например, строка 1101 соответствует тому, что K=1, L=1, M=0, N=1. Это выражение ложно только если ложны 3 составляющие: (K → M)=0, здесь возможен только один случай: К=1, M=0 (L ∧ K)=0, так как К=1 из предыдущего случая, то L=0 ¬N=0 , N=1 Запишем в нужном порядке K, L, M и N = > 1001 Ответ 1001
Задача 3. ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © Сколько различных решений имеет уравнение (X ∧ Y ∨ Z) → (Z ∨ P) = 0 где X, Y, Z, P – логические переменные? В ответе не нужно перечислять все различные наборы значений, при которых выполнено данное равенство. В качестве ответа вам нужно указать только количество таких наборов. Чтобы данное уравнение принимало значение «Ложь», требуется выполнение 2-х равенств: (X ∧ Y ∨ Z)=1 , если Z=1, то X и Y могут принимать любое значение и мы получим 4 решения. Если Z=0, то мы имеем только одно решение X=1, Y=1, Z=0. (Z ∨ P) = 0, Здесь возможно только одно решение – Z=0, P=0. Из 2-х уравнений следует, что Z=0, а в этом случае существует только одно решение. Ответ 1
Задача 4. ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © Сколько различных решений имеет уравнение J ∧ ¬K ∧ L ∧ ¬M ∧ (N ∨ ¬N) = 0, где J, K, L, M, N — логические переменные ? В ответе не нужно перечислять все различные наборы значений J, K, L, M и N, при которых выполнено данное равенство . В качестве ответа нужно указать количество таких наборов. Данное выражение истинно, если все переменные истинны. Для N=1 мы имеем 2 4 =16 возможных комбинаций (2 значения 1 и 0 – основание системы, а 4 переменных – 4 разряда) Лишь одна комбинация, где все переменные J , K, L, M равны 1, не подойдёт, т.е. нам подходит 15 комбинаций. Для N= 0 мы тоже получим 15 подходящих комбинаций, итого у нас 15+15=30 различных решений. Ответ 30
Задача 5. ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © Сколько существует различных наборов значений логических переменных x1, х2, хЗ , х4, х5, y1, у2, уЗ , у4, у5, которые удовлетворяют всем перечисленным ниже условиям ? (x1 → х2) ∧ (х2 → хЗ ) ∧ ( хЗ → х4) ∧ (х4 → х5 ) = 1 (y1 → y2) ∧ (у2 → уЗ ) ∧ ( уЗ → у4) ∧ (у4 → у5 ) = 1 x1 ∨ y1 = 1 В ответе не нужно перечислять все различные наборы значений переменных x1, х2, хЗ , х4, х5, y1, у2, уЗ , у4, у5, при которых выполнена данная система равенств . В качестве ответа Вам нужно указать количество таких наборов. Эта задача отлична от предыдущих, удобнее всего решать её таблицей. Последнее уравнение будем называть исключающим. Рассмотрим первое уравнение и заметим, что оно будет истинным, только если все скобки истинны: ( x1 → х2) =1, (х2 → хЗ )=1 и т. д., так как они связаны коньюнкцией .
Задача 5. ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © ( x1 → х2) =1, (х2 → хЗ )=1 и т. д. связаны импликацией; она ложна, если первое выражение истинно, а второе ложно. Так же первые скобки связанны переменной х2, а значит выражения являются зависимыми . Предположим, что первая переменная истинна, тогда вторая может быть только истинной и истинными должны быть все. Заметьте, что если x3=1 , то все следующие за ней переменные должны быть также истинны. Таким образом мы получим таблицу решений для первого уравнения, из которой видно, что решений шесть. Точно такая же таблица получится и для 2-го уравнения. Попробуем их совместить. x1 x2 x3 x4 x5 1 1 1 1 1 0 1 1 1 1 0 0 1 1 1 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0
Задача 5. ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © Рассмотрим условие: x1 ∨ y1 = 1 , исключим из таблицы все неподходящие под это уравнение решения, т.е. такие, где x1 и y1 одновременно принимают ложное значение. Отметим их оранжевым. Таблица возможных комбинаций решений первых двух уравнений. решения X / решения Y 11111 01111 00111 00011 00001 00000 х1х2х3х4х5 х1х2х3х4х5 х1х2х3х4х5 х1х2х3х4х5 х1х2х3х4х5 х1х2х3х4х5 y1y2y3y4y5 11111 11111 11111 11111 11111 11111 y1y2y3y4y5 01111 01111 01111 01111 01111 01111 y1y2y3y4y5 00111 00111 00111 00111 00111 00111 y1y2y3y4y5 00011 00011 00011 00011 00011 00011 y1y2y3y4y5 00001 00001 00001 00001 00001 00001 y1y2y3y4y5 00000 00000 00000 00000 00000 00000
Задача 5. ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © Всего у нас 6*6 = 36 решений в таблице, из них, после исключающего уравнения, у нас остаётся 36-25=11 решений. Ответ 11 Таблица возможных комбинаций решений первых двух уравнений. решения X / решения Y 11111 0 1111 0 0111 0 0011 0 0001 0 0000 х1х2х3х4х5 х1 х2х3х4х5 х1 х2х3х4х5 х1 х2х3х4х5 х1 х2х3х4х5 х1 х2х3х4х5 y1y2y3y4y5 11111 11111 11111 11111 11111 11111 y1 y2y3y4y5 01111 0 1111 0 1111 0 1111 0 1111 0 1111 y1 y2y3y4y5 00111 0 0111 0 0111 0 0111 0 0111 0 0111 y1 y2y3y4y5 00011 0 0011 0 0011 0 0011 0 0011 0 0011 y1 y2y3y4y5 00001 0 0001 0 0001 0 0001 0 0001 0 0001 y1 y2y3y4y5 00000 0 0000 0 0000 0 0000 0 0000 0 0000
Задача 6. ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © Сколько существует различных наборов значений логических переменных x 1, x 2, x 3, x 4, x 5, x 6, x 7, x 8, которые удовлетворяют всем перечисленным ниже условиям? ( x 1∨ x 2)→( x 3∨ x 4)=1 ( x 3∨ x 4)→( x 5∨ x 6)=1 ( x 5∨ x 6)→( x 7∨ x 8)= 1 Так как нам надо найти все наборы переменных, при которых выполняются все условия, то мы можем объединить условия с помощью функции «и»: (( x 1∨ x 2)→( x 3∨ x 4 )) /\ (( x 3∨ x 4)→( x 5∨ x 6)) /\ (( x 5∨ x 6)→( x 7∨ x 8 ))=1
Задача 6. ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © Далее нам следует заменить выражения в скобках буквенными переменными, чтобы упростить выражение: x 1∨ x 2= A; x 3∨ x 4 =B; x 5∨ x 6 =C; x 7∨ x 8 =D. ( A → B ) /\ ( B → C ) /\ ( C → D )= 1 Напомним, что решение этого уравнения мы уже знаем: A , B,C,D – независимы(не имеют общих переменных), в таком случае количество возможных решений = количество решений A * к оличество решений B *количество решений С*количество решений D. Для А=1 существует 3 решения, для А=0 всего 1. Так же дела обстоят и с остальными переменными. A B C D 1 1 1 1 0 1 1 1 0 0 1 1 0 0 0 1 0 0 0 0
Задача 6. ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © Отметим рядом с каждым решением количество комбинаций, которое ему соответствует: Далее складываем получившиеся значения: 81+27+9+3+1=121. Ответ 121 A B C D Подсчёт комбинаций 1 3 1 3 1 3 1 3 3*3*3*3=81 0 1 1 3 1 3 1 3 1*3*3*3=27 0 1 0 1 1 3 1 3 1*1*3*3=9 0 1 0 1 0 1 1 3 1*1*1*3=3 0 1 0 1 0 1 0 1 1*1*1*1=1
Задача 7. ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © Сколько существует различных наборов значений логических переменных x 1 , x 2 , ... x 10 , которые удовлетворяют всем перечисленным ниже условиям? (x 1 ∧ ¬x 2 ) ∨ (¬x 1 ∧ x 2 ) ∨ (x 3 ∧ x 4 ) ∨ (¬x 3 ∧ ¬x 4 ) = 1 (x 3 ∧ ¬x 4 ) ∨ (¬x 3 ∧ x 4 ) ∨ (x 5 ∧ x 6 ) ∨ (¬x 5 ∧ ¬x 6 ) = 1 ... (x 7 ∧ ¬x 8 ) ∨ (¬x 7 ∧ x 8 ) ∨ (x 9 ∧ x 10 ) ∨ (¬x 9 ∧ ¬x 10 ) = 1 В ответе не нужно перечислять все различные наборы значений переменных x 1 , x 2 , … x 10 при которых выполнена данная система равенств . В качестве ответа Вам нужно указать количество таких наборов. Сначала сделаем преобразование: ( x 1 ∧ ¬x 2 ) ∨ (¬x 1 ∧ x 2 ) = ¬ ( x 1 ≡x 2 ) (x 3 ∧ x 4 ) ∨ (¬x 3 ∧ ¬x 4 ) = ( x 3 ≡x 4 ) ¬ ( x 1 ≡x 2 ) ∨ ( x 3 ≡x 4 )=( x 1 ≡x 2 ) → ( x 3 ≡x 4 )
Задача 7. ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © ( x 1 ≡x 2 ) → ( x 3 ≡x 4 )=1 ( x 3 ≡x 4 ) → ( x 5 ≡x 6 )= 1 ( x 5 ≡x 6 ) → ( x 7 ≡x 8 )= 1 ( x 7 ≡x 8 ) → ( x 9 ≡x 10 )= 1 Сделаем, как в предыдущей задаче: ( ( x 1 ≡x 2 ) → ( x 3 ≡x 4 ) ) /\ ( ( x 3 ≡x 4 ) → ( x 5 ≡x 6 ) ) /\ ( ( x 5 ≡x 6 ) → ( x 7 ≡x 8 ) ) /\ ( ( x 7 ≡x 8 ) → ( x 9 ≡x 10 ) ) =1 Теперь замена: A= ( x 1 ≡x 2 ) B= ( x 3 ≡x 4 ) C= ( x 5 ≡x 6 ) D= ( x 7 ≡x 8 ) E= ( x 9 ≡x 10 ) (A → B) /\ (B → C) /\ (C → D) /\ (D → E)=1
Задача 7. ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © Теперь составим таблицу решений. A, B, C, D, E тоже независимы, но у А х 1 и х2 теперь соединены тождеством, а не дизъюнкцией, поэтому будет 2 случая ложного исхода и 2 случая истинного исхода. Это распространяется и на оставшиеся 4 переменные B, C, D, E . Далее находим сумму 32*6=192 решения. Ответ 192 A B C D E Подсчёт комбинаций 1 2 1 2 1 2 1 2 1 2 2 * 2 * 2 * 2*2 = 32 0 2 1 2 1 2 1 2 1 2 2 * 2 * 2 * 2*2 = 32 0 2 0 2 1 2 1 2 1 2 2 * 2 * 2 * 2*2 = 32 0 2 0 2 0 2 1 2 1 2 2 * 2 * 2 * 2*2 = 32 0 2 0 2 0 2 0 2 1 2 2 * 2 * 2 * 2*2 = 32 0 2 0 2 0 2 0 2 0 2 2 * 2 * 2 * 2*2 = 32
Задача 8. ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © Сколько существует различных наборов значений логических переменных x 1 , x 2 , ... x 10 , которые удовлетворяют всем перечисленным ниже условиям ? (x 1 ∧ x 2 ) ∨ (¬x 1 ∧ ¬x 2 ) ∨ (x 2 ∧ ¬x 3 ) ∨ (¬x 2 ∧ x 3 ) = 1 (x 2 ∧ x 3 ) ∨ (¬x 2 ∧ ¬x 3 ) ∨ (x 3 ∧ ¬x 4 ) ∨ (¬x 3 ∧ x 4 ) = 1 ... (x 8 ∧ x 9 ) ∨ (¬x 8 ∧ ¬x 9 ) ∨ (x 9 ∧ ¬x 10 ) ∨ (¬x 9 ∧ x 10 ) = 1 В ответе не нужно перечислять все различные наборы значений переменных x 1 , x 2 , … x 10 при которых выполнена данная система равенств . В качестве ответа Вам нужно указать количество таких наборов. Казалось бы задача похожа на предыдущую, но! в правой и левой части есть одинаковые переменные, а значит они зависимы и решать придётся графом, а не таблицей. Далее находим сумму 32*6=192 решения. Ответ 192
Задача 8. ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © Вначале преобразуем: (x 1 ∧ x 2 ) ∨ (¬x 1 ∧ ¬x 2 )= (x 1 ≡ x 2 ) ( x 2 ∧ ¬x 3 ) ∨ (¬x 2 ∧ x 3 ) = ¬(x 2 ≡ x 3 ) (x 1 ≡ x 2 ) ∨ ¬(x 2 ≡ x 3 ) = ¬(x 2 ≡ x 3 ) ∨ (x 1 ≡ x 2 )=(x 3 ≡ x 2 ) → ( x 2 ≡ x 1 )= 1 (x 3 ≡ x 2 ) → (x 2 ≡ x 1 )= 1 (x 4 ≡ x 3 ) → (x 3 ≡ x 2 )= 1 (x 5 ≡ x 4 ) → (x 4 ≡ x 3 )= 1 (x 6 ≡ x 5 ) → (x 5 ≡ x 4 )= 1 (x 7 ≡ x 6 ) → (x 6 ≡ x 5 )= 1 (x 8 ≡ x 7 ) → (x 7 ≡ x 6 )= 1 (x 9 ≡ x 8 ) → (x 8 ≡ x 7 )= 1 (x 10 ≡ x 9 )→ (x 9 ≡ x 8 )= 1 Тождество – симметричная операция, поэтому существует 2 симметричных набора решений, для нуля и для единицы, построим граф решений, предположив что все переменные равны единице, а затем будем варьировать переменные.
Задача 8. ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © Составим граф или таблицу решений: x 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 x 10 1 1 1 1 1 1 1 1 1 1 0 0 1 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 0
Задача 8. ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © Из таблицы видно, что существует 10 решений для единицы и, соответственно, будет еще 10 для нуля. Всего 20 решений. Ответ 20
Вопросы. ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, которые удовлетворяют всем перечисленным ниже условиям ? ( x1 → x2) ∧ (x2 → x3) ∧ (x3 → x4) ∧ (x4 → x5 ) = 1 ( y2 → y1) ∧ ( y3 → y2) ∧ ( y4 → y3) ∧ ( y5 → y4 ) ∧ ( y6 → y5 ) = 1 x5 → y6 = 1 В ответе не нужно перечислять все различные наборы значений переменных x1, x2, x3, x4, x5 , x6, y1, y2, y3, y4, y5 , y6, при которых выполнена данная система равенств . В качестве ответа Вам нужно указать количество таких наборов . Указание: переставьте скобки во 2-м выражении от (y6 → y5 ) к (y2 → y1) , из таблицы решений исключите все те, в которых одновременно x5=1, y6 =0. Ответ 12.
Вопросы. ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © Сколько различных решений имеет система уравнений ¬x1 ∨ x2 = 1 ¬x2 ∨ x3 = 1 … ¬x9 ∨ x10 = 1, где x1, x2, … x10 — логические переменные? В ответе не нужно перечислять все различные наборы значений x1, x2, … x10, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов. Указание: преобразуйте каждое выражение вот таким образом:¬x1 ∨ x2 = x1 → x2, затем объедините все выражения конъюнкцией, и получится уравнение, такого же вида, как в задаче №5. Ответ 1 1 .
Вопросы. ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, y1, y2, y3, y4, z1, z2, z3, z4, которые удовлетворяют всем перечисленным ниже условиям? ( x1→x2) ∧ ( x2 →x3) ∧ ( x3 →x4) = 1 (¬x1 ∧ y1 ∧ z1) ∨ (x1 ∧ ¬y1 ∧ z1) ∨ (x1 ∧ y1 ∧ ¬z1) = 1 (¬x2 ∧ y2 ∧ z2) ∨ (x2 ∧ ¬y2 ∧ z2) ∨ (x2 ∧ y2 ∧ ¬z2) = 1 (¬x3 ∧ y3 ∧ z3) ∨ (x3 ∧ ¬y3 ∧ z3) ∨ (x3 ∧ y3 ∧ ¬z3) = 1 (¬x4 ∧ y4 ∧ z4) ∨ (x4 ∧ ¬y4 ∧ z4) ∨ (x4 ∧ y4 ∧ ¬z4) = 1 В ответе не нужно перечислять все различные наборы значений переменных x1, x2, x3, x4, y1, y2, y3, y4, z1, z2, z3, z4, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.
0 Вопросы. ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © Решение. Слева - решение первого уравнения. Посередине - решение второго уравнения. Справа – подсчет комбинаций. Решения третьего, четвертого и пятого уравнений рассматривать не будем, т.к. они совпадают со вторым, при этом они не содержат одинаковых переменных, т.е. независимы. Заметим, что для х1=1 существует 2 решения, а для х1=0 – одно решение. Это верно и для х2,х3,х4. Всего в сумме 16+8+4+2+1=31 комбинация. Ответ 31 x 1 х2 х3 х4 1 1 1 1 0 1 1 1 0 0 1 1 0 0 0 1 0 0 0 0 x1 y1 z1 0 1 1 1 0 1 1 1 0 x 1 х2 х3 х4 Комбинации 1 2 1 2 1 2 1 2 2*2*2*2=16 0 1 1 2 1 2 1 2 1*2*2*2=8 0 1 0 1 1 2 1 2 1*1*2*2=4 0 1 0 1 0 1 1 2 1*1*1*2=2 0 1 0 1 0 1 0 1 1*1*1*1=1
По теме: методические разработки, презентации и конспекты
Решение тригонометрических уравнений и систем уравнений
видеоурок интегрированного урока по математике и информатике...
Подготовка к ЕГЭ. Разбор решений систем логических уравнений.
В презентации рассмотрены примеры решения заданий В15 по теме "Решение логических уравнений"...
урок по теме "Примеры решения тригонометрических уравнений и систем уравнений"
Класс 10Урок закрепления....
Методы решения систем логических уравнений
Методы решения систем логических уравнений при подготовке к ЕГЭ (задание В15)...
Решение систем логических уравнений, задание 27 ЕГЭ по информатике
Материал содержит презентацию, в которой разбираются задания 27 (Решение логических уравнений и систем логических уравнений), которые представлены в демо-версии, а также реальные задания экзамена 2014...
Презентация" Решение систем логических уравнений"
Учебный материал сформирует у учащихся навык решения логических уравнений и систем логических уравнений....
Проверь себя! ЕГЭ. Задание 23 (Задачи на систему логических уравнении)
Проверь себя! ЕГЭ. Задание 23 (Задачи на систему логических уравнении)...