Рішення таблиць істинності логічних виразів. Правила введення логічної функції

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

Глосарій, визначення логіки

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

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

Логічне вираження- усне затвердження чи запис, куди, поруч із постійними величинами, обов'язково входять змінні величини (об'єкти). Залежно від значень цих змінних величин (об'єктів) логічний вираз може набувати одного з двох можливих значень: істина (логічна 1) або брехня (логічний 0).

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

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

1) Логічне множення чи кон'юнкція:

Кон'юнкція - це складне логічне вираз, яке вважається істинним у тому й лише тому випадку, коли обидва простих вирази є істинними, у всіх інших випадках цей складний вираз хибно.
Позначення: F = A&B.

Таблиця істинності для кон'юнкції

3) Логічне заперечення чи інверсія:

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

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

5) Логічна рівнозначність чи еквівалентність:

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

Таблиця істинності для еквівалентності

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

1. Інверсія;
2. Кон'юнкція;
3. диз'юнкція;
4. Імплікація;
5. Еквівалентність.

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

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

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

Алгебраїчні перетворення логічних виразів

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

Заперечення

Заперечення та інверсія- Найпростіше логічне перетворення. Йому відповідає частка "не." Це перетворення просто змінює твердження протилежне. Відповідно значення твердження теж змінюється на протилежне. Якщо твердження А істинне, то "не А" - хибно. Наприклад, твердження "прямий кут - це кут, що дорівнює дев'яносто градусів" - істина. Тоді його заперечення "прямий кут не дорівнює дев'яноста градусам" - брехня.

Таблиця істинності для запереченнябуде така:

Диз'юнкція

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

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

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

Таблиця значень виключає або

Імплікація та еквівалентність

Імплікація є слідствоі граматично може бути виражена як "з А слідує Б". Тут твердження А називатиметься передумовою, а Б - наслідком. Імплікація може бути хибною, тільки в одному випадку: якщо передумова істинна, а слідство хибне. Тобто брехня не може випливати з істини. У решті випадків імплікація істинна. Варіанти, коли обидва твердження мають однакову істинність, питань не викликають. Але чому правильне слідство з помилкової причини - істина? Справа в тому, що з помилкової причини може випливати будь-що. І це відрізняє імплікацію від еквівалентності.

У математиці (та інших доказових дисциплінах) імплікація використовується для вказівки необхідної умови. Наприклад, твердження А - "точка О - екстремум безперервної функції", твердження Б - "похідна безперервної функції в точці Про звертається в нуль". Якщо О, точка екстремуму безперервної функції, то похідна в цій точці буде, і справді, дорівнює нулю. Якщо ж не є точкою екстремуму, то похідна в цій точці може бути нульовою, а може не бути. Тобто Б необхідно для А, але не достатньо.

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

Логічна операція еквівалентність, по суті, є взаємною імплікацією. "А еквівалентно Б" означає, що "з А випливає Б" і "з Б випливає А" одночасно. Еквівалентність вірна, коли обидва твердження або одночасно вірні, або одночасно невірні.

В математиці еквівалентність використовується для визначення необхідної та достатньої умови. Наприклад, твердження А - "Точка є точкою екстремуму безперервної функції", твердження Б - "У точці Про похідна функції звертається в нуль і змінює знак". Ці два твердження еквівалентні. Б містить необхідну та достатню умову для А. Зверніть увагу, що в даному прикладітверджень Б насправді є кон'юнкцією двох інших: "похідна в точці Про звертається в нуль" та "похідна в точці Про змінює знак".

Інші логічні функції

Вище були розглянуті основні логічні операції, які часто використовуються. Є й інші функції, що використовуються:

• Штрих Шеффера або несумісність є запереченням кон'юнкції А і Б
• Стрілка Пірса представляє збій заперечення диз'юнкції.

Побудова таблиць істинності

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

1. Розбити вираз на прості твердження та позначити кожне з них як змінну.
2. Визначити логічні перетворення.
3. Виявити порядок дій цих перетворень.
4. Порахувати рядки у майбутній таблиці. Їх кількість дорівнює два ступеня N, де N - число змінних, плюс один рядок для шапки таблиці.
5. Визначити кількість стовпців. Воно дорівнює сумі кількості змінних та кількості дій. Можна представляти результат кожної дії у вигляді нової змінної, якщо так буде зрозуміліше.
6. Шапка заповнюється послідовно, спочатку всі змінні, потім результати дій у порядку виконання.
7. Заповнення таблиці треба розпочати з першої змінної. Для неї кількість рядків ділиться навпіл. Одна половина заповнюється нулями, друга – одиницями.
8. Для кожної наступної змінної нулі та одиниці чергуються вдвічі частіше.
9. Таким чином заповнюються всі стовпці зі змінними та для останньої змінної значення змінюється у кожному рядку.
10. Потім послідовно заповнюються результати всіх процесів.

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

Окремо слід сказати про порядок логічних дій. Як його визначити? Тут, як і в алгебрі, є правила, що задають послідовність дій. Вони виконуються у такому порядку:

1. вирази у дужках;
2. заперечення чи інверсія;
3. кон'юнкція;
4. строга та звичайна диз'юнкція;
5. імплікація;
6. еквівалентність.

Приклади

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

• Штрих Шеффера.
• Стрілка Пірса.
• Визначення еквівалентності.

Штрих Шеффера

Штрих Шеффера - це логічний вираз, який можна записати у вигляді "не (А та Б)". Тут дві змінні, і дві дії. Кон'юнкція у дужках, отже, вона виконується першою. У таблиці буде шапка та чотири рядки зі значеннями змінних, а також чотири стовпці. Заповнимо таблицю:

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

Стрілка Пірса

Розглядаючи Стрілку Пірса, яка є заперечення диз'юнкції "не (А або Б)", порівняємо її з кон'юнкцією заперечень "не А і не Б". Заповнимо дві таблиці:

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

Визначення еквівалентності

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

Тут дві змінні та п'ять дій. Будуємо таблицю:

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

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

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

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

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

• словесне опис – це форма, що використовується початковому етапі проектування має умовне уявлення.
• опис функції алгебри логіки як таблиці істинності.
• опис функції алгебри логіки у вигляді виразу алгебри: використовується дві алгебраїчні форми ФАЛ:
  а) ДНФ – диз'юнктивна нормальна форма- Це логічна сума елементарних логічних творів. ДНФ виходить із таблиці істинності за наступним алгоритмом або правилом:
  1) у таблиці вибираються ті рядки змінних для яких функція на виході =1.
  2) для кожного рядка змінних записується логічний твір; причому змінні =0 записуються з інверсією.
  3) отриманий твір логічно підсумовується.
  Fднф = X 1 * Х 2 * Х 3 ∨ Х 1 x 2 Х 3 ∨ Х 1 Х 2 x 3 ∨ Х 1 Х 2 Х 3
  ДНФ називається досконалою, якщо перемінні мають однаковий ранг чи порядок, тобто. до кожного твіру обов'язково повинні включатися всі змінні у прямому або інверсному вигляді.
  б) КНФ – кон'юнктивна нормальна форма– це логічний добуток елементарних логічних сум.
  КНФ може бути отримана з таблиці істинності за таким алгоритмом:
  1) вибираємо набори змінних для яких функція на виході = 0
  2) для кожного набору змінних записуємо елементарну логічну суму, причому змінні = 1 записуються з інверсією.
  3) логічно перемножуються одержані суми.
  Fскнф=(X 1 V X 2 V X 3) ∧ (X 1 V X 2 V X 3) ∧ (X 1 V X 2 V X 3) ∧ (X 1 V X 2 V X 3)
  КНФ називається досконалоюякщо всі змінні мають однаковий ранг.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Алгебра логіки(англ. 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- з'єднання) - логічне множення, операція, що вимагає як мінімум двох логічних величин (операндів) і що з'єднує два або більше висловлювань за допомогою зв'язки «і»(наприклад, «А та В»), яка символічно позначається за допомогою знака ∧ (А ∧ В) та читається: «А та В». Для позначення кон'юнкції застосовуються такі знаки: А ∙ В; А & В, А and В, інколи ж між висловлюваннями не ставиться ніякого знака: АВ. Приклад логічного множення: Цей трикутник рівнобедрений і прямокутний. Даний вислів може бути істинним тільки в тому випадку, якщо виконуються обидві умови, інакше висловлювання є хибним.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 = істина, без подальших обчислень можна сказати, що результат для всього виразу теж «істина».

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

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

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

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

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

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

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

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

Вираз 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$.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

приклад 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 ∧ 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) буде мати значення «істина», якщо які-небудь дві змінні мають значення «істина».

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вибираємо рядки, де
і виписуємо кон'юнкції всіх змінних, причому, якщо змінна в цьому наборі дорівнює 1, то записуємо її саму, а якщо змінна = 0, то її заперечення.

