сергиевская

Запишем ¬A . Каждая формула из множества Γ и формула ¬A независимо преобразуются во множество предложений. В этом множестве нужно найти резольвируемые предложения и применить к ним правило резолюций. Резольвенты добавляются во множество предложений до тех пор, пока не будет получено пустое предложение. Возможны два случая:

•Среди множества предложений нет резольвируемых. Вывод: теорема опровергнута, и формула A не выводима из множества формул Γ .

•Получено пустое предложение. Теорема доказана. Имеет место выводимость

Γ├A .

Примеры. 1. Методом резолюций доказать теорему ├¬A → ( A → B) .

Доказательство. Запишем инверсию исходной формулы:

¬(¬A → (A → B)).

Заменим все импликации по соответствующей формуле:

¬(¬A → (A → B))= ¬(¬¬A (¬A B)).

Применим закон двойного отрицания и закон де Моргана:

¬(¬A → (A → B))= ¬(A (¬A B))= ¬A ¬(¬A B)= = ¬A ¬¬A ¬B = ¬A A ¬B .

Получаем предложения: ¬A , A , ¬B . Резольвируем их:

1.¬A – предложение.

2.A – предложение.

3.¬B – предложение.

2.Методом резолюций доказать теорему

├A → (B → A B).

Доказательство. Запишем инверсию исходной формулы:

¬(A → (B → A B)).

Заменим все импликации по соответствующей формуле:

¬(A → (B → A B))= ¬(¬A (¬B A B)).

Применим закон двойного отрицания и закон де Моргана:

¬(A → (B → A B))= ¬¬A ¬(¬B (A B))= = A B ¬(A B)= A B (¬A ¬B).

Получаем предложения: A , B , ¬A ¬B .

1.A – предложение.

2.B – предложение.

3.¬A ¬B – предложение.

В Содержание.

26

Задачи.

Методом резолюций доказать теоремы:

1)├(A → B)→ ((B →C) → ( A →C)) .

2)├( A → (B → C)) → (B → ( A →C)) .

3)├(A → B)→(¬B →¬A) .

4)├( A → B) → ((C → A) → (C → B)) .

5)├A → (¬A → B) .

6)├(A → B)→((¬A → B)→ B).

7)├(A → B)→ (( A → (B →C)) → (A →C)).

8)├(A → B) (A → ¬B)→ ¬A .

9)├(A → (B →C))→ (A B →C).

10)├( A → B) → ((B →C) → ((C → D) → ( A → D))) .

11)├( A → B) → ((B →C) → ( A →C)) .

12)├(A B → C)→ (A → (B →C)).

13)├( A → (B → A)) → A.

14)êA A.

15)├(A → B) (B → A) .

В Содержание.

Глава 5. Предикаты.

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

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

Примеры. 1. Предикат A(x) =" x ≤ 2" на множестве X = R – одноместный. 2. Предикат B(x, y) =" xy > 0" на множестве X = R2 – двуместный.

27

Если X ={0,1}, то n -местный предикат представляет собой n -местную булеву функцию.

Нульместный предикат представляет собой высказывание.

Для каждого предиката A областью истинности называется множество Y ={x X A(x) =1}, на котором предикат принимает значение 1.

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

3. Коммутативность:

P(x) Q(x)= Q(x) P(x), P(x) Q(x)= Q(x) P(x).

2. Ассоциативность:

P(x) (Q(x) R(x))= (P(x) Q(x)) R(x),

P(x) (Q(x) R(x))= (P(x) Q(x)) R(x).

3. Дистрибутивность:

P(x) (Q(x) R(x))= (P(x) Q(x)) (P(x) R(x)), P(x) (Q(x) R(x))= (P(x) Q(x)) (P(x) R(x)).

4. Идемпотентность: P(x) P(x)= P(x), P(x) P(x)= P(x). 5. Закон двойного отрицания: ¬¬P(x)= P(x).

6. Закон исключения третьего: P(x) ¬P(x)=1. 7. Закон противоречия: P(x) ¬P(x)= 0 .

8. Законы де Моргана:

¬(P(x) Q(x))= ¬P(x) ¬Q(x),

¬(P(x) Q(x))= ¬P(x) ¬Q(x).

9. Свойства операций с логическими константами:

P(x) 1 =1, P(x) 0 = P(x), P(x) 1 = P(x), P(x) 0 = 0 .

Здесь P(x), Q(x) и R(x) – любые предикаты.

В то же время, для предикатов определены операции специального вида, которые называются кванторами.

Пусть дан n -местный предикат A(x1 , x2 ,..., xn ) на множестве X , означающий, что для набора (x1, x2 ,..., xn ) выполнено свойство A, и пусть xi – одна из переменных. Тогда запись xi A(x1, x2 ,..., xn ) означает, что для всех значений переменной xi свойство A выполнено. Символ называется квантором

28

всеобщности (общности). Предикат xi A(x1, x2 ,..., xn ) является ( n −1)-местным. Он зависит от переменных x1, x2 ,..., xi−1, xi+1,..., xn . Если дан одноместный предикат P(x) , то утверждение xP(x) представляет собой нульместный предикат, то есть истинное или ложное высказывание.

