WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

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

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


Реферат на тему:
"Елементи математичної логіки.
Висловлення і операції на ними"
ПЛАН
Вступ
1. Поняття математичної логіки
2. Елементи математичної логіки.
Висловлення та операції над ними
3. Булеві функції та предикати
Список використаної літератури
Вступ
Логіка - наука про закони мислення. Зародження логіки можна віднести до 6 ст. до н.е. (Фалес, Парменід, Піфагор). Загальні принципи логічних міркувань розвинув Платон. Основоположником логіки як цілісної науки є Арістотель. Саме Арістотель виклав закони логічного виведення, розробив аксіоматичний метод, запропонував першу формально-аксіоматичну систему логіки - силогістику, заклав основи модальної логіки. Після Арістотеля істотний крок в розвитку логіки зроблений тільки в 17 ст. - Г. Лейбніц (1646-1716) розвинув ідею створення універсального логічного числення, яка далеко обігнала свій час. Подальші успіхи логіки пов'язані з іменами філософів, логіків і математиків 19 та 20 ст.
Математична логіка є наукою про закони математичного мислен-ня. Предметом математичної логіки є математичні теорії в цілому, які вивчаються за допомогою логіко-математичних мов. При цьому в першу чергу цікавляться питаннями несуперечливості математичних теорій, їх розв'язності та повноти.
1. Поняття математичної логіки
Математична логіка по суті є формальною логікою, що викори-стовує математичні методи. Формальна логіка вивчає акти мислення (поняття, судження, умовиводи, доведення) з точки зору їх форми, логічної структури, абстрагуючись від конкретного змісту. Творцем формальної логіки є Арістотель, а першу завершену систему математичної логіки на базі строгої логіко-математичної мови - алгебру логіки, - запропонував Дж.Буль (1815-1864). Логіко-математичні мови і теорія їх смислу розвинуті в роботах Г.Фреге (1848-1925), який ввів поняття предикату і кванторів. Це надало можливість застосувати логіко-математичні мови до питань основ математики. Виклад цілих розділів математики на мові математичної логіки та аксіоматизація арифметики зроблені Дж.Пеано (1858-1932). Грандіозна спроба Г.Фреге та Б.Рассела (1872-1970) зведення всієї математики до логіки не досягла основної мети, але привела до створення багатого логічного апарату, без якого оформлення математичної логіки як повноцінного розділу математики було б неможливе.
На межі 19-20 ст. були відкриті парадокси, зв'язані з основними поняттями теорії множин (найвідомішими є парадокси Г.Кантора та Б.Рассела). Для виходу з кризи Л.Брауер (1881-1966) висунув інтуї-ціоністську програму, в якій запропонував відмовитися від актуаль-ної нескінченності та логічного закону виключеного третього, вважа-ючи допустимими в математиці тільки конструктивні доведення. Інший шлях запропонував Д.Гільберт (1862-1943), який в 20-х роках 20 ст. виступив з програмою обгрунтування математики на базі мате-матичної логіки. Програма Гільберта передбачала побудову формаль-но-аксіоматичних моделей (формальних систем) основних розділів математики та подальше доведення їх несуперечливості надійними фінітними засобами. Несуперечливість означає неможливість одночасного виведення деякого твердження та його заперечення. Таким чином, математична теорія, несуперечливість якої хочемо довести, стає предметом вивчення певної математичної науки, яку Д.Гільберт назвав метаматематикою, або теорією доведень. Саме з розробки Д.Гільбертом та його учнями теорії доведень на базі розвинутої в роботах Г.Фреге та Б.Рассела логічної мови починається становлення математичної логіки як самостійної математичної дисципліни.
2. Елементи математичної логіки.
Висловлення та операції над ними
Математична логіка - різновид формальної логіки, тобто науки, що вивчає умовиводи з погляду їхньої формальної будівлі.
Визначення. Висловленням називається пропозиція, до якого можливо застосувати поняття істинне чи хибне.
У математичній логіці не розглядається сам зміст висловлень, визначається тільки його чи істинність хибність, що прийнято позначати відповідно І чи Х.
Зрозуміло, що щирі і помилкові висловлення утворять відповідні безлічі. За допомогою простих висловлень можна складати більш складні, з'єднуючи прості висловлення союзами "і", "чи".
Таким чином, операції з висловленнями можна описувати за допомогою деякого математичного апарата.
Уводяться наступні логічні операції (зв'язування) над висловленнями
1) Заперечення. Запереченням висловлення Р називається висловлення, що істинно тільки тоді, коли висловлення Р помилкове.
Позначається Р чи .
Відповідність між висловленнями визначається таблицями істинності. У нашому випадку ця таблиця має вид:
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
І І І
І Х Х
Х І Х
Х Х І
За допомогою цих основних таблиць істинності можна складати таблиці істинності складних формул.
3. Булеві функції та предикати
Визначення. Булевой функцією 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) Перейменування зв'язаних перемінних. Якщо замінити зв'язану перемінну формули А інший перемінний, що не входить у цю формулу, у кванторі й усюди в області дії квантора одержуємо формулу, рівносильну А.
Числення предикатів базується на приведених вище властивостях і правилах, називаних аксіомами.
Якими б ні були формули А и В для них справедливі наступні аксіоми:
1) A ==> (B ==> A);
2) (A ==> (B ==> C)) ==> ((A ==> B) ==> (A ==> C));
3) ( B ==> A) ==> (( B ==> A) ==> B);
4) ( xi)A(xi) ==> A(xj), де формула А(хi) не містить перемінної xi.
5) A(xi) ==> ( xj)A(xj), де формула А(хi) не містить перемінної xi.
Список використаної літератури
1. Конверський А.С. Математична логіка. - К., 1998.
2. Тофтул М.Г. Логіка. - К., 1999.
3. Хоменко І.В., Алексюк І.А. Основи логіки. - К., 1996.
Loading...

 
 

Цікаве