Символи формула Пропозиционални смятане аксиоми.
правила извод
Помислете за официална аксиоматична система, в известен смисъл адекватна Пропозиционални алгебра. Ние наричаме тази система на Пропозиционални смятане.
За изграждането на изчислението, е необходимо да се определи изчисляването на азбуката, концепцията за формула, формули, класа, наречени аксиоми, правилата за извод на смятане.
Големи букви A, B, C X, Y, Z. променливи се наричат изказвания.
Герои операции за изчисление Ù, Ú, ®, три четвърти (знак на връзка, дизюнкция и повторение отрицание).
Други символи на Пропозиционални система смятане не съдържат.
Формула в Пропозиционални смятане е определена последователност от символи. Но не всяка последователност от символи е формула. Например, последователност А → В (C →) и (А Б) не са формули. Определяне с формула в Пропозиционални смятане се определя, както следва:
1. Всеки Пропозиционални променлива е формула.
2. Ако, б имат формулата, експресията на Форма (АÙб) ,. , (аÚб), (a®b) са също формули.
Ще дефинираме клас Пропозиционални смятане първоначалните истинските формули аксиоми.
правила извод позволяват от дадена система от аксиоми да получи други верни формули на Пропозиционални смятане. Ние казваме, че една формула на Пропозиционални смятане лъжата, ако нейното отрицание е вярно. Ще означаваме истинските формули буквата R, лъжливи - F.
Основните правила на извод са два:
1) на правата на затворниците.
Ако и (a®b) - истински формули, тогава В е вярно. Тази оферта може да се запише като
2) правилото за смяна
Да предположим, че формула съдържа Пропозиционални променлива А. След това, на мястото на изказване А, когато се среща всяка формула Ь, получаване вярно формула. Това предложение е записано във формуляра.
Формулата се нарича подразбират в Пропозиционални смятане, ако тя може да бъде получена чрез прилагане на принципите на извод на аксиоми на Пропозиционални смятане. Приемане на тази формула е извлича б се записва, както следва:
Метод за получаване на формули от Пропозиционални смятане официални аксиоми нарича терминал. Официално заключение се състои от уточняват какви правила, в какъв ред и каква формула се използва за извличане на тази формула.
Ние трябва да се докаже, че формулата е постигнато ® А, т.е. А ®.
1. Пишем аксиома 2 от група I.
2. Приложете го към правилото за смяна. т.е.
3. Отбележете, че има истински формула е аксиома от група I, т.е. Ние имаме истински формули и a®b. Прилагане на принципите на извод и получаване на (® B) ® (А ®).
4. Нанесете правилото за смяна на формула, получена чрез замяна B в изявление:
5. Но. 2 е аксиома от група IV. Прилагане на формулата към получения принципите на извод. т.е. -A®A.
Твърди се, че формулата е извлича от формули б А1. А2. с. ако формула могат да бъдат получени от заключения б правило, като като първоначалните формули А1. А2. една и всички истински предложения в формула смятане. Люпимостта с формула В на формули А1. А2. записва като А1. А2. с. б.
Ако формулата е извлича от формули б А1. А2. с. изхода е формула а1 ® (а2 ® (. (на ®b).)), т.е.
дедуктивно теорема позволява да се установят различни излюпване Пропозиционални смятане формули по-прост начин, отколкото директното получаването на тези формули от аксиоми, използвайки правилата за извеждане. С приспадане теорема показва основните правила на Пропозиционални смятане:
1. Правилото на силогизма. Ако формула (a®b) и (b®g) са вярно, тогава с формула (a®g), т.е.
2. Правило пренареждане на парцели. Ако формула (A® (b®g)) е вярно, тогава формулата е вярно (b® (a®g)), т.е. ;
3. Правото на United Parcel. Ако истината е формулата (A® (b®g)), след това формулата е вярно (аÙb®g), т.е. ,
Проблеми на последователност, пълнота,
Независимост на аксиомите на Пропозиционални смятане
Използвайте алгебра изявления като определен модел на Пропозиционални смятане. Формулите на Пропозиционални смятане ще бъдат третирани като формула на Пропозиционални алгебра. За да направите това, всички писма, включени в азбуката на Пропозиционални смятане, ние приемаме, а Пропозиционални променлива, по смислен смисъл, т.е. променливи, които се стойности I и L. азбука символа Ù, Ú, ®, ¾. - ще се разбира като логическите connectives на Пропозиционални алгебра.
В този случай, следната теорема притежава.
Всички аксиоми на Пропозиционални смятане е идентично истинските формули на Пропозиционални алгебра. Всички формули подразбират от аксиомите на Пропозиционални смятане е идентично истинските формули на Пропозиционални алгебра.
Доказателството на първата част на теоремата може да се извършва чрез директна проверка.
Валидността на втората част на теоремата може да се види, като показва, че чрез прилагането на правилото за извод и правилото за смяна на идентично вярно формула на Пропозиционални алгебра, ние получаваме идентично вярно формула. По този начин, всеки подразбират в Пропозиционални смятане формула е еднакво вярно формула на Пропозиционални алгебра.
При разглеждане на някакво формално логична система, включително Пропозиционални смятане, има три проблема: последователност, пълнота, независимо изчисление система аксиоми на.
Логически смятане се счита за да бъде в съответствие, ако не се подразбират няма две формули, един от които е отрицание на другия.
последователността на проблема е, че вие трябва да разберете е това смятане последователни.
Ако изчислението може да се извлече определена формула и нейното отрицание. тогава такъв смятане е несъвместимо. Ако логично смятане е в противоречие, то е подразбират всяка формула. Това смятане, няма никаква стойност, тъй като той не може да покаже разликата между истината и лъжата.
За доказване на съответствието на логически смятане е достатъчно, за да се намери в нея най-малко един не-подразбират формула. Консистенцията на Пропозиционални смятане проблем е решен така.
Теорема I. Изчисляване на последователни изявления.
Това твърдение следва от предишната теорема. В действителност, дори - известна формула е подразбират в изявленията. Поради това е тавтология, ако тя се разглежда като значим формула на Пропозиционални алгебра. След това - на самоличността е невярно, т.е. не е постигнато за всички стойности на своите член-променливи. Следователно, и то не може да бъде изведена заедно в Пропозиционални смятане.
Така, всяка формула е подразбират в Пропозиционални смятане е еднакво вярно, ако формулата на Пропозиционални смятане счита за значима формула на Пропозиционални алгебра. Има проблем обратен.
Ще всяко идентично вярно формула на Пропозиционални алгебра да бъде получен от аксиомите на Пропозиционални смятане.
Този проблем е проблем на изчисляване на пълнотата на отчет в широкия смисъл на думата.
За всяка пълнота логично определение система в най-широкия смисъл на думата може да се формулира по следния начин: логично смятане се нарича пълна, ако всичко това в истинския смисъл на съдържание формула може да бъде получена в съответствие с правилата на аксиоми смятане.
За пълнота на Пропозиционални смятане проблем е решен положително.
Теорема II. Пропозиционални система смятане е завършена.
Не по-малко важно е да се определи пълнотата на логическата система в тесния смисъл на думата. Логически смятане се нарича пълна в тесния смисъл на думата, ако добавите към системата на underivable аксиоми в това изчисление формула прави смятане противоречива. Пропозиционални смятане е завършена в тесния смисъл на думата.
За всяка логична система има проблем за независимост на аксиоми за смятане. Нека се запитаме дали аксиома смятане изведени от останалите аксиоми, използвайки правилата за извеждане на системата. Ако е възможно, аксиомата, изходът от останалите аксиоми, може да бъде заличен от списъка на аксиоми за смятане. Аксиома, не е подразбират от останалите аксиоми, се нарича независим от тези аксиоми. Системата на аксиоми, в която няма да аксиома не е подразбират от другите, наречена независима система от аксиоми.
Този проблем е решен положително за камъни.
Теорема III. Пропозиционални система смятане аксиома е независима.
Проблемът на независимостта на логическата система смятане аксиома е много важна математическа задача, което понякога води до въпроса за подмяна на някой от нейните аксиоми отрицание. Като пример, въпросът за независимостта на Евклид пети постулат на системата за аксиоми на геометрията, въпросът за независимостта на аксиоми Zermelo система от аксиоми на теория на множествата. Тези въпроси са от голямо значение за развитието на математиката.
За определянето на предикат, обърнете внимание на следните примери.
1. Нека N - набор от естествени числа и буквата Р е посочено от свойствата на естествени числа да бъде проста. Ако X е всеки елемент от N, след това изразът "естествено число х е бърз", които могат да бъдат написани като Р (х), вече не е изказване, като истинната стойност на изявлението зависи от х. По същество Р (х) е променлива (неопределен) изявление, което става определена, когато X е заместен с конкретен елемент на Н. Например, Р (3) = 1, Р (4) = 0. С други думи, Р (х) е функция, определена на множеството на естествените числа, и да вземат само две стойности: 0 и 1.
2. Нека Z - набор от числа и P - двойки числа са собственост на един и същ знак. Тогава P (X, Y) означава "цели числа х и у имат един и същ знак." Това е несигурна предложение е уточнено дали х и у са заменени с конкретни числа. Например, Р (2,3) = 1, Р (-1,5) = 0. Несигурни изказване Р (х, у) е функция на две променливи.
3. Да А и В - множеството от точки, С - множество линии на Euclidean равнина, и Р (а, Ь, с) означава "линия в простира през точките А и В». В този пример се занимават с функция на трите променливи, където А и В приемат стойности от множество точки, и в приема стойности от множество директно Евклидово равнина.
Определение 1. предиката е функция, която показва набор от произволен характер в много, или (фалшиво, вярно).
Позовавайки се на определението за предикат като цяло.
Определение 2. Нека N = 1, N2, N3, ..., Nn> - ограничен набор от комплекти. Всяка функция P (X1, ..., Xn), който свързва с всеки комплект от п елементи 1, а2, ..., с), където AI ÎNi. всеки от елементите на булевата алгебра се нарича N-местен предикат на Н. Ni набор се нарича предмет областта на променливата XI. В променливи x1, ..., хп се наричат обект променливи. Някои от множество Ni може да съвпадат.
Ако показаната снимка набор от P (А1, А2, ... едно) е единица на записа.
и да кажа, че предикат P за набора (a1, ..., с) е вярно. Ако по същия начин (А1, ..., с) е нула, се записва
и да кажа, че предикат P за набора (a1, ..., с) е невярно.
п - местно предикат когато п = 1, се нарича в унарна
п = 2 - двукомпонентни и трикомпонентни п = 3. За всеобщност, ще се въведе понятието за 0-мерното връзка, а именно 0 местен предикат нарича Люба вярно или невярно твърдение.
Както предикати вземат стойностите на (0,1), а след това върху тях може да произвежда всички логически операции, предвидени от нас в декларациите за алгебра (-, Ù, Ú, ®, «), и ги оставете същите дефиниции. В допълнение към операциите на Пропозиционални алгебра, ние ще използваме две нови операции, които са свързани с функциите за предикатните и изрази универсалните и екзистенциални отчети.
Нека Р (х) - унарна предикат определено на набор М. Ако променливата X означава всеки член на серия т, тогава Р (х) е неопределена изказване.
Операция "възлага неопределен изявление Р (х) казва" XP (х), който гласи следното: "за всяко х е P (х)» и по дефиниция е вярно, ако и само ако P (х) е вярно за всеки елемент хÎМ. Преходът от неопределен изрази P (х) с твърдението "XP (х) се нарича операцията за поставяне на универсален квантор обект променлива х.
Операция $ възлага неопределен изявление Р (х) казва $ XP (х), който гласи следното: "има х, която държи P (х)» и по дефиниция е вярно, ако и само ако P (х) вярно за най-малко един елемент хÎМ. Преходът от неопределен изявления P (х) на изложението $ XP (х) се нарича екзистенциална операция квантор виси по предмет променлива х.
В първия случай ние казваме, че обект променлива х е свързано с предикат P (х) универсален квантор, във втория случай - екзистенциалната квантор.
Ние дефинираме операциите, свързани квантор за общия случай на п-матрични предикат P (x1, ..., хп). Операции quantifiers висящи "и в променливата $ X1 на (В общия случай на променлива XI където I =.) Свързва предикат P (x1, ..., Xn) (М-1) - местни предикати
Стойностите на истината на предикати са определени за определен набор от ценности на отделните променливи x2, ..., Xn, както следва:
По принцип, ако к Помислете за предикат L (x1, x2) - «броя, разделен на броя x1 x2», определена на множеството на естествените числа. След операцията за поставяне квантор води до следните твърдения: 1. "D x1 (x1, x2) -« за всеки x1 държи D (x1, x2) », т.е. всеки x1, разделено на x2 Този предикат се изчислява на вярно само за x2 = 1 .. 2. $ x1 (x1, x2) - «там x1, което се дели на x2». Този предикат се изчислява на вярно за всяка стойност на x2. 3. "x1" x2 D (x1, x2) - «за всеки x1 и x2 за всеки има място за делимост на x1 x2. Това твърдение е невярно. 4. $ x1 "x2 D (x1, x2) -« там x1 е разделена на всеки x2. »- фалшиво изявление.Свързани статии