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

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

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

Розглянемо метод зведення до одного рівняння . Даний метод передбачає перетворення логічних рівнянь, таким чином, щоб їхні права частини були рівні істиннісному значенню (тобто 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 →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.

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

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

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

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

Носкін Андрій Миколайович,
вчитель інформатики
вищої кваліфікаційної категорії,
кандидат військових наук, доцент
ДБОУ Ліцей №1575 місто Москва

Оптимізований метод відображення для вирішення задачі 23 з КІМ ЄДІ з інформатики та ІКТ

Однією з найважчим завданням КІМ ЄДІ є завдання 23, в якій треба знайти кількість різних наборів значень логічних змінних, які задовольняють зазначеній умові.
Це завдання є чи не найскладнішим завданням КІМ ЄДІ з інформатики та ІКТ. З ним, зазвичай, справляються трохи більше 5% екзаменованих (1).
Такий маленький відсоток учнів, які впоралися із цим завданням, пояснюється наступним:
- учні можуть плутати (забути) знаки логічних операцій;
- математичні помилки у процесі виконання розрахунків;
- помилки у міркуваннях під час пошуку рішення;
- Помилки в процесі спрощення логічних виразів;
- вчителі рекомендують вирішувати це завдання, після виконання всієї роботи, оскільки ймовірність припущення
помилок дуже велика, а «вага» завдання становить лише один первинний бал.
Крім того, деякі вчителі самі важко вирішують даний тип завдань і тому намагаються вирішувати з дітьми простіші завдання.
Також ускладнює ситуацію, що в даному блоці існує велика кількість різноманітних завдань та неможливо підібрати якесь шаблонне рішення.
Для виправлення цієї ситуації педагогічним співтовариством допрацьовуються дві основні методики вирішення завдань даного типу: рішення за допомогою бітових ланцюжків (2) і метод відображень (3).
Необхідність доопрацювання (оптимізації) даних методик обумовлена ​​тим, що завдання постійно видозмінюються як за структурою, так і за кількістю змінних (тільки один тип змінних Х, два типи змінних Х та Y, три типи: X, Y, Z).
Складність освоєння даними методиками вирішення завдань підтверджується тим, що на сайті К.Ю. Полякова існує аналізів цього типу завдань у кількості 38 штук(4). У деяких розборах наведено більше одного типу розв'язання задачі.
Останнім часом у КІМ ЄДІ з інформатики зустрічаються завдання з двома типами змінних X та Y.
Я оптимізував метод відображення та пропоную своїм учням користуватися вдосконаленим методом.
Це дає результат. Відсоток моїх учнів, які справляються з цим завданням, варіюється до 43% від тих, хто здає. Як правило, щорічно у мене здає ЄДІ з інформатики від 25 до 33 осіб із усіх 11-х класів.
До появи завдань із двома типами змінними метод відображення учні використовували дуже успішно, але після появи у логічному виразі Y, я став помічати, що у дітей перестали збігатися відповіді з тестами. Виявилося, вони зовсім чітко стали уявляти, як скласти таблицю відображень з новим типом змінної. Тоді мені спало на думку, що для зручності треба весь вислів привести до одного типу змінної, як зручно дітям.
Наведу докладніше цю методику. Для зручності її розглядатиму на прикладі системи логічних виразів, наведених в (4).
Скільки різних рішень має система логічних рівнянь

(x 1 ^ y 1)=(¬x 2 V ¬ y 2 )
(x 2 ^ y 2)= (¬ x 3 V ¬ y 3 )
...
(x 5 ^ y 5) = (¬ x 6 V ¬ y 6 )

(z 1 ^ z 2)= (¬z 3V¬ z 4 )
(z 3 ^ z 4)= (¬ z 5 V¬ z 6 )
...
(z 9 ^ z 10) = (¬ z 11 V¬ z 12)

5. Заповнюємо таблицю, обчислюючи кількість пар змінних, у якому система має рішення.

6. Складаємо всі результати: 9+9+9+27=54
7. Відповідь: 54.
Наведена вище оптимізована методика розв'язання задачі 23 з КІМ ЄДІ дозволила учням знову набути впевненості та успішно вирішувати цей тип завдання.

Література:

1. ФІПД. Методичні рекомендації для вчителів, підготовлені на основі аналізу типових помилок учасників ЄДІ 2015 року щодо ІНФОРМАТИКИ та ІКТ. Режим доступу: http://www.fipi.ru/sites/default/files/document/1442163533/informatika_i_ikt.pdf

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

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

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 коренів.

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

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

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

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

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

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

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

Опанування азами цієї науки неможливе без вирішення логічних завдань. Перевірка сформованості умінь застосовувати свої знання у новій ситуації здійснюється з допомогою здачі. Зокрема це вміння вирішувати логічні завдання. Завдання В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

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) рівні відповідно 01, 11, 10.

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

