Математическая логика формулы и теоремы

Если в ЭД (ЭК) входит каждая высказывательная переменная системы с отрицанием или без него и притом только 1 раз, то она называется полной ЭД или ЭК.

Систему значащих высказывательных переменных, для которых данная ПЭД принимает значение 0, назовём нулем ПЭД.

Систему значащих высказывательных переменных, для которых данная ПЭК принимает значение 1, назовём ПЭК. (стр. 39, лекции С. Яблокова, автор кратких записей в сомнениях).

Теорема 1

Для того, чтобы ЭД была ТИ необходимо и достаточно, чтобы в ней содержались вместе с некоторой высказывательной переменной xi, и ее отрицание xi.

Теорема 2

Чтобы ЭК была ТЛ необходимо и достаточно, чтобы в ней содержалось хотя бы одна пара множителей, один из которых является отрицанием другого.

Формула A называется конъюнктивной нормальной формой (КНФ) системы высказывательных переменных x1, x2, …, xn, если A является конъюнкцией элементарных дизъюнкций (ЭД) высказывательных переменных этой системы.

Формула А называется дизъюнктивной нормальной формой (ДНФ) системы высказывательных переменных x1, x2, …, xn, если A является дизъюнкцией ЭК-ций высказывательных переменных этой системы.

Теорема 3

Для каждой формулы существует эквивалентная ей КНФ.

Формула А называется совершенной КНФ (СКНФ) от высказывательных переменных x1, x2, …, xn, если она является конъюнкцией различных полных элементарных дизъюнкций от высказывательных переменных этой системы. При этом порядок членов в элементарных дизъюнкциях не учитывается.

Формула B называется СДНФ от высказывательных переменных x1, x2, …, xn, если она является дизъюнкцией различных полных элементарных конъюнкций от x1, x2, …, xn. Формула B – СДНФ, если B = A*для некоторой СКНФ формулы А.

СДНФ формулы А(x1, x2, …, xn) обладает следующими свойствами:

1) в ней нет одинаковых слагаемых;

2) ни одно слагаемое не содержит 2-х одинаковых множителей;

3) ни какое слагаемое не содержит переменную вместе с ее отрицанием;

4) в каждом слагаемом содержится в качестве множителя либо xi, либо ˥xi.

Условия 1) – 4) являются необходимыми и достаточными, чтобы ДНФ была совершенной нормальной формой.

АЛ используется в релейно-контактных схемах.

Логическое следствие.

Теорема 1

A |= B ó | = A –> B

Теорема 2

1) A1, A2, …, An |= B

2) A1 Λ A2 Λ … Λ An |= B

3) |= A1 Λ A2 Λ … Λ An -> B – общезначима

Следствие

Если А1, А2, …, Аn |= B, то A1, …, An |= An -> B

Теорема 3

Из любых посылок вытекает любая другая.

Алгоритм распознавания логического следствия.

1. Предположим, что рассуждение не является логическим следствием, т. е. рассуждение нелогично:

Ai = 1 (i = ), B = 0.

2. Подберем переменные, входящие в B таким образом, чтобы B = 0. будем подбирать значения других переменных так, чтобы все Ai = 1.

3. Возможны два случая:

а) удалось подобрать переменные согласно пункту 2;

значит, предположение верное, рассуждение нелогично;

б) не удалось подобрать переменные, и получилось противоречие;

значит, предложение было неверным, рассуждение логично.

Правила вывода

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

Пусть А1, А2, …, Аn |= B

1. Сокращение посылки. Правило определения.

Пусть А = 1 и А -> B = 1, тогда можно вывести B:

2. Цепное правило

3. Правило подстановки

Множество {A1, A2, …, An} высказываний непротиворечиво, если А1 Λ А2 Λ … Λ А3 = 1 по меньшей мере для одной комбинации, приписываемых простым компонентам истинностных значений. (т. е. то есть хотя бы для одной комбинации значений, приписываемых переменным А)

Множество {A1, A2, …, An} высказываний противоречиво, если А1 Λ А2 Λ … Λ А3 = 0 для всех комбинаций истинных значений, приписываемые простым компонентам.

Противоречие – формула, которая всегда ложна. Например,

Множество {A1, A2, …, An} высказываний противоречиво, если из него в качестве логического следствия можно вывести противоречие.

ЛОГИКА ПРЕДИКАТОВ

Одноместным предикатом P(x) называется всякая функция одного переменного, в которой x пробегает значения из некоторого множества M, а функция при этом принимает значения 0 или 1.

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

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

Предикат P(x) называется ТИ (ТЛ) на множестве M, если Ip Ξ M (Ip = ).

n-местным предикатом на множестве M называется функция P(x1, x2, …, xn), имеющая тип , где аргумент – вектор длины n с компонентами из множества M, а значением 0 или 1.

Множество M – предметное множество. Предикаты обозначаются большими буквами латинского алфавита.

P, Q, R, Z – предикатные переменные

p, q, r, z – предметные переменные

При n = 1 одноместный предикат P(x) называют свойством.

При n = 2 двуместный предикат P(x) называют отношением.

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

x P(x) – будем обозначать таким образом высказывание, которое истинно тогда и только тогда, когда P(x) = 1 для любых x, т. е. предикат P(x) принимает значение истина для всех x из предметной области.

P(x) не высказывание.

x P(x) – высказывание.

x P(x) – будем обозначать таким образом высказывание, которое ложно тогда и только тогда, когда P(x) = 0 при всех x из предметной области.

Операция навешивания квантора на переменную называется связыванием, и понижает мощность предиката на 1.

Символом x обозначается n-местный предикат на множестве M, зависящий от x1, x2, …, xn и не зависящий от x. Он принимает значение 1 для тех и только тех векторов (a1, a2, …, an), для которых одноместный предикат P(x, a1, …, an) тоже является истинным на M.

x P(x, x1, …, xn) называется n-местным на мн-ве M, зависит от x1, x2, …, xn и не зависит от x. Он принимает значение 0 для тех векторов (a1, a2, …, an) из M, для кот-х предикат P(x, a1, a2, …, an) = 0 на M.

Определение формулы логики предикатов (ЛП):

1. Каждое высказывание, как переменные, так и постоянные, является формулой.

2. Если P – символ предиката, а x1, x2, …, xn – предметные переменные или предметные константы, то P(x1, x2, …, xn) – формула. Такая формула элементарная, в ней предметные переменные свободны, не связаны кванторами.

3. Если A, B – формулы, то A Λ B, A v B, , A -> B, A <—> B тоже формулы.

4. Если A(x) – формула, в которой переменная x входит свободно, то x A(x), x A(x) – формулы, предметная переменная входит связанно.

5. Других формул нет.

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