Таблиці істинності логічних операцій як вирішувати. Тотожні перетворення логічних виразів

Сьогодні ми поговоримо про предмет із назвою інформатика. Таблиця істинності, різновиди функцій, порядок їх виконання – це наші основні питання, на які ми намагатимемося знайти відповіді у статті.

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

Предмет логіки

Що ж це за предмет – інформатика? Таблиця істинності – як її будувати? Для чого потрібна наука логіка? На всі ці запитання ми зараз із вами відповімо.

Інформатика – це досить цікавий предмет. Він не може викликати складнощі у сучасного суспільства, адже все, що нас оточує, так чи інакше, відноситься до комп'ютера.

Основи науки логіки даються викладачами середньої школи під час уроків інформатики. Таблиці істинності, функції, спрощення виразів – усе це мають пояснювати вчителі інформатики. Ця наука просто необхідна у нашому житті. Придивіться, все підкоряється будь-яким законам. Ви підкинули м'яч, він підлетів угору, але після цього впав знову на землю, це сталося через закони фізики і сили земного тяжіння. Мама варить суп та додає сіль. Чому коли ми його їмо, нам не трапляються крупинки? Все просто, сіль розчинилася у воді, підкоряючись законам хімії.

Тепер зверніть увагу, як ви розмовляєте.

• «Якщо я відвезу свого кота до ветеринарної клініки, то йому зроблять щеплення».
• «Сьогодні був дуже тяжкий день, бо приходила перевірка».
• «Я не хочу йти до університету, бо сьогодні буде колоквіум» і таке інше.

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

Функції

Для того щоб скласти таблицю істинності до запропонованого вам завдання, необхідно знати логічні функції. Що це таке? Логічна функція має деякі змінні, які є твердженнями (істинними чи хибними), і саме значення функції має дати нам відповідь на запитання: «Вираз істинно чи хибно?».

Усі висловлювання приймають такі значення:

• Істина чи брехня.
• І чи Л.
• 1 чи 0.
• Плюс чи мінус.

Тут віддавайте перевагу тому способу, який для вас є зручнішим. Для того, щоб скласти таблицю істинності, нам потрібно перерахувати всі комбінації змінних. Їх кількість обчислюється за такою формулою: 2 у ступені n. Результат обчислення - це кількість можливих комбінацій, змінної n у цій формулі позначається кількість змінних за умови. Якщо вираз має багато змінних, можна скористатися калькулятором чи зробити собі невелику таблицю зі зведенням двійки в ступінь.

Всього в логіці виділяють сім функцій або зв'язків, що поєднують вирази:

• Множення (кон'юнкція).
• Додавання (диз'юнкція).
• Наслідок (імплікація).
• Еквівалентність.
• Інверсія
• Штрих Шеффера.
• Стрілка Пірса.

Перша операція, подана у списку, має назву «логічне множення». Її графічно можна відзначити як перевернутої галочки, знаками & чи *. Друга в нашому списку операція – логічне додавання, графічно позначається у вигляді галочки, +. Імплікацію називають логічним наслідком, що позначається у вигляді стрілки, що вказує від умови на слідство. Еквіваленція позначається двосторонньою стрілкою, функція має справжнє значення тільки в тих випадках, коли обидва значення приймають або значення «1», або «0». Інверсію називають логічним запереченням. Штрих Шеффера називають функцією, що заперечує кон'юнкцію, а стрілку Пірса – функцією, що заперечує диз'юнкцію.

Основні двійкові функції

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

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

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

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

Еквіваленція є істиною лише у випадках однакових значень вхідних даних. Тобто при парах: "0; 0" або "1; 1".

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

Штрих Шиффера буде на виході мати хибний результат лише за наявності двох істинних виразів.

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

В якому порядку виконувати логічні операції

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

• логічне заперечення;
• множення;
• додавання;
• слідство;
• еквівалентність;
• заперечення множення (штрих Шеффера);
• заперечення додавання (стрілка Пірса).

Приклад №1

Зараз пропонуємо розглянути приклад побудови таблиці істинності для 4 змінних. Необхідно дізнатися, у яких випадках F=0 у рівняння: неА+В+С*D

Відповіддю це завдання буде перерахування наступних комбінацій: «1;0;0;0», «1;0;0;1» і «1;0;1;0». Як бачите, складати таблицю істинності досить легко. Ще раз хочеться звернути увагу на порядок виконання дій. У конкретному випадку він був таким:

1. Інверсія першого простого висловлювання.
2. Кон'юнкція третього та четвертого виразу.
3. Диз'юнкція другого виразу з результатами попередніх обчислень.

Приклад №2

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

• Якщо Ваня не крав чи Петя крав, то Сергій взяв участь у крадіжці.
• Якщо Ваня не винен, то й Сергій м'яч не крав.

Введемо позначення: І – Ваня вкрав м'яч; П – Петя вкрав; С – Сергій вкрав.

За цією умовою ми можемо скласти рівняння: F=((неІ+П) імплікація С)*(неІ імплікація неС). Нам потрібні ті варіанти, де функція набуває справжнього значення. Далі потрібно скласти таблицю, оскільки дана функція має цілих 7 процесів, ми їх опустимо. Вноситимемо тільки вхідні дані та результат.

Зверніть увагу на те, що в цьому завданні ми замість знаків "0" і "1" використовували плюс і мінус. Це також прийнятно. Нас цікавлять комбінації, де F = +. Проаналізувавши їх, ми можемо зробити наступний висновок: Ваня брав участь у крадіжці м'яча, тому що у всіх випадках, де F набуває значення +, І має позитивне значення.

Приклад №3

Наразі пропонуємо вам знайти кількість комбінацій, коли F=1. Рівняння має такий вигляд: F=неА+В*А+неВ. Складаємо таблицю істинності:

Відповідь: 4 комбінації.

Основні логічні операції

Заперечення (інверсія), від латинського inversio -перевертаю:

Відповідає частинці НЕ, словосполучення НЕВЕРНО, ЩО;

Позначення: не A, A, -A;

таблиця істинності:

Інверсія логічної змінної істинна, якщо сама змінна помилкова, і, навпаки, інверсія помилкова, якщо змінна істинна.

Приклад: A = (На вулиці йде сніг).

A=(Не вірно, що на вулиці йде сніг)

A=(На вулиці не йде сніг);

Логічне складання (диз'юнкція), від латинського disjunctio - розрізняю:

Відповідає союзу АБО;

Позначення: + або or, V;

Таблиця істинності:

Диз'юнкція хибна тоді і лише тоді, коли обидва висловлювання хибні.

Приклад: F = (На вулиці світить сонце або дме сильний вітер);

Логічне множення (кон'юкція), від латинського conjunctio -зв'язую:

Відповідає союзу І

(в природній мові: і А, і В, як А, так і, А разом з В, А, не дивлячись на В, А, в той час як В);

Позначення: Ч, , &, та, ^, and;

Таблиця істинності:

Кон'юкція істинна тоді й тільки тоді, коли обидва висловлювання є істинними.

Приклад: F = (На вулиці світить сонце і дме сильний вітер);

Будь-яке складне висловлювання можна записати за допомогою основних логічних операцій І, АБО, НЕ. За допомогою логічних схем І, АБО, НЕ можна реалізувати логічну функцію, що описує роботу різних пристроїв комп'ютера.

2) Таблиця істинності - це таблиця, що визначає логічну функцію.

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

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

Кон'юнкція - логічна операція, за своїм застосуванням максимально наближена до союзу "і". логічне множення, іноді просто "І".

Диз'юнкція-логічна операція, за своїм застосуванням максимально наближена до союзу "або" в сенсі "або те, або це, або обидва відразу". логічне складення, іноді просто «АБО».

Імплікація - бінарна логічна зв'язка, що за своїм застосуванням наближена до союзів «якщо…то…». Імплікація записується як посилка слідство; застосовуються також стрілки іншої форми та направлені в інший бік (вістря завжди вказує на слідство).

Еквівалентність (або еквівалентність) - двомісна логічна операція. Зазвичай позначається символом ≡ або ↔.

7 . Логічні вирази, таблиці істинності логічних виразів.

Логічне вираз – запис чи усне твердження, у якому, поруч із постійними, обов'язково входять змінні величини (об'єкти). Залежно від значень цих змінних логічний вираз може набувати одне з двох можливих значень: ІСТИНА (логічна 1) або БРЕХНЯ (логічний 0)

Складне логічне вираз – логічне вираз, складене з однієї чи кількох простих (чи складних) логічних висловів, що з допомогою логічних операцій.

Логічні операції та таблиці істинності

Логічне множення КОН'ЮНКЦІЯ - це нове складне вираження буде істинним лише тоді, коли істинні обидва вихідні прості вирази. Кон'юнкція визначає поєднання двох логічних виразів за допомогою спілки І.

Логічне додавання – ДИЗЬЮНКЦІЯ - це нове складне вираз буде істинним тоді і тільки тоді, коли істинно хоча б один із вихідних (простих) виразів. Диз'юнкція визначає поєднання двох логічних виразів за допомогою союзу АБО

Логічне заперечення: ІНВЕРСІЯ - якщо вихідний вираз істинний, то результат заперечення буде хибним, і навпаки, якщо вихідний вираз хибний, то результат заперечення буде істинним/ Дана операція означає, що до вихідного логічного виразу додається частка НЕ ​​або слова НЕВЕРНО

Логічне слідування: ІМПЛІКАЦІЯ - пов'язує два простих логічних вирази, з яких перше є умовою (А), а друге (В) – наслідком цієї умови. Результатом ІМПЛІКАЦІЇ є брехня тільки тоді, коли умова А істинна, а слідство В хибне. Позначається символом "отже" і виражається словами ЯКЩО … , ТО …

Логічна рівнозначність: ЕКВІВАЛЕНТНІСТЬ - визначає результат порівняння двох простих логічних виразів А і В. Результатом ЕКВІВАЛЕНТНОСТІ є нове логічне вираження, яке буде істинним тоді і тільки тоді, коли обидва вихідні вирази одночасно істинні чи хибні. Позначається символом "еквівалентності"

Порядок виконання логічних операцій у складному логічному вираженні:

1. інверсія

2. кон'юнкція

3. диз'юнкція

4. імплікація

5. еквівалентність

Для зміни зазначеного порядку виконання операцій використовуються дужки.

Побудова таблиць істинності для складних виразів:

Кількість рядків = 2n + два рядки для заголовка (n – кількість простих висловлювань)

Кількість стовпців = кількість змінних + кількість логічних операцій

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

ПРИКЛАД: скласти таблицю істинності складного логічного виразу D = неA & (B+C)

А,В, З - три простих висловлювання, тому:

кількість рядків = 23 +2 = 10 (n = 3, т.к. на вході три елементи А, В, С)

кількість стовпців: 1) А

4) не A це інверсія А (позначимо Е)

