85764 (612568), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

1. (g r) - правило вилучення імплікації з першої із заданих формул.

2. ( g) ( r) - закон дистрибутивності 9б для формули 1.

3. (р→g) (p→r) - правило введення імплікації для формули 2.

Отже, задані формули еквівалентні: р→(g r) та (p→g) (p→r).

Приклад 1.16. Застосуванням законів логіки висловлювань доведемо еквівалентність формул р→g та → . Цю еквівалентність називають правилом контрапозиції.

1. g - правило вилучення імплікації у першій із заданих формул.

2. g - закон комутативності 1а для формули 1.

3. - закон подвійного заперечення 6 для формули 2.

4. → - правило введення імплікації для формули 3.

Отже, задані формули еквівалентні: р→g= → .

1.3. Нормальні форми логіки висловлювань.

Літералом називатимемо атом або заперечення атома. Прикладами літералів є р, , r. Літерал називають позитивним, якщо він не має знака заперечення, та негативним, якщо він має знак заперечення. Пару літералів {p, } називають контрарною парою.

Кажуть, що формулу f записано у кон'юнктивній нормальній формі (КНФ), якщо вона має вигляд f=f₁ f₂ … f_n(n≥1) і всі f_i (i=1,2,...,n) різні. Тут кожна з формул f₁,f₂,…,f_n є диз'юнкцією літералів, у якій всі атоми різні.

Приклад 1.17. Нехай p, g та r — атоми. Тоді f=(р ) ( g) - формула, записана в кон'юнктивній нормальній формі. У цій формулі f₁=(р ) та f₂=( g), тобто f₁ - диз'юнкція літералівp, , , а f₂ - диз'юнкція літералів таg.

Кажуть, що формулу f записано у диз'юнктивній нормальній формі (ДНФ), якщо вона має вигляд f=f₁ f₂ … f_n(n≥1) і всі f_i (i=1,2,...,n) різні. Тут кожна з формул f₁,f₂,…,f_n є кон'юнкцією літералів, у якій всі атоми різні.

Приклад 1.18. Нехай p, g та r - атоми. Тоді f=( g) (p ) - формула, записана у диз'юнктивній нормальній формі. У цій формулі f₁=( g) та f₂=( p ), де f₁ - кон'юнкція літералів та g, а f₂ - кон'юнкція літералівp, та .

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

Крок 1. Використати правила f→g= g та f~g=(f→g) (g→f) (див. параграф 1.2) для усунення логічних зв'язок "→" та "~".

Крок 2. Використати закон подвійного заперечення та закони де Моргана для перенесення знаку заперечення безпосередньо до атомів.

Крок 3. Використати відповідні закони дистрибутивності закони для побудови нормальної форми. Для побудови кон'юнктивної нормальної форми використати закон дистрибутивності для диз'юнкції відносно кон'юнкції (закон 3а з табл. 1.8). Для побудови диз'юнктивної нормальної форми використати закон дистрибутивності для кон'юнкції відносно диз'юнкції (закон 3 б з табл. 1.8).

Приклад 1.19. Побудуємо диз'юнктивну нормальну форму формули ((p )→r) ( →s). Наведемо послідовність кроків для побудови ДНФ та застосовані закони.

1. ( r) ( ) - усунення логічної зв'язки "→" із заданої формули.

1. (( ) r) ( ) - закон де Моргана 8а до формули з рядка 1.

2. (( g) r) (r s) - закон подвійного заперечення 6 до формули 2.

3. (( g) (r s)) (r (r s)) - закон дистрибутивності 3б до формули 3.

4. (( g r) ( g s)) ((r r) (r s)) - закон дистрибутивності 3б до формули 4.

5. ( g r) ( g s) (r r) (r s) - асоціативний закон 2а до формули 5.

6. ( g r) ( g s) r (r s) - закон ідемпотентності 7б до формули 6.

Ми одержали ДНФ. Звернемо увагу, що її можна спростити, якщо двічі використати закон поглинання 9б: диз'юнктивний член к поглинає члени ( g r) та (r s). Отже, ДНФ заданої формули ((p )→r) ( →s) також буде ( g s) r. Останні міркування свідчать, що ДНФ певної формули, якщо казати загалом, не єдина.

Приклад 1.20. Побудуємо кон’юнктиву нормальну форму формули (р (g→r))→s. Наведемо послідовність кроків побудови КНФ і застосовані закони та правила.

1. - усунення логічної зв'язки "→" із заданої формули.

2. s - закон де Моргана 8б до формули 1.

3. ( ) s - закон де Моргана 8а до формули 2.

4. (g ) s - закон подвійного заперечення 6 до формули 3.

5. s (g ) - закон комутативності 1а до формули 4.

6. ( s) (g ) - закон асоціативності 2а до формули 5.

7. ( g s) ( s) - закон дистрибутивності За до формули 6.

Формула ( g s) ( s) є КНФ формули (р (g→r))→s.

Розділ ІІ: Логіка предикатів.

2.1. Основні поняття логіки предикатів.

Як уже відзначалось під час вивчення логіки висловлювань, існують речення, які не є висловлюваннями та містять змінні. Був наведений приклад речення "х+1=3". Речення зі змінними не є висловлюваннями, але перетворюються в них, якщо надати значення змінним. Речення зі змінними дуже поширені. Вони містяться в математичних формулах та комп'ютерних програмах. Зокрема, у мовах програмування зустрічаються оператори такого змісту "повторювати цикл доти, поки змінні х та у не стануть рівними, або припинити обчислення циклу після 100 повторень". Якщо позначити через і лічильник повторень, то умова закінчення програми задаватиметься виразом "(x=y) (i>100)", а сам оператор матиме вигляд "повторювати, якщо (¬((x=y) (i>100)))"

Приклад 2.1. Прикладами речень, які містять змінні є "х>3", "x=y+3", "x+у=z". Ці речення ні істинні, ні фальшиві доти, поки змінні не одержать значення.

У наведеному прикладі речення "х>3", або, в іншій формі, "х більше 3" складається з двох частин: першу, змінну х, називають предметом, другу - "більше 3", - яка вказує властивість предмета, називають предикатом. Часто предикатом називають все речення.

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

1. Індивідні символи або сталі - це імена об'єктів, які починаються з великої букви: Іван, Марія та сталі: Т, F або 3.

2. Предметні символи - імена змінних, які позначають малими буквами, можливо, з індексами: х,у,z,v_i,w_j.

3. Предикатні символи — імена, якими позначають предикати та записують великими буквами: Р, Q, R, або змістовними словами, які записують великими буквами БІЛЬШЕ, ЛЮБИТЬ тощо.

Приклад 2.2. Позначимо речення "х більше 3" через Р(х), де предикатний символ Р позначає предикат "більше 3", а х - змінна, або предметний символ. Вираз Р(х) у цілому теж називають предикатом. Щоб записати твердження "х більше 3" як предикат, можна поступити інакше - визначити предикат БІЛЬШЕ(х,у), який означає "х більше y". Тоді речення "х більше 3" можна записати за допомогою предиката БІЛЬШЕ(х, 3).

Загалом, предикат, який містить n змінних: x₁, x₂, x₃,…, x_n, записують Р(х₁,х₂,...,х_n) та називають n-місним. Змінну x_i D_i (i=1,2,..,n) називають предметною, множину D_i - її предметною областю, а символ Р - n-місним предикатним символом. Замість терміну "предикат" іноді використовують "пропозиційна функція".

Щойно змінна х дістає значення з предметної області, предикат Р(х) набуває значення Т або F та перетворюється у висловлювання. Аналогічно, якщо всі змінні багатомісного предиката одержать значення, то він набуде значення істинності й теж перетвориться у висловлювання.

Атом логіки першого ступеня має вигляд Р(х₁, х₂,...,х_n), де Р- предикатний символ, а x₁,x₂,…,x_n - предметні або індивідні символи.

Приклад 2.3. Нехай вираз "x+у=2" задано предикатом Q(х, у). Тоді Q(1,2) - фальшиве висловлювання, а Q(2,0) - істинне. Позначимо це так: Q(1,2)=F, Q(2,0)=Т. Задамо речення "х любить y" предикатом ЛЮБИТЬ(х,у). Тоді істинне речення "Іван любить Марію" подається істинним висловлюванням ЛЮБИТЬ (Іван, Марія).

Приклад 2.4. Якщо БІЛЬШЕ(х, у) - предикат, визначений у прикладі 2.2, то БІЛЬШЕ(5,3) - істинне висловлювання, а БІЛЬШЕ (1,3) - фальшиве висловлювання.

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

Характеристики

Список файлов курсовой работы