Погода
Календарь
Март 2019
Пн Вт Ср Чт Пт Сб Вс
« Сен    
 123
45678910
11121314151617
18192021222324
25262728293031
Страницы сайта

Логические уравнения.

1. Одно уравнение с непересекающимися операндами внешней операции и одним вариантом решения:

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

  • Так как внешняя операция — конъюнкция (логическое умножение), то чтобы результат был истинным (равен единице), оба операнда должны быть равны единице. То есть мы имеем одно решение для внешней операции.
  • Переменные не пересекаются, значит, ищем отдельные решения для двух уравнений:
  • Результат истинен (равен единице) для операции дизъюнкция (логическое сложение) имеет 3 решения (01, 10 и 11):
  • Поскольку оба уравнения «работают» одновременно, то результат — это произведение двух решений:

2. Одно уравнение с непересекающимися операндами внешней операции и несколькими вариантами решения

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

  • Так как внешняя операция — дизъюнкция (логическое сложение), результат истинен (равен единице) в трех случаях: 01, 10 11. То есть мы имеем три решения для внешней операции.
  • Переменные не пересекаются, значит, ищем отдельные решения для двух уравнений, НО! для трех случаев:
  • Результат единица для операции конъюнкция (логическое умножение) имеет 1 решение (11), а результат ноль — 3 решения (00, 01 и 10):
  • Поскольку для двух уравнений решения в трех случаях «работать» одновременно не могут, то результат — это сложение трех решений:
    3 + 3 + 1 = 7

3. Одно уравнение с пересекающимися операндами внешней операции

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

  • Так как внешняя операция — импликация, результат ложен (равен нулю) в одном случае (1 → 0). То есть мы имеем одно решение для внешней операции.
  • Составим систему уравнений:
  • Переменные пересекаются, значит, необходимо рассмотреть отдельно каждое уравнение системы:
  • Рассмотрим первое уравнение системы. В нем операция дизъюнкция (логическое сложение) возвращает единицу в трех случаях: 01 10 11.

Рассмотрим каждый случай отдельно и учтем его результаты для второго уравнения системы:

1

Поскольку для двух уравнений решения в трех случаях не могут «работать» одновременно, то результат — это сложение трех решений: 4 + 3 + 3 = 10

4. Несколько уравнений: метод отображения решений уравнения

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

Метод отображения можно использовать:

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

5. Несколько уравнений: использование битовых масок

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

Побитовая маска (битовая маска) — метод, который можно использовать:

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

Решение заданий

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

где x1, …, x8, y1, …, y8  – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.

Решение:

перепишем систему уравнений в более понятном виде:

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

построим новую эквивалентную систему из трёх уравнений, сгруппировав сомножители «по вертикали»:

в этой системе первые два уравнения независимы, а третье представляет собой уравнение связи

из первого уравнение сразу следует, что в цепочке X=x1x2…x8  запрещена комбинация 10, то есть все допустимые цепочки X имеют структуру «все нули, потом – все единицы», их 9 штук (на 1 больше, чем число переменных):

00000000    00000001    00000011    00000111

00001111    00011111    00111111    01111111    11111111

те же самые решения (для цепочек Y=y1y2…y8 ) будут и у второго уравнения, которое имеет точно такую же структуру

если бы третьего уравнения не было, система имела бы 81 решение (9*9) – каждая цепочка X может сочетаться с каждой цепочкой Y

остаётся учесть уравнение связи:

из которого следует, что если xi = 1, то нужно выполнить условие yi+1 = 1.

рассмотрим цепочку X = 00000000; в ней нет единиц, поэтому она сочетается со всеми Y-цепочками (9 решений)

рассмотрим цепочку X = 00000001; в ней одна единица, уравнение связи требует, чтобы следующий бит Y-цепочки был равен 1, но такого (9-го) бита в Y-цепочке нет поэтому эта X-цепочка сочетается со всеми Y-цепочками (9 решений)

рассмотрим цепочку X = 00000011; в ней две единицы, согласно уравнению связи требуется, чтобы 8-й бит Y-цепочки был равен 1, поэтому она сочетается только со всеми Y-цепочками, кроме одной – 00000000 (8 решений)

продолжая рассуждать тем же способом, находим, что следующие X-цепочки дают 7, 6, 5, 4, 3 и 2 решения, всего получается 2 · 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 = 53.

Ответ: 53.

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

где x1, …, x4, y1, …, y4, z1, …, z4, – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.

Решение:

перепишем систему уравнений в более понятном виде:

сначала решим первое уравнение, а затем посмотрим, как будет изменяться количество решений при добавлении переменных yi и zi и учёте остальных однотипных уравнений

в первом уравнении каждая скобка должна быть равна 1, поэтому в цепочке битов X = x1 x2 x3 запрещена комбинация 10; это значит, что после первой встретившейся единицы могут следовать только единицы, и любая цепочка-решение имеет структуру «все нули, потом – все единицы»

таких решений для первого уравнения – 5:

0000, 0001, 0011, 0111 и 1111

теперь рассмотрим остальные уравнения, имеющие (для i=1, …, 4) одинаковую структуру

пусть в этом уравнении xi = 0, тогда получаем

этому уравнению соответствуют две допустимых пары

а при двух оставшихся вариантах одна из скобок обращается в 0

