Елементи логіки
Висловлення - речення, про яке стверджують, що воно є істинним або хибним, як основне поняття логіки. Правила запису висловлень у вигляді формул. Таблиці істинності формул і закони. Нормальні форми висловлень. Тавтології, суперечності та логічні висновки.
| Рубрика | Философия |
| Вид | реферат |
| Язык | украинский |
| Дата добавления | 26.02.2012 |
| Размер файла | 38,7 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
1. Елементи логіки
Рекомендована література: [3, 5, 6, 7, 9, 11, 12, 13, 14].
Цей розділ не є введенням у логіку. Тут лише представлено деякі поняття логіки, необхідні у подальшому.
1.1 Висловлення та формули
Одним з основних понять логіки є висловлення - розповідне речення, про яке можна стверджувати, що воно є або істинним, або хибним.
Звичайно, в мові існують речення, про які не можна сказати, істинні вони чи хибні. Наприклад, речення "Це речення є хибним". Якщо припустити, що воно є істинним, то з нього випливає його хибність, а якщо воно є хибним, то маємо, що воно істинне. Отже, це речення не можна розглядати як висловлення. Насправді воно є варіантом відомого парадокса брехуна: неможливо сказати, чи є істинною або хибною фраза брехуна "Я брешу".
Проте наявність таких парадоксальних речень не заважатиме нам далі, оскільки математичні знання формулюються саме висловленнями.
Хибність чи істинність висловлень може змінюватися, наприклад, у часі ("Зараз ніч"), у просторі ("Ми летимо над Африкою") тощо. Будемо дивитися на висловлення як на змінну, що може мати одне з двох значень - "хибність" або "істина", позначені 0 і 1 відповідно. Ці значення вважаються протилежними одне до одного.
Означення. Змінна з можливими значеннями "хибність" або "істина" називається пропозиційною.
Будемо позначати пропозиційні змінні великими літерами A, B, C, …, можливо, з індексами. Ці літери також називаються пропозиційними.
З висловлень можна одержувати інші висловлення, пов'язуючи їх сполучниками "та", "або", "якщо …, то …" та іншими. Ці сполучники позначаються спеціальними знаками й називаються пропозиційними зв'язками. Означимо їх.
Означення. Висловлення вигляду "Не A" записується A й називається запереченням висловлення A. Його значення є протилежним до значення A.
Означення. Висловлення вигляду "A та B" записується як A&B або AB або AB і називається кон'юнкцією висловлень A і B, або їх логічним добутком. Висловлення A і B називаються співмножниками кон'юнкції. Вона істинна, коли кожний із співмножників істинний. Якщо ж хоча б один із них хибний, то й вона хибна. Її ще записують у вигляді .
Означення. Висловлення вигляду "A або B" записується як AB і називається диз'юнкцією висловлень A і B, або логічною сумою (доданків диз'юнкції). Вона істинна, коли хоча б один із доданків істинний (можливо, і обидва). Якщо ж обидва доданки хибні, то й вона хибна. Її ще записують у вигляді .
Означення. Висловлення вигляду "Якщо A, то B" записується як AB і називається імплікацією з засновком A і висновком B. Імплікація хибна, коли засновок істинний, а висновок хибний. В усіх інших випадках вона істинна. Наприклад, висловлення "Якщо 2*2=4, то Сонце обертається навколо Землі" за цим означенням є хибним, а висловлення "Якщо 2*2=5, то Сонце обертається навколо Землі" - істинним. Імплікацію часто позначають знаком "": AB.
Зауважимо, що запис AB читається також, як "B є необхідною умовою для A", або як "A є достатньою умовою для B", або як "З A випливає B", або як "A тільки тоді, коли B", або як "B тоді, коли A".
Імплікація "З не B випливає не A", що позначається (B) (A), називається висловленням, протилежним до висловлення AB. Імплікація "З B випливає A", що позначається BA, називається висловленням, оберненим до висловлення AB.
Означення. Висловлення вигляду "A тоді й тільки тоді, коли B" записується як AB і називається еквівалентністю висловлень A і B. Вона істинна, коли значення висловлень A і B збігаються. Якщо ж вони різні, то еквівалентність хибна. Наприклад, висловлення "Якщо 2*2=5, то Сонце обертається навколо Землі" є істинним. Еквівалентність часто позначають не знаком "", а знаком "".
Зауважимо, що запис AB читається також як "B є необхідною і достатньою умовою для A", а також як "Якщо A, то B, і якщо B, то A". Заперечення еквівалентності (AB) читається як "Або A, або B". Складений сполучник "або …, або …" інколи називається "виключне або". Підкреслимо, що диз'юнкція AB відрізняється від заперечення еквівалентності (AB).
Означення. Висловлення записують у вигляді формул за такими правилами:
1) пропозиційна літера є формулою;
2) якщо X і Y - формули, то (X), (XY), (XY), (XY), (XY) також є формулами;
3) інших формул немає.
За цими правилами, наприклад, (AB), ( (AB) & ( (AB))) є формулами, ABC - ні. Далі ми розглянемо узгодження, які дозволяють скорочувати запис формул. Зокрема, ці узгодження дозволяють розглядати ABC як формулу. Тут лише зауважимо, що можна не записувати зовнішні дужки формул, наприклад, писати XY.
Задачі
1.1 Записати висловлення у вигляді формули, позначивши літерами атомарні висловлення, тобто не побудовані з інших висловлень:
логіка висловлення тавтологія суперечність
Якщо собака гавкає, то господар не спить, і якщо господар не спить, то собака гавкає.
Студент добре складає іспит тоді й тільки тоді, коли добре працює в семестрі.
Або Петро піде на заняття, і Дмитро туди не піде, або Петро не піде на заняття, і Дмитро відмінно проведе час.
Необхідна й достатня умова для щастя студента складається в тім, щоб пити пиво, багато спати і насолоджуватися музикою.
Іван дивиться телевізор тільки в тому випадку, коли там показують бойовик.
Іван дивиться телевізор тоді, коли там показують бойовик.
Корінь із цілого числа є або цілим, або ірраціональним.
Для того, щоб X було непарним, достатньо, щоб X було простим.
Необхідною умовою того, що послідовність збігається, є її обмеженість.
1.2 Таблиці істинності формул і закони
Формула є словом, тобто послідовністю символів - імен пропозиційних змінних, знаків зв'язок і дужок. Це слово має певну структуру, обмежену правилами побудови формул. Підслово цього слова, яке є формулою, називається підформулою. Наприклад, у формулі ( (AB) & ( (AB))) є підформули A, B, (AB), (AB), ( (AB)).
Формула, що позначає висловлення, складене з інших, простіших, має значення, яке залежить від значень цих складових висловлень. Для його обчислення спочатку кожній пропозиційній змінній ставиться у відповідність одне зі значень "хибність" чи "істина" (0 чи 1). Далі за означеннями пропозиційних зв'язок обчислюється значення підформул, починаючи від найпростіших і закінчуючи всією формулою. Значення формул з однією двомісною зв'язкою при всіх можливих наборах значень змінних наведено в таблиці:
|
A B |
AB |
AB |
AB |
AB |
|
|
0 0 |
0 |
0 |
1 |
1 |
|
|
0 1 |
0 |
1 |
1 |
0 |
|
|
1 0 |
0 |
1 |
0 |
0 |
|
|
1 1 |
1 |
1 |
1 |
1 |
Обчислимо значення формули, наприклад, (AB) & (BA) при всіх можливих наборах значень змінних A і B. Обчислення подамо такою таблицею:
|
A B |
AB |
BA |
(AB) & (BA) |
|
|
0 0 |
1 |
1 |
1 |
|
|
0 1 |
1 |
0 |
0 |
|
|
1 0 |
0 |
1 |
0 |
|
|
1 1 |
1 |
1 |
1 |
Таблиці, в яких представлено залежність значень формул від пропозиційних змінних, називаються таблицями істинності.
Розглянемо узгодження, які дозволяють скорочувати запис формул. Пропозиційні зв'язки упорядковуються за "силою тяжіння до формул" подібно до знаків арифметичних операцій. Всі розуміють, що вираз 1+23 позначає суму 1 і 23, а не добуток 1+2 і 3, тобто знак множення "притягується" сильніше за знак додавання. Зв'язка вважається найсильнішою, тобто AB є скороченням від (A) B, а не від (AB). Далі за спаданням "сили тяжіння" двомісні зв'язки ідуть у такому порядку: &, , , . Отже, формулу ABC можна розглядати, як скорочений запис формули A (BC), а формулу ABCA - як A (B (CA)).
Всі двомісні зв'язки мають властивість лівобічного зв'язування. Це означає, що якщо праворуч і ліворуч від підформули записано без дужок знаки двомісних зв'язок, "сила тяжіння" яких однакова, то першою до підформули застосовується ліва з них. Наприклад, ABC є скороченим записом формули (AB) C.
Означення. Дві формули називаються еквівалентними, або рівносильними, якщо приймають однакові значення при всіх можливих значеннях пропозиційних змінних. Рівносильність формул позначається знаком і в логіці називається законом.
Наприклад, неважко переконатися, що за довільних формул A, B, C наступні рівносильності є законами (праворуч указано назви деяких з них):
AB BA, AB BA - закони комутативності
A (BC) (AB) C, A (BC) (AB) C - закони асоціативності
A (BC) (AB) (AC), A (BC) (AB) (AC) - закони дистрибутивності кон'юнкції відносно диз'юнкції та диз'юнкції відносно кон'юнкції
AA A, AA A - закони ідемпотентності
A (AB) A, A (AB) A
(AB) AB, (AB) AB - закони Де Моргана
A A - закон подвійного заперечення
A0 0, A1 A, A0 A, A1 1 - закони поглинання
AA 1 - закон виключеного третього
AA 0 - закон суперечності
AB BA - закон контрапозиції
Корисно також пам'ятати ще два закони:
(12) AB AB
(13) AB (AB) (BA).
На законах грунтуються так звані рівносильні перетворення формул, коли формула або її підформула заміняється на рівносильну їй. В результаті одержується формула, рівносильна початковій. Такі перетворення бувають потрібні для спрощення формул. Наприклад, формула A (AB) має рівносильні формули A (AB), A (AB), (AA) B, AB, що одержуються послідовним застосуванням законів (12), (7), (2), (4).
Задачі
1.2 Побудувати таблицю істинності формули:
(AB) (AAB);
(AB);
AAB;
(AB) AB
A (BA) (BAB);
(A (BA)) A;
(AB) (BA)
(AB) (BA)
( (AB) B) A;
(AB) C;
A (BC);
(AB) (BC);
(AB) C;
A (BC);
(AB) ( (BC) (AC))
(CAB) ( (AB) C).
1.3 Довести закон:
(AA) A
A (BC) (AB) C;
A (BC) (AB) C;
A (BC) (AB) (AC);
A (BC) (AB) (AC);
(AB) AB;
(AB) AB;
AB BA;
AB AB;
AB (AB) (BA);
AB (AB) (AB) AB;
AAB AB;
(AB) C A (BC);
1.3 Нормальні форми висловлень
Розглянемо два різновиди формул, що мають певні структурні особливості. Саме структура цих формул зумовлює їх використання у таких важливих галузях застосування математичної логіки, як автоматизація доведення тверджень і логічне програмування.
Закони (2) стверджують асоціативність зв'язок кон'юнкції. Звідси формула вигляду ( (… ( (A1A2) A3) …) An) має еквівалентний запис A1A2A3…An. Формула в такому записі називається кон'юнкцією формул A1, A2, A3, …, An.
Означення. Елементарною кон'юнкцією називається кон'юнкція формул, кожна з яких є або пропозиційною змінною, або запереченням такої. Наприклад, A1A2A3.
Означення. Диз'юнктивною нормальною формою (скорочено ДНФ) називається диз'юнкція елементарних кон'юнкцій. Наприклад, формула ABBCD. Зауважимо, що її структуру краще видно в записі ABBCD або в записі .
Будь-яка формула може бути перетворена до ДНФ. Ми не будемо доводити це твердження, а лише опишемо потрібні рівносильні перетворення. Застосуванням законів (13) і (12) можна позбутися зв'язок і , тобто перетворити формулу до рівносильної, у якій є лише зв'язки , і . Далі, якщо у формулі є заперечення диз'юнкцій чи кон'юнкцій, то вони "спускаються" до пропозиційних змінних застосуванням законів Де Моргана (6). Далі, якщо у формулі є множники-диз'юнкції, то їх можна позбутися застосуванням першого з законів дистрибутивності (3). В результаті всі множники у кон'юнкціях формули є елементарними, і вона являє собою ДНФ. Застосування законів (1), (2), (4), (5), (7) - (10) може скоротити цей процес.
Приклад. Розглянемо перетворення (AB) (CB). Після знаків у дужках указано номери законів, застосованих при черговому перетворенні:
(AB) (BC) (13,12)
( (AB) (CB)) ( (CB) (AB)) (6, 7,2)
(ABCB) (BCAB) (3)
ABBCABAABBCBCCACB
BBCBABB (1, 4, 9,8)
ABCACBCBAB (5)
ABCACB
За законами (2) зв'язки диз'юнкції також асоціативні, звідки формули ( (… ( (A1A2) A3) …) An) і A1A2A3…An також є еквівалентними. Остання з них називається диз'юнкцією формул A1, A2, A3, …, An.
Означення. Елементарною диз'юнкцією називається диз'юнкція формул, кожна з яких є або пропозиційною змінною, або запереченням такої. Наприклад, A1A2A3.
Означення. Кон'юнктивною нормальною формою (скорочено КНФ) називається кон'юнкція елементарних диз'юнкцій. Наприклад, формула (AB) (BCD), яку можна подати також у вигляді .
Будь-яка формула перетворюється до рівносильної їй КНФ з використанням тих самих законів, тільки замість першого з законів дистрибутивності (3) вживається другий: A (BC) (AB) (AC).
Приклад. Розглянемо перетворення формули (AB) (CB) після одержання формули (ABCB) (BCAB):
(ABCB) (BCAB) (3)
(ABC) (ABB) (BCA) (BCB) (3)
(AC) (BC) (AB) (BB) (BA) (CA)
(BB) (CB) (9)
(AC) (BC) (AB) (BA) (CA) (CB)
Задачі
1.4 Перетворити формулу до ДНФ і КНФ (див. відповідний варіант задачі 1.2)
1.4 Тавтології, суперечності та логічні висновки
Означення. Формула називається тотожньо істинною, або тавтологією, якщо має значення 1 при всіх можливих значеннях пропозиційних змінних.
Наприклад, AA чи (AB) (BA). Неважко також переконатися, що заміною знаків на зв'язку у законах (1) - (13), наведених у п.1.1, одержуються саме тавтології.
Тавтології характерні тим, що коли всі входження тієї самої літери замінити на будь-яке, але одне й те саме висловлення, то нове висловлення буде істинним. Наприклад, підставимо у тавтологію ( (AB) B) A замість літери A висловлення "світить сонце", а замість літери B - "світять зорі". Одержане висловлення "Якщо світить сонце або світять зорі, і не світять зорі, то світить сонце" є істинним. Підкреслимо, що сама по собі структура цього висловлення вже забезпечує його істинність.
Неважко переконатися, що якщо тавтологіями є деяка формула X і формула XY, то Y також є тавтологією.
Означення. Формула називається тотожньо хибною, або суперечністю, якщо має значення 0 при всіх можливих значеннях пропозиційних змінних.
Одним із характерних прикладів суперечності є висловлення AA. Ця суперечність використовується у доведенні тверджень вигляду AB методом "від супротивного". Припускають істинність заперечення (AB), тобто істинність AB. З істинності B виводять A, одержуючи суперечність AA. Вона свідчить про хибність AB, тобто істинність AB.
Зауважимо, що для доведення істинності AB достатньо з B вивести A, тобто довести істинність протилежного твердження BA. Адже за законом контрапозиції (11) AB BA
Очевидно, що заперечення будь-якої тавтології є суперечністю, і навпаки. На відміну від тавтологій, підстановка висловлень у суперечності породжує хибні висловлення.
Тепер розглянемо поняття логічного висновку. У математиці, як і у звичайному житті, доводиться з'ясовувати, чи випливає деяке твердження з одного або кількох інших, тобто чи є це твердження їх логічним висновком.
Приклад. Припустимо, що купівельна спроможність грошей падає, якщо зростають податки, і що люди незадоволені, коли падає купівельна спроможність грошей. Припустимо також, що податки зростають. Звідси можна дійти висновку, що люди незадоволені.
Для цього позначимо висловлення літерами:
A - "податки зростають",
B - "купівельна спроможність грошей падає",
C - "люди незадоволені".
Припущення прикладу висловимо формулою:
(AB) (BC) A.
Доведемо, за істинності такої умови істинним буде висловлення C. Перетворимо (AB) (BC) A до ДНФ:
(AB) (BC) A (AB) (BC) A A (AB) (BC)
(AA) (AB) (BC) (AB) (BC)
(ABB) (ABC) ABC.
Отже, маємо, що істинною є формула ABC. Але вона істинна лише тоді, коли кожний співмножник істинний. Звідси висловлення C є істинним.
Таким чином, з істинності формул (AB), (BC) і A випливає істинність C. У такому випадку C називається логічним висновком цих формул.
Означення. Формула Y називається логічним висновком формул X1, X2, …, Xn, якщо з істинності X1X2…Xn випливає істинність формули Y. Формули X1, X2, …, Xn називаються засновками Y.
Перевірити, чи є одна формула логічним висновком інших, можна за допомогою порівняння таблиць істинності цієї формули та кон'юнкції інших. Але можна діяти зовсім іншим способом на основі двох наступних тверджень.
Теорема 1. Формула Y є логічним висновком формул X1, X2, …, Xn тоді й тільки тоді, коли формула (X1X2…Xn) Y є тавтологією.
Доведення.1 (Необхідність). Припустимо, що формула Y є логічним висновком формул X1, X2, …, Xn. Якщо за деяких значень літер у формулах X1, X2, …, Xn хоча б одна з них хибна, то за означенням імплікації (X1X2…Xn) Y істинна. Якщо ж за деяких значень літер у формулах X1, X2, …, Xn всі вони істинні, X1X2…Xn також істинна. Але формула Y є логічним висновком формул X1, X2, …, Xn, тому вона також істинна. Тоді істинна і формула (X1X2…Xn) Y. Отже, за будь-яких значень літер (X1X2…Xn) Y істинна, тобто є тавтологією.
2 (Достатність). Припустимо, що (X1X2…Xn) Y є тавтологією. Тоді якщо за якихось значень літер у формулах X1, X2, …, Xn всі вони істинні, то Y також істинна, тобто є їх логічним висновком.
Теорема 2. Формула Y є логічним висновком формул X1, X2, …, Xn тоді й тільки тоді, коли формула (X1X2…XnY) є суперечністю.
Доведення. За теоремою 1, формула Y є логічним висновком формул X1, X2, …, Xn тоді й тільки тоді, коли формула (X1X2…Xn) Y є тавтологією. Звідси Y є логічним висновком формул X1, X2, …, Xn тоді й тільки тоді, коли заперечення ( (X1X2…Xn) Y) є суперечністю. Але
( (X1X2…Xn) Y) ( (X1X2…Xn) Y)
( (X1X2…Xn)) Y X1X2…XnY.
Таким чином, твердження теореми істинне.
Розглянемо приклад застосування наведених теорем. Доведемо, що формула B є логічним висновком формул AB і A. Перетворимо формулу (AB) AB:
(AB) AB (AB) AB (AAB) (BAB) 00 0.
Отже, формула (AB) AB суперечлива, і за теоремою 2 формула B є логічним висновком формул AB і A.
Той факт, що формула B є логічним висновком формул AB і A, відіграє в математиці дуже важливу роль. Він дозволяє з уже відомих істинних тверджень AB і A одержати нове істинне твердження B. Зауважимо, що такий спосіб одержання, або виведення нових тверджень у математичній логіці є одним із основних. Таке виведення задається спеціальним правилом виведення, яке має вигляд і назву modus ponens (правило відокремлення). Воно дозволяє одержати висновок B твердження AB як окреме висловлення, тобто відокремити його вид засновку A. У математичній логіці існують і інші правила виведення, але тут ми їх не розглядаємо.
Підіб'ємо невеличкий неформальний підсумок. Ми познайомилися з двома принципово різними способами одержання нових висловлень. Перший полягає в тому, що ми будуємо складні висловлення з простіших за допомогою логічних зв'язок, а також "перебудовуємо" їх, виконуючи рівносильні перетворення на основі законів. Описані способи побудови та перетворення висловлень складають основу алгебри висловлень.
Другий спосіб одержання нових істинних висловлень полягає в застосуванні згаданих правил виведення до вже відомих істинних висловлень. При цьому формулюється система висловлень-тавтологій, що складає основу для виведення інших. Вони називаються аксіомами, а висловлення, що виводяться, - теоремами. Прикладом аксіоми може служити висловлення AA, яке називається законом виключеного третього. Такий спосіб породження висловлень називається численням висловлень.
Підкреслимо ще раз, що в цьому розділі нашою метою є лише знайомство з основними поняттями і мовою позначень логіки, тому ми не торкаємося її суттєвих питань. Вони розкриваються у багатьох джерелах (див. список рекомендованої літератури).
Задачі
1.5 Указати, чи є формула тавтологією, суперечністю або ні тим, ні іншим:
(BA) (AB);
( (AB) A) A;
A (BAB)
A (BA);
(AB) ( (AB) A)
(A (BC)) (B (AC));
(A (BC)) ( (AB) (AC));
(BA)) ( (BA) B);
(BC) ( (AB) (AC));
( (AB) (AC) (BC)) C;
(A (BC)) (ABC);
(BC) (ABAC);
(AB) ( (AC) (BC));
(AB) ( (BC) (AC));
(AC) ( (BC) (ABC));
1.6. Припустимо, що якщо парламент не приймає нові закони, то страйк гірників не буде закінчено, якщо тільки він не триває довше року. Припустимо, що парламент відмовляється працювати, а страйк тільки-но розпочався. Чи закінчиться страйк?
1.7 Припустимо, що ми можемо проводити такі хімічні реакції:
MgO+H2 Mg+H2O,
C+O2 CO2,CO2+H2O H2CO3.
Припустимо, що у нас є деяка кількість MgO, H2, O2 і C. Чи можемо ми одержати H2CO3?
1.8 Довести, що висловлення "Петро добре вчиться, якщо тільки його дівчина йому допомагає" є логічним висновком висловлення "Петро вчиться погано, якщо неправда, що він здібний і його дівчина йому допомагає".
1.9 Припустимо, що якщо парламент не приймає нових законів, то страйк не буде закінчено, крім випадку, коли він триває більше року й міністр іде у відставку. Припустимо також, що парламент не діє, страйк триває і міністр не йде у відставку. Чи тривав страйк більше року?
1.10 Висловлення A: "Якщо президент не має авторитету або не бере на себе відповідальність, то заворушення триватимуть доти, поки учасникам заворушень це не набридне і влада не почне примирних дій".
Висловлення B: "Якщо президент не бере на себе відповідальність і учасникам заворушень це не набридне, то заворушення триватимуть".
Довести, що висловлення B є логічним висновком висловлення A.
1.11 Припустимо, що:
1) якщо Петро не зустрів учора Дмитра, то або Дмитро розбив вікно, або Петро бреше;
2) якщо Дмитро не розбив вікно, то Петро не зустрів учора Дмитра, і вікно було розбито сьогодні;
3) якщо вікно було розбито сьогодні, то або його розбив Дмитро, або Петро бреше.
Чи є логічним висновком наведених припущень твердження про те, що Дмитро розбив вікно?
1.12 Припустимо, що:
1) якщо інвестиції не збільшаться, то зростуть урядові витрати або виникне масове безробіття;
2) якщо урядові витрати не зростуть, то податки буде знижено;
3) якщо податки буде знижено і інвестиції не збільшаться, то масове безробіття не виникне.
Чи є логічним висновком наведених припущень твердження про те, що урядові витрати зростуть?
1.13. Перевірити, чи не є суперечністю кон'юнкція наступних висловлень:
1) або Петро спав, або, якщо Дмитро розбив вікно, то птах був порятований;
2) якщо Петро спав, то Дмитро не розбив вікно;
3) якщо птах був порятований, то Дмитро розбив вікно.
1.14. Перевірити, чи не є суперечністю кон'юнкція наступних висловлень:
1) якщо Петро спав або Дмитро розбив вікно, то або птах був порятований, або Федір не прийшов;
2) птах був порятований тоді й тільки тоді, коли Петро спав і Федір прийшов;
3) якщо Дмитро розбив вікно, то або птах не був порятований, або Петро спав;
4) або Федір прийшов, або птах був порятований і Дмитро розбив вікно.
1.5 Неформальне знайомство з кванторами
У математиці, як і у повсякденному житті, виникають твердження зі специфічною структурою. Ця структура робить можливими міркування, які не можна відтворити виведенням висловлень. Класичним прикладом таких міркувань є:
Кожна людина смертна.
Сократ - людина.
Звідси випливає, що Сократ смертний.
Очевидно, що висловлення "Сократ смертний" не є логічним висновком засновків "Кожна людина смертна" і "Сократ - людина". Проте коректність наведених міркувань ні в кого не викликає сумніву. Очевидно, що вона зумовлена якимсь особливим змістом слова "кожна".
Введемо додаткові позначення. Нехай 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) (znxn+yn)).
Задачі
1.15. Записати у вигляді формули з кванторами та пропозиційними зв'язками наступне речення:
Кожне раціональне число є дійсним числом.
Деяке дійсне число є раціональним числом.
Не кожне дійсне число є раціональним числом.
Усі риби, крім акул, ставляться добре до людей.
Не всі птахи можуть літати.
Жодний продавець старих автомобілів не купує старий автомобіль для себе.
Деякі люди, що купують старі автомобілі, є людьми нечесними.
Або кожний кохає кого-небудь, і жодний не кохає всіх, або дехто кохає всіх, і дехто не кохає нікого.
Деякі люди дотепні тільки тоді, коли напідпитку.
Жодний політикан не є чесним.
Якщо хтось може це зробити, то й Петро може.
Кожний, хто має впертість, може вивчити логіку.
Ви можете дурити декого весь час, ви можете дурити всіх деякий час, але ви не можете дурити всіх весь час.
З того, що кожний розумний філософ є циніком і лише жінки є розумними філософами, випливає, що, якщо існують розумні філософи, то деякі з жінок є циніками.
1.16. З'ясувати, чи є наступне твердження істинним:
( (x P (x)) (x Q (x))) (x (P (x) Q (x)));
( (x P (x)) (x Q (x))) (x (P (x) Q (x)));
(x (P (x) Q (x))) ( (x P (x)) (x Q (x)));
( (x P (x)) (x Q (x))) (x (P (x) Q (x)));
(x (P (x) Q (x))) ( (x P (x)) (x Q (x)));
(x (P (x) Q (x))) ( (x P (x)) (x Q (x)));
(x (P (x) Q (x))) ( (x P (x)) (x Q (x)));
( (x P (x)) (x Q (x))) (x (P (x) Q (x)));
(x (P (x) Q (x))) ( (x P (x)) (x Q (x)));
(x (P (x) Q (x))) ( (x P (x)) (x Q (x)));
( (x P (x)) (x Q (x))) (x (P (x) Q (x)));
(x (P (x) Q (x))) ( (x P (x)) (x Q (x)));
(x (P (x) Q (x))) ( (x P (x)) (x Q (x)));
( (x P (x)) (x Q (x))) (x (P (x) Q (x)));
(x (P (x) Q (x))) ( (x P (x)) (x Q (x)));
(x (P (x) Q (x))) ( (x P (x)) (x Q (x)));
( (x P (x)) (x Q (x))) (x (P (x) Q (x)));
(x (P (x) Q (x))) ( (x P (x)) (x Q (x)));
1.17. Записати у вигляді формули з кванторами та пропозиційними зв'язками наступне речення:
Немає колес, які б підходили до всіх марок автомобілів.
Кожне колесо підходить до якоїсь марки автомобілів.
При будь-яких натуральних x, y, z справджується, що якщо x ділить y, y ділить z, то x ділить z.
При будь-яких натуральних x, y справджується, що якщо x ділить y, і y ділить x, то x=y.
Через будь-які три точки простору можна провести площину.
Кожний трикутник можна вписати в коло.
Для будь-якої прямої і двох точок по один бік її можна провести коло, що дотикається прямої і проходить через ці точки.
У деякі трапеції можна вписати коло.
Будь-яку рівнобедрену трапецію можна вписати в коло.
Для будь-яких точок A, B, C і прямої l на площині істинно, що якщо точки A і B належать l, B і C належать l, то A і C належать l.
Для будь-яких натуральних x, y, z не існує натурального n>2, такого, що zn=xn+yn.
Для будь-яких натуральних z і натурального n>2 не існує x, y, таких, що zn=xn+yn.
1.18. З'ясувати, чи є наступне твердження істинним:
x y A (x, y) y x A (x, y);
x y A (x, y) y x A (x, y);
x y A (x, y) y x A (x, y);
y x A (x, y) x y A (x, y);
x y A (x, y) y x A (x, y);
(x y A (x, y)) x y A (x, y);
(x y A (x, y)) x y A (x, y);
(x y A (x, y)) x y A (x, y);
(x y A (x, y)) x y A (x, y).
Размещено на Allbest.ru
Подобные документы
Визначення поняття мислення та його форм. Типи помилок, пов'язаних з порушенням законів логіки та математики. Основні закони логіки (тотожності, суперечності, виключеного третього і достатньої підстави) як відображення основ правильного мислення.
реферат [29,7 K], добавлен 22.11.2010Мислення - розумовий процес людини, в ході якого вже з наявних знань формуються нові знання. Правильне та неправильне мислення: відповідність правилам і законам логіки, логічна необхідність висновку. Логічна помилка у софізмі. Поняття некласичної логіки.
реферат [38,1 K], добавлен 16.12.2010Досягнення попередників Аристотеля у Стародавній Греції. Вчення про істину і закони мислення, про судження, про поняття, про умовивід, про доведення, логічні помилки, модальності. Індукція та її особливе місце в логіці Аристотеля. Парадейгма й ентимема.
реферат [31,4 K], добавлен 19.03.2014Дихотомія "контекстів відкриття" і "контекстів обґрунтування". Причини непопулярності епістемічної логіки серед філософів. Слабка ефективність "сильної" раціональності та універсалістська парадигма логіки. Труднощі епістемічної логіки "другого покоління".
реферат [83,1 K], добавлен 15.12.2010Дитинство та юність Аристотеля - давньогрецького вченого-енциклопедиста, філософа і логіка, засновника класичної (формальної) логіки. Періоди творчої діяльності Аристотеля - перший античний, подорожей, другий античний. Аналіз аристотелівської логіки.
презентация [996,9 K], добавлен 14.10.2014Темпоральна логіка як розділ модальної логіки, де досліджуються темпоральні висловлювання та їх відношення в структурі міркування, історія її становлення та розвитку. Поняття та аналіз прикладів темпоральних висловлювань. Теорія можливих світів.
контрольная работа [55,8 K], добавлен 24.04.2014Поняття визначення, його сутність і особливості, гносеологічні завдання та роль у практичному пізнанні. Термін "умовивід", його тлумачення, структура та елементи. Доведення як процес думки, його етапи, структурні елементи та значення в мисленні людини.
контрольная работа [12,3 K], добавлен 17.02.2009Семіотичні категорії логіки. Показники, символи і сигнали як немовні знаки. Денотат та концепт імені. Оповідна пропозиція у формальній логіці. Таємниця гегелівської діалектичної логіки. Саморефлексія ідеології марксиста: приховані основи тоталітарності.
реферат [27,8 K], добавлен 15.06.2009Основні закони формальної логіки в діяльності вітчизняного юриста. Формування у риторів чітких суджень і обґрунтування їх доказовими даними. Підготовлення юристом логічно стрункої, добре аргументованої промови, побудування судової несуперечливої версії.
контрольная работа [16,6 K], добавлен 03.11.2014Суть та зміст логічного закону: внутрішній суттєвий, необхідний зв'язок між логічними формами у процесі побудови міркувань. Характеристика законів тотожності, виключеного третього, протиріччя, достатньої підстави. Вчення та логічні судження Аристотеля.
контрольная работа [73,4 K], добавлен 25.04.2009
