Методические указания к лабораторной работе 10 для студентов по специальности 1-53 01 02 «Автоматизированные системы обработки информации»


Скачать 203.93 Kb.
НазваниеМетодические указания к лабораторной работе 10 для студентов по специальности 1-53 01 02 «Автоматизированные системы обработки информации»
Дата публикации28.10.2013
Размер203.93 Kb.
ТипМетодические указания
referatdb.ru > Информатика > Методические указания
ГОСУДАРСТВЕННОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«БЕЛОРУССКО-РОССИЙСКИЙ УНИВЕРСИТЕТ»

Кафедра "Автоматизированные системы управления"

МАТЕМАТИЧЕСКИЕ МОДЕЛИ ИНФОРМАЦИОННЫХ ПРОЦЕССОВ И УПРАВЛЕНИЯ

Методические указания

к лабораторной работе 10 для студентов по специальности 1-53 01 02

« Автоматизированные системы обработки информации»

Могилев 2010

УДК 621.01

ББК 36.4

И87
Рекомендовано к опубликованию

учебно-методическим управлением

ГУВПО «Белорусско-Российский университет»
Одобрено кафедрой «Автоматизированные системы управления»

«11» мая 2010 г. протокол №8

Составитель канд. техн. наук, доц. А.И. Якимов
Рецензент канд. техн. наук, доц. Г.С. Леневский
Изложены последовательность выполнения и варианты заданий для лабораторной работы по нечеткой логике.
Учебное издание

^ МАТЕМАТИЧЕСКИЕ МОДЕЛИ ИНФОРМАЦИОННЫХ ПРОЦЕССОВ И УПРАВЛЕНИЯ



Ответственный за выпуск

С.К. Крутолевич

Технический редактор

А.Т. Червинская

Компьютерная верстка

Н.П. Полевничая


Подписано в печать . Формат 60х84/16. Бумага офсетная. Гарнитура Таймс.

Печать трафаретная. Усл.печ.л. . Уч.-изд.л. . Тираж 65 экз. Заказ №
Издатель и полиграфическое исполнение

Государственное учреждение высшего профессионального образования

«Белорусско-Российский университет»

ЛИ № 02330/375 от 29.06.2004 г.

212030, г. Могилев, пр. Мира, 43





© ГУВПО «Белорусско-Российский университет», 2010

^ ЛАБОРАТОРНАЯ РАБОТА 10.
ЛОГИКА ПРЕДИКАТОВ
Цель работы: Изучить предикаты и их применение в алгебре, булеву алгебру предикатов.
Порядок выполнения работы.

  1. Изучить теоретические сведения.

  2. Получить задание у преподавателя.

  3. Исследовать булеву алгебру предикатов.

  4. Сделать выводы по результатам исследований.

  5. Оформить отчет.


Требования к отчету.

  1. Цель работы.

  2. Постановка задачи.

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

  4. Выводы.


Теоретические сведения.
1. Предикаты

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

Рассмотрим пример: «х просто число». Это выражение не является высказыванием, но если в нем переменную х заменить на определенное число, то получим высказывание. Причем при замене х на число 3 получим истинное высказывание, тогда как при замене х на 8 получим ложное высказывание.

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

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

Чтобы задать n-местный предикат P(x1,x2,…,xn), следует указать множества X1,X2,…,Xn – области изменения переменных x1,x2,…,xn, причем чаще всего рассматривается случай, когда X1=X2=…=Xn.

С теоретико-множественной точки зрения предикат определяется заданием подмножества М в декартовом произведении X1X2…Xn.

Переменные x1,x2,…,xn называются предметными переменными. Элементы множеств X1,X2,…,Xn называют предметами. Множество М – множество кортежей длины n < x1,x2,…,xn > называется полем предиката P (x1,x2,…,xn).

Будем обозначать предметные переменные малыми буквами конца латинского алфавита (иногда будем снабжать эти буквы индексами) x, y, z, …, x,1x2, …, xn.

