Скільки розв'язків має логічне рівняння. логіка. Логічні функції. Розв'язання рівнянь. Де можна вирішити логічне рівняння онлайн

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

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

приклад 1.

Скільки існує різних наборів значень логічних змінних 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 перемножуються:

Складемо кількість наборів: 1+3+9+27+81=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) = z1, (x2 ≡ y2) = z2,…. ,(x9 ≡ y9) = z9

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

(¬ z1 ≡ z2) ∧ (¬ z2 ≡ z3) ∧ …..∧ (¬ z8 ≡ z9)

Еквівалентність істинна, тільки якщо обидва операнди рівні. Розв'язаннями цього рівняння будуть два набори:

Т.к. zi = (xi ≡ yi), то значенню zi = 0 відповідають два набори (xi, yi): (0,1) та (1,0), а значенню zi = 1 - два набори (xi, yi): (0 ,0) та (1,1).

Тоді першому набору z1, z2, ..., z9 відповідає 29 наборів (x1, y1), (x2, y2), …, (x9, y9).

Стільки ж відповідає другому набору z1, z2, …, z9. Тоді всього 29 +29 = 1024 наборів.

Відповідь: 1024

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

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

приклад 3.

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

¬x9 ∨ x10 = 1,

де 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 +1 = 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) = 1

(y 1 → y 2) ∧ (y 2 → y 3) ∧ (y 3 → y 4) = 1

(z 1 → z 2) ∧ (z 2 → z 3) ∧ (z 3 → z 4) = 1

x 4 ∧ y 4 ∧ z 4 = 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 = 0. Рішенням будуть усі набори x4, y4, z4, у яких хоча б одна із змінних дорівнює 0.

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

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

Відповідь: 61

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

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

Приклад 5.

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

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

(x2 ∨ y2) ∧ ((x3 ∧ y3) → (x2 ∧ y2)) = 1

(x6 ∨ y6) ∧ ((x7 ∧ y7) → (x6 ∧ y6)) = 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) через D1.

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

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

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

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

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

A1=0, B1=1, C1=1, D1=1.

Зауважимо, що набір (0,0) на змінних (x2, y2) виходить із наборів (0,1), (1,0) та (1,1) на змінних (x1, y1). Тобто. A 2 = B1 + C1 + D1.

Набір (0,1) на змінних (x2, y2) виходить із наборів (0,1), (1,0) та (1,1) на змінних (x1, y1). Тобто. B2 = B1 + C1 + D1.

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

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

A i+1 = B i + C i + D i

B i+1 = B i + C i + D i

C i+1 = B i + C i + D i

D i+1 = A i +B i + C i + D i

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

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

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

Відповідь: 255

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

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

Таблиця істинності X=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)

Як вирішувати деякі завдання розділів A та B іспиту з інформатики

Урок №3. логіка. Логічні функції. Розв'язання рівнянь

1. Велика кількість завдань ЄДІ присвячена логіці висловлювань. Для вирішення більшості їх достатньо знання основних законів логіки висловлювань, знання таблиць істинності логічних функцій однієї та двох змінних. Наведу основні закони логіки висловлювань.
   Комутативність диз'юнкції та кон'юнкції:
   a ˅ b ≡ b ˅ a
2. a^b≡b^a
   Дистрибутивний закон щодо диз'юнкції та кон'юнкції:
   a ˅ (b^с) ≡ (a ˅ b) ^(a ˅ с)
3. Заперечення заперечення:
   ¬(¬а) ≡ а
4. Несуперечність:
   a ^ ¬а ≡ false
5. Виключне третє:
   a ˅ ¬а ≡ true
6. Закони де-Моргана:
   ¬(а ˅ b) ≡ ¬а ˄ ¬b
   ¬(а ˄ b) ≡ ¬а ˅ ¬b
7. Спрощення:
   a ˄ a ≡ a
   a ˅ a ≡ a
   a ˄ true ≡ a
   a ˄ false ≡ false
8. Поглинання:
   a ˄ (a ˅ b) ≡ a
   a ˅ (a ˄ b) ≡ a
9. Заміна імплікації
   a → b ≡ ¬a ˅ b
10. Заміна тотожності
    a ≡ b ≡(a ˄ b) ˅ (¬a ˄ ¬b)

Подання логічних функцій

Будь-яку логічну функцію від n змінних – F(x 1 , x 2 , … x n) можна встановити таблицею істинності. Така таблиця містить 2 n наборів змінних, кожному за яких задається значення функції цьому наборі. Такий спосіб хороший, коли кількість змінних відносно невелика. Вже при n > 5 уявлення стає погано доступним для огляду.

Інший спосіб полягає в тому, щоб задавати функцію деякою формулою, використовуючи досить відомі прості функції. Система функцій (f 1 , f 2 , ... f k ) називається повною, якщо будь-яку логічну функцію можна виразити формулою, що містить лише функції f i .

Повною є система функцій (¬, ˄, ˅). Закони 9 і 10 є прикладами, що демонструють, як імплікація та тотожність виражається через заперечення, кон'юнкцію та диз'юнкцію.