при xi = 1 получаем

этому уравнению соответствуют три допустимых пары

а при двух оставшихся вариантах одна из скобок обращается в 0

объединяя результаты пп. 6 и 7, получаем, что каждый нуль в решении X первого уравнения удваивает количество решений системы, а каждая единица – утраивает

таким образом первое решение X = 0000 даёт 16 = 24 решений системы, решение 0001 даёт 23 ∙ 3 = 24 решений системы, решение 0011 даёт 22 ∙ 32 = 36 решений системы, решение 0111 даёт 2 ∙ 33 = 54 решений и решение 1111 даёт 34 = 81 решений системы;

всего решений системы 16 + 24 + 36 + 54 + 81 =  211

Ответ: 211.

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

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

Решение (табличный метод):

количество комбинаций 10 логических переменных равно 210 = 1024, поэтому вариант с построением полной таблицы истинности отпадает сразу

перепишем уравнения, используя более простые обозначения операций

заметим, что по свойству операции эквивалентности

поэтому уравнения можно переписать в виде

сделать замену переменных так, чтобы новые переменные был независимы друг от друга, здесь довольно затруднительно, поэтому будем решать уравнения последовательно табличным методом рассмотрим все возможные комбинации первых двух переменных  ­X1 и X2, и сразу попытаемся для каждой из них подобрать значения третьей так, чтобы выполнялось первое уравнение

очевидно, что в первой и последней строчках таблицы, где X1=X2, значения X3 могут быть любыми, то есть каждая из этих строчек дает два решения; в то же время во второй и третьей строках, где X1<>X2, мы сразу получаем, что для выполнения первого равнения необходимо X2=X3, то есть, эти две строчки дают по одному решению:

заметим, что количество решений для каждой строчки исходной таблицы (с двумя переменными) определялось лишь тем, равны значения в двух последних столбцах (X2 и X1) или не равны;

переставим строки так, чтобы сверху стояли те строки, в которых X2 = X3:

также заметим, что в новой таблице в четырех строках значения X2 = X3, а в остальных 2-х эти переменные не равны;

поэтому на следующем шаге (при подключении четвертой переменной и третьего уравнения) 4 первые строки дадут по 2 варианта (всего 4·2=8) решений, из них 4 штуки с равными X­4 и X3, и 4 варианта, где X­4 и X3 не равны

две нижние строки, где X2 <> X3, дадут 2 варианта, где X­4 и X3 равны

в общем виде: если на шаге i в таблице решений есть

ni  строк, где значения в двух самых левых столбцах таблицы равны, и …

mi строк, где значения в двух самых левых столбцах таблицы не равны,

то на следующем шаге будет (ni+mi) строк с равными значения в двух самых последних столбцах и ni строк с неравными значениями

эту последовательность можно записать в виде таблицы (i – число задействованных переменных):

таким образом, для системы с 10 переменными общее количество решений равно 110 + 68 = 178

Ответ: 178 решений

Решение (использование дерева для представления решения):

идея представления множества решений в виде дерева использовалась, например, в решениях  О.А. Тузовой (Санкт-Петербург, школа № 550) и М.В. Демидовой (г. Пермь, гимназия №17); как верно отметила О.А. Тузова, предложенный выше табличный метод по сути представляет собой компактную запись дерева

так же, как и в предыдущем варианте решения, перейдем к равносильной системе уравнений

все переменные логические, в принятых обозначениях каждая из них может быть равна 1 или 0; для X1 получаем два варианта, которые можно представить в виде

при этом X­2 может быть  любым, то есть, имеем всего 4 варианта

теперь рассматриваем переменную X3;  если X1 = X2, то уравнение

выполняется при любом X3; если X1 ¹ X2, то это уравнение сразу дает X3 = X2; дерево получается уже неполным, число решений первого уравнения – 6:

рассуждая аналогично, находим, что на следующем шаге (подключение переменной X4 и второго уравнения) получается 10 решений, затем – 16 и т. д.; в результате получается удвоенная последовательность Фибоначчи (2, 4, 6, 10, 16, 26, …), в которой каждый следующий элемент равен сумме двух предыдущих:

в некоторых вариантах такой подход рассматривался совместно с методом декомпозиции: сначала предполагаем, что X1 = 0 и находим все решения для этого варианта; затем находим все решения при X1 = 1; после этого общее количество решений вычисляется как сумма полученных двух чисел

Ответ: 178 решений

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

(¬x1 \/ y1 ) → (¬x2 /\ y2 ) = 1
(¬x2 \/ y2 ) → (¬x3 /\ y3 ) = 1

(¬x6 \/ y6 ) → (¬x7 /\ y7 ) = 1

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

  • Рассмотрим 1-е уравнение:

(¬x1 ∨ y1 ) → (¬x2 ∧ y2 ) = 1

  • Построим для 1-го уравнения таблицу истинности:
  • Итого 7 решений дает одно первое уравнение. Столько же решений будет и у отдельно взятого второго уравнения:
  • Добавим ко второй таблице истинности х1 и y1 (переменные, которые есть в первом уравнении):
  • Вывод: второе уравнение увеличило количество наборов на 3, следовательно, каждое следующее уравнение будет увеличивать количество наборов на 3.
  • Итого: 7 + 5*3 = 22

Ответ: 22

Top