Складання логічного рівняння (формули) та приведення його до нормальної форми
Для вирішення логічних задач 2 способом (шляхом складання логічного рівняння та приведення його до нормальної форми) потрібно:
1. Уважно вивчити умову.
2. Виділити елементарні (прості) висловлювання і позначити їх – як заведено – великими латинськими літерами.
3. Записати умову задачі на мові алгебри логіки, поєднавши прості висловлювання в складні за допомогою логічних операцій, Ú і т.д.
4. Отриманий вираз спростити, використовуючи закони алгебри логіки; перетворюючи висловлювання, замінити свідомо справжні чи хибні висловлювання (відповідно до умови завдання) їх значенням.
5. Вибрати рішення – набір значень, у якому вираз (п. 3) є істинним.
6. Перевірити, чи задовольняє отримане рішення умові завдання.
Завдання 1. Хто з абітурієнтів А, В, С та D грає, а хто не грає у шахи, якщо відомо:
а) якщо А або грає, то С не грає;
б) якщо не грає, то грають З і D;
Запишемо висловлювання. Отримані вирази спростимо:
а) (А + В) ® `С = А + В + `С = `А` В + `С;
Якщо всі ці справжні висловлювання логічно перемножити, то вийде справжнє складне висловлювання:
( 'А'В + 'С)(B + CD) С = 1
Розкривши дужки, отримаємо: `А`В С D = 1.
Відповідь: C та D грають, А та В не грають.
Завдання 2. Аня, Віка та Сергій вирішили піти в кіно. Вчитель, який добре знав цих хлопців, висловив припущення:
а) Аня піде тільки тоді, коли підуть Віка та Сергій;
б) Аня і Сергій підуть у кіно разом або обоє залишаться вдома;
в) Щоб Сергій пішов у кіно, необхідно щоб пішла Віка.
З трьох тверджень істинними виявилися лише два. Хто з хлопців пішов у кіно?
а) А ®ВС = 'А + ВС(X)
(1) `X = `А + ВС = А × ВС = А × (`В + `С) = А×`В + А×`С; `XYZ = (А×`В + А×`С)(АС + `А`С)(`С +В) = (А`ВС + 0 + 0 + 0)( `С +В) = 0 + 0 = 0
(2) `Y = АС + `А`С = АС × `А`С = (`А + `С) × (А + С) = `АС + А`С; 'YXZ = ('АС + А'С)('А + ВС)('З + В) = ('АС + 'АВС)('С +В) =`АВС
(3) `Z = `З + В = С × `В; 'ZXY = (С × 'В)('А + ВС)(АС + 'А'С) = ('А'С + АВС) ×(С'В) = 0
Відповідь: А = 0, У = 1, З = 1, тобто. у кіно підуть Віка та Сергій, а Аня не піде.
Завдання 3. На запитання, яка буде погода, синоптик відповів:
а) якщо не буде вітру, то буде хмарна погода без дощу;
б) якщо буде дощ, то буде хмарно і без вітру;
в) якщо буде похмура погода, буде дощ і не буде вітру.
Яка буде погода? Що хотів сказати синоптик?
Введемо прості висловлювання:
Р = "Буде похмура погода"
Тоді складові умови завдання запишуться як:
`В® Р`D; б) D® Р`В; с) Р® D`В
Склавши кон'юнкцію цих висловлювань і привівши її до нормальної форми, отримаємо В`Р`D. Таким чином, три висловлювання синоптика можна замінити одним: "Буде ясна погода без дощу, але з вітром".
Вправи
Завдання 1. Увага Андрія, Дениса і Марата привернув автомобіль, що промчався повз них.
- Це англійська машина марки "Феррарі", - сказав Андрій.
- Ні, машина італійська марки "Понтіак", - заперечив Денис.
- Це "Сааб", і зроблено він не в Англії, - сказав Марат.
Знавець автомобілів, що виявився поруч, сказав, що кожен з них правий тільки в одному з двох висловлених припущень.
Який марки цей автомобіль і в якій країні виготовлений?
Рішення: Розглянемо прості висловлювання:
А ="Англійська машина", F = "Феррарі", I = "Італійська", Р = "Понтіак", С = "Сааб".
Запишемо на мові логіки умову завдання, враховуючи висловлювання хлопчиків і те, що чітко вказано або країну або марку автомобіля:
1) A"F = A`F +`A F = 1 (Слова Андрія)
2) I"P = I`P +`I P=1 (Слова Дениса)
3) 'A'C = 'A'C + AC=1 (Слова Марата)
Якщо всі ці справжні висловлювання перемножити, то вийде справжнє складне висловлювання.
(A`F +`A F) & (I `P + `I P) & (`A`C + AC) = 1
Враховуючи, що AI=0; FP=0; PC = 0; FC=0 (машина не може бути одночасно італійською та англійською, «Феррарі», «Понтіак» та «Сааб»),. отримуємо вираз:
I`A F`P`C = 1 Робимовисновок : машина "Феррарі", виготовлена в Італії.
Завдання 2. У клуб службового собаківництва на чергове тренування прийшли зі своїми собаками Антон, Борис, Петро, Віктор та Олег. Бажаючи пожартувати з нового інструктора, на його запитання: «Хто ж господар кожного з собак?», кожен юнак дав одну правильну і одну неправильну відповідь.
Антон сказав: «Мій собака – Рекс, а собака Петра – Лайма». Борис сказав: "Рекс - мій собака, а собака Віктора - Джек". Петро сказав: «Собака Віктора – Зевс, а моя – Рекс». Віктор сказав: «Мій собака – Джек, а собака Олега – Бічо». Олег сказав: «Так, мій собака – Бічо, а собака Бориса – Зевс».
Хто ж насправді господар кожного із собак?
Завдання 3. Троє друзів, уболівальників автоперегонів «Формула-1», сперечалися про результати майбутнього етапу перегонів.
- Ось побачиш, Шумахер не прийде першим, - сказав Джон. - Першим буде Хілл.
— Та ні, переможцем буде, як завжди, Шумахер! - Вигукнув Нік. — А про Алезі й казати нема чого, йому не бути першим. Пітер, до якого звернувся Нік, обурився:
-Хіллу не видно першого місця, а ось Алезі пілотує найпотужнішу машину.
Після завершення етапу перегонів виявилося, що кожне з двох припущень двох друзів підтвердилося, а обидва припущення третього з друзів виявилися невірними. Хто виграв етап перегонів?
(Примітка:висловлювання «Алезі пілотує найпотужнішу машину» зовсім не означає, що він здобуде перемогу)
Самостійна робота №3.
1) Спростити формулу;
2) вирішити задачу шляхом складання логічного рівняння (формули) та приведення його до нормальної форми)
Складання логічного рівняння та вирішення його за допомогою ЕОМ
Для вирішення логічних задач 3 способом (шляхом складання логічного рівняння та розв'язання його за допомогою ЕОМ) необхідно знати наступне:
1) У мові програмування Qbasic логічне значення “істина” кодується числом "-1", а "брехня" кодується числом "0". В умовному операторі після ключового слова IF можна замість умови писати логічну змінну. Приклад: x = 1 : y = 2: z = x