8. Определяне на формула А предикат логика наречен е задоволителен в М, ако има променливи, включени в тази формула и възложени на М (в противен случай - има модел), в която формула А е истинската стойност.
Opredelenie9. Формулата на предикатна логика, се нарича осъществимо. ако има област, в която тази формула е възможно.
10. Определяне на формула A предикатна логика, наречена идентично вярно в M (изпълнител), ако получи истинските стойности за всички променливи, включени в тази формула и възлага на района.
Определение 11. формула на предикатна логика, се нарича валиден. ако е идентична е вярно, във всяка област (за всички модели).
Ако двама равностойни формули на предикатна логика, за да се свържете познатия еквивалентността. След това получената формула ще вземе стойност и за всеки набор от променливи във всяка област, т.е. Това ще бъде най-общо е валиден.
Тази концепция е обобщение на идентично истинските формули на Пропозиционални логика. Всички логически закони, въведени през Пропозиционални логически формули са валидни в общи формули на предикатна логика, и да изразят, както и друга общовалидна формула, законите на логиката на езика на предикатна логика.
Общата валидността на формула предикатното логика, например, F е означен # 9500; F. Всички общовалидни формули могат да бъдат източник на нови # 9500; формули. Например, като се замести в средата изключени закона - вместо х предикат P (x1, ..., Xn), ние се получи всеобщо валидно формула P (x1, ..., Xn) (x1, ..., Xn). Когато п = 1 имаме универсално валиден формула. и по този начин - обикновено валиден предикатна логика формула.
От еднакво вярно Пропозиционални логика формула чрез заместване на х предикат Р (х, у), а вместо у предикат Q (х, у) получаваме формула универсално валидно и т. D.
12. Определяне на формула A предикатна логика наречените фалшиви идентично в M, ако получи фалшивите стойности за всички променливи, включени в тази формула и се разпределят в областта (с други думи, в този модел).
Определение 13. формула на предикатна логика, се нарича фалшива самоличност (невъзможно), ако тя е по същия начин неверни всяка област (всички модели).
Например, формулата е идентично невярно (невъзможно) предикат логика формула.
От горните определения недвусмислено следва:
1. Ако формулата А е валидна, а след това е възможно да се всяка област (модел).
2. Ако формула тавтология в М, то тогава е възможно в тази област.
3. Ако формулата А е идентично фалшиво в Москва не е възможно в тази област.
4. Ако формулата А не е възможно, то е идентично фалшива всяка област (всички модели).
5. За да Формулата на предикатна логика беше важи единствено и само ако му отрицание не е осъществимо.
6. За предикатна логика формула А е възможно, е необходимо и достатъчно, че формулата не е общовалиден.
Пример 1. докаже еквивалентност (логически идентичност):
Имайте предвид, че във всеки един от subformulae на квантор както за индивидуални променливи са свързани и че, следователно, те са твърдения, ще се въведе обозначението:
V или означаване на първи и втори обект променливи от N1 и N2, съответно:
В тази бройна система на набора за разглеждане на идентичност ще бъде :.
Осъществяване на стойност реализация може да се провери валидността на тази идентичност:
За да се опише този израз като цяло, ние виждаме, че тя е общовалидна формула.
Пример 2. За да се определи вида на формула.
Нека P (х). "Броят на х - дори -" предиката определено в М = N2.
Ето защо, се разглежда в този модел формула е следната теза: "Сред естествени числа съществуват дори, така и странно." Очевидно е, че това твърдение е вярно, и по този начин, по формула F е тавтология в този модел.
Въпреки това, ако същото предиката разположен на набор М = NHN където N - набор от четни числа, с формула F в такъв модел ще бъде фалшива самоличност.
Като се има предвид изложеното по-горе, ние заключаваме, че горната формула F е възможно (но не обикновено валиден).
Пример 3. За да се поберат формула модел, в който е идентичен вярно (и по този начин по принцип е възможно).
Нека Р (х, х, у): "х · х = у" или друго "х 2 = Y" - предикат определена на набор от естествени числа, т.е. М = Н. Тогава помисли за формула изразява твърдението за съществуването на природен квадрат на естествено число, което е очевидно вярно, т.е. на формула модел е идентично така, както се изисква.
Пример 4. Разглеждане на формулата. Това е възможно формула. Всъщност, ако F (X, Y, X): "х + у = х" - предикат размер, след това има М = N заместване на съответните у стойности, за разрешаване истина стойност на формулата. Очевидно е, че това е у = 0, тъй като в този случай ние се "х = х".
Ако Р (х, у, х): "XY = Х" - предикат продукт, след това тази стойност на у е у = 1, тъй като се получи вярно твърдение с него.
Но това е само една смяна, което води до вярно твърдение, че казва, че е за осъществимостта на формулата (но не и неговата валидност).
Пример 5. обикновено е валиден формула е:
Нека P (X, Y) - за да предикат (двоично връзка) "" определена на ограничен набор от естествени числа M1. След това, когато е заместен във формулата вместо свободните променливи стойности у получаваме вярно твърдение, както и чрез заместване на всеки друг от многото константи М1 - невярно. По този начин, гледани формула по принцип не е валиден.
Пример 6. Да разгледаме формула. Ние показваме, че това не е възможно.
Да приемем, напротив, т.е. че това е възможно. Това означава, че съществува определен М и конкретен предикат в него, че когато. След това тази формула се превръща в специфичен предикат. който от своя страна се превръща в истински изявление когато замества у всички елементи на комплекта М. Вземете всяка. След това изявление е вярно, както току-що инсталиран. Следователно, изявления и вярно.
Истината на второто твърдение можем да заключим, че едно твърдение е вярно (защото "за всички обекти, променливи", без значение колко те са били посочени). Но това противоречи на истината за първото твърдение.
Така ни предположение за осъществимостта на Формула неправилно.
Решимост проблем в предикат логика се поставя по същия начин, както в алгебра логика дали съществуват алгоритми, позволяващи всяко предикат логика формула А за да се определи какъв тип (клас), който поддържа, т.е. дали то е валидно, изпълним идентично или невярно (невъзможно). Ако съществуваше такъв алгоритъм, както и в Пропозиционални алгебра, той щеше да бъде намалена с критерия за идентичен истина всяка формула на предикатна логика. Имайте предвид, че, за разлика от алгебра логика, предикатна логика да се приложи методът не търси от всички варианти на променливи в мляко, защото тези опции могат да бъдат безкрайни.
Предикатна смятане - пример за неразрешим официална система. Undecidability предикат смятане доказа през 1936 г., американският логик Алонсо Чърч. теорема гласи те доказаха липсата на ефективна процедура при вземането на решение за произволна формула официална система, съдържаща аритметични естествени числа, независимо дали тази формула теорема.
Свързани статии