Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

Лекция №11



Тема: ПРЕДИКАТЫ И ОПЕРАЦИИ НАД НИМИ

Основные вопросы, рассматриваемые на лекции:

1. Определение n -местного предиката

2. Область определения и множество истинности предиката

3. Операции над предикатами

Краткое содержание лекционного материала

n - местным предикатом A = P (x 1,…, xn) называется математическое предложение, содержащее n свободных переменных x 1,…, xn. Говорят, что вхождение переменной в предложение или формулу свободно, если переменную можно заменять ее допустимым значением. Синонимы термина предикат: свойство, условие, отношение.

n -местный предикат A = P (x 1,…, xn) при замене всех свободных вхождений переменной xn ее допустимым значением dn обращается в (n -1)-местный предикат B = P (x 1,…, xn -1, dn)= P (x 1,…, xn -1) (n >1). Одноместныйпредикат A = P (x) при замене всех свободных вхождений переменной x ее допустимым значением d обращается в высказывание A = P (d).

Пусть D 1,…, Dn – множества допустимых значений соответственно переменных x 1,…, xn. Множество (декартово произведение)

DP = D 1´…´ Dn ={(d 1,…, dn)| d 1Î D 1,…, dn Î Dn }

всех упорядоченных n -ок элементов множеств D 1,…, Dn называется областью определения n -местного предиката P (x 1,…, xn).

Множеством истинности n -местного предиката P (x 1,…, xn) называется множество MP ={(d 1,…, dnD | P (d 1,…, dn)=1} всех n -ок допустимых значений переменных x 1,…, xn, при которых предикат P (x 1,…, xn) истинен.

Например, если P (x, y) есть x 2+ y 2=13, а DP = N ´ N, то MP ={(2,3),(3,2)}.

Для одноместного предиката P (x) множество истинности есть множество MP ={ d Î DP | P (d)=1}допустимых значений переменной x, при котором предикат P (x) истинен.

Например, если P (x) есть x 2£13, а DP = N, то MP ={1,2,3}.

Используя связки Ø, Ú, Ù, Þ, Û, из данных предикатов P (x 1,…, xn) и Q (x 1,…, xn) с общей областью определения D образуются новые предикаты с той же областью определения D.

Отрицание Ø P (x 1,…, xn) строится из P (x 1,…, xn) при помощи связки Ø, при этом для любой n -ки (a 1,…, anD.

Дизъюнкция P (x 1,…, xnQ (x 1,…, xn) образуется из P (x 1,…, xn) и Q (x 1,…, xn) при помощи связки Ú, при этом для любой n -ки (a 1,…, anD

Конъюнкция P (x 1,…, xnQ (x 1,…, xn) составляется из P (x 1,…, xn) и Q (x 1,…, xn) при помощи связки Ú, при этом для любой n -ки (a 1,…, anD

Легко увидеть, что , и .

Импликация P (x 1,…, xnQ (x 1,…, xn) получается из P (x 1,…, xn) и Q (x 1,…, xn) при помощи связки Þ, при этом для любой n -ки (a 1,…, anD

Эквивалентность P (x 1,…, xnQ (x 1,…, xn) строится из P (x 1,…, xn) и Q (x 1,…, xn) при помощи связки Û, при этом для любой n -ки (a 1,…, anD

Для предикатов, кроме пропозициональных операций Ø, Ú, Ù, Þ, Û, существует операции навешивания кванторов.

Знак $ обозначает слова вида "существует", "некоторые" и т.п.

Знак " обозначает слова вида "все", "для всякого" и т.п.

Квантор существования и общности – это символы $ x и " x с некоторой переменной x.

Навешивание квантора $ xi или " xi (i =1,…, n) к предикату P (x 1,…, xn), с n свободными переменными x 1,…, xn, приводит, соответственно, к предикату $ xiP (x 1,…, xn) или " xi (x 1,…, xn) уже с n -1 свободными переменными x 1,…, xi -1, xi +1,…, xn (переменная xi станет связанной).





Дата публикования: 2015-03-26; Прочитано: 142 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.007 с)...