Предметы из множеств X1,X2,…,Xn – малыми буквами начала латинского алфавита a, b, c, …, a1, a2, a3….

Предикаты – большики буквами латинского алфавита с приписанными предметными переменными или без них A(x,x), B, F(x,y), P(x1, …,xn).

Числа переменных будем указывать как верхний индекс у предиката: Pk(x1, x2, …, xk) – k местный предикат, Q2(x,y) – двуместный предикат, P(x) – одноместный предикат.

Итак, k-местный предикат – Pk(x1, x2, …, xk) есть функция, предметные переменные которой принимают значения: истина (1) или ложь (0), т.е.

Pk(x1, x2, …, xk) : Mk  {1, 0}.

Например, если Х – множество действительных чисел, то x2>1 – одноместный предикат.

Если X, Y – множества действительных чисел, то xy=5 – двуместный предикат.

Предикат называется разрешимым, если существуют такие кортежи, компоненты которых обращают предикат в истинное высказывание.

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

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

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

Например, если к предикатам «x=y» и «x^ 2. Применение предикатов в алгебре

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

Типичным примером является уравнение, например, х2 – 3x + 2 = 0. Свободная переменная может принимать здесь любое числовое значение. Для некоторых чисел х (а именно х = 1, х = 2) утверждение, содержащееся в этом уравнении, истинно, в остальных оно ложно. В подобных случаях, когда истинность или ложность предиката зависит только от значения, принимаемого свободной переменной х, множество допустимых значений х можно рассматривать как множество логических возможностей U, а множество всех значений этой переменной, при которых высказывание истинно – как его множество истинности.

В приведенном выше примере множество U состоит из всех действительных чисел, а множеством истинности является множество {1, 2}.

В результате введения понятия множества истинности для предикатов мы сможем сказать, что решить уравнение – значит найти один элемент или все элементы его множества истинности. При решении системы двух уравнений у нас имеется предикат, представляющий конъюнкцию двух уравнений. Поэтому мы ищем пересечение двух множеств истинности. Если это пересечение пусто, то система уравнений не имеет решений. Такие уравнения называются несовместными, поскольку их множества истинности не имеют общих элементов х.

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

Если Uмножество действительных чисел, то множество истинности неравенства х < 0 состоит из всех отрицательных действительных чисел. Множество же истинности неравенства х > –3 состоит из всех действительных чисел, больших, чем –3. Если мы потребуем, чтобы эти неравенства выполнялись одновременно, то множеством истинности будет множество, являющееся пересечением двух исходных множеств, т. е. все действительные числа между –3 и 0.

Понятие множества истинности предиката позволяет выяснить, чем разнятся между собой уравнения и тождества. Когда мы решаем уравнение, мы тем самым ищем один из элементов множества истинности этого уравнения или все его элементы. Если же мы доказываем тождество, то тем самым утверждаем, что оно справедливо для всех х. Таким образом, тождество представляет собой уравнение, множеством истинности которого является универсальное множество U, т. е. является логически истинным или тождественно истинным.
^ 3. Булева алгебра предикатов

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

1. 

2. PQ=QP

3. PQ=QP

4. P(QR)=(PQ)R

5. P(QR)=(PQ)R

6. P(QR)=(PQ)(PR)

7. P(QR)=(PQ)(PR)

8. 

9. PP=P; PP=P

10. P1=1; P0=0; P0=P; P1=P; 

11. P(PQ)=P

12. P(PQ)=P
4. Кванторы

Помимо операций алгебры высказываний, в логике предикатов есть две операции, которые связаны с природой предикатов. Пусть дан предикат P(x), зависящий от одной переменной и определенный на поле М.

а) Выражение (x)P(x) означает высказывание, истинное только в том случае, когда предикат P(x) истинен для всех предметов из поля М. Выражение (x)P(x) читается «для всякого x, P(x)», здесь символ  - квантор общности.

