Інформатика методи розв'язання системи логічних рівнянь. Системи логічних рівнянь у задачах еге з інформатики

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

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 або 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

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

Носкін Андрій Миколайович,
вчитель інформатики
вищої кваліфікаційної категорії,
кандидат військових наук, доцент
ДБОУ Ліцей №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