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

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

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 змінних, методи перетворення логічних выражений. Крім того, необхідно знати такі властивості логічних операцій: кон'юнкції, диз'юнкції, інверсії, імплікації та еквівалентності.

Будь-яку логічну функцію від змінних - можна задати таблицею істинності.

Вирішимо кілька логічно рівнянь:

\[\rightharpoondown X1\vee X2=1 \]

\[\rightharpoondown X2\vee X3=1\]

\[\rightharpoondown X3\vee X4=1 \]

\[\rightharpoondown X9\vee X10=1\]

Почнемо рішення з [Х1] і визначимо які значення дана змінна може набувати: 0 і 1. Далі розглянемо кожне їх вищенаведених значень і подивимося, яке може бути при цьому [Х2.]

Як видно з таблиці, наше логічне рівняння має 11 рішень.

Де можна вирішити логічне рівняння онлайн?

Вирішити рівняння можна на нашому сайті https://сайт. Безкоштовний онлайн вирішувач дозволить вирішити рівняння онлайн будь-якої складності за лічені секунди. Все, що вам необхідно зробити – це просто ввести свої дані у вирішувачі. Також ви можете переглянути відео інструкцію та дізнатися, як вирішити рівняння на нашому сайті. А якщо у вас залишилися питання, ви можете задати їх у нашій групі Вконтакте http://vk.com/pocketteacher. Вступайте до нашої групи, ми завжди раді допомогти вам.

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

Кіргізова Є.В., Нємкова А.Є.

Лісосибірський педагогічний інститут -

філія Сибірського федерального університету, Росія

Вміння мислити послідовно, міркувати доказово, будувати гіпотези, спростовувати негативні висновки, не приходить саме собою, це вміння розвиває наука логіка. Логіка - це наука, що вивчає методи встановлення істинності чи хибності одних висловлювань на основі істинності чи хибності інших висловлювань.

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

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

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

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

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

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

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

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

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

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

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

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

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

З першого рівняння отримуємо B =0, та якщо з другого – З=1. Рішення системи: A = 0, B = 0 і C = 1 .

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

Перше рівняння системи залежить від A і B , а друге рівняння від А і C . Змінна А може набувати 2 значень 0 і 1:

З першого рівняння випливає, що , Тому при A = 0 отримаємо B = 0 , а при A = 1 маємо B = 1 . Отже, перше рівняння має два рішення щодо змінних A та B .

Зобразимо друге рівняння, з якого визначимо значення C для кожного варіанта. При A = 1 імплікація може бути хибною, тобто друга гілка дерева немає рішення. При A = 0 отримуємо єдине рішення C = 1 :

Таким чином, отримали рішення системи: A = 0 B = 0 і C = 1 .

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

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

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

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

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

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

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

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

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

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

(1; 1; 1; …; 1)

(0; 1; 1; …; 1)

(0; 0; 0; …; 0)

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

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

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

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

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

Далі можна побачити, що одне рівняння є істинним у наступних трьох випадках: (0; 0), (0; 1), (1; 1). Система двох рівнянь істина у чотирьох випадках (0; 0; 0), (0; 0; 1), (0; 1; 1), (1; 1; 1). При цьому відразу видно, що існує рішення, що складається з одних нулів і ще mрішень, у яких додається по одній одиниці, починаючи з останньої позиції до заповнення всіх можливих місць. Можна припустити, що загальне рішення матиме такий самий вигляд, але щоб такий підхід став рішенням, потрібен доказ, що припущення правильне.

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

Література:

1. Логічні завдання/О.Б. Богомолова - 2-ге вид. - М.: БІНОМ. Лабораторія знань, 2006. - 271 с.: Іл.

2. Поляков К.Ю. Системи логічних рівнянь / Навчально-методична газета для вчителів інформатики: Інформатика №14, 2011

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

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

1. Метод заміни змінних.

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

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

приклад.

((X1 ≡ X2) ∧ (X3 ≡ X4)) ∨ (¬(X1 ≡ X2) ∧ ¬(X3 ≡ X4)) = 0

((X3 ≡ X4) ∧ (X5 ≡ X6)) ∨ (¬(X3 ≡ X4) ∧ ¬(X5 ≡ X6)) = 0

