Вопрос №10. Проблемы аксиоматического исчисления высказываний.

1. Проблема разрешимости ИВ заключается в доказательстве существования алгоритма, который позволяет определить, доказуема формула или недоказуема

2. Проблема противоречивости – в нем не доказуемы одновременно две формулы

3. Проблема полноты

Определение:

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

2. ИВ называется полным в широком смысле, если любые ТИ формула в нем доказуема

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

Определение:

Аксиома называется независимой от всех аксиом исчисления, если она не может быть выведена из остальных аксиом.

Вопрос  №11. Понятие предиката. Классификация предикатов. Множество истинности предиката.

Определённым на множествах M1…..Mn n-местным предикатом называется предположение, содержащее n-переменных x1,x2,…,xn, превращающиеся в высказывание при подстановке вместо этих переменных любых конкретных элементов их множеств M1…..Mn.

P(x1,x2,…,xn) – предикат, x1,x2,…,xn – предметные переменные.

Пример. «Река х впадает в озеро Байкал» - это одноместный предикат, определённый на множестве рек. Если х принимает значение «Барбузин» (0о), то данный предикат = истина.

Классификация предикатов.

Предикат P(x1,x2,…,xn), заданный на множествах M1…..Mn называется:

1. Тождественно Истинным (ТИ), если при любой постановке вместо x1,x2,…,xn любых конкретных предметов их множеств M1…..Mn он превращается в истинное высказывание.

2. Тождественно Ложным (ТЛ) - <наоборот>

3. Выполнимым (опровержимым), если существует по меньшей мере один набор конкретных предметов, при подстановке которых вместо соответствующих предметных переменных предикат превращается в истинное (ложное) высказывание.

Пример. «Город х расположен на берегу Волги» Предикат определн на множестве городов. Является выполнимым.

Множеством истинности предиката P(x1,x2,…,xn), заданного на множествах M1…..Mn, называется совокупность всех упорядоченных n-систем от (a1,a2,…,an), в которых a1 ϵ M1, a2 ϵ M2,….,an ϵ Mn, таких, что данный предикат превращается в истинное высказывание Р(a1,a2,…,an), где х1=а1,х2=а2,….,хn=an

Р+ - область истинности

Если Р(х) одноместный предикат, заданный на М, то его множество истинности является подмножеством М (Р+ ϵ М).

Предикат P(x1,x2,…,xn) заданный на M1…..Mn будет:

1. ТИ тогда и только тогда, когда P+=М1*М2*…*Mn (декартого произведение)

2. ТЛ тогда и только тогда, когда Р+= Ø

3. Выполнимым когда Р+ не равно Ø

4. Опровержимым тогда и только тогда, когда P+ не равно М1*М2*…*Mn

Два предиката P(x1,x2,…,xn) и Q(x1,x2,…,xn) заданных на одних и тех же множествах M1…..Mn называются равносильными тогда и только тогда, когда P+=Q+

Равносильность изображается как «P<=>Q»

Вопрос №12. Логические операции над предикатами.

Коньюнкция, дизьюнкция, отрицание, импликация, эквивалентность

Коньюнкцией двух предикатов Р(х) и Q(x) называется новый предикат Р(х)&Q(x) который принимает значение истинно при тех и только тех значениях х€М при которых каждый из предикатов принимает значение истинна и ложь во всех остальных случаях

Область истинности  Р(х)&Q(x) является Р+UQ+

Пример. P(x) «x – чётное число»

Q(х) «х –кратно 3»

Тогда предикат Р(х)&Q(x) можно записать следующим образом: «х делится на 6»

Р+UQ+ объединение.

Для остальных операций по анологии- так написано в лекциях.