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

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

Приклад 1.5. Вирази (р→), (р), (р¬), (g) - не формули.

Якщо не виникає непорозумінь, то деякі пари круглих дужок можуть бути випущені.

Приклад 1.6. Вирази рg, р→g є формулами (рg) та (р→g), відповідно.

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

Нехай p та g — формули. Тоді значення істинності формул (¬p), (рg), (рg), (р→g) та (р~g) так пов'язані зі значеннями істинності формул р та g.

1.   Формула (¬р) істинна, коли р фальшива, і фальшива, коли р істинна. Її читають "не р", або "це не так, що р" та називають запереченням р. Замість (¬р) заперечення р позначають також . У такому разі знак заперечення одночасно відіграє роль дужок.

2.   Формула (рg) істинна, якщо р та g одночасно істинні. У всіх інших випадках (рд) фальшива. Формулу (рg) читають "р і g" та називають кон’юнкцією формул р та g.

3.   Формула (рg) істинна, якщо істинна принаймні одна з формул р або g. В іншому випадку (рg) - фальшива. Формулу (рg) читають "р або g" та називають диз'юнкцією формул р та g.

4.   Формула (р→g) фальшива, якщо р істинна, а g - фальшива. У всіх інших випадках (р→g) істинна. Формулу (р→g) читають "якщо р, то g", "з р випливає g", або "р лише, якщо g" та називають імплікацією. Тут атом р називають припущенням імплікації, а g - висновком імплікації.

5. Формула (р~g) істинна, якщо р та g мають однакові значення істинності. У всіх інших випадках (р~g) - фальшива. Формулу (р~g) читають "р тоді й лише тоді, коли g" або ″р еквівалентне g" та називають еквівалентністю формул р та g.

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

Таблиця 1.1

р g (¬p)

(pg)

g)

(p→g) (p~g)
T T F T T T T
T F F F T F F
F T T F T T F
F F T F F T T

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

Приклад 1.8. Знайдемо кон'юнкцію висловлювань p та g, де р є висловлюванням "Сьогодні п'ятниця", а g - висловлюванням "Сьогодні падає дощ". Кон'юнкцією цих висловлювань є висловлювання "Сьогодні п'ятниця і сьогодні падає дощ". Це висловлювання істинне у дощову п'ятницю і фальшиве не в п'ятницю або у не дощову п'ятницю.

Приклад 1.9. Що є диз'юнкцією висловлюваньg та p, які визначені у прикладі 1.8? Диз'юнкцією висловлювань p та g, є висловлювання pg "Сьогодні п'ятниця або падає дощ". Це висловлювання істинне в будь-яку п'ятницю або в дощовий день. Дощова п'ятниця також долучається. Це висловлювання фальшиве тільки в одному випадку - у не дощову п'ятницю.

Логічна зв'язка "диз'юнкція" відповідає одному з двох способів уживання слова "або" в українській мові. Диз'юнкція істинна, якщо істинне принаймні одне з двох висловлювань. Наприклад, її використовують у реченні "Лекції з логіки можуть відвідувати студенти, які прослухали курси математичного аналізу або дискретної математики". Зміст цього речення полягає в тому, що лекції можуть відвідувати як студенти, які прослухали обидва курси, так і ті студенти, які прослухали тільки один з цих курсів. Інший спосіб використання диз'юнкції - це альтернативне "або". Для прикладу, така диз'юнкція відповідає реченню "Лекції з логіки можуть відвідувати студенти, які прослухали один з двох курсів — математичний аналіз або дискретну математику". Зміст цього речення полягає в тому, що студенти, які прослухали обидва ці курси, вже не повинні слухати лекцій з логіки. Аналогічно, якщо в меню вказано "Закуску або салат подають з першою стравою", то це майже завжди означає, що з першою стравою подадуть або закуску, або салат, але не обидві страви. Тобто, це альтернативне, а не звичайне "або", його позначають "". Значення істинності альтернативного "або" наведено у табл. 1.2.

Таблиця 1.2

p g

pg

T T F
T F T
F T T
F F F

Імплікацію, як логічну зв'язку, ще називають умовним реченням. Щоб зрозуміти значення істинності імплікації, треба розуміти її як зв'язок обов'язкового та очікуваного. Для цього розглянемо речення "Якщо ви виконаєте всі завдання, то отримаєте відмінну оцінку". Це означає, що якщо студенти виконали всі завдання, то вони отримають відмінну оцінку. Якщо ж студенти не виконали всіх завдань, то вони можуть отримати оцінку "відмінно", а можуть і не отримати її, залежно від інших обставин. Однак, якщо студенти зробили всі завдання, але викладач не поставив оцінку "відмінно", то студенти відчуватимуть себе ображеними. Останній випадок відповідає ситуації, коли p істинне, а g фальшиве в імплікації p→g , де p - припущення імплікації "Ви виконаєте всі завдання", а g - її висновок "Ви отримаєте відмінну оцінку".

Визначення імплікації дещо інше від розуміння її в природній мові, де її вживають для вказання причинно-наслідкового зв'язку. Для прикладу, речення "Якщо буде сонячно, то ми підемо на пляж" - умовне, яке вживають у звичайній мові. Це речення залишається істинним до того моменту, коли настане сонячний день, але ми не підемо на пляж. За означенням імплікації умовне речення "Якщо сьогодні п'ятниця, то 2+3=5" істинне, оскільки її висновок істинний. При цьому значення істинності припущення імплікації тут не має відношення до висновку. Імплікація "Якщо сьогодні п'ятниця, то 2+3=6" істинна щодня, крім п'ятниці, хоча 2+3=6 фальшиве. Останні дві імплікації ми не вживаємо у природній мові (хіба що, як жарт), оскільки немає змістовного зв'язку між припущенням та висновком у кожному з наведених умовних речень.

Конструкція IF-THEN , яку використовують в алгоритмічних мовах, відрізняється від імплікації у логіці. В алгоритмічних мовах цю конструкцію використовують у вигляді "ІF р ТНЕN S ", де р висловлювання, а S - програмний сегмент, що складається з одного або багатьох операторів. Програмний сегмент S виконують, якщо р істинне, та не виконують, якщо p фальшиве.

Для знаходження значення істинності складного висловлювання потрібно надати значення істинності всім атомам, які містить формула. Надання значень істинності всім атомам формули називають її інтерпретацією. У разі обчислення значень істинності формул, які зображають складні висловлювання, потрібно знаходити значення логічних зв'язок згідно з правилами, визначеними в табл. 1.1. Послідовність обчислень визначають парами дужок, які містить складне висловлювання. Якщо формула має n атомів, то існує 2n способів надати значення істинності її атомам, тобто така формула має 2n інтерпретацій, а всі її значення можна звести в таблицю істинності з 2n рядками. Формулу, яка містить n атомів, називають n-місною. У разі n=1 формула одномісна.

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

Приклад 1.10. Розглянемо формулу (рg)→(р~). Оскільки кожному з атомів р, g та r можна надати 2 значення - F або Т, то задана формула має 23=8 інтерпретацій. Для прикладу, обчислимо значення істинності заданої формули для значень істинності атомів p, g та r, які дорівнюють F, Т та F, відповідно. Це задає одну з інтерпретацій формули. Тоді (рg) має значення F, оскільки р фальшиве;  має значення Т, оскільки r фальшиве; (р~r) фальшиве, оскільки р фальшиве, а  істинне; нарешті ((рg)→(р~)) істинне, оскільки (рg) фальшиве. Отже, задана формула виконується у цій інтерпретації, оскільки набуває значення Т. Значення істинності формули (рg)→(р~) у всіх її інтерпретаціях наведено в табл. 1.3.

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

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


Таблиця 1.3

p g r

(pg)

(р~)

g)→(р~)

T T T F T F F
T T F T T T T
T F T F F F T
T F F T F T T
F T T F F T T
F T F T F F T
F F T F F T T
F F F T F F T

Приклад 1.11. Розглянемо формулу ((р→g) p)→g. Атомами в цій формулі є р та g, а формула має 22=4 інтерпретації. Значення істинності заданої формули наведено в табл. 1.4. Задана формула істинна в усіх її інтерпретаціях, тобто вона - тавтологія.

Таблиця 1.4

p g (р→g)

(р→g) p

((р→g) p)→g

T T T T T
T F F F T
F F T F T
F F T F T

Приклад 1.12. Розглянемо формулу (р→g)  (р). З табл. 1.5 робимо висновок, що задана формула фальшива в усіх інтерпретаціях, тобто заперечувана.

Таблиця 1.5

p g (р→g)

р

(р→g)  (р)

T T T F F F
T F F T T F
F T T F F F
F F T T F F


Информация о работе «Математична логіка»
Раздел: Математика
Количество знаков с пробелами: 34324
Количество таблиц: 8
Количество изображений: 0

Похожие работы

Скачать
30757
0
0

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

Скачать
29719
0
0

... (логіці, етиці і політиці) означає не що інше, як повернення до традиціоналістсько-авторитарного типу цивілізації, на що і претендував тоталітаризм XX в. 3. Загальне і відмінності формальної і діалектичної логіки В четвертій книзі “Метафізики" Арістотель ставив питання: який принцип є таким самоочевидним, що його можна покласти в основу істинної філософії. Таким самоочевидним принципом Арі ...

Скачать
17324
0
0

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

Скачать
110024
13
4

... і продукції. Виробничі потужності ТОВ «Брусилівський маслозавод» дозволяють виробляти близько 150 т масла, 30 т глазурованих сирків за рік, переробляючи приблизно 1000 кг молока за день. Основні споживачі продукції ТОВ «Брусилівський маслозавод» - населення Брусилівсьекого району та районів, що знаходяться поруч з Брусилівським, Житомирської області. .  Отже, ТОВ «Брусилівський маслозавод» – ...

0 комментариев


Наверх