Фактично повною є і система з двох функцій - заперечення та кон'юнкції або заперечення та диз'юнкції. З законів де-Моргана випливають уявлення, що дозволяють виразити кон'юнкцію через заперечення та диз'юнкцію і відповідно висловити диз'юнкцію через заперечення та кон'юнкцію:

(а ˅ b) ≡ ¬(¬а ˄ ¬b)
(а ˄ b) ≡ ¬(¬а ˅ ¬b)

Парадоксально, але повною є система, що складається лише з однієї функції. Існують дві бінарні функції - антикон'юкція і антидиз'юнкція, звані стрілкою Пірса і штрих Шеффера, що представляють порожню систему.

До складу базових функцій мов програмування включають зазвичай тотожність, заперечення, кон'юнкцію та диз'юнкцію. У завданнях ЄДІ поряд із цими функціями часто зустрічається імплікація.

Розглянемо кілька простих завдань, що з логічними функціями.

Завдання 15:

Дано фрагмент таблиці істинності. Яка із трьох наведених функцій відповідає цьому фрагменту?

1. (X 1 → X 2) ˄ ¬ X 3 ˅ X 4
2. (¬ X 1 ˄ X 2) ˅ (¬ X 3 ˄ X 4)
3. ¬ X 1 ˅ X 2 ˅ (X 3 ˄ X 4)

Функція за номером 3.

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

Завдання 16:

Яке з наведених чисел задовольняє умову:

(цифри, починаючи зі старшого розряду, йдуть у порядку спадання) → (число – парне) ˄ (молодша цифра – парна) ˄ (старша цифра – непарна)

Якщо таких чисел кілька, вкажіть найбільше.

1. 13579
2. 97531
3. 24678
4. 15386

Умову задовольняє номер під номером 4.

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

Завдання 17: Два свідки дали такі показання:

Перший свідок: Якщо А винний, то В і винний, а С – невинний.

Другий свідок: Винні двоє. А точно винен і винен один із тих, хто залишився, але хто саме сказати не можу.

Які висновки про винність А, В і С можна зробити на підставі показань свідків?

Відповідь: З показань свідків випливає, що А і В винні, а С - невинний.

Рішення: Звичайно, відповідь можна дати, ґрунтуючись на здоровому глузді. Але давайте розглянемо, як це можна зробити строго та формально.

Перше, що потрібно зробити – це формалізувати висловлювання. Введемо три логічні змінні - А, В і С, кожна з яких має значення true (1), якщо відповідний підозрюваний винен. Тоді показання першого свідка задаються формулою:

A → (B ˄ ¬C)

Свідчення другого свідка задаються формулою:

A ˄ ((B ˄ ¬C) ˅ (¬B ˄ C))

Показання обох свідків вважаються істинними і є кон'юнкцією відповідних формул.

Побудуємо таблицю істинності цих показань:

Сумарні показання свідків істинні тільки в одному випадку, що призводять до однозначної відповіді – А і В винні, а С – невинний.

З аналізу цієї таблиці також випливає, що показання другого свідка є більш інформативними. З істинності його показання випливає лише два можливі варіанти - А і В винні, а С - невинний або А і С винні, а В - невинний. Свідчення першого свідка менш інформативні – існує 5 різних варіантів, що відповідають його показанням Спільно показання обох свідків дають однозначну відповідь про винність підозрюваних.

Логічні рівняння та системи рівнянь

Нехай F(x 1 , x 2 , … x n) – логічна функція від змінних. Логічне рівняння має вигляд:

F(x 1 , x 2 , … x n) = З,

Константа має значення 1 або 0.

Логічне рівняння може мати від 0 до 2 n різних рішень. Якщо З дорівнює 1, то рішеннями є ті набори змінних з таблиці істинності, у яких функція F приймає значення істина (1). Решта наборів є рішеннями рівняння при C, що дорівнює нулю. Можна завжди розглядати лише рівняння виду:

F(x 1 , x 2 , … x n) = 1

Справді, нехай задано рівняння:

F(x 1 , x 2 , … x n) = 0

У цьому випадку можна перейти до еквівалентного рівняння:

¬F(x 1 , x 2 , …x n) = 1

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

F 1 (x 1 x 2 … x n) = 1

F 2 (x 1 x 2 … x n) = 1

F k (x 1 x 2 … x n) = 1

Рішенням системи є набір змінних, у якому виконуються все рівняння системи. У термінах логічних функцій отримання рішення системи логічних рівнянь слід знайти набір, у якому істинна логічна функція Ф, що представляє кон'юнкцію вихідних функцій F:

Ф = F 1 ˄ F 2 ˄ … F k

Якщо кількість змінних невелика, наприклад, менше 5, то неважко побудувати таблицю істинності функції Ф, що дозволяє сказати, скільки рішень має система і які набори, дають рішення.

