Закони логіки кванторние операції
Математика. Курс лекцій для студентів спеціальності Психологія
Частина 1. Елементи теорії множин і математичної логіки
закони логіки. кванторние операції
закони логіки
Квантори спільності і існування
Заперечення висловлень з кванторами
Необхідні і достатні умови
1. Закони логіки
Важливу роль в логіці грають тотожне справжні і тотожно хибні висловлювання (формули).
Формула називається тотожно істинною. якщо вона приймає значення «істина» при будь-яких значеннях висказивательной змінних, що входять в неї. Записується так:.
Формула називається тотожно хибною. якщо вона приймає значення «брехня» при всіх значеннях вхідних в неї висловлювань. Записується так:.
Приклад 1. Дано дві формули: 1.; 2.. Складіть таблиці істинності і вкажіть, які формули є тотожно істинними, які - тотожно-помилковими.
Рішення. Кожна висказивательной змінна може приймати два значення: або. Тому таблиця істинності формули повинна складатися з рядків, де - число різних висказивательной змінних у формулі.
1. Складемо для формули таблицю істинності, яка буде містити два рядки.
Порівнюючи два останніх стовпчика в таблиці істинності для формул і, зауважимо, що вони містять однакові істинності значення наших формул, причому при всіх однакових наборах значень висказивательной змінних і. Значить, формули і є рівносильними. тобто .
Равносильность формул і означає, що які б не були висловлювання і, формули і або одночасно істинні, або хибні. Іншими словами, з істинності (або хибності) однієї з них слід істинність (хибність) інший.
Нові знання про світ можна отримати, не тільки звертаючись до досвіду, а й застосовуючи логічні міркування. Правила, на підставі яких по істінностним значенням одних висловлювань робиться висновок про істиннісних значеннях інших висловлювань, називають законамімишленія або логічними законами.
(Закон подвійного заперечення)
(Закон протиріччя)
(Закон виключеного третього)
(Закон де Моргана)
(Закон де Моргана)
(Контрапозиція)
Приклад 3. Закон зняття подвійного заперечення дозволяє замінювати складне висловлювання простим висловлюванням. Наприклад, «Дві будь-які точки не можуть не належати одній прямій» () рівносильно висловом «Дві будь-які точки належать одній прямій» ().
2. Квантори спільності і існування
Квантор спільності
Розглянемо невизначений висловлювання (предикат), істинність або хибність якого залежить від значення змінної. Наприклад, пропозиція - невизначене висловлювання. Воно звертається в істинне висловлення при, а саме: «», а при стає хибним висловлюванням.
Безліч елементів, при яких невизначений висловлювання стає справжнім, називається безліччю істинності висловлювання.
Отже, щоб отримати з предікатависказиваніе. можна в невизначеному висловленні замінити змінну одним зі значень безлічі істинності. Але існує інший спосіб побудови висловлювання - за допомогою логічних операцій, які називаються кванторами. Найбільш споживані два квантора - квантор спільності і квантор існування.
Якщо невизначений висловлювання істинно для всіх елементів множини, то застосовують квантор спільності і пишуть:. При цьому невизначений висловлювання перетворюється в істинне висловлення. Квантор спільності є перевернуту букву (першу букву англійського слова All - «все»).
Запис Новомосковскется так:
для будь-якого (всякого, кожного) значення з безлічі висловлювання істинно; або
всякий (будь-який, кожен) елемент з безлічі має властивість; або
яким би не було з безлічі, висловлювання істинно.
Змінну в невизначеному висловленні називають вільної змінної (їй можна надавати різні значення з безлічі), а в висловлюванні називають змінної. пов'язаної квантором спільності.
Приклад 4. На множині натуральних чисел задана висказивательной форма: «Число кратно 5». Застосовуючи до невизначеного висловом квантор спільності, отримаємо висловлювання, яке означає: «Все натуральні числа кратні 5».
Щоб довести хибність висловлювання, тобто спростувати його, досить вказати лише один елемент, для якого воно помилкове - знайти, як кажуть, контрприклад.
Приклад 5. Визначте істинність або хибність висловлювання з квантором спільності: «У будь-якому трикутнику один з кутів прямий».
Рішення. Вислів «У будь-якому трикутнику один з кутів прямий» помилкове. Як контрпримера можна привести трикутник, у якого немає прямого кута.
Якщо невизначений висловлювання (предикат) істинно хоча б для одного елемента, то застосовують квантор існування і пишуть. При цьому невизначений висловлювання перетворюється в істинне висловлення. Квантор існування являє собою перевернуту букву (першу букву англійського слова Exists - «існує»).
Запис Новомосковскется так:
1) існує значення з безлічі таке, що це правда, або
2) для деяких значень з безлічі висловлювання істинно; або
3) хоча б одне значення з безлічі таке, що висловлювання істинно.
Змінну в невизначеному висловленні називають вільної змінної (їй можна надавати різні значення з безлічі), а в висловлюванні називають змінної. пов'язаної квантором існування.
Приклад 6. Нехай на безлічі натуральних чисел задано предикат: «Число кратно 5». Запишіть висловлювання.
Рішення. Застосовуючи квантор існування, з даного предиката можна отримати висловлювання - «Існує натуральне число, кратне 5».
Використання квантора дозволяє встановити істинність або хибність висловлювання. Висловлення істинно. коли знайдеться хоча б одне значення з безлічі, для якого висловлювання істинно, і помилково. коли для кожного значення з безлічі висловлення помилкове.
Приклад 7. Визначте істинність або хибність висловлювання з квантором існування: «Існують трикутники, в яких один з кутів прямий».
Рішення. «Існують трикутники, в яких один з кутів прямий» - справжнє висловлювання. Дійсно, можна побудувати прямокутний трикутник (більш того - не один).
Побудова висловлювань «» і «» з предиката називають логічними операціями навішування кванторів або логічними операціями зв'язування змінної.
3. Заперечення висловлень з кванторами
Нерідко доводиться будувати заперечення висловлювання, сформульованого за допомогою кванторів.
Приклад 8. Є предикат: «- прямокутний трикутник» на безлічі трикутників. Навісьте на предикат черзі квантори спільності, існування і визначте логічне значення отриманих висловлювань.
Рішення. Висловлення - «Будь-який трикутник - прямокутний» помилкове. Висловлення - «Існує прямокутний трикутник» справжнє.
Як побудувати заперечення висловлювань і?
Кожне заперечення висловлювання з кванторами можна словесно побудувати двома способами.
Перший спосіб. використовується частка «не» для всього висловлювання. Цей спосіб заперечення висловлювання символічно зображується як або, тобто проставляється риса заперечення над усім висловлюванням, включаючи квантори.
Приклад 9. Побудуйте заперечення висловлювань - «Будь-який трикутник прямокутний» і - «Існує прямокутний трикутник» з використанням частки «не» для всього висловлювання.
Рішення. Для помилкового висловлювання - «Будь-який трикутник прямокутний» отримаємо його заперечення - «Невірно, що всякий трикутник прямокутний», яке є істинним висловлюванням.
Для істинного висловлювання - «Існує прямокутний трикутник» отримаємо заперечення - «Невірно, що існує прямокутний трикутник» - хибне висловлювання.
Другий спосіб. використовується частка «не» тільки для предиката, але квантори і замінюються один на одного. Це символічно зображується, відповідно, так:
тобто проставляється риса заперечення над предикатом, а квантор замінюється квантором, і навпаки.
Приклад 10. Побудувати заперечення висловлювань - «Будь-який трикутник прямокутний» і - «Існує прямокутний трикутник» з використанням частки «не» тільки для предиката.
Рішення. Відповідно до зазначеного способом для помилкового висловлювання - «Будь-який трикутник прямокутний» отримаємо його заперечення в формі - «Існує трикутник, який не є прямокутним» - справжнє висловлювання.
Для істинного висловлювання - «Існує прямокутний трикутник» отримаємо заперечення в формі - «Всякий трикутник не є прямокутним» - хибне висловлювання.
Другий спосіб побудови заперечення висловлювання з кванторами дозволяє сформулювати наступне правило.
Правило побудови заперечення висловлювання з квантором
Якщо в висловлюванні, що містить квантори:
над предикатом поставити знак заперечення «»,
квантор спільності замінити квантором існування, або
квантор існування замінити квантором спільності,
то вийде висловлювання, що заперечує це висловлювання.
З урахуванням сформульованого правила заперечення висловлювання набуває вигляду, а заперечення висловлювання набуває вигляду.
4. Необхідні і достатні умови
У багатьох висловлюваннях і при формулюванні теорем часто використовуються слова «досить», «необхідно», «необхідно і достатньо». У чому сенс цих термінів?
Із треба.
є наслідок.
Якщо то .
«Виконується тоді. коли виконується ».
«Виконується в тому випадку. коли виконується ».
Висловлення називається достатньою умовою для висловлювання. Висловлення Новомосковскется так: «Для того щоб виконувалася, досить. щоб виконувалося ».
Висловлювання є необхідною умовою для висловлювання. Висловлення Новомосковскется так: «Для того щоб виконувалася, необхідно. щоб виконувалося ».
Приклад 11. Розглянемо висловлювання «Якщо я здав всі іспити в сесію, то перейшов на другий курс». Знайдіть достатня умова і необхідна умова.
Рішення. Висловлення - «Я склав іспити в сесію» є достатньою умовою для висловлювання - «Я перейшов на другий курс». Значить, назвати себе другокурсником ви можете лише в тому випадку, коли здасте всі іспити. Висловлення - «Я перейшов на другий курс» є лише необхідною умовою (наслідком) для висловлювання - «Я здав усі іспити в сесію».
Якщо висловлювання і такі, що і, то кожне з цих висловлювань і буде необхідним і достаточнимусловіем для іншого висловлювання.
У цьому випадку замість двох імплікацій і пишуть еквіваленцію, Новомосковський це як «тоді і тільки тоді, коли».
Приклад 12. Розглянемо теорему: «Для того щоб трикутник був рівнобедреним, необхідно і достатньо, щоб кути при основі трикутника дорівнювали». Тут висловлювання - «трикутник рівнобедрений» є необхідна і достатня умова для висловлювання - «кути при основі трикутника рівні», і навпаки.
Замість слів «необхідно і достатньо» часто вживають слова «тоді і тільки тоді», «в тому і тільки в тому випадку».
Іноді слово «умова» заміняють словом «ознака» і говорять про необхідному ознаці, або достатній ознаку, або необхідний і достатній ознаку.
У тих випадках, коли в теоремі містяться словá «необхідно і достатньо», доказ обов'язково має складатися з двох частин: 1) докази необхідності умови і 2) докази достатності умови. У такому формулюванні насправді об'єднані формулювання двох теорем: прямий і зворотній, кожна з яких потребує доказу, так як з справедливості однієї теореми не слід справедливість інший теореми.