Мат. логика

Ответ: схема рассуждения верна.

**

Каждый раз в полдень солнце находится в зените. Сейчас полдень, значит, сейчас солнце находится

**

Если целое число 1, то оно простое или составное. Если целое число 2 и четное, то оно не является простым. Следовательно, если целое число 2 и четное, то оно составное.

х – число 1, у – число простое

z – число составное

u – число 2 и четное

Надо добавить (), тогда х → (y + z), u →, если u → z

12.Понятие формулы исчисления высказываний. Система аксиом исчисления высказываний.

Всякое исчисление включает в себя описание символов этого исчисления (алфавита), формул, являющихся конечными последовательностями символов, и определение выводимых формул.

Алфавит ИВ состоит из символов трех категорий:

1.Символы второй категории: x, y, z, x1, x2… - эти символы называются переменными высказывания. Еще эти переменные называют пропозициональными переменными или пропозициональными буквами ( от латинского propositio – предложение, высказывание)

2.Символы второй категории: ¬, , +, → - логические связки: отрицание, конъюнкция, дизъюнкция и импликация соответственно. Причем в рамках ИВ таблицы истинности для этих связок не принимаются во внимание, т.е. отбрасываются.

3.Третью категорию составляет пара символов ( , ) – скобки.

Формулы ИВ представляют собой последовательности символов алфавита, построенные по определенным правилам (синтаксическим).

Определение (синтаксические правила)

1.Всякая переменная x, y, z, x1, x2… является формулой (элементарной формулой).

2.Если А и В - формулы, то слова вида - также формулы.

3.Никакая другая строчка символов не является формулой. Примеры:

1)Переменные х, y, z, x1, x2,… являются формулами согласно п.1

2)Слова (хy), (x+y), (x → y) являются формулами согласно п.2

3)Согласно п.2 формулами будут слова , ((x+z) * (y → z)

- формула

- не формула Впредь будем опускать скобки по тем же правилам, что и в алгебре высказываний.

Определение доказуемой формулы

Доказуемые формулы образуются из исходных доказуемых формул, которые называют аксиомами, путем применения определенных правил вывода.

Система аксиом ИВ состоит из 11 аксиом, которые для удобства разобьем на 4 группы.

Первая группа:

I1

I2

Вторая группа:

II1

II2

II3

Третья группа:

III1

III2

III3

Четвертая группа:

IV1 IV2

IV3

13.Правила вывода исчисления высказываний: правило подстановки, правило заключения.

Правило подстановки: Если формула А доказуема в ИВ, х – переменная, а В – произвольная формула ИВ, то формула, полученная в результате замены в формуле А переменной х всюду, где она входит формулой В, является также доказуемой формулой.

Замена в формуле А переменной х формулой В называется подстановкой и символически записывается так:

Если А – доказуемая формула, то будем писать ├ А.

Тогда правило подстановки схематично будет выглядеть так:

├А __

├

Правило заключения: Если формулы А и А→ В доказуемы, то формула В также доказуема. Схематическая запись этого правила имеет вид:

14. Формальное доказательство.

Формальным доказательством называется конечная последовательность формул: B1, B2, …Bk. При чем каждая формула этой последовательности есть либо аксиома, либо получена по одному из правил (правило подстановки, правило заключения) из одной или двух предшествующих формул этой последовательности. Формальное доказательство является доказательством своей последней формулы Вк.

Формула В называется формально доказуемой или формальной теоремой, если она имеет формальное доказательство.

Дальше для краткости вместо «формальное доказательство», «формальная теорема» будем говорить «доказательство», «теорема».

Примеры доказательств: Доказать, что├ А → А

Пример: пусть требуется доказать является ли теоремой следующая формула:

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

Правило одновременной подстановки.

Пусть А – доказуемая формула. х1, х2, …, хn – переменные

В1, В2, …, Вn – произвольные формулы исчисления высказывания.

Тогда результат одновременной подстановки в А вместо х1, х2, …, хn соответственны формул В1, В2, …, Вn является доказуемой формулой.

Доказательство. Выберем переменные z1, z2, …, zn попарно различные и отличные от всех переменных, входящих в формулы А, В1, В2, …, Вn.

Теперь последовательно сделаем в формуле А n подстановок.

├- это дает то, что ├ А1

├дает ├ А2

……………………

├дает ├ Аn

После этого проведем последовательно еще n подстановок в формулу An

├дает ├ C1

├дает ├ C2

……………………

├дает ├ Cn

Ясно, что доказуемая формула Сn получается одновременной подстановкой в формулу А вместо переменных х1, х2, …, хn формул В1, В2, …, Вn. Схематично одновременная подстановка записывается в виде:

├ А____

├

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

Это правило формулируется так:

Если формулы A1, A2, …, An и доказуемы, то доказуема и формула L. Доказательство:

.

2) Так как доказуемой является формула А2 и ├ , тогда доказуемой является формула ├

……………………………….

n) Так как Аn доказуема (├ Аn) и ├ Аn → L, тогда по правилу заключения, формула L является доказуемой (├ L).

Схематично можно записать так:

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

Правило силлогизма. Если доказуемы А→ В, В → С, то доказуема формула

А→ С, то есть

├А → В, ├ В → С

├А → С

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

Выполнив следующие одновременные подстановки:

,, получим доказуемые формулы

1)├

2)├

Учитывая, что по условию доказуемы формулы:

3)├ А → В

4)├ В → С

Далее по правилу ПЗ(4,2) получим:

5)├ А → ( В → С)

Но тогда из формул 5, 3 и 1 по правилу сложного заключения получим, что

6)├ А → С

Правило контрпозиции.

Если доказуема формула А → В, то доказуема формула

Доказательство. Выполнив одновременную подстановку , получим доказуемую формулу

Тогда по правила ПЗ(2,1) получим:

3)├

17.Правила вывода исчисления высказываний: правило снятия двойного отрицания.

Правило снятия двойного отрицания.

Доказательство. Выполнив подстановки

,

Получим доказуемые формулы

1)├

2)├

По условию имеем:

3)├

4)├

Тогда по правилу силлогизма из 3 и 2 формул получаем:

5)├

То же можно получить из 1 и 4.

18. Формальный вывод.

Договоримся обозначать конечную совокупность формул Н = {A1, A2, …An} A1, A2,…,An называются посылками или гипотезами.

Обобщим понятие формального доказательства на случай вывода некоторой формулы В из других

формул A1, A2, …An.

Определение. Формальным выводом формулы В из посылок A1, A2, …An называется конечная последовательность формул: В1, В2, …, Вк (Вк = В), при чем, каждая формула этой последовательности есть или одна из посылок A1, A2,….An, или теорема, или формула, полученная из двух предшествующих формул этой последовательности по правилу заключения.

Если существует формальный вывод формулы В из формул A1, A2,…,An, то формула называется формально выводимой из формул A1, A2,…,An.

Схематично записывается:

A1, A2, …An ├ В (из A1, A2,…,An выводится В) Н ├ В.

Заметим, что доказательство – частный случай формального вывода из пустого множества посылок

(H = ).

Если же Н содержит хотя бы одну недоказуемую формулу, то класс формул, выводимых из Н, шире класса доказуемых формул.

В дальнейшем вместо «формальный вывод», «формально выводима», будем говорить просто «вывод», «выводима».

19. Основные правила выводимости.

Пусть Н и W – две совокупности формул исчисления высказывания. Обозначим через H, W и их объединение, т.е.

В частности, если W = {C}, тогда

Рассмотрим основные правила выводимости:

1.

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

2.

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

Существует вывод формулы А из формул Н,С (Н,С├А), то существует вывод А из Н и С

В1, В2, …, Вк-1, А (1)

По условию Н├С, поэтому существует вывод С из Н С1, С2, …, Сm, С (2)

В(1) возможны два случая:

a)в выводе (1) формула С отсутствует, тогда Н├А.

b)в выводе (1) одна из формул, например Вi есть С. Подставив вместо Вi в (1) вывод (2), получим:

В1, В2, …, Вi-1, C1, …, Cm, Bi+1, …A

И это уже будет вывод из Н, т.е. Н├А, следовательно, в любом случае Н├А

3. H,C├ A, W├ C

H,W├ A

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

Так как Н,С├А, то по первому правилу выводимости мы можем записать, что Н,W,С├А Так как W├С, то первому правилу выводимости Н,W ├С

Тогда, используя второе правило выводимости, можем записать, что H,W├A

4.H├ С→ А H,С├ A

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

H├ С → А, это означает, что существует вывод из Н, в конце которого стоит формула С→А, т.е. В1,

В2, …, Вк-1, С→А (1)

Присоединим теперь к совокупности формул Н формулу С, взяв вывод (1) и добавив в конце формулу С. Получим совокупность формул Н,С. Взяв вывод (1) и добавив в конце формулу С, получим вывод:

В1, В2, …, Вк-1, С→А, С (2), который является выводом из Н,С.

По правилу заключения из двух последних формул можно записать формулу А: H,C├ A

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

H,С├ А

H├ С → A

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

Предварительно докажем, что для любого вывода В1, В2, …, Вк из совокупности Н,С справедливо следующее утверждение: Н├ С→Вк.

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

1.k = 1 . Убедимся в справедливости Н├С→В.

А)

Б) В1 – теорема В) В1 – С

Вслучаях А) и Б) можно записать вывод из Н, а именно:

В1, В1 → (С → В1), С → В1

Н├ С → В1

Вслучае В) нужно доказать, что Н├ С → С

Но формула С→С доказуема и поэтому выводима из любой совокупности.

2.Предположим, что утверждение справедливо для любого вывода длины i<k и докажем, что оно справедливо для вывода длины k.

В1, В2, …, Вk из Н,С (К > 1).

Следовательно, относительно Вk возможны четыре случая:

А) Bk H

Б) Вк – теорема В) Вк – С

Г) Вк получается по правилу заключения из двух предшествующих формул.

Для случаев А), Б), В) доказательство утверждения Н├ С → Вк совпадает как для А), Б) в случае при k = 1.

В случае Г) формула Вк получается из двух формул Bi, Bj, при чем I < k, j < k. Bj должна иметь вид

Все формулы (1)-(3) выводимы из Н. Применяя к ним правило сложного заключения, мы получим,

что Н├ С → Вк.

Вернемся к общему случаю, пусть из Н├С→А, тогда существует вывод В1, В2, …, Вк-1, А из Н,С. При этом по доказанному справедливо утверждение, что Н├ С → А.

Следствие (обобщенная теорема дедукции):

При k = 1 имеем:

С учетом 4 и 5 правил выводимости можно записать:

A1, A2, …, A n-1, An ├ В  A1, A2, …, A n-1, An → В

В частности А├ В  ├ А → В Последнее соотношение устанавливает связь между выводимостью и доказуемостью.