б) Выражение (x)P(x) означает высказывание, истинное только в том случает, когда предикат P(x) истинен хотя бы для одного предмета из поля М. Выражение (x)P(x) читается «существует x, что P(x)»; символ  - квантор существования.

Рассмотрим примеры применения операций квантирования к предикатам. Пусть даны предикаты над полем натуральных чисел:

  1. x2=x·x, тогда (x)( x2=x·x) – истинное высказывание;

  2. x+2=7, тогда (x)(x+2=7) – ложное высказывание; а (x)(x+2=7) – истинное высказывание;

  3. x+2=x, тогда (x)(x+2=x) – ложное высказывание.

Название

Прочтение

Обозначение

Квантор общности

«все», «всякий», «каждый», «любой»



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

«хотя бы один», «найдется», «существует»




Квантор общности - это оператор, приводящий в соответствии любому заданному предикату y=P(x) такую двузначную логическую переменную z, которая принимает значение 1 тогда и только тогда, когда y=1 при всех значениях х.

Квантор существования – это оператор, приводящий в соответствии любому одноместному предикату y=P(x) такую двузначную логическую переменную z, которая принимает значение 0 тогда и только тогда, когда y=0 при всех значениях х.
Рассмотрим некоторые общие свойства введенных операторов.

В соответствии с определениями кванторов логическая переменная z в выражениях


уже не является функцией предметной переменной х.

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

Например, в предикате

(x)A(x,y)(z)B(z,v)
переменные x и z – связанные, а y и v – свободные.

Если квантор общности или квантор существования применяется не к одноместному предикату, а к какому-нибудь k-местному предикату, то в результате этого получается снова предикат, но за счет связывания одной предметной переменной получаемый предикат будет (k-1)-местным.
^ 5. Формулы логики предикатов

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

W(x1, …,xn); U(x,y), … .

Применяя к переменным предикатам операции , , , , , , , получим формулы логики предикатов, т.е. формулой логики предикатов называется выражение, составленное из переменных предикатов с помощью логических операций и кванторов и обращающееся в конкретный предикат при подстановке вместо переменных конкретных предикатов.

Например, ((x)W(x,y)B)U(z) – формула логики предикатов.

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

Сформулируем следующие правила.

  1. Формула логики предикатов называется атомарной, т.е. элементарной, если в ней нет связанных переменных.

  2. Пусть F – формула, тогда F – тоже формула. Свободные и связанные переменные формулыF – это соответственно свободные и связанные переменные формулы F.

  3. Пусть F и G – формулы, причем в них нет предметных переменных, которые были бы связаны в одной формуле и свободны в другой.

Тогда FG, FG, FG, FG – формулы, в которых свободные переменные формул F и G остаются свободными, а связанные - связанными.

  1. Пусть F – формула, содержащая свободную переменную х. Тогда (x)F, (x)F – тоже формулы, в которых переменная х связана, а остальные свободные переменные, входящие в F, остаются свободными.

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

Значение формулы определено лишь тогда, когда задана какая-то интерпретация входящих в нее символов. Под интерпретацией понимаю систему М = , состоящую из непустого множества М и соответствия f, которое сопоставляет каждой формуле определенный предикат. При заданной интерпретации предметные переменные пробегают множество М, а логические символы и символы кванторов имеют свой обычный смысл.
^ Индивидуальные задания

Задача 1

Пусть х {люди}, у {вещи, которые можно читать и писать}. На этих областях определения заданы предикаты:

P(x): x – профессор,

S(x):x – студент,

V(x):x – поэт,

R(x,y): x пишет y,

W(x,y): x любит читать y,

N(y):y – роман,

К(y):y – конспект,

C(y):y – стихи,

U(y): y – учебник,

L(y):y – письмо,

H(y):y – шпаргалка.

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

Некоторые учебники представляют собой конспекты - y(U(y)&K(y));

