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

4) первое уравнение выполняется, когда есть X₂ равно X₁ или X₃

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

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

6) добавим еще одно уравнение и еще одну переменную X­₄:

7) чтобы «подключить» второе уравнение, нужно использовать то же самое правило: каждой строчке в первых двух столбцах должно быть, по крайней мере, одно значение, равное значению в третьем столбце (который выделен желтым); это значит, что в первой и последней строчках (где X­₁ = X₃) значение X₄ может быть любое (0 или 1), а в остальных строчках – только строго определенное:

8) таким образом, количество решений при подключении очередного уравнения к системе возрастает на 2!

9) подключили X₅ – получили 10 решений, X₆ – получили 12 решений, X₇ – получили 14 решений, X₈ – получили 16 решений, X₉ – получили 18 решений, X₁₀ – получили 20 решений.

10) остается одно последнее уравнение (X₁₀ º X₁) = 0, из которого следует, что X₁₀ не равен X­₁

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

12) таким образом, получается 20 – 2 = 18 решений

13) ответ: 18 решений

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

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

(X₁ Ù X₂) Ú (X₁ Ù X₂) Ú (X₁ º X₃) = 1

(X₂ Ù X₃) Ú (X₂ Ù X₃) Ú (X₂ º X₄) = 1

...

(X₈ Ù X₉) Ú (X₈ Ù X₉) Ú (X₈ º X₁₀) = 1

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

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

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

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

...

3) заметим, что по свойству операции эквивалентности , поэтому уравнения можно переписать в виде

...

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

5) рассмотрим все возможные комбинации первых двух переменных ­X₁ и X₂, и сразу попытаемся для каждой из них подобрать значения третьей так, чтобы выполнялось первое уравнение :

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

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

8) также заметим, что в новой таблице в самой верхней и самой нижней строках значения X₃ и X₂ равны, а в остальных не равны (их 4 штуки); поэтому на следующем шаге (при подключении четвертой переменной и третьего уравнения) верхняя и нижняя строки дадут 2 варианта с равными X­₄ и X₃, и 2 + 4 = 6 вариантов, где X­₄ и X₃ не равны

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

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

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

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

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

i			всего решений
		2+4=6
		2+6=8
		2+8=10
		2+10=12
		2+12=14
		2+14=16
		2+16=18

11) таким образом, для системы с 10 переменными общее количество решений равно 2 + 18 = 20

12) ответ: 20 решений

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

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

(X₁ Ù X₂) Ú (X₁ Ù X₂) Ú (X₂ Ù X₃) Ú (X₂ Ù X₃) = 1

(X₂ Ù X₃) Ú (X₂ Ù X₃) Ú (X₃ Ù X₄) Ú (X₃ Ù X₄) = 1

...

(X₈ Ù X₉) Ú (X₈ Ù X₉) Ú (X₉ Ù X₁₀) Ú (X₉ Ù X₁₀) = 1

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

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

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

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

...

3) заметим, что по свойству операции эквивалентности , поэтому уравнения можно переписать в виде

...

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

5) рассмотрим все возможные комбинации первых двух переменных ­X₁ и X₂, и сразу попытаемся для каждой из них подобрать значения третьей так, чтобы выполнялось первое уравнение :

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

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

8) переставим строки так, чтобы сверху стояли те строки, в которых X₂ = X₃:

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

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

11) две нижние строки, где X₂ ¹ X₃, дадут 2 варианта, где X­₄ и X₃ равны

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

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

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

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

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

i			всего решений
	4
	4+2=6
	6+4=10
	10+6=16
	16+10=26
	26+16=42
	42+26=68
	68+42=110

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

15) ответ: 178 решений

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

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

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

...

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

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

5) теперь рассматриваем переменную X₃; если X₁ = X₂, то уравнение выполняется при любом X₃; если X₁ ¹ X₂, то это уравнение сразу дает X₃ = X₂; дерево получается уже неполным, число решений первого уравнения – 6:

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

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

8) ответ: 178 решений

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

Каково наибольшее целое число X, при котором истинно высказывание

(50 < X·X)→(50 > (X+1)·(X+1))

Решение (вариант 1):

1) это операция импликации между двумя отношениями и

2) попробуем сначала решить неравенства

,

3) обозначим эти области на оси X:

на рисунке фиолетовые зоны обозначают область, где истинно выражение , голубая зона – это область, где истинно

4) вспомним таблицу истинности операции «импликация»:

5) согласно таблице, заданное выражение истинно везде, кроме областей, где и ; область истинности выделена зеленым цветом

6) поэтому наибольшее целое число, удовлетворяющее условию – это первое целое число, меньшее , то есть, 7

7) таким образом, верный ответ – 7 .

Решение (вариант 2, преобразование выражения):

1) сначала можно преобразовать импликацию, выразив ее через «ИЛИ» и «НЕ»:

2) это значит, что выражение истинно там, где или

3) дальнейшие действия точно такие же, как и в варианте 1.

Решение (вариант 3, математический):

1) это операция импликации между двумя отношениями и

2) пусть – истинно, тогда, с учетом того, что , находим, что – ложно, таким образом, импликация ложна

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

4) максимальное целое значение X, при котором , равно 7

5) таким образом, верный ответ – 7 .

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

Каково наибольшее целое число X, при котором истинно высказывание

(10 < X·(X+1))→(10 > (X+1)·(X+2))

Решение (в целых числах):

1) это операция импликации между двумя отношениями:

и

2) конечно, здесь можно применить тот же способ, что и в предыдущем примере, однако при этом понадобится решать квадратные уравнения (не хочется…)

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

4) рассмотрим неравенство : очевидно, что может быть как положительным, так и отрицательным числом;

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

6) поэтому для целых можно заменить на равносильное выражение

7) область истинности выражения – объединение двух бесконечных интервалов:

8) теперь рассмотрим второе неравенство : очевидно, что так же может быть как положительным, так и отрицательным числом;

9) в области высказывание истинно при всех целых , а в области – при всех целых , поэтому для целых можно заменить на равносильное выражение

10) область истинности выражения – закрытый интервал, обозначенный голубой полоской

11) вспомним таблицу истинности операции «импликация»:

12) согласно таблице, заданное выражение истинно везде, кроме областей, где и ; область истинности выделена на рисунке зеленым цветом;

13) обратите внимание, что значение уже не входит в зеленую зону, потому что там и , то есть импликация дает 0

14) по схеме видно, что максимальное целое число в зеленой области – 2

15) таким образом, верный ответ – 2.

Возможные проблемы: · нужно помнить, что мы рассматриваем значения выражения только для целых , при этом появляются свои особенности: может появиться желание продлить зеленую область до точки , что приведет к неверному ответу, потому что там уже и

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

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

((K Ú L)→(L Ù M Ù N)) = 0

где K, L, M, N – логические переменные? В ответе не нужно перечислять все различные наборы значений K, L, M и N, при которых выполнено данное равенство. В качестве ответа Вам нужно указать количество таких наборов.

Решение (вариант 1, разделение на части):