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

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

{├}╞

                        ТД :    ├             Ч. и т.д.

├, ├      

                        МР :                           ├                                 Ч. и т.д.

§ 5. Эквивалентность формул

Введём значок :

Опр.

Две формулы  и  называются эквивалентными друг другу, если доказуема :

├

                                         ├

1)  Рефлексивность :

2)  Симметричность :        ├

├

3) Транзитивность :           ├,├

├

Докажем свойство 3) :

                                          ├

Замечание 3. :      ├, ├

├

            Замечание 3. :      ├, ├

├,├ 

По Правилу Силлогизма :                                    ├

├,     

По Правилу Силлогизма :                                    ├

 Замечание  5.

            ├,├

├()() по

├         Ч. и т.д.

Теорема Эквивалентности

Если  содержат пропозициональную переменную  и, если формулы  равносильны друг другу (), тогда

Доказательства не требуется !

§ 6. Свойства формальных теорий

(логических систем)

Опр.

Интерпретацией называется некоторая функция, которая множество формул отображает в множество , которое накладывает на них определённый смысл.

                                   , →

Теорема 1.

Каждая доказуемая формула в Исчислении высказываний является тождественно истинная а Алгебре высказываний.

Теорема 2.

Каждая тавтология в Алгебре высказываний является доказуемой формулой в Исчислении высказываний.

Свойства :

1)  Непротиворечивость :

: ├ и ├

Нельзя доказать высказывание и его отрицание.

            2) Полнота :

Про любую последовательность символов можно сказать доказуемая она или нет.

 тождественно истинная формула доказуемая.

3) Разрешимость :

Исчисление высказываний разрешимо.

4) Независимость системы аксиом :

Все 11 аксиом полезны и их нельзя выбросить.

Логика предикатов

§ 1.      Понятие логики предикатов.

Опр.

Предикат (лат. сказуемое) – изучает движение.

Опр.

Одноместным предикатом называется функция, которая множество предметных переменных переводит в 0 или 1.

                                   {0,1}

Пр.

”… - столица РФ “

”- столица РФ “ ,  (города)

Москва): “ Москва – столица РФ ”      (1)

Хабаровск):”Хабаровск – столица РФ “          (0)

Опр.

Многоместным предикатом называется функция, которая Декартово множество  переводит в это же множество.

                       

Пр.

                     

                                    (0)

 - одноместный предикат {0,1}

Опр.

Множеством истинности предикатов называется множество таких  из , что

Опр.

Область ложности предикатов :            

Пр.

”… - столица РФ “

Москва}

Москва}

Опр.

Тождественно истинным предикатом называется такой предикат, что его область истинности совпадает с областью определения.

                                                          

Пр.

” - белый “ , {Сахар, Соль}

§ 2.      Логические операции над предикатами

1) Опр.

Отрицанием одноместного предиката называется новый предикат, такой что :           

0	1
1	0

Замечание :

Область истинности  .

2) Опр.

Конъюнкцией предикатов   и  называется новый предикат &,

		&
0	0	0
0	1	0
1	0	0
1	1	1

Замечание :  

3) Опр.

Дизъюнкцией предикатов   и  называется новый предикат ,

0	0	0
0	1	1
1	0	1
1	1	1

3)  Опр.

Импликацией предикатов   и  называется новый предикат ,

0	0	1
0	1	1
1	0	0
1	1	1

Опр.                                                   1, если , ,