2) "11" K ∧ L = 1; M ∧ N = 1. => 1 рішення.

3) "10" K ∧ L = 1; M ∧ N = 0. => 3 рішення.

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

Відповідь: 7

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

(X ∧ Y ∨ Z) ​​→ (Z ∨ P) = 0

де X, Y, Z, P – логічні змінні? У відповіді не потрібно перераховувати всі різні набори значень, при яких виконана ця рівність. Як відповідь вам потрібно вказати лише кількість таких наборів.

Пояснення.

(X ∧ Y ∨ Z) ​​→ (Z ∨ P) = 0 =>

¬(X ∧ Y ∨ Z) ​​∨ (Z ∨ P) = 0;

(¬X ∨ ¬Y ∧ ¬Z) ∨ (Z ∨ P) = 0;

Логічне АБО хибно тільки в одному випадку: коли обидва вислови хибні.

Отже,

(Z ∨ P) = 0 => Z = 0, P = 0.

¬X ∨ ¬Y ∧ ¬Z = 0 => ¬X ∨ ¬Y ∧ 1 = 0 =>

¬X ∨ ¬Y = 0 => X = 1; Y = 1.

Отже, існує лише одне рішення рівняння.

Відповідь: 1

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

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

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

Пояснення.

Логічне І істинно тільки в одному випадку: коли всі вирази істинні.

K ∨ L = 1, M ∨ N = 1.

Кожне із рівнянь дає по 3 рішення.

Розглянемо рівняння А ∧ В = 1 якщо і А і приймають справжні значення у трьох випадках кожне, то загалом рівняння має 9 рішень.

Отже, відповідь 9.

Відповідь: 9

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

((A → B)∧ C) ∨ (D ∧ ¬D)= 1,

де A, B, C, D – логічні змінні?

У відповіді не потрібно перераховувати всі різні набори значень A, B, C, D, при яких виконана ця рівність. Як відповідь вам потрібно вказати кількість таких наборів.

Пояснення.

Логічне "АБО" істинно, коли істинно хоча б одне із тверджень.

(D ∧ ¬D)= 0 за будь-яких D.

Отже,

(A → B)∧ C) = 1 => C = 1; A → B = 1 => ¬ A ∨ B = 1, що дає нам 3 варіанти рішень при кожному D.

(D ∧ ¬ D)= 0 за будь-яких D, що дає нам два варіанти рішень (при D = 1, D = 0).

Отже: всього розв'язків 2*3 = 6.

Разом 6 рішень.

Відповідь: 6

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

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

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

Пояснення.

Застосуємо заперечення до обох частин рівняння:

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

Логічне АБО істинно у трьох випадках.

Варіант 1.

K ∧ L ∧ M = 1, тоді K, L, M = 1, а L ∧ M ∧ N = 0. N будь-яке, тобто 2 рішення.

Варіант 2.

¬L ∧ M ∧ N = 1, тоді N, M = 1; L = 0, K будь-яке, тобто 2 рішення.

Отже, відповідь 4.

Відповідь: 4

A, B і С - цілі числа, для яких істинно висловлювання

¬ (A = B) ∧ ((A > B)→(B > C)) ∧ ((B > A)→(С > B)).

Чому дорівнює В, якщо A = 45 і C = 43?

Пояснення.

1) ¬(А = B); (A > B)→(B > C); (B> A)→(С> B);

2) ці прості висловлювання пов'язані операцією ∧ (І, кон'юнкція), тобто вони повинні виконуватися одночасно;

3) з ¬(А = B)=1 відразу випливає, що AB;

4) припустимо, що A > B, тоді з другої умови отримуємо 1→(B > C)=1; цей вираз може бути істинним тоді і тільки тоді, коли B > C = 1;

5) тому маємо A > B > C, цій умові відповідає лише число 44;

6) про всяк випадок перевіримо і варіант A 0 → (B > C) = 1;

це вираз істинно за будь-якого B; тепер дивимося третю умову отримуємо

цей вираз може бути істинним тоді і тільки тоді, коли C > B, і тут ми отримали протиріччя, тому що немає такого числа B, для якого C > B > A.

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

Відповідь: 44

Складіть таблицю істинності для логічної функції

X = (А ↔ B) ∨ ¬(A → (B ∨ C))

в якій стовпець значень аргументу А являє собою двійковий запис числа 27, стовпець значень аргументу - числа 77, стовпець значень аргументу С - числа 120. Число в стовпці записується зверху вниз від старшого розряду до молодшого (включаючи нульовий набір). Переведіть отриманий двійковий запис значень функції X до десяткової системи числення.

Пояснення.

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

