Спосіб вирішення систем логічних рівнянь. Рішення логічних рівнянь з математики Приклади рішень логічних рівнянь

Рішення систем логічних рівнянь методом заміни змінних

Метод заміни змінних застосовується, якщо деякі змінні входять до складу рівнянь тільки у вигляді конкретного вираження, і ніяк інакше. Тоді цей вислів можна позначити нової змінної.

Приклад 1.

Скільки існує різних наборів значень логічних змінних x1, х2, х3, х4, х5, х6, х7, х8, які задовольняють всім нижченаведеними умовами?

(X1 → х2) → (х3 → х4) \u003d 1

(Х3 → х4) → (х5 → х6) \u003d 1

(Х5 → х6) → (х7 → х8) \u003d 1

У відповіді не потрібно перераховувати всі різні набори значень змінних x1, х2, х3, х4, х5, х6, х7, х8, при яких виконана дана система рівності. Як відповідь Вам потрібно вказати кількість таких наборів.

Рішення:

(X1 → х2) \u003d y1; (Х3 → х4) \u003d y2; (Х5 → х6) \u003d y3; (Х7 → х8) \u003d y4.

Тоді можна записати систему у вигляді одного рівняння:

(Y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) \u003d 1. Кон'юнкція дорівнює 1 (істинна), коли кожен операнд приймає значення 1. Тобто кожна з імплікацій повинна бути істинною, а це виконується при всіх значеннях, крім (1 → 0). Тобто в таблиці значень змінних y1, y2, y3, y4 одиниця не повинна стояти лівіше нуля:

Тобто умови виконуються для 5 наборів y1-y4.

Оскільки y1 \u003d x1 → x2, то значення y1 \u003d 0 досягається на єдиному наборі x1, x2: (1, 0), а значення y1 \u003d 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 \u003d 121.

відповідь: 121

Приклад 2.

Скільки існує різних наборів значень логічних змінних x1, x2, ... x9, y1, y2, ... y9, які задовольняють всім нижченаведеними умовами?

(¬ (x1 ≡ y1)) ≡ (x2 ≡ y2)

(¬ (x2 ≡ y2)) ≡ (x3 ≡ y3)

(¬ (x8 ≡ y8)) ≡ (x9 ≡ y9)

У відповіді не потрібноперераховувати всі різні набори значень змінних x1, x2, ... x9, y1, y2, ... y9, при яких виконана дана система рівності. Як відповідь Вам потрібно вказати кількість таких наборів.

Рішення:

Зробимо заміну змінних:

(X1 ≡ y1) \u003d z1, (x2 ≡ y2) \u003d z2, .... , (X9 ≡ y9) \u003d 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 \u003d (xi ≡ yi), то значенням zi \u003d 0 відповідають два набори (xi, yi): (0,1) і (1,0), а значенням zi \u003d 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 \u003d 1024 наборів.

відповідь:1024

Рішення систем логічних рівнянь методом візуального визначення рекурсії.

Цей метод застосовується, якщо система рівнянь досить проста і порядок збільшення кількості наборів при додаванні змінних очевидний.

Приклад 3.

Скільки різних рішень має система рівнянь

¬x9 ∨ x10 \u003d 1,

де x1, x2, ... x10 - логічні змінні?

У відповіді не потрібно перераховувати всі різні набори значень x1, x2, ... x10, при яких виконана дана система рівності. Як відповідь Вам потрібно вказати кількість таких наборів.

Рішення:

Вирішимо перше рівняння. Диз'юнкція дорівнює 1, якщо хоча б один з її операндів дорівнює 1. Тобто рішеннями є набори:

Для x1 \u003d 0 існують два значення x2 (0 і 1), а для x1 \u003d 1 тільки одне значення x2 (1), такі, що набір (x1, x2) розв'язує рівняння. Всього 3 набору.

Додамо змінну x3 і розглянемо друге рівняння. Воно аналогічно першому, значить для x2 \u003d 0 існують два значення x3 (0 і 1), а для x2 \u003d 1 тільки одне значення x3 (1), такі, що набір (x2, x3) є рішенням рівняння. Всього 4 набори.

Нескладно помітити, що при додаванні черговий змінної додається один набір. Тобто рекурсивна формула кількості наборів на (i + 1) змінних:

N i +1 \u003d N i + 1. Тоді для десяти змінних отримаємо 11 наборів.

відповідь: 11

Рішення систем логічних рівнянь різного типу

Приклад 4.

Скільки існує різних наборів значень логічних змінних x 1, ..., x 4, y 1, ..., y 4, z 1, ..., z 4, які задовольняють всім нижченаведеними умовами?

(X 1 → x 2) ∧ (x 2 → x 3) ∧ (x 3 → x 4) \u003d 1

(Y 1 → y 2) ∧ (y 2 → y 3) ∧ (y 3 → y 4) \u003d 1

(Z 1 → z 2) ∧ (z 2 → z 3) ∧ (z 3 → z 4) \u003d 1

x 4 ∧ y 4 ∧ z 4 \u003d 0

У відповіді не потрібно перераховувати всі різні набори значень змінних x 1, ..., x 4, y 1, ..., y 4, z 1, ..., z 4, при яких виконана дана система рівності.

Як відповідь Вам потрібно вказати кількість таких наборів.

Рішення:

Зауважимо, що три рівняння системи однакові на різних незалежних наборах змінних.

Розглянемо перше рівняння. Кон'юнкція істинна (дорівнює 1) тільки тоді, коли всі її операнди істинні (рівні 1). Імплікація дорівнює 1 на всіх наборах, крім (1,0). Значить, рішенням першого рівняння будуть такі набори x1, x2, x3, x4, в яких 1 не варто лівіше 0 (5 наборів):

Аналогічно, рішеннями другого і третього рівнянь будуть абсолютно такі ж набори y1, ..., y4 і z1, ..., z4.

Тепер проаналізуємо четверте рівняння системи: x 4 ∧ y 4 ∧ z 4 \u003d 0. Рішенням будуть все набори x4, y4, z4, в яких хоча б одна з змінних дорівнює 0.

Тобто для x4 \u003d 0 підійдуть всі можливі набори (y4, z4), а для x4 \u003d 1 підійдуть набори (y4, z4), в яких присутній хоча б один нуль: (0, 0), (0,1), (1, 0).

				Кількість наборів

Загальна кількість наборів 25 + 4 * 9 \u003d 25 + 36 \u003d 61.

відповідь: 61

Рішення систем логічних рівнянь методом побудови рекурентних формул

Метод побудови рекурентних формул застосовується при вирішенні складних систем, в яких порядок збільшення кількості наборів неочевидний, а побудова дерева неможливо через обсягів.

Приклад 5.

Скільки існує різних наборів значень логічних змінних x1, x2, ... x7, y1, y2, ... y7, які задовольняють всім нижченаведеними умовами?

(X1 ∨ y1) ∧ ((x2 ∧ y2) → (x1 ∧ y1)) \u003d 1

(X2 ∨ y2) ∧ ((x3 ∧ y3) → (x2 ∧ y2)) \u003d 1

(X6 ∨ y6) ∧ ((x7 ∧ y7) → (x6 ∧ y6)) \u003d 1

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

Рішення:

Зауважимо, що перші шість рівнянь системи однакові і відрізняються тільки набором змінних. Розглянемо перше рівняння. Його рішенням будуть наступні набори змінних:

позначимо:

число наборів (0,0) на змінних (x1, y1) через A 1,

число наборів (0,1) на змінних (x1, y1) через B 1,

число наборів (1,0) на змінних (x1, y1) через C 1,

число наборів (1,1) на змінних (x1, y1) через D 1.

число наборів (0,0) на змінних (x2, y2) через A 2,

число наборів (0,1) на змінних (x2, y2) через B 2,

число наборів (1,0) на змінних (x2, y2) через C 2,

число наборів (1,1) на змінних (x2, y2) через D 2.

З дерева рішень бачимо, що

A 1 \u003d 0, B 1 \u003d 1, C 1 \u003d 1, D 1 \u003d 1.

