<
  • Главная
Статьи

Логіка висловлювань: теорія і застосування. Приклади рішень завдань

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

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

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

Логіка висловлювань відволікається від змістового навантаження висловлювань і вивчає їх истинностное значення, тобто чи є висловлювання істинним або хибним.

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

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

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

Так, може бути оголошена логічна змінна з ім'ям "ПользовательЗарегістрірован" (або його англомовний аналог), що має форму висловлювання, якої може бути присвоєно логічне значення "істина" при виконанні умов, що дані для реєстрації відправлені користувачем і ці дані програмою визнані придатними. У подальших обчисленнях значення змінних можуть змінюватися в залежності від того, яке логічне значення ( "істина" або "брехня") має змінна "ПользовательЗарегістрірован". В інших случах змінної, наприклад, з ім'ям "ДоДняХОсталосьБолееТрёхДней", може бути присвоєно значення "Істина" до деякого блоку обчислень, а в ході подальшого виконання програми це значення може зберігатися або змінюватися на "брехня" і від значення цієї змінної залежить хід подальшого виконання програми.

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

Для математичних висловлювань завжди можна зробити вибір між двома різними альтернативами "істина" і "брехня", а для висловлювань, зроблених на "словесному" мовою, поняття "істинності" і "хибність" дещо розпливчасті. Однак, наприклад, такі словесні форми, як "Іди додому" і "Чи йде дощ?", Не є висловлюваннями. Тому зрозуміло, що висловлюваннями є такі словесні форми, в яких щось стверджується. Чи не є висловлюваннями питальні або оклику пропозиції, звернення, а також побажання або вимоги. Їх неможливо оцінити значеннями "істина" і "брехня".

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

Наприклад, дані судження: "собака - тварина", "Париж - столиця Італії", "3

Перше з цих висловлювань може бути оцінений символом "істина", друге - "брехня", третє - "істина" і четверте - "брехня". Таке трактування висловлювань складає предмет алгебри висловлювань. Будемо позначати висловлювання великими латинськими літерами A, B, ..., а їх значення, тобто істину і брехня, відповідно І і Л. У звичайній мові вживаються зв'язку між висловлюваннями "і", "або" і інші.

Ці зв'язки дозволяють, поєднуючи між собою різні висловлювання, утворювати нові висловлювання - складні висловлювання. Наприклад, зв'язка "і". Нехай дано висловлювання: більше 3" і висловлювання менше 4". Можна організовувати нове - складне висловлювання більше 3 і π менше 4". Вислів "якщо π ірраціонально, то π ² теж ірраціонально" виходить зв'язуванням двох висловлювань зв'язкою "якщо - то". Нарешті, ми можемо отримати з будь-якого висловлювання нове - складне висловлювання - заперечуючи початкове висловлювання.

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

Нехай дано два довільних висловлювання A і B.

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

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

AB

І І І І Л Л Л І Л Л Л Л

2. Друга логічна операція над висловлюваннями A і B - диз'юнкція, що виражається у вигляді, визначається наступним чином: воно істинне тоді і тільки тоді, коли хоча б одне з первинних висловлювань істинно. У звичайній мові ця операція відповідає з'єднанню висловлювань зв'язкою "або". Однак тут ми маємо не розділову "або", яке розуміється в сенсі "або-або", коли A і B не можуть бути обидва істинними. У визначенні логіки висловлювань істинно і при істинності лише одного з висловлювань, і при істинності обох висловлювань A і B.

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

AB

І І І І Л І Л І І Л Л Л

3. Третя логічна операція над висловлюваннями A і B, що виражається у вигляді; отримане таким чином висловлення помилкове тоді і тільки тоді, коли A істинно, а B помилково. A називається посилкою, B - наслідком, а висловлювання - проходженням, звана також импликацией. У звичайній мові ця операція відповідає зв'язці "якщо - то": "якщо A, то B". Але у визначенні логіки висловлювань цей вислів завжди істинно незалежно від того, істинно або хибно висловлювання B. Цю обставину можна коротко сформулювати так: "з помилкового слід все, що завгодно". У свою чергу, якщо A істинно, а B помилково, то все висловлення помилкове. Воно буде істинним тоді і тільки тоді, коли і A, і B істинні. Коротко це можна сформулювати так: "з істинного не може слідувати помилкове".

Таблиця істинності для проходження (імплікації):

AB

І І І І Л Л Л І І Л Л І

4. Четверта логічна операція над висловлюваннями, точніше над одним висловом, називається запереченням висловлювання A і позначається ~ A (можна зустріти також вживання не символу ~, а символу ¬, а також верхнього надчёрківанія над A). ~ A є висловлювання, яке помилково, коли A істинно, і істинно, коли A помилково.

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

5. І, нарешті, п'ята логічна операція над висловлюваннями називається еквівалентністю і позначається. Отримане таким чином висловлювання є висловлювання істинне тоді і тільки тоді, коли A і B обидва істинними чи обидва хибні.

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

AB

І І І І І І Л Л І Л Л І І Л Л Л Л І І І

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

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

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

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

Приклад 1. Обчисліть логічні значення наступних висловлювань:

1);

2)

3);

4);

5);

6);

7).

Рішення.

1) Значення висловлювання в перших дужках одно "істина", значення виразу в других дужках - також істина. Обидва висловлювання з'єднані логічною операцією "І" (дивимося правила для цієї операції вище), тому логічне значення всього цього висловлювання - "істина".

2) Значення висловлювання в дужках - "брехня". Перед цим зтім висловлюванням варто логічна операція заперечення, тому логічне значення всього цього висловлювання - "істина".

3) Значення висловлювання в перших дужках - "брехня", значення висловлювання в других дужках - також "брехня". Висловлювання з'єднані логічною операцією "АБО" і жодне з висловлювань не має значення "істина". Тому логічне значення всього цього висловлювання - "брехня".

4) Значення висловлювання в дужках - "брехня". Перед цим висловлюванням варто логічна операція заперечення. Тому логічне значення всього цього висловлювання - "істина".

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

6) Значення висловлювання в перших дужках - "істина", значення висловлювання в других дужках - також "істина". Два цих висловлювання з'єднані логічною операцією "І", тобто виходить "істина І істина". Отже, логічне значення всього цього висловлювання - "істина".

7) Значення висловлювання в перших дужках - "істина". Значення висловлювання в других дужках - "брехня". Два цих висловлювання з'єднані логічною операцією "АБО", тобто виходить "істина АБО брехня". Отже, логічне значення всього цього висловлювання - "істина".

Приклад 2. Запишіть за допомогою логічних операцій наступні складні висловлювання:

1) "Користувач не зареєстрований";

2) "Сьогодні неділя і деякі співробітники знаходяться на роботі";

3) "Користувач зареєстрований тоді і тільки тоді, коли відправлені користувачем дані визнані придатними".

Рішення.

1) - одиночне висловлювання "Користувач зареєстрований", логічна операція: 1) - одиночне висловлювання Користувач зареєстрований, логічна операція:   ; ;

2) - одиночне висловлювання "Сьогодні неділя", - "Деякі співробітники знаходяться на роботі", логічна операція: 2) - одиночне висловлювання Сьогодні неділя, - Деякі співробітники знаходяться на роботі, логічна операція:   ; ;

3) - одиночне висловлювання "Користувач зареєстрований", - "Відправлені користувачем дані визнані придатними", логічна операція: 3) - одиночне висловлювання Користувач зареєстрований, - Відправлені користувачем дані визнані придатними, логічна операція: .

Вирішити приклади на логіку висловлювань самостійно, а потім подивитися рішення

Приклад 3. Обчисліть логічні значення наступних висловлювань:

1);

2);

3);

4);

5).

Правильне рішення і відповідь .

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

1) "Якщо годинник неправильно показують час, то можна невчасно прийти на заняття";

2) "У дзеркалі можна побачити своє відображення і Париж - столиця США";

3) Чи не "дуб - дерево".

Правильне рішення і відповідь .

Приклад 5. Визначте логічне значення виразу

,

якщо

,

,

,

.

Правильне рішення і відповідь .

Поняття логічної форми складного висловлювання уточнюється за допомогою поняття формули логіки висловлювань.

У прикладах 1 і 2 ми вчилися записувати за допомогою логічних операцій складні висловлювання. Взагалі-то вони називаються формулами логіки висловлювань.

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

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

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

~, ∧, ∨, →, ↔,

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

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

1) елементарні формули (атоми) є формулами логіки висловлювань;

2) якщо і - формули логіки висловлювань, то,,,, теж є формулами логіки висловлювань;

3) тільки ті вирази є формулами логіки висловлювань, для яких це випливає з 1) і 2).

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

Приклад 6. Нехай - одиночне висловлювання (атом) "Все раціональні числа є дійсними", - "Деякі дійсні числа - раціональні числа", - "деякі раціональні числа є дійсними". Переведіть в форму словесних висловлювань такі формули логіки висловлювань:

1) 1)   ; ;

2) 2)   ; ;

3) 3)   ; ;

4) 4)   ; ;

5) 5)   ; ;

6) 6) .

Рішення.

1) "немає дійсних чисел, які є раціональними";

