Формула на Пропозиционални алгебра
1. Определяне и примери на формули
С помощта на логически операции, разгледани в предишния раздел, ние можем, въз основа на опростена декларация, за изграждане на нова, по-сложна. Например, въз основа на извлечения от Р. "А. С. Пушкин - български поет", Р. "Гаус - немски математик", Р. "", може да се изгради ново изявление :. "Ако Пушкин - български поет и Гаус - немски математик г." Това ново изявление има формата
Експресия (1), с изключение на специфично значение Р. С. R. отчети може да се разглежда като схема, която позволява, изхождайки от изявления R. В. R. изграждане на нови изказване. Че подобни схеми и ще се интересуват от нас днес. Те се наричат Пропозиционални алгебра. Разбира се, ние сме свикнали с малко по-различна интерпретация на термина "формула"; формула за нас - това е равнопоставеността на типа (формула района на кръг), (формула изразяване на Питагоровата теорема) и т.н. Въпреки това, изразът може да се разглежда като един вид формула - .. формула за изграждане на композиция от по-прости твърдения.
Преди да даде обща формула определение на Пропозиционални алгебра, съгласни сме, както следва. Пропозиционални променливи, които наричаме тези променливи, които могат да вземат като стойността му някакви конкретни изявления. Ние трябва да се обозначи тези променливи главни букви X, Y, Z, U, V .. или от същите букви с индекси: Представяме, в допълнение, две по-конкретни и Пропозиционални променливи и А; а не на първата, можете да заместите всеки вярно твърдение, вместо втори - който и да е фалшива.
Пълното описание на формулите за концепция дава следните споразумения:
1 °. Всеки отделен Пропозиционални променлива е формула.
2 °. Ако - две формули, експресията. Те също са формули.
3 °. Той няма други формули, различни от тези, които са получени чрез прилагане на определен брой пъти от претенции 1 ° и 2 °.
Например, формулата е следните изрази: и т.н.
За по-голяма яснота, ние говорим за примери на изрази, които не са формули.
Фактът, че не можем да разпознаем формулата на последното писмено изрази, може да доведе до най-напред озадачаващо. Въпреки това, ако следвате горното определение, изразът - не е формула; да стане формула, липсва скоби, тъй като според п. ° 2, формулата трябва да бъде израз. вместо това. Разликата между изрази и става особено важно, ако включва експресията като съставна част на по-сложна формула: сравнение, например, експресия. Това е формула с (не формула); не е ясно как да се тълкува втория израз (който експлоатация следва: след или след).
По този начин, записването на външните скоби във формулата ще бъде разгледана по избор, освен ако тази формула не съдържа елемент на една по-сложна формула.
2. Истината маси за формули
Разглежда всеки формула на Пропозиционални алгебра, например. Ние означават това намаление формула F (X, Y, Z). Стойността на истината с формула F (X, Y, Z) е напълно определя от стойностите на истинността на променливи X, Y, Z. Това обстоятелство позволява да се изготви таблица дава стойност истина за F (X, Y, Z) в зависимост от стойностите на истината за X, Y, Z. Това трябва да се състои от четири колони: трите - за променливите X, Y, Z, и една - за самата формула. Тъй като всяка от променливите X, Y, Z може да приеме две стойности (1 или 0), след това се утроява X, Y, Z, получени различни функции. Това означава, че на масата трябва да има 8 реда. За да се запълни последната колона на таблица заместващи стойности Х, Y и Z във формула F (X, Y, Z). Например, ако X = 1, Y = 1, Z = 1, имаме
когато X = 1, Y = 1, Z = 0 намираме
.. т.н. Като резултат, пълнене получаване на следната таблица:
Като цяло, за всеки формула на Пропозиционални алгебра, можете да създадете таблица, която дава стойността на истината на формулата, в зависимост от истината стойностите на променливите. Такава маса се нарича маса
истина формула
Процедури за таблицата на истината могат да бъдат опростени, като използвате някои трикове. Нека илюстрираме това със следния пример.
Пример. Създайте таблица истината за формулата
(По силата на споразумението външни скоби във формула пропуснато).
Първата стъпка е да се създаде последователност на операциите. За да направите това от знака всеки логически операция срещащи се във формула комплект номер, което показва последователността на тази операция. В този случай е възможно, например, такава номерация:
Първият (глава) ред от таблицата се пише X, Y, и тази формула. В рамките на променливите х и у, пишем всички видове групи от логически стойности. След това ние получаваме една маса
Колона номер 5 (получен последния) дава истина стойност на формулата.
Определение 1. Формулата на Пропозиционални алгебра се нарича по същия начин вярно (или тавтология), ако нейната истина стойност е равен на 1 за всяка стойност на истината за.
Тавтологии роля преди всичко е, че те дават веригите на верни твърдения, независимо от съдържанието и достоверността на изявленията компоненти.
Например, формулата е тавтология
( «X или X»). Всъщност, каквото и конкретен израз да бъде заместен за X, а твърдение е вярно, тъй като
Въпреки тавтологии значение се крие не само в това, че с тяхна помощ построен верни твърдения; не по-малко важен е фактът, че тавтология даде правилните методи за извод. Ние илюстрират това за примера с формула
Тази формула е тавтология; че е лесно да се провери дали запис (една единица ще бъде в стойности на графи за цялото формули), за да му истина маса. Схема логически заключения, изразени това тавтология; обикновено се използва в математиката: тази схема се нарича "довеждане до абсурд". А именно, нека да се изисква да докаже твърдението X. Ние твърдим, като това: да кажем, че X е лъжа (т.е., че е вярно ..). След това с помощта на някои аргументи (в рамките на теорията, която се изучава) ние твърдим, че от една utverzhdenieY. и - че трябва да бъде точно обратното на твърдението. Тъй като едновременно валидността на твърдения и Y не е възможно, от горните съображения, ние се направи заключение за валидност (истина) X.
Нека посочим някои много важни тавтология.
1. Законодателството на commutativity на връзка и дизюнкция:
2. Законите на асоциативност на връзка и дизюнкция:
3. разпределителни закон:
4. Законите на Де Морган :.
5. Правото на изключени средата :.
6. противопоставяне :.
7. Правило Chain затвор (законът на силогизъм):
8. Правило "модус поненс". ,
9. Схемата на доказване "за противното" :.
Доказателство, че всеки един от посочените формули е тавтология, притежават собствен в упражнение.
4. формули еквивалентността
Определение 2. Две формули и Пропозиционални алгебра се наричат еквивалентни. ако някой от логическите стойности на променливи Пропозиционални логика стойности F и H са едни и същи. Еквивалентността на формули F и Н се изписва като :.
Съществува тясна връзка между понятието равностойност формула и концепцията за тавтология. Е както следва: Формула F и Н са еквивалентни, ако и само ако формулата е тавтология.
Това твърдение следва директно от самите определения
еквивалентност формули и тавтология.
1. докаже еквивалентността на формули и.
За всяка от тези формули се образува маса истина:
Сравнявайки таблиците, виждаме, че те формула са еквивалентни.
2. доказа еквивалентността на формули и.
Разбира се, можете да сравните масата на истината тези формули! Въпреки това, може да се твърди по този начин: формула е невярно само ако X = 1, Y = 0. формула и - само ако X = О, Y = 0. т.е. когато X = 1, Y = 0. По този начин двете .. формула невярна или вярно едновременно.
Редица equipollences могат да бъдат получени като се излиза от даден п. 3 тавтология. Например, формули са еквивалентни, тъй като формулата е тавтология (вж. Тавтология 4 °).
Трябва да се отбележи, че изразът не е формула. Това е просто запис на факта, че между формули F и Н е определен вид връзка (а именно, че F е еквивалентно на Н).