Зауважимо, що набір (0,0) на змінних (x2, y2) виходить з наборів (0,1), (1,0) і (1,1) на змінних (x1, y1). Тобто A 2 \u003d B 1 + C 1 + D 1.

Набір (0,1) на змінних (x2, y2) виходить з наборів (0,1), (1,0) і (1,1) на змінних (x1, y1). Тобто B 2 \u003d B 1 + C 1 + D 1.

Аналогічно розмірковуючи, зауважимо, що С 2 \u003d B 1 + C 1 + D 1. D 2 \u003d D 1.

Таким чином, отримуємо рекурентні формули:

A i + 1 \u003d B i + C i + D i

B i + 1 \u003d B i + C i + D i

C i + 1 \u003d B i + C i + D i

D i + 1 \u003d A i + B i + C i + D i

складемо таблицю

набори	обозн.	Формула	кількість наборів
			i \u003d 1	i \u003d 2	i \u003d 3	i \u003d 4	i \u003d 5	i \u003d 6	i \u003d 7
(0,0)	A i	A i + 1 \u003d B i + C i + D i	0	3	7	15	31	63	127
(0,1)	B i	B i + 1 \u003d B i + C i + D i	1	3	7	15	31	63	127
(1,0)	C i	C i + 1 \u003d B i + C i + D i	1	3	7	15	31	63	127
(1,1)	D i	D i + 1 \u003d D i	1	1	1	1	1	1	1

Останньому рівняння (x7 ∨ y7) \u003d 1 задовольняють всі набори, крім тих, в яких x7 \u003d 0 і y7 \u003d 0. У нашій таблиці число таких наборів A 7.

Тоді загальна кількість наборів одно B 7 + C 7 + D 7 \u003d 127 + 127 + 1 \u003d 255

відповідь: 255

Рішення рівняння 1.Перейті до префиксной формі записи рівняння, замінивши позначення заперечень на ¬ 2.Построіть заголовок таблиці істинності спеціального виду 3.Заполніть рядки таблиці істинності для всіх сполучень А і В, підставляючи замість X - 0 або 1. 4.Сформіровать таблицю істинності для X \u003d F (А, B) 5.По таблиці істинності визначити вид функції X, при необхідності скориставшись методами побудови СКНФ і СДНФ, які будуть розглянуті нижче.

Побудова таблиці істинності спеціального виду ¬ ((А + B) · (X A · B)) \u003d ¬ (B + ¬ (X A))

Таблиця істинності X \u003d F (A, B) ABX Відповідає заперечення імплікації В в А ВІДПОВІДЬ:

Комбінаційні схеми логічних пристроїв Базисні елементи (ГОСТ): 1 А В Диз'юнкція А В Еквівалентність & А В Кон'юнкція M2 А В XOR

Комбінаційні схеми логічних пристроїв Базисні елементи (ГОСТ): 1 А В Імплікація & А В Елемент Шеффера & А В Коімплікація 1 А В Елемент Вебба

Приклад схеми F 1 & 1 & & 1M2 B A

Рішення схем 1 Варіант - перетворення схеми в складне логічне вираз і потім - спрощення його за законами логіки. 2 Варіант - побудова таблиці істинності а потім, при необхідності, побудова через СКНФ або СДНФ (див. Нижче). Розглянемо другий варіант, як більш простий і зрозумілий.

Побудова таблиці істинності AB A + B + · B B · A + A B A + · ·

Таблиця істинності F (A, B) ABX Відповідає заперечення імплікації В в А ВІДПОВІДЬ:

СДНФ і СКНФ (визначення) Елементарної кон'юнкція називається кон'юнкція декількох змінних, взятих з запереченням або без заперечення, причому серед змінних можуть бути однакові Елементарної диз'юнкція називається диз'юнкція кількох змінних, взятих з запереченням або без заперечення, причому серед змінних можуть бути однакові Всяку диз'юнкцію елементарних кон'юнкція назвемо диз'юнктивній нормальною формою (ДНФ) Будь-яку кон'юнкцію елементарних диз'юнкцій назвемо кон'юнктівной нормальною формою (ДНФ)

СДНФ і СКНФ (визначення) Зробленої диз'юнктивній нормальною формою (СДНФ), називається ДНФ, в якій немає однакових елементарних кон'юнкція і всі кон'юнкції складаються з одного і того ж набору змінних, в який кожна змінна входить лише один раз (можливо з запереченням). Досконалої кон'юнктівной нормальною формою (СКНФ), називається КНФ, в якій немає однакових елементарних диз'юнкцій і все диз'юнкції складаються з одного і того ж набору змінних, в який кожна змінна входить лише один раз (можливо з запереченням).

Алгоритм отримання СДНФ по таблиці істинності 1.Отметіть рядки таблиці істинності в останньому стовпці яких стоять 1. 2.Випісать для кожної зазначеної рядки кон'юнкцію всіх змінних наступним чином: якщо значення змінної в цьому рядку дорівнює 1, то в кон'юнкцію включати саму цю змінну, якщо дорівнює 0, то її заперечення. 3.Все отримані кон'юнкції зв'язати в диз'юнкцію. Алгоритм отримання СКНФ по таблиці істинності 1.Отметіть рядки таблиці істинності в останньому стовпці яких стоять 0. 2.Випісать для кожної зазначеної рядки диз'юнкцію всіх змінних наступним чином: якщо значення змінної в цьому рядку дорівнює 0, то в кон'юнкцію включати саму цю змінну, якщо дорівнює 1, то її заперечення. 3.Все отримані диз'юнкції зв'язати в кон'юнкцію.

Приклад побудови СKНФ XY F (X, Y) Відзначити нулі 2. диз'юнкцій: X + Y 3. Кон'юнкція: (X + Y) · (X + Y)

Можна виділити різні способи вирішення систем логічних рівнянь. Це зведення до одного рівняння, побудова таблиці істинності і декомпозиція.

завдання:Вирішити систему логічних рівнянь:

Розглянемо метод зведення до одного рівняння . Даний метод передбачає перетворення логічних рівнянь, таким чином, щоб праві їх частини були рівні істинності значення (тобто 1). Для цього застосовують операцію логічного заперечення. Потім, якщо в рівняннях є складні логічні операції, замінюємо їх базовими: «І», «АБО», «НЕ». Наступним кроком об'єднуємо рівняння в одне, рівносильне системі, за допомогою логічної операції «І». Після цього, слід зробити перетворення отриманого рівняння на основі законів алгебри логіки і отримати конкретне рішення системи.

Рішення 1:Застосовуємо інверсію до обох частин першого рівняння:

Уявімо імплікації через базові операції «АБО», «НЕ»:

Оскільки ліві частини рівнянь рівні 1, можна об'єднати їх за допомогою операції "І" в одне рівняння, рівносильне вихідної системі:

Розкриваємо першу дужку за законом де Моргана і перетворюємо отриманий результат:

Отримане рівняння, має одне рішення: A \u003d 0, B \u003d 0 і C \u003d 1.

Наступний спосіб - побудова таблиць істинності . Оскільки логічні величини мають тільки два значення, можна просто перебрати всі варіанти і знайти серед них ті, при яких виконується дана система рівнянь. Тобто, ми будуємо одну загальну таблицю істинності для всіх рівнянь системи і знаходимо рядок з потрібними значеннями.

Рішення 2: Складемо таблицю істинності для системи:

0	0	1	1	0	1

Напівжирним виділена рядок, для якої виконуються умови задачі. Таким чином, A \u003d 0, B \u003d 0 і C \u003d 1.

спосіб декомпозиції . Ідея полягає в тому, щоб зафіксувати значення однієї із змінних (покласти її рівною 0 або 1) і за рахунок цього спростити рівняння. Потім можна зафіксувати значення другої змінної і т.д.

Рішення 3:Нехай A \u003d 0, тоді:

З першого рівняння отримуємо B \u003d 0, а з другого - С \u003d 1. Рішення системи: A \u003d 0, B \u003d 0 і C \u003d 1.