2) "якщо не всі раціональні числа є дійсними, то немає раціональних чисел, які є дійсними";

3) "якщо всі раціональні числа є дійсними, то деякі дійсні числа - раціональні числа і деякі раціональні числа є дійсними";

4) "всі дійсні числа - раціональні числа і деякі дійсні числа - раціональні числа і деякі раціональні числа є дійсними числами";

5) "всі раціональні числа є дійсними тоді і тільки тоді, коли не має місце бути, що не всі раціональні числа є дійсними";

6) "не має місця бути, що не має місце бути, що не всі раціональні числа є дійсними і немає дійсних чисел, які є раціональними чи ні раціональних чисел, які є дійсними".

Приклад 7. Складіть таблицю істинності для формули логіки висловлювань Приклад 7 , Яку в таблиці можна позначити.

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

Зауважимо, що ніякої атом не має виду,,,,. Такий вигляд мають складні формули.

Число дужок в формулах логіки висловлювань можна зменшити, якщо прийняти, що

1) в складній формулі будемо опускати зовнішню пару дужок;

2) впорядкуємо знаки логічних операцій "по старшинству":

↔, →, ∨, ∧, ~.

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

Приклад 8. Відновіть дужки у формулі логіки висловлювань.

Рішення. Дужки відновлюються покроково наступним чином:

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

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

Так як істинність або хибність складних висловлювань залежить лише від значень, а не від змісту висловлювань, кожному з яких відповідає певна буква, то перевірку того, чи є це висловлювання тавтологією, можна підставити в такий спосіб. У досліджуваному вираженні на місце букв підставляються значення 1 і 0 (відповідно "істина" і "брехня") усіма можливими способами і з використанням логічних операцій обчислюються логічні значення виразів. Якщо всі ці значення рівні 1, то досліджуваний вираз є тавтологія, а якщо хоча б одна підстановка дає 0, то це не тавтологія.

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

Протилежний сенс має логічне протиріччя. Якщо всі значення висловлювань рівні 0, то вираз є логічне протиріччя.

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

Крім тавтологію і логічних протиріч існують такі формули логіки висловлювань, які не є ні тавтологія, ні протиріччями.

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

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

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

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

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

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

Те, що ми називаємо логічними операціями, вперше з'явилося приблизно в Стародавній Греції для доказу філософських постулатів. А в наш час логічні операції найбільш широко застосовуються в комп'ютерній техніці. Але при всьому цьому комп'ютер "не вміє" виконувати логічну операцію імплікації. Вона комп'ютера "незрозуміла". Є, однак, спосіб змусити комп'ютер розуміти умова "якщо ..., то", відповідне, як відомо, імплікації. Для цього замість складеного оператора "якщо p, то q" потрібно використовувати складовою оператор »не p або q". Тобто, Те, що ми називаємо логічними операціями, вперше з'явилося приблизно в Стародавній Греції для доказу філософських постулатів вместо .

Як видно нижче, таблиця істинності для такої замісної логічної операції ідентична таблиці істинності для імплікації.

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

; ;

. .

Рішення.

Замінюємо імплікації між двома парами дужок, заперечуючи самий лівий знак заперечення:

. .

Прибираємо еквіваленцію між і і між і:

. .

Використовуючи закон де Моргана, трохи спрощуємо і остаточно отримуємо:

. .

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

Приклад валидного аргументу:

  • Посилка. A і B - програмісти
  • Посилка. A і B розробляють програми для бухгалтерів
  • Висновок. Є програмісти, які розробляють програми для бухгалтерів

Тобто, з посилок логічно випливає висновок.

Приклад не валидного аргументу:

  • Посилка. Запис числа може містити кому
  • Посилка. У реченні може бути кома
  • Висновок. Є числа, які називаються пропозиціями

Тобто, з посилок логічно не випливає висновок.

Приклад 12. Перевірте валідність аргументу, якщо

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

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

Однак, наприклад, такі словесні форми, як "Іди додому" і "Чи йде дощ?


Новости
  • Виртуальный хостинг

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

  • Редизайн сайта

    Редизайн сайта – это полное либо частичное обновление дизайна существующего сайта.... 
    Читать полностью

  • Консалтинг, услуги контент-менеджера

    Сопровождение любых интернет ресурсов;- Знание HTML и CSS- Поиск и обновление контента;-... 
    Читать полностью

  • Трафик из соцсетей

    Сравнительно дешевый способ по сравнению с поисковым и контекстным видами раскрутки... 
    Читать полностью

  • Поисковая оптимизация

    Поисковая оптимизация (англ. search engine optimization, SEO) — поднятие позиций сайта в результатах... 
    Читать полностью