5) B + C це операція диз'юнкції (позначимо F)

6) D = неA&(B+C), тобто. D = E&F це операція кон'юнкції

А В З E = не А (не 1) F = В+С (2+3) D = E&F (4*5)

Алгебра логіки

Алгебра логіки

Алгебра логіки(Англ. algebra of logic) - один із основних розділів математичної логіки, в якому методи алгебри використовуються в логічних перетвореннях.

Основоположником алгебри логіки є англійський математик і логік Дж. Буль (1815-1864), який поклав основою свого логічного вчення аналогію між алгеброю і логікою. Будь-яке висловлювання він записував за допомогою символів розробленої ним мови та отримував «рівняння», істинність чи хибність яких можна було довести, виходячи з певних логічних законів, таких як закони комутативності, дистрибутивності, асоціативності та ін.

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

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

Наприклад, «3 помножити на 3 і 9», «Архангельськ на північ від Вологди» — справжні висловлювання, а «П'ять менше трьох», «Марс — зірка» — хибні.

Очевидно, що не всяка пропозиція може бути логічним висловлюванням, тому що не завжди є сенс говорити про його хибність чи істинність. Наприклад, вислів «Інформатика – цікавий предмет» невизначений і вимагає додаткових відомостей, а вислів «Для учня 10-А класу Іванова А. А. інформатика – цікавий предмет» залежно від інтересів Іванова А. А. може набувати значення «істина» або «брехня».

Крім двозначної алгебри висловлювань, в якій приймаються тільки два значення - "істинно" і "хибно", існує багатозначна алгебра висловлювань.У такій алгебрі, крім значень «істинно» і «хибно», вживаються такі істинні значення, як «ймовірно», «можливо», «неможливо» тощо.

У алгебрі логіки різняться прості(елементарні) висловлювання, що позначаються латинськими літерами (A, B, C, D, …), та складні(складові), складені з декількох простих за допомогою логічних зв'язок, наприклад, таких, як "ні", "і", "або", "тоді і тільки тоді", "якщо ... то". Істинність чи хибність одержуваних таким чином складних висловлювань визначається значенням простих висловлювань.

Позначимо як Ависловлювання «Алгебра логіки успішно застосовується в теорії електричних схем», а через В- "Алгебра логіки застосовується при синтезі релейно-контактних схем".

Тоді складний вислів «Алгебра логіки успішно застосовується в теорії електричних ланцюгів і при синтезі релейно-контактних схем» можна коротко записати як А і В; тут "і" - логічна зв'язка. Вочевидь, оскільки елементарні висловлювання А і Вістинні, то істинно і складне висловлювання А і В.

Кожна логічна зв'язка розглядається як операція над логічними висловлюваннями та має свою назву та позначення.

Логічних значень лише два: істина (TRUE)і брехня (FALSE). Це відповідає цифровому уявленню. 1 і 0 . Результати кожної логічної операції можна записати як таблиці. Такі таблиці називають таблицями істинності.

Основні операції алгебри логіки

1. Логічне заперечення, інверсія(Лат. inversion- перевертання) - логічна операція, в результаті якої з цього висловлювання (наприклад, А) виходить нове висловлювання ( не А), яке називається запереченням вихідного висловлювання, позначається символічно рисою зверху ($A↖(-)$) або такими умовними позначеннями, як ¬, "not", і читається: "не А", "А хибно", "невірно, що А", "заперечення А". Наприклад, "Марс - планета Сонячної системи" (висловлювання А); "Марс - не планета Сонячної системи" ($A↖(-)$); висловлювання «10 — просте число» (висловлювання) помилкове; висловлювання "10 - не просте число" (висловлювання B) істинно.

Операція, що використовується щодо однієї величини, називається унарної. Таблиця значень цієї операції має вигляд

Висловлювання $A↖(-)$ хибно, коли А істинно, і істинно, коли А хибно.

Геометрично заперечення можна так: якщо А — це кілька точок, то $A↖(-)$ — це доповнення безлічі А, т. е. всі точки, які належать безлічі А.

2.Кон'юнкція(Лат. conjunctio- з'єднання) - логічне множення, операція, що вимагає як мінімум двох логічних величин (операндів) і що з'єднує два або більше висловлювань за допомогою зв'язки «і»(наприклад, «А та В»), яка символічно позначається за допомогою знака ∧ (А ∧ В) та читається: «А та В». Для позначення кон'юнкції застосовуються такі знаки: А∙В; А&В, А&В, Іноді між висловлюваннями не ставиться жодного знака: АВ. Приклад логічного множення: «Цей трикутник рівнобедрений та прямокутний». Дане висловлювання може бути істинним тільки в тому випадку, якщо виконуються обидві умови, інакше висловлювання є хибним.

A	B	A ∧ B
1	0	0
0	1	0
0	0	0
1	1	1

Висловлювання А ∧ Вістинно тільки тоді, коли обидва висловлювання — Аі Вістинні.

Геометрично кон'юнкцію можна представити так: якщо А, В А ∧ Вє перетин множин Аі В.

3. Диз'юнкція(Лат. disjunction- поділ) - логічне додавання, операція, що з'єднує два або більше висловлювань за допомогою зв'язки «або»(наприклад, «А чи В»), яка символічно позначається за допомогою знака ∨ (А∨ В)і читається: «А чи В». Для позначення диз'юнкції застосовуються такі знаки: А+В; А or; А | B. Приклад логічного додавання: «Число x ділиться на 3 або 5». Це висловлювання буде істинним, якщо виконуються обидві умови або хоча б одна з умов.

Таблиця істинності операції має вигляд

A	B	A ∨ B
1	0	1
0	1	1
0	0	0
1	1	1

Висловлювання А∨ Вхибно тільки тоді, коли обидва висловлювання Аі Впомилкові.

Геометрично логічне складання можна так: якщо А, В- це деякі множини точок, то А ∨ В- це об'єднання множин Аі В, тобто фігура, що поєднує і квадрат, і коло.