У деяких завданнях ЄДІ щодо знаходження рішень системи логічних рівнянь число змінних сягає значення 10. Тоді побудувати таблицю істинності стає практично нерозв'язним завданням. Для вирішення завдання потрібен інший підхід. Для довільної системи рівнянь немає загального способу, відмінного від перебору, що дозволяє вирішувати такі завдання.

У пропонованих на іспиті завдання рішення зазвичай ґрунтується на обліку специфіки системи рівнянь. Повторюю, крім перебору всіх варіантів набору змінних, загального способу розв'язання задачі немає. Рішення потрібно будувати виходячи зі специфіки системи. Найчастіше корисно провести попереднє спрощення системи рівнянь, використовуючи відомі закони логіки. Інший корисний прийом розв'язання цього завдання полягає в наступному. Нам цікаві в повному обсязі набори, лише ті, у яких функція Ф має значення 1. Замість побудови повної таблиці істинності будуватимемо її аналог — бінарне дерево рішень. Кожна гілка цього дерева відповідає одному рішенню та задає набір, на якому функція Ф має значення 1. Число гілок у дереві рішень збігається з числом рішень системи рівнянь.

Що таке бінарне дерево рішень та як воно будується, поясню на прикладах кількох завдань.

Завдання 18

Скільки існує різних наборів значень логічних змінних x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, які задовольняють системі двох рівнянь?

Відповідь: Система має 36 різних рішень.

Рішення: Система рівнянь включає два рівняння. Знайдемо число рішень для першого рівняння, що залежить від 5 змінних - x1, x2, … x5. Перше рівняння можна розглядати як систему з 5 рівнянь. Як показано, система рівнянь фактично представляє кон'юнкцію логічних функцій. Справедливе та зворотне твердження — кон'юнкцію умов можна розглядати як систему рівнянь.

Побудуємо дерево рішень для імплікації (x1→x2) — першого члена кон'юнкції, який можна як перше рівняння. Ось як виглядає графічне зображення цього дерева:

Дерево складається з двох рівнів за кількістю змінних рівнянь. Перший рівень визначає першу змінну X 1 . Дві гілки цього рівня відображають можливі значення цієї змінної - 1 і 0. На другому рівні гілки дерева відображають лише ті можливі значення змінної X 2 , для яких рівняння набуває значення істина. Оскільки рівняння задає імплікацію, то гілка, на якій X1 має значення 1, вимагає, щоб на цій галузі X2 мало значення 1. Гілка, на якій X1 має значення 0, породжує дві гілки зі значеннями X2, рівними 0 і 1 . Побудоване дерево задає три рішення, на яких імплікація X 1 → X 2 приймає значення 1. На кожній гілки виписаний відповідний набір змінних змін, що дає рішення рівняння.

Ось ці набори: ((1, 1), (0, 1), (0, 0))

Продовжимо побудову дерева розв'язків, додаючи наступне рівняння, наступну імплікацію X 2 → X 3 . Специфіка нашої системи рівнянь у тому, що кожне нове рівняння системи використовує одну змінну попереднього рівняння, додаючи одну нову змінну. Оскільки змінна X 2 вже має значення на дереві, то на всіх гілках, де змінна X 2 має значення 1, змінна X 3 також матиме значення 1. Для таких гілок побудова дерева продовжується на наступний рівень, але нові гілки не з'являються. Єдина гілка, де змінна X 2 має значення 0, дасть розгалуження на дві гілки, де змінна X 3 отримає значення 0 і 1. Таким чином кожне додавання нового рівняння, враховуючи його специфіку, додає одне рішення. Вихідне перше рівняння:

