Studopediya

КАТЕГОРИЯ:


Астрономия- (809) Биология- (7483) Биотехнологии- (1457) Военное дело- (14632) Высокие технологии- (1363) География- (913) Геология- (1438) Государство- (451) Демография- (1065) Дом- (47672) Журналистика и СМИ- (912) Изобретательство- (14524) Иностранные языки- (4268) Информатика- (17799) Искусство- (1338) История- (13644) Компьютеры- (11121) Косметика- (55) Кулинария- (373) Культура- (8427) Лингвистика- (374) Литература- (1642) Маркетинг- (23702) Математика- (16968) Машиностроение- (1700) Медицина- (12668) Менеджмент- (24684) Механика- (15423) Науковедение- (506) Образование- (11852) Охрана труда- (3308) Педагогика- (5571) Полиграфия- (1312) Политика- (7869) Право- (5454) Приборостроение- (1369) Программирование- (2801) Производство- (97182) Промышленность- (8706) Психология- (18388) Религия- (3217) Связь- (10668) Сельское хозяйство- (299) Социология- (6455) Спорт- (42831) Строительство- (4793) Торговля- (5050) Транспорт- (2929) Туризм- (1568) Физика- (3942) Философия- (17015) Финансы- (26596) Химия- (22929) Экология- (12095) Экономика- (9961) Электроника- (8441) Электротехника- (4623) Энергетика- (12629) Юриспруденция- (1492) Ядерная техника- (1748) Arhitektura- (3434) Astronomiya- (809) Biologiya- (7483) Biotehnologii- (1457) Военни бизнесмен (14632) Висока technologies- (1363) Geografiya- (913) Geologiya- (1438) на държавата (451) Demografiya- ( 1065) Къща- (47672) журналистика и смирен (912) Izobretatelstvo- (14524) външен >(4268) Informatika- (17799) Iskusstvo- (1338) историята е (13644) Компютри- (11,121) Kosmetika- (55) Kulinariya- (373) културата е (8427) Lingvistika- (374) Literatura- (1642) маркетинг-(23702) математиците на (16968) Механична инженерно (1700) медицина-(12668) Management- (24684) Mehanika- (15423) Naukovedenie- (506) образователна (11852) truda- сигурност (3308) Pedagogika- (5571) Poligrafiya- (1312) Politika- (7869) Лево- (5454) Priborostroenie- (1369) Programmirovanie- (2801) производствено (97 182 ) индустрия- (8706) Psihologiya- (18388) Religiya- (3217) Svyaz (10668) Agriculture- (299) Sotsiologiya- (6455) на (42831) спортист строително (4793) Torgovlya- (5050) транспорт ( 2929) Turizm- (1568) физик (3942) Filosofiya- (17015) Finansy- (26596) химия (22929) Ekologiya- (12095) Ekonomika- (9961) Electronics- (8441) Elektrotehnika- (4623) Мощност инженерно ( 12629) Yurisprudentsiya- (1492) ядрена technics- (1748)

Prenex, Skolem нормално и Skolem образец




Еквивалентно на предикатното логика

В допълнение към еквивалентите на Пропозиционални логика да предикат логика ние сме следното еквивалентност ( , , - Предикати, а - Резюме):

Комбинацията от quantifiers:

1. ;

2. ;

3. ,

Комбинацията от quantifiers и отрицание:

;

;

;

,

Разширяване на обхвата на quantifiers ( Това не зависи от ):

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. ;

8. ,

Разширяване на обхвата на quantifiers:

1. ;

2. ;

3. ;

4. ;

5. /

Нормалната форма. Формулата на предикатното логика е в нормална форма, ако той съдържа само операциите на връзка, дизюнкция и операции квантор и експлоатация отказ приписани на основни формули. Например, формулата нормална форма воля ,

Prenex Normal Form (ЛНЧ) - нормална форма, в която операциите по квантор или напълно отсъства или се използват след всички булеви операции.

Например, за една нормална форма

prenex нормална форма ще ,

Всяка формула на предикатното логика може да се намали до PNP, ако използвате следния алгоритъм:

Стъпка 1. изключване логически connectives и ,

Стъпка 2. Насърчаване на отрицанието регистрирате атоми. Много пъти (толкова дълго, колкото е възможно), направени подмяна:

,

,

,

,

,

Стъпка 3: Преименуване на свързани променливи.

Стъпка 4. Въвеждане на quantifiers. За отстраняване на quantifiers равностойност формула се използва за смятане на предикат.

След четвъртата стъпка, получаваме PNP.

Нека разгледаме по-подробно в третия параграф на алгоритъма - преименуването на променливи.