4. Диз'юнкція строго-розділювальна, додавання по модулю два— логічна операція, що поєднує два висловлювання за допомогою зв'язки «або», вживаної у винятковому сенсі, яка символічно позначається за допомогою знаків ∨ ∨ або ⊕ ( А ∨ ∨ В, А ⊕ В) і читається: "або А, або В". Приклад додавання по модулю два — вислів «Цей трикутник тупокутний або гострокутний». Вислів істинний, якщо виконується якась одна з умов.

Таблиця істинності операції має вигляд

А	В	А⊕ B
1	0	1
0	1	1
0	0	0
1	1	0

Висловлювання А ⊕ В істинно тільки тоді, коли висловлювання А і мають різні значення.

5. Імплікація(Лат. implisito- тісно пов'язую) - логічна операція, що поєднує два висловлювання за допомогою зв'язки "якщо то"у складне висловлювання, яке символічно позначається за допомогою знака → ( А → В) і читається: «якщо А, то», «А тягне», «з А випливає», «А імплікує». Для позначення імплікації також застосовується знак ⊃ (A ⊃ B). Приклад імплікації: «Якщо отриманий чотирикутник квадрат, біля нього можна описати окружність». Ця операція пов'язує два простих логічних висловлювання, у тому числі перше є умовою, а друге — наслідком. Результат операції покладено лише тоді, коли передумова є істина, а наслідок – брехня. Наприклад, «Якщо 3 * 3 = 9 (А), то Сонце – планета (В)», результат імплікації А → В – брехня.

Таблиця істинності операції має вигляд

А	В	А→В
1	0	0
0	1	1
0	0	1
1	1	1

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

6. Еквівалентність, подвійна імплікація, рівнозначність(Лат. aequalis- рівний і valentis- має силу) - логічна операція, що дозволяє з двох висловлювань Аі Вотримати новий вислів А ≡ В, яке читається: "А еквівалентно B". Для позначення еквівалентності використовуються також такі знаки: ⇔, ∼. Ця операція може бути виражена зв'язками "тоді і тільки тоді", "необхідно і достатньо", "рівносильно". Прикладом еквівалентності є висловлювання: «Трикутник буде прямокутним тоді і лише тоді, коли один із кутів дорівнює 90 градусам».

Таблиця істинності операції еквівалентності має вигляд

А	В	А∼ В
1	0	0
0	1	0
0	0	1
1	1	1

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

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

Пріоритет виконання логічних операцій наступний: заперечення ( «ні») має найвищий пріоритет, потім виконується кон'юнкція ( «і»), після кон'юнкції - диз'юнкція ( «або»).

За допомогою логічних змінних та логічних операцій будь-яке логічне висловлювання можна формалізувати, тобто замінити логічною формулою. При цьому елементарні висловлювання, що утворюють складове висловлювання, можуть абсолютно не пов'язані за змістом, але це не заважає визначати істинність або помилковість складеного висловлювання. Наприклад, висловлювання «Якщо п'ять більше двох ( А), то вівторок завжди настає після понеділка ( В)» - імплікація А→ В, і результат операції в даному випадку – «істина». У логічних операціях сенс висловлювань не враховується, розглядається лише їхня істинність чи хибність.

Розглянемо, наприклад, побудову складного висловлювання з висловлювань Аі В, Що було б помилкове тоді і тільки тоді, коли обидва висловлювання істинні. У таблиці істинності для операції додавання по модулю знаходимо: 1 ⊕ 1 = 0. А висловлювання може бути, наприклад, таким: «Цей м'яч повністю червоний або повністю синій». Отже, якщо затвердження А"Цей м'яч повністю червоний" - істина, і твердження В"Цей м'яч повністю синій" - істина, то складне твердження - брехня, тому що одночасно і червоним, і синім м'яч бути не може.

Приклади розв'язання задач

приклад 1.Визначити для зазначених значень X значення логічного висловлювання ((X > 3) ∨ (X< 3)) → (X < 4) :

1) X = 1; 2) X = 12; 3) X = 3.

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

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

Звідси отримуємо:

1) для X = 1:

((1 > 3) ∨ (1 < 3)) → (1 < 4) = ложь ∨ истина → истина = истина → истина = истина;

2) для X = 12:

((12 > 3) ∨ (12 < 3) → (12 < 4) = истина ∨ ложь → ложь = истина → ложь = ложь;

3) для X = 3:

((3 > 3) ∨ (3 < 3)) → (3<4) = ложь ∨ ложь → истина = ложь → истина = истина.

приклад 2.Вказати множину цілих значень X, для яких істинно вираз ¬((X > 2) → (X > 5)) .

Рішення.Операція заперечення застосована до всього виразу ((X > 2) → (X > 5)), отже, коли вираз ¬((X > 2) → (X > 5)) істинно, вираз ((X > 2) →(X > 5)) хибно. Тому необхідно визначити, для яких значень X вираз ((X > 2) → (X > 5)) є хибним. Операція імплікації приймає значення «брехня» лише у разі: коли з істини слід брехня. І це виконується лише X = 3; X = 4; X = 5.

Приклад 3.Для яких із наведених слів хибне висловлювання (перша буква голосна ∧ третя буква голосна) ⇔ рядок з 4 символів? 1) асса; 2) куку; 3) кукурудза; 4) помилка; 5) силач.

Рішення.Розглянемо послідовно всі запропоновані слова:

1) для слова асса отримаємо: ¬ (1 ∧ 0) ⇔ 1, 1 ⇔ 1 - висловлювання істинно;

2) для слова куку отримаємо: ¬ (0 ∧ 0) ⇔ 1, 1 ⇔ 1 - висловлювання істинно;

3) для слова кукурудза отримаємо: ¬ (0 ∧ 0) ⇔ 0, 1 ⇔ 0 - висловлювання хибне;

4) для слова помилка отримаємо: ¬ (1 ∧ 1) ⇔ 0, 0 ⇔ 0 - висловлювання істинно;

5) для слова силач отримаємо: ¬ (0 ∧ 0) ⇔ 1, 1 ⇔ 0 - висловлювання хибне.

Логічні висловлювання та їх перетворення

Під логічним виразомслід розуміти такий запис, який може набувати логічного значення «істина» або «брехня». При такому визначенні серед логічних виразів необхідно розрізняти:

• вирази, які використовують операції порівняння («більше», «менше», «рівно», «не дорівнює» тощо) і набувають логічних значень (наприклад, вираз а > b , де а = 5 і b = 7, дорівнює значенню «брехня»);
• безпосередні логічні висловлювання, пов'язані з логічними величинами та логічними операціями (наприклад, A ∨ В ∧ С, де А = істина, B = брехня та C = істина).

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

1. обчислення існуючих функціональних залежностей;
2. виконання алгебраїчних операцій (спочатку множення та розподіл, потім віднімання та додавання);
3. виконання операцій порівняння (у довільному порядку);
4. виконання логічних операцій (спочатку операції заперечення, потім операції логічного множення, логічного складання, останніми виконуються операції імплікації та еквівалентності).

У логічному вираженні можна використовувати дужки, які змінюють порядок виконання операцій.

приклад.Знайти значення виразу:

$1 ≤ a ∨ A ∨ sin(π/a - π/b)< 1 ∧ ¬B ∧ ¬(b^a + a^b >a + b ∨ A ∧ B)$ для а = 2, b = 3, A = істина, В = брехня.

Рішення.Порядок підрахунку значень:

1) b a + a b > a + b після підстановки отримаємо: 3 2 + 2 3 > 2 + 3, тобто 17 > 2 + 3 = істина;

2) A ∧ B = істина ∧ брехня = брехня.

Отже, вираз у дужках рівний (b a + a b > a + b ∨ A ∧ B) = істина ∨ брехня = істина;

3) 1 ≤ a = 1 ≤ 2 = істина;

4) sin(π/a - π/b)< 1 = sin(π/2 - π/3) < 1 = истина.

Після цих обчислень одержимо остаточно: істина ∨ А ∧ істина ∧ ¬В ∧ ¬істина.

Тепер мають бути виконані операції заперечення, потім логічного множення та додавання:

5) ¬В = ¬брехня = істина; ¬істина = брехня;

6) A ∧ істина ∧ істина ∧ брехня = істина ∧ істина ∧ істина ∧ брехня = брехня;

7) істина ∨ брехня = істина.

Таким чином, результат логічного вираження при заданих значеннях - "Істина".

Примітка.Враховуючи, що вихідний вираз є, зрештою, сума двох доданків, і значення одного з них 1 ≤ a = 1 ≤ 2 = істина, без подальших обчислень можна сказати, що результат для всього виразу також «істина».

Тотожні перетворення логічних виразів

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

Закон	Для ∨	Для ∧
Пересувний	A ∨ B = B ∨ A	A ∧ B = B ∧ A
Сполучний	A ∨ (B ∨ C) = (B ∨ A) ∨ C	A ∧ (B ∧ C) = (A ∧ B) ∧ C
Розподільний	A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C)	A ∨ B ∧ C = (A ∨ B) ∧ (A ∨ C)
Правила де Моргана	$(A ∨ B)↖(-)$ = $A↖(-) ∧ B↖(-)$	$(A ∧ B)↖(-)$ = $A↖(-) ∨ B↖(-)$
Ідемо потенції	A ∨ A = A	A ∧ A = A
Поглинання	A ∨ A ∧ B = A	A ∧ (A ∨ B) = A
Склеювання	(A ∧ B) ∨ (A↖(-) ∧ B) = B	(A ∨ B) ∧ (A↖(-) ∨ B) = B
Операція змінної із її інверсією	$A ∨ A↖(-)$ = 1	$A ∧ A↖(-)$ = 0
Операція із константами	A ∨ 0 = A A ∨ 1 = 1	A ∧ 1 = A A ∧ 0 = 0
Подвійного заперечення	$A↖(=)$ = A

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

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

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

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

1) X1 ∧ X2 ∨ X1 ∧ X2 ∪ ¬X1 ∧ X2 = X1 ∧ X2 ∨ ¬X1 ∧ X2 = (X1 ∨ ¬X1) ∧ X2 = 1 ∧ X2 = X2 .

Для перетворення тут можна застосувати закон демпотенції, розподільчий закон; операцію змінної з інверсією та операцію з константою.

2) X1 ∨ X1 ∧ X2 = X1 ∨ (1 ∨ 1 ∧ X2) = X1 ∨ (1 ∨ X2) = X1 .

Тут спрощення застосовується закон поглинання.

3) ¬(X1 ∧ X2) ∨ X2 = (¬X1 ∨ ¬X2) ∨ X2 = ¬X1 ∨ ¬X2 ∨ X2 = ¬X1 ∨ 1 = 1 .

При перетворенні застосовуються правило де Моргана, операція змінної з її інверсією, операція з константою

Приклади розв'язання задач

приклад 1.Знайти логічний вираз, рівносильний виразу A ∧ ¬(¬B ∨ C) .

Рішення.Застосовуємо правило де Моргана для В і С: ¬(¬B ∨ C) = B ∧ ¬C .

Отримуємо вираз, рівносильний вихідному: A ∧ ¬(¬B ∨ C) = A ∧ B ∧ ¬C .

Відповідь: A ∧ B ∧ ¬C.

приклад 2.Вказати значення логічних змінних А, В, С, для яких значення логічного виразу (A ∨ B) → (B ∨ C ∨ B) хибно.

Рішення.Операція імплікації помилкова тільки у випадку, коли з істинної посилки слід брехня. Отже, для заданого виразу посилка A ∨ B повинна набувати значення «істина», а наслідок, тобто вираз B ∨ C ∨ B , - «брехня».

1) A ∨ B - результат диз'юнкції - "істина", якщо хоча б один з операндів - "істина";

2) B ∨ ¬C ∨ B — вираз хибно, якщо всі доданки мають значення «брехня», тобто В — «брехня»; ¬C — «брехня», а отже, змінна має значення «істина»;

3) якщо розглянути посилку і врахувати, що В - "брехня", то отримаємо, що значення А - "істина".

Відповідь:А – істина, В – брехня, С – істина.

Приклад 3.Яке найбільше ціле число X, у якому істинно висловлювання (35

Рішення.Запишемо таблицю істинності для операції імплікації:

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

Вираз X< (X - 3) ложно при любых положительных значениях X. Следовательно, для того чтобы результатом импликации была «истина», необходимо и достаточно, чтобы выражение 35 < X · X также было ложно. Максимальное целое значение X, для которого 35 < X · X ложно, равно 5.

Відповідь: X = 5.

Використання логічних виразів для опису геометричних областей

Логічні вирази можна використовувати для описи геометричних областей. У цьому випадку завдання формулюється так: записати для заданої геометричної області такий логічний вираз, який набуває значення «істина» для значень x, y тоді і лише тоді, коли будь-яка точка з координатами (x; y) належить геометричній області.

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

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

1) .

Рішення.Задану геометричну область можна представити у вигляді набору наступних областей: перша область — D1 — напівплощина $(x)/(-1) +(y)/(1) ≤ 1$, друга — D2 — коло з центром на початку координат $x ^2 + y^2 ≤ 1$. Їх перетин D1 $∩$ D2 є шуканою областью.

Результат:логічний вираз $(x)/(-1)+(y)/(1) ≤ 1 ∧ x^2 + y^2 ≤ 1$.

2)

Цю область можна записати так: | ≤ 1 ∧ y ≤ 0 ∧ y ≥ -1.

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

Можна вирішити обернену задачу, а саме: намалювати область для заданого логічного вираження.

приклад 2.Намалювати та заштрихувати область, для точок якої виконується логічна умова y ≥ x ∧ y + x ≥ 0 ∧ y< 2 .

Рішення.Шукана область являє собою перетин трьох напівплощин. Будуємо на поверхні (x, y) прямі y = x; y = -x; y = 2. Це межі області, причому остання межа y = 2 не належить області, тому її наносимо пунктирною лінією. Для виконання нерівності y ≥ x потрібно, щоб точки знаходилися ліворуч від прямої y = x, а нерівність y = -x виконується для точок, що знаходяться праворуч від прямої y = -x. Умова y< 2 выполняется для точек, лежащих ниже прямой y = 2. В результате получим область, которая изображена на рис.:

Використання логічних функцій для опису електричних схем

Логічні функції дуже зручні описи роботи електричних схем. Так, для схеми, представленої на рис., де значення змінної X - це стан вимикача (якщо він включений, значення X - "істина", а якщо вимкнений - "брехня"), це значення Y - це стан лампочки (якщо вона горить - Значення «істина», а якщо ні - «брехня»), логічна функція запишеться так: Y = X . Функцію Y називають функцією провідності.

Для схеми, представленої на рис., логічна функція Y має вигляд: Y = X1 ∪ X2, тому що достатньо одного включеного вимикача, щоб горіла лампочка. У схемі на рис., щоб горіла лампочка, повинні бути включені обидва вимикачі, отже, функція провідності має вигляд: Y = X1 ∧ X2 .

Для більш складної схеми функція провідності матиме вигляд: Y = (X11 ∨ (X12 ∧ X13)) ∧ X2 ∧ (X31 ∨ X32).

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

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

Використання апарату алгебри логіки під час проектування логічних схем

Математичний апарат алгебри логіки дуже зручний опис того, як функціонують апаратні засоби комп'ютера. Будь-яка інформація при обробці на комп'ютері подається у двійковій формі, тобто кодується деякою послідовністю 0 і 1. Обробку двійкових сигналів, що відповідають 0 та 1, виконують у комп'ютері логічні елементи. Логічні елементи, що виконують основні логічні операції І, АБО, НЕ,представлені на рис.

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

Технічно комп'ютерний логічний елемент реалізується як електричної схеми, що є з'єднання різних деталей: діодів, транзисторів, резисторів, конденсаторів. На вхід логічного елемента, який називають також вентилем, надходять електричні сигнали високого та низького рівнів напруги, на вихід видається один вихідний сигнал або високого, або низького рівня. Ці рівні відповідають одному із станів двійкової системи: 1 - 0; ІСТИНА - БРЕХНЯ. Кожен логічний елемент має своє умовне позначення, яке виражає його логічну функцію, але не вказує на те, яка електронна схема в ньому реалізована. Це спрощує запис та розуміння складних логічних схем. Роботу логічних схем описують з допомогою таблиць істинності. Умовне позначення на схемі АБО знак «1» — від застарілого позначення диз'юнкції як «>=1» (значення диз'юнкції дорівнює 1, якщо сума двох операндів більша або дорівнює 1). Знак & на схемі І є скороченим записом англійського слова and.

З логічних елементів складаються електронні логічні схеми, що виконують складніші логічні операції. Набір логічних елементів, що складається з елементів НЕ, АБО, І, за допомогою яких можна побудувати логічну структуру будь-якої складності, називається функціонально повним.

Побудова таблиць істинності логічних виразів

Для логічної формули завжди можна записати таблицю істинності, тобто уявити задану логічну функцію в табличному вигляді. У цьому випадку таблиця повинна містити всі можливі комбінації аргументів функції (формули) та відповідні значення функції (результати формули на заданому наборі значень).

Зручною формою запису при знаходженні значень функції є таблиця, що містить, крім значень змінних та значень функції, також значення проміжних обчислень. Розглянемо приклад побудови таблиці істинності для формули $(X1)↖(-) ∧ X2 ∨ (X1 ∨ X2)↖(-) ∨ X1$.

X1	X2	$(X1)↖(-)$	$(X1)↖(-)$ \ X2	X1 ∧ X2	$(X1 ∨ X2)↖(-)$	$(X1)↖(-)$ ∧ X2 ∨ $(X1 ∨ X2)↖(-)$	$(X1)↖(-)$ ∧ X2 ∨ $(X1 ∨ X2)↖(-)$ ∨ X1
1	1	0	0	1	0	0	1
1	0	0	0	1	0	0	1
0	1	1	1	1	0	1	1
0	0	1	0	0	1	1	1

Якщо функція набуває значення 1 при всіх наборах змінних змін, вона є тотожно-істинної; якщо при всіх наборах вхідних значень функція набуває значення 0, вона є тотожно-хибний; якщо набір вихідних значень містить як 0, і 1, функція називається здійсненною. Наведений вище приклад є прикладом тотожно-істинної функції.

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

1. Диз'юнктивно нормальна форма (ДНФ)- Сума творів, утворених зі змінних та їх заперечень для хибних значень.

Алгоритм побудови ДНФ наступний:

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

приклад.Побудувати функцію, що визначає, що перше число дорівнює другому, використовуючи метод ДНФ. Таблиця істинності функції має вигляд

X1	X2	F(X1, X2)
1	1	1
0	1	0
1	0	0
0	0	1

Рішення.Вибираємо набори значень аргументів, у яких функція дорівнює 1. Це перший і четвертий рядки таблиці (рядок заголовка при нумерації не враховуємо).

Записуємо логічні твори аргументів цих наборів, об'єднавши їх логічною сумою: X1 ∧ X2 ∨ X1 ∧ X2 .

Записуємо заперечення щодо аргументів обраних наборів, що мають хибне значення (четвертий рядок таблиці; другий набір у формулі; перший і другий елементи): X1 ∧ X2 ∨ $(X1)↖(-)$ ∧ $(X2)↖(-)$.

Відповідь: F(X1, X2) = X1 ∧ X2 ∨ $(X1)↖(-)$ ∧ $(X2)↖(-)$.

2. Кон'юнктивно нормальна форма (КНФ)- Добуток сум, утворених зі змінних та їх заперечень для істинних значень.

Алгоритм побудови КНФ наступний:

1. у таблиці істинності вибирають набори аргументів, для яких логічні форми дорівнюють 0 («брехня»);
2. всі вибрані логічні набори як логічні суми аргументів записують послідовно, поєднавши їх між собою операцією логічного твору (кон'юнкції);
3. для аргументів, які є істинними, у побудованому записі проставляють операцію заперечення.

Приклади розв'язання задач

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

X1	X2	F(X1, X2)
1	1	1
0	1	0
1	0	0
0	0	1

Рішення.Вибираємо набори значень аргументів, у яких функція дорівнює 0. Це другий і третій рядки (рядок заголовка при нумерації не враховуємо).

Записуємо логічні суми аргументів цих наборів, об'єднавши їх логічним твором: X1 ∨ X2 ∧ X1 ∨ X2 .

Записуємо заперечення щодо аргументів вибраних наборів, що мають справжнє значення (другий рядок таблиці, перший набір формули, другий елемент; для третього рядка, а це другий набір формули, перший елемент): X1 ∨ $(X2)↖(-)$ ∧ $( X1)↖(-)$ ∨ X2.

Таким чином, отримано запис логічної функції у КНФ.

Відповідь: X1 ∨ $(X2)↖(-)$ ∧ $(X1)↖(-)$ ∨ X2.

Отримані двома методами значення функцій є еквівалентними. Для доказу цього твердження використовуємо правила логіки: F(X1, X2) = X1 ∨ $(X2)↖(-)$ ∧ $(X1)↖(-)$ ∨ X2 = X1 ∧ $(X1)↖(-)$ ∨ X1 ∧ X2 ∨ $(X2)↖(-)$ ∧ $(X1)↖(-)$ ∨ $(X2)↖(-)$ ∧ X2 = 0 ∨ X1 ∨ X2 ∨ $(X2)↖(- )$ ∧ $(X1)↖(-)$ ∨ 0 = X1 ∧ X2 ∨ $(X1)↖(-)$ ∧ $(X2)↖(-)$.

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

Шукана формула: X1 ∧ X2 ∨ $(X1)↖(-)$ ∧ X2 .

Її можна спростити: X1 ∧ X2 ∨ $(X1)↖(-)$ ∧ X2 = X2 ∧ (X1 ∨ $(X1)↖(-)$) = X2 ∧ 1 = X2.

Приклад 3.Для наведеної таблиці істинності збудувати логічну функцію, використовуючи метод ДНФ.

X1	X2	X3	F(X1, X2, X3)
1	1	1	1		X1 ∧ X2 ∧ X3
1	0	1	0
0	1	1	1		$(X1)↖(-)$ ∧ X2 ∧ X3
0	0	1	0
1	1	0	1		X1 ∧ X2 ∧ $(X3)↖(-)$
1	0	0	1		X1 ∧ $(X2)↖(-)$ ∧ $(X3)↖(-)$
0	1	0	0
0	0	0	0

Пошукова формула: X1 ∧ X2 ∧ X ∨ $(X1)↖(-)$ ∧ X2 ∧ X3 ∨ X1 ∧ X2 ∧ $(X3)↖(-)$ ∪ X1 ∧ $(X2)↖(-) (X3)↖(-)$.

Формула досить громіздка, і її слід спростити:

X1 ∧ X2 ∧ X3 ∨ $(X1)↖(-)$ ∧ X2 ∧ X3 ∨ X1 ∧ X2 ∧ $(X3)↖(-)$ ∨ X1 ∧ $(X2)↖(-)$ ∧ ↖(-)$ = X2 ∧ X3 ∧ (X1 ∨ $(X1)↖(-)$) ∨ X1 ∧ $(X3)↖(-)$ ∧ (X2 ∨ $(X2)↖(-)$) = X2 ∧ X3 ∨ X1 ∧ $(X3)↖(-)$.

Таблиці істинності для вирішення логічних завдань

Упорядкування таблиць істинності — одне із способів розв'язання логічних завдань. При використанні такого способу вирішення умови, які містить завдання, фіксуються за допомогою спеціально складених таблиць.

Приклади розв'язання задач

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

Рішення.Очевидно, що результатом рішення буде таблиця, в якій функція Y(X1, X2, X3) буде мати значення «істина», якщо які-небудь дві змінні мають значення «істина».

X1	X2	X3	Y(X1, X2, X3)
1	1	1	0
1	1	0	1
1	0	1	1
1	0	0	0
0	1	1	1
0	1	0	0
0	0	1	0
0	0	0	0

приклад 2.Скласти розклад уроків щодня, враховуючи, що урок інформатики може лише першим чи другим, урок математики — першим чи третім, а фізики — другим чи третім. Чи можливо скласти розклад, задовольнивши всі вимоги? Скільки існує варіантів розкладу?

Рішення.Завдання легко вирішується, якщо скласти відповідну таблицю:

	1-й урок	2-й урок	3-й урок
Інформатика	1	1	0
Математика	1	0	1
Фізика	0	1	1

З таблиці видно, що є два варіанти шуканого розкладу:

1. математика, інформатика, фізика;
2. інформатика, фізика, математика.

Приклад 3.До спортивного табору приїхали троє друзів — Петро, ​​Борис та Олексій. Кожен із них захоплюється двома видами спорту. Відомо, що таких видів спорту є шість: футбол, хокей, лижі, плавання, теніс, бадмінтон. Також відомо, що:

1. Борис - найстарший;
2. що грає у футбол молодше грає у хокей;
3. що грають у футбол і хокей і Петро живуть у одному домі;
4. коли між лижником та тенісистом виникає сварка, Борис мирить їх;
5. Петро не вміє грати ні теніс, ні бадмінтон.

Якими видами спорту захоплюється кожен із хлопчиків?

Рішення.Складемо таблицю і відобразимо в ній умови завдання, заповнивши відповідні клітини цифрами 0 і 1 залежно від того, чи хибно чи істинно відповідне висловлювання.

Оскільки видів спорту шість, виходить, що всі хлопчики захоплюються різними видами спорту.

З умови 4 випливає, що Борис не захоплюється ні лижами, ні тенісом, а з умов 3 та 5, що Петро не вміє грати у футбол, хокей, теніс та бадмінтон. Отже, улюблені види спорту Петра – лижі та плавання. Занесемо це в таблицю, а клітини стовпців «Лижі» і «Плавання», що залишилися, заповнимо нулями.

З таблиці видно, що у теніс може грати лише Олексій.

З умов 1 та 2 випливає, що Борис не футболіст. Таким чином у футбол грає Олексій. Продовжимо заповнювати таблицю. Внесемо до порожніх осередків рядки «Олексій» нулі.

Остаточно отримуємо, що Борис захоплюється хокеєм та бадмінтоном. Підсумкова таблиця виглядатиме так:

Відповідь:Петро захоплюється лижами та плаванням, Борис грає у хокей та бадмінтон, а Олексій займається футболом та тенісом.

Завдання 1 #10050

\((x \wedge y) \vee (x \wedge \overline y) \vee (y\wedge z) \vee (z \wedge x)\)

Складіть її таблицю істинності. Як відповідь введіть кількість наборів \((x,\) \(y,\) \(z),\) при яких функція дорівнює 1.

1. Спростимо \((x \wedge y) \vee (x \wedge \overline y).\)

За законом дистрибутивності \((y \wedge x) \vee (x \wedge \overline y)\) = \(x \wedge (y \vee \overline y).\)\(y \vee \overline y = 1\) (якщо \(y = 0,\) то \(\overline y \vee y = 1 \vee 0 = 1,\)якщо \(y = 1,\) то \(\overline y \vee y = 0 \vee 1 = 1).\)Тоді \(x \wedge (y \vee \overline y) = x \wedge 1 = x .\)

2. Спростимо \((y\wedge z) \vee (z \wedge x).\)За законом дистрибутивності \((y\wedge z) \vee (z \wedge x) = z \wedge (y \vee x).\)

3. Отримаємо: \((x \wedge y) \vee (x \wedge \overline y) \vee (y\wedge z) \vee (z \wedge x) = x \vee z \wedge (y \vee x).\)

4. У таблиці істинності міститься 8 рядків (рядок завжди \(2^n,\) де \(n\) - кількість змінних). У разі змінних 3.

5. Заповнимо таблицю істинності.

\[\begin(array)(|c|c|c|c|c|c|c|) \hline x & y & z & y \vee x & z \wedge (y \vee x) & F = x \vee z \wedge (y \vee x) \\ \hline 0 & 0 & 0 & 0 & 0 & 0 \\ \hline 0 & 0 & 1 & 0 & 0 & 0 \\ \hline 0 & 1 & 0 & 1 & 0 & 0 \\ \hline 0 & 1 & 1 & 1 & 1 & 1 \\ \hline 1 & 0 & 0 & 1 & 0 & 1 \\ \hline 1 & 0 & 1 & 1 & 1 & 1 \\ \hline 1 & 1 & 0 & 1 & 0 & 1 \\ \hline 1 & 1 & 1 & 1 & 1 & 1 \\ \hline \end(array)\]

Оскільки диз'юнкція \(x \vee z \wedge (y \vee x)\)істинна, якщо істинно хоча б одне з висловлювань, що входять до неї, то для \(x = 1\) \(F = 1\) при будь-яких \(y\) і \(z\) (рядки 5-8 у таблиці істинності ).

Розглянемо випадок, коли \(x = 0.\) Тоді значення функції буде залежати від значення \(z \wedge (y \vee x).\) Якщо \(z \wedge (y \vee x)\) істинна, то і \(F\) істинна, якщо помилкова, то \(F\) помилкова. Розглянемо випадок, коли \(F = 1.\) Кон'юнкція \((z \wedge (y \vee x))\) істинна, якщо всі висловлювання, що входять до неї, істинні, тобто \(y \vee x = 1\) і \(z = 1.\) \(x = 0,\) означає, \(y \vee x = 1,\) коли \(y = 1\) (рядок 4).

Якщо одне з висловлювань, які входять у кон'юнкцію, хибно, то вся кон'юнкція хибна. Якщо \(x = 0\) та \(y = 0,\) то \(y \vee x = 0.\) Тоді \(z \wedge (x \vee y) = 0\) за будь-якого \(z \) (Рядки 1-2). Оскільки \(x = 0,\) а друге висловлювання, що входить в диз'юнкцію \((z \wedge (x \vee y)),\) теж хибно, то і вся функція хибна. Якщо \(x = 0\) та \(y = 1,\) то \(y \vee x = 1.\) Якщо \(z = 0,\) \(z \wedge (y \vee x) = 0.\) Тоді \(F = 0\) (рядок 3). Випадок, коли \(z = 1,\) \(y = 1,\) \(x = 0,\) було розглянуто у попередньому абзаці.

Ми збудували таблицю істинності. Бачимо, що у ній є 5 наборів, у яких \(F = 1.\) Тому відповідь: 5.

Відповідь: 5

Завдання 2 #10051

Логічна функція \(F\) задається виразом:

\((x \wedge \overline y \wedge z) \vee (x \rightarrow y)\)

Складіть її таблицю істинності. Як відповідь введіть кількість наборів \((x,\) \(y,\) \(z),\) при яких функція дорівнює 0.

\[\begin(array)(|c|c|c|c|c|c|c|c|c|) \hline x & y & z \overline y & x\wedge \overline y & x \wedge \overline y \wedge z & \overline x \\overline x \vee y&x \wedge \overline y \wedge z \vee \overline x \vee y \\ \hline 0 & 0 & 0 & 1 & 0 & 0 &1&1&1\\\hline 0&0&1&1&1&0&0&1&1&1\\\hline 0&1&0&0&0&0&0&1&1&1\\ \hline 0&1&1&0&0&0&0&1&1&1\\\hline 1&0&0&1&1&0&0&0&0&\\hline 1&0&1& 1&1&1&0&0&0&1\\hline 1&1&0&0&0&0&0&0&1&1\\\hline 1&1&1&0&0&0&0&0& 1 & 1\\hline \end(array)\]

1. \(x \rightarrow y\) = \(\overline x \vee y.\)

2. Зауважимо, що з \(y = 1\) \(F = 1,\) оскільки диз'юнкція істинна, якщо істинно хоча б одне вираз, що входить у неї (рядки 3-4, 7-8 у таблиці істинності). Аналогічно при \(\overline x = 1,\) тобто при \(x = 0,\) \(F = 1\) (рядки 1-4).

3. При \(x = 1\) та \(y = 0\) \(\overline x \vee y = 0,\) \(x \wedge \overline y = 1.\) При \(z = 1 \) \(x \wedge \overline y \wedge z = 1\)і \(F = 1,\) тому що істинно одне з виразів (рядок 6), а при \(z = 0\) \(x \wedge \overline y \wedge z = 0\)і \(F = 0,\) так як обидва вирази, що входять до диз'юнкції, помилкові (рядок 5).

За побудованою таблиці істинності бачимо, що для одного набору \((x,\) \(y,\) \(z)\) \(F = 0.\)

Відповідь: 1

Завдання 3 #10052

Логічна функція \(F\) задається виразом:

\((\overline(z \vee \overline y)) \vee (w \wedge (z \equiv y)) \)

Складіть її таблицю істинності. Як відповідь введіть суму значень \(z,\) \(y\) та \(w,\) при яких \(F = 1.\)

\[\begin(array)(|c|c|c|c|c|c|c|c|c|) \hline w&y&z&overline y&z z \vee \overline y) \ z \equiv y & w \wedge (z \equiv y) & \overline z \vee \overline y \vee w \wedge (z \equiv y) \\ \hline 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ \hline 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ \hline 0 & 1 & 0 & 0 & 0 & 1 & 0&0&1\\\hline 0&1&1&0&1&0&1&0&0\\\hline 1&0&0&1&1&0&1&1&1\\\ hline 1&0&1&1&1&0&0&0&0&0\\hline 1&1&0&0&0&1&0&0&0&1\\\hline 1&1&1&0 & 1 & 0 & 1 & 1 & 1 \\ \hline \end(array)\]