В ЄДІ з інформатики дуже часто потрібно визначити кількість рішень системи логічних рівнянь, без знаходження самих рішень, для цього теж існують певні методи. Основний спосіб знаходження кількості рішень системи логічних рівнянь -заміна змінних. Спочатку необхідно максимально спростити кожне з рівнянь на основі законів алгебри логіки, а потім замінити складні частини рівнянь новими змінними і визначити кількість рішень нової системи. Далі повернутися до заміни і визначити для неї кількість рішень.

завдання:Скільки рішень має рівняння (A → B) + (C → D) \u003d 1? Де A, B, C, D - логічні змінні.

Рішення:Введемо нові змінні: X \u003d A → B і Y \u003d C → D. З урахуванням нових змінних рівняння запишеться у вигляді: X + Y \u003d 1.

Диз'юнкція вірна в трьох випадках: (0; 1), (1; 0) і (1; 1), при цьому X і Y є импликацией, тобто є істинною в трьох випадках і помилковою - в одному. Тому випадок (0; 1) буде відповідати трьом можливим сполученням параметрів. Випадок (1; 1) - буде відповідати дев'яти можливим сполученням параметрів вихідного рівняння. Значить, все можливих рішень даного рівняння 3 + 9 \u003d 15.

Наступний спосіб визначення кількості рішень системи логічних рівнянь - бінарне дерево. Погляньмо на цей метод на прикладі.

завдання:Скільки різних рішень має система логічних рівнянь:

Наведена система рівнянь рівносильна рівняння:

(x 1 → x 2 )*(x 2 → x 3 )*…*(x m -1 → x m) = 1.

Припустимо, що x 1 - істинно, тоді з першого рівняння отримуємо, що x 2 також істинно, з другого - x 3 \u003d 1, і так далі до x m \u003d 1. Значить набір (1; 1; ...; 1) з m одиниць є рішенням системи. нехай тепер x 1 \u003d 0, тоді з першого рівняння маємо x 2 \u003d 0 або x 2 =1.

коли x 2 істинно отримуємо, що інші змінні також істинні, тобто набір (0; 1; ...; 1) є рішенням системи. при x 2 \u003d 0 отримуємо, що x 3 \u003d 0 або x 3 \u003d, І так далі. Продовжуючи до останньої змінної, отримуємо, що рішеннями рівняння є такі набори змінних (m +1 рішення, в кожному рішенні по m значень змінних):

(1; 1; 1; …; 1)

(0; 1; 1; …; 1)

(0; 0; 0; …; 0)

Такий підхід добре ілюструється за допомогою побудови бінарного дерева. Кількість можливих рішень - кількість різних гілок побудованого дерева. Легко помітити, що воно дорівнює m +1.

	дерево	кількість рішень
x 1
x 2
x 3
		…

У разі труднощів у рассужд пах і побудові дереву рішень можна шукати рішення звикористанням таблиць істинності, Для одного - двох рівнянь.

Перепишемо систему рівнянь у вигляді:

І складемо таблицю істинності окремо для одного рівняння:

x 1	x 2	(X 1 → x 2)

Складемо таблицю істинності для двох рівнянь:

x 1	x 2	x 3	x 1 → x 2	x 2 → x 3	(X 1 → x 2) * (x 2 → x 3)

Даною матеріал містить презентацію, в якій представлені методи рішення логічних рівнянь і систем логічних рівнянь в завданні В15 (№ 23, 2015) ЄДІ з інформатики. Відомо, що це завдання є одним з найскладніших серед завдань ЄДІ. Презентація може бути корисна при проведенні уроків по темі "Логіка" в профільних класах, а також при підготовці до здачі ЄДІ.

Завантажити:

Попередній перегляд:

Щоб користуватися попереднім переглядом презентацій створіть собі аккаунт (обліковий запис) Google і увійдіть в нього: https://accounts.google.com

Підписи до слайдів:

Рішення завдання В15 (системи логічних рівнянь) Вишневська М.П., \u200b\u200bМАОУ «Гімназія №3» 18 листопада 2013 року, м Саратов

Завдання В15 - одне з найскладніших в ЄДІ з інформатики !!! Перевіряються вміння: перетворювати вирази, що містять логічні змінні; описувати природною мовою безліч значень логічних змінних, при яких заданий набір логічних змінних праведний підраховувати число двійкових наборів, які відповідають заданим умовам. Найскладніше, тому що немає формальних правил, як це зробити, потрібно здогад.

Без чого не обійтися!

Без чого не обійтися!

Умовні позначення кон'юнкція: A / \\ B, A  B, AB, А & B, A and B диз'юнкція: A \\ / B, A + B, A | B, А or B заперечення:  A, А, not A еквіваленція: A  В, A  B, A  B виключає «або»: A  B, A xor B

Метод заміни змінних Скільки існує різних наборів значень логічних змінних х1, х2, ..., х9, х10, які задовольняють всім перерахованим нижче умовам: ((x1 ≡ x2) \\ / (x3 ≡ x4)) / \\ (¬ (x1 ≡ x2) \\ / ¬ (x3 ≡ x4)) \u003d 1 ((x3 ≡ x4) \\ / (x5 ≡ x6)) / \\ (¬ (x3 ≡ x4) \\ / ¬ (x5 ≡ x6)) \u003d 1 ((x5 ≡ x6 ) \\ / (x7 ≡ x8)) / \\ (¬ (x5 ≡ x7) \\ / ¬ (x7 ≡ x8)) \u003d 1 ((x7 ≡ x8) \\ / (x9 ≡ x10)) / \\ (¬ (x7 ≡ x8) \\ / ¬ (x9 ≡ x10)) \u003d 1 У відповіді не потрібно перераховувати всі різні набори х1, х2, ..., х9, х10, при яких виконується дана система рівності. Як відповідь необхідно вказати кількість таких наборів (демо-версія 2012 року)

Рішення Крок 1. Спрощуємо, виконавши заміну змінних t1 \u003d x1  x2 t2 \u003d x3  x4 t3 \u003d x5  x6 t4 \u003d x7  x8 t5 \u003d x9  x10 Після спрощення: (t1 \\ / t2) / \\ (¬t1 \\ / ¬ t2) \u003d 1 (t2 \\ / t3) / \\ (¬t2 \\ / ¬ t3) \u003d 1 (t3 \\ / t4) / \\ (¬t3 \\ / ¬ t4) \u003d 1 (t4 \\ / t5) / \\ ( ¬t4 \\ / ¬ t5) \u003d 1 Розглянемо одне з рівнянь: (t1 \\ / t2) / \\ (¬t1 \\ / ¬ t2) \u003d 1 Очевидно, воно \u003d 1 тільки якщо одна з змінних дорівнює 0, а інша - 1. скористаємося формулою для вираження операції XOR через кон'юнкцію і диз'юнкцію: (t1 \\ / t2) / \\ (¬t1 \\ / ¬ t2) \u003d t1  t2 \u003d ¬ (t1 ≡ t2) \u003d 1 ¬ (t1 ≡ t2) \u003d 1 ¬ ( t2 ≡ t3) \u003d 1 ¬ (t3 ≡ t4) \u003d 1 ¬ (t4 ≡ t5) \u003d 1

КРОК 2. Аналіз системи ¬ (t1 ≡ t2) \u003d 1 ¬ (t2 ≡ t3) \u003d 1 ¬ (t3 ≡ t4) \u003d 1 ¬ (t4 ≡ t5) \u003d 1 t1 t2 t3 t4 t5 0 1 0 1 0 1 0 1 0 1 Т .до. tk \u003d x2k-1 ≡ x2k (t1 \u003d x1  x2, ....), то кожному значенню tk відповідає дві пари значень x2k-1 і x2k, наприклад: tk \u003d 0 відповідають дві пари - (0,1) і (1, 0), а tk \u003d 1 - пари (0,0) і (1,1).

Шаг3. Підрахунок числа рішень. Кожне t має 2 рішення, кількість t - 5. Таким чином для змінних t існує 2 +5 \u003d 32 рішення. Але кожному t відповідає пара рішень х, тобто вихідна система має 2 * 32 \u003d 64 рішення. Відповідь: 64

