Скільки розв'язків має система логічних рівнянь. Логіка

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

0	0	1	1	0	1

Напівжирним виділено рядок, на який виконуються умови завдання. Таким чином, 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.

Змінні	Дерево	Кількість рішень
x 1
x 2
x 3

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

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

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

x 1	x 2	(x 1 → x 2)

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

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

Далі можна побачити, що одне рівняння є істинним у наступних трьох випадках: (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 корені:

		X1 ≡ X2

З цієї ж таблиці видно, що рівняння А = 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 ∧ ¬ X10	(X1 ∧ X10) ∨ (¬X1 ∧ ¬ X10)

Зверніть увагу на останній стовпець, він збігається з результатом дії X1 ≡ 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 коренів.

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

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

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

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

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

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

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

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

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

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

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

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

0	0	1	1	0	1

Напівжирним виділено рядок, на який виконуються умови завдання. Таким чином, 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.

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

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

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

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

x 1	x 2	(x 1 → x 2)

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

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

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 і С - цілі числа, для яких істинно висловлювання

¬ (А = 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 відразу слідує, що А B;

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) навряд чи ви зможете відразу написати значення функції Х для кожної комбінації, тому зручно додати до таблиці додаткові стовпці для розрахунку проміжних результатів (див. таблицю нижче)

X0

А	В	З
0	0
0	1	1
0	0	1
1	0	1
1	1	1
0	1	0
1	0	0
1	1	0

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

А	В	З					X
0	0	0	1	0	1	0	1
0	1	1	0	1	1	0	0
0	0	1	1	1	1	0	1
1	0	1	0	1	1	0	0
1	1	1	1	1	1	0	1
0	1	0	0	1	1	0	0
1	0	0	0	0	0	1	1
1	1	0	1	1	1	0	1

значення дорівнює 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 отримуємо.

Нехай - Логічна функція від n змінних. Логічне рівняння має вигляд:

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

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

Справді, нехай встановлено рівняння:

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

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

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

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

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

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

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

Завдання 18

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

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

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

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

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

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

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

має 6 рішень. Ось як виглядає повне дерево рішень для цього рівняння:

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

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

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

Завдання 19

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

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

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

Завдання 20

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

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

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

Завдання 21

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

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

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

Завдання 22

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