5.2 Лабораторна робота №4

Тема. Логіка висловлень

Мета. Засвоїти основні поняття логіки висловлень

Завдання.

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

2 Записати формулу під № m із Додатку 1, користуючись тільки логічними операціями (, ), де .m = 33- n.

3 Користуючись формулами логіки висловлень під № 1-14 із Додатку 1,перетворити складне висловлення із завдання № 2 (яке містить тільки логічні операції (, )) так, щоб рівносильне йому висловлення містило заперечення лише простих висловлень.

4 За методом Куайна довести тотожну істинність формули логіки висловлень із завдання № 3.

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

1 Користуючись таблицями істинності доведемо тотожну істинність формули логіки висловлень :

1) (АВ)  (ВА)

А		В		В		А
1	1	1	1	1	1	1
1	0	0	1	0	1	1
0	1	1	1	1	0	0
0	1	0	1	0	1	0

2 Запишемо формулу логіки висловлень, користуючись тільки логічними операціями (, ).



3 Користуючись формулами логіки висловлень під № 1-14 із Додатку 1,перетворимо складне висловлення із завдання № 2 (яке містить тільки логічні операції (, )) так, щоб рівносильне йому висловлення містило заперечення лише простих висловлень.

4. За методом Куайна довести тотожну істинність формули логіки висловлень із завдання № 3. Скористаємося тим, що ММ1, а формула ММ є суперечністю, тобто ММ0

Контрольні питання

1 Що називається простим висловленням або атомом?

2 Як будувати правильно побудовані формули (ППФ)Приклад

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

4 Рівносильні формули.

5 Повні системи логічних зв'язок. Приклад .

6 Відновлення формул за таблицями істинності.

7 Визначення числення висловлювань як аксіоматичної теорії.

8 Приклад виведення теореми із посилок ( гіпотез) в численні висловлювань .

9 Методи перевірки тавтологічності формул числення висловлю-вань (метод Куайна).

10 Теорема дедукції.

11 Зв'язок між тавтологіями та теоремами числення висловлень.

12 Несуперечність числення висловлень.

6 Математична логіка.

Логіка предикатів 1-го порядку.

6.1 Теоретичні поняття і визначення

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

Наприклад, розглянемо такі висловлення:

1 Всі люди смертні, Сократ - людина. Значить Сократ смертний.

2 Деякі студенти не є відмінниками.

3 Не всі студенти першого курсу ровесники.

Мова логіки предикатів дозволяє формалізувати такі слова як "всі", "деякі" і дозволяє обгрунтувати коректність таких висновків як в прикладі 1.

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

Приклади елементарних предикатів:

1 "х являється студентом кафедри ІТП". Якщо замість х указати конкретне призвище, то речення перетвориться на істине або хибне висловлення.

2 "студент х є ровесник студенту у". Так само, якщо замість х, у указати конкретні призвища, то речення перетвориться на істинне або хибне висловлення.

3 х + у = z Це рівняння від трьох змінних можна розглядати як предикат, де х, у, z – натуральні числа. Якщо замість змінних підставити які-небудь натуральні числа, то отримаємо істинні, або хибні висловлення.

4 Якщо ж використовувати логіку предикатів для створення інформаційної системи проектування машин, то як приклад можна розглянути такий предикат:

"у являється деталлю пристрою х"

Якщо підставити назви окремих деталей і пристроїв, то отримаємо хибне, або істинне висловлення.

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

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

Предикати можуть мати не тільки одну, 2, 3, а і більше число змінних.

Предикат від n змінних називають n-місним предикатом.

Позначають предикати великими латинськими буквами: F(x),

P(x, y), R(x, y, z) і т. д.

Більш складні логічні формули на основі предикатів можна будувати із простих, якщо застосовувати логічні зв'язки , , , , .

Наприклад, " х – непарне число"  " х кратне 7".

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

Запис (х) Р(х) буде означати, що існує об'єкт, суб'єкт, предмет, який має властивість Р(х). Припускається існування хоча б одного х, для якого виконується властивість Р(х). Частину (х) виразу (х) Р(х) називають квантором існування.

Запис (х)Р(х) буде означати, що для кожного (будь-якого) х властивість Р(х) виконується. Частина (х) виразу (х)Р(х) називається квантором загальності

Вираз (х)Р(х) може бути істинним або хибним.

Приклад

Нехай Р(х) – є властивість "х –парне число", де х N. Тоді вираз (х)Р(х) приймає значення хибність, а вираз (х) Р(х) приймає значення істина.

Предметна змінна, віднесена до квантора, називається зв'язаною змінною.

Квантори застосовують і до багатомісних предикатів.