Метод виключення частини рішень Скільки існує різних наборів значень логічних змінних х1, х2, ..., х5, y1, y2, ..., y5, які задовольняють всім перерахованим нижче умовам: (x1 → x2) ∧ (x2 → x3) ∧ (x3 → x4 ) ∧ (x4 → x5) \u003d 1; (Y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) ∧ (y4 → y5) \u003d 1; y5 → x5 \u003d 1. У відповіді не потрібно перераховувати всі різні набори х1, х2, ..., х5, y 1, y2, ..., y5, при яких виконується дана система рівності. Як відповідь необхідно вказати кількість таких наборів.

Рішення. Крок 1. Послідовне вирішення рівнянь х1 1 0 х2 1 0 1 х3 1 0 1 1 х4 1 0 1 1 1 х5 1 0 1 1 1 1 Перше рівняння - кон'юнкція декількох операцій імплікації, дорівнює 1, тобто кожна з імплікацій істинна. Імплікація помилкова тільки в одному випадку, коли 1  0, у всіх інших випадках (0  0, 0  1, 1  1) операція повертає 1. Запишемо це у вигляді таблиці:

Крок 1. Послідовне вирішення рівнянь Т.ч. отримано 6 наборів рішень для х1, х2, х3, х4, х5: (00000), (00001), (00011), (00111), (01111), (11111). Міркуючи аналогічно, приходимо до висновку, що для y1, y2, y3, y4, y5 існує такий же набір рішень. Оскільки рівняння ці незалежні, тобто в них немає загальних змінних, то рішенням цієї системи рівнянь (без урахування третього рівняння) буде 6 * 6 \u003d 36 пар «іксів» і «ігрек». Розглянемо третє рівняння: y5 → x5 \u003d 1 Рішенням є пари: 0 0 0 1 1 1 Чи не є рішенням пара: 1 0

Порівняємо отримані рішення Там, де y5 \u003d 1, не підходять x5 \u003d 0. таких пар 5. Кількість рішень системи: 36-5 \u003d 31. Відповідь: 31 Знадобилася комбинаторика !!!

Метод динамічного програмування Скільки різних рішень має логічне рівняння x 1 → x 2 → x 3 → x 4 → x 5 → x 6 \u003d 1, де x 1, x 2, ..., x 6 - логічні змінні? У відповіді не потрібно перераховувати всі різні набори значень змінних, при яких виконано дане рівність. Як відповідь потрібно вказати кількостей про таких наборів.

Рішення Шаг1. Аналіз умови Зліва в рівнянні послідовно записані операції імплікації, пріоритет однаковий. Перепишемо: ((((X 1 → X 2) → X 3) → X 4) → X 5) → X 6 \u003d 1 NB! Кожна наступна змінна залежить не від попередньої, а від результату попередньої імплікації!

КРОК 2. Виявлення закономірності Розглянемо першу імплікації, X 1 → X 2. Таблиця істинності: X 1 X 2 X 1 → X 2 0 0 1 0 1 1 1 0 0 1 1 1 З одного 0 отримали 2 одиниці, а з 1 отримали один 0 і одну 1. Всього один 0 і три 1, це результат першої операції.

КРОК 2. Виявлення закономірності Підключивши до результату першої операції x 3, отримаємо: F (x 1, x 2) x 3 F (x 1, x 2)  x 3 0 0 1 0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 з двох 0 - дві 1, з кожної 1 (їх 3) по одному 0 і 1 (3 + 3)

Крок 3. Висновок формули Т.ч. можна скласти формули для обчислення кількості нулів N i і кількості одиниць E i для рівняння з i змінними:,

Крок 4. Заповнення таблиці Заповнимо зліва направо таблицю для i \u003d 6, обчислюючи число нулів і одиниць за наведеними вище формулами; в таблиці показано, як будується наступний стовпець за попереднім:: число змінних 1 2 3 4 5 6 Число нулів N i 1 1 3 5 11 21 Число одиниць E i 1 2 * 1 + 1 \u003d 3 2 * 1 + 3 \u003d 5 11 21 43 Відповідь: 43

Метод з використанням спрощень логічних виразів Скільки різних рішень має рівняння ((J → K) → (M  N  L))  ((M  N  L) → (¬ J  K))  (M → J) \u003d 1 де J, K, L, M, N - логічні змінні? У відповіді не потрібно перераховувати всі різні набори значень J, K, L, M і N, при яких виконано дане рівність. Як відповідь Вам потрібно вказати кількість таких наборів.

Рішення Зауважимо, що J → K \u003d ¬ J  K Введемо заміну змінних: J → K \u003d А, M  N  L \u003d В Перепишемо рівняння з урахуванням заміни: (A → B)  (B → A)  (M → J) \u003d 1 4. (A  B)  (M → J) \u003d 1 5. Очевидно, що A  B при однакових значеннях А і В 6. Розглянемо останню імплікації M → J \u003d 1 Це можливо, якщо: M \u003d J \u003d 0 M \u003d 0, J \u003d 1 M \u003d J \u003d 1

Рішення Оскільки A  B, то При M \u003d J \u003d 0 отримуємо 1 + К \u003d 0. Немає рішень. При M \u003d 0, J \u003d 1 отримуємо 0 + К \u003d 0, К \u003d 0, а N і L - будь-які, 4 рішення: ¬ J  K \u003d M  N  LKNL 0 0 0 0 0 1 0 1 0 0 1 1

Рішення 10. При M \u003d J \u003d 1 отримуємо 0 + К \u003d 1 * N * L, або K \u003d N * L, 4 рішення: 11. Разом має 4 + 4 \u003d 8 рішень Відповідь: 8 KNL 0 0 0 0 0 1 0 1 0 1 1 1

Джерела інформації: О.Б. Богомолова, Д.Ю. Усенков. В15: нові завдання і нове рішення // Інформатика, № 6, 2012, з. 35 - 39. К.Ю. Поляков. Логічні рівняння // Інформатика, № 14, 2011 року, з. 30-35. http://ege-go.ru/zadania/grb/b15/, [Електронний ресурс]. http://kpolyakov.narod.ru/school/ege.htm, [Електронний ресурс].

УДК 004.023

Семенов Сергій Максимович

Владивостоцький державний університет економіки і сервісу Росія. Владивосток

Про один спосіб вирішення систем логічних рівнянь

Розглядається спосіб визначення кількості рішень системи логічних рівнянь. Спосіб заснований на побудові дерева рішень і визначенні рекурентних співвідношень для рівня N. Застосування розробленого способу забезпечує конструктивний підхід до вирішення завдання В15 ЄДІ.

Ключові слова і словосполучення: системи логічних рівнянь, дерево рішень, рекурентні співвідношення, B15, ЄДІ.

На практиці системи логічних рівнянь корисні при розробці цифрових логічних пристроїв. Вирішенню систем логічних рівнянь присвячена одна із завдань ЄДІ з інформатики. На жаль, різні відомі способи вирішення цього завдання не дозволяють сформувати якийсь один підхід до вирішення цього завдання. В результаті рішення задачі є серйозні труднощі у випускників. Ми пропонуємо спосіб вирішення систем логічних рівнянь, який дозволяє випускнику слідувати цілком певним алгоритмом. Ідея цього способу викладено в. Ми застосували і розвинули цю ідею (побудова дерева рішень), майже не використовуючи таблиці істинності для всього дерева. При вирішенні різних завдань з'ясувалося, що кількість рішень багатьох систем логічних рівнянь підпорядковується рекурентним співвідношенням, таким, як числа Фібоначчі і ін.

Системи логічних рівнянь. Будемо дотримуватися наступних позначень: диз'юнкція (+), кон'юнкція (), що виключає АБО (©), імплікація (-\u003e ■), еквівалентність (\u003d), заперечення (- ■). На малюнках темний гурток позначає 1, а світлий кружок - 0. Fl - кількість рішень при Х1, рівному 1. Fo - кількість рішень при Х1, рівному 0. N - число змінних в системі рівнянь. F (N) \u003d F1 (N) + F0 (N) - загальне число рішень.