((X5 ≡ X6) ∧ (X7 ≡ X8)) ∨ (¬(X5 ≡ X6) ∧ ¬(X7 ≡ X8)) = 0

((X7 ≡ X8) ∧ (X9 ≡ X10)) ∨ (¬(X7 ≡ X8) ∧ ¬(X9 ≡ X10)) = 0

Рішення:

Введемо нові змінні: А = (X1≡ X2); В=(X3 ≡ X4); С=(X5 ≡ X6); D=(X7 ≡ X8); E=(X9 ≡ X10).

(Увага! Кожна їх змінних x1, x2, …, x10 повинна входити лише одну з нових змінних А,В,С,D,Е, тобто нові змінні незалежні один від одного).

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

(А ∧ В) ∨ (¬А ∧ ¬В)=0

(В ∧ C) ∨ (¬B ∧ ¬C)=0

(З ∧ D) ∨ (¬C ∧ ¬D)=0

(D ∧ E) ∨ (¬D ∧ ¬E)=0

Побудуємо дерево рішень отриманої системи:

Розглянемо рівняння А=0, тобто. (X1≡ X2) = 0. Воно має 2 корені:

З цієї ж таблиці видно, що рівняння А = 1 теж має 2 корені. Розставимо кількість коренів на дереві рішень:

Щоб знайти кількість розв'язків однієї гілки, треба перемножити кількість розв'язків на кожному її рівні. Ліва гілка має 2⋅ 2 ⋅ 2 ⋅ 2 ⋅ 2 = 32 рішення; права гілка має також 32 рішення. Тобто. вся система має 32 +32 = 64 рішення.

Відповідь: 64.

2. Метод міркувань.

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

приклад 1. Скільки існує різних наборів значень логічних змінних 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

У відповіді не потрібно перераховувати всі різні набори значень змінних x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, за яких виконана дана система рівностей. Як відповідь Вам потрібно зазначити кількість таких наборів.

Рішення :

Перше та друге рівняння містять незалежні змінні, які пов'язані третьою умовою. Побудуємо дерево розв'язків першого та другого рівнянь.

Щоб уявити дерево розв'язків системи з першого та другого рівнянь, треба кожну гілку першого дерева продовжити деревом для змінниху . Побудоване таким чином дерево міститиме 36 гілок. Деякі з цих гілок не задовольняють третє рівняння системи. Відзначимо на першому дереві кількість гілок дерева«у» , які задовольняють третьому рівнянню:

Пояснимо: для виконання третьої умови при х1=0 має бути у1=1, тобто всі гілки дерева«х» , де х1=0 можна продовжити лише однією гілкою з дерева«у» . І лише для однієї гілки дерева«х» (правою) підходять усі гілки дерева"у". Таким чином, повне дерево всієї системи містить 11 гілок. Кожна гілка є одним рішенням вихідної системи рівнянь. Отже, вся система має 11 рішень.

Відповідь: 11.

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

(X1 ≡ X2) ∨ (X1 ∧ X10) ∨ (¬X1 ∧ ¬ X10)= 1

(X2 ≡ X3) ∨ (X2 ∧ X10) ∨ (¬X2 ∧ ¬ X10)= 1.

………………

(X9 ≡ X10) ∨ (X9 ∧ X10) ∨ (¬X9 ∧ ¬ X10)= 1

(X1 ≡ X10) = 0

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

Рішення : Спростити систему. Побудуємо таблицю істинності частини першого рівняння:

Зверніть увагу на останній стовпець, він збігається з результатом дії X1 ≡ X10.

Після спрощення отримаємо:

(X1 ≡ X2) ∨ (X1 ≡ X10)=1

(X2 ≡ X3) ∨ (X2 ≡ X10)=1

(X3 ≡ X4) ∨ (X3 ≡ X10)=1

……

(X9 ≡ X10) ∨ (X9 ≡ X10)=1

(X1 ≡ X10) = 0

Розглянемо останнє рівняння:(X1 ≡ X10) = 0, тобто. х1 не повинно збігатися з х10. Щоб перше рівняння дорівнювало 1, повинна виконуватись рівність(X1 ≡ X2) = 1, тобто. х1 має збігатися з х2.

Побудуємо дерево розв'язків першого рівняння:

Розглянемо друге рівняння: при х10 = 1 і при х2 = 0 дужкаповинна дорівнювати 1 (тобто х2 збігається з х3); при х10 = 0 і при х2 = 1 дужка(X2 ≡ X10)=0 , значить, дужка (X2 ≡ X3) повинна дорівнювати 1 (тобто х2 збігається з х3):

Розмірковуючи таким чином, збудуємо дерево рішень для всіх рівнянь:

Таким чином, система рівнянь має лише 2 рішення.

Відповідь: 2.

приклад 3.

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

(x1→x2) /\ (x2→x3) /\ (x3→x4) = 1

(¬x1 /\ y1 /\ z1) \/ (x1 /\ ¬y1 /\ z1) \/ (x1 /\ y1 /\ ¬z1) = 1

(¬x2 /\ y2 /\ z2) \/ (x2 /\ ¬y2 /\ z2) \/ (x2 /\ y2 /\ ¬z2) = 1

(¬x3 /\ y3 /\ z3) \/ (x3 /\ ¬y3 /\ z3) \/ (x3 /\ y3 /\ ¬z3) = 1

(¬x4 /\ y4 /\ z4) \/ (x4 /\ ¬y4 /\ z4) \/ (x4 /\ y4 /\ ¬z4) = 1

Рішення:

Побудуємо дерево розв'язків 1-го рівняння:

Розглянемо друге рівняння:

• При х1 = 0 : друга і третя дужки дорівнюватимуть 0; щоб перша дужка дорівнювала 1, повинні у1=1 , z1=1 (тобто в цьому випадку - 1 рішення)
• При х1 = 1 : перша дужка дорівнюватиме 0; другаабо третя дужка повинна дорівнювати 1; друга дужка дорівнюватиме 1 при у1=0 і z1=1; третя дужка дорівнюватиме 1 при у1=1 і z1=0 (тобто в цьому випадку - 2 рішення).

Аналогічно інших рівнянь. Зазначимо отриману кількість рішень у кожного вузла дерева:

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

1 гілка: 1 ⋅ 1 ⋅ 1 ⋅ 1 = 1 рішення

2 гілка: 1 ⋅ 1 ⋅ 1 ⋅ 2 =2 рішення

3 гілка: 1 ⋅ 1 ⋅ 2 ⋅ 2 =4 рішення

4 гілка: 1 ⋅ 2 ⋅ 2 ⋅ 2 =8 рішення

5 гілка: 2 ⋅ 2 ⋅ 2 ⋅ 2=16 рішення

Складемо отримані числа: лише 31 рішення.

Відповідь: 31.

3. Закономірне збільшення кількості коренів

У деяких системах кількість коренів чергового рівняння залежить кількості коренів попереднього рівняння.

приклад 1. Скільки існує різних наборів значень логічних змінних x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, які задовольняють всі перелічені нижче умови?

¬(x1 ≡ x2) ∧ ((x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)) = 0

¬(x2 ≡ x3) ∧ ((x2 ∧ ¬x4) ∨ (¬x2 ∧ x4)) = 0

¬(x8 ≡ x9) ∧ ((x8 ∧ ¬x10) ∨ (¬x8 ∧ x10)) = 0

Спростимо перше рівняння:(x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)=x1 ⊕ x3=¬(x1 ≡ x3). Тоді система набуде вигляду:

¬(x1 ≡ x2) ∧ ¬(x1 ≡ x3) = 0

¬(x2 ≡ x3) ∧ ¬(x2 ≡ x4)= 0

¬(x8 ≡ x9) ∧ ¬(x8 ≡ x10) = 0

І т.д.

Кожне наступне рівняння має на 2 корені більше, ніж попереднє.

4 рівняння має 12 коренів;

5 рівняння має 14 коренів

8 рівняння має 20 коренів.

Відповідь: 20 коренів.

Іноді кількість коренів зростає згідно із законом чисел Фібоначчі.

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

Муніципальна бюджетна загальноосвітня установа

«Середня загальноосвітня школа №18»

міського округу місто Салават Республіки Башкортостан

Системи логічних рівнянь

у завданнях ЄДІ з інформатики

Розділ «Основи алгебри логіки» у завданнях ЄДІ вважається одним із найскладніших і погано вирішуваних. Середній відсоток виконання завдань на цю тему найнижчий і становить 43,2.

