Логика предикатов. Логические следствия. Контрольная работа

Вариант 14 (смотрите демо-файл!)

Задание № 6

1.Пусть C(x) означает «х – нечётное число» Что означают утверждения:
C(12)
C(5)
"xC(x)
Какие из них истинны, какие нет?
2 Введен предикат D(x,y) «х дружит с y».
Как записать утверждения: «У каждого есть друзья» «Петр друг Сергея» Что означает утверждение
"x $y ( D(x,y) ® D(y,x) ) Верно ли оно?
В задании 6 требуется выразить утверждения естественного языка средствами формальной системы Исчисление предикатов 1 порядка. Также необходимо оценить истинность или ложность записанных утверждений в конкретной интерпретации.
Рассмотрим пример.

Пусть предикат О(x, y) означает «х является отцом y - ка» Что означают утверждения:
О(Иван, Василий) О(Иван, Ольга)
$x О(x, Тамара)
"x$y O(y, x)
Какие из них истинны, какие нет?

Решение

В условии задано: предикат О(x, y) означает «х является отцом y - ка» Это означает, что предикат О(x, y) , задающий отношение родства между двумя людьми, имеет интерпретацию. Тогда каждой формуле может быть приписано значение «истина» или «ложь».
О(Иван, Василий)
В предикате О(x, y) переменные x, y заменены на конкретные величины (константы) : «Иван является отцом Василия»

Аналогично, второе утверждение О(Иван, Ольга) получает интерпретацию :
«Иван является отцом Ольги» . Оба выражения примут значение И (Л)

Рассмотрим формулу $x О(x, Тамара) .
О(x, Тамара) означает « х является отцом Тамары». Переменная х связана квантором существования, поэтому формула не содержит свободных переменных. Её смысл: «Существует такой х, который является отцом Тамары», или, короче, «У Тамары есть отец». Такой формуле мы припишем значение Истина.
Последняя формула "x$y O(y, x) не содержит ни одной константы, но обе переменные связаны кванторами:
«Для каждого х найдётся y, такой, что y является отцом х » ( O(y, x) ),

или «У каждого человека есть отец» . Такой формуле мы смело припишем значение Истина.

Задание № 7.

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

1. Пример решения задания

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

Прежде всего, введём предикаты, которые используются в рассуждении. Это предикаты для обозначения свойств «быть первокурсником» и «быть второкурсником»:
P(x) – « x – первокурсник»,
B(х) - « х – второкурсник».
Также введём предикат для обозначения «х проживает в общежитии»: O(x). L(x, y) будет обозначать отношение « x любит y – ка», представленное как двуместный предикат.
При записи формул исчисления предикатов помним: фразы «все», «каждый»
«любой» и т.п. требуют использования квантора всеобщности.
Фразы «некоторый», «кто-то», «найдётся» и т.п. требуют использования квантора существования.
Важно: Если используется квантор всеобщности – связкой между частями формулы обязательно будет импликация. Если используется квантор существования – связкой между частями формулы будет конъюнкция (&).
Например, фраза «Некоторые первокурсники любят всех второкурсников» представляется формулой: $xP(x) & ("y(B(y)®L(x, y))



Формализация рассуждения приведена ниже.
(1) "x(P(x)®"y(B(y)® ØL(x, y)))
(2) "x(O(x)®B(x))



"x(P(x)®"y(O(y)® ØL(x, y)))

Задание № 8

Построить множество дизъюнктов для заданного рассуждения. Для этого привести посылки и отрицание заключения к ПНФ, а затем к Сколемовской стандартной форме. Методом резолюции вывести пустой (тождественно ложный) дизъюнкт из исходного множества дизъюнктов, доказав тем самым справедливость рассуждения. (Рассуждение берётся из задания 7)

1. Пример решения задачи методом резолюции

Доказать следующее утверждение на естественном языке: ”Ни один первокурсник не любит второкурсников. Все живущие в общежитии - второкурсники. Следовательно, ни один первокурсник не любит никого из живущих в общежитии”.



Формализация рассуждения приведена ниже.
"x(P(x)®"y(B(y)®ØL(x,y)))
"x(O(x)®B(x))



"x(P(x)®"y(O(y)®ØL(x,y)))

Докажем рассуждение «от противного», построив логическое произведение посылок и отрицания заключения.

Посылка 1: "x(P(x)®"y(B(y)®ØL(x,y))) = "x(ØP(x)Ú"y(ØB(y)ÚØL(x, y)))
=
= "x"y (ØP(x)Ú ØB(y)ÚØL(x, y)) формула преобразована к ПНФ.
Посылка 2: "x(O(x)®B(x)) = "x(Ø O(x)ÚB(x)) формула преобразована к
ПНФ.
Отрицание заключения: Ø ("x(P(x)®"y(O(y)®ØL(x, y))) ) =
= Ø ( "x(ØP(x)Ú"y(ØO(y)ÚØL(x, y))) ) = Ø ("x"y (ØP(x)Ú ØO(y)ÚØL(x, y)))
= $ x $y Ø(ØP(x)Ú ØO(y)ÚØL(x, y)) (применили правило двойственности кванторов)
$x$yØ(ØP(x)ÚØO(y)ÚØL(x,y)) = $x$y(P(x)&O(y)&L(x,y)) формула преобразована к ПНФ.

