Про обозначения 1 страница

К сожалению, обозначения логических операций И, ИЛИ и НЕ, принятые в «серьезной» математической логике (Ù, Ú, ), неудобны, интуитивно непонятны и никак не проявляют аналогии с обычной алгеброй. Автор, к своему стыду, до сих пор иногда путает Ù и Ú. Поэтому на его уроках операция «НЕ» обозначается чертой сверху, «И» – знаком умножения (поскольку это все же логическое умножение), а «ИЛИ» – знаком «+» (логическое сложение).
В разных учебниках используют разные обозначения. К счастью, в начале задания ЕГЭ приводится расшифровка закорючек (Ù, Ú, ), что еще раз подчеркивает проблему.

Что нужно знать:

· условные обозначения логических операций

A, не A (отрицание, инверсия)

A Ù B, A и B (логическое умножение, конъюнкция)

A Ú B, A или B (логическое сложение, дизъюнкция)

A→B импликация (следование)

A↔B, эквиваленция (эквивалентность, равносильность)

· таблицы истинности логических операций «И», «ИЛИ», «НЕ», «импликация», «эквиваленция» (см. презентацию «Логика»)

· операцию «импликация» можно выразить через «ИЛИ» и «НЕ»:

A→B = A Ú Bили в других обозначениях A→B =

· операцию «эквиваленция» также можно выразить через «ИЛИ» и «НЕ»:

A↔B = A Ù B Ú A Ù Bили в других обозначениях A↔B =

· если в выражении нет скобок, сначала выполняются все операции «НЕ», затем – «И», затем – «ИЛИ», потом – «импликация», и самая последняя – «эквиваленция»

· логическое произведение A∙B∙C∙… равно 1 (выражение истинно) только тогда, когда все сомножители равны 1 (а в остальных случаях равно 0)

· логическая сумма A+B+C+… равна 0 (выражение ложно) только тогда, когда все слагаемые равны 0 (а в остальных случаях равна 1)

· правила преобразования логических выражений (законы алгебры логики):

Закон	Для И	Для ИЛИ
двойного отрицания
исключения третьего
исключения констант	A · 1 = A; A · 0 = 0	A + 0 = A; A + 1 = 1
повторения	A · A = A	A + A = A
поглощения	A · (A + B) = A	A + A · B = A
переместительный	A · B = B · A	A + B = B + A
сочетательный	A · (B · C) = (A · B) · C	A + (B + C) = (A + B) + C
распределительный	A + B · C = (A + B) · (A + C)	A · (B + C) = A · B + A · C
де Моргана

Пример задания:

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

(x₁ ® x₂) Ù (x₂ ® x₃) Ù (x₃ ® x₄)= 1

(у₁ ® у₂) Ù (у₂ ® у₃) Ù (у₃ ® у₄) = 1

(Øy₁ Ú x₁) Ù (Øy₂ Ú x₂) Ù (Øy₃ Ú x₃) Ù (Øy₄ Ú x₄) = 1

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

Решение:

1) видим, что первые два уравнения независимы друг от друга (в первое входят только x₁, x₂, …, x₄, а во второе – только y₁, y₂, …, y₄)

2) третье уравнение связывает первые два, поэтому можно поступить так:

· найти решения первого уравнения

· найти решения второго уравнения

· найти множество решений первых двух уравнений

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

3) найдем решения первого уравнения; каждая из логических переменных x₁, x₂, …, x₄ может принимать только два значения: «ложь» (0) и «истина» (1), поэтому решение первого уравнения можно записать как битовую цепочку длиной 4 бита: например, 0011 означает, что
x₁=x₂ = 0 и x₃=x₄ = 1

4) вспомним, что импликация x₁®x₂ ложна только для x₁ = 1и x₂ = 0, поэтому битовая цепочка, представляющая собой решение первого уравнения, не должна содержать сочетания «10»; это дает такие решения (других нет!):

(x₁, x₂, x₃, x₄) =0000 0001 0011 0111 1111

5) видим, что второе уравнение полностью совпадает по форме с первым, поэтому все его решения:

(y₁, y₂, y₃, y₄) =0000 0001 0011 0111 1111

6) поскольку первые два уравнения независимы друг от друга, система из первых двух уравнений имеет 5·5=25 решений: каждому решению первого соответствует 5 разных комбинаций переменных y₁, y₂, …, y₄, которые решают второе, и наоборот, каждому решению второго соответствует 5 разных комбинаций переменных x₁, x₂, …, x₄, которые решают первое:

(y₁, y₂, y₃, y₄) = 0000 0001 0011 0111 1111

(x₁, x₂, x₃, x₄) =0000 0000 0000 0000 0000

0001 0001 0001 0001 0001

0011 0011 0011 0011 0011

0111 0111 0111 0111 0111