Змінні n-місного предиката, які не віднесені до кванторів, називаються вільними змінними.

Наприклад

(х)Р(х, у) х – зв'язана змінна,

у – вільна змінна.

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

Тепер дамо формальне визначення n-місного предиката.

Нехай х1, …, хn - набір із n змінних, які приймають значення відповідно із множин D1, ….. Dn. Функція P: D1x …x Dn. {1, 0} називається n-арним (n-місним) предикатом; х1, …, хn - предметними змінними; добуток D1x …x Dn – предметною областю; елементи множини D1, ….. Dn – предметними константами; позначення функції Р – предикатним символом; а елементи 1, 0 називаються істиною і хибністю, відповідно.

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

Перш ніж перейти до опису алфавіту і формул логіки предикатів, неформально пояснемо роль додаткових елементів – функціональних символів.

Розглянемо предикат "х⁷ > 1". Цей предикат можна записати у іншому вигляді, застосувавши функціональний символ f(x) = х⁷:

" f(x) > 1"

Функціональні символи – це символи функцій, які перетворюють значення предметних змінних.

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

Індуктивне визначення терма таке: 1) кожна предметна змінна є термом; 2) якщо t1….tn – терми, f – n-арний функціональний символ, то f(t1….tn) є терм.

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

Алфавіт логіки складаєтся із таких символів: предметні змінні х1, х2, ……; предметні константи a1, a2, ……; функціональні символи f1m1, f1m2, ……fjmk; предикатні символи А1n1, A1n2, ……Ajnk - Верхні індекси вказують на чсло аргументів, нижні – щоб розрізнити предикати з однаковим числом аргументів; символи логічних операцій ,  та квантор . допоміжні символи: дужки (),кома (,) .

Основними конструкціями мови логіки предикатів є терми і формули.

Терми використовують для позначення об'єктів , для назви об'єктів.

Формули використовують для запису тверджень про об'єкти.

Атомарною (елементарною ) формулою називається вираз виду An(t1, t2….tn), де An – n-арний предикатний символ, t1, t2….tn - терми.

Індуктивне визначення формули таке: всяка елементарна формула є формулою; якщо А і В - формули і х – предметна змінна, то кожний із виразів: (А) (АВ) (х)А - є формулою. 3) формулами являються ті і тільки ті вирази, які побудовані згідно пунктів 1), 2) цього визначення.

Розглянемо таку формулу:

(х) (А)

яка означає "не для кожного х не виконується властивість А" це очевидно означає, що існує х, для якого виконуєтьс властивість А. Тому по додатковому визначенню (х)(А) = (х) (А)

будемо ще розглядати квантор існування, ввівши для його запису символ .

Кон'юнкцію можна виразити через ,  таким чином:

А  В  (АВ).

Диз'юнкцію можна виразити через  і  таким чином:

А  В  (А  В).

Еквівалентність можна виразити через , , :

АВ  (А  В)  (А  В).

Згідно з визначенням формул, квантори застосовуються у формулах як і логічні зв'язки. Тому треба визначити порядок (ранги)

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

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

, , ,(х) або (х), , .

Наприклад, наступні вирази є формулами:

1. (х)(у)А(х,у)  (В(х,у) (*);

х у А(х,у)  В(х,у)

2) х А₁²(х, f₁¹(x)) х А₁¹( f₂¹(x)) (**)

де f₁¹(x) =  х ,

А₁²(х, f₁¹(x)) – це така властивість:"дійсна змінна не більше за модуль цієї змінної" . А₁²(х, f₁¹(x))  "х   х "

f₂¹(x) = х², А₁¹( f₂¹(x)) це властивість числа бути парним числом.

Змінні х,у в першій формулі (*) зв'язані бо перше їх входження віднесене до квантора і водночас х,у – вільне, бо друге їх входження не віднесене до квантора.

У формулі х А або х А формулу А називають областю дії квантора по змінній х.

У першій формулі предикат А(х, у) є областю дії квантора загальності () по зміній х і квантора існування () по змінній у.

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

Що означає задати інтерпретацію даної формули? Це означає:

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

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

Так формула (**) має значення істина в даній інтерпретації.

Приклад

Розглянемо дві інтерпретації однієї і тієї формули

хА²(f¹(x), а₁).

Перша інтерпретація D = R; a₁= 2, f¹(x)=cosx, А²(f¹(x), а₁)  "f¹(x) > а₁".

Отримане висловлення х(cosx > 2) є хибним.

Друга інтерпретація D = R; a₁= 1, f¹(x)=x², А²(f¹(x), а₁)  "f¹(x) = а₁".

Отримане висловлення х(x² = 1) є істинним.