Виходячи зі специфікації КІМу 2018 року, цей блок включає чотири завдання різного рівня складності.

Завдання 23 є високим за рівнем складності, тому має найнижчий відсоток виконання. Серед підготовлених випускників (81-100 балів) 49,8% виконавців, середньо підготовлені (61-80 балів) справляються на 13,7%, група учнів, що залишилася, дане завдання не виконує.

Успішність розв'язання системи логічних рівнянь залежить від знання законів логіки та від чіткого застосування методів розв'язання системи.

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

(23.154 Поляков К.Ю.) Скільки різних рішень має система рівнянь?

((x1  y1 )  (x2  y2 ))  (x1  x2 )  (y1  y2 ) =1

((x2  y2 )  (x3  y3 ))  (x2  x3 )  (y2  y3 ) =1

((x7  y7 )  (x8  y8 ))  (x7  x8 )  (y7  y8 ) =1

де x1 , x2 ,…, x8, у1 ,у2 ,…,у8 - Логічні змінні? У відповіді не потрібно перераховувати всі різні набори значень змінних, при яких виконана ця рівність. Як відповідь слід зазначити кількість таких наборів.

Рішення. Всі рівняння, включені в систему, однотипні, і кожне рівняння включено чотири змінних. Знаючи x1 та y1, можемо знайти всі можливі значення x2 та y2, що задовольняють першому рівнянню. Розмірковуючи аналогічним чином, з відомих x2 і y2 можемо знайти x3, y3, що задовольняє друге рівняння. Тобто, знаючи пару (x1, y1) і визначивши значення пари (x2, y2), ми знайдемо пару (x3, y3), яка, у свою чергу, призведе до пари (x4, y4) і так далі.

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

Таблиця істинності:

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

(x1  y1 )  (x2  y2 ))=1

(x1  x2 ) =1

(y1  y2 ) =1

Розглянемо перше рівняння. Проходження дорівнює 1, коли 0 0, 0 1, 1 1, значить (x1 y1)=0 при (01), (10), то пара (x2  y2 ) може бути будь-який (00), (01), (10), (11), а при (x1 y1)=1, тобто (00) і (11) пара (x2 y2)=1 набуває таких же значень (00) та (11). Виключимо з цього рішення ті пари, для яких помилкові друге та третє рівняння, тобто x1=1, x2=0, y1=1, y2=0.

Загальна кількість пар 1+1+1+22= 25

2) (23.160 Поляков К.Ю.) Скільки різних рішень має система логічних рівнянь

(x 1  (x 2  y 2 ))  (y 1  y 2 ) = 1

(x 2  (x 3  y 3 ))  (y 2  y 3 ) = 1

...

( x 6  ( x 7  y 7 ))  ( y 6  y 7 ) = 1

x 7  y 7 = 1

Рішення. 1) Рівняння однотипні, тому методом міркування знайдемо різні пари (x1, y1), (x2, y2) першого рівняння.

(x1  (x2  y2 ))=1

(y1  y2 ) = 1

Рішенням другого рівняння є пари (00), (01), (11).

Знайдемо рішення першого рівняння. Якщо x1=0, то x2 , y2 - будь-які, якщо x1=1, то x2 , y2 набуває значення (11).

Складемо зв'язки між парами (x1, y1) та (x2, y2).

Складемо таблицю для обчислення кількості пар кожному етапі.

Враховуючи рішення останнього рівняння x 7  y 7 = 1, виключимо пару (10). Знаходимо загальну кількість рішень 1+7+0+34=42

3)(23.180) Скільки різних рішень має система логічних рівнянь

(x1  x2 )  (x3  x4 ) = 1

(x3  x4 )  (x5  x6 ) = 1

(x5  x6 )  (x7  x8 ) = 1

(x7  x8 )  (x9  x10 ) = 1

x1  x3  x5  x7  x9 = 1

Рішення. 1) Рівняння однотипні, тому методом міркування знайдемо різні пари (x1, x2), (x3, x4) першого рівняння.

(x1  x2 )  (x3  x4 ) = 1

Виключимо з рішення пари, які в дотриманні дають 0 (1 0), це пари (01, 00, 11) та (10).

Складемо зв'язок між парами (x1,x2), (x3,x4)