(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
має 6 рішень. Ось як виглядає повне дерево рішень для цього рівняння:

Друге рівняння нашої системи аналогічне першому:

(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1

Різниця лише тому, що у рівнянні використовуються змінні Y. Це рівняння також має 6 рішень. Оскільки кожне рішення для змінних X i може бути скомбіноване з кожним рішенням для змінних Y j то загальна кількість рішень дорівнює 36.

Зауважте, побудоване дерево рішень дає як число рішень (за кількістю гілок), а й самі рішення, виписані кожної гілки дерева.

Завдання 19

Скільки існує різних наборів значень логічних змінних x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, які задовольняють всі перелічені нижче умови?

(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1
(x1→ y1) = 1

Це завдання є модифікацією попереднього завдання. Різниця в тому, що додається ще одне рівняння, що зв'язує змінні X та Y.

З рівняння X 1 → Y 1 випливає, що коли X 1 має значення 1 (одне таке рішення існує), то і Y 1 має значення 1. Таким чином, існує один набір, на якому X 1 та Y 1 мають значення 1. X 1 , рівному 0, Y 1 може мати будь-яке значення, як 0, так і 1. Тому кожному набору з X 1 , рівному 0, а таких наборів 5 відповідає всі 6 наборів зі змінними Y. Отже, загальна кількість рішень дорівнює 31 .

Завдання 20

(¬X 1 ˅ X 2) ˄ (¬X 2 ˅ X 3) ˄ (¬X 3 ˅ X 4) ˄ (¬X 4 ˅ X 5) ˄ (¬X 5 ˅ X 1) = 1

Рішення: Згадки про основні еквівалентності, запишемо наше рівняння у вигляді:

(X 1 → X 2) ˄ (X 2 → X 3) ˄ (X 3 → X 4) ˄ (X 4 → X 5) ˄ (X 5 → X 1) = 1

Циклічний ланцюжок імплікацій означає тотожність змінних, так що наше рівняння еквівалентне рівнянню:

X 1 ≡ X 2 ≡ X 3 ≡ X 4 ≡ X 5 = 1

Це рівняння має два рішення, коли всі X i дорівнюють або 1, або 0.

Завдання 21

(X 1 → X 2) ˄ (X 2 → X 3) ˄ (X 3 → X 4) ˄ (X 4 → X 2) ˄ (X 4 → X 5) = 1

Рішення: Так само, як і в задачі 20, від циклічних імплікацій перейдемо до тотожності, переписавши рівняння у вигляді:

(X 1 → X 2) ˄ (X 2 ≡ X 3 ≡ X 4) ˄ (X 4 → X 5) = 1

Збудуємо дерево рішень для цього рівняння:

Завдання 22

Скільки розв'язків має наступна система рівнянь?

((X 1 ≡X 2) ˄ (X 3 ≡X 4)) ˅(¬(X 1 ≡X 2) ˄ ¬(X 3 ≡X 4)) = 0

((X 3 ≡X 4) ˄ (X 5 ≡X 6)) ˅(¬(X 3 ≡X 4) ˄ ¬(X 5 ≡X 6)) = 0

((X 5 ≡X 6) ˄ (X 7 ≡X 8)) ˅(¬(X 5 ≡X 6) ˄ ¬(X 7 ≡X 8)) = 0

((X 7 ≡X 8) ˄ (X 9 ≡X 10)) ˅(¬(X 7 ≡X 8) ˄ ¬(X 9 ≡X 10)) = 0

Відповідь: 64

Рішення: Перейдемо від 10 змінних до 5 змінних, ввівши наступну заміну змінних:

Y 1 = (X 1 ≡ X 2); Y 2 = (X 3 ≡ X 4); Y 3 = (X 5 ≡ X 6); Y 4 = (X 7 ≡ X 8); Y 5 = (X 9 ≡ X 10);

Тоді перше рівняння набуде вигляду:

(Y 1 ˄ Y 2) ˅ (¬Y 1 ˄ ¬Y 2) = 0

Рівняння можна спростити, записавши його у вигляді:

(Y 1 ≡ Y 2) = 0

Переходячи до традиційної форми, запишемо систему після спрощень у вигляді:

¬(Y 1 ≡ Y 2) = 1

¬(Y 2 ≡ Y 3) = 1

¬(Y 3 ≡ Y 4) = 1

¬(Y 4 ≡ Y 5) = 1

Дерево рішень для цієї системи просте і складається з двох гілок з значеннями змінних, що чергуються:

Повертаючись до вихідних змінних X, зауважимо, що кожному значенню змінної Y відповідає 2 значення змінних X, тому кожне рішення в змінних Y породжує 2 5 рішень у змінних X. Дві гілки породжують 2 * 2 5 рішень, так що загальна кількість рішень дорівнює 64.

Як бачите, кожне завдання на розв'язання системи рівнянь потребує свого підходу. Загальним прийомом є виконання еквівалентних перетворень спрощення рівнянь. Спільним прийомом є і побудова дерев рішень. Застосовуваний підхід частково нагадує побудову таблиці істинності з особливістю, що будуються в повному обсязі набори можливих значеньзмінних, лише ті, у яких функція приймає значення 1 (істина). Часто в пропонованих задачах немає необхідності в побудові повного дерева рішень, оскільки вже на початковому етапі вдається встановити закономірність появи нових гілок на кожному наступному рівні, як це зроблено, наприклад, завдання 18.

Загалом завдання знайти рішення систем логічних рівнянь є хорошими математичними вправами.

Якщо завдання важко розв'язати вручну, можна доручити розв'язання завдання комп'ютеру, написавши відповідну програму розв'язання рівнянь і систем рівнянь.

Написати таку програму нескладно. Така програма легко впорається з усіма завданнями, які пропонуються в ЄДІ.

Як це не дивно, але завдання знаходження рішень систем логічних рівнянь є складним і для комп'ютера, виявляється і комп'ютер має свої межі. Комп'ютер може досить просто впоратися із завданнями, де кількість змінних 20 -30, але почне надовго замислюватися на завдання більшого розміру. Справа в тому, що функція 2 n , що задає число наборів, є експонентою, що швидко зростає зі збільшенням n. Настільки швидко, що звичайний персональний комп'ютер за добу не впорається із завданням, яке має 40 змінних.

Програма мовою C# для розв'язання логічних рівнянь

Написати програму для вирішення логічних рівнянь корисно з багатьох причин, хоча б тому, що за її допомогою можна перевіряти правильність власного вирішення тестових завдань ЄДІ. Інша причина в тому, що така програма є чудовим прикладом завдання на програмування, що відповідає вимогам, що висуваються до завдань категорії С у ЄДІ.

Ідея побудови програми проста, вона заснована на повному переборі всіх можливих наборів значень змінних. Оскільки для заданого логічного рівняння або системи рівнянь кількість змінних n відома, то відомо і число наборів - 2 n, які потрібно перебрати. Використовуючи базові функції мови C# - заперечення, диз'юнкцію, кон'юнкцію та тотожність, неважко написати програму, яка для заданого набору змінних обчислює значення логічної функції, що відповідає логічному рівнянню або системі рівнянь.

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

Єдина складність, що виникає при реалізації програми, пов'язана із завданням формування за номером набору набору значень змінних. Краса цієї задачі в тому, що ця, здавалося б, важка задача, фактично зводиться до простого завдання, що вже неодноразово виникало. Дійсно, досить зрозуміти, що відповідний числу i набір значень змінних, що складається з нулів та одиниць, представляє двійковий запис числа i. Так що складна задачаотримання набору значень змінних за номером набору зводиться до добре знайомого завдання переведення числа двійкову систему.

Ось як виглядає функція мовою C#, яка вирішує наше завдання:

///

///

/// логічна функція - метод,

/// сигнатура якого задається делегатом DF

///

/// кількість змінних

/// кількість рішень

static int SolveEquations(DF fun, int n)

bool set = новий bool [n];

int m = (int) Math.Pow (2, n); //кількість наборів

int p = 0, q = 0, k = 0;

//Повний перебір за кількістю наборів

for (int i = 0; i< m; i++)

//Формування чергового набору - set,

//заданого двійковим уявленням числа i

for (int j = 0; j< n; j++)

k = (int) Math.Pow (2, j);

//Обчислення значення функції на наборі set

Для розуміння програми, сподіваюся, достатньо зроблених пояснень ідеї програми та коментарів у її тексті. Зупинюся лише з поясненні заголовка наведеної функції. У функції SolveEquations два вхідні параметри. Параметр fun задає логічну функцію, що відповідає рівнянню, що вирішується, або системі рівнянь. Параметр n визначає кількість змінних функції fun. Як результат функція SolveEquations повертає число рішень логічної функції, тобто кількість тих наборів, у яких функція приймає значення true.

Для школярів звично, коли деякою функцією F(x) вхідним параметром x є змінна арифметичного, рядкового чи логічного типу. У нашому випадку використовується потужніша конструкція. Функція SolveEquations відноситься до функцій вищого порядку - функцій типу F(f), у яких параметрами можуть бути не тільки прості змінні, але й функції.

Клас функцій, які можуть передаватися як параметр функції SolveEquations, задається таким чином:

delegate bool DF(bool vars);

Цьому класу належать всі функції, яким як параметр передається набір значень логічних змінних, заданих масивом vars. Як результат повертається значення булевського типу, що представляє значення функції цьому наборі.

Насамкінець наведу програму, в якій функція SolveEquations використовується для вирішення декількох систем логічних рівнянь. Функція SolveEquations є частиною наведеного нижче класу ProgramCommon:

class ProgramCommon

delegate bool DF(bool vars);

static void Main(string args)

Console.WriteLine(«У Функції And рішень -» +

SolveEquations(FunAnd, 2));

Console.WriteLine («У Функції 51 рішень -» +

SolveEquations(Fun51, 5));

Console.WriteLine(«У Функції 53 рішень -» +

SolveEquations(Fun53, 10));

static bool FunAnd(bool vars)

return vars && vars;

static bool Fun51(bool vars)

f = f && (!vars ||vars);

f = f && (!vars ||vars);

f = f && (!vars ||vars);

f = f && (!vars ||vars);

f = f && (!vars ||vars);

static bool Fun53(bool vars)

f = f && ((vars == vars) || (vars == vars));

f = f && ((vars == vars) || (vars == vars));

f = f && ((vars == vars) || (vars == vars));

f = f && ((vars == vars) || (vars == vars));

f = f && ((vars == vars) || (vars == vars));

f = f && ((vars == vars) || (vars == vars));

f = f && (!((vars == vars) || (vars == vars)));

Ось як виглядають результати рішення щодо цієї програми:

10 завдань для самостійної роботи

1. Які з трьох функцій еквівалентні:
   1. (X → Y) ˅ ¬Y
   2. ¬(X ˅ ¬Y) ˄ (X → ¬Y)
   3. ¬X ˄ Y
2. Дано фрагмент таблиці істинності:

Який із трьох функцій відповідає цей фрагмент:

1. (X 1 ˅ ¬X 2) ˄ (X 3 → X 4)
2. (X 1 → X 3) ˄ X 2 ˅ X 4
3. X 1 ˄ X 2 ˅ (X 3 → (X 1 ˅ X 4))
4. До складу журі входять троє людей. Рішення приймається, якщо за нього голосує голова журі, підтриманий хоча б одним із членів журі. В іншому випадку рішення не ухвалюється. Побудуйте логічну функцію, що формалізує процес ухвалення рішення.
5. X виграє у Y, якщо за чотирьох киданнях монети тричі випадає «орел». Вкажіть логічну функцію, яка описує виграш X.
6. Слова у реченні нумеруються, починаючи з одиниці. Пропозиція вважається правильно побудованою, якщо виконуються такі правила:
   1. Якщо парне в нумерації слово закінчується на голосну, то наступне слово, якщо воно існує, повинне починатися з голосної.
   2. Якщо непарне в нумерації слово закінчується приголосною, то наступне слово, якщо воно існує, повинне починатися із приголосною і закінчуватися голосною.
      Які з наступних пропозицій правильно побудовані:
   3. Мама мила Машу милом.
   4. Лідер завжди є взірцем.
   5. Правда добре, а щастя краще.
7. Скільки рішень має рівняння:
   (a ˄ ¬ b) ˅ (¬a ˄ b) → (c ˄ d) = 1
8. Перелічіть усі рішення рівняння:
   (a → b) → c = 0
9. Скільки рішень має така система рівнянь:
   X 0 → X 1 ˄ X 1 → X 2 = 1
   X 2 → X 3 ˄ X 3 → X 4 = 1
   X 5 → X 6 ˄ X 6 → X 7 = 1
   X 7 → X 8 ˄ X 8 → X 9 = 1
   X 0 → X 5 = 1
10. Скільки рішень має рівняння:
    ((((X 0 → X 1) → X 2) → X 3) → X 4) → X 5 = 1

Відповіді до завдань:

1. Еквівалентними є функції b та c.
2. Фрагмент відповідає функції b.
3. Нехай логічна змінна P набуває значення 1, коли голова журі голосує «за» ухвалення рішення. Змінні M 1 та M 2 представляють думку членів журі. Логічна функція, що задає ухвалення позитивного рішення може бути записана так:
   P ˄ (M 1 ˅ M 2)
4. Нехай логічна змінна P i приймає значення 1, коли при i-му киданні монети випадає орел. Логічна функція, що задає виграш X, може бути записана так:
   ¬((¬P 1 ˄ (¬P 2 ˅ ¬P 3 ˅ ¬P 4)) ˅
   (¬P 2 ˄ (¬P 3 ˅ ¬P 4)) ˅
   (¬P 3 ˄ ¬P 4))
5. Пропозиція b.
6. Рівняння має 3 рішення: (a = 1; b = 1; c = 0); (a = 0; b = 0; c = 0); (a = 0; b = 1; c = 0)

Каталог завдань.
Логічні рівняння

J ∧ ¬K ∧ L ∧ ¬M ∧ (N ∨ ¬N) = 0, де J, K, L, M, N — логічні змінні?

Рішення.

Вираз (N ∨ ¬N) істинно за будь-якого N, тому

J ∧ ¬K ∧ L ∧ ¬M = 0.

Застосуємо заперечення до обох частин логічного рівняння та використовуємо закон де Моргана (А ∧ В) = ¬ А ∨ ¬ В. Отримаємо ¬J ∨ K ∨ ¬L ∨ M = 1.

Логічна сума дорівнює 1, якщо хоча б одне із складових її висловлювань дорівнює 1. Тому отриманому рівнянню задовольняють будь-які комбінації логічних змінних крім випадку, коли всі врівняння величини рівні 0. Кожна з 4 змінних може бути або 1, або 0, тому всіляких комбінацій 2 · 2 · 2 · 2 = 16. Отже, рівняння має 16 -1 = 15 рішень.

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

Відповідь: 30

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

((J → K) → (M ∧ N ∧ L)) ∧ ((J ∧ ¬K) → ¬ (M ∧ N ∧ L)) ∧ (M → J) = 1

де J, K, L, M, N - логічні змінні?

У відповіді не потрібно перераховувати всі різні набори значень J, K, L, M і N, при яких виконана ця рівність. Як відповідь слід зазначити кількість таких наборів.

Рішення.

Використовуємо формули A → B = ¬A ∨ B і ¬(А ∨ В) = ¬А ∧ ¬В

Розглянемо першу підформулу:

(J → K) → (M ∧ N ∧ L) = ¬(¬J ∨ K) ∨ (M ∧ N ∧ L) = (J ∧ ¬K) ∨ (M ∧ N ∧ L)

Розглянемо другу підформулу

(J ∧ ¬K) → ¬(M ∧ N ∧ L) = ¬(J ∧ ¬K) ∨ ¬(M ∧ N ∧ L) = (¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬L

Розглянемо третю підформулу

1) M → J = 1 отже,

(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (1 ∧ ¬K) ∨ (1 ∧ N ∧ L) = ¬K ∨ N ∧ L;

(0 ∨ K) ∨ 0 ∨ ¬N ∨ ¬L = K ∨ ¬N ∨ ¬L;

Об'єднаємо:

K ∨ N ∧ L ∧ K ∨ ¬N ∨ ¬L = 0 ∨ L ∨ 0 ∨ ¬L = L ∨ ¬L = 1 отже, 4 рішення.

(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (1 ∧ ¬K) ∨ (0 ∧ N ∧ L) = ¬K;

(¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬L = (0 ∨ K) ∨ 1 ∨ ¬N ∨ ¬L = K ∨ 1 ∨ ¬N ∨ ¬L

Об'єднаємо:

K ∨ 1 ∨ ¬N ∨ ¬L ∧ ¬K = 1 ∨ ¬N ∨ ¬L отже, 4 рішення.

в) M = 0; J = 0.

(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (0 ∧ ¬K) ∨ (0 ∧ N ∧ L) = 0.

(¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬L = (1 ∨ K) ∨ 1 ∨ ¬N ∨ ¬L.

Відповідь: 4+4=8.

Відповідь: 8

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

((K ∨ L) → (L ∧ M ∧ N)) = 0

де K, L, M, N - логічні змінні? У Відповіді не потрібно перераховувати всі різні набори значень K, L, M і N, при яких виконана ця рівність. Як відповідь Вам потрібно вказати кількість таких наборів.

Рішення.

перепишемо рівняння, використовуючи простіші позначення операцій:

((K + L) → (L · M · N)) = 0

1) з таблиці істинності операції «імплікація» (див. перше завдання) випливає, що ця рівність вірна тоді і тільки тоді, коли одночасно

K + L = 1 і L · M · N = 0

2) з першого рівняння випливає, що хоча одна зі змінних, K або L, дорівнює 1 (або обидві разом); тому розглянемо три випадки

3) якщо K = 1 і L = 0, то друга рівність виконується за будь-яких М і N; оскільки існує 4 комбінації двох логічних змінних (00, 01, 10 та 11), маємо 4 різні рішення

4) якщо K = 1 і L = 1, то друга рівність виконується за М · N = 0; існує 3 таких комбінації (00, 01 та 10), маємо ще 3 рішення

5) якщо K = 0, то обов'язково L = 1 (з першого рівняння); при цьому друга рівність виконується за М · N = 0; існує 3 таких комбінації (00, 01 та 10), маємо ще 3 рішення

6) всього отримуємо 4+3+3=10 рішень.

Відповідь: 10

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

(K ∧ L) ∨ (M ∧ N) = 1

де K, L, M, N - логічні змінні? У відповіді не потрібно перераховувати всі різні набори значень K, L, M і N, при яких виконана ця рівність. Як відповідь вам потрібно вказати лише кількість таких наборів.

Рішення.

Вираз істинний у трьох випадках, коли (K ∧ L) і (M ∧ N) рівні відповідно 01, 11, 10.

1) "01" K ∧ L = 0; M ∧ N = 1, => M, N дорівнюють 1, а K і L будь-які, крім одночасно 1. Отже, 3 рішення.