1) це вираз із трьома змінними, у таблиці істинності буде рядків; отже, двійковий запис чисел, якими будуються стовпці таблиці А, У і З, має складатися з 8 цифр

2) переведемо числа 27, 77 і 120 у двійкову систему, відразу доповнюючи запис до 8 знаків нулями на початку чисел

3) навряд чи ви зможете одразу написати значення функції Х для кожної комбінації, тому зручно додати до таблиці додаткові стовпці для розрахунку проміжних результатів (див. таблицю нижче)

4) заповнюємо стовпці таблиці:

значення дорівнює 1 тільки в тих рядках, де А = В

значення дорівнює 1 у тих рядках, де або В або С = 1

значення дорівнює 0 тільки в рядках, де А = 1 і В + С = 0

значення – це інверсія попереднього стовпця (0 замінюється на 1, а 1 – на 0)

результат Х (останній стовпець) - це логічна сума двох стовпців і

5) щоб отримати відповідь, виписуємо біти зі стовпця Х зверху донизу:

6) переводимо це число до десяткової системи:

Відповідь: 171

Яким є найбільше ціле число X, при якому істинно висловлювання (10 (X+1)·(X+2))?

Пояснення.

Рівняння є операцією імплікації між двома відносинами:

1) Звичайно, тут можна застосувати той самий спосіб, що й у прикладі 2208, проте при цьому знадобиться вирішувати квадратні рівняння (не хочеться...);

2) Зауважимо, що за умовою нас цікавлять лише цілі числа, тому можна спробувати якось перетворити вихідний вираз, отримавши рівносильне висловлювання (точні значення коренів нас зовсім не цікавлять!);

3) Розглянемо нерівність: очевидно, що то, можливо як позитивним, і негативним числом;

4) Легко перевірити, що в області висловлювання істинно при всіх цілих, а в області - при всіх цілих (щоб не заплутатися, зручніше використовувати нестрогі нерівності, і замість і);

5) Тому для цілих можна замінити на рівносильний вираз

6) область істинності висловлювання - поєднання двох нескінченних інтервалів;

7) Тепер розглянемо друге нерівність: очевидно, що може бути як позитивним, і негативним числом;

8) В області висловлювання істинно при всіх цілих, а в області - при всіх цілих, тому для цілих можна замінити на рівносильний вираз

9) область істинності виразу - закритий інтервал;

10) Задане вираз істинно скрізь, крім областей, де і ;

11) Зверніть увагу, що значення вже не підходить, тому що там і , тобто імплікація дає 0;

12) При підставі 2, (10 (2+1) · (2+2)), або 0 → 0, що задовольняє умові.

Отже, відповідь 2.

Відповідь: 2

Яке найбільше ціле число X, за якого істинно висловлювання

(50 (X+1)·(X+1))?

Пояснення.

Застосуємо перетворення імплікації та перетворюємо вираз:

(50 (X+1)·(X+1)) ⇔ ¬(X 2 > 50) ∨ ((X+1) 2) ∨ (|X+1|).

Логічне АБО істинно коли істинно хоча б одне логічне висловлювання. Вирішивши обидві нерівності і враховуючи, що бачимо, що найбільше ціле число, при якому виконується хоча б одне з них – 7 (на малюнку жовтим зображено позитивне рішення другої нерівності, синім – першої).

Відповідь: 7

Вкажіть значення змінних К, L, M, N, за яких логічний вираз

(¬(М ∨ L) ∧ К) → (¬К ∧ ¬М ∨ N)

помилково. Відповідь запишіть у вигляді рядка із 4 символів: значень змінних К, L, М та N (у зазначеному порядку). Приміром, рядок 1101 відповідає тому, що К=1, L=1, M=0, N=1.

Пояснення.

Дублює завдання 3584.

Відповідь: 1000

(¬K ∨ M) → (¬L ∨ M ∨ N)

Пояснення.

Застосуємо перетворення імплікації:

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

Застосуємо заперечення до обох частин рівняння:

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

Перетворюємо:

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

Отже, M = 0, N = 0, розглянемо тепер (¬K ∧ L ∨ M ∧ L):

з того, що M = 0, N = 0 випливає, що M ∧ L = 0, тоді K ∧ L = 1, тобто K = 0, L = 1.

Відповідь: 0100

Вкажіть значення змінних K, L, M, N, за яких логічний вираз

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

помилково. Відповідь запишіть у вигляді рядка із чотирьох символів: значень змінних K, L, M та N (у зазначеному порядку). Приміром, рядок 1101 відповідає тому, що K=1, L=1, M=0, N=1.

Пояснення.

Запишемо рівняння, використовуючи простіші позначення операцій (умова «вираз хибно» означає, що воно дорівнює логічному нулю):

1) з формулювання умови випливає, що вираз має бути хибним тільки для одного набору змінних

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