Для цього прикладу

кон'юнкція цих диз'юнкцій і буде шуканою формулою:

Визначення: Кон'юнкція називається елементарноюякщо всі змінні, що входять до неї, різні. Кількість літер, що входять до елементарної кон'юнкції або елементарної диз'юнкції, називається рангом.

Число 1 вважається елементарною кон'юнкцією рангу 0. Змінна вважається елементарною кон'юнкцією або елементарною диз'юнкцією рангу 1. Число 0 вважається елементарною диз'юнкцією рангу 0. , також можна привести до елементарного вигляду. Для цього треба застосувати властивості комутативності, ідемпотентності та асоціативності кон'юнкції та диз'юнкції.

Строго доведено, що будь-яку формулу булевої алгебри можна висловити за допомогою операцій , &,. Інтуїтивно цей факт очевидний, згадаємо алгоритм складання формули за таблицею істинності. При цьому ми використовуємо лише ці операції. Така форма запису називається диз'юнктивною нормальною формою(ДНФ). Це своєрідний механізм нормалізації алгебри формул логіки.

Визначення: ДНФ– це диз'юнкція різних елементарних кон'юнкцій (тобто кожна кон'юнкція складається з елементарних висловлювань чи його заперечень).

Аналогічно визначається КНФ - нормальна кон'юктивна форма.

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

Теорема. Для будь-якої функції, яка не є тотожно хибною, існує і єдина СДНФ.

Слідство . Будь-яку булеву функцію, яка не є тотожно помилковою, можна представити у вигляді суперпозиції&,,, причому заперечення відноситься лише до змінних.

Визначення: p align="justify"> Система логічних операцій називається функціонально повною, якщо за допомогою цих операцій і констант цієї системи можна представити будь-яку функцію булевої алгебри.

Системи (&,,); (,); (&,),(/) – є функціонально повними

(&,) – функціонально неповна.

Ми приймемо ці факти без доказу, і вирішуючи завдання, намагатимемося будь-яку формулу подати за допомогою (&,,). Пізніше ми докладніше обговоримо питання функціональної повноти та неповноти системи операцій.

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

Розглянемо приклад розв'язання логічного завдання.

приклад :

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

Якщо поїде Арбузов, то маємо їхати Брюквін чи Вишневський

Якщо поїдуть Арбузов і Вишневський, то поїде Брюквін.

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

Введемо змінні та відповідні їм елементарні висловлювання.

- поїде Арбузов

- поїде Брюквін

- поїде Вишневський

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

Складемо загальну формулу та спростимо вираз

тобто. якщо поїде Арбузов, то поїде Брюквін.

Приклад:

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

- гарна погода

– ми підемо на пляж

– ми поїдемо до лісу

Тепер побудуємо заперечення цієї фрази

т.ч. отримаємо вислів "Завтра буде хороша погода, і ми не підемо в ліс та на пляж.

Бажаючі можуть побудувати таблицю істинності та перевірити це твердження.

приклад :

За підозрою у скоєному злочині затримано Брауна, Джона та Сміта. Один із них шанований у місті старий, другий чиновник, а третій відомий шахрай. У ході слідства старий говорив правду, шахрай брехав, а третій затриманий в одному випадку говорив правду, а в іншому брехав.

Ось що вони казали:

Браун: Я зробив це. Джон не винний. (Б&Д)

Джон: Браун не винний. Злочинець Сміт. (Б&С)

Сміт: Я не винний. Винен Браун (С&Б)

Опишемо ці висловлювання формально:

- Злочин скоїв Браун

- Злочин скоїв Джон

- Злочин скоїв Сміт

Тоді їхні слова описуються такими виразами:

Браун:

Джон:

Сміт:

Т.к. за умовами задачі дві з цих помилкові і одна істинна, то

Складемо таблицю істинності

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

отже - Помилково і - істинно

= 1 – Джон шановний старий

Залишається, що Браун чиновник, і оскільки - Помилково, то - Істинно.

Користуючись законами та тотожностями булевої алгебри можна спрощувати логічні вирази.

приклад :

Вправа: