Osvita.ua Вища освіта Реферати Логіка Висловлення і операції над ними. Елементи математичної логіки. Реферат
Провідні компанії та навчальні заклади Пропозиції здобуття освіти від провідних навчальних закладів України та закордону. Тільки найкращі вищі навчальні заклади, компанії, освітні курси, школи, агенції. З питань розміщення інформації звертайтесь за телефоном (044) 200-28-38.

Висловлення і операції над ними. Елементи математичної логіки. Реферат

Поняття математичної логіки. Елементи математичної логіки. Висловлення та операції над ними. Булеві функції та предикати

Логіка - наука про закони мислення. Зародження логіки можна віднести до 6 ст. до н. е. (Фалес, Парменід, Піфагор). Загальні принципи логічних міркувань розвинув Платон. Основоположником логіки як цілісної науки є Аристотель. Саме Аристотель виклав закони логічного виведення, розробив аксіоматичний метод, запропонував першу формально-аксіоматичну систему логіки - силогістику, заклав основи модальної логіки.

Після Аристотеля істотний крок в розвитку логіки зроблений тільки в 17 ст. - Г. Лейбніц (1646-1716) розвинув ідею створення універсального логічного числення, яка далеко обігнала свій час. Подальші успіхи логіки пов'язані з іменами філософів, логіків і математиків 19 та 20 ст.

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

Поняття математичної логіки

Математична логіка по суті є формальною логікою, що використовує математичні методи. Формальна логіка вивчає акти мислення (поняття, судження, умовиводи, доведення) з точки зору їх форми, логічної структури, абстрагуючись від конкретного змісту. Творцем формальної логіки є Аристотель, а першу завершену систему математичної логіки на базі строгої логіко-математичної мови - алгебру логіки, - запропонував Дж. Буль (1815-1864).

Логіко-математичні мови і теорія їх смислу розвинуті в роботах Г. Фреге (1848-1925), який ввів поняття предикату і кванторів. Це надало можливість застосувати логіко-математичні мови до питань основ математики. Виклад цілих розділів математики на мові математичної логіки та аксіоматизація арифметики зроблені Дж. Пеано (1858-1932). Грандіозна спроба Г. Фреге та Б. Рассела (1872-1970) зведення всієї математики до логіки не досягла основної мети, але привела до створення багатого логічного апарату, без якого оформлення математичної логіки як повноцінного розділу математики було б неможливе.

На межі 19-20 ст. були відкриті парадокси, зв'язані з основними поняттями теорії множин (найвідомішими є парадокси Г. Кантора та Б. Рассела). Для виходу з кризи Л. Брауер (1881-1966) висунув інтуїціоністську програму, в якій запропонував відмовитися від актуальної нескінченності та логічного закону виключеного третього, вважаючи допустимими в математиці тільки конструктивні доведення. Інший шлях запропонував Д. Гільберт (1862-1943), який в 20-х роках 20 ст. виступив з програмою обґрунтування математики на базі математичної логіки.

Програма Гільберта передбачала побудову формально-аксіоматичних моделей (формальних систем) основних розділів математики та подальше доведення їх несуперечливості надійними фінітними засобами. Несуперечливість означає неможливість одночасного виведення деякого твердження та його заперечення. Таким чином, математична теорія, несуперечливість якої хочемо довести, стає предметом вивчення певної математичної науки, яку Д. Гільберт назвав метаматематикою, або теорією доведень. Саме з розробки Д. Гільбертом та його учнями теорії доведень на базі розвинутої в роботах Г. Фреге та Б. Рассела логічної мови починається становлення математичної логіки як самостійної математичної дисципліни.

Елементи математичної логіки. Висловлення та операції над ними

Математична логіка – різновид формальної логіки, тобто науки, що вивчає умовиводи з погляду їхньої формальної будівлі.

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

У математичній логіці не розглядається сам зміст висловлень, визначається тільки його чи істинність хибність, що прийнято позначати відповідно І чи Х.

Зрозуміло, що щирі і помилкові висловлення утворять відповідні безлічі. За допомогою простих висловлень можна складати більш складні, з'єднуючи прості висловлення союзами "і", "чи".

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

Уводяться наступні логічні операції (зв'язування) над висловленнями

Заперечення. Запереченням висловлення Р називається висловлення, що істинно тільки тоді, коли висловлення Р помилкове.

Позначається Р чи .

Відповідність між висловленнями визначається таблицями істинності. У нашому випадку ця таблиця має вид:

P

 Р

І

Х

Х

І

 

2) Кон’юнкція. Кон’юнкцією двох висловлень P і Q називається висловлення, щире тоді і тільки тоді, коли щирі обоє висловлення.

Позначається P&Q чи РÙQ.

P

Q

P&Q

