Список вопросов лекций и лабораторных работ

↑

▷ Содержание

Стр 1 из 6Следующая ⇒

СПИСОК ВОПРОСОВ ЛЕКЦИЙ И ЛАБОРАТОРНЫХ РАБОТ

(ВОПРОС № 1)

1. Логическая модель представления знаний. Префикс. Матрица.

Символы ∀ и ∃ называются соответственно кванторами всеобщности и существования. Запись вида (∀x) читается как «Для всех x», а запись вида (∃x) - как «Существует x».

Вхождение переменной x в формулу называется связанным, если оно совпадает с вхождением в кванторный комплекс (∀x) или (∃x) или находится в области действия этого комплекса, иначе вхождение называется свободным. Если хотя бы одно из вхождений переменной в формулу свободно, то переменная называется свободной в этой формуле. Если хотя бы одно из вхождений переменной в формулу связанно, то переменная называется связанной. Интерпретация формулы F логики предикатов состоит из непустой предметной области D и указания значения всех констант, функциональных символов и предикатных символов, встречающихся в F.

С помощью законов логики предикатов можно любую формулу преобразовать в формулу вида (Q1x1)(Q2x2)…(QNxN) M, где каждое (Qi xi), i = 1, 2, …, N, есть (∀xi) или (∃xi) , а M есть формула, не содержащая кванторов. Формула такого вида называется формулой в предваренной нормальной форме. Последовательность (Q1x1)(Q2x2)…(QNxN) называется префиксом, а M - матрицей формулы в предваренной нормальной форме.

2. Формы представления матрицы. Правила Хорна. Дизъюнкты.

𝑀𝑗= & &…& → ∨ ∨…∨  , где & &…& - посылка или условие вывода, ∨ ∨…∨ - заключение.

Форма дизъюнктов. 𝑀𝑗= ( & &…& )∨ ∨ ∨…∨  

𝑀𝑗= ∨…∨ ∨ ∨ ∨…∨

Форма правил Хорна.

𝑀𝑗=( ∨…∨ )∨

𝑀𝑗= ( & &…& )∨  

𝑀𝑗= & &…& →

Правила Хорна без условий – факты, т.е. истина. → Аj

Правила Хорна без заключений – отрицание фактов, т.е. ложь. & &…& →

3. Сколемская форма. Правила удаления кванторов.

Если формула находится в предваренной нормальной форме и при этом из префикса удалены все кванторы существования, переменные, находившиеся под действием этих кванторов, заменены в матрице символами констант или функциональными символами, а сама матрица находится в КНФ, то говорят, что она представлена в сколемовской стандартной форме. Все переменные должны быть связаны с кванторами всеобщности.

Удаление кванторов существования и замена переменных производится согласно следующему правилу:

1)если левее удаляемого квантора существования нет ни одного квантора всеобщности, то переменная, относящаяся к этому квантору, заменяется на символ константы, отличный от символов констант, имеющихся в матрице;

2).если левее удаляемого квантора существования имеется n кванторов всеобщности, то переменная, относящаяся к этому квантору, заменяется на n-местный функциональный символ, отличный от функциональных символов, уже имеющихся в матрице, аргументами которого будут переменные при кванторах всеобщности, стоящих левее удаляемого квантора существования

4. Приведение к предваренной форме и форме дизъюнктов.

Формула G имеет предваренную нормальную форму, если G(Q1,x1)…(Qn,xn)H, где Q1,…,Qn кванторы, а формула H не содержит кванторов. Например, формула (∀x)(∃y)(P(x,y)&Q(y)) имеет предваренную нормальную форму, а формула (∀x)(T(x)&S(x,y)) не имеет.

Алгоритм приведения к предваренной нормальной форме:

Шаг 1. Исключить эквивалентность и импликацию, пользуясь законами: F→G ≈ F∨G; F↔G ≈ (F→G)&(G→F) ≈ (F∨G) &(G∨F)

Шаг 2. Занести отрицание к атомарным формулам, пользуясь законами:

(F&G) ≈ F∨G;

F ≈ F;

(∀x)F(x) ≈ (∃x)F(x);

(∃x)F(x) ≈ (∀x)F(x).

Шаг 3. С помощью законов вынести кванторы вперед, используя при необходимости переименование связанных переменных.

(∀x)(F(x)&G(x)) ≈ (∀x)(F(x)&(∀x)G(x));

(∃x)(F(x)∨G(x)) ≈ (∃x)F(x)∨(∃x)G(x);

(∀x)(F(x)∨G) ≈ (∀x)(F(x)∨G);

(∃x)(F(x)&G) ≈ (∃x)(F(x)&G), где G не содержит x;

