ЕЛЕМЕНТИ � МАТЕМАТИЧНОЇ � ЛОГІКИ

Лекція 5

«Математична логіка є логікою за предметом, математичною за методами»

​

​

Платон Порецький

(1846-1907)

(російській вчений-логік, українець за походженням)

​

• Що ми будемо знати ?

​

• Висловлення та операції над ними.
• Логічні закони і відношення логічного слідкування.
• Предикати. Область істинності предикатів.
• Операції над предикатами.
• Квантори.
• Теореми та їх види.
• Прями й обернені теореми. Необхідні й достатні умови.

​

АРІСТОТЕЛЬ�(384 р.-322 р. до н.е.)

• Заклав основи формальної логіки

​

• Виклав закони логічного виведення

​

• Розробив аксіоматичний метод

​

• Запропонував першу формально-аксіоматичну систему логіки - силогістику

​

• Заклав основи модальної логіки

ВІЛЬГЕЛЬМ ЛЕЙБНІЦ�(1646-1716)

• Розвинув ідею створення універсального логічного числення, яка далеко обігнала свій час
• Склав «Азбуку думок», стислий і короткий словник символів.
• Розробив ідею логічного числення.
• Розмірковування позначив буквами, складні висловлювання-формулами.
• В результаті вдалося змістовні міркування замінити формальними обчисленнями.

ДЖОРДЖ БУЛЬ�(1815-1864 гг.)

• Дж. Буль - автор «Математичний аналіз логіки»(1847г.)
• Основна робота Дж. Буля «Дослідження законів думки», в ній представлено розділ логіки - алгебра висловлювань.
• В 1844 г. Буль отримує золоту медаль за работи з математичного аналізу.

• У теорії релейно-контактних схем і в теорії автоматів

​

• У кібернетиці

​

• У лінгвістиці

​

• У економічних дослідженнях

​

• У фізіології мозку і психології

​

• Є основою, ядром

інтелектуальних

інформаційних систем

ЗАСТОСУВАННЯ МАТЕМАТИЧНОЇ ЛОГІКИ

Формальна логіка вивчає акти мислення (поняття, судження, умовиводи, доведення) з точки зору їх форми, логічної структури, абстрагуючись від конкретного змісту.

Математична логіка - наука про закони

математичного мислення.

Предметом математичної логіки є математичні теорії в цілому, які вивчаються за допомогою логіко-математичних мов.

Математична логіка вивчає способи утворення висновків з даних умов, насамперед її цікавить міркування, які використовують в математиці

​

Основні поняття логіки висловлень

Висловленням називають розповідне речення, про яке можна сказати, що воно або істинне, або хибне, але не одно й інше разом.

​

Розділ логіки, що вивчає висловлювання та їх властивості, називають пропозиційною логікою або логікою висловлювань (Аристотель понад 2300 років тому).

1. Сніг білий

2. Київ – столиця України

3. Х+1 = 4

4. І.Ньютон – відомий німецький математик

5. Котра година?

6. Читай уважно!

Приклади:

У математичній логіці висловлення вважають своєрідною змінною, яка може набувати лише одного з двох значень: «істина» або «хибність», такі змінні називають логічними змінними.

​

А= {Київ – столиця України}

В= {І.Ньютон – відомий німецький математик}

​

Якщо висловлення істинне то його можна позначати: Т, I, або 1.

​

Якщо висловлення хибне то його позначають: Х, F або 0.

Якщо задано деяку множину висловлень, то можна розглядати функцію f, областю визначення якої є ця множина, а областю значень – двоелементна множина {0,1}. Таку функцію f будемо називати функцією істинності.

​

Наприклад:

якщо А={16 ділиться на 2}, то f(А)=1.

Логічні операції над висловленнями

• Заперечення

Запереченням висловлення А називають висловлення, яке є істинним, коли висловлення А хибне, і є хибним, коли висловлення А істинне.

​

Позначається заперечення:Ā ,¬ А, ~А.

Читається:«не А», «неправильно, що А».

Наприклад:

А={5>2}, тоді Ā={5≤2}.

​

Е = {сьогодні йде дощ}, тоді Ē = {сьогодні не йде дощ}

Таблиця істинності:

Функцію, яка впорядкованим набором з чисел 1 і 0 ставить у відповідність число множини {0,1}, називають булевою функцією. Таблиця істинності задає булеву функцію.

• Кон’юнкція

Кон’юнкцією (або логічним добутком) двох висловлень А і В називають висловлення, яке є істинним, коли кожне з висловлень А і В істинне, і є хибним, коли хоча б одне з них хибне.