3) перша рівність (логічний твір дорівнює 1) виконується тоді і тільки тоді, коли і; звідси випливає (логічна сума дорівнює нулю), що можливо тільки при ; таким чином, три змінні ми вже визначили

4) з другої умови, , при і отримуємо .

Дублює завдання

Відповідь: 1000

Вкажіть значення логічних змінних Р, Q, S, Т, за яких логічний вираз

(Р ∨ ¬Q) ∨ (Q → (S ∨ Т)) помилково.

Відповідь запишіть у вигляді рядка із чотирьох символів: значень змінних Р, Q, S, T (у вказаному порядку).

Пояснення.

(1) (Р ∨ ¬Q) = 0

(2) (Q → (S ∨ Т)) = 0

(1) (Р ∨ ¬Q) = 0 => P = 0, Q = 1.

(2) (Q → (S ∨ Т)) = 0 Застосуємо перетворення імплікації:

¬Q ∨ S ∨ Т = 0 => S = 0, T = 0.

Відповідь: 0100

Вкажіть значення змінних K, L, M, N, за яких логічний вираз

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

помилково. Відповідь запишіть у вигляді рядка із чотирьох символів: значень змінних K, L, M та N (у зазначеному порядку). Приміром, рядок 1101 відповідає тому, що K=1, L=1, M=0, N=1.

Пояснення.

Логічне "АБО" хибне тоді і тільки тоді, коли хибні обидва твердження.

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

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

¬K ∨ M = 0 => K = 1, M = 0.

Розглянемо другий вираз:

(L ∧ K) ∨ ¬N = 0 (див. результат першого виразу) => L ∨ ¬N = 0 => L = 0, N = 1.

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

Відповідь: 1001

Вкажіть значення змінних K, L, M, N, за яких логічний вираз

(K → M) ∧ (K → ¬M) ∧ (¬K → (M ∧ ¬L ∧ N))

істинно. Відповідь запишіть у вигляді рядка із чотирьох символів: значень змінних K, L, M та N (у зазначеному порядку). Приміром, рядок 1101 відповідає тому, що K=1, L=1, M=0, N=1.

Пояснення.

Логічне "І" істинно тоді і тільки тоді, коли істинні обидва твердження.

1) (K → M) = 1 Застосуємо перетворення імплікації: ¬K ∨ M = 1

2) (K → ¬M) = 1 Застосуємо перетворення імплікації: ¬K ∨ ¬M = 1

Звідси випливає, що K = 0.

3) (¬K → (M ∧ ¬L ∧ N)) = 1 Застосуємо перетворення імплікації: K ∨ (M ∧ ¬L ∧ N) = 1 з того, що K = 0 отримуємо:

M ∧ ¬L ∧ N = 1 => M = 1, L = 0, N = 1.

Відповідь: 0011

Відомо, що для цілих чисел X, Y та Z істинно висловлювання

(Z Чому дорівнює Z, якщо X=25 та Y=48?

Пояснення.

Виконавши підстановку чисел отримуємо, що Z = 47.

Звернемо увагу, що цей складний вислів складається з трьох простих

1) (Z 2) ці прості висловлювання пов'язані операцією ∧ (І, кон'юнкція), тобто вони мають виконуватися одночасно.

3) із ¬(Z+1 24, а із ¬(Z+1 47).

4) із (Z Z Відповідь: 47.

Відповідь: 47

A, B і C – цілі числа, котрим істинно висловлювання:

(C Чому дорівнює C, якщо A=45 та B=18?

Пояснення.

Логічне "І" істинно тоді і тільки тоді, коли істинні обидва твердження.

Підставимо значення чисел у вираз:

1) (C (C 2) ¬(C+1 , C ≥ 44).

3) ¬(C+1 , C ≥ 17).

З 2) та 1) випливає, що C

Відповідь: 44

¬(A = B) ∧ ((B A)) ∧ ((A 2C))

Чому дорівнює A, якщо C = 8 і B = 18?

Пояснення.

Логічне "І" істинно тоді і тільки тоді, коли істинні обидва твердження.

1) ¬(А = B) = 1, тобто А ≠ 18 = 1.

2) ((B A)) Застосуємо перетворення імплікації: (18 > A) ∨ (16 > A) = 1

3) (A 2C) Застосуємо перетворення імплікації: (A > 18) ∨ (A > 16) = 1

З 2) і 3) випливає, що (18 > A) і (A > 16), оскільки інакше виникає протиріччя А = 17.

Відповідь: 17

A, B і С – цілі числа, для яких істинно висловлювання

¬(A = B) ∧ ((A > B) → (C = B)) ∧ ((B > A) → (C = A))

Чому дорівнює B, якщо A = 45 та C = 18?

Пояснення.

Логічне " І " істинно лише тоді, коли істинні всі висловлювання.