Якщо інтерпретація задана, то можна знайти значення даної формули в заданій інтерпретації.

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

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

Приклад

Розглянемо приклад загальнозначимої формули

х А¹(х)  х А¹(х).

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

Приклад

Формула х(Р(х))  х(Р(х)) .

Ця формула не є загальнозначимою.

Роглянемо таку інтерпретацію.

Нехай Р(х) – предикат ("х- просте число"). Цей предикат заданий на множині D= {2, 4}. Тоді:

- формула х(Р(х)) має значення "істина";

- Формула х(Р(х)) має значення "хибність" і вся формула

х(Р(х))  х(Р(х)) має значення "хибність". Тобто ця формула не є загальнозначимою.

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

А  В  (АВ)  (В А)

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

Розглянемо найбільш застосовні рівносильні перетворення формул з кванторами (закони логіки предикатів).

1 Введення заперечення формули

хА  хА

хА  хА

2 Перенесення кванторів через заперечення

(хА)  хА

(хА)  хА

Тобто можна сформулювати правило

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

Правило для побудови заперечення висловлення, яке має кілька кванторів.

Щоб побудувати заперечення висловлення, яке починається з кількох кванторів, достатньо кожний квантор замінити двоїстим, а заперечення перенести на вираз, який стоїть за кванторами (тобто на область дії кванторів)

3 Перейменування зв'язаних змінних

хВ(х)  уВ(у)

хВ(х)  уВ(у)

4. Перестановка кванторів одного типу

хуА(х,у)  ухА(х,у)

ху(х,у)  ухА(х,у)

4. Винесення кванторів за дужки

1) (Qx)A(x)  B  (Qx)(A(x)  B)

(Qx)A(x)  B  (Qx)(A(x)  B),

де (Qx) є або (х), або (х),

формула A(x) містить змінну х, а формула В не містить змінної х.

Ця пара формул показує, що квантор не має відношення до висловлення В.

2) (х)А(х) (х)В(х)  (х)(A(x)  B(х))

(х)(A(x)  B(х))  (х)А(х)  (х)B(х)

(перенесення квантора загальності через кон'юнкцію.

Дистрибутивність квантора загальності відносно кон'юнкції).

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

(х)(В(x)  С(х))  хВ(х)  хС(х)

(х)А(х)  (х)B(х)  (х)(А(х)  B(х))

(х)(А(х)  B(х))  (х)А(х)  (х)B(х)

(перенесення квантора існування через диз'юнкцію.

Дистрибутивність квантора існування відносно диз'юнкції)

В той же час дистрибутивність квантора існування відносно кон'юнкції не має місця, тобто

х(А(х)  B(х)  хА(х)  хB(х)

3) (Q₁x) A(x)  (Q₂x) B(x)  (Q₁x) (Q₂y)(A(x)  B(y))

(Q₁x) A(x)  (Q₂x) B(x)  (Q₁x) (Q₂y)(A(x)  B(y))

Не можна переставляти квантори різних типів, тобто

ху(А(х,у)  ухА(х,у)

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

Для визначення загальнозначущих формул, так само, як і в численні висловлень, у численні (логіці) предикатів 1-го порядку задані аксіоми і правила виведення (5 аксіом і 2 правила виведення). Ці аксіоми і правила виведення дають змогу з одних загальнозначущих формул одержувати інші.

Нагадаємо, що логіка першого порядку – це числення, в якому квантори ,  завжди діють лише на множині предметних змінних.

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

Наприклад,

(х)(у)(А(х)  В(у) - нормальна форма формули;

(х)А(х) (у) В(у) не є нормальною формою для формули.

Формальне визначення префіксної (попередньої) нормальної форми (ПНФ) формули логіки предикатів 1-го порядку. Говорять, що формула логіки предикатів 1-го порядку знаходиться в ПНФ тоді і тільки тоді, коли вона має вигляд (Q1x1)(Q2x2) ….(Qnxn) A, де (Qixi) є або (хi) або (хi) і всі хi різні для різних і, та А – формула, яка не має кванторів.

Алгоритм побудови ПНФ формули логіки предикатів

1-го порядку

Перший крок. Вилучити логічні зв'язки ,  за допомогою правил:

А  В  (А  В)  ( В  А)

А  В  А  В.

Другий крок. Перенести знак  всередину формул, користуючись правилами:

(А)  А (подвійного заперечення);

(А  В) = А  В де – Моргана;

(А  В) = А  В

(х)А = хА введення заперечення формули з

 (х)А = хА кванторами.

Третій крок. Перейменувати зв'язані змінні, якщо є така необхідність.

Четвертий крок. Використати правила винесення кванторів за дужки для одержання ПНФ.