І

І

І

І

Х

Х

Х

І

Х

Х

Х

Х

 

3) Диз'юнкція. Диз'юнкцією двох висловлень P і Q називається висловлення, помилкове тоді і тільки тоді, коли обоє висловлення помилкові.

Позначається PÚQ.

P

Q

PÚQ

І

І

І

І

Х

І

Х

І

І

Х

Х

Х

 

4) Імплікація. Імплікацією двох висловлень P і Q називається висловлення, щире тоді і тільки тоді, коли висловлення Р щире, а Q – ложно.

Позначається PÉQ (чи РÞQ). Висловлення Р називається посилкою імплікації, а висловлення Q – наслідком.

P

Q

PÞQ

І

І

І

І

Х

Х

Х

І

І

Х

Х

І

 

5). Еквіваленція. Еквіваленцією двох висловлень P і Q називається висловлення, щире тоді і тільки тоді, коли істинності висловлень збігаються.

Позначається Р~Q чи РÛQ.

P

Q

P~Q

І

І

І

І

Х

Х

Х

І

Х

Х

Х

І

 

За допомогою цих основних таблиць істинності можна складати таблиці істинності складних формул.

Булеві функції та предикати

Визначення. Булевой функцією f (X1, X2, …, Xn) називається довільна n – місцева функція, аргументи і значення якої належать безлічі {0, 1}.

Узагалі говорячи між логічними висловленнями, логічними зв'язуваннями і булевими функціями проглядається явна аналогія. Якщо логічні функції можуть приймати значення чи істинно ложно, то для булевой функції аналогами цих значень будуть значення 0 чи 1.

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

X1

X2

  • ØX1

X1&X2

X1ÚX2

X1ÞX2

X1ÛX2

1

1

0

1

1

1

1

1

0

0

0

1

0

0

0

1

1

0

1

1

0

0

0

1

0

0

1

1

 

Поняття предикатів

Визначення. Предикатом P (x1, x2, …, xn) називається функція, перемінні якої приймають значення з деякої безлічі М, а сама функція приймає два значення: И (істина) і Х (неправда), тобто

 

Предикат від п аргументів називається п – місцевим предикатом. Висловлення вважаються нуль – місцевими предикатами.

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

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

Квантори бувають двох видів.

1) Квантор спільності. Позначається ("х) Р (х). Квантором спільності називається висловлення щире, коли Р (х) істинно для кожного елемента х з безлічі М, і помилкове – у противному випадку.

2) Квантор існування. Позначається ($х) Р (х). Квантором існування називається висловлення, щире, коли існує елемент із безлічі М, для якого Р (х) істинно, і помилкове в противному випадку.

Операцію зв'язування квантором можна застосовувати і до предикатів від більшого числа перемінних.

Для формул логіки предикатів зберігається справедливість усіх правил рівносильних перетворень логіки висловлень.

Крім того, справедливі наступні властивості:

1) Перенос квантора через заперечення.

  • Ø ("x) A (x) º ($x) ØA (x); Ø ($x) A (x) º ("x) ØA (x);

2) Винесення квантора за дужки.

($х) (А (х) & B) º ($x) A (x) & B; ("x) (A (x) & B) º ("x) A (x) & B;

($х) (А (х) Ú B) º ($x) A (x) Ú B; ("x) (A (x) Ú B) º ("x) A (x) Ú B;

3) Перестановка однойменних кванторів.

("y) ("x) A (x, y) º ("x) ("y) A (x, y); ($y) ($x) A (x, y) º ($x) ($y) A (x, y);

4) Перейменування зв'язаних перемінних. Якщо замінити зв'язану перемінну формули А інший перемінний, що не входить у цю формулу, у кванторі й усюди в області дії квантора одержуємо формулу, рівносильну А.

Числення предикатів базується на приведених вище властивостях і правилах, називаних аксіомами.

Якими б ні були формули А и В для них справедливі наступні аксіоми:

  • A Þ (B Þ A);
  • (A Þ (B Þ C)) Þ ((A Þ B) Þ (A Þ C));
  • (ØB Þ ØA) Þ ((ØB Þ A) Þ B);
  • ("xi) A (xi) Þ A (xj), де формула А (хi) не містить перемінної xi.
  • A (xi) Þ ($xj) A (xj), де формула А (хi) не містить перемінної xi.

Література

  1. Конверський А. С. Математична логіка. – К., 1998.
  2. Тофтул М. Г. Логіка. – К., 1999.
  3. Хоменко І. В., Алексюк І. А. Основи логіки. – К., 1996.


23.10.2011

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

Щоб отримувати всі публікації
від сайту «Osvita.ua»
у Facebook — натисніть «Подобається»

Osvita.ua

Дякую,
не показуйте мені це!