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

Войти
Регистрация

Главная
ЕГЭ
- Вопросы и ответы
- Перевод баллов
- Соответствие заданий
- Программирование
  - Типы данных Pascal
  - Математические функции
  - Логические операции
  - Приоритет операций
  - Законы логики
  - О системах счисления
  - Перевод чисел
  - Таблица триад и тетрад
  - Досрочный-2016
  - Демо-2016
  - Досрочный-2015
  - Алгебра логики
  - Вариант 1
  - Вариант 2
  - Вариант 3
  - Вариант 4
  - Вариант 5
  - Вариант 6
  - Вариант 7
  - Вариант 8
  - Вариант 9
  - Вариант 10
  - Степени двойки
  - IP, маска и адрес сети
  - Решатор 5
  - Решатор 13
  Скобки независимы друг от друга. Заменим каждую отдельной переменной:
  
  a → b = 1
  b → c = 1
  
  В битовой цепочке не может быть единицы перед нулём, т.к. в этом случае уравнение будет ложным. Построим цепочки по этому правилу:
  
  a 1 0 0 0
  b 1 1 0 0
  c 1 1 1 0
  
  Всего четыре цепочки.
  Каждая из переменных a, b, c является импликацией иксов, значит на каждую истину приходится 3 варианта, а на каждую ложь — 1 вариант.
  То есть для первой цепочки (1 1 1) приходится 3^3 = 27 наборов, для второй цепочки (0 1 1) — 3^2 = 9 наборов, для третьей цепочки (0 0 1) — три набора, и для четвёртой цепочки (0 0 0) — один набор.
  27+9+3+1 = 40 решений.
  
  Ещё пример задания (а.Б. Ислентьев):
  
  где x₁, …,x₃,y₁, …,y₃– логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.
  
  Решение (метод отображений):
  
  перепишем систему уравнений в более понятном виде:
  
  рассмотрим первое уравнение
  
  его левая часть равна 1, если приz₁ = 1; таким образом, есть всего 3 различных варианта, дающих 1 в левой части:
  
  в левой части первого уравнения 3 переменных, поэтому всего есть 2 3 = 8 комбинаций этих данных; в оставшихся 5 комбинациях левая часть первого уравнения равна 0
  
  обе части равны…
  
  аналогично находим, что правая часть первого уравнения равна 0 при 3-х комбинациях переменных , причём каждой из них соответствует 5 троек; эта же правая часть равна 1 для пяти остальных комбинаций, причём каждой из них соответствует 3 комбинации:
  
  обе части равны…
  
  поэтому первое уравнение имеет 5∙3 + 3∙5 = 30 решений: 15 решений, при которых обе части равны 0, и 15 решений, при которых обе части равны 1
  
  теперь подключаем второе уравнение: выпишем в следующий столбец все комбинации , при которых его левая часть равна 0, и в следующую строку – все комбинации, при которых его левая часть равна 1, указав соответствующее число решений первого уравнения:
  
  обе части равны…
  
  таким образом, на каждую комбинацию , при которых правая часть второго уравнения равна 1, приходится 3 + 3 + 3 = 9 допустимых троек, а на каждую комбинацию, при которых правая часть второго уравнения равна 0, приходится 5 + 3 + 5 + 3 + 5 = 21 допустимая тройка.
  
  обе части равны…
  
  несложно проверить, что 5 троек дают 1 в правой части второго уравнения, а оставшиеся 3 тройки – 0:
  
  обе части равны…
  
  для получения ответа нужно сложить числа в скобках в последнем столбце таблицы:
  
  9 + 9 + 9 + 9 + 9 + 21 + 21 + 21 = 108
  
  Решение (метод отображений, Р. Еннер):
  
  перепишем систему уравнений в более понятном виде:
  
  рассмотрим первое уравнение
  
  его левая часть равна 1, если приz₁ = 1; таким образом, есть всего 3 различных варианта, дающих 1 в левой части:
  
  в левой части первого уравнения 3 переменных, поэтому всего есть 2 3 = 8 комбинаций этих данных; в оставшихся 5 комбинациях левая часть первого уравнения равна 0
  
  обе части равны…
  
  аналогично находим, что правая часть первого уравнения равна 0 при 3-х комбинациях переменных x₂y₂z₂, эта же правая часть равна 1 для пяти остальных комбинацийx₂y₂z₂,
  
  выполняем те же рассуждения для второго уравнения и все сводим в одну таблицу:
  
  обе части равны…
  
  001
  
  011
  
  100
  
  000
  
  010
  
  110
  
  обозначим стрелочкойнаборыx₂y₂z₂равные 1 которые совпадают в первом и втором уравнении. Обозначимстрелочкойнаборыx₂y₂z₂равные 0 которые совпадают в первом и втором уравнении. Обозначимстрелочкойнаборыx₂y₂z₂равные 1 в первом уравнении и равные 0 во втором.
  
  решением исходной системы
  
  ((x₁  y₁)  z₁)  ((x₂  y₂)  z₂)
  
  ((x2  y2)  z2)  ((x3  y3)  z3)
  
  могут быть 4 варианта:
  
  Вариант I: такой вариант получается, если переходить от первого уравнения ко второму по синим стрелкам. 3 набораx₁y₁z₁можно объединить только с 3 наборамиx₂y₂z₂, а их можно объединить с 5 наборамиx₃y₃z₃. Таким образом, получаем 3*3*5 =45наборов.
  
  Вариант II: такой вариант получается, если переходить от первого уравнения ко второму по черным стрелкам. 3 набораx₁y₁z₁можно объединить только с 2 наборамиx₂y₂z₂, а их можно объединить с 3 наборамиx₃y₃z₃. Таким образом, получаем 3*2*3 =18наборов.
  
  Вариант III: таких вариантов нет.
  
  Вариант IV: такой вариант получается, если переходить от первого уравнения ко второму по оранжевым стрелкам. 5 наборовx₁y₁z₁можно объединить с 3 наборамиx₂y₂z₂, а их можно объединить с 3 наборамиx₃y₃z₃. Таким образом, получаем 5*3*3 =45наборов.
  
  Задача №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)
  
  Эквивалентность истинна, только если оба операнда равны. Решениями этого уравнения будут два набора:
  
  z1 z2 z3 z4 z5 z6 z7 z8 z9
  
  0 1 0 1 0 1 0 1 0
  
  1 0 1 0 1 0 1 0 1
  
  Т.к. 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₊₁ = 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 наборов):
  
  Сколько различных решений имеет система логических уравнений
  
  РАЗОБРАННЫЕ ПРИМЕРЫ ЗАДАЧ:
  
  Решение. Все “сомножители”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 комбинации.
  Похожие публикации: