Контрольная работа по "Математическая логика и теория алгоритмов"

4. Рассмотрим вывод с использованием линейной стратегии. В начале выпишем и пронумеруем дизъюнкты исходного множества:

1. p Ú q;
2. Øq Ú Ør Ú Øs;
3. r;
4. Øp;
5. Ør Ú s;
6. p Ú Ør Ú Øs (1, 2);
7. p Ú Øs (3, 6);
8. Øs (4, 7);
9. s (3, 5);
10. F (8, 9).

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

 

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

м) Судья  Джонс не восхищается ни одним  жуликом.

Решение:

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

      P(x) – “ x – судья”;

     Q(x) – “x – жулик”;

     R(x, y) – “x восхищается у”;

     d – “Джонс”.

Окончательно  запишем формулу: P(d) & "xØ(Q(x) & R(d, x)). 

4.2 Указать все подформулы, а также области действия квантификаций, свободные и связанные вхождения всех переменных в следующих формулах:

г) S(t, w) Ú $x"w[(Y(x, w) ® X(x)) ® Z(w)]

      Решение:

1. Перечислим все подформулы:

S(t, w);

$x"w[(Y(x, w) ® X(x)) ® Z(w)];

"w[(Y(x, w) ® X(x)) ® Z(w)];

(Y(x, w) ® X(x)) ® Z(w);

Y(x, w) ® X(x);

Y(x, w); X(x); Z(w).

2. Области действия квантификаций:

$x – (Y(x, w) ® X(x)) ® Z(w);

"w – (Y(x, w) ® X(x)) ® Z(w).

3. Вхождения переменных:

Переменная  x имеет только 3 связанных вхождения в квантификаторе $x и предикатах Y(x, w) и X(x) и не имеет свободных. Переменная w имеет только три связанных вхождения в квантификаторе "w и предикатах Y(x, w) и Z(w) и одно свободное в предикате S(t, w). Переменная t имеет только одно свободное вхождение в предикате S(t, w). 
 

5.1 Выполнить сколемизацию следующих формул, представленных в предваренной форме:

б) "v"w"t$z[(Z(w, t) Ú S(z)) « (X(v) & ØS(w))]

Решение:

1. Поставим каждой $-квантифицированной переменной функциональную форму от предшествующих ей в префиксе "-квантифицированных переменных:

z – f(v, w, t).

2. Подставим в формулу функциональные формы:

"v"w"t$z[(Z(w, t) Ú S(f(v, w, t))) « (X(v) & ØS(w))]

3. Удалим $-квантификацию:

"v"w"t[(Z(w, t) Ú S(f(v, w, t))) « (X(v) & ØS(w))]

Получили  Сколемовскую форму. 

5.2  Преобразовать следующие формулы в клаузальную форму:

    г) Z(t, w) Ú Ø$x"w[Ø(X(w) Ú S(x)) ® ØY(w)]

Решение:

Сначала получим предваренную форму:

1. Исключим связки импликации и эквивалентности:

    Z(t, w) Ú Ø$x"w[ØØ(X(w) Ú S(x)) Ú ØY(w)]

2. Переименование и удаление ненужных квантификаций:

Z(t, w) Ú Ø$x"u[ØØ(X(u) Ú S(x)) Ú ØY(u)]

3. Сужение области действия отрицаний и снятие двойных отрицаний:

      Z(t, w) Ú "x$u[ØX(u) & ØS(x) & Y(u)]

4. Перенос квантификаций в начало формулы:

"x$u (Z(t, w) Ú [ØX(u) & ØS(x) & Y(u)])

Получена  предваренная форма. Получим из нее  скорлемовскую форму:

5. Поставим каждой $-квантифицированной переменной функциональную форму от предшествующих ей в префиксе "-квантифицированных переменных:

u = f(x)                                                                                                                                             

6. Подставим в формулу функциональные формы и удалим $-квантификацию:

"x(Z(t, w) Ú [ØX(f(x)) & ØS(x) & Y(f(x))])

    Получили  Сколемовскую форму.

7. Приведем к КНФ:

   "x((Z(t, w) Ú ØX(f(x))) & (Z(t, w) Ú ØS(x)) & (Z(t, w) ÚY(f(x))))

   Поскольку все переменные связаны "- квантификациями, префикс может быть опущен.

   Имеем множество дизъюнктов (каузальную форму):

   {Z(t, w) Ú ØX(f(x)); Z(t, w) Ú ØS(x); Z(t, w) ÚY(f(x))} 

5.3. Записать следующие предложения в виде формул логики предикатов и преобразовать их в клаузальную форму:

   в) Если для любых трех чисел одно из них равно сумме двух других, то существуют  два числа, одно из которых является квадратом другого.

Решение:

1. Запишем формулу.

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

      f(x, y) – “x + y”;

      g(x) – “x²”

      P(x, y) – “ x = y”.

   Окончательно  запишем формулу:

   "x"y"z (P(f(x, y), z) Ú P(f(x, z), y) Ú P(f(y, z), x)) ®$x$yP(g(x), y).

2. Исключим связки импликации и эквивалентности:

    Ø"x"y"z (P(f(x, y), z) Ú P(f(x, z), y) Ú P(f(y, z), x)) Ú $x$yP(g(x), y))

3. Переименование и удаление ненужных квантификаций:

Ø"x"y"z (P(f(x, y), z) Ú P(f(x, z), y) Ú P(f(y, z), x)) Ú $u$vP(g(u), v))

4. Сужение области действия отрицаний и снятие двойных отрицаний:

$x$y$z (ØP(f(x, y), z) & ØP(f(x, z), y) & ØP(f(y, z), x)) Ú $u$vP(g(u), v))

5. Перенос квантификаций в начало формулы: