Пропозиционални смятане Проверка на излюпване правилни заключения. Куайн алгоритъм. Обикновено резолюции. алгоритъм на Вонг.

I официалната система (FS)

W - азбука специални разделители

PPF - добре оформени формули на имената и символи

А Î PPF - формулите, които се наричат ​​аксиоми

PV - на снимачната площадка на извод правила PPF вид ", ако, след това"

Смятане такава, че се генерира от множество структурно аксиоми използват MF.

Пример 1. Официално граматика. Когато А - терминал азбука; V - спомагателен азбука; P - правилата на извод, вида, където (всичките думи на обединената азбука); S - първоначалната спомагателни символ (ранно поколение) са аксиома.

Граматиката G генерира (изчислява) език, който е набор от думи, разпределени за целите на синтактичните описание модели на някои обекти (например АЛГОЛ език за програмиране).

II. Официално модел на отчети (извлечения на езика)

A - азбука имена =. Z - азбуката символи = ®, , ù, В. Å, º, други признаци на логически операции, - скоби>. PPF скоби са от формула А и Z. конструирана съгласно определени правила, например - имат PPF и PPF формула не е така. Буквите A, B, C и така нататък. Г. Комплекс определени PPD.

1) всеки са атомна изложение. Например, стр - "Студент спи", р - "слоновете живеят в Африка"

2) Всяка PPF образува комплекс изречение, когато знакът е прикрепен към смисъла на логическите връзки между отчети.

- значение: А или В, но не и двете (разделени от или).

- значение: А е идентичен (еквивалент) в.

ù - значение: няма друго обозначение А. -

Пример: р - студент спане, Q - дойде времето, г - скучна лекция.

Студент спи и дойде времето

Студентски спане, ако лекцията е скучно -.

5.Interpretatsiya PPF.

1) Всеки изказване се дължи атомен стойност.

2) Всяка PPF се дава стойността в зависимост от тълкуването на сухожилията, като операциите по букви. Тълкуване сухожилие съответства на таблиците за истинност FAL.

3) Ако в някакъв интерпретация PPF е вярно, то се нарича изпълним относно тълкуването.

4) Ако PPF е възможно (вярно) за всички набори, той се нарича по същия начин е вярно. тавтология. или универсално валидни.

Други тълкувания на PPF.

а) Multi-ценен логика. Например, всеки атомен присъда от PPF и самата PPF получите стойност от снимачната площадка - трикомпонентна логика.

б) и правдоподобно логика. Г. Поля въведени в книгата, "Математика и правдоподобно мислене." PPF вземе стойности от снимачната площадка и се тълкува като мярка за декларациите за достоверност. Г. Поля въведени правилата за изчисляване на вероятността за наличие на отчети, съставени по отношение на основателността на неговите компоненти.

III. Специален вид изказвания - разсъждение или

В мотивите е две изказвания «р» и «S». р - декларация - помещение, S - казва - в резултат, на официалния отчет на мотивите - чете "р предполага S», или "ако P след това S» .Inogda изявление S се нарича също заключението.

Какво свойства са разпределени правилния мотивите? следната връзка трябва да бъдат изпълнени:

а) ако P = "истинска", тогава S = трябва да бъде "истинска".

б) ако P = "фалшиво", а след това на "лъжи", може да бъде последвано от нещо, това е. е. Най-накрая, S може да бъде фалшива и вярно.

в) от истинската Помещението не следва фалшиво заключение.

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

Можете да въведете това тълкуване правилните аргументи: Ако правилно, тогава.

Добре оформен аргумент е тавтология. Правилният аргумент не може да бъде, че парцелът е вярно, но заключението е невярно. Тази линия в истина маса правилно мотивите на отсъства. Ако е тавтология, ние казваме, че аргументът е изграден в съответствие с логиката и е логично право. който не зависи от тълкуването, но се определя само от конструкцията (ППФ) парцелите и ефекти.

закони IV.Logicheskie (Aristo-322 г. н.е.).

За първи път изрично логически закони, с които можете да се изгради правилните аргументи се формира Аристотел. Учудващо е, че теорията на правилните аргументи, което се нарича силогистична заключения и коригиране на метода за извеждане на парцелите - приспадане са се образували преди повече от 2 хиляди години, никой не отрича и се считат за присъщи на човешкото мислене.