Ни один роман не является учебником - y(N(y)U(y));

Каждый читает какие-нибудь учебники - xy(U(y)&W(x,y));

Некоторые студенты читают только учебники - x(S(x)&y(W(x,y)U(y)));

Пушкин писал и стихи, и романы - y(C(y)N(y)R(Пушкин, y));

Студент Боб не пишет письма – S(Боб)&y(L(y)R(Боб, y));

Студент Боб читает только конспекты – S(Боб)&y(W(Боб, y)K(y));

Любой поэт пишет письма - x(V(x)y(L(y)R(x,y))).
Задания.

  1. Некоторые романы написаны в стихах.

  2. Ни один учебник не написан в стихах.

  3. Все конспекты – учебники.

  4. Некоторые стихи – письма.

  5. «Евгений Онегин» - это роман в стихах.

  6. Никто не любит писать письма.

  7. Некоторые люди пишут стихи.

  8. Те, кто пишет стихи, - поэты.

  9. Все поэты любят читать стихи.

  10. Все студенты любят читать учебники.

  11. Все студенты пишут конспекты.

  12. Некоторые студенты пишут только шпаргалки.

  13. Никто из студентов не пишет учебники.

  14. Некоторые профессора, а также студенты, пишут стихи.

  15. Некоторые не любят читать никаких учебников.

  16. Студент Том любит читать учебники.

  17. Профессор Джонс – поэт.

  18. Шекспир писал только стихи.

  19. Каждый любит читать какие-либо стихи.

  20. Каждый, кто любит читать какие-либо стихи, любит читать стихи Шекспира.

  21. Только студенты пишут конспекты.

  22. Профессора пишут учебники.

  23. Ни один профессор не пишет шпаргалки.

  24. Студенты, которые пишут конспекты, не пишут шпаргалки.

  25. Поэты пишут стихи.

  26. Поэты пишут только стихи.

  27. Некоторые поэты пишут и стихи, и романы.

  28. Все пишут письма.

  29. Только поэты пишут только стихи.

  30. Любой поэт любит читать свои стихи.


Задание 1. Построить таблицы истинности на области интерпретации D={1,2}.

Пример. У =xy(P(x)Q(y)R).

Предикаты P(x), Q(y) на области интерпретации D={1,2} принимают следующие значения:

x

P1

P2

P3

P4

1

F

F

T

T

2

F

T

F

T




y

Q1

Q2

Q3

Q4

1

F

F

T

T

2

F

T

F

T


R – замкнутая формула, т.е. высказывание, которое принимает значение T и F.

Поскольку предикат P(x) принимает 4 значения, предикат Q(y) – 4 значения, формула R-2 значения, и в формуле Е нет свободных переменных, ее таблица истинности будет состоять из 442=32 строк. Очевидно, что если |R|=T, то |E|=T, поэтому остается вычислить значение формула на оставшихся 16 интерпретациях формулы при |R|=F.

Пусть |R|=F. Рассмотрим вычисление значения формулы на интерпретации P=P1 и Q=Q2.


Пусть P=P2 и Q=Q1. Тогда


Аналогично находятся остальные значения формулы Е, которые приведены ниже в таблице.


P

P1

P1

P1

P1

P2

P2

P2

P2

P3

P3

P3

P3

P4

P4

P4

P4

Q

Q1

Q2

Q3

Q4

Q1

Q2

Q3

Q4

Q1

Q2

Q3

Q4

Q1

Q2

Q3

Q4

E

T

T

T

F

F

F

F

F

F

F

F

F

F

F

F

F