1. \((\overline(z \vee \overline y)) = \overline z \wedge y \)

2. У таблиці істинності буде \(2^3 = 8\) рядків.

3. Якщо \(z = 1 \) і \(y = 1,\) \(то (z \equiv y) = 1 \) (оскільки еквівалентність істинна тоді і тільки тоді, коли обидва висловлювання одночасно помилкові або істинні) . \(\overline z \wedge y = 0\) \((0 \wedge 1 = 0).\) Якщо \(w = 1,\) \(w \wedge (z \equiv y) = 1\) \ ((1 \ wedge 1 = 1) \) і \ (F = 1, \) так як диз'юнкція істинна, якщо істинно хоча б одне з висловлювань, що входять до неї (рядок 8 в таблиці істинності). Якщо \(w = 0,\) \(w \wedge (z \equiv y) = 0\) \((0 \wedge 1 = 0)\) і \(F = 0,\) так як обидва висловлювання, входять у диз'юнкцію, хибні (рядок 4).

4. Аналогічно для \(z = 0, y = 0.\) \((z \equiv y) = 1,\) \(\overline z \wedge y = 0\) \((1 \wedge 0 = 0) ).\) Тоді знову значення функції залежатиме від \(w.\) При \(w = 1\) \(w \wedge (z \equiv y) = 1,\)\(F = 1,\) оскільки одне з висловлювань, що входять до диз'юнкції, істинно (рядок 5), а при \(w = 0\) \(w \wedge (z \equiv y) = 0,\)\(F = 0,\) оскільки всі висловлювання помилкові (рядок 1).

5. Якщо \(z = 0\) і \(y = 1,\) то \(\overline z \wedge y = 1\) \((1 \wedge 1 = 1).\) Оскільки \(( z \equiv y) = 0\) (адже значення \(z\) і \(y\) різні), буде помилкова за будь-якого \(w.\) Тоді, оскільки значення змінної \(w\) не буде впливати на значення функції, при \(z = 0\) і \(y = 1\) \(w\) може бути як 0, так і 1. \(F = 1,\) оскільки одне з висловлювань, що входять до диз'юнкцію, істинно (рядки 3, 7).

6. Якщо \(z = 1\) та \(y = 0,\) то \(\overline z \wedge y = 0 \wedge 0 = 0.\)Оскільки \((z \equiv y) = 0,\) \(w \wedge (z \equiv y) = w \wedge 0\)буде хибна за будь-якого \(w\) (тобто \(w\) може бути і 0 і 1). Значить, при \(z = 1\) і \(y = 0\) \(F\) завжди буде хибна (оскільки обидва висловлювання, що входять до диз'юнкції, хибні, рядки 2, 5).

7. \(F = 1\) при наступних наборах \(z,\) \(y,\) \(w:\) (0, 0, 1), (0, 1, 1), (1, 1 , 1), (0, 1, 0). Якщо підсумувати значення, отримаємо 7.

Відповідь: 7

Завдання 4 #10053

Логічна функція \(F\) задається виразом:

\(a \wedge ((\overline(b \wedge c)) \vee (a \wedge \overline b) \vee (\overline c \wedge a)) \)

Складіть її таблицю істинності. Як відповідь введіть суму значень \(a,\) \(b\) та \(c,\) при яких \(F = 1.\)

\[\begin(array)(|c|c|c|c|) \hline a & b&c&F\\hline 0&0&0&0 \\ \hline 0&0&1&0\ \ \ hline 0 & 1 & 0 & 0 \ \ \ hline 0 & 1 & 1 & 0 \ \ \ hline 1 & 0 & 0 & 1 \\ \ hline 1 & 0 & 1 & 1 \\ \ hline 1 & 1 & 0 & 1 \\ \hline 1 & 1 & 1 & 0 \\ \hline \end(array)\]

1. У таблиці істинності \(2^3 = 8\) рядків.

2. При \(a = 0\) \(F = 0\) при будь-яких значеннях \(b\) і \(c,\) тому що кон'юнкція істинна тоді і тільки тоді, коли всі висловлювання, що входять до неї, істинні (Рядки 1-4 в таблиці істинності).

3. Розглянемо випадки, коли \(a = 1.\) Якщо \(\overline ((b \wedge c)) \vee (a \wedge \overline b) \vee (\overline c \wedge a) = 1,\)то \(F = 1\) (оскільки обидва висловлювання будуть істинними), інакше \(F = 0\) (оскільки одне висловлювання буде хибним). За законом де Моргана \(\overline(b \wedge c) = \overline b \vee \overline c.\)Тоді з огляду на те, що \(a = 1,\) \(\overline ((b \wedge c)) \vee (a \wedge \overline b) \vee (\overline c \wedge a) = \overline b \vee \overline c \vee \overline b \vee \overline c = \overline b \vee \overline c.\)

4. Якщо \(\overline b = 0\) та \(\overline c = 0\) (одночасно, тобто при \(b = 1\) та \(c = 1),\) то \(\overline b \vee \overline c = 0\)і (F = 0) (рядок 8). В інших випадках \(\overline b \vee \overline c = 1\)і (F = 1) (рядки 5-7).

5. Набори \((x,\) \(y,\) \(z),\) при яких \(F = 1:\) (1, 0, 0), (1, 1, 0), ( 1, 0, 1). Сума значень дорівнює 5.

Відповідь: 5

Завдання 5 #10054

Логічна функція \(F\) задається виразом:

\(((a \wedge b) \vee (b \wedge c)) \equiv ((d \rightarrow a) \vee (b \wedge \overline c)) \)

Складіть таблицю істинності. Як відповідь введіть суму значень \(a,\) при яких \(F = 0.\)

\[\begin(array)(|c|c|c|c|c|) \hline a & b&c&d&F\\hline 0&0&0&0&0&0 \\\hline 0& 0 & 0 & 1 & 1 \\ \hline 0 & 0 & 1 & 1 & 1 \\ \hline 0 & 1 & 1 & 1 & 0 \\ \hline 1 & 0 & 0 & 0 & 0 \\ \hline 1 & 1 & 0 & 0 & 1 \\ \hline 1 & 1 & 1 & 0 & 1 \\ \hline 1 & 1 & 1 & 1 & 1 \\ \hline 0 & 1 & 0 & 0 & 0 \\ \hline 0 & 0 & 1 & 0 & 0 \\ \hline 1 & 1 & 0 & 1 & 1 \\ \hline 1 & 0 & 1 & 0 & 0 \\ \hline 1 & 0 & 0 & 1 & 0 \\ \hline 0 & 1 & 1 & 0 & 1 \\ \hline 1 & 0 & 1 & 1 & 0 \\ \hline 0 & 1 & 0 & 1 & 0 \\ \hline \end(array)\]

1. За законом дистрибутивності \((a \wedge b) \vee (b \wedge c) = b \wedge (a \vee c).\)

2. \(d \rightarrow a = \overline d \vee a.\)

3. \(((a \wedge b) \vee (b \wedge c)) \equiv ((d \rightarrow a) \vee (b \wedge \overline c)) = b \wedge (a \vee c) \equiv (\overline d \vee a \vee (b \wedge \overline c)) .\)

4. Якщо \(b = 0,\) то ліва частина функції дорівнює 0 \((0 \wedge (a \vee c) = 0).\) \(b \wedge \overline c = 0 \wedge \overline c = 0.\)Отже, для \(b = 0\) \(c\) може бути будь-яким, тому що не впливає на значення функції. \(F = 1,\) якщо \(\overline d \vee a = 0\) (тоді один із виразів, що входять до диз'юнкції, буде істинним). Це виконується при \(\overline d = 0\) \((d = 1)\) та \(a = 0\) (рядки 2, 3). За інших \(d\) і \(a\) \(\overline d \vee a = 0,\) означає, \(F = 0,\) тому що операція еквівалентності істинна тоді і тільки тоді, коли обидва висловлювання одночасно істинні чи хибні (рядки 1, 10 у таблиці істинності).

5. Якщо \(b = 1,\) то \(b \wedge (a \vee c) = 1 \wedge (a \vee c) = a \vee c.\) \(b \wedge \overline c = 1 \wedge \overline c = \overline c.\)Тоді маємо, що \(a \vee c \equiv \overline d \vee a \vee \overline c.\)Якщо \(a = 1,\) то \(a \vee c = 1 \) та \(\overline d \vee a \vee \overline c = 1,\)тому що диз'юнкція істинна, якщо хоча б одне з виразів істинно (а в обох диз'юнкціях є \(a = 1). \) Тоді, якщо \(b = 1\) та \(a = 1,\) \(F = 1\) при будь-яких (c) і (d) (рядки 5, 7, 8, 11).

Якщо \(a = 0,\) то \(a \vee c = 0 \vee c = c,\) а \(\overline d \vee a \vee \overline c = \overline d \vee \overline c.\)Маємо: \(c \equiv (\overline d \vee \overline c).\)При \(c = 1\) \(1 \equiv \overline d.\) При \(d = 1\) \(F = 0,\) оскільки висловлювання різні (рядок 4), при \(d = 0 \) \ (F = 1, \) так як обидва висловлювання істинні (рядок 14). При \(c = 0\) \(0 \equiv (\overline d \vee 1).\)Оскільки \(\overline d \vee 1\) - диз'юнкція, в якій одне з висловлювань істинне, то і вся диз'юнкція істинна. Тоді \(0 \equiv 1,\) що невірно, значить, \(F = 0\) за будь-яких \(d\) (рядок 9, 16).

По побудованій таблиці бачимо, що (F = 0) при (a = 0) (рядки 1, 4, 9, 10, 16) і при (a = 1) (рядки 6, 12, 13, 15). Тоді сума значень дорівнює 0*5+1*4=4.

Відповідь: 4

Завдання 6 #10055

Логічна функція \(F\) задається виразом:

\((a \equiv (b \vee \overline c)) \rightarrow (c \wedge (b \vee a)) \)

Складіть таблицю істинності. Як відповідь введіть суму значень \(c,\) при яких \(F = 1.\)

\[\begin(array)(|c|c|c|c|) \hline a&b&c&F\\hline 0&0&0&1 \\ \hline 0&0&1&0\ \\hline 0 & 1 & 1 & 1 \\ \hline 0 & 1 & 0 & 1 \\ \hline 1 & 0 & 0 & 0 \\ \hline 1 & 1 & 0 & 0 \\ \hline 1 & 1 & 1 & 1 \\ \hline 1 & 0 & 1 & 1 \\ \hline \end(array)\]

У таблиці (2 ^ 3 = 8) рядків.

1. Імплікація хибна тоді і лише тоді, коли з істинного висловлювання випливає хибне. Значить, \(F = 0,\) якщо a \(c \wedge (b \vee a) = 0.\) В інших випадках \(F = 1.\) Розглянемо, за яких значень \(a,\) \(b\) та \(c\) \(a \equiv (b \vee \overline c) = 1\)(якщо \(a \equiv (b \vee \overline c) = 0,\)то \(F = 1\) за будь-якого значення \(c \wedge (b \vee a) = 0).\)

Якщо \(a = 0,\) то щоб виконуватися \(a \equiv (b \vee \overline c) = 1,\)необхідно \(b \vee \overline c = 0\) (адже операція еквівалентності істинна тоді і тільки тоді, коли обидва висловлювання істинні або обидва помилкові). Щоб диз'юнкція \((b \vee \overline c)\) була помилкова, обидва висловлювання, що входять до неї, повинні бути помилковими, тобто \(b = 0\) і \(\overline c = 0\) \(( c = 1).\) За таких значень \(c \wedge (b \vee a) = 1 \wedge (0 \vee 0) = 0.\)Тоді \((a \equiv (b \vee \overline c)) \rightarrow (c \wedge (b \vee a)) = 1 \rightarrow 0 = 0,\)\(F = 0.\) Це відповідає рядку 2 з таблиці істинності.

Якщо \(a = 1,\) то щоб виконувалося \(a \equiv (b \vee \overline c) = 1,\)\(b \vee \overline c = 1.\) Це виконується у кількох випадках. Якщо \(b = 1,\) то \(c\) може дорівнювати і нулю і одиниці, адже одне з висловлювань, що входять до диз'юнкції, вже істинно. При \(c = 1\) \(c \wedge (b \vee a) = 1 \wedge 1 = 1,\)тоді \(F = 1\) (бо \(1 \rightarrow 1 = 1,\) рядок 7). При \(c = 0\) \(c \wedge (b \vee a) = 0 \wedge 1 = 0,\)отже, \(F = 0\) \((1 \rightarrow 0 = 0,\) рядок 6). Якщо \(b = 0,\) то \(\overline c = 1\) \((c = 0,\) тоді одне з висловлювань, що входять до диз'юнкції, буде істинним). В такому випадку \(c \wedge (b \vee a) = 0 \wedge (0 \vee 1) = 0.\)\(F = 0,\) так як \(1 \rightarrow 0 = 0\) (рядок 5).