УДК 004.023

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

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

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

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

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

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

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

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

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

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

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

Бх(8) = 16 + 7 = 23,

Fl(9) = 23 + 11 = 34.

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

Отже, F(9) = Fl(9) + Fo(9) = 34 + 16 = 50.

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

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

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

к2> 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 = FN-1 + FN-3.

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

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

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

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

XI Х2 ХЗ >:1 Х5 Хб Х7

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

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

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

(Х1 ^ Х2) ■ (Х2 ^ Хз) ■ (Хз ^ Х4) ■ (Х4 ^ Х5) = 1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

^ ^ Y2 = 1 Y2 ^ Yз = 1 Yз ^ Y4 = 1 Y4 ^ Y5 = 1

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

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

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

(^ ^ Ь) ■ (-X ^ Xз) ■ № ^ X) ■ (-X ^ Кз) = 1 № ^ Y2) ■ (У1 ^ Yз) ■ (-Г1 ^ Y4) ■ (У1 ^ Y5) = 1 (-X + Y 1) ■ (-X + Y5) = 1

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

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

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

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

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

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

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

(У^2) ■ (-Ъ + ^)=1

(Y2 + Yз) ■ № + -Тз) = 1

(Yз+Y4) ■ № + ^)=1

(Y4+Y5) ■ (^4 + ^)=1

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

У1 У2 УЗ У4 У5

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

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

Х1 + Х2 = 1-Х2 + Хз = 1

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

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

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

(Х1 = Х2) + (Х2 = Хз) = 1

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

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

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

F(N) = 2 х 9 = 18.

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

- (Х1 = Х2) + (Хз = Х4) = 1

- (Хз = Х4) + (Х5 = Х) = 1

- (Х = Х) + (Х7 = Х) = 1

- (Х7 = Х8) + (Х9 = Х10) = 1

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

(Х1 = Х2) = Yl

(Х5 = Х) = Yз

(Х7 = Х8) = Y4

(Х9 = Х10) = Y5

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

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

У1 У2 УЗ У4 У5

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

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

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

((Х = Ъ) ■ (Xз = X4)) + (4X1 = Ъ) ■ -(X = X)) =0 ((Xз = X4) ■ (X5 = X6)) + (4X3 = X4) ■ - (X = X6)) = 0

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

Ъ) = Yl (X = ^4) = Y2

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

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

(УЛ) + (-У« ■ -У2) = 0

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

(У2 = Yз) = 0 (Уз = У4) = 0 (У4 = У5) = 0

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

У1 У2 УЗ У4 У5

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

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

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

(Х4 Х5) + (-Х4-Х5) + (Х4 = Х) = 1