нека произволна формула на предикатното логика. формула Ние получи от формула заместване на съответните променливи други променливи, различен от всички свободни променливи с формула , И замества променливите във формулата Тя следва да се променя по същия начин навсякъде в областта на квантор задължителен тази променлива, и квантор. В този случай, еквивалентни на ,

По този начин, преименувате свързаните променливи необходими само в областта и квантор

Действия на този квантор. Същите променливи, за които quantifiers обвързващи ги имат различен обхват могат да бъдат преименувани по различни начини и един от тях може да се преименува, а другият не.

Пример 1. Да предположим, че имаме формулата , Нормално формула е ,

преименуване на променливата в квантор и обхвата на квантор на ,

,

променлива получава формулата на Можете да преименувате да в първото помещение и втората пратка, или да напусне през втората предпоставка непроменена

=



Следващите примери илюстрират прилагането на алгоритъма за привеждане на PNP.

Пример 2. ,

Етап 1.

Етап 2.

,

Етап 3.

,

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

Многократно използване на този подход, ние се

,

Пример 3.

Етап 1: От израза не съдържа отражение и еквивалентност на операции, не е необходимо в първия етап.

Етап 2.

Етап 3.

Етап 4. =

,

Можете да мислите за още по-тесен клас формули, така наречения - формули.

формула Тя се нарича - Формулата, ако тя е представена в PNP, на квантор е само част от универсалните quantifiers, т.е. където - Free формула. Следователно задачата за премахване на екзистенциални quantifiers във формули, представени в PNP. Това може да стане чрез въвеждане Skolem функции.

Skolem нормална форма (ОЯГ) е изграден в съответствие със следните правила:

1. Формулата на предикатното логика е представена в PNP.

2. В съответствие (от ляво на дясно) зачеркнете всеки екзистенциален квантор, например , Подмяна на всички срещания на променливата ново не се използва функционален символ , Като аргументи Ние приемаме всички променливи, свързани с предишния универсални quantifiers. функционален символ Тя се нарича функция Skolem. Формулата на предикатното логика, получени след завършване на етапи 1 и 2, се нарича Skolem нормална форма (ОЯГ).

Пример 1.

За ОЯГ зачеркнете наличието на фактор всички срещания на се заменя с постоянна защото квантор не се предшества от всяка универсална квантор, т.е. функция Skolem не зависи от една променлива, т.е., тази функция е постоянна.

В следващата стъпка ще изтрие екзистенциална квантор всички срещания на замени функцията на

,

В последната стъпка ние изтриете квантор ,

,

Преходът от PNP да Skolem нормална форма на формулата не влияе на свойство да бъде невъзможно (противоречива). Това се доказва от следната теорема.

Теорема. Нека формула и набор от PNP превръща в ОЯГ. след това в PNP логически невъзможно, ако и само ако това е невъзможно за ОЯГ ,

Въпреки това, следва да се отбележи, че ако има възможно формула , Може да е, че за SNF Тя ще бъде невъзможно.

Нека сега разгледаме един квантор без преобразуване на формата на така наречените клаузи. Отделен вид, наречен формула където - Един произволен характер. Клаузи, все още няма букви, наречени празната клаузата (Y). По дефиниция, тя винаги е фалшива.

Помислете алгоритъма е еквивалентно на превръщането на всяко квантор формула без в CNF.

Стъпка 1. Dana формула Предполага се, че във формулата са изключени между същите скоби връзки, т.е. Не са израз на формата , , , ,

Стъпка 2. Намерете първата поява на символа вляво " ( "Или") "(Тук се предполага, че скобата не е скоба атом). Ако няма такива събития, на - формула Това е в CNF.

Стъпка 3: Нека първата поява на двойката символи е " ( ". След това трябва да се вземе най-голямата формула така че част формула , Което е свързано с влизането " (. "Сменете формула с формула

Стъпка 4: Нека първият запис е ") ". След това вземете най-голямата формула така че част формула Свързани с влизането ") ". замени с формула

,

Стъпка 5. Отидете на стъпка 2.

Пример. Конвертиране формула

CNF.

Ние практикува първо първото и след втората поява на героите " ".

=

=

,

Тук по-долу маркираното " ". В допълнение, алгоритъмът е необходимо да се осигури намаляване на други членове, както и всички видове свързване и усвояване.

По този начин, последователно прилагане на алгоритъма на PNP, производство на ОЯГ и алгоритъм алгоритъмът да донесе CNF запазване свойства неприложими всяка формула Тя може да бъде представена чрез набор от клаузи, обединени универсален квантор. Тази формула ще се нарича формулата, посочена в Skolem стандартен формуляр (SSF).