Завдання 1. Потрібно знайти кількість рішень системи рівнянь (, тест № 2)

Спочатку вважаємо Х1 \u003d 1. Тоді для першого рівняння значення Х2 і Хз можуть бути будь-якими. Таким чином, дерево побудовано до третього рівня. Далі з урахуванням Х2 і Хз вибираємо Х4. Після цього алгоритм повторюється для кожної трійки змінних (рис. 1). Починаючи з четвертого рівня можна помітити, що Fl (4) \u003d Fl (3) + Fl (1), Fl (5) \u003d Fl (4) + Fl (2). Таким чином, отримуємо Fl (N) \u003d Fl (N-1) + Fl (N-3) (1)

Мал. 1. Завдання 1

З рівняння (1) випливає:

Бх (8) \u003d 16 + 7 \u003d 23,

Fl (9) \u003d 23 + 11 \u003d 34.

Щоб побудувати дерево з нуля, можна скористатися нижньої гілкою з рис. 1. Легко бачити, що вона повторює кореневу, але зі зрушенням вправо на 2, тобто

Разом, F (9) \u003d Fl (9) + Fo (9) \u003d 34 + 16 \u003d 50.

При побудові дерева рішень можна візуально встановити рекурентні співвідношення для визначення кількості рішень на рівні N.

Принцип математичної індукції говорить: нехай є послідовність тверджень Fl, F2, Fз і нехай перше твердження Fl вірно. Ми можемо довести, що з вірності твердження FN слід вірність FN + l. Тоді всі твердження в цій послідовності вірні.

Розглянемо рис. 2 для завдання 1.

к2\u003e 3 х5 хб Х7

Мал. 2. Аналіз дерева рішень

На малюнку 2 виділені фігури, які мають загальну вершину (комбінації значень змінних) для перших п'яти рівнянь системи. У кожному рівнянні задіяні три змінних, тому скульптури складаються зі значень трьох змінних (трьох рівнів дерева). Для того щоб ідентифікувати фігури, можна було б ввести позначення. Однак ми поступимо таким чином: кожній фігурі поставимо у відповідність кількість складових її гуртків (значень змінних). Тоді отримаємо для послідовності наступні рівняння:

4. 7, 4, 4, 1, 7

5. 7, 4, 4, 1, 7, 7, 4.

З рівняння 4 можна бачити, що фігури для рівняння N складаються з фігур рівняння N-1 і фігур рівняння N-3. Важливо, що інших фігур немає і бути не може для даного типу рівнянь, тобто перехід від одного рівняння до іншого проводиться шляхом збільшення числа фігур з обмеженого набору за суворо визначеними правилами. Цей факт і є основним для того, щоб стверджувати по індукції, що для рівняння N + 1 набір фігур буде складатися з фігур рівняння N і фігур рівняння N-2.

Іншим способом ідентифікації фігур є визначення кількості значень змінних на останньому рівні для даного рівняння, тобто потрібно перейти від номера рівняння до номера рівня дерева, оскільки нам потрібно визначити кількість рішень для системи рівнянь, Тоді для побудованого дерева отримаємо послідовність: 1, 2, 4 , 5, 7, 11, 16. Для цієї послідовності справедлива формула: FN \u003d FN-1 + FN-3.

Відповідно до наших міркуваннями ця формула буде вірна для N + 1, а по індукції і для будь-якого N.

Наведений спосіб докази можна використовувати для будь-яких систем подібного типу. На практиці досить визначати рекурентне співвідношення для рівня N оскільки в основі його лежить обмежений набір фігур і способів їх перетворень при переході від рівняння, що відповідає рівню N до рівняння, відповідного рівня N + 1.

Завдання 2. Потрібно знайти кількість рішень системи рівнянь (, 4.16)

(Х1 \u003d Х2) + (Х1 \u003d Х3) \u003d 1 (Х2 \u003d Хз) + (Х2 \u003d Х4) \u003d 1 (Хз \u003d Х4) + (Хз \u003d Х5) \u003d 1 (Х4 \u003d Х5) + (Х4 \u003d Х6) \u003d 1 (Х5 \u003d Х6) + (Х5 \u003d Х7) \u003d 1

XI Х2 ХЗ\u003e: 1 Х5 Хб Х7

Мал. 3. Завдання 2

Для отримання числа рішень завдання 2 можна було не будувати дерево рішень повністю (рис. 3), так як очевидно, що Fl (N) \u003d N. Аналогічно, Fo (N) \u003d N. Разом F (7) \u003d 7 + 7 \u003d 14.

Завдання 3. Потрібно знайти кількість рішень системи рівнянь (, тест № 1)

(Х1 ^ Х2) ■ (Х2 ^ Хз) ■ (Хз ^ Х4) ■ (Х4 ^ Х5) \u003d 1

(Yl ^ Y2) ■ (У2 ^ Yз) ■ (Yз ^ Y4) ■ (Y4 ^ Y5) \u003d 1

(Yl ^ Х1) ■ (У2 ^ Х2) ■ (Yз ^ Хз) ■ (У4 ^ Х4) ■ (Y5 ^ Х5) \u003d 1

На малюнку 4 показані дерева рішень для X і Y і наведені відповідні таблиці істинності.

Мал. 4. Завдання 3

З перших двох рівнянь, оскільки X і Y незалежні, слід, що загальне число рішень F (5) \u003d 6 * 6 \u003d 36. Для того щоб врахувати третє рівняння, потрібно для кожної змінної Y підрахувати, яка кількість наборів з таблиці X не задовольняє рівняння. Імплікація Yi ^ Xi \u003d 0, якщо Yi \u003d 1, а Xi \u003d 0. Інакше кажучи, для Yl \u003d 1 третього рівняння не задовольняють всі рядки з таблиці X, де Х1 \u003d 0. Число таких рядків дорівнює 5. Для Y2 \u003d 1 таких рядків - 4 і т.д. Загальна кількість рядків, які не задовольняють третього рівняння, дорівнює 5 + 4 + 3 + 2 + 1 \u003d 15.

Таким чином, загальне число допустимих рішень одно 36 - 15 \u003d 21. Завдання 4. Потрібно знайти кількість рішень системи рівнянь (, 4.17.а)

(Х1 \u003d Х2) + (Х1 \u003d Х3) \u003d (Х2 \u003d Х3) + (Х2 \u003d Х4) \u003d (Х4 \u003d Х5) + (Х4 \u003d Х6) \u003d (Х5 \u003d Х6) + (Х5 \u003d Х7) \u003d (Хб \u003d Х7) + (Хб \u003d Х8) \u003d (Х5 \u003d Х6) \u003d 0

Мал. 5. Завдання 4

Для даного прикладу складно визначити кінцеву формулу F (N), простіше побудувати дерево рішень до кінця (або хоча б до Х6). На малюнку 5 показано побудоване дерево рішень. В результаті отримуємо F (8) \u003d Fl (8) + Fo (8) \u003d 5 + 5 \u003d 10.

Завдання 5. Необхідно знайти кількість рішень системи рівнянь (, 4.17.б)

(Х1 \u003d Х2) + (Х1 \u003d Х3) \u003d 1 (Х2 \u003d Х3) + (Х2 \u003d Х4) \u003d 1 (Х3 \u003d Х4) + (Х3 \u003d Х5) \u003d 1 (Х4 \u003d Х5) + (Х4 \u003d Х6) \u003d 1 (Х5 \u003d Х6) + (Х5 \u003d Х7) \u003d 1 (Х6 \u003d Х8) \u003d 1

Для цього прикладу, так само як і для попереднього, простіше побудувати дерево рішень до кінця (рис. 6). В результаті отримуємо F (8) \u003d Fl (8) + Fo (8) \u003d 7 + 7 \u003d 14.

Завдання 6. Потрібно знайти кількість рішень системи рівнянь ([!]\u003e 4.17.в)

