а) Альтернативна диз'юнкція, так як передбачається одна умова з двох, але не обидва разом.
б) Диз'юнкція (хоча, якщо мовець «чесний», то можлива альтернативна диз'юнкція).
в) Альтернативна диз'юнкція.
Тотожне істинні висловлювання і формули:
а) Якщо Земля зіткнеться з Сонцем, то піде дощ;
а) Тотожно-істинно, так як посилка - помилкова, а з брехні слід все що завгодно.
б) Імплікація помилкова в єдиному випадку, коли з істини слід брехня. Якщо істинно, то P і Q приймають однакові істинності значення. Значить, імплікація істинна і зовнішня імплікація - теж. Якщо помилково, то зовнішня імплікація завжди істинна. Отже, вся формула - тотожно-істинною.
По-іншому дослідження можна провести, побудувавши таблицю істинності для нашої формули. Побудуємо скорочену таблицю істинності (т. Е. Для кожної змінної будемо відводити тільки по одному стовпцю, в місці її першого входження в формулу; для кожної логічної зв'язки - теж по одному стовпцю, використовуючи при цьому запис самої формули):
Тут наведена скорочена таблиця істинності формули: спочатку заповнюються стовпці можливих значень P і Q. таких наборів буде; потім - стовпці для «внутрішніх» логічних зв'язок (еквівалентність і права імплікація) і, нарешті, стовпець для зовнішньої (лівої) імплікації, який і дає істинності значення всієї формули. Цифри під таблицею показують порядок заповнення стовпців. Оскільки на будь-яких наборах істиннісних значень змінних формула приймає тільки значення 1. то вона є тотожно-істинною.
в) Розглянемо відразу таблицю істинності:
Оскільки формула може приймати обидва істиннісних значення (див. Виділений стовпець), то вона не є тотожно-істинною.
Скласти таблиці істинності для формул:
1.2. Спрощення формул. Тотожні перетворення.
Доказ равносильности, тотожною
істинності і тотожної хибності
формул і булевих функцій
зведення теорії
При використанні формального визначення формули алгебри логіки запис формул часто містить «зайві» дужки, якими можна нехтувати без шкоди для сенсу, якщо застосовувати деякі загальноприйняті правила.
По-перше, в окремо розташованих формулах (або якщо кордону формули ясні з контексту) можна опускати зовнішні дужки.
По-друге, як і арифметичні операції, зв'язки і квантори можна впорядкувати по їх «силі», т. Е. Розташувати в певному порядку, вважаючи, що ті символи, які в цьому порядку знаходяться правіше, «пов'язують сильніше», т. Е . їх слід виконувати в першу чергу:
Таким чином, диз'юнкція і кон'юнкція пов'язують сильніше, ніж імплікація, але слабкіше, ніж заперечення. Кон'юнкція зв'язує сильніше диз'юнкції. Слабкіше за все пов'язує еквівалентність. Рівноправні щодо зв'язування квантори (про це докладно в розділі 2), вони пов'язують сильніше, ніж будь-які логічні зв'язки.
У порівнянні із загальним визначенням формули формального мови для формул логіки висловлювань (далі в цьому розділі - просто формул) внесемо такі уточнення:
1) в якості пропозіціональних букв (індивідуальна змінних) будемо розглядати тільки прості висловлювання x, y. z,. B. B = 1, 0>;
2) складні формули з простих будемо будувати тільки за допомогою логічних операцій і дужок.
При такому підході будь-яка формула буде повністю визначатися своєю таблицею істинності.
Булевой функцією (або функцією алгебри логіки, логічної функцією) називається будь-яка функція n змінних (n = 1. 2.) з областю визначення, безліч значень якої міститься в B.
Будь-яку булеву функцію можна, очевидно, задати таблицею істинності точно такого ж виду, як ті таблиці, які зіставляються формулами. Якщо таблиця істинності, що задає булеву функцію f. збігається з таблицею істинності деякої формули Ф. то кажуть, що формула Ф являє (або задає. або реалізує) функцію f.
Дві формули Ф і називаються рівносильними (що позначається Ф), якщо вони представляють одну і ту ж булеву функцію.
Для будь-яких двох формул не представляє ніяких труднощів перевірити, рівносильні вони: досить порівняти їх істінностние таблиці.
Булеві функції (від будь-якого числа змінних), які беруть значення 1 незалежно від значень аргументів, називаються (як і реалізують їх формули) тавтологія (або тотожно-істинними).
Булеві функції (і реалізують їх формули), завжди приймають значення 0. називаються суперечностями (або тотожно-хибними).
Переконатися в тотожною істинності або тотожною хибності конкретної формули можна по тій же таблиці істинності (підсумковий стовпець таблиці буде містити тільки відповідну константу).
Інший спосіб докази равносильности формул або перевірки їх тотожної істинності чи хибності полягає у використанні так званих основних логічних законів (основних рівносильно), обгрунтування яких можна провести шляхом побудови відповідних таблиць істинності. До основних логічним законам зазвичай відносять такі співвідношення:
Результати обчислень таблиць істинності обох частин рівносильно не залежать від того, як отримані значення змінних, що входять в ці співвідношення, т. Е. Від того, чи є ці змінні незалежними або, в свою чергу, отримані в результаті будь-яких обчислень. Тому наведені равносильности залишаються справедливими при підстановці замість змінних будь-яких логічних функцій і, отже, будь-яких формул, що представляють ці функції. Важливо лише дотримуватися такого правила підстановки формули замість змінної. при підстановці формули Ф замість змінної x все входження змінної x в вихідне співвідношення повинні бути одночасно замінені формулою Ф.
У всякій алгебри (в тому числі і в булевої алгебри функцій) співвідношення
ФФ означає, що формули Фі Ф описують одну й ту ж булеву функцію f. Отже, якщо будь-яка формула Ф містить Фв якості подформули, то заміна Фна Ф не змінює елемента булевої алгебри f. над яким проводяться операції у формулі Ф; тому Ф ', отримана з Ф такою заміною, рівносильна Ф. Це твердження є правило заміни подформул. яке дозволяє за наявними рівносильно отримувати формули, рівносильні даної.
Відзначимо різницю між правилами підстановки і заміни. При підстановці змінна замінюється на формулу; формула може бути будь-хто. але потрібно одночасна її підстановка замість всіх входжень змінної. При заміні подформул замінюється будь-яка подформула, проте не на будь-яку іншу, а тільки на рівносильну їй. При цьому заміна всіх входжень вихідної подформули не обов'язкова.
Нехай є равносильность ФФ, де Фі Ф містять змінну x. Якщо замість всіх входжень x в Фі Ф підставити довільну формулу Ф. то вийдуть нові формули Ф 'і Ф', причому не обов'язково ФФ 'і ФФ'; проте між собою нові формули рівносильні: Ф 'Ф'. Якщо ж в Фкакую-небудь подформулу замінити на рівносильну їй, то вийде нова формула Ф '. рівносильна Ф.
Такі перетворення, що використовують равносильности формул (запас яких можна розширювати за допомогою правила підстановки) та правило заміни, називаються тотожними перетвореннями. Тотожні перетворення є потужним засобом докази равносильности формул і тотожної істинності або тотожною хибності формул, як правило, більш ефективним, ніж їх обчислення на наборах значень змінних (т. Е. Чим складання таблиць істинності).
Відзначимо, що «тактика» докази равносильности може бути різна: або перетворимо одну з формул, приводячи її до уваги інший, або перетворимо обидві формули, приводячи їх до однієї і тієї ж формулою.
Довести равносильность формул, використовуючи їх таблиці істинності:
а) Порівняємо таблиці істинності для правої і лівої частин:
1.13. Побудувати формулу U таку, щоб дана формула була тотожно істинною:
1.14. Побудувати формулу від трьох змінних, яка істинна в тому і тільки в тому випадку, коли рівно дві змінні помилкові.
1.15. Побудувати формулу від трьох змінних, яка приймає таке ж значення, як і більшість (меншість) змінних.
1.3. Нормальні форми формул логіки висловлювань
зведення теорії
Елементарної кон'юнкція називається кон'юнкція змінних або їх заперечень, в якій кожна змінна або її заперечення зустрічаються не більше одного разу.
Будь-яка диз'юнкція елементарних кон'юнкція називається диз'юнктивній нормальною формою (ДНФ).
Слід зазначити, що ДНФ функції (або формули) може бути не єдиною.
Алгоритм приведення до ДНФ може бути описаний із залученням наведених раніше рівносильно або основних логічних законів (див. Розд. 1.2). Спочатку за допомогою закону (II.1) і законів де Моргана (II.2), (II.3) все заперечення «спускаються» до змінних. Потім розкриваються дужки, за допомогою логічних законів (I.7), (I.8), (IV.7) і (IV.8) видаляються зайві кон'юнкції і повторення змінних в кон'юнкції, а за допомогою логічних законів (IV.1. ) - (IV.6) видаляються константи.
Елементарна кон'юнкція називається правильною. якщо в неї кожна змінна входить не більше одного разу (включаючи її входження під знаком заперечення).
Правильна елементарна кон'юнкція називається повною відносно змінних, якщо кожна з цих змінних входить в неї один і тільки один раз (може бути, під знаком заперечення).
Досконалої диз'юнктивній нормальною формою (СДНФ) щодо змінних називається ДНФ, в якій немає однакових елементарних кон'юнкція і всі елементарні кон'юнкції правильні і повні щодо змінних.
З через великий обсяг цей матеріал розміщений на декількох сторінках:
1 2 3