WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

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

ГоловнаМатематика, Геометрія, Статистика → Елементи логіки - Реферат

Елементи логіки - Реферат

формулах X1, X2, …, Xn хоча б одна з них хибна, то за означенням імплікації (X1 X2 … Xn) Y істинна. Якщо ж за деяких значень літер у формулах X1, X2, …, Xn всі вони істинні, X1 X2 … Xn також істинна. Але формула Y є логічним висновком формул X1, X2, …, Xn, тому вона також істинна. Тоді істинна і формула (X1 X2 … Xn) Y. Отже, за будь-яких значень літер (X1 X2 … Xn) Y істинна, тобто є тавтологією.
2 (Достатність). Припустимо, що (X1 X2 … Xn) Y є тавтологією. Тоді якщо за якихось значень літер у формулах X1, X2, …, Xn всі вони істинні, то Y також істинна, тобто є їх логічним висновком.
Теорема 2. Формула Y є логічним висновком формул X1, X2, …, Xn тоді й тільки тоді, коли формула (X1 X2 … Xn Y) є суперечністю.
Доведення. За теоремою 1, формула Y є логічним висновком формул X1, X2, …, Xn тоді й тільки тоді, коли формула (X1 X2 … Xn) Y є тавтологією. Звідси Y є логічним висновком формул X1, X2, …, Xn тоді й тільки тоді, коли заперечення ((X1 X2 … Xn) Y)є суперечністю. Але
((X1 X2 … Xn) Y) ( (X1 X2 … Xn) Y)
( (X1 X2 … Xn)) Y X1 X2 … Xn Y.
Таким чином, твердження теореми істинне.
Розглянемо приклад застосування наведених теорем. Доведемо, що формула B є логічним висновком формул A B і A. Перетворимо формулу (A B) A B:
(A B) A B ( A B) A B ( A A B) (B A B) 0 0 0.
Отже, формула (A B) A B суперечлива, і за теоремою 2 формула B є логічним висновком формул A B і A.
Той факт, що формула B є логічним висновком формул A B і A, відіграє в математиці дуже важливу роль. Він дозволяє з уже відомих істинних тверджень A B і A одержати нове істинне твердження B. Зауважимо, що такий спосіб одержання, або виведення нових тверджень у математичній логіці є одним із основних. Таке виведення задається спеціальним правилом виведення, яке має вигляд і назву modus ponens (правило відокремлення). Воно дозволяє одержати висновок B твердження A B як окреме висловлення, тобто відокремити його вид засновку A. У математичній логіці існують і інші правила виведення, але тут ми їх не розглядаємо.
Підіб'ємо невеличкий неформальний підсумок. Ми познайомилися з двома принципово різними способами одержання нових висловлень. Перший полягає в тому, що ми будуємо складні висловлення з простіших за допомогою логічних зв'язок, а також "перебудовуємо" їх, виконуючи рівносильні перетворення на основі законів. Описані способи побудови та перетворення висловлень складають основу алгебри висловлень.
Другий спосіб одержання нових істинних висловлень полягає в застосуванні згаданих правил виведення до вже відомих істинних висловлень. При цьому формулюється система висловлень-тавтологій, що складає основу для виведення інших. Вони називаються аксіомами, а висловлення, що виводяться, - теоремами. Прикладом аксіоми може служити висловлення A A, яке називається законом виключеного третього. Такий спосіб породження висловлень називається численням висловлень.
Підкреслимо ще раз, що в цьому розділі нашою метою є лише знайомство з основними поняттями і мовою позначень логіки, тому ми не торкаємося її суттєвих питань. Вони розкриваються у багатьох джерелах (див. список рекомендованої літератури).
4. Неформальне знайомство з кванторами
У математиці, як і у повсякденному житті, виникають твердження зі специфічною структурою. Ця структура робить можливими міркування, які не можна відтворити виведенням висловлень. Класичним прикладом таких міркувань є:
Кожна людина смертна.
Сократ - людина.
Звідси випливає, що Сократ смертний.
Очевидно, що висловлення "Сократ смертний" не є логічним висновком засновків "Кожна людина смертна" і "Сократ - людина". Проте коректність наведених міркувань ні в кого не викликає сумніву. Очевидно, що вона зумовлена якимсь особливим змістом слова "кожна".
Введемо додаткові позначення. Нехай x позначає деяку змінну, значення якої можуть мати деяку властивість P. Такі змінні називаються предметними. Висловлення "x має властивість P" позначимо P(x). Наприклад, висловлення "Ціле число x є парним" позначимо E(x). Значення такого висловлення залежить від значення цієї змінної. При x=1 висловлення E(x) хибне, при x=2 - істинне. Замість літери x можна записати її значення, наприклад, E(2).
Речення "Кожне значення x має властивість P", або "Всі значення x мають властивість P", або "Всі x мають властивість P", або "При всіх x справджується властивість P" позначимо записом x P(x). У цьому записі частина x називається квантором загальності. Слово "квантор" походить від слова "квантифікація", що означає "кількісне вираження". Продовжуючи приклад про парні числа, зауважимо, що твердження x E(x) є хибним.
Речення "Існує значення x, що має властивість P", або "Деякі значення x мають властивість P", або "При деякому значенні x справджується властивість P", або "Деякі x мають властивість P" позначимо записом x P(x). У цьому записі частина x називається квантором існування. Очевидно, що у прикладі про парні числа твердження x E(x) є істинним.
Очевидно, що
x P(x) x P(x),
причому твердження x P(x) і x P(x) нерівносильні.
Розглянемо деякі з можливих застосувань пропозиційних зв'язок до виразів із кванторами. Заперечення ( x P(x)) читається як "неістинно, що всі значення x мають властивість P", тобто як "існує значення x, що не має властивості P". Таке речення можна позначити як x P(x). Таким чином,
( x P(x)) x P(x).
Аналогічно
( x P(x)) x P(x).
Висловлення x P(x) x Q(x) читається як "всі значення x мають властивість P і всі значення x мають властивість Q", тобто "всі значення x мають властивість P і властивість Q". Таким чином,
( x P(x)) ( x Q(x)) x (P(x) Q(x)).
Висловлення x P(x) x Q(x) читається як "усі значення x мають властивість P або всі значення x мають властивість Q". З цього речення випливає, що "усі значення x мають властивість P або властивість Q", але ці два речення не рівносильні. Таким чином, x(P(x) Q(x)) є логічним висновком висловлення ( x P(x)) ( x Q(x)),тобто
(( x P(x)) ( x Q(x))) x(P(x) Q(x)),
але вони нерівносильні.
Приклад. Якщо P(x) позначає речення "x - парне число", а Q(x) - "x - непарне число", то висловлення x(P(x) Q(x)) є істинним, а ( x P(x)) ( x Q(x)) - хибним.
Насамкінець, розглянемо речення з двома й більше кванторами. Вони з'являються, коли йдеться про властивості пар, трійок тощо змінних. Наприклад, речення "При будь-якому натуральному значенні x існує значення y, таке, що x є дільником y" можна записати як
x ( y D(x, y)),
де D(x, y) позначає речення "x є дільником y".
Речення вигляду "При будь-якому значенні x справджується, що при будь-якому значенні y істинно A(x, y)" можна позначити так:
x ( y A(x, y)).
Будемо опускати дужки, записуючи, наприклад, x y D(x, y) або x y A(x, y). Останній вираз можна прочитати також, як "При будь-якому значенні x і при будь-якому значенні y істинно A(x, y)".
Аналогічно речення вигляду " При будь-якому значенні x і при будь-якому значенні y і при будь-якому значенні z істинно A(x, y, z)" можна позначити виразом
x y z A(x, y, z).
І так далі. Розглянемо, наприклад, твердження великої теореми Ферма:
Рівняння zn=xn+yn, де n - ціле число, більше 2, не має розв'язків у цілих додатних числах.
Одним із можливих записів цього твердження є такий:
x y z n ((n>2) (zn xn+yn)).
Loading...

 
 

Цікаве