Припомнете си, че всички закони на логиката трябва да са тавтологии. Понякога закони се наричат ​​правила за извеждане, които определят правилното заключение от помещенията.

1) модус поненс (обикновено офиси); което означава, че ако е вярно, че А означава, Б и А е вярно, тогава Б е вярно.

Официално изказване запис (изводи аргументи) в формула. Проверка на аргументите, държани от масата за истина.

Проверка тавтологии чрез еквивалентни трансформации.

Пример: Ако един скучен лекция, студентът не спи. Лекцията е скучно.

2) Начин Толенс (отрицателна Marus)

3) Правило силогизъм;

4) Законът НАСРЕЩНИТЕ

5) Всички (идентичност) са на Булева тавтология и затова са логически закони.

6) Правото на изключени средата.

7) и разпределителни закона.

8) Акт "фатална дилема"

Следната теорема може да бъде доказано.

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

За пример - е тавтология, т.е., означаващ да ..

За представяне под формата на F въведат

V.Ischislenie отчети.

Най-голям интерес е изграждането на официална система, която наред с всички възможни отчети на PPF разграничава тези, които са логически закони (добре оформени аргументи, логическо мислене, тавтологии, общовалидни твърдения).

Официално система, която генерира отчети, които да тавтологии, и само тях, се наричат ​​Пропозиционални смятане (BPI). Беше показано, че всяка формула изказвания (включително тавтология) могат да бъдат намалени в структурата на мотиви (извод), "ако R. S».

Формула IV се считат извлича от аксиоми. Всеки изход на тавтология изход на тавтология. обозначение: # 8870; ; Тълкуване: от подразбират.

Формално IV система се определя от:

Формула - аксиоми са тавтологии. правила извод са също под формата на тавтологии.

В днешния момента се знае "20 IW, които се различават едни от други аксиоми (аксиоми вериги) и правила изходи. Mark IV има 1) пълнотата на имота - (те са подразбират всички тавтологии и само те) 2) набор от аксиоми има минимален завършеност (т.е. премахване на най-малко един от набор от аксиоми прави BPI непълна) ...

1) IV Uytheda и Russell (1920¸1930, England).

Правила изход Р1: заместване на вместо Б; Р2 е заменен с еквивалентно P3 формула: модус поненс # 8870; V.

2) Никодим IW (1952, USA)

Единственият аксиома с експлоатацията на удара Sheffer:

само PV: # 8870; C.

VI. Методи и алгоритми излюпване тест.

Като се има предвид набор от PPF, който се нарича помещенията (понякога хипотези) и PPF -. "" Се отнася до логично следствие. или извлича от А (записва като # 8870; ), Ако това е тавтология (идентично вярно твърдение).

По този начин, проблемът се свежда тест люпимост да направите проверка за идентично вярно. Има няколко десетки методи и алгоритми за създаване идентичен истина логично формула.

AIT е сведена до последователна смяна на всички възможни интерпретации (набори "вярно" и "невярно") променливи в. Алгоритъмът спира, ако стойността е фалшива (това не е възможно, поради което не е подразбират от всички интерпретации); истина (възможно във всички интерпретации, тогава същността на тавтология и A # 8870 ;. Този алгоритъм изисква в най-лошия 2n замествания (2n възможни интерпретации), където «п» броят на променливите във формулата F.

2. Куайн на алгоритъм (Куайн. 1960 USA)

Идея: замествания при последователни стойности на променливи могат да бъдат намалени дължина на формула, на базата на множеството от проверка на тяхната валидност провежда Е. и по този начин да се намали броят на променливите да бъдат проверени.

Той въвежда концепцията за дървото тест, който в действителност е графика на всички тълкувания на тествана формула. Куайн го нарича "семантично дърво."

Пример: Да предположим, че искаме да се провери валидността на формулата

Семантичната дървото. Всеки левия край на дървото съответства на една променлива и всеки десния край -.

Всеки клон (например, най-лявата) съответства на набор от (р х р х г), Четвъртата картина. Дървото изброява всички възможни елементарни съюзи.

1) настроен на F (горе), а след това

(В горната формула "1")

2) да се определят, след това

(В горната формула "2")