Задания.

  1. xy(P(x)Q(y)R);

  2. x(y(RP(x) Q(y)));

  3. x(Ry(P(x) Q(y)));

  4. x(Ry(Q(y)P(x)));

  5. x(P(x) y(R Q(y)));

  6. x(P(x) y(Q(y) P(x)));

  7. x(P(x)&y(Q(y) R));

  8. x(P(x) y(Q(y) R) S);

  9. x(P(x)& y Q(y)) x P(x);

  10. xy(P(x) Q(y) Q(y));

  11. x(P(x)& y(Q(y) P(x)));

  12. x(y(P(x) R(y))Q);

  13. x(P(x)& z R(z) y Q(y));

  14. x((P(x)y Q(y))&P(x));

  15. y(P(y) xQ(x) P(y));

  16. y(P(y) x R(x))Q;

  17. xy(P(x) Q(y)) R;

  18. x P(x) y Q(y) R;

  19. x(P(x) y Q(y) R);

  20. x(y(RP(x) Q(y)));

  21. x(P(x) y(Q(y) P(x)));

  22. y(x P(x) Q(y) Q(y));

  23. x(P(x)& y(Q(y) P(x)));

  24. x(y(P(x) (RQ(y))));

  25. x((P(x) y Q(y))&P(x)).


Задача 5. Основные аксиомы натуральных чисел таковы:

А1: Для каждого числа существует одно и только одно число, непосредственно следующее за ним.

А2: Нет числа, за которым непосредственно следует 0.

А­3: Для каждого числа, отличного от нуля, существует одно и только одно непосредственно предшествующее ему число.

Пусть f(x) и y(x) представляют соответственно число, непосредственно следующее за х и непосредственно предшествующее х.

Пусть «х равно у» - предикат, обозначенный через Е(х,у). Записать аксиомы с помощью формул логики предикатов.

Решение. А1: (x)(y)E(y, f(x))( z)(E(z, f(x))E(y, z)),

A2:

A3: (x)
Задача 6. Определите значение формул:

а) (x)P(x); б) (x)

в интерпретации М=, где М={1,2}: f: P(1) – истина; P(2) – ложь.

Решение.

а) (x)P(x) – ложь, так как P(x) – не истина как для х=1, так и для х=2;

б) (x) – истина, так как  в этой интерпретации истина.
Задача 7. Оцените формулу (x)(y)P(x,y) в интерпретации М{1,2}

P(1,1)

P(1,2)

P(2,1)

P(2,2)

И

Л

Л

И


Решение. Если х=1, то существует у=1 такой, что P(1,y) есть истина.

Если х=2, также существует такой у, что P(2,y) – истина.

Следовательно, в указанной интерпретации для каждого х из М существует такое значение у, что P(x,y) есть истина, т.е. (x)(y)P(x,y) есть истина в этой интерпретации.
Задача 8. Рассмотрим формулу G: (x)P(x)Q(f(x), a), здесь а – константа, f – одноместная функция, P – одноместный предикат, Q – двуместный предикат. f(2)=1; P(1) – Л; P(2) – И; Q(1,1) – И; Q(1,2) – И; Q(2,1) – Л; Q(2,2) – И. Оцените эту формулу.

Решение. Если х=1, то

P(x)Q(f(x), a)=P(1)Q(f(1), a)=P(1)Q(2,1)=ЛИ=И.

Если х=2, то

P(x)Q(f(x), a)=P(2)Q(f(2), a)=P(2)Q(2,1)=ИИ=И.

Так как P(x)Q(f(x), a) истинно для всех х из области М, то формула (x)(P(x)Q(f(x), a)) истинно в заданной интерпретации.
Задача 9. Используя интерпретации из задачи 8, оцените следующие формулы:

а) (x)(P(f(x))Q(x, f(a)));

б) (x)(P(x)Q(x, a));

в) (x)(у)(P(x)Q(x,у)).

Ответ: а) – истина; б) – ложь; в) – ложь.
Задача 10. Рассмотрим формулы

F1: (x)(P(x)Q(x));

F2: P(a).

Докажите, что Q(a) есть логическое следствие формул F1 и F2.

Решение. Рассмотрим любую интерпретацию. Из определения следует, что формула есть логическое следствие формул F1 и F2 тогда и только тогда, когда для каждой интерпретации данная формула истинна, если F1F2 – истина.