1111 1111 1111 1111 1111

7) теперь проверим, какие ограничения накладывает третье уравнение; вспомнив формулу, которая представляет импликацию через операции «НЕ» и «ИЛИ» ( ), можно переписать третье уравнение в виде

(y₁ ® x₁) Ù (y₂ ® x₂) Ù (y₃ ® x₃) Ù (y₄ ® x₄) = 1

8) импликация y₁®x₁ ложна только для y₁ = 1и x₁ = 0, следовательно, такая комбинация запрещена, потому что нарушает третье уравнение; таким образом, набору с y₁ = 1:

(y₁, y₂, y₃, y₄) =1111

соответствует, с учетом третьего уравнения, только одно решение первого, в котором x₁ = 1

(y₁, y₂, y₃, y₄) =1111

поэтому множество решений «редеет»:

(y₁, y₂, y₃, y₄) = 0000 0001 0011 0111 1111

(x₁, x₂, x₃, x₄) =0000 0000 0000 0000

0001 0001 0001 0001

0011 0011 0011 0011

0111 0111 0111 0111

1111 1111 1111 1111 1111

9) аналогично двигаемся дальше по третьему уравнению; второй сомножитель равен 0, если импликация y₂®x₂ ложна, то есть только для y₂ = 1и x₂ = 0, это «прореживает» предпоследний столбец:

(y₁, y₂, y₃, y₄) = 0000 0001 0011 0111 1111

(x₁, x₂, x₃, x₄) =0000 0000 0000

0001 0001 0001

0011 0011 0011

0111 0111 0111 0111

1111 1111 1111 1111 1111

10) аналогично проверяем еще два ограничения, отбрасывая все решения, для которых y₃ = 1и x₃ = 0, а также все решения, для которых y₄ = 1и x₄ = 0:

(y₁, y₂, y₃, y₄) = 0000 0001 0011 0111 1111

(x₁, x₂, x₃, x₄) =0000

0001 0001

0011 0011 0011

0111 0111 0111 0111

1111 1111 1111 1111 1111

11) итак, остается одно решение при (y₁, y₂, y₃, y₄)=1111, два решения при (y₁, y₂, y₃, y₄)=0111, три решения при(y₁, y₂, y₃, y₄)=0011, четыре решения при(y₁, y₂, y₃, y₄)=0001 и 5 решений при (y₁, y₂, y₃, y₄)=0000

12) всего решений 1+2+3+4+5=15.

Ещё пример задания:

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

X₁→X₂ ÚX₃ Ù X₄ = 1

X₃→X₄ ÚX₅ Ù X₆ = 1

X₅→X₆ ÚX₁ Ù X₂ = 1

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

Решение:

13) перепишем уравнения в более простом виде, заменим знаки Ú и Ù соответственно на (логические) сложение и умножение:

14) вспомним, что сначала выполняется логическое умножение, потом логические сложение и только потом – импликация, поэтому уравнения можно переписать в виде

15) раскрывая импликацию по формуле , получаем

16) далее замечаем, что , и , поэтому можно ввести новые переменные , и , и переписать уравнения в виде

17) пусть , тогда из первого уравнения сразу имеем и далее из второго ; при этом третье автоматически выполняется; получили одно решение

18) теперь пуст , тогда из последнего уравнения имеем , а из второго – , при этом первое уравнение справедливо

19) таким образом, система уравнений относительно переменных имеет два решения: (0,0,0) и (1,1,1)

20) теперь вернемся обратно к исходным переменным; значению соответствует единственный вариант ; значению соответствуют остальные 3 пары возможных значений

21) то же самое можно сказать про и : нулевое значение дает один набор соответствующих исходных переменных, а единичное – три

22) переменные , и независимы друг от друга, так как каждая из них составлена из разных X-переменных, поэтому Y-решение (0,0,0) (см. п. 7) дает только одно X-решение, а Y-решение (1,1,1) – 3·3·3=27 решений

23) всего решений 1 + 27 = 28.

Ещё пример задания:

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

X₁→X₂ → X₃ → X₄ → X₅ → X₆ = 1

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

Решение (вариант 1, табличный метод, динамическое программирование):

24) в левой части заданного уравнения стоят последовательно несколько операций импликации, скобок нет, поэтому порядок выполнения операций определяется приоритетом этих операций; в данном случае все операции имеют одинаковый приоритет

25) операции, имеющие одинаковый приоритет, выполняются слева направо, то есть первой выполняется импликация X₁→X₂, а последней – последняя импликация

((((X₁→X₂) → X₃) → X₄) → X₅) → X₆

26) каждая логическая переменная может принимать значение «истина» (1) или «ложь» (0)

27) для набора из 6 независимых логических переменных существует 2⁶ =64 разных комбинаций значений этих переменных

