Логіка і множини
СОДЕРЖАНИЕ: Виключення третього як фундаментальний принцип логіки, істинність і хибність як логічні значення пропозиції. Таблиці істинності, поняття тавтології і еквівалентності. Властивості функцій множин і запереченням гіпотези Гольдбаха в термінах квантифікаторів.Міністерство освіти і науки України
Реферат
на темуЛогіка і множини
з дисципліни Дискретна математика
Харків 2011
Зміст
Вступ
1. Логічні операції над пропозиціями
2. Таблиця істинності
3. Тавтологія і логічна еквівалентність
4. Функції висловлювань і множини
5.Функції множин
6. Логіка квантифікаторів
Література
Вступ
Пропозиція це виcлів (твердження), який може бути істинним або хибним – третього не дано. В цьому полягає один із фундаментальних принципів логіки – принцип виключення третього. Істинність і хибність називаються логічними значеннями пропозиції. Пропозиція 2 + 2 = 4 істинна, а p є раціональне число хибна. З точки зору граматики пропозиція є речення – закінчена думка. Будемо розрізняти елементарні пропозиції і складні. Елементарній пропозиції відповідає просте речення з простими підметом і присудком. Виясняти, який з окремих елементарних висловів є істинним чи хибним, не є завданням логіки. Логіка займається знаходженням логічних значень складних пропозицій при умові, що логічні значення складових елементарних пропозицій відомі. Існує багато тверджень, істинність або хибність яких нікому не вдається довести. Наприклад, відома теорема Гольдбаха що кожне парне число більше 2 є сумою двох простих чисел. В даному вище означенні пропозиції є великий дефект, згідно нього не завжди можна визначити, чи є дане твердження пропозицією. Наприклад, вираз Я завжди говорю неправду. Тому інколи замість замість терміну пропозиція вживають більш нейтральний термін вислів, в цьому разі не обов’язково треба знати, істинний вислів чи хибний.
1. Логічні операції над пропозиціями
Спочатку з’ясуємо правила з’єднання висловівдля одержання нових висловів. Позначимо довільні вислови pі q.
Означення 1. (Кон’юнкція) Говорять, що вислів pq(pі q) істинний, якщо обидва вислови p, qістинні і хибний в противному випадку.
Приклад 1. Вислів 2 + 2 = 4 і 2 + 3 = 5 є істинним.
Приклад 2. Вислів 2 + 2 = 4 і pє число раціональне хибний.
Означення 2. (Диз’юнкція). Говорять, що вислів pq(pабо q) хибний, якщо хоча б один з висловів p, qістинний, і хибний в противному випадку.
Приклад 3. Вислів 2 + 2 = 2 або1 + 3 = 5 хибний.
Приклад 4. Вислів 2 + 2 = 4 або pє число раціональне істинний.
Означення 3. (Заперечення) Говоримо, щоp(неp) істинний, якщоpхибний, і навпаки, хибний, якщо piстинний.
Зауваження. В деяких підручниках замість pвживають позначення 
, в залежності від зручності ми будемо користуватися обома.
Приклад 5. Заперечення вислову 2 + 2 = 4 є вислів 2 + 2 4.
Приклад 6. Заперечення висловуpє число раціональне є вислів pє число ірраціональне. Означення 4. (Імплікація).Говорять, що вислів pq(якщо p, то q) істинний, якщо pхибний, або qiстинний, або обидва істинні і хибний в противному випадку.Зауваження. Простіше визначити вислів pqяк хибний у випадку, коли 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 для позначення істинного вислову і Ffalse для хибного, вище наведені означення можуть бути представлені у вигляді таблиці істинності truthtable:
Приклад 1 Побудуємо таблицю істинності для більш складної логічної конструкції 
3. Тавтологія і логічна еквівалентність
Означення 1. Тавтологія це істинний в логічному значенні вислів.
Важко привести приклад елементарної пропозиції, яку б можна було назвати тавтологією. Як правило це поняття характерне для складних пропозицій і означає, які б не були логічні значення складових пропозицій, складна пропозиція завжди буде істинною, якщо вона є тавтологією. Всі можливі комбінації логічних значень складових називаються інтерпретаціями. Вище наведені таблиці істинності показують, що для двох складових існує всього 4 інтерпретації. Якщо трохи подумати, то прийдемо до висновку, що три складові мають 23 = 8 інтерпретацій і взагалі, n складових мають 2n інтерпретацій. Використовуючи цей термін можна перефразувати означення 1.1 як : тавтологія – це пропозиція істинна при всіх інтерпретаціях її складових. Керуючись цим означенням легко довести істинність наступних пропозицій:
Приклад 1. Вислови
є тавтології. Це дає можливість писати pqrбез дужок, узагальнивши поняття кон’юнкції для більше ніж двох висловів.
Приклад 2. Вислови
є тавтології. Це дає можливість писати pqrбез дужок, узагальнивши поняття диз’юнкції для більше ніж двох висловів.
Приклад 3. Вислівppє тавтологія.
Приклад 4. Вислів (pq) «(qp) є тавтологія.
Приклад 5. Вислів (pq) «(pq) є тавтологія.
Приклад 6. Вислів (p«q) «((pq)(pq)) є тавтологія; про що свідчить наступна таблиця істинності:
Пропонуємо студентам довести, що наступні вислови є тавтології.
Розподільний закон.
(a) (p(qr)) «((pq) (pr)); (b) (p(qr)) «((pq) (pr)).
Закон де Моргана.
(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. Вислови pqі qpлогічно еквівалентні. Останній вислів називають контра позицією першого.
Зауваження. Вислови pqі qpне є логічно еквівалентними. Останній називається обернений до першого.
4. Функції висловлювань і множини
В багатьох випадках ми вживаємо вислови типу xє парне число, що містять одну або декілька змінних. Ми будемо називати їх функціями висловлювань або пропозицій. В наведеному прикладі вислів є істинний для одних значень х і хибний для інших. Виникають наступні питання:
Які значенняxдопустимі?
Чи вислів є істинним при всіх допустимих значеннях x?
При яких саме допустимих значеннях xвислів є істинним?
Щоб відповісти на ці питання нам потрібно поняття множини. Нехай Р є множина і х є елемент цієї множини. Цей факт позначають xP. Елементи множини можна задати двома способами:
· Перечисленням, наприклад {1, 2, 3} означає множину, що складається з чисел 1, 2, 3 і нічого більше;
· Визначенням властивості (функції висловлюваньp(x)). В цьому випадку важливо визначити множинуUдопустимих значень x. Тодіможемонаписати
P= {x: xUі p(x) істинно} або, просто , P= {x: p(x)}.
Множина без жодного елемента називається пустою і позначається .
N = {1, 2, 3, 4, 5, ...} називається множиною натуральних чисел.
Z = {. . . ,-2,-1, 0, 1, 2, . . .} називається множиною цілих чисел.
{x: xNі -2 x 2} = {1}.
{x : xZі-2 x 2} = {-1, 0, 1}.
{x: xNі-1 x 1} = .
5.Функції множин
Припустимо, що функції висловів p(x), q(x) відносяться до множин P, Q, тобто P= {x: p(x)} і Q= {x: q(x)} . Визначимо наступні операції над множинамиперетинPQ= {x: p(x) q(x)};
об’єднання PQ= {x: p(x) q(x)};
доповнення CP= {x: p(x)};
різницюP\Q= {x: p(x) q(x)}.
Ці означення легко перефразувати у форму
PQ= {x: xPіxQ};
PQ= {x: xPабоxQ};
СP= {x: xP};
P\Q= {x: xPі xQ}.
Множина Pє підмножиною Q і позначається PQабо QP, якщо кожен елемент Pє елементом Q. Іншими словами, для множин P= {x: p(x)} і Q= {x: q(x)} маємо PQтоді і тільки тоді, коли p(x) q(x) для всіх допустимих значень xU.
Множини Pі Qназиваються рівними P= Qякщо вони містять ті ж самі елементи, іншими словами, якщо PQі QP.
Множина Pназивається власною підмножиною Qі позначається PQабо QP, якщо PQі PQ.
Наступні властивості функцій множин можуть бути легко доведені на основі їх аналогів в логіці.
Розподільний закон. ЯкщоP,Q,Rє множини, то
(a) P(QR) = (PQ) (PR);
(b) P(QR) = (PQ) (PR).
логіка тавтологія еквівалентність квантифікатор
Закон де Моргана. ЯкщоP,Qє множини, то
(a) С (PQ) = СP СQ;
(b) С(PQ) = СP СQ.
Зробимо це, наприклад, для першого розподільного закону. Припустимо, що функції p(x), q(x), r(x) відносяться до множин P, Q, R, тобто P= {x: p(x)}, Q= {x: q(x)} і R= {x: r(x)}. Тоді
P(QR) = {x: p(x) (q(x) r(x))}
(PQ) (PR) = {x: (p(x) q(x)) (p(x) r(x))}.
Припустимо, що xP(QR). Тоді 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(PQ) (PR). А це значить, що
(1) P(QR) (PQ) (PR).
Тепер припустимо, що x(PQ) (PR). Тоді (p(x) q(x)) (p(x) r(x)) істинно. З першого розподільного закону для логічних функцій слідує, що p(x) (q(x) r(x)) істинно, так що xP(QR). Це дає
(2) (PQ) (PR) P(QR).
Потрібний результат слідує з (1) і (2).
6. Логіка квантифікаторів
Повернемось до прикладуxє парне число. Обмежимо xмножиною цілих чисел Z . Tоді вислів xє парне число істинний лише для деяких xвZ. Звідси слідує, що вислів деякіxZпарні істинний, якщо вислів всіxZ непарні хибний.
В загальному випадку розглянемо функцію вислів p(x) в якій змінна xналежить певній множині. Введемо наступні позначення для висловів
x, p(x) (для всіхx, p(x) істинний);
і
x, p(x) (для деякихx, p(x) істинний).
Символ (для всіх) і (для деяких) називаються відповідно універсальним квантифікатором і квантифікатором існування. Зауважимо, що змінна xне є суттєва, вона може бути замінена будь якою іншою, так що x, p(x) і y, p(y) означають одне й те ж саме.
(Теорема Лагранжа) Кожне натуральне число є сума квадратів чотирьох цілих чисел. Це можна записати як
nN, a, b, c, dZ, n= a2 + b2 + c2 + d2.
(Гіпотеза Гольдбаха) Кожне парне число більше 2 є сума двох простих чисел. Це можна записати як
nN\ {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).
Підсумовуючи сказане, заперечуючи вислів з кавантифікатрором ми змінюємо квантифікатор і заперечуємо функцію висловів. Застосовуючи це правило послідовно декілька раз одержимо заперечення більш складного вислову
спочатку як
Потім
Потім
і, нарешті,
Запереченням гіпотези Гольдбаха в термінах квантифікаторів буде
nN\ {1}, p, qпрості числа, 2np+ 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.