(Q1x)(Q2z)(F(x)∨G(z)) ≈ (Q1x)F(x)∨(Q2z)G(z);

(Q1x)(Q2u)(F(x)&G(u)) ≈ (Q1x)F(x)&(Q2u)G(u).

Переименовать переменные по необходимости.

Таким образом мы получим формулу, которая имеет предваренную форму. Далее приводим её к форме дизъюнктов.

Шаг 4. Бескванторную часть привести к КНФ, используя дистрибутивный закон: F∨(G&H) ≈ (F∨G)&(F∨H);

Шаг 5. Исключить кванторы существования

Шаг 6. Исключить кванторы всеобщности

5. Построение логических моделей по вербальному (естественно-языковому) описанию.

№

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

Примеры предложений

Формальная запись

и

Произошло А и В

А&В

или

Произошло А или В

А∨В

не

Произошло не А

А

либо

Произошло А либо В

А⊕В

Если, … , то

Если происходит А, то происходит и В

А→В

Необходимо

Для А необходимо В

А→В

Достаточно

Для В достаточно А

А→В

Равносильно

Утверждение А равносильно утверждению В

А=В

Тогда и только тогда, когда

А происходит тогда, когда В

А=В

Эквивалентно

Утверждение А эквивалентно утверждению В

А=В

Необходимо и достаточно

Для А необходимо и достаточно В

А=В

Ни и ни

Ни А и ни В

(А ↓В)

6. Интерпретация в логике предикатов. Квантор всеобщности и существования.

Квантор всеобщности - ∀х А(х). (1.для всех. 2.для каждого. 3. для произвольного. 4. для любого. 5. какое бы не было. 6. Все(любой, но не ВСЕ вместе))

Квантор существования - ∃х А(х). (7.существует. 8.найдется. 9.имеется. 10.существует хотя бы для одного. 11.для некоторого(1.некот-й, но

возможно и все. 2.Нек-й, но не все) 12.некоторый(1.некот-й, но возможно и все. 2.нек-й, но не все).

Интерпретация в ЛП

1. Задано непустое мн-во объектов V(область интерпритации).

2. Заданы следующие соответствия:

2.1. Предикатным буквам поставлены в соответствие некоторые

отношения(предикаты), заданные на V.

2.2. Функциональным символам поставлены в соответствие

некоторые операции в V, т.е. функции отображающие V n в V.

2.3. Каждой предметной постоянной поставлен в соответствие

некоторый фиксированный элемент мн-ва в V.

2.4. Символам &, v, ┐,→, ≡,↓,+, ∃, ∀.

3. Считается, что каждая предметная переменная может принимать

любое значение из мн-ва V.

7. Структуры предложений. Преобразование логических выражений и их естественно-языковое представление.

Структуры предложений:

1. Всякое А есть В, Прим: ∀x(A(x) → B(X))

2. Ни одно А не есть В, Пр: ∀x(A(x) → ┐B(X))

3. Некоторое А есть В, Пр: ∃x(A(x) & B(X))

4. Некоторое А не есть В, Пр: ∃x(A(x) & ┐B(X))

Преобразование ЛВ:

1. Всякий студент, подготовившейся к экзамену, успешно его сдает.

∀x(A(x) → B(X))

1. Всякий студент, или не подготовился к экзамену или успешно

его сдает: ∀x(┐A(x) V B(X))

2. Для всякого студента неверно, что подготовился к экзамену и

его не сдал: ∀x ┐(A(x) & ┐B(X))

3. Не существует студента, что подготовился к экзамену и его не

сдал: ┐∃x(A(x) & ┐B(X))

4. Всякий студент, если не сдал экзамен, то к нему не

подготовился: ∀x(┐B(X) → ┐A(x))

8. Формы представления правил Хорна.

𝑀𝑗= & &…& → ∨ ∨…∨  , где & &…& - посылка или условие вывода, ∨ ∨…∨ - заключение.

Форма дизъюнктов. 𝑀𝑗= ( & &…& )∨ ∨ ∨…∨  

𝑀𝑗= ∨…∨ ∨ ∨ ∨…∨

Форма правил Хорна.

𝑀𝑗=( ∨…∨ )∨

𝑀𝑗= ( & &…& )∨  

𝑀𝑗= & &…& →

Правила Хорна без условий – факты, т.е. истина. → Аj

Правила Хорна без заключений – отрицание фактов, т.е. ложь. & &…& →

9. Метод резолюции. Постановка задачи. Резольвента. Нахождение резольвенты. Доказательство теоремы.  Пример с трассировочной таблицей.

Познавательные статьи:



Техника нижней прямой подачи мяча

Комплекс физических упражнений для развития мышц плечевого пояса

Стандарт Порядок надевания противочумного костюма

Общеразвивающие упражнения без предметов