Міністерствоосвіти і науки України
Реферат
на тему «Логікаі множини»
здисципліни «Дискретна математика»
Харків2011
Зміст
Вступ
1. Логічні операції над пропозиціями
2. Таблиця істинності
3. Тавтологія і логічна еквівалентність
4. Функції висловлювань і множини
5.Функції множин
6. Логікаквантифікаторів
Література
Вступ
Пропозиція це виcлів (твердження), який може бутиістинним або хибним – третього не дано. В цьому полягає один із фундаментальних принципівлогіки – принцип виключення третього. Істинність і хибність називаютьсялогічними значеннями пропозиції. Пропозиція «2 + 2 = 4» істинна, а «p є раціональне число» хибна.З точки зору граматики пропозиція є речення – закінчена думка. Будеморозрізняти елементарні пропозиції іскладні. Елементарній пропозиції відповідає просте речення з простими підметомі присудком. Виясняти, який з окремих елементарних висловів є істинним чихибним, не є завданням логіки. Логіка займається знаходженням логічних значеньскладних пропозицій при умові, що логічні значення складових елементарнихпропозицій відомі. Існує багато тверджень, істинність або хибність яких нікому не вдається довести.Наприклад, відома теорема Гольдбаха що «кожне парне число більше 2 є сумоюдвох простих чисел». В даному вище означенніпропозиції є великий дефект, згідно нього не завжди можна визначити, чи є данетвердження пропозицією. Наприклад, вираз «Я завжди говорю неправду».Тому інколи замість замість терміну «пропозиція» вживають більшнейтральний термін «вислів», в цьому разі не обов’язково треба знати,істинний вислів чи хибний.
1. Логічніоперації над пропозиціями
Спочатку з’ясуємо правила з’єднання висловів для одержання нових висловів.Позначимо довільні вислови p і q.
Означення 1. (Кон’юнкція)Говорять, що вислів p∧q (p і q) істинний, якщо обидва вислови p, q істинні і хибний в противномувипадку.
Приклад 1. Вислів«2 + 2 = 4» і «2 + 3 = 5» є істинним.
Приклад 2. Вислів«2 + 2 = 4» і «p є числораціональне» хибний.
Означення 2.(Диз’юнкція). Говорять, що вислів p ∨ q (p або q) хибний, якщо хоча б один з висловівp, q істинний, і хибний в противномувипадку.
Приклад 3. Вислів «2 + 2 = 2» або «1 + 3 = 5» хибний.
Приклад 4. Вислів «2 + 2 = 4» або «p є числораціональне» істинний.
Означення 3. (Заперечення) Говоримо, що p (не p) істинний, якщо p хибний, і навпаки, хибний, якщо p iстинний.
Зауваження. Вдеяких підручниках замість p вживаютьпозначення />,в залежності від зручності ми будемо користуватися обома.
Приклад 5. Заперечення вислову «2 + 2 = 4» є вислів «2 + 2 ¹ 4».
Приклад 6. Заперечення вислову «p є число раціональне» є вислів «p є число ірраціональне». Означення 4. (Імплікація). Говорять, що вислів p → q (якщо p, то q) істинний, якщо p хибний, або q iстинний, або обидва істинні і хибнийв противному випадку. Зауваження. Простіше визначити вислів p → q як хибний у випадку, коли p істинний, а q хибний. Це требарозуміти наступним чином. Якщо ми зробили хибний висновок з істинного, то нашеміркування помилкове. Але допускаємо, що істинний висновок може бути одержанийі з хибного припущення.
Приклад 7. Вислів «якщо 2+ 2 = 2», то «1 + 3 = 5» істинний, тому що вислів «2 + 2 = 2» хибний.
Приклад 8. Вислів «якщо 2 + 2 = 4», то «p є числораціональне » хибний.
Приклад 9. Вислів «якщо p є число раціональне», то «2+ 2 = 4» істинний.
Означення 5. (Еквівалентність) Говорять, що вислів p « q (p тоді і лише тоді, коли q) істинний у випадку, коли p, q істинні або хибні одночасно і хибнийв противному випадку.
Приклад 10. Вислів «2 + 2 = 4» тоді і лише тоді, коли «p є число раціональне » істинний.
Приклад 11. Вислів «2 + 2 ¹ 4» тоді і лише тоді, коли «p є число раціональне „також істинний.
2. Таблицяістинності
Якщо вжити Т “true» для позначення істинноговислову і F «false» для хибного, вище наведеніозначення можуть бути представлені у вигляді таблиці істинності «truth table»:
/>
Приклад 1Побудуємо таблицю істинності для більш складної логічної конструкції />
/>
3. Тавтологія ілогічна еквівалентність
Означення 1.Тавтологія це істинний в логічному значенні вислів.
Важко привестиприклад елементарної пропозиції, яку б можна було назвати тавтологією. Якправило це поняття характерне для складних пропозицій і означає, які б не булилогічні значення складових пропозицій, складна пропозиція завжди буде істинною,якщо вона є тавтологією. Всі можливі комбінації логічних значень складовихназиваються інтерпретаціями. Вище наведені таблиці істинності показують, що длядвох складових існує всього 4 інтерпретації. Якщо трохи подумати, то прийдемодо висновку, що три складові мають 23 = 8 інтерпретацій і взагалі, n складових мають 2n інтерпретацій. Використовуючи цейтермін можна перефразувати означення 1.1 як: тавтологія – це пропозиціяістинна при всіх інтерпретаціях її складових. Керуючись цим означенням легкодовести істинність наступних пропозицій:
Приклад 1.Вислови
/>
/>
є тавтології. Це даєможливість писати p ∧ q ∧ r без дужок, узагальнившипоняття кон’юнкції для більше ніж двохвисловів.
Приклад 2. Вислови
/>
/>
є тавтології. Це даєможливість писати p Ú q Ú r без дужок, узагальнивши поняття диз’юнкції для більше ніж двох висловів.
Приклад 3. Вислів p ∨ p є тавтологія.
Приклад 4. Вислів(p → q) « (q → p) є тавтологія.
Приклад 5. Вислів(p → q) « (p ∨ q) є тавтологія.
Приклад 6. Вислів(p « q) « ((p∨q)∧(p ∧ q)) єтавтологія; про що свідчить наступна таблиця істинності:
/>
Пропонуємо студентамдовести, що наступні вислови є тавтології.
Розподільнийзакон.
(a) (p ∧ (q ∨ r)) « ((p ∧ q) ∨ (p ∧ r)); (b) (p ∨ (q ∧ r)) « ((p ∨ q) ∧ (p ∨ r)).
Закон де Моргана.
(a) (p ∧ q) « (p ∨ q); (b) (p ∨ q) « (p ∧ q).
Правила виводу.
(a) (MODUS PONENS) (p ∧ (p → q)) → q;
(b) (MODUS TOLLENS) ((p → q) ∧ q) → p;
(c) (SYLLOGISM) ((p → q) ∧ (q → r)) → (p → r).
Всі ці закони зточки зору логіки є тавтології, що можна легко довести за допомогою таблиціістинності.
Означення 1.Говорять, що вислови p і q логічно еквівалентні, якщо вислів p « q є тавтологія.
Приклад 7.Вислови p → q і q → p логічно еквівалентні. Останнійвислів називають контра позицією першого.
Зауваження.Вислови p → q і q → p не є логічно еквівалентними.Останній називається обернений до першого.
4. Функції висловлювань і множини
В багатьох випадках мивживаємо вислови типу «x є парнечисло», що містятьодну або декілька змінних. Ми будемо називати їх функціями висловлювань абопропозицій. Внаведеному прикладі вислів є істинний для одних значень х і хибний для інших.Виникають наступні питання:
Які значення x допустимі?
Чи вислів єістинним при всіх допустимих значеннях x ?
При яких самедопустимих значеннях x вислів єістинним?
Щоб відповісти наці питання нам потрібно поняття множини. Нехай Р є множина і х є елемент цієїмножини. Цей факт позначають x ∈ P. Елементи множини можна задати двома способами:
· Перечисленням, наприклад {1, 2, 3}означає множину,що складається з чисел 1,2, 3 і нічогобільше;
· Визначеннямвластивості (функції висловлювань p(x)). В цьому випадку важливовизначити множинуU допустимих значень x. Тодіможемо написати
P = {x: x ∈ U і p(x) істинно} або, просто, P = {x: p(x)}.
Множина безжодного елемента називається пустою і позначається Æ.
N = {1, 2, 3, 4, 5, ...}називаєтьсямножиною натуральних чисел.
Z = {… ,-2,-1, 0, 1,2,… .} називається множиною цілихчисел.
{x: x ∈ N і -2
{x: x ∈ Z і -2
{x: x ∈ N і -1
5. Функції множин
Припустимо, щофункції висловів p(x), q(x) відносяться до множин P, Q, тобто P = {x: p(x)} і Q = {x: q(x)}. Визначимо наступні операції надмножинами перетин P ∩ Q = {x: p(x) ∧ q(x)};
об’єднання P ∪ Q = {x: p(x) ∨ q(x)};
доповнення CP = {x: p(x)};
різницю P \ Q = {x: p(x) ∧ q(x)}.
Ці означеннялегко перефразувати у форму
P ∩ Q = {x: x ∈ P і x ∈ Q};
P ∪ Q = {x: x ∈ P або x ∈ Q};
СP = {x: x Ï P};
P \ Q = {x: x ∈ P і x Ï Q}.
Множина P є підмножиною Q і позначається P ⊆ Q або Q ⊇ P, якщокожен елемент P є елементом Q. Іншими словами, для множин P = {x: p(x)} і Q = {x: q(x)} маємо P ⊆ Q тоді і тільки тоді, коли p(x) → q(x) для всіх допустимих значень x ∈ U.
Множини P і Q називаються рівними P = Q якщо вони містять ті ж самі елементи,іншими словами, якщо P ⊆ Q і Q ⊆ P.
Множина P називається власною підмножиною Q і позначається P ⊂ Q або Q ⊃ P, якщо P ⊆ Q і P ¹ Q.
Наступні властивості функцій множинможуть бути легко доведені на основі їх аналогів в логіці.
Розподільнийзакон. Якщо P,Q,R є множини, то
(a) P ∩ (Q ∪ R) = (P ∩ Q) ∪ (P ∩ R);
(b) P ∪ (Q ∩ R) = (P ∪ Q) ∩ (P ∪ R).
логікатавтологія еквівалентність квантифікатор
Закон де Моргана. Якщо P,Q є множини, то
(a) С (P ∩ Q) = СP∪ СQ;
(b) С(P ∪ Q) = СP ∩ СQ.
Зробимо це,наприклад, для першого розподільного закону. Припустимо, що функції p(x), q(x), r(x) відносяться до множин P, Q, R, тобто P = {x: p(x)}, Q = {x: q(x)} і R = {x: r(x)}. Тоді
P ∩ (Q ∪ R) = {x: p(x) ∧ (q(x) ∨ r(x))}
(P ∩ Q) ∪ (P ∩ R) = {x: (p(x) ∧ q(x)) ∨ (p(x) ∧ r(x))}.
Припустимо, що x ∈ P ∩ (Q ∪ R). Тоді p(x) ∧ (q(x) ∨ r(x)) істинно. По першому розподільномузакону для логічних функцій маємо тавтологію
(p(x) ∧ (q(x) ∨ r(x))) « ((p(x) ∧ q(x)) ∨ (p(x) ∧ r(x)))
Звідси слідує, що(p(x) ∧ q(x)) ∨ (p(x) ∧ r(x)) істинно, так що x ∈ (P ∩ Q) ∪ (P ∩ R). А це значить, що
(1) P ∩ (Q ∪ R) ⊆ (P ∩ Q) ∪ (P ∩ R).
Тепер припустимо,що x ∈ (P ∩ Q) ∪ (P ∩ R). Тоді (p(x) ∧ q(x)) ∨ (p(x) ∧ r(x)) істинно. З першого розподільногозакону для логічних функцій слідує, що p(x) ∧ (q(x) ∨ r(x)) істинно, так що x ∈ P ∩ (Q ∪ R). Це дає
(2) (P ∩ Q) ∪ (P ∩ R) ⊆ P ∩ (Q ∪ R).
Потрібнийрезультат слідує з (1) і (2).
6. Логіка квантифікаторів
Повернемось доприкладу «x є парне число». Обмежимо x множиною цілих чисел Z. Tоді вислів «x є парне число» істинний лише для деяких x в Z. Звідси слідує, що вислів «деякі x ∈ Z парні» істинний, якщо вислів «всі x ∈ Z непарні» хибний.
В загальномувипадку розглянемо функцію вислів p(x) в якійзмінна x належить певній множині. Введемонаступні позначення для висловів
∀x, p(x) (для всіх x, p(x) істинний);
і
∃x, p(x) (для деяких x, p(x) істинний).
Символ ∀ (для всіх) і ∃ (для деяких) називаються відповідноуніверсальним квантифікатором і квантифікатором існування. Зауважимо, що зміннаx не є суттєва, вона може бути заміненабудь якою іншою, так що ∀x, p(x) і ∀y, p(y) означають одне й те ж саме.
(Теорема Лагранжа) Кожне натуральне число є сумаквадратів чотирьох цілих чисел. Це можна записати як
∀n ∈ N, ∃a, b, c, d ∈ Z, n = a2 + b2 + c2 + d2.
(Гіпотеза Гольдбаха) Кожне парне число більше 2 є сумадвох простих чисел. Це можна записати як
∀n ∈ N \ {1}, ∃p, q прості, 2n = p + q.
Ще невідомо, чи це дійсно так. Цеодна з найцікавіших з ще не розв’язаних проблем математики.
Заперечення
Розглянемозаперечення висловів з квантифікаторами. Давайте скажемо, що всі люди дурні.Дехто з вас з цим не погодиться. Можна здогадатися, що запереченням вислову ∀x, p(x) буде вислів ∃x, p(x). Тепер будемо не так категоричними іскажемо, що дехто з вас дурень. Якщо і цього разу заперечите, то запереченнямвислову ∃x, p(x) буде ∀x, p(x). Отже, маємоформули аналогічні законам де Моргана для квантіфікаторів
∀x, p(x) « ∃x, p(x)
∃x, p(x) « ∀x, p(x).
Підсумовуючисказане, заперечуючи вислів з кавантифікатрором ми змінюємо квантифікатор ізаперечуємо функцію висловів. Застосовуючи це правило послідовно декілька раз одержимо запереченнябільш складного вислову
/>
спочатку як
/>
Потім
/>
Потім
/>
і, нарешті,
/>
Запереченнямгіпотези Гольдбаха в термінах квантифікаторів буде
∃n ∈ N \ {1}, ∀p, q прості числа, 2n ¹ p + q.
Іншими словами,існує парне число більше 2, яке не є сумою двох простих чисел. Отже, щобвідкинути гіпотезу Гольдбаха досить знайти таке число. Це називається «привести контр приклад».
Література
1. Вищаматематика: Основні означення, приклади і задачі. У 2-х кн. / За ред.І.П.Васильченко. _ К: Либідь, 1994.- 280 ст.
2. ШкільМ.І. Вища математика: Підручник у 3-х кн./ Шкіль М.І., Колеснік Т.В., КотловаВ.М. – К.: Либідь, 1994.
3. Вищаматематика: Основні означення, приклади і задачі. У 2-х кн. / За ред. Г.Л.Кулініча: Підручник К.: Либідь, 1994.
4. Кудрявцев В.А., ДемидовичБ.П. Краткий курс высшей математики. — М.: Наука, 1985.
5. Карасев А.И., АксютинаЭ.М., Савельева Т.И. Курс высшей математики для экономических вузов. М.: Высшаяшкола. ч. 1,2. 1990.
6. Пискунов Н.С.Дифференциальное и интегральное исчисление. — М.: Наука, 1988, т.1,2.
7. Ильин В.Н., Позняк З.Г.Аналитическая геометрия. М.: Наука, 1984.
8. Ильин В.Н., Позняк З.Г.Линейная алгебра. М.: Наука, 1989.
9. Бахвалов С.В.Аналитическая геометрия. — М.: Высшая школа, 1992.
10. ЦубербиллерО.Н. Задачи по аналитической геометрии. М.: Высшая школа, 1984.