Рассмотрим любую интерпретацию, которая удовлетворяет

(x)(P(x)Q(x))P(a).

В этой интерпретации P(a) – истина.

Пусть Q(a) не является истиной в этой интерпретации, тогда Q(a)=P(a)Q(a) – не истина. Это значит, что (x)(P(x)Q(x)) – ложь, что невозможно. Следовательно, Q(a) должно быть истиной в каждой интерпретации, которая удовлетворяет (x)(P(x)Q(x))P(a). Это означает, что Q(a) есть следствие из F1 и F2.
Задача 11. Докажите следующее:

  1. (x)P(x) (у) - противоречива (невыполнима), т.е. не существует интерпретации, удовлетворяющей этой формуле.

  2. P(a) – непротиворечива (выполнима), т.е. существует такая интерпретация, что формула истинна в этой интерпретации.

  3. а) (x)P(x) (у)P(y), б) (x)P(x) (у) общезначимы, т.е. не существует никакой интерпретации, которая удовлетворяет формулам.


^ Индивидуальные задания

Вариант

Задание 1

Задание 2

1

1(30)

2(18)

2

1(20)

2(22)

3

1(24)

2(14)

4

1(17)

2(20)

5

1(29)

2(21)

6

1(21)

2(13)

7

1(19)

2(17)

8

1(27)

2(24)

9

1(23)

2(15)

10

1(28)

2(12)

11

1(22)

2(19)

12

1(26)

2(12)

13

1(19)

2(25)

14

1(25)

2(16)

15

1(18)

2(23)

Контрольные вопросы

  1. Что называется предикатом? Приведите примеры предикатов.

  1. Какой предикат называется разрешимым, тождественно истинным, тождественно ложным?

  2. Перечислите операции, которые можно осуществить над предикатами. Как применяются предикаты в алгебре? Что такое множество истинности предиката?

  1. Из чего состоит алфавит логики предикатов? Что такое квантор?

  2. Что называется формулой логики предикатов?

  3. Сформулируйте основные правила построения формул.

  4. В чем состоит смысл термина «интерпретация» в логике предикатов?

Похожие рефераты:

Методические указания к лабораторной работе 14 для студентов по специальности...
Изложены последовательность выполнения и варианты заданий для лабораторной работы по нечеткой логике
Методические указания к лабораторной работе 12 для студентов по специальности...
Изложены последовательность выполнения и варианты заданий для лабораторной работы по нечеткой логике
Методические указания к лабораторной работе 8 для студентов по специальности...
Изложены последовательность выполнения и варианты заданий для лабораторной работы по нечеткой логике
Методические указания к лабораторной работе 1 для студентов по специальности...
Изложены последовательность выполнения и варианты заданий для лабораторной работы по нечеткой логике
Методические указания к лабораторной работе 7 для студентов по специальности...
Изложены последовательность выполнения и варианты заданий для лабораторной работы по нечеткой логике
Методические указания и задания контрольной работе №1 для студентов...
Компьютерные информационные технологии. Методические указания и задания к контрольной работе для студентов заочной формы обучения...
Методические указания по выполнению курсового проекта для студентов...
Методические указания по выполнению курсового проекта для студентов специальности 1-53 01 02 «Автоматизированные системы обработки...
Методические указания к самостоятельной работе студентов специальности...
Изложены последовательность выполнения и варианты заданий для самостоятельной работы по дисциплине «Математические модели информационных...
Методические указания к лабораторным работам для студентов специальности...
В методических указаниях изложены этапы проектирования систем обработки информации с использованием case-средств. Предназначены для...
Методические указания по выполнению лабораторных и контрольных работ...
Содержат задания к контрольной работе, методические указания по выполнению контрольной и лабораторных работ

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
referatdb.ru
referatdb.ru
Рефераты ДатаБаза