13 1_ОСОБЕННОСТИ ФОРМАЛИЗАЦИИ ЛП

&, , , , , , , 

ОСОБЕННОСТИ ФОРМАЛИЗАЦИИ В ЛОГИКЕ ПРЕДИКАТОВ

НАЧАЛЬНЫЙ КЛАССИЧЕСКИЙ (АРИСТОТЕЛЬ) ПРИМЕР:

Рассуждение:

Все люди смертны. Сократ-человек. Следовательно, Сократ смертен.

В логике высказываний формализация имеет вид:

А, В ╠ С

В логике предикатов рассматривается объектно-предикатная структура:

Ч(х) – х человек, С(х) – х смертен, с- константа «Сократ».

Запись на языке логики предикатов это рассуждение запишется так:

 х (Ч(х)  С(х)) , Ч(с) ╠ С(с)

Пример неполной, но полезной формализации математического понятия.

«Функция f, определенная на множестве M, непрерывна на M, если для каждого x из M и для любого сколь угодно малого положительного ε найдется такое положительное δ, зависящее от ε, что, когда x1 лежит в M и отличается от x меньше, чем на δ, f(x1) отличается от f(x) меньше, чем на ε».

На современном символизме «f непрерывна на M» записывается компактно и изящно:

x є M ε > 0 δ > 0 x1 є M (|x − x1| < δ )  |f(x) − f(x1)| < ε).

ПРИЕМЫ ФОРМАЛИЗАЦИИ

1. «ОГРАНИЧЕНЫЕ» КВАНТОРЫ.

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

Рассмотрим внимательнее утверждение «Все коровы любят сено».

Если универс нашей теории — множество всех живых существ, то напрашиваются два варианта перевода этого утверждения:

x(К(x) & ЛС(x)); (1)

x(К(x) ЛС(x)) (2)

Здесь К означает “ корова”, а ЛС —“ любит сено”.

Из варианта (1) следует, что всякое живое существо, в том числе и автор, и даже уважаемый читатель, является коровой и любит сено,

что, мягко говоря, несколько преувеличено.

Вариант же (2) кажется более многообещающим: коль скоро нам дана корова, она любит сено.

Проверим (2) тщательнее.

Случай, соответствующий “здравому смыслу”, — подстановка вместо x коровы Машки — ничего не дает.

Если М — эта корова, то К(М) истинно, ЛС(М) тоже истинно, и К(М)  ЛС(М), К(М) & ЛС(М) истинны. Итак, “разумный” случай не дает нам возможности отличить правильный вариант перевода на формальный язык от неправильного.

Рассмотрим теперь случаи безумные.

Пусть Ч— уважаемый читатель. Он (она), безусловно, коровой не является и сена не любит. Значит, К(Ч) и ЛС(Ч) ложны, и значение К(Ч)  ЛС(Ч) есть истина.

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

Похоже на то, что если все коровы любят сено, то (2) истинно.

В самом деле, единственный способ опровергнуть (2) — задать такое c, при котором К(c)  ЛС(c) было бы ложно, т. е. К(c) было бы истинно, а ЛС(c)—ложно. Другими словами, чтобы опровергнуть (2), необходимо указать корову, которая сено не любит.

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

Рассмотрим утверждение «некоторые молодые люди—студен-

ты». Есть две бросающиеся в глаза возможности перевода (М означает

“ молодой человек”, С —“ студент”):

x(М(x) & C(x)) (1)

x(М(x)  C(x)) (2)

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

установить, что (2) неправильно.

Итак,

“Все А есть B” переводится x(A(x)  B(x)).

“Некоторые А есть B” переводится x(A(x) & B(x)).

2. МНОГОЭТАЖНОСТЬ.

А) Рассмотрим утверждение: “Все волки и зайцы серы”.

Для него прямо ошибочен перевод

x (В(x) & З(x)  С(x)) ,

(покажите мне хотя бы одно животное, которое было бы одновременно и

волком, и зайцем),

