Полнота логических функций. Теорема дедукции. Свойства формальных теорий (логических систем). Равносильные формулы логики предикатов, страница 2

D1

                                                                                  ├

И так далее применяя правило подстановки получаем :      ├

├               ч.  и  т.д.

Правило сложного заключения            

Теорема 2

Если формула ├,├,…,├, ├- доказуемы, тогда и доказуема формула .

Доказательство

Используем правило отделения (modus ponens) :

├,├      

                                               М.Р :     ├

Далее используя правило отделения :

├,├     

                                               М.Р :     ├

Если мы применим это правило n раз, то получим, что доказуема. Ч. и т.д.

Правило симметричности импликации (контрпозиции)

Теорема 3

Если доказуема , то и доказуема

Доказательство

Возьмём аксиому a₉)   - она доказуема по определению.

Сделаем в формуле подстановку :   a₉)                                   ├                       

П.С.П :     ├

По условию мы имеем :                   ├,├

                                               М.Р :                           ├                    Ч. и т.д.

Теорема 4

Если ├, то и ├

Доказательство

Пусть a₁) - доказуема по определению.

Сделаем в ней подстановку :   a₁)                    ├                

П.С.П :     ├                                     

Применим правило  :                                                      ├,├ 

                                                     М.Р :                                        ├                               Ч. и т.д.                                                        

Рефлексивность импликации

Теорема 5

├ ,      

                        Доказательство

Пусть  a₂) - доказуема по определению.

Сделаем в ней подстановку :   a₂)                    ├                  

                                                 П.С.П :   ├

Возьмём  a₁) - доказуема по определению.

├,├                  

                                                 М.Р :                     ├ 

F

  

Делаем подстановку :    

├                   

                                                 П.П :   ├  

Т.к   a₃) - доказуема по определению.

├,├                       

                                                 М.Р :                     ├           

Делаем подстановку :    

                                                           ├               

П.П :   ├       Ч. и т.д.

Правило силлогизма

Теорема 6                               ├, ├                     

                                                 П.С :               ├    

Доказательство

Пусть  a₂) - доказуема по определению.

Делаем подстановку :     a₂)                            ├      

                                                                       П.С.П :     ├  

Т.к  a₁) - доказуема по определению.

Делаем подстановку :     a₁), тогда

                                         ├   

П.С.П :     ├   

├,├

                                                 М.Р :                  ├)             

├) ,├  

                                                 М.Р :                  ├              

├),├,├

 М.Р :                  ├                                                                                                         Ч. и т.д.         

§ 3. Теорема дедукции

Опр.

Пусть дана H={} – совокупность формул. Каждая  называется гипотезой.

Опр.

Формула А называется выводимой из совокупности гипотез H, если выполняется :

1)  =, то она сразу же выводима.

2)  ├.

3)  H╞, H╞

H╞                 : МР

Замечание.

├из пустого множества ╞.

Лемма.

            Если из совокупность гипотез  H={}╞

                                                     {╞} 

Доказательство

Если n=1 :                ╞

                                           Пустое множество ╞