(Х5 Х) + (-Х-Х6) + (Х5 = Х7) = 1

(X Х7) + (-Х-Х7) + (Х = Х8) = 1

(Х7 Х) + (-Х7 -Х8) + (Х7 = Х9) = 1

(Х8 Х9) + (-Х-Х9) + (Х8 = Х10) = 1

(Х1 = Х2) + (Х1 = Хз) = 1

(Х = Хз) + (Х2 = Х4) = 1

(Хз = Х4) + (Хз = Х5) = 1

(Х4 = Х5) + (Х4 = Х) = 1

(Х5 = Х6) + (Х5 = Х7) = 1

(Х = Х7) + (Х6 = Х8) = 1

(Х7 = Х8) + (Х7 = Х9) = 1

(Х = Х9) + (Х8 = Х10) = 1

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

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

(Х1 Х2) + (-Х1 -Х2) + (Х1 = Хз) = 1

(Х2 Хз) + (-Х-Хз) + (Х2 = Х4) = 1

(Хз Х4) + (-Хз-Х4) + (Хз = Х5) = 1

(Х4 Х5) + (-Х-Х5) + (Х4 = Хб) = 1

(Х5 Хб) + (-Х-Хб) + (Х5 = Х7) = 1

(Хб Х7) + (-Хб-Х7) + (Хб = Х8) = 1