(Х! 8 "Х2) + (Х2ЕХз) \u003d 1 (Х2фХз) + (Хз \u003d Х4) \u003d 1 (Хз8" Х4) + (Х4 \u003d Х5) \u003d 1 (Х4 © Х5) + (Х5 \u003d Хб) \u003d 1 (Х5фХб) + (Хб \u003d Х7) \u003d 1 (Хб © Х7) + (Х7 \u003d Х8) \u003d 1 Дерево рішень показано на рис. 7.

XI Х2 ХЗ Х4 Х5 Х6 Х7 Х8 XI Х2 ХЗ Х4 Х5 Х6 Х7 Х8

Мал. 6. Завдання 5 Рис. 7. Завдання 6

Для даної системи рівнянь можна було не будувати повне дерево рішень, так як вже з третього - четвертого кроку зрозуміло, що F1 (N) \u003d N. Легко побачити, що Fo (N) можна отримати з дерева, що починається на другому рівні з нуля. Тоді Fo (N) \u003d N. Разом, F (8) \u003d Fl (8) + Fo (8) \u003d 8 + 8 \u003d 16.

Завдання 7. Потрібно знайти кількість рішень системи рівнянь

(Х4ЕХ5) + (Х4 © Х6) \u003d 1 (Х5 © Хб) + (Х5 © Х7) \u003d 1

Зауважимо, що якщо X! \u003d X2 \u003d 1, то перше рівняння виконується при xз \u003d 0. Побудуємо спочатку дерево для Xl \u003d X2 \u003d 1 (рис. 8). Тоді число рішень Fl (N) \u003d Fll (N) + Flo (N).

XI Х2 ХЗ Х4 Х5 Х6 Х7 Х8

Мал. 8. Завдання 7

З малюнка 8 видно, що число рішень F11 (N) \u003d F11 (N-1) + F11 (N-2). Інакше кажучи, число рішень описується числами Фібоначчі. Другу гілку дерева для F10 можна не будувати, так як вона виходить з рис. 1, починаючи з другого рівня. Тоді F10 (N) \u003d F11 (N + 1). Остаточно отримуємо, що Fll (8) \u003d +1 з і Flo (8) \u003d Fll (9) \u003d 1з + 8 \u003d 21. Тоді Fl (8) \u003d Fll (8) + Flo (8) \u003d 1з + 21 \u003d з4.

Для того щоб отримати F0 (N), також необов'язково будувати дерево рішень, оскільки воно виходить з рис. 1 починаючи з третього рівня. Тоді Fo (N) \u003d Fll (N + 2). Звідси отримуємо, що Fo (8) \u003d Fll (10) \u003d Fll (9) + Fll (8) \u003d 21 + 1З \u003d з4. Таким чином, загальне число рішень F (8) \u003d F1 (8) + F0 (8) \u003d з4 + з4 \u003d 68.

Завдання 8. Потрібно знайти кількість рішень системи рівнянь ([з], завдання 2)

(Х1 + Х2) ^ (Хз + Х4) \u003d 1 (Хз + Х4) ^ (Х5 + Х6) \u003d 1 (Х5 + Х6) ^ (Х7 + Х8) \u003d 1 (Х7 + Х8) ^ (Х9 + Х10) \u003d 1

Зробимо підстановку (Х1 + Х2) \u003d Yl і т.д. і отримаємо систему рівнянь:

^ ^ Y2 \u003d 1 Y2 ^ Yз \u003d 1 Yз ^ Y4 \u003d 1 Y4 ^ Y5 \u003d 1

Дерево рішень і таблиця істинності для цієї системи в точності збігаються з деревом і таблицею, зображеними на рис. 4. З урахуванням підстановки відзначимо, що вираз (Х1 + Х2) дорівнює одиниці в трьох випадках (за винятком випадку, коли обидві змінні дорівнюють нулю).

Оскільки змінні Y незалежні, то для першого рядка таблиці істинності, показаної на рис. 4, число різних комбінацій дорівнює 35, для другого рядка - 34 і т.д. Загальна кількість різних комбінацій дорівнює 35 + 34 + 33 + 32 + 31 + 30 \u003d 364.

Завдання 9. Чи потрібно знайти кількість рішень системи рівнянь (, завдання 4)

(^ ^ Ред) ■ (-X ^ xз) ■ № ^ X) ■ (-X ^ Кз) \u003d 1 № ^ Y2) ■ (У1 ^ Yз) ■ (-Г1 ^ Y4) ■ (У1 ^ Y5) \u003d 1 (-X + Y 1) ■ (-X + Y5) \u003d 1

Для X і Y маємо такі дерева рішень

Мал. 9. Завдання 8

З урахуванням третього рівняння отримуємо наступні чотири набори комбінацій:

А - З: 4 * 4 \u003d 16 ((- £ 1 + Y 1) ■ (-X + Y5) \u003d (0 + 1) ■ (0 + 1) \u003d 1) У - З: 4 * 4 \u003d 16 ( (-X + Y 1) ■ (-X + Y5) \u003d (1 + 1) ■ (1 + 1) \u003d 1) А - D: \u003d 0 (0 + 0) ■ (-X + Y5) \u003d 0) В - D: 4 * 4 \u003d 16 (1 + 0) ■ (1 + Y5) \u003d 1) Всього виходить 48 наборів рішень.

Завдання 10. Потрібно знайти кількість рішень системи рівнянь (^ 1 \u003d ред) + (xз \u003d X)) ■ \u003d ред) + ФЗ \u003d X4)) \u003d 1 ((xз \u003d X4) + (X5 \u003d X6)) ■ ( - (X \u003d X) + - (X \u003d X6)) \u003d 1 ((X5 \u003d X6) + ^ 7 \u003d X «)) ■ (- (X \u003d X6) + - (^ 7 \u003d X8)) \u003d 1

((X7 \u003d X8) + (X9 \u003d Xlo)) ■ (- ^ 7 \u003d X8) + \u003d Xlo)) \u003d 1 Проведемо заміну: (Xl \u003d ред) \u003d Yl (xз \u003d X4) \u003d Y2

(Х5 \u003d Х) \u003d Yз (Х7 \u003d Х8) \u003d Y4 (Х9 \u003d Х10) \u003d Y5

(У ^ 2) ■ (-'+ ^) \u003d 1

(Y2 + Yз) ■ № + -Тз) \u003d 1

(Yз + Y4) ■ № + ^) \u003d 1

(Y4 + Y5) ■ (^ 4 + ^) \u003d 1

На малюнку 10 показано дерево рішень

У1 У2 УЗ У4 У5

Мал. 10. Завдання 10

Завдання 11. Потрібно знайти кількість рішень системи рівнянь (, Приклад 2)

Х1 + Х2 \u003d 1 -х2 + Хз \u003d 1

На малюнку 11 показано дерево рішень. Ми обмежилися чотирма рівнями замість десяти, так як очевидно, що F1 (N) \u003d 1 і F0 (N) \u003d N. Тоді Р (И) \u003d Р1 (И) + босі) \u003d 1 + N. У нашому випадку Р (10 ) \u003d 1 + 10 \u003d 11.

Мал. 11. Завдання 11

Завдання 12. Потрібно знайти кількість рішень системи рівнянь (, Приклад з)

(Х1 \u003d Х2) + (Х2 \u003d Хз) \u003d 1

(Х1 \u003d Хз) + (Хз \u003d Х4) (Х1 \u003d Х4) + (Х4 \u003d Х5) (Х1 \u003d Х5) + (Х5 \u003d Х6) (Х1 \u003d Х6) + (Х6 \u003d Х7) (Х1 \u003d Х7) + (Х7 \u003d Х8) (Х1 \u003d Х) + (Х8 \u003d Х9) (Х1 \u003d Х9) + (Х9 \u003d Х10) (Х1 \u003d Х10) \u003d 0

Мал. 12. Завдання 12

