Як вирішувати системи логічних рівнянь еге. логіка. Логічні функції. Розв'язання рівнянь

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

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

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

Комутативність диз'юнкції та кон'юнкції:
a ˅ b ≡ b ˅ a
a^b≡b^a
Дистрибутивний закон щодо диз'юнкції та кон'юнкції:
a ˅ (b^с) ≡ (a ˅ b) ^(a ˅ с)
a ^ (b ˅ с) ≡ (a ^ b) ˅ (a ^ с)
Заперечення заперечення:
¬(¬а) ≡ а
Несуперечність:
a ^ ¬а ≡ false
Виключне третє:
a ˅ ¬а ≡ true
Закони де-Моргана:
¬(а ˅ b) ≡ ¬а ˄ ¬b
¬(а ˄ b) ≡ ¬а ˅ ¬b
Спрощення:
a ˄ a ≡ a
a ˅ a ≡ a
a ˄ true ≡ a
a ˄ false ≡ false
Поглинання:
a ˄ (a ˅ b) ≡ a
a ˅ (a ˄ b) ≡ a
Заміна імплікації
a → b ≡ ¬a ˅ b
Заміна тотожності
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:

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

X 1	X 2	X 3	X 4	F
1	1	0	0	1
0	1	1	1	1
1	0	0	1	0

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

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

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

Завдання 16:

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

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

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

13579
97531
24678
15386

Умовою відповідає число під номером 4.

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

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

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

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

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

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

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

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

A → (B ˄ ¬C)

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

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

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

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

A	B	C	F 1	F 2	F 1 ˄ F 2
0	0	0	1	0	0
0	0	1	1	0	0
0	1	0	1	0	0
0	1	1	1	0	0
1	0	0	0	0	0
1	0	1	0	1	0
1	1	0	1	1	1
1	1	1	0	0	0

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

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

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

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

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

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

Логічне рівняння може мати від 0 до 2n різних рішень. Якщо З дорівнює 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 змінних - x 1, x 2, ... x 5. Перше рівняння можна своє чергу розглядати як систему з 5 рівнянь. Як було показано, система рівнянь фактично є кон'юнкцією логічних функцій. Справедливе й зворотне твердження — кон'юнкцію умов можна як систему рівнянь.

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

Дерево складається з двох рівнів за кількістю змінних рівнянь. Перший рівень визначає першу змінну X 1 . Дві гілки цього рівня відображають можливі значення цієї змінної - 1 і 0. На другому рівні гілки дерева відображають ті можливі значення змінної X 2 , для яких рівняння набуває значення істина. Оскільки рівняння задає імплікацію, то гілка, на якій X 1 має значення 1, вимагає, щоб на цій галузі X 2 мало значення 1. Гілка, на якій X 1 має значення 0, породжує дві гілки зі значеннями X 2 , рівними 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 породжує 25 рішень в змінних X. Дві гілки породжують 2 * 2 5 рішень, так що загальна кількість рішень дорівнює 64.

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

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

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

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

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

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

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

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

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

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

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

///

/// програма підрахунку числа рішень

/// логічного рівняння (системи рівнянь)

///

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

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

///

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

/// число рішень

static int SolveEquations(DF fun, int n)

bool set = New 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);

static bool Fun53(bool vars)

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

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

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

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

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

X 1	X 2	X 3	X 4	F
1	0	0	1	1
0	1	1	1	1
1	0	1	0	0

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Завдання 18

Відповідь: Система має 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

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

Завдання 20

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

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

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

Завдання 21

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

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

Завдання 22

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

Призначення сервісу. Онлайн-калькулятор призначений для побудови таблиці істинності для логічного вираження.
Таблиця істинності – таблиця що містить всі можливі комбінації вхідних змінних та відповідне їм значення на виході.
Таблиця істинності містить 2 n рядків, де n – число вхідних змінних, і n+m – стовпці, де m – вихідні змінні.

Інструкція. Під час введення з клавіатури використовуйте такі позначення:

Наприклад, логічний вираз abc+ab~c+a~bc необхідно ввести так: a*b*c+a*b=c+a=b*c
Для введення даних у вигляді логічної схеми використовуйте цей сервіс.

Правила введення логічної функції