Преобразование Сколема и получение множества дизъюнктов.
Посылка 1: ПНФ "x"y (ØP(x)Ú ØB(y)ÚØL(x, y)) при отсутствии кванторов существования совпадает со Сколемовской стандартной формой. Получаем дизъюнкт: ØP(x)Ú ØB(y)ÚØL(x, y)

Посылка 2: ПНФ "x(Ø O(x)ÚB(x)) при отсутствии кванторов существования совпадает со Сколемовской стандартной формой. Получаем дизъюнкт: Ø O(x)ÚB(x)

Отрицание заключения: ПНФ $x$y(P(x)&O(y)&L(x, y))
Применяем два раза преобразование Сколема, вычёркивая кванторы существования и заменяя последовательно переменные x, y константами a, b:
P(a)&O(b)&L(a,b)
Получили три дизъюнкта: P(a), O(b), L(a,b)
Методомрезолюциивывестипустой (тождественно ложный) дизъюнкт из исходного множества, S = {ØP(x)Ú ØB(y)ÚØL(x,y), Ø O(x)ÚB(x), P(a), O(b), L(a,b) }
содержащего пять дизъюнктов, доказав тем самым справедливость рассуждения.
D1: ØP(x)Ú ØB(y)ÚØL(x, y) D2: Ø O(x)ÚB(x)
D3: P(a)
D4: O(b)
D5: L(a, b)



D6: ØB(y)ÚØL(a, y) (резольвента D1 и D3) . Чтобы получить резольвенту, к D1 применяем подстановку : заменяем х на константу а. {x/a}. Получ
D1 {x/a} = ØP(a)Ú ØB(y)ÚØL(a,y) и резолюция с P(a) стала возможна.

D7: B(b) (резольвента D2 и D4). Чтобы получить резольвенту, к D2 применяем подстановку : заменяем х на константу b.

D2 {x/ b} = Ø O(b)ÚB(b) и резолюция с O(b) возможна.
D8: ØL(a, b) (резольвента D6 и D7) Для получения резольвенты к D6 применяем подстановку – заменяем y на константу b:
D6 {y/b} = ØB(b)ÚØL(a,b) D9: ð (резольвента D5 и D8).
Получен пустой дизъюнкт


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


ØP(x)ÚØB(y)ÚØL(x, y) P(a) Ø O(x)ÚB(x) O(b)



ØB(y)ÚØL(a,y) B(b)

ØL(a, b) L(a, b)
ð

Практическое задание 9

Построить линейную разделяющую функцию для объектов двух классов Класс 1 и Класс 2. Координаты точек для каждого класса заданы в таблице (по 3 точки в каждом классе). Предварительно представьте 6 точек на плоскости. Когда решение найдено – нарисуйте прямую, разделяющую классы 1 и 2 в соответствии с полученным уравнением.




Рассмотрим далее пример решения задачи

Пример решения задачи.
Ваше задание представлено в строке:






Изобразим точки на плоскости:




0 | | | | | | | | | | 1 2 3 4 5 6 7 8 9 х1
Классы 1 и 2 линейно разделимы. Найдём разделяющую линейную функцию и нарисуем её график. Алгоритм пересчета коэффициентов описан подробно в лекционном материале.
Цель – получить линейную разделяющую функцию, которая дает положительные значения для точек 1, 2 и 3 и принимает отрицательные значения для точек 4, 5, 6. Функция
должна иметь вид F(X ) = w0 + w1 × x1 + w2 × x2 .


Выполняем итерацию 0. Коэффициенты
w0 = w1 = w2 = 0 .


Выполняем итерацию 1. Выбираем первый объект класса С1 – вектор Х1=<1, 2>.
Значение функции F (X₁ ) = 0 + 0 ×1 + 0 × 2 = 0 , (ошибка классификации произошла в первой
же точке из шести, так как точка <1, 2> принадлежит классу 1 и функция F(<1, 2>) должна дать значение больше нуля, а не нулевое ). Таким образом, по правилу П8 алгоритма необходима коррекция коэффициентов при значении множителя с=1. Вычисляем новые коэффициенты функции:

w¹ = w + c = 0 +1 = 1; w¹ = w + c × x = 0 +1×1 = 1; w¹ = w + c × x
= 0 +1× 2 = 2 . Получаем

0 0 1 1 1 2 2 2

F ¹ (X ) = 1 + x + 2 × x2
. Обратите внимание: величины 1 и 2, которые мы используем при

расчёте новых коэффициентов функции F, это координаты той точки, где произошла ошибка классификации, в нашем случае это точка <1, 2>.
Выполняем итерацию 2. Вычислим последовательно значения F ¹ (X )для элементов выборки:
F ¹(< 1, 2 >) = 1+1×1+ 2 × 2 = 6 > 0; F ¹(< 1, 3 >) = 1+1×1+ 2 × 3 = 7 > 0; F ¹(< 3, 3 >) = 13 > 0 .