(Х7 Х8) + (-Х7-Х8) + (Х7 = Х9) = 1

(Х8 Х9) + (-Х8-Х9) + (Х8 = Х10) = 0

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

(XI = Х2) + (XI = Хз) = 1 (Х = Хз) + (Х2 = X) = 1 (Хз = X) + (Хз = Х5) = 1 (X = Х5) + (Х4 = Хб) = 1 (Х5 = Хб) + (Х5 = Х7) = 1 (Хб = Х7) + (Хб = Х8) = 1 (Х = Х8) + (Х7 = Х9) = 1 (Х = Х9) + (Х8 = Ххс) = 0

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

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

(Х1 Х2) + (-Х1 -Х2) + (Х2 Хз) + (-Х2 -Хз) = 1

(Х2 Хз) + (-Х2 -Хз) + (Хз Х) + (-Хз ■ -Х4) = 1

(Хз Х) + (-Хз-Х4) + (Х4 Х5) + (-Х4-Х5) = 1

(Х4 X) + (-Х-Х5) + (Х5 Хб) + (-Х5-Хб) = 1

(Х5 Хб) + (-Х-Хб) + (Хб Х7) + (-Хб ■ -Х7) = 1

(Хб Х7) + (-Хб-Х7) + (Х7 Х8) + (-Х7-Х8) = 1

(Х7 Х) + (-Х7-Х8) + (Х8 Х9) + (-Х8-Х9) = 1

(Х8 Х9) + (-Х8-Х9) + (Х9 Х10) + (-Х9 ■-Х10) = 1

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

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

(Хб = Х7) + (Х7 = X) = 1 (Х7 = Х8) + (Х8 = Х9) = 1 (Хв = X9) + (Х9 = Х10) = 1

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

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

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

(Х1 Х2) + (-Х1 -Х2) + (Х2 Хз) + (-Х2 ■ -Хз) = 1

(Х2 Хз) + (-Х-Хз) + (Хз Х4) + (-Хз-Х4) = 1

(Хз Х4) + (-Хз -Х4) + (Х4 Х5) + (-Х4 ■-Х5) = 1

(Х4 Х5) + (-Х4 -Х5) + (Х Хб) + (-Х5 ■ -Хб) = 1

(Х5 Хб) + (-Х5 -Хб) + (Хб Х7) + (-Хб ■ -Х7) = 1

(Хб Х7) + (-Хб-Х7) + (Х7 Х8) + (-Х7 ■-Х8) = 1

(Х7 Х8) + (-Х7-Х8) + (Х8 Х9) + (-Х8-Х9) = 1

(Х8 Х9) + (-Х8-Х9) + (Х9 Х10) + (-Х9 ■-Х10) = 0

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

(Х = Х2) + (Х2 = Х3) = 1 (Х2 = Хз) + (Хз = Х4) = 1

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

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

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

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

- - - -*- - - -*-о

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

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

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

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

(X7^Xs) + (X7^X9) = 1 (Xs^X9) + (Xs^X10) = 1

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

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

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

Зауважимо, що F0(N) = Fx(N+1) - 1. Тоді Fx(10) = 89, а F0(10) = Fx(11) - 1 = 144 - 1. Отже, F(10) = F1 (10) + F0(10) = 89 + 143 = 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. Як Integer. _ j As Integer. N As Integer, vg As Integer Dim з As String vg=S j-0

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

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

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

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

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

з = с - 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=77&id=103&option=com_con-