2. При інших значеннях \(a,\) \(b\) та \(c\) \(F = 1,\) тому що \(a \equiv (b \vee \overline c) = 0\)(Рядки 1, 3, 7, 8).

3. Зі складеної таблиці істинності бачимо, що (F = 1) при (c = 0) (рядки 1, 4) і при (c = 1) (рядки 3, 7, 8). Сума значень дорівнює 0 * 2 + 1 * 3 = 3. \ (2 ^ 4 = 16 \) рядків.

1. Оскільки кон'юнкція хибна, якщо хибно хоча б одне з висловлювань, то при \(d = 0\) \(F = 0\) за будь-яких \(a,\) \(b\) і \(c\) (Рядки 1, 6-10, 12, 14 в таблиці істинності).

2. Розглянемо випадок, коли \(d = 1.) Тоді \((a \rightarrow b) \wedge (b \equiv c) \wedge d = (a \rightarrow b) \wedge (b \equiv c) \wedge 1 = (a \rightarrow b) \wedge (b \equiv c).При (b = 1 \) \(a \rightarrow b = a \rightarrow 1 = 1\)за будь-якого \(a,\) тому що імплікація хибна тоді і тільки тоді, коли з істинного висловлювання випливає хибне. Якщо \(c = 1,\) то \(b \equiv c = 1,\) так як операція еквівалентності істинна, коли обидва вирази істинні або обидва помилкові, і \(F = 1\) (оскільки всі вирази, що входять в кон'юнкцію, істинні). Це відповідає рядкам 4 і 5. Якщо \(c = 0,\) то \(b \equiv c = 0,\) \(F = 0,\) оскільки один з виразів, що входить до кон'юнкції, є хибним (рядки 11 та 16).

При \(b = 0:\) якщо \(a = 1,\) то \(a \rightarrow b = 1 \rightarrow 0 = 0,\)тоді один з виразів, що входять до кон'юнкції, хибно, і (F = 0) при будь-якому (рядки 13 і 15). Якщо \(a = 0,\) то \(a \rightarrow b = 0 \rightarrow 0 = 1.\)Якщо \(c = 0,\) то \(b \equiv c = 0 \equiv 0 = 1,\)\(F = 1,\) так як обидва вирази, що входять до кон'юнкції, істинні (рядок 2). Якщо \(c = 1,\) то \(b \equiv c = 0 \equiv 1 = 0,\)\(F = 0,\) так як один з виразів, що входять до кон'юнкції, хибно (рядок 3).

Таким чином, (F = 1) при (d = 1) (рядки 2, 4, 5). Сума значень \(d\) дорівнює 1 * 3 = 3.

Побудова таблиць істинності складних висловлювань.

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

1) інверсія 2) кон'юнкція 3) диз'юнкція 4) імплікація та еквівалентність

Як скласти таблицю істинності?

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

Для формули, яка містить дві змінні, таких наборів значень змінних всього чотири:

(0, 0), (0, 1), (1, 0), (1, 1).

Якщо формула містить три змінні, то можливих наборів значень змінних вісім (0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0) ), (1, 0, 1), (1, 1, 0), (1, 1, 1).

Кількість наборів для формули із чотирма змінними дорівнює шістнадцяти тощо.

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

приклади.

1. Складемо таблицю істинності для формули 96%.

З таблиці видно, що при всіх наборах значень змінних x та y формула набуває значення 1, тобто є тотожно істинною.

2. Таблиця істинності для формули 96%"

З таблиці видно, що при всіх наборах значень змінних x та y формула набуває значення 0, тобто є тотожно хибний .

3. Таблиця істинності для формули 96%"

З таблиці видно, що формула 0 "border-collapse:collapse;border:none">

Висновок: отримали в останньому стовпчику всі одиниці. Отже, значення складного висловлювання істинно за будь-яких значеннях простих висловлювань До і З. Отже, вчитель міркував логічно правильно.