В бъдеще, формулата на формата където - Клаузи и - Различните променливи, включени в тези клаузи ще бъдат удобно представени като съвкупност от клаузите

Например, множеството от клаузите

съответства на следната представяне в SSF

И най-накрая, когато казваме, че множеството на клаузи

невъзможно (противоречива), винаги предполага невъзможност формула където - Различните променливи, включени в клаузите.

Доказателство за правилността на извод се основава на следната теорема.

Теорема 1. Формули и , формула Това е логично следствие от формулите ако и само ако формулата е валиден.

Теорема 2. Формули и , формула Това е логично следствие от формулите ако и само ако формулата противоречива.

Помислете за механизма на доказателство за правилността на изводите на предикатното логика за примера

,

Ние използваме втората теорема. Първо ние даваме израз на ключалките от неръждаема стомана. Намираме отрицание на сключване:

=

= ,

Обръщаме се към PNF

,

Качваме се на ОЯГ, което също е ключалките от неръждаема стомана.

,

Ние се образува продукт

,

Контролни въпроси и упражнения

Задача 1

Кой от следните изрази са предикати. Маркирайте сред думите на предиката.

1. номер - Обикновено;

2. ;

3. ;

4. ;

5 Всички тези триъгълници са равни;

6 ;

7. всички нечетни номера са разделени на броя ;

8. Всички четни числа са разделени от 2;

9. 8 - нечетно число;

10. Има безкраен брой различни прости числа;

11. Броят на Това не е проста.

Задача 2

Нека променливите в следните изрази са избрани от набор от реални числа и алгебрични знаци имат обичайните си значения. За да се определи дали тези изрази са верни:

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. ;

8. ;

9. ;

10. ;

11. ;

12. ,

Дейност 3

За реални числа да се записват на езика на предикатните присъди изразяващи:

1. Освен е комутативен;

2. размножаването е комутативен;

3. асоциативност на допълнение;

4. асоциативност на умножение;

5. distributivity на умножение по отношение на допълнение.

Дейност 4

Експресна областта на предикатното истината на през района на истината предикати и Ако:

1. ;

2. ;

3. ;

4. ;

5. ,

Задача 5

Посочва се свободни и обвързани променливи:

1. ;

2. ;

3. ;

4. ;

5. ,

Задача 6

Нека всички тези предикати определени на снимачната площадка на реални числа. Тя показва графично диапазона на изменение на свободните променливи, за които са определени тези предикати за "истинска":

1. ; 2. ;

3. ; 4. ;

5. ; 6. ,

Задача 7

Намери отрицание на следните формули.

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. ,

Задача 8

Донеси следната формула на предикатното логика да prenex първата нормална форма (ЛНЧ), а след това Skolem нормална форма (ОЯГ) и Skolem стандартен формуляр (SSF).

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. ;

8. ;

9. ;

10. ;

11. ;

12. ;

13.

;

14. ;

15. ;

16. ;

17. ;

18. ;

19. ;

20. ;

21. ;

22. ;

23. ;

24. ;

25. ;

26. ,

Задача 9

нека и две единични предикат определено на снимачната площадка така че изявлението - Винаги е вярно. Докажете, че изявлението - Винаги фалшива.

Задача 10

нека означава " - А просто число " - " - Още по брой, " - " - Нечетно число " - " разделен ". Публикувай формулировка на следните формули:

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. ;

8. ;

9. ;

,

Задача 11

одобрение Dana - "Номер 3 е разделена на " - "Номер 2 е разделена на " - "Номер 4 е разделена на " - "Номер разделена на 6 " - "Номер разделена на 12 ". Посочете кои от следните твърдения са верни и които са фалшиви.

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. ,

Задача 12

Докажете следната еквивалентността.

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. ;

8. ;

9. ;

10. ;

11. ,

Дейност 13

Кои от дадените формули са валидни по принцип?

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. ;

8. ;

9. ;

10. ;

11. ;

12. ;

13. ;

14. ;

15. ;

16. ;

17. ;

18. ;

19. ).

Задача 14

За да докаже неистинността на идентични формули.

1. ;

2. /





; Дата: 27.06.2015; ; Прегледи: 4956; Нарушаването на авторските права? ;


Ние ценим Вашето мнение! Беше ли полезна публикуван материал? Да | не



ТЪРСЕНЕ:


Вижте също:



zdes-stroika.ru - Studopediya (2013 - 2017) на година. Тя не е автор на материали, и дава на студентите с безплатно образование и използва! Най-новото допълнение , Al IP: 66.102.9.26
Page генерирана за: 0.089 сек.