Независимость системы аксиом.

Опр. Система аксиом S (S' подмножество S) называется независимой, если в S' существует аксиома не выводимая из аксиом S\S'.

Опр. Система аксиом называется независимой, если любая её подсистема независима.

Опр. Моделью системы аксиом называется алгебра, состоящая из не пустого множества М и системы логических связок Ω.

Где М-множество истинностных значений формул данного исчисления. (М,Ω), Ω-система логических связок.

Лемма:

Подсистема S' системы S является независимой, если существует модель этой системы в которой:

1) В системе S' существует аксиома принимающая невыделенное значение;

2) Каждая из аксиом системы S\S' принимает одинаковые выделенные значения;

3) Правила отделения, применимое к выделенным формулам даёт выделенную формулу.

Теорема 1. A1 является независимой от A2,A3

Теорема 2. А2 является независимой от А1,А3.

Теорема 3. A3 является независимой от A1,A2.

Алгебра предикатов.

Основные операции над предикатами.

Опр.   N – местным предикатом, заданным на множествах М1,М2,…..Мn –называется повествовательное предложение, которое обозначается Р и указываются переменные Р(x1,X2,…..xn), содержащие переменные, которые принимают значения xn принадлежит Mn, n=1,k и обращающиеся в высказывание при подстановке значений этих переменных.

x1,X2,…..xn- предметные переменные, а их значение называют предметами.

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

Опр. Предикаты P и Q, заданные на одних и тех же множествах называются равносильными, если они обращаются в истинные высказывания на одинаковых наборах значений переменных(или в случае совпадения области истинности).

Опр. Предикат P(x1,X2,…..xn) – называется следствием предиката Q(x1,X2,…..xn), если он обращается в истинное высказывание на всех тех наборах в предметах, на которых Q обращается в истинное высказывание.

Одноместным предикатом Р(x) называется произвольная функция переменного x, определенная на множестве M и принимающая значение из множества {1; 0}.

Множество М, на котором определен предикат Р(x), называется областью определения предиката Р(x).

Операции над предикатами.

Предикаты так же, как высказывания, могут принимать два значения: “истина” (1) и “ложь” (0), поэтому к ним применимы все операции логики высказываний, в результате чего из элементарных предикатов формируются сложные предикаты (как и в логике высказываний, где из элементарных высказываний формировались сложные, составные). Рассмотрим применение операций логики высказываний к предикатам на примерах одноместных предикатов. Эти операции в логике предикатов сохраняют тот же смысл, который был им присвоен в логике высказываний.

Пусть на некотором множестве M определены два предиката P(x) и Q(x).

  Определение 1.

Конъюнкцией двух предикатов P(x) и Q(x) называется новый (сложный) предикат, который принимает значение “истина” при тех и только тех значениях, при которых каждый из предикатов принимает значение “истина”, и принимает значение “ложь” во всех остальных случаях.

Очевидно, что областью истинности предиката является общая часть области истинности предикатов P(x) и Q(x), т.е. пересечение.

Так, например, для предикатов P(x): “x – четное число” и Q(x): “x кратно 3” конъюнкцией является предикат “x – четное число и x кратно трем”, т.е. предикат “x делится на 6”.

Определение 2.

Дизъюнкцией двух предикатов P(x) и Q(x) называется новый предикат, который принимает значение “ложь” при тех и только тех значениях, при которых каждый из предикатов принимает значение “ложь”, и принимает значение “истина” во всех остальных случаях.

Определение 3.

Отрицанием предиката P(x) называется новый предикат, который принимает значение “истина” при всех значениях, при которых предикат P(x) принимает значение “ложь”, и принимает значение “ложь” при тех значениях, при которых предикат P(x) принимает значение “истина”.

Очевидно, что, т.е. множество истинности предиката является дополнением к множеству I_P.

Определение 4.

Импликацией предикатов P(x) и Q(x) называется новый предикат, который является ложным при тех и только тех значениях, при которых одновременно P(x) принимает значение “истина”, а Q(x) – значение “ложь”, и принимает значение “истина” во всех остальных случаях.

Поскольку при каждом фиксированном справедлива равносильность, то.

Определение 5.

Эквиваленцией предикатов P(x) и Q(x) называется новый предикат, который обращается в “истину” при всех тех и только тех, при которых P(x) и Q(x) обращаются оба в истинные или оба в ложные высказывания.

 

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

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

Определение 2.

Предикат Р(х), определенный на множестве М, называется  тождественно истинным, если его множество истинности совпадает с областью определения, т. е. I_p=M.

Определение 3.

Предикат Р(х), определенный на множестве М, называется тождественно ложным, если его множество истинности является пустым множеством, т. е. I_p=0.

Естественным обобщением понятия одноместного предиката является понятие многоместного предиката, с помощью которого выражаются отношения между предметами.

Примером бинарного отношения, т. е. отношения между двумя предметами, является отношение “меньше ”. Пусть это отношение введено на множестве Z целых чисел. Оно может быть охарактеризовано высказывательной формой “х<y”, где, то–есть является функцией двух переменных Р(х,y), определенной на множестве упорядоченных пар целых чисел ZхZ=Z² c множеством значений {1;0}.

Определение 4. Предикат называется опровержимым, если существует набор предметов обращающий его в ложное высказывание.

Операции связывания переменных кванторами.

1.1 Квантор всеобщности.

Пусть Р(х) – предикат, определенный на множестве М. Под выражением понимают высказывание, истинное, когда Р(х) истинно для каждого элемента х из множества М, и ложное в противном случае. Это высказывание уже не зависит от х. Соответствующее ему словесное выражение звучит так: “Для всякого х Р(х) истинно ”.

Символ называют квантором всеобщности (общности). Переменную х в предикате Р(х) называют свободной ( ей можно придавать различные значения из М), в  высказывании  же х называют связанной квантором всеобщности.

1.2 Квантор существования.

Пусть P(x) - предикат определенный на множестве М. Под выражением понимают высказывание, которое является истинным, если существует элемент, для которого P(x) истинно, и ложным – в противном случае. Это высказывание уже не зависит от x. Соответствующее ему словесное выражение звучит так: “Существует x, при котором P(x) истинно.” Символ называют квантором существования. В высказывании переменная x связана этим квантором (на нее навешен квантор).

Кванторные операции применяются и к многоместным предикатам. Пусть, например, на множестве М задан двухместный предикат P(x,y). Применение кванторной операции к предикату P(x,y) по переменной x ставит в соответствие двухместному предикату P(x,y) одноместный предикат (или одноместный предикат), зависящий от переменной y и не зависящий от переменной x. К ним можно применить кванторные операции по переменной y, которые приведут уже к высказываниям следующих видов:

Рассмотрим предикат P(x) определенный на множестве M={a₁,…,a_n}, содержащем конечное число элементов. Если предикат P(x) является тождественно - истинным, то истинными будут высказывания P(a₁),P(a₂),…,P(a_n). При этом истинными будут высказывания и конъюнкция.

Если же хотя бы для одного элемента P(a_k)окажется ложным, то ложными будут высказывание и конъюнкция. Следовательно, справедлива равносильность