Замість символу v (диз'юнкція, АБО) використовуйте знак + .
Перед логічною функцією не треба вказувати позначення функції. Наприклад, замість F(x,y)=(x|y)=(x^y) необхідно ввести просто (x|y)=(x^y) .
Максимальна кількість змінних дорівнює 10.

Проектування та аналіз логічних схем ЕОМ ведеться за допомогою спеціального розділу математики – алгебри логіки. В алгебрі логіки можна виділити три основні логічні функції: "НЕ" (заперечення), "І" (кон'юнкція), "АБО" (диз'юнкція).
Для створення будь-якого логічного пристрою необхідно визначити залежність кожної з вихідних змінних від діючих вхідних змінних така залежність називається функцією перемикання або функцією алгебри логіки.
Функція алгебри логіки називається цілком певною якщо задані все 2 n її значення, де n – число вихідних змінних.
Якщо визначено в повному обсязі значення, функція називається частково визначеної.
Пристрій називається логічним, якщо його стан описується за допомогою алгебри логіки.
Для представлення функції алгебри логіки використовують такі способи:
За формою алгебри можна побудувати схему логічного пристрою, використовуючи логічні елементи.

Рисунок1- Схема логічного устрою

Усі операції алгебри логіки визначаються таблицями істинностізначень. Таблиця істинності визначає результат виконання операції для всіх можливіх логічних значень вихідних висловлювань. Кількість варіантів, що відображають результат застосування операцій, залежатиме від кількості висловлювань у логічному вираженні. Якщо число висловлювань у логічному вираженні N, то таблиця істинності міститиме 2 N рядків, оскільки існує 2 N різних комбінацій можливих значень аргументів.

Операція НЕ – логічне заперечення (інверсія)

Логічна операція НЕ застосовується до одного аргументу, якою може бути і просте, і складне логічне вираження. Результатом операції НЕ є таке:

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

Для операції заперечення НЕ прийнято такі умовні позначення:
не А, Ā, not A, ¬А, !A
Результат операції заперечення не визначається наступною таблицею істинності:

A	не А
0	1
1	0

Результат операції заперечення істинний, коли вихідне висловлювання хибне, і навпаки.

Операція АБО - логічне складання (диз'юнкція, об'єднання)

Логічна операція АБО виконує функцію об'єднання двох висловлювань, як яких може бути і просте, і складне логічне вираження. Висловлювання, що є вихідними для логічної операції, називають аргументами. Результатом операції АБО є вираз, який буде істинним тоді і тільки тоді, коли істинно буде хоча б один із вихідних виразів.
Позначення, що застосовуються: А або В, А V В, A or B, A||B.
Результат операції АБО визначається наступною таблицею істинності:
Результат операції АБО істинний, коли істинно А, або істинно, або істинно і А і В одночасно, і складний тоді, коли аргументи А і В - помилкові.

Операція І – логічне множення (кон'юнкція)

Логічна операція І виконує функцію перетину двох висловлювань (аргументів), як яких може бути і простий, і складний логічний вираз. Результатом операції І є вираз, який буде істинним тоді і тільки тоді, коли істинні обидва вихідні вирази.
Позначення, що застосовуються: А і В, А Λ В, A & B, A and B.
Результат операції І визначається наступною таблицею істинності:

A	B	А і В
0	0	0
0	1	0
1	0	0
1	1	1

Результат операції І правдивий тоді і тільки тоді, коли істинні одночасно висловлювання А і В, і складний у всіх інших випадках.

Операція «ЯКЩО-ТО» - логічне слідування (імплікація)

Ця операція пов'язує два простих логічних висловлювання, у тому числі перше є умовою, а друге - наслідком цієї умови.
Позначення, що застосовуються:
якщо А, то; А тягне В; if A then; А→В.
Таблиця істинності:

A	B	А → B
0	0	1
0	1	1
1	0	0
1	1	1

Результат операції слідування (імплікації) покладено лише тоді, коли передумова А істинна, а висновок (слідство) хибно.

Операція "А тоді і тільки тоді, коли В" (еквівалентність, рівнозначність)

Позначення, що застосовується: А ↔ В, А ~ В.
Таблиця істинності:

A	B	А↔B
0	0	1
0	1	0
1	0	0
1	1	1

Операція «Додаток за модулем 2» (XOR, що виключає або, сувора диз'юнкція)

Позначення, що застосовується: А XOR В, А ⊕ В.
Таблиця істинності:

A	B	А⊕B
0	0	0
0	1	1
1	0	1
1	1	0

Результат операції еквівалентність істинний тільки тоді, коли А і одночасно істинні або одночасно помилкові.

Пріоритет логічних операцій

Дії у дужках
Інверсія
Кон'юнкція (&)
Диз'юнкція (V), що виключає АБО (XOR), сума за модулем 2
Імплікація (→)
Еквівалентність (↔)

Досконала диз'юнктивна нормальна форма

Досконала диз'юнктивна нормальна форма формули(СДНФ) це рівносильна їй формула, що є диз'юнкцією елементарних кон'юнкцій, що володіє властивостями:

Кожне логічне доданок формули містить усі змінні, що входять до функції F(x 1 ,x 2 ,...x n).
Усі логічні доданки формули різні.
Жоден логічний доданок не містить змінну та її заперечення.
Жоден логічний доданок формули не містить одну й ту саму змінну двічі.

СДНФ можна отримати за допомогою таблиць істинності або за допомогою рівносильних перетворень.
Для кожної функції СДНФ та СКНФ визначено єдиним чином з точністю до перестановки.

Досконала кон'юнктивна нормальна форма

Досконала кон'юнктивна нормальна форма формули (СКНФ)це рівносильна їй формула, що є кон'юнкцією елементарних диз'юнкцій, що задовольняє властивостям:

Всі елементарні диз'юнкції містять усі змінні, що входять до функції F(x 1 ,x 2 ,...x n).
Усі елементарні диз'юнкції різні.
Кожна елементарна диз'юнкція містить один раз змінну.
Жодна елементарна диз'юнкція не містить змінну та її заперечення.

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

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

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

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

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

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

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

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

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

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








0	0	1	1	0	1

Напівжирним виділено рядок, на який виконуються умови завдання. Таким чином, A=0, B=0 та C=1.

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

Рішення 3:Нехай A = 0, тоді:

З першого рівняння отримуємо B =0, та якщо з другого – З=1. Рішення системи: A = 0, B = 0 та C = 1.

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

Завдання:Скільки розв'язків має рівняння (A →B ) + (C →D ) = 1? Де A, B, C, D – логічні змінні.

Рішення:Введемо нові змінні: X = A B і Y = C D . З урахуванням нових змінних рівняння запишеться як: X + Y = 1.

Диз'юнкція вірна у трьох випадках: (0;1), (1;0) та (1;1), при цьому X та Y є імплікацією, тобто є істинною у трьох випадках і хибною – в одному. Тому випадок (0;1) буде відповідати трьом можливим поєднанням параметрів. Випадок (1;1) – відповідатиме дев'яти можливим поєднанням параметрів вихідного рівняння. Отже, всього можливих розв'язків цього рівняння 3+9=15.

Наступний спосіб визначення кількості розв'язків системи логічних рівнянь – бінарне дерево. Розглянемо цей спосіб на прикладі.

Завдання:Скільки різних рішень має система логічних рівнянь:

Наведена система рівнянь рівносильна рівнянню:

(x 1 → x 2 )*(x 2 → x 3 )*…*(x m -1 → x m) = 1.

Припустимо, що x 1 - Істинно, тоді з першого рівняння отримуємо, що x 2 також істинно, з другого - x 3 =1, і так далі x m= 1. Отже набір (1; 1; …; 1) з m одиниць є рішенням системи. Нехай тепер x 1 =0, тоді з першого рівняння маємо x 2 =0 або x 2 =1.

Коли x 2 Істинно отримуємо, що інші змінні також істинні, тобто набір (0; 1; …; 1) є рішенням системи. При x 2 =0 отримуємо, що x 3 =0 або x 3 =, і так далі. Продовжуючи до останньої змінної, отримуємо, що рішеннями рівняння є наступні набори змінних (m +1 рішення, у кожному рішенні по m значень змінних):

(1; 1; 1; …; 1)

(0; 1; 1; …; 1)

(0; 0; 0; …; 0)

Такий підхід добре ілюструється за допомогою побудови бінарного дерева. Кількість можливих рішень – кількість різних гілок збудованого дерева. Легко помітити, що воно дорівнює m+1.

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

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

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

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

x 1	x 2	(x 1 → x 2)

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

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

Тема уроку: Розв'язання логічних рівнянь

Освітня – вивчення способів розв'язання логічних рівнянь, формування умінь та навичок розв'язання логічних рівнянь та побудови логічного вираження за таблицею істинності;

Розвиваюча створити умови у розвиток пізнавального інтересу учнів, сприяти розвитку пам'яті, уваги, логічного мислення;

Виховна : сприяти вихованню вміння вислуховувати думку інших,виховання волі та наполегливості для досягнення кінцевих результатів.

Тип уроку: комбінований урок

Обладнання: комп'ютер, мультимедійний проектор, презентація 6.

Хід уроку

Повторення та актуалізацію опорних знань. Перевірка домашнього завдання (10 хвилин)

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

Виконаємо перевірку домашнього завдання зі спрощення логічних виразів:

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

(перша літера приголосна→друга літера приголосна)٨ (Остання буква голосна → передостання буква голосна)? Якщо таких слів кілька, вкажіть найменше.

1) АННА 2) МАРІЯ 3) ОЛЕГ 4) СТЕПАН

Введемо позначення:

А – перша буква згодна

В – друга буква приголосна

С – остання буква голосна

D – передостання буква голосна

Складемо вираз:

Складемо таблицю:

2. Вкажіть, який логічний вираз рівносильний виразу

Спростимо запис вихідного виразу та запропонованих варіантів:

3. Даний фрагмент таблиці істинності виразу F:

Який вираз відповідає F?

Визначимо значення цих виразів при зазначених значеннях аргументів:

Ознайомлення з темою уроку, виклад нового матеріалу (30 хвилин)

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

1. Розв'язати логічне рівняння

(¬K M) → (¬L M N) = 0

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

Рішення:

Перетворимо вираз(¬K  M) → (¬L  M  N)

Вираз помилкове, коли обидва доданки помилкові. Друге доданок дорівнює 0, якщо M = 0, N = 0, L = 1. У першому доданку K = 0, так як М = 0, а
.

Відповідь: 0100

2. Скільки розв'язків має рівняння (у відповіді вкажіть лише число)?

Рішення: перетворюємо вираз

(A + B) * (C + D) = 1

A+B=1 та C+D=1

2 спосіб: складання таблиці істинності

3 спосіб: побудова СДНФ – досконалої диз'юнктивної нормальної форми функції – диз'юнкції повних правильних елементарних кон'юнкцій.

Перетворимо вихідний вираз, розкриємо дужки для того, щоб отримати диз'юнкцію кон'юнкцій:

(A+B)*(C+D)=A*C+B*C+A*D+B*D=

Доповнимо кон'юнкції до повних кон'юнкцій (твор всіх аргументів), розкриємо дужки:

Врахуємо однакові кон'юнкції:

У результаті отримуємо СДНФ, що містить 9 кон'юнкцій. Отже, таблиця істинності цієї функції має значення 1 на 9 рядках з 2 4 =16 наборів значень змінних.

3. Скільки розв'язків має рівняння (у відповіді вкажіть лише число)?

Спростимо вираз:

3 спосіб: побудова СДНФ

Врахуємо однакові кон'юнкції:

У результаті отримуємо СДНФ, що містить 5 кон'юнкцій. Отже таблиця істинності цієї функції має значення 1 на 5 рядках з 2 4 =16 наборів значень змінних.

Побудова логічного виразу за таблицею істинності:

для кожного рядка таблиці істинності, що містить 1 складаємо добуток аргументів, причому, змінні, рівні 0, входять у твір із запереченням, а змінні, рівні 1 – без заперечення. Шуканий вираз F буде складатися із суми отриманих творів. Потім, якщо можливо, цей вираз необхідно спростити.

Приклад: дано таблицю істинності виразу. Побудувати логічний вираз.

Рішення:

3. Завдання додому (5 хвилин)

Розв'язати рівняння:

Скільки розв'язків має рівняння (у відповіді вкажіть лише число)?

За заданою таблицею істинності скласти логічне вираження та

спростити його.