Все элементы класса С1 распознаны правильно. Выбираем текущим класс С2.
F ¹(< 4, 1 >) = 1 +1× 4 + 2 ×1 = 7 > 0 - объект распознан неправильно. Необходима коррекция коэффициентов при значении множителя с=-1.

w² = w¹ + c = 1-1 = 0; w² = w¹ + c × x = 1-1× 4 = -3; w² = w¹ + c × x
= 2 -1×1 = 1. Новая

0 0 1 1 1 2 2 2

функция F ² (X ) = x - 3× x1 .

Выполняем итерацию 3. Вычисляем значения функции для элементов выборки
F ² (< 1, 2 >) = 2 - 3×1 = -1 < 0 . Необходима коррекция коэффициентов с поправкой с=1:


w³ = w² + c = 0 +1 = 1; w³ = w² + c × x = -3 +1×1 = -2; w³ = w² + c × x
= 1+1× 2 = 3. Новая

0 0 1 1 1 2 2 2

функция F ³ (X ) = 1 - 2x + 3x2 .

Начинаем новую итерацию с проверки значений F ³ (X ) на элементах выборки:

F ³ (< 1, 2 >) = 5 > 0;
F ³ (< 1, 3 >) = 8 > 0;
F ³ (< 3, 3 >) = 4 > 0 . Переходим к проверке объектов

класса С2:
F ³ (< 4, 1 >) = -4 < 0;
F ³ (< 5, 2 >) = -3 < 0;
F ³ (< 6, 2 >) = -5 < 0 . Все объекты

обучающей выборки разделены правильно, таким образом получена искомая решающая функция
F (X ) = 1 - 2x₁ + 3x₂ . На рисунке дана геометрическая интерпретация решения.









1-2х1+3х2=0










0 | | | | | | | | | | 1 2 3 4 5 6 7 8 9 х1

Для особенно ленивых ниже приведён алгоритм.
Рассмотрим алгоритм построения линейных решающих функций. Линейная
n

функция имеет следующий вид:
D(X ) = w0 + å wj × x j . Цель алгоритма – найти
j =1

коэффициенты
wj решающей функции
D(X )
методом последовательного уточнения.

Рассмотрим случай двух классов (выше было показано, какими приемами можно свести к
этому случаю вариант нескольких классов). Основой для вычисления коэффициентов wj
~
является анализ обучающей выборки X , где известна заранее принадлежность объектов
~
X классу 1 или классу 2. Далее эти два класса обозначим С1 и С2.
Решающая функция считается построенной, если все объекты обучающей выборки
~
X распознаются этой функцией правильно, то есть D(X ) > 0 , если X Î C₁ , и,
соответственно, D(X ) < 0 , если X Î C2 . Коррекция коэффициентов решающей функции
выполняется по следующему правилу: коэффициенты решающей функции увеличиваются при неправильном распознавании объекта из класса С1, уменьшаются при неправильном распознавании объекта из класса С2 и остаются без изменения, если распознавание идет правильно. Если на некотором шаге произойдет корректировка коэффициентов решающей функции, счетчик правильно распознанных объектов, обозначаемый далее как сч, сбрасывается в ноль, поскольку мы перешли к новой функции и теперь ее надо проверить на всех элементах обучающей выборки.
Алгоритм завершается, когда окажется, что построенная решающая функция D(Х) правильно распознает все объекты обучающего множества.


Алгоритм

1. X

   1

   Получить обучающую выборку ~ = (X , X , …, X ), элементы которой

2 M
принадлежат непересекающимся классам С1 или С2.

1. Установить в ноль счетчик правильно распознанных объектов: сч=0.
2. Установить номер итерации равным нулю: к=0.

1. Задать начальные значения коэффициентов

wj в решающей функции (например,

wj = 0
для
j = 1, 2, …, n ). Получим решающую функцию
D0 (X ) .

1. Выбираем класс С1 в качестве текущего класса.
2. Переход к новой итерации: к=к+1.

1. Выбрать очередной объект

X _k текущего класса (класса С1). Если класс С1

исчерпан, объявить текущим классом класс С2 выбрать первый объект этого класса.

1. Вычислить новые значения коэффициентов решающей функции на итерации к:

^k = w^k-1 + c × x , где с – множитель, определяемый из условия

ì n k -1

ï 1,
ï
ï
å w j j =0
n
× xkj £ 0,
k -1
и X k ÎC1 ;

c = í
ï
- 1,
å w j j =0
× xkj > 0,
и X k ÎC2 ;

ï0 при правильном
ïî
распознавании.

1. Если с=0, сч=сч+1 (увеличиваем на 1 число правильно распознанных объектов), иначе сч=0.

~

1. Если сч=М – общему числу объектов обучающей выборки X , то КОНЕЦ, иначе

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