Пример. На множестве X = R дан предикат A(x) =" x ≤ 2" . Высказываниеx(x ≤ 2) ложно.

Пусть дан n -местный предикат A(x1 , x2 ,..., xn ) на множестве X , означающий, что для набора (x1, x2 ,..., xn ) выполнено свойство A , и пусть xi – одна из переменных. Тогда запись xi A(x1, x2 ,..., xn ) означает, что существует значение переменной xi , такое, что выполняется свойство A . Символ называется квантором существования. Предикат xi A(x1, x2 ,..., xn ) является ( n −1)-местным. Если дан одноместный предикат P(x) , то утверждение xP(x) представляет собой нульместный предикат, то есть истинное или ложное высказывание.

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

xi A(x10 , x20 ,..., xi ,..., xn0 ) → A(x10 , x20 ,..., xi0 ,..., xn0 ) = B0 .

29

Покажем, что это высказывание истинно. Возможны два случая.

1.xi A(x10 , x20 ,..., xi ,..., xn0 ) = 0 , следовательно B0 =1.

2.xi A(x10 , x20 ,..., xi ,..., xn0 ) =1.

Соотношение выполнено при любых значениях xi , следовательно, и при значении xi = xi0 . При подстановке этого значения получаем:

A(x10 , x20 ,..., xi0 ,..., xn0 ) =1.

Следовательно, по свойству импликации получаем, что B0 =1, что и требовалось доказать.

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

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

Справедливы эквивалентности:

x yP(x, y) = y xP(x, y) , x yP(x, y) = y xP(x, y) .

Разноименные кванторы можно переставлять только следующим образом:

x yP(x, y) → y xP(x, y) , y xP(x, y) → x yP(x, y) .

Обратные формулы неверны.

30

Пример. Очевидно, что высказывание x y(x + y = 0) ( X = R ) истинно. Поменяем кванторы местами. Получим высказывание y x(x + y = 0), которое является ложным.

тождественно истинным. Тогда (по свойствам конъюнкции) тождественно истинным не будет и предикат P(x) Q(x) , следовательно, ложным будет

высказывание x(P(x) Q(x)). Высказывания xP(x) и xP(x) xQ(x) также

будут ложными.

Таким образом, обе части эквивалентности одновременно истинны или ложны, и эквивалентность доказана.

Замечание. Формула x(P(x) Q(x)) не эквивалентна формуле

xP(x) xQ(x) .

Доказательство. Рассмотрим обе формулы на множестве R . Пусть предикат

следовательно, ложно и высказывание xP(x) xQ(x) . Таким образом, построен пример, когда формулы x(P(x) Q(x)) и xP(x) xQ(x) принимают различные значения.

Тем не менее, справедливы эквивалентности:

xP(x) xQ(x) = xP(x) yQ( y) = x(P(x) yQ( y))=

= x y(P(x) Q( y)).

Аналогично, формулы x(P(x) Q(x)) и xP(x) xQ(x) не эквивалентны. Но

справедливы эквивалентности:

xP(x) xQ(x) = xP(x) yQ( y) = x(P(x) yQ( y))=

= x y(P(x) Q( y)).

Имеют место формулы:

x(P(x) C)= xP(x) C , x(P(x) C)= xP(x) C ,

x(P(x) C)= xP(x) C , x(P(x) C)= xP(x) C .

Здесь C не содержит переменной x .

31

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

Определение. Предикатная формула находится в предваренной форме

(предваренной нормальной форме), если она имеет вид Q1x1Q2 x2 ...Qk xk A , где

Q1,Q2 ,...,Qk - кванторы всеобщности или существования, а формула A находится в приведенной форме и не содержит кванторов.

Пример. Записать формулу

A= x yP(x, y) → x yQ(x, y) R(x)

впредваренной нормальной форме.

Решение. A = x yP(x, y) → x yQ(x, y) R(x) =

=¬x yP(x, y) x yQ(x, y) R(x) =

=x¬yP(x, y) x yQ(x, y) R(x) =

=x y¬P(x, y) x yQ(x, y) R(x).

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

A= t y¬P(t, y) z yQ(z, y) R(x) =

=t( y¬P(t, y) z yQ(z, y) R(x))=

=t z( y¬P(t, y) yQ(z, y) R(x))=

=t z y(¬P(t, y) Q(z, y) R(x)).

истинными будут высказывания P(a1 ) , P(a2 ) , …, P(an ) . При этом истинными будут высказывания xP(x) и конъюнкция P(a1 ) P(a2 ) … P(an ) .

определены на множестве {a,b,c}.

Решение. z yA( y, z) xB(x, y) =

32

=( yA( y, a) yA( y,b) yA( y,c)) B(a, y)B(b, y)B(c, y) =

=A(a, a) A(b, a) A(c, a) A(a,b) A(b,b)A(c,b) A(a, c) A(b,c) A(c,c)

B(a, y)B(b, y)B(c, y).

Спомощью предикатов можно записывать различные математические утверждения.

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

последовательность {xn } имеет пределом число a ( lim xn = a )”.

n→∞

Решение. Запишем данное утверждение с помощью кванторов и обозначим его A :

A = ε N n(ε > 0 → (n > N → xn −a <ε)).

Запишем инверсию данного высказывания:

¬A = ¬ ε N n(ε > 0 → (n > N → xn −a < ε))=

=ε¬ N n(ε > 0 → (n > N → xn −a < ε))=

=ε N¬ n(ε > 0 → (n > N → xn −a < ε))=

=ε N n¬(ε > 0 → (n > N → xn −a < ε)).

По известным формулам, инверсия импликации преобразуется следующим

образом:

¬(K → M )= ¬(¬K M )= ¬¬K ¬M = K ¬M .

Отсюда получаем:

¬A = ε N n((ε > 0) ¬(n > N → xn −a <ε))= = ε N n((ε > 0) (n > N ) ¬(xn −a <ε))= = ε N n((ε > 0) (n > N ) (xn −a ≥ε)).

Утверждение ¬A означает, что lim xn ≠ a , то есть число a не является

n→∞

пределом числовой последовательности {xn }.

В Содержание.

Задачи.

1. Среди следующих предложений выделить предикаты, и для каждого предиката установить местность и область истинности, если X = R . Для двуместных предикатов изобразить область истинности графически.

1)x +2 = 0 .

2)При x = 0 выполняется равенство x −2 = 0 .

3)x3 −8 = 0 .

4)x(x3 −8 = 0).

33

5)x − y =1.

6)x2 −5x +7 .

7)sin 2 x +cos2 x =1.

8)x − y2 ≥ 0 .

9)Однозначное число x является простым.

2.Определить значение высказывания, полученного из трехместного предиката на множестве X .

1)x y z(xz = y), X = N .

2)z x y(xz = y2 ), X = Z .

3)z y x(xy > xz), X = N .

4)x y z(xyz < yz), X = Z .

5)x z y(x + y = z), X = N .

6)x y z(xyz = yz), X = R .

7)z x y(x + y > z + y), X = R .

8)y z x(x2 + y2 = z), X = R .

9)x y z(x( y + z) = xy + xz), X = R .

10)x z y(x + y = z), X = R .

3.Записать инверсию формулы в предваренной нормальной форме.

1)x¬A(x) .

2)x(A(x)¬B(x)).

3)x¬A(x) .

4)x(A(x) → yB( y)).

5)x(A(x)B(x)C(x)).

6)x(A(x) → B(x)).

7)x(A(x) ↔ B(x)).

8)x(A(x) yB( y)).

9)x(A(x) → B(x)) x(C(x) ¬D(x)).

10)x y z(A(x, y, z) → B(x, y, z)).

4.Записать формулу в приведенной форме, если это необходимо, а затем преобразовать к предваренной форме.

1)x zR(x, y, z) → xP(x, y) .

2)x yR(x, y, z) → xP(x, y) .

3)xP(x, y) yQ(x, y) .

4)x yP(x, y) xQ(x, y) .

34

5)yR(x, y) → x zP(x, y, z) .

6)x yP(x, y) x yQ(x, y) .

7)xP(x, y) → x zQ(x, z) .

8)x yP(x, y) ¬x yQ(x, y) .

9)x zP(x, y, z) → ( zR(x, y, z) Q(x, y)).

10)xP(x, y, z) → x zQ(x, y, z) .

5.Найти предикат, не содержащий кванторов, логически эквивалентный данному предикату. Предикаты A и B определены на множестве {a,b,c}.

1)yA(x, y) → x zB(x, z) .

2)x yA(x, y) zB(x, z) .

3)xA(x, y) x zB(x, z) .

4)y xA(x, y) → x zB(x, z) .

5)y xA(x, y) zB(x, z) .

6)xA(x, y) x zB(x, z) .

7)xA(x, y) z xB(x, z) .

8)xA(x, z) → x yB(x, y) .

9)x yA(x, y) zB(x, z) .

10)yA(x, y) x zB(x, z) .

6.Записать с помощью кванторов следующие утверждения и их отрицания.

1)Функция f (x) возрастает на интервале (a,b).

2)Функция f (x) непрерывна на интервале (a,b).

3)Множество A является собственным подмножеством множества B .

4)Точка x0 является точкой экстремума функции f (x) .

5)Функция f (x) достигает наибольшего значения на отрезке [a,b] в точке x0 .

6)Функция f (x) дифференцируема в точке x0 .

7)Бинарное отношение ρ является симметричным.

8)Функция f (x) ограничена на множестве R .

9)Булева функция f (x1, x2 ,..., xk ) самодвойственна.

10)Множества A и B не пересекаются.

7.Доказать эквивалентность

x(P(x) Q(x))= xP(x) xQ(x) .

8.Доказать, что не эквивалентны формулы x(P(x) Q(x)) и xP(x) xQ(x) .

ВОтветы и указания.

ВСодержание.

35