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

Як вирішувати деякі завдання розділів A та B іспиту з інформатики

Урок №3. логіка. Логічні функції. Розв'язання рівнянь

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

1. Комутативність диз'юнкції та кон'юнкції:
   a ˅ b ≡ b ˅ a
   a^b≡b^a
2. Дистрибутивний закон щодо диз'юнкції та кон'юнкції:
   a ˅ (b^с) ≡ (a ˅ b) ^(a ˅ с)
   a ^ (b ˅ с) ≡ (a ^ b) ˅ (a ^ с)
3. Заперечення заперечення:
   ¬(¬а) ≡ а
4. Несуперечність:
   a ^ ¬а ≡ false
5. Виключне третє:
   a ˅ ¬а ≡ true
6. Закони де-Моргана:
   ¬(а ˅ b) ≡ ¬а ˄ ¬b
   ¬(а ˄ b) ≡ ¬а ˅ ¬b
7. Спрощення:
   a ˄ a ≡ a
   a ˅ a ≡ a
   a ˄ true ≡ a
   a ˄ false ≡ false
8. Поглинання:
   a ˄ (a ˅ b) ≡ a
   a ˅ (a ˄ b) ≡ a
9. Заміна імплікації
   a → b ≡ ¬a ˅ b
10. Заміна тотожності
    a ≡ b ≡(a ˄ b) ˅ (¬a ˄ ¬b)

Подання логічних функцій

Будь-яку логічну функцію від n змінних – F(x 1 , x 2 , … x n) можна встановити таблицею істинності. Така таблиця містить 2 n наборів змінних, кожному за яких задається значення функції цьому наборі. Такий спосіб хороший, коли кількість змінних відносно невелика. Вже при n > 5 уявлення стає погано доступним для огляду.

Інший спосіб полягає в тому, щоб задавати функцію деякою формулою, використовуючи досить відомі прості функції. Система функцій (f 1 , f 2 , ... f k ) називається повною, якщо будь-яку логічну функцію можна виразити формулою, що містить лише функції f i .

Повною є система функцій (¬, ˄, ˅). Закони 9 і 10 є прикладами, що демонструють, як імплікація та тотожність виражається через заперечення, кон'юнкцію та диз'юнкцію.

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

(а ˅ b) ≡ ¬(¬а ˄ ¬b)
(а ˄ b) ≡ ¬(¬а ˅ ¬b)

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

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

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

Завдання 15:

Дано фрагмент таблиці істинності. Яка із трьох наведених функцій відповідає цьому фрагменту?

1. (X 1 → X 2) ˄ ¬ X 3 ˅ X 4
2. (¬ X 1 ˄ X 2) ˅ (¬ X 3 ˄ X 4)
3. ¬ X 1 ˅ X 2 ˅ (X 3 ˄ X 4)

Функція за номером 3.

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

Завдання 16:

Яке з наведених чисел задовольняє умову:

(цифри, починаючи зі старшого розряду, йдуть у порядку спадання) → (число – парне) ˄ (молодша цифра – парна) ˄ (старша цифра – непарна)

Якщо таких чисел кілька, вкажіть найбільше.

1. 13579
2. 97531
3. 24678
4. 15386

Умову задовольняє номер під номером 4.

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

Завдання 17: Два свідки дали такі показання:

Перший свідок: Якщо А винний, то В і винний, а С – невинний.

Другий свідок: Винні двоє. А точно винен і винен один із тих, хто залишився, але хто саме сказати не можу.

Які висновки про винність А, В і С можна зробити на підставі показань свідків?

Відповідь: З показань свідків випливає, що А і В винні, а С - невинний.

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

Перше, що потрібно зробити – це формалізувати висловлювання. Введемо три логічні змінні - А, В і С, кожна з яких має значення true (1), якщо відповідний підозрюваний винен. Тоді показання першого свідка задаються формулою:

A → (B ˄ ¬C)

Свідчення другого свідка задаються формулою:

A ˄ ((B ˄ ¬C) ˅ (¬B ˄ C))

Показання обох свідків вважаються істинними і є кон'юнкцією відповідних формул.

Побудуємо таблицю істинності цих показань:

Сумарні показання свідків істинні тільки в одному випадку, що призводять до однозначної відповіді – А і В винні, а С – невинний.

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

Логічні рівняння та системи рівнянь

Нехай F(x 1 , x 2 , … x n) – логічна функція від змінних. Логічне рівняння має вигляд:

F(x 1 , x 2 , … x n) = З,

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

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

F(x 1 , x 2 , … x n) = 1

Справді, нехай задано рівняння:

F(x 1 , x 2 , … x n) = 0

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

¬F(x 1 , x 2 , …x n) = 1

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

F 1 (x 1 x 2 … x n) = 1

F 2 (x 1 x 2 … x n) = 1

F k (x 1 x 2 … x n) = 1

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

Ф = F 1 ˄ F 2 ˄ … F k

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

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

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

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

Завдання 18

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

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

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

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

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

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

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

(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
має 6 рішень. Ось як виглядає повне дерево рішень для цього рівняння:

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

(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1

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

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

Завдання 19

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

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

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

Завдання 20

(¬X 1 ˅ X 2) ˄ (¬X 2 ˅ X 3) ˄ (¬X 3 ˅ X 4) ˄ (¬X 4 ˅ X 5) ˄ (¬X 5 ˅ X 1) = 1

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

(X 1 → X 2) ˄ (X 2 → X 3) ˄ (X 3 → X 4) ˄ (X 4 → X 5) ˄ (X 5 → X 1) = 1

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

X 1 ≡ X 2 ≡ X 3 ≡ X 4 ≡ X 5 = 1

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

Завдання 21

(X 1 → X 2) ˄ (X 2 → X 3) ˄ (X 3 → X 4) ˄ (X 4 → X 2) ˄ (X 4 → X 5) = 1

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

(X 1 → X 2) ˄ (X 2 ≡ X 3 ≡ X 4) ˄ (X 4 → X 5) = 1

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

Завдання 22

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

((X 1 ≡X 2) ˄ (X 3 ≡X 4)) ˅(¬(X 1 ≡X 2) ˄ ¬(X 3 ≡X 4)) = 0

((X 3 ≡X 4) ˄ (X 5 ≡X 6)) ˅(¬(X 3 ≡X 4) ˄ ¬(X 5 ≡X 6)) = 0

((X 5 ≡X 6) ˄ (X 7 ≡X 8)) ˅(¬(X 5 ≡X 6) ˄ ¬(X 7 ≡X 8)) = 0

((X 7 ≡X 8) ˄ (X 9 ≡X 10)) ˅(¬(X 7 ≡X 8) ˄ ¬(X 9 ≡X 10)) = 0

Відповідь: 64

Рішення: Перейдемо від 10 змінних до 5 змінних, ввівши наступну заміну змінних:

Y 1 = (X 1 ≡ X 2); Y 2 = (X 3 ≡ X 4); Y 3 = (X 5 ≡ X 6); Y 4 = (X 7 ≡ X 8); Y 5 = (X 9 ≡ X 10);

Тоді перше рівняння набуде вигляду:

(Y 1 ˄ Y 2) ˅ (¬Y 1 ˄ ¬Y 2) = 0

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

(Y 1 ≡ Y 2) = 0

Переходячи до традиційної форми, запишемо систему після спрощень у вигляді:

¬(Y 1 ≡ Y 2) = 1

¬(Y 2 ≡ Y 3) = 1

¬(Y 3 ≡ Y 4) = 1

¬(Y 4 ≡ Y 5) = 1

Дерево рішень для цієї системи просте і складається з двох гілок з значеннями змінних, що чергуються:

Повертаючись до вихідних змінних X, зауважимо, що кожному значенню змінної Y відповідає 2 значення змінних X, тому кожне рішення в змінних Y породжує 2 5 рішень у змінних X. Дві гілки породжують 2 * 2 5 рішень, так що загальна кількість рішень дорівнює 64.

Як бачите, кожне завдання вирішення системи рівнянь вимагає свого підходу. Загальним прийомом є виконання еквівалентних перетворень спрощення рівнянь. Спільним прийомом є і побудова дерев рішень. Застосовуваний підхід частково нагадує побудову таблиці істинності з тією особливістю, що будуються в повному обсязі набори можливих значень змінних, лише ті, у яких функція приймає значення 1 (істина). Часто в пропонованих задачах немає необхідності в побудові повного дерева рішень, оскільки вже на початковому етапі вдається встановити закономірність появи нових гілок на кожному наступному рівні, як це зроблено, наприклад, завдання 18.

Загалом завдання знайти рішення систем логічних рівнянь є хорошими математичними вправами.

Якщо завдання важко розв'язати вручну, можна доручити розв'язання завдання комп'ютеру, написавши відповідну програму розв'язання рівнянь і систем рівнянь.

Написати таку програму нескладно. Така програма легко впорається з усіма завданнями, які пропонуються в ЄДІ.

Як це не дивно, але завдання знаходження рішень систем логічних рівнянь є складним і для комп'ютера, виявляється і комп'ютер має свої межі. Комп'ютер може досить просто впоратися із завданнями, де кількість змінних 20 -30, але почне надовго замислюватися на завдання більшого розміру. Справа в тому, що функція 2 n , що задає число наборів, є експонентою, що швидко зростає зі збільшенням n. Настільки швидко, що звичайний персональний комп'ютер за добу не впорається із завданням, яке має 40 змінних.

Програма мовою C# для розв'язання логічних рівнянь

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

Ідея побудови програми проста, вона заснована на повному переборі всіх можливих наборів значень змінних. Оскільки для заданого логічного рівняння або системи рівнянь кількість змінних n відома, то відомо і число наборів - 2 n, які потрібно перебрати. Використовуючи базові функції мови C# - заперечення, диз'юнкцію, кон'юнкцію та тотожність, неважко написати програму, яка для заданого набору змінних обчислює значення логічної функції, що відповідає логічному рівнянню або системі рівнянь.

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

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

Ось як виглядає функція мовою C#, яка вирішує наше завдання:

///

///

/// логічна функція - метод,

/// сигнатура якого задається делегатом DF

///

/// кількість змінних

/// кількість рішень

static int SolveEquations(DF fun, int n)

bool set = новий bool [n];

int m = (int) Math.Pow (2, n); // число наборів

int p = 0, q = 0, k = 0;

//Повний перебір за кількістю наборів

for (int i = 0; i< m; i++)

//Формування чергового набору - set,

//заданого двійковим уявленням числа i

for (int j = 0; j< n; j++)

k = (int) Math.Pow (2, j);

//Обчислення значення функції на наборі set

Для розуміння програми, сподіваюся, достатньо зроблених пояснень ідеї програми та коментарів у її тексті. Зупинюся лише з поясненні заголовка наведеної функції. У функції SolveEquations два вхідні параметри. Параметр fun задає логічну функцію, що відповідає рівнянню, що вирішується, або системі рівнянь. Параметр n визначає кількість змінних функції fun. Як результат функція SolveEquations повертає число рішень логічної функції, тобто кількість тих наборів, у яких функція приймає значення true.

Для школярів звично, коли деякою функцією F(x) вхідним параметром x є змінна арифметичного, рядкового чи логічного типу. У нашому випадку використовується потужніша конструкція. Функція SolveEquations відноситься до функцій вищого порядку - функцій типу F(f), у яких параметрами можуть бути не тільки прості змінні, але й функції.

Клас функцій, які можуть передаватися як параметр функції SolveEquations, задається таким чином:

delegate bool DF(bool vars);

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

Насамкінець наведу програму, в якій функція SolveEquations використовується для вирішення декількох систем логічних рівнянь. Функція SolveEquations є частиною наведеного нижче класу ProgramCommon:

class ProgramCommon

delegate bool DF(bool vars);

static void Main(string args)

Console.WriteLine(«У Функції And рішень —» +

SolveEquations(FunAnd, 2));

Console.WriteLine(«У Функції 51 рішень -» +

SolveEquations(Fun51, 5));

Console.WriteLine(«У Функції 53 рішень -» +

SolveEquations(Fun53, 10));

static bool FunAnd(bool vars)

return vars && vars;

static bool Fun51(bool vars)

f = f && (!vars ||vars);

f = f && (!vars ||vars);

f = f && (!vars ||vars);

f = f && (!vars ||vars);

f = f && (!vars ||vars);

static bool Fun53(bool vars)

f = f && ((vars == vars) || (vars == vars));

f = f && ((vars == vars) || (vars == vars));

f = f && ((vars == vars) || (vars == vars));

f = f && ((vars == vars) || (vars == vars));

f = f && ((vars == vars) || (vars == vars));

f = f && ((vars == vars) || (vars == vars));

f = f && (!((vars == vars) || (vars == vars)));

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

10 завдань для самостійної роботи

1. Які з трьох функцій еквівалентні:
   1. (X → Y) ˅ ¬Y
   2. ¬(X ˅ ¬Y) ˄ (X → ¬Y)
   3. ¬X ˄ Y
2. Дано фрагмент таблиці істинності:

Який із трьох функцій відповідає цей фрагмент:

1. (X 1 ˅ ¬X 2) ˄ (X 3 → X 4)
2. (X 1 → X 3) ˄ X 2 ˅ X 4
3. X 1 ˄ X 2 ˅ (X 3 → (X 1 ˅ X 4))
4. До складу журі входять троє людей. Рішення приймається, якщо за нього голосує голова журі, підтриманий хоча б одним із членів журі. В іншому випадку рішення не ухвалюється. Побудуйте логічну функцію, що формалізує процес ухвалення рішення.
5. X виграє у Y, якщо за чотирьох киданнях монети тричі випадає «орел». Вкажіть логічну функцію, яка описує виграш X.
6. Слова у реченні нумеруються, починаючи з одиниці. Пропозиція вважається правильно побудованою, якщо виконуються такі правила:
   1. Якщо парне в нумерації слово закінчується на голосну, то наступне слово, якщо воно існує, має починатися з голосної.
   2. Якщо непарне в нумерації слово закінчується приголосною, то наступне слово, якщо воно існує, повинне починатися із приголосною і закінчуватися голосною.
      Які з наступних пропозицій правильно побудовані:
   3. Мама мила Машу милом.
   4. Лідер завжди є взірцем.
   5. Правда добре, а щастя краще.
7. Скільки рішень має рівняння:
   (a ˄ ¬ b) ˅ (¬ a ˄ b) → (c ˄ d) = 1
8. Перелічіть усі рішення рівняння:
   (a → b) → c = 0
9. Скільки рішень має така система рівнянь:
   X 0 → X 1 ˄ X 1 → X 2 = 1
   X 2 → X 3 ˄ X 3 → X 4 = 1
   X 5 → X 6 ˄ X 6 → X 7 = 1
   X 7 → X 8 ˄ X 8 → X 9 = 1
   X 0 → X 5 = 1
10. Скільки рішень має рівняння:
    ((((X 0 → X 1) → X 2) → X 3) → X 4) → X 5 = 1

Відповіді до завдань:

1. Еквівалентними є функції b та c.
2. Фрагмент відповідає функції b.
3. Нехай логічна змінна P набуває значення 1, коли голова журі голосує «за» ухвалення рішення. Змінні M 1 та M 2 представляють думку членів журі. Логічна функція, що задає прийняття позитивного рішення, може бути записана так:
   P ˄ (M 1 ˅ M 2)
4. Нехай логічна змінна P i приймає значення 1, коли при i-му киданні монети випадає орел. Логічна функція, що задає виграш X, може бути записана так:
   ¬((¬P 1 ˄ (¬P 2 ˅ ¬P 3 ˅ ¬P 4)) ˅
   (¬P 2 ˄ (¬P 3 ˅ ¬P 4)) ˅
   (¬P 3 ˄ ¬P 4))
5. Пропозиція b.
6. Рівняння має 3 рішення: (a = 1; b = 1; c = 0); (a = 0; b = 0; c = 0); (a = 0; b = 1; c = 0)

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

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

Константа має значення 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

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

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

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

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

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

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

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

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

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

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

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

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

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

приклад.

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

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

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

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

Рішення:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1

x1/y1 =1

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

Рішення :

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

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

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

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

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

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

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

………………

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

(X1 ≡ X10) = 0

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

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

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

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

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

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

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

……

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

(X1 ≡ X10) = 0

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

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

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

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

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

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

приклад 3.

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

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

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

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

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

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

Рішення:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

І т.д.

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

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

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

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

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

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

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