​

Позначається кон’юнкція: А ^ В, А& В.

Читається:«А і В», «А кон’юнкція В».

Наприклад:

А={ 5 - просте число}, В ={ 17- складне число}.

Тоді А ^ В ={ 5 - просте число і 17- складне число}.

f(А ^ В)=0.

Таблиця істинності:

• Диз’юнкція

Диз’юнкцією (або логічною сумою) двох висловлень А і В називають висловлення, яке є істинним, коли хоча б одне з висловлень А або В істинне, і є хибним, коли обидва хибні.

​

Позначається диз’юнкція: АvВ.

Читається:«А або В», «А диз’юнкція В».

Наприклад:

А={93=93}, В ={93<93}.

Тоді А v В ={93≤93}. f(А v В)=1.

Таблиця істинності:

• Імплікація

Імплікацією (або логічним слідуванням) двох висловлень А і В називають таке висловлення А В, яке є хибним тоді і тільки тоді, коли А - істинне, а В - хибне.

​

Позначається імплікація: А В, А В, А В, А > В.

​

​

Читається: «якщо А, то В», «А імплікує В», «з А випливає В».

​

Висловлення А – називається умовою імплікації, В - наслідком імплікації.

Наприклад:

А={36 ділиться на 24}, В ={36>24}. Тоді f(А В) =1,

а f(В А)=0

​

​

Таблиця істинності:

• Еквіваленція

Еквіваленцією двох висловлень А і В називається таке висловлення, яке істинне тоді і тільки тоді, коли обидва компоненти А і В однозначно істинні або однозначно хибні.

​

Позначається еквіваленція: А В, А~В.

​

Читається: « А еквівалентне В», «А тоді і тільки тоді, коли В».

​

Наприклад:

А={585 ділиться на 9}, В ={сума цифр числа 585 ділиться на 9}. Тоді f(А В)=1.

​

Таблиця істинності:

«Недостатньо мати гарний розум. Головне правильно його використовувати.»

Рене Декарт

3. Які з наведених нижче висловлень істинні, а які – хибні:

а) {вирази і тотожно рівні»};

б) {сума ділиться на 200};

в) {різниця ділиться на 7};

г) {рівняння 50х =х не має коренів};

д) {рівність 18:11=7:4 є пропорцією};

е) {якщо многокутники мають рівні периметри, то їх площі також рівні};

є) {якщо трапеція вписана в коло, то вона рівнобедрена}.

​

​

​

1. Які з наведених виразів є висловленнями? Якщо вираз є висловленням, то вказати, яким саме — істинним чи хибним.

а) 15 кратне 3, але не кратне 4.

б) Кожне дійсне число задовольняє нерівністьх²≥0.

в) Число 168 кратне 9.

г) Ця задача легка.

д) Існує найбільше просте число.

е) Рівняння x²+ 7x+ 1= 0 має хоч один дійсний корінь.

є) Розв’язати рівняння x² + 7x + 1= 0.

Самостійна робота:

ж) Кожне парне число, більше за 2, є сумою двох про­стих чисел.

з) Розкрийте підручник на сторінці 23.

к) Вчитель сказав: «Розкрийте підручник на сторінці 23».

л) Всі дійсні числа задовольняють нерівність х²≤ 9.

м) 1 є просте число.

н) Хай живе математика!

о) Якщо 3< 2, то 3² <2².

п) На дошці написано лише одне речення: «Те, що написано на дошці,- неправда».

2. Занумерувати послідовність виконання операцій у формулах:

а) A→¬B∨(¬A↔C)∧B∨C;

б) (A→¬((B∨C)∧¬D))→(¬C∨B)∧C↔¬A.

​

3. Порівняти послідовність виконання логічних операцій у формулах:

а) (A→(B→C))→((A→B)→(A→C)) і

(A→(B→C)→(A→B))→(A→C);

б) (A→B∨C)→¬(B∨C) і ¬(B∨C→¬(B∨C).

ЕЛЕМЕНТИ � МАТЕМАТИЧНОЇ � ЛОГІКИ

Логічні закони і відношення логічного слідкування

Употребляйте с пользой время,

Учиться надо по системе:

Сперва хочу вам в долг вменить

На курсы логики ходить.

Ваш ум, нетронутый доныне,

На них приучат к дисциплине,

Чтоб взял он направленья ось,

Не разбредаясь вкривь и вкось.

Гёте “Фауст”

У математичній логіці за допомогою операцій

​

​

з одних висловлень утворюють нові, складніші висловлення.

Наприклад:

.

Такі висловлення прийнято називати формулами або логічними виразами (причому кожна буква, яка позначає висловлення, також є формулою).

Порядок виконання операцій над висловленнями регулюють дужками так, як це роблять, виконуючи операції над алгебраїчними виразами.

Якщо у виразі немає дужок, то порядок виконання операцій такий:

1. заперечення,
2. кон’юнкція,
3. диз’юнкція,
4. Імплікація,
5. еквіваленція

​

Наприлад:

.

Наприклад: Складіть таблицю істинності для виразу

.

Висловлювання А і В називають логічно еквівалентними, якщо вони обидва істинні, або обидва хибні ( А=В ).

​

​

Два вирази (формули) називаються рівносильними, якщо вини при однакових значеннях букв набувають однакових логічних значень ( А В).

Важливі рівносильності:

1.

1. - закон подвійного заперечення;

2.

3.

4.

5.

6.

​

7.

• перша розподільна

властивість для ;

;

• друга розподільна

властивість для ;

Важливі рівносильності:

8.

9.

10.

11.

12.

13.

14.

​

- закон виключення третього;

Сукупність усіх висловлень разом з визначеними на ній операціями і основними властивостями цих операцій становить алгебру висловлень.

Вирази алгебри висловлень називаються тотожно істинними ( тавтологіями ) або логічними законами, якщо для будь-яких наборів значень букв, які входять до них, ці вирази набувають тільки істинних значень.

Поширені логічні закони:

1. - закон включення третього: кожне

висловлення або істинне або хибне, і

третього бути не може;

2. - закон тотожності: кожне висловлення

є логічним висновком із самого себе;

3. - закон суперечності: неправильно,

що висловлення одночасно може бути

істинним і хибним;

4. - правило висновку: висновок В з

імплікації є висновком з неї і

її умови А;

​

5. - правило заперечення умови

6. - правило силогізму

7. - правило контропозиції:

Наприклад:

Визначити істинність твердження: «Якщо трикутник рівнобедрений, то дві його сторони рівні; якщо дві сторони трикутника рівні, то два кути його рівні: отже, якщо трикутник рівнобедрений, то два кути його рівні.»

Розв’язання:

У цьому твердженні можна виділити три змінні висловлення:

А= {трикутник рівнобедрений};

В = {дві сторони трикутника рівні};

С = {два кути трикутника рівні}.

Першу умову міркування запишемо:

, другу -

і висновок –

.

Дане твердження можна записати формулою:

. Ця формула є логічним законом (6), тобто твердження логічно правильне.

1. З висловлень А і В побудувати висловлення:

і знайти значення їх істинності, якщо:

а) А = {число 14612 ділиться на 9}, В = {сума цифр числа 14612 ділиться на 9};

б) А = {діагоналі прямокутника не рівні між собою}, В = {вертикальні кули рівні};

в) А = {існують такі значення m, для яких рівняння 5х=m, не має розв’язку в Z}, В = {рівняння mх=5 має розв’язок в Q для будь-яких значень m};

Розв’язування вправ:

2. Нехай А = {зараз ранок}, В = {зараз тиха погода}, С = {зараз накрапає дощ}. Записані за допомогою формул висловлення сформулювати словами:

а)

б)

в)

​

г)

д)

​

​

1. Опрацювати записи конспекту.

2. Вивчити основні означення.

3. Виконати завдання:

№ 1: Нехай А = {Микола вміє малювати}, В = {Петро пише вірші}. Записати у вигляді формул такі висловлення:

а) Микола вміє малювати і Петро пише вірші.

б) Микола не вміє малювати або Петро пише вірші.

в) Петро не пише вірші або Микола не вміє малювати.

г) Неправильно, що Микола вміє малювати або Петро не пише вірші.

д) Якщо Петро не пише вірші, то Микола вміє малювати.

Домашнє завдання:

​

№2: Записати твердження логіко-математичною символікою і визначити істинність чи хибність їх:

1) Якщо 3219 кратне 111, то 3219 кратне 37, а якщо 3219 не кратне 37, то 3219 не кратне 111.

2. Якщо 3221 кратне 111, то 3221 кратне 37.

3) Якщо 3256 кратне 111, то 3256 кратне 37.

4) х²> 4 тоді і тільки тоді, коли х> 2 або х< -2.

5) х²> 4 тоді і тільки тоді, коли х> 2 і х< -2.

6) х²< 4 тоді і тільки тоді, коли х< 2 іх> -2.

7) х²< 4 тоді і тільки тоді, коли х< 2 або х>-2.