невыразителен, хотя и формально правилен перевод

x  y (В(x) & З(y)  С(x) & C(y))

и лучше всего перевод

x (В(x)  С(x)) & x (З(x)  C(x)) ,

где каждый квантор относится лишь к тем утверждениям, которые он

связывает.

Б) Порядок кванторов очень существенен. Сравним:

x (x є N  y (y є N & y > x)) и

y (y є N & x (x є N  y > x))

3. «НЕПРЯМОТА» ПЕРЕВОДА.

А) Проверить правильность рассуждения:

«Таможенные чиновники обыскивают каждого, кто въезжает в страну, кроме высокопоставленных лиц. Если некоторые люди способствуют провозу наркотиков, то на внутреннем рынке есть наркотик. Никто из высокопоставленных лиц не способствует провозу наркотиков. Следовательно, некоторые из таможенников способствуют провозу наркотиков?»

Введем обозначения предикатов

P1(x):=«x - таможенный чиновник»,

P2(x,y):=«x обыскивает y»,

P3(y):=«y въезжает в страну»,

P4(y):=«y – высокопоставленное лицо»,

P5(y):=«y способствует провозу наркотиков».

Тогда формальная запись суждения имеет вид:

F1=∀y(P3(y) & ¬P4(y) ∀x(P1(x) & P2(x,y))) (?)

F2=∃y(P3(y)&P5(y)) (?)

F3=∀y(P3(y)&P4(y) ¬P5(y))

G=∃y(P1(y)&P5(y))

Б) Пример (Клини). Политик, произнося «Некоторые политики - мошенники», имеет в виду «Неверно, будто все политики - мошенники, но некоторые - мошенники», и делает упор на первой части этого высказывания.

В) Рассмотрим теперь предложение: «Все доисторические ящеры пожирали друг друга». Тут так и напрашивается перевод

x, y(Я(x) & Я(y) П(x, y) & П(y, x)),

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

x (Я(x)  y (Я(y) & (П(x, y) ∨ П(y, x)))) .

4. СУЩЕСТВОВАНИЕ «ЕДИНСТВЕННОГО».

Утверждение «задача имеет единственное решение», «существует единственное x, такое, что A(x)» выражается в форме

xA(x) & x, y (A(x) & A(y)  x = y) .

Но это не самая выразительная запись утверждения о единственности. Гораздо выразительнее

x y(A(y) x = y).

Сказать, что есть не менее двух различных решений задачи, очень просто:

x, y ( (x = y) & A(x) & A(y)) .

Так же просто сказать и то, что иx ровно два:

x, y ((x = y) & z(A(z) z = x ∨ z = y)) .

Упражнения на формализацию

Записать на языке логики предикатов:

1) Все рыбы, кроме акул, добры к детям;

  2) Не все птицы могут летать;

  3)  Ты  можешь  обманывать  кое-кого  все  время,  ты  можешь  обманывать  всех некоторое время, но ты не можешь обманывать всех все время;

  4) Если кто-нибудь может сделать это, то и Джон может;

 

5) Если  всякий  предок  предка  данного  индивидуума  есть  также  предок  того  же  индивидуума,  и  никакой  индивидуум  не  есть  предок  самого  себя,  то должен существовать некто, не имеющий предков;

6) Парадокс сельского парикмахера

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

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

7. Игра «Судоку».

8. Арифметические проблемы:

Гипотеза Гольбаха (каждое четное число есть сумма 2-х простых);

Проблема близнецов (бесконечность пар близнецов);

Нечетное совершенное число;

Бесконечность совершенных чисел.

9. Определения из анализа:

Непрерывная функция. Разрывная функция.

Равномерно непрерывная функция.

10.

(ШБ1) Каждая программа содержит ошибку.

(ШБ2) Если программа не содержит ошибок, то неверен примененный метод.

(ШБ3) Если программа на самом деле полностью и абсолютно правильна, она никому не нужна.