28) рассмотрим первую импликацию, X₁→X₂; она дает в трёх случаях 1, и в одном – 0:

29) посмотрим, как меняется количество решений, если «подключить» следующую переменную;

· если X₁=0, то X₁→X₂ =1 (из нулей получаются единиц)

· если X₁=1, то X₁→X₂ =0 при X₂ =0 и X₁→X₂ =1 при X₂ =1 (из единиц получаются нулей и единиц)

30) исходя из этого, можно составить формулы для вычисления количества нулей и количества единиц для уравнения с переменными:

,

31) для одной переменной имеем 1 ноль и 1 единицу, поэтому начальные условия для расчёта:

32) составим таблицу, которую будем заполнять слева направо, вычисляя число нулей и единиц по приведенным выше формулам; в таблице показано, как строится следующий столбец таблицы для :

33) таким образом, ответ: 43 решения.

Решение (вариант 2, «с хвоста»):

1) те же рассуждения, что и в п. 1-4 решения по варианту 1

2) если X₆ =1, то левая часть уравнения равна 1, то есть равенство выполняется; комбинаций с X₆ =1 ровно половина от общего количества, то есть 32

3) теперь проверяем варианты с X₆ =0; сразу получаем, что для выполнения заданного уравнения нужно, чтобы (X₁→X₂ → X₃ → X₄ → X₅)=0; иначе получим 1 → X₆ = 1 →0 = 0

4) проверим отдельно случаи X₅=0 и X₅=1

5) пусть X₆ = 0 и X₅ =1; в этом случае никогда не будет выполнено условие
(X₁→X₂ → X₃ → X₄ → X₅)=0, решений нет

6) пусть X₆ = X₅ =0; в этом случае условие (X₁→X₂ → X₃ → X₄ → X₅)=0 выполняется только при (X₁→X₂ → X₃ → X₄)=1; если X₄=1, это условие всегда верно, поэтому получаем еще 8 решений – 8 комбинаций, где X₆ = X₅ =0 и X₄=1 (1/8 всех комбинаций)

7) теперь рассмотрим случаи, когда X₆ = X₅ = X₄=0; рассуждая аналогично, находим, что условие (X₁→X₂ → X₃ → 0)=1 верно при (X₁→X₂ → X₃)=0, это сразу дает X₃ =0 и
(X₁→X₂)=1

8) при всех известных значениях остальных переменных (X₆ = X₅ = X₄=X₃=0) условие
(X₁→X₂)=1 истинно в трёх случаях: (X₁,X­₂) =(0,0) , (0,1) и (1,1), это дает еще 3 решения

9) таким образом, ответ: 32 + 8 + 3 = 43 решения.

Решение (вариант 3, приведение к базису «И-ИЛИ-НЕ», Е.Н. Смирнова):

1) те же рассуждения, что и в п. 1-4 решения по варианту 1

2) заменяем импликацию по формуле ; на первом шаге получаем

3) далее по той же формуле

инверсию в первом слагаемом раскроем по закону де Моргана ( ):

4) сделав те же операции с оставшейся скобкой, получаем

5) и, применяя ту же формулу еще раз, получим уравнение

6) при остальные 5 переменных можно выбирать любым способом, это дает 2⁵ = 32 решения4⁴⁴⁴⁴⁴⁴

7) при и решений нет

8) при получаем 2³ = 8 решений при (можно выбирать , и произвольно)

9) при сразу находим, что , это дает еще 3 решения, при которых истинно выражение

10) таким образом, ответ: 32 + 8 + 3 = 43 решения.

Ещё пример задания:

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

X₁ Ú X₂ Ù X₃ = 1

X₂ Ú X₃ Ù X₄ = 1

...

X₈ Ú X₉ Ù X₁₀ = 1

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

Решение (последовательное подключение уравнений):

1) рассмотрим сначала все решения первого уравнения; его левая части истинна, когда X₁=1 (при этом X₂ и X₃ могут быть любыми), а также когда X₁=0 и X₂=X₃=1:

2) заметим, что первое и второе уравнения связаны через последние две переменных, в данном случае это X₂ и X₃

3) пусть i – число переменных в уравнениях; введем обозначения:

K_i– количество решений, в которых последние две переменные принимают
значения (0,0)

L_i– количество решений, в которых последние две переменные принимают
значения (0,1)

M_i– количество решений, в которых последние две переменные принимают
значения (1,0)

N_i– количество решений, в которых последние две переменные принимают
значения (1,1)

4) из таблицы видим, что K₃=1, L₃=1, M₃=1 и N₃=2

5) теперь подключаем второе уравнение; посмотрим, к чему приводят разные комбинации последних двух переменных:

6) находим, что
комбинация (0,0) не дает ни одного решения,
комбинация (0,1) дает одно решение, и при этом (X₃,X₄)=(1,1)