Побудувавши дерево рішень з «1» (обмежимося п'ятьма рівнями), зауважимо, що Fl (N) \u003d N. Причому значення Хн складаються з N-1 значень «0» і одного значення «1». Однак останнє рівняння в нашій системі забороняє значення «1» для Х10. Тому число рішень Fl (10) \u003d 10 - 1. Неважко помітити, що дерево рішень з «0» буде симетричним (замість нулів будуть одиниці). Тому F0 \u003d 10 - 1. Повністю

F (N) \u003d 2 х 9 \u003d 18.

Завдання 13. Потрібно знайти кількість рішень системи рівнянь (, Приклад 4)

- (Х1 \u003d Х2) + (Хз \u003d Х4) \u003d 1

- (Хз \u003d Х4) + (Х5 \u003d Х) \u003d 1

- (Х \u003d Х) + (Х7 \u003d Х) \u003d 1

- (Х7 \u003d Х8) + (Х9 \u003d Х10) \u003d 1

Проведемо заміну:

(Х1 \u003d Х2) \u003d Yl

(Х5 \u003d Х) \u003d Yз

(Х7 \u003d Х8) \u003d Y4

(Х9 \u003d Х10) \u003d Y5

Перепишемо систему рівнянь з урахуванням заміни:

З завдання 11 видно, що F (5) \u003d 5 + 1 \u003d 6. Таблиця істинності представлена \u200b\u200bна рис. 13.

У1 У2 УЗ У4 У5

Мал. 13. Завдання 13

З урахуванням підстановки відзначимо, що вираз ^ \u003d X2) дорівнює одиниці (або нулю) в двох випадках (коли значення змінних збігаються). Ураховуючи незалежність змінних для кожного рядка таблиці отримуємо, що число наборів рішень дорівнює 25 \u003d 32. Загальна кількість наборів рішень дорівнює 6 * 32 \u003d 192.

Завдання 14. Потрібно знайти кількість рішень системи рівнянь (, завдання 1)

((Х \u003d ред) ■ (xз \u003d X4)) + (4X1 \u003d ред) ■ - (X \u003d X)) \u003d 0 ((xз \u003d X4) ■ (X5 \u003d X6)) + (4X3 \u003d X4) ■ - (X \u003d X6)) \u003d 0

((X5 \u003d X) ■ (X7 \u003d X8)) + (- (X \u003d X6) ■ 4X7 \u003d X8)) \u003d 0 ((X7 \u003d X8) ■ (X9 \u003d X «,)) + (- (^ 7 \u003d X8) ■ ^ 9 \u003d Xlo)) \u003d 0 Проведемо заміну:

Ред) \u003d Yl (X \u003d ^ 4) \u003d Y2

(X5 \u003d X6) \u003d Yз ^ 7 \u003d X8) \u003d Y4 ^ 9 \u003d Xlo) \u003d Y5

Перепишемо систему рівнянь з урахуванням заміни:

(ВУЛ) + (-У «■ -У2) \u003d 0

(Y2 Yз) + (-У2 ■ -У3) \u003d 0 (У3-У4) + (-У3 ■ -У4) \u003d 0 (У4-У5) + (-У4 ■ -У5) \u003d 0

(У2 \u003d Yз) \u003d 0 (Уз \u003d В4) \u003d 0 (У4 \u003d У5) \u003d 0

На малюнку 14 показано дерево рішень

У1 У2 УЗ У4 У5

Мал. 14. Завдання 14

З урахуванням підстановки відзначимо, що вираз (Х1 \u003d Х2) дорівнює одиниці (або нулю) в двох випадках (коли значення змінних збігаються). Ураховуючи незалежність змінних для кожного дерева отримуємо, що число наборів рішень дорівнює 25 \u003d з2. Загальна кількість наборів рішень одно 64.

Завдання 15. Потрібно знайти кількість рішень системи рівнянь (, завдання 2)

(Х4 Х5) + (-Х4 -Х5) + (Х4 \u003d Х) \u003d 1

(Х5 Х) + (Х -Х6) + (Х5 \u003d Х7) \u003d 1

(X Х7) + (Х -Х7) + (Х \u003d Х8) \u003d 1

(Х7 Х) + (-Х7 -Х8) + (Х7 \u003d Х9) \u003d 1

(Х8 Х9) + (Х -Х9) + (Х8 \u003d Х10) \u003d 1

(Х1 \u003d Х2) + (Х1 \u003d Хз) \u003d 1

(Х \u003d Хз) + (Х2 \u003d Х4) \u003d 1

(Хз \u003d Х4) + (Хз \u003d Х5) \u003d 1

(Х4 \u003d Х5) + (Х4 \u003d Х) \u003d 1

(Х5 \u003d Х6) + (Х5 \u003d Х7) \u003d 1

(Х \u003d Х7) + (Х6 \u003d Х8) \u003d 1

(Х7 \u003d Х8) + (Х7 \u003d Х9) \u003d 1

(Х \u003d Х9) + (Х8 \u003d Х10) \u003d 1

Але ця система повторює систему з завдання 5, тільки без умови обмеження і для N \u003d 10. Тоді число рішень одно F (N) \u003d F1 (N) + F0 (N) \u003d N + N. При N \u003d 10 отримуємо F (N ) \u003d 20.

Завдання 16. Потрібно знайти кількість рішень системи рівнянь (, завдання 3)

(Х1 Х2) + (-Х1 -х2) + (Х1 \u003d Хз) \u003d 1

(Х2 Хз) + (Х -Хз) + (Х2 \u003d Х4) \u003d 1

(Хз Х4) + (-Хз -Х4) + (Хз \u003d Х5) \u003d 1

(Х4 Х5) + (Х -Х5) + (Х4 \u003d Хб) \u003d 1

(Х5 Хб) + (Х -бавовна) + (Х5 \u003d Х7) \u003d 1

(Хб Х7) + (-бавовна -Х7) + (Хб \u003d Х8) \u003d 1

(Х7 Х8) + (-Х7 -Х8) + (Х7 \u003d Х9) \u003d 1

(Х8 Х9) + (-Х8 -Х9) + (Х8 \u003d Х10) \u003d 0

Цю систему рівнянь, як і в попередньому завданні, можна переписати у вигляді:

(XI \u003d Х2) + (XI \u003d Хз) \u003d 1 (Х \u003d Хз) + (Х2 \u003d X) \u003d 1 (Хз \u003d X) + (Хз \u003d Х5) \u003d 1 (X \u003d Х5) + (Х4 \u003d Хб) \u003d 1 (Х5 \u003d Хб) + (Х5 \u003d Х7) \u003d 1 (Хб \u003d Х7) + (Хб \u003d Х8) \u003d 1 (Х \u003d Х8) + (Х7 \u003d Х9) \u003d 1 (Х \u003d Х9) + (Х8 \u003d ХХС) \u003d 0

З останнього рівняння легко перевірити, що після N \u003d 8 число рішень перестає зростати. Тоді F (10) \u003d F (8) \u003d 8 + 8 \u003d 16.

Завдання 17. Потрібно знайти кількість рішень системи рівнянь (, завдання 4)

(Х1 Х2) + (-Х1 -х2) + (Х2 Хз) + (-х2 -Хз) \u003d 1

(Х2 Хз) + (-х2 -Хз) + (Хз Х) + (-Хз ■ -Х4) \u003d 1

(Хз Х) + (-Хз -Х4) + (Х4 Х5) + (-Х4 -Х5) \u003d 1

(Х4 X) + (Х -Х5) + (Х5 Хб) + (-Х5 -бавовна) \u003d 1

(Х5 Хб) + (Х -бавовна) + (Хб Х7) + (-бавовна ■ -Х7) \u003d 1

(Хб Х7) + (-бавовна -Х7) + (Х7 Х8) + (-Х7 -Х8) \u003d 1

(Х7 Х) + (-Х7 -Х8) + (Х8 Х9) + (-Х8 -Х9) \u003d 1

(Х8 Х9) + (-Х8 -Х9) + (Х9 Х10) + (-Х9 ■ -Х10) \u003d 1

Зауважимо, що систему рівнянь можна переписати у вигляді:

(Х \u003d Х2) + (X \u003d Хз) \u003d 1 (Х \u003d Хз) + (X \u003d Х) \u003d 1 (Хз \u003d Х4) + (Х4 \u003d Х5) \u003d 1 (Х \u003d Х5) + (Х5 \u003d Хб) \u003d 1 (Х5 \u003d Хб) + (Хб \u003d Х7) \u003d 1

(Хб \u003d Х7) + (Х7 \u003d X) \u003d 1 (Х7 \u003d Х8) + (Х8 \u003d Х9) \u003d 1 (Хв \u003d X 9) + (Х9 \u003d Х10) \u003d 1

На малюнку 15 дерево побудовано до п'ятого рівня і видно, що число рішень описується числами Фібоначчі, тобто Fl (N) \u003d Fl (N-1) + Fl (N-2). Тоді Fl (10) \u003d 89. Легко перевірити, що для F0 (N) дерево буде симетрично. Тому Fo (10) \u003d 89. Б (10) \u003d р1 (10) + Ро (10) \u003d 89 + 89 \u003d 178.

Мал. 15. Завдання 17

Завдання 18. Потрібно знайти кількість рішень системи рівнянь (, завдання 5)

(Х1 Х2) + (-Х1 -х2) + (Х2 Хз) + (-х2 ■ -Хз) \u003d 1

(Х2 Хз) + (Х -Хз) + (Хз Х4) + (-Хз -Х4) \u003d 1

(Хз Х4) + (-Хз -Х4) + (Х4 Х5) + (-Х4 ■ -Х5) \u003d 1

(Х4 Х5) + (-Х4 -Х5) + (Х Хб) + (-Х5 ■ -бавовна) \u003d 1

(Х5 Хб) + (-Х5 -бавовна) + (Хб Х7) + (-бавовна ■ -Х7) \u003d 1

(Хб Х7) + (-бавовна -Х7) + (Х7 Х8) + (-Х7 ■ -Х8) \u003d 1

(Х7 Х8) + (-Х7 -Х8) + (Х8 Х9) + (-Х8 -Х9) \u003d 1

(Х8 Х9) + (-Х8 -Х9) + (Х9 Х10) + (-Х9 ■ -Х10) \u003d 0

Зауважимо, що систему рівнянь можна переписати у вигляді:

(Х \u003d Х2) + (Х2 \u003d Х3) \u003d 1 (Х2 \u003d Хз) + (Хз \u003d Х4) \u003d 1

(Хз \u003d Х) + (Х4 \u003d Х5) \u003d 1 (Х \u003d Х5) + (Х5 \u003d Хб) \u003d 1 (Х \u003d Хб) + (Хб \u003d Х7) \u003d 1 (Хб \u003d Х7) + (Х7 \u003d Х8) \u003d 1 (Х7 \u003d Х8) + (Х8 \u003d Х9) \u003d 1 (Х8 \u003d Х 9) + (Х \u003d Х10) \u003d 0

Завдання 18 схоже на завдання 17, проте останнє рівняння призводить до того, що починаючи з сьомого рівня число рішень не збільшується. В результаті F (10) \u003d Fl (10) + Fo (10) \u003d Fl (7) + Fo (7) \u003d 21 + 21 \u003d 42.

Завдання 19. Потрібно знайти кількість рішень системи рівнянь (, завдання б)

(Х \u003d Х2) + (Х \u003d Х10) \u003d 1 (Х \u003d Хз) + (Х2 \u003d Х10) \u003d 1 (Хз \u003d Х4) + (X \u003d Х10) \u003d 1 (Х \u003d Х5) + (Х \u003d Х10) \u003d 1 (Х \u003d Хб) + (Х5 \u003d Х10) \u003d 1 (Хб \u003d Х7) + (Хб \u003d Х10) \u003d 1 (Х7 \u003d Х) + (Х \u003d Х10) \u003d 1 (Х8 \u003d Х9) + (Х \u003d Х10) \u003d 1 (Х9 \u003d Х10) + (Х9 \u003d Х10) \u003d 1 (Х \u003d Х10) \u003d 0

- - - - * - - - - * - про

Мал. 1б. завдання 19

Дерева рішень для отримання F1 (N) і F0 (N) показані на рис. 1б. Однак рівняння (Х9 \u003d Х10) \u003d 1 не може бути виконано. Тому система рівнянь не має рішень.

Завдання 20. Потрібно знайти кількість рішень системи рівнянь (, завдання 7)

(Х ^ Х2) + (Х ^ Хз) \u003d 1 (Х2 ^ Хз) + (Х2 * Х4) \u003d 1 (Хз ^ Х4) + (Хз ^ Х5) \u003d 1 (Х ^ Х5) + (Х4 ^ Хб) \u003d 1 (Х5 ^ Хб) + (Х5 ^ Х7) \u003d 1 (Хб ^ Х7) + (Хб ^ Х8) \u003d 1

(X7 ^ Xs) + (X7 ^ X9) \u003d 1 (Xs ^ X9) + (Xs ^ X10) \u003d 1

На малюнку 17 показано дерево рішень з «1».

Мал. 17. Завдання 20 Рис. 18. Завдання 20

Замість десяти рівнів ми обмежилися п'ятьма, так як завдання схожа із завданням 17. Однак з «0» дерево буде виглядати інакше (рис. 18).

Зауважимо, що F0 (N) \u003d Fx (N + 1) - 1. Тоді Fx (10) \u003d 89, а F0 (10) \u003d Fx (11) - 1 \u003d 144 - 1. Разом, F (10) \u003d F1 (10) + F0 (10) \u003d 89 + 143 \u003d 232.

На закінчення наведемо програму на бейсике VBA, за допомогою якої можна вирішувати системи логічних рівнянь. Програма може знадобитися при складанні нових систем рівнянь. На малюнку 19 показана програма, за допомогою якої вирішується система рівнянь із завдання 7.

У програмі, показаної на рис. 19, масив m і змінна c містять значення змінних, які відповідають системі рівнянь із завдання 7. Програма видає відповідь 68. В програмі використовується факт, що число різних наборів значень n логічних змінних одно 2n. Для отримання всіх наборів потрібно виконати цикл від 0 до 2n-1. Мінлива циклу на кожному кроці перекладається в двійкову систему, результат записується в масив m, і потім вже перевіряються умови з системи рівнянь. Для вирішення іншої системи рівнянь досить поміняти розмірність масиву m, змінити значення змінної vg (дорівнює розмірності) і поміняти умови перевірки.

Dim m (S) As Integer, k As Integer, j. As Integer. _ J As Integer. N As Integer, vg As Integer Dim з As String vg \u003d S j-0

For 1 To 2 ■ "" ■ vg "Цикл по ^ від 1 до 2n. Де n \u003d ,. g For k \u003d 1 To vg

N \u003d) .- 1: Двійково e ін e ц ставлю e нне починається з нуля k \u003d 1

Do "^ Tiils N\u003e 0" Переклад e двійкову сЯстему m (k) \u003d N Mod 2 К \u003d N ■ 2 k \u003d k +! Loop

Ifim (l) Про m (2) Or m (l) 0- ni (3)) And_ "Умови рівнянні (m (2)

c \u003d "" "Змінна з на кожному кроці оудет містити рішення системи For k \u003d 1 Те vg

з \u003d з - Foimat (m (k) j Next k j-j-1 End If Next I.

Ms ^ Eox i "Кількість рішень

VvVvVlVvVvv- -1 i

Мал. 19. Програма для завдання 7

1. Крилов С.С. ЄДІ 2014. Інформатика. Тематичні тестові завдання / С.С. Крилов, Д.М. Ушаков. - М .: Изд-во «Іспит». - 245 с.

2. Сайт К.Ю. Полякова. Режим доступу: http: //kpolyakov.namd.-ru/download/inf-2011-14.pdf

3. Методичний сертифікований курс фірми «1С» «Підготовка до ЄДІ з інформатики. Модуль 1 ». - М .: Изд-во «1С». - 218 с.

4. Успішно скласти еге з інформатики. Режим доступу: http://infoegehelp.ru/index.php?Itemid\u003d77&id\u003d103&option\u003dcom_con-