Метод зведення до одного рівняння у логіці. Розв'язання логічних рівнянь з математики

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

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

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

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

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

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

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?

Пояснення.

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

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

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

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

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

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

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

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