Дискретная математика. Элементы теории задачи и упражнения. Часть 2. Булгакова И.Н - 61 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

Составители: 

Рубрика: 

Операция замыкания . Основные замкнутые классы .
__________________________________________________________________________________________
107
Предложение или утверждение, содержащее одно или несколько пе-
ременных, при подстановке вместо которых конкретных значений из неко-
торых множеств мы получаем высказывание (истинное или ложное), назы-
вается предикатом . Количество переменных , от которых зависит преди-
кат, называется местностью или арностью.
Пусть
n
M,,M,M K
21
— множества элементов произвольной приро -
ды.
Определение 1:
n
-местным предикатом называется функция
(
)
n
x,,x,xP K
21
, зависящая от
n
переменных , определенная на множестве
n
MMMM
×
×
×
=
K
21
и принимающая на этом множестве значение
1(истина) или 0 (ложь).
Например,
(
)
xP
= [натуральное число
x
кратно 5] — одноместный
предикат:
(
)
,P 04
=
(
)
,P 115
=
(
)
,P 011
=
(
)
.P 120
=
(
)
=
y,xQ
[ город
x
нахо -
дится на территории государства y] — двухместный предикат:
(
)
,Россия,МоскваQ 1
=
(
)
,Венгрия,ПарижQ 0
=
(
)
.Франция,ПарижQ 1
=
Само высказывание считается нуль-местным предикатом.
Переменные
n
x,,x,x K
21
, от которых зависит предикат, называются
предметными переменными. Конкретные значения предметных перемен -
ных называются предметными константами.
Множество
M
, на котором задан предикат, называется областью
определения предиката.
Множество ME
p
⊂
, на котором предикат принимает только ис-
тинные значения, называется множеством истинности предиката
(
)
n
x,,x,xP K
21
:
(
)
(
)
{
}
1
2121
=∈=
nnp
a,,a,aPMa,,a,aE KK
.
Различают четыре типа предикатов:
1. Предикат
(
)
n
x,,x,xP K
21
называется тождественно истинным на
множестве
n
MMMM
×
×
×
=
K
21
, если ME
p
=
, т.е. если на любом
наборе
(
)
Ma,,a,a
n
K
21
предикат принимает значение 1 (истина).
2. Предикат
(
)
n
x,,x,xP K
21
называется тождественно ложным на
множестве
M
, если
∅
=
p
E , т.е. если на любом наборе значений пере -
менных предикат принимает значение 0 (ложь).
3. Предикат
(
)
n
x,,x,xP K
21
называется выполнимым , если его множест -
во истинности
p
E не пусто:
∅
≠
p
E .
4. Предикат
(
)
n
x,,x,xP K
21
называется опровержимым , если его множе-
ство истинности
p
E не совпадает с его областью определения, т.е. су -
ществуют такие наборы
(
)
Ma,,a,a
n
K
21
, на которых предикат при -
нимает значение 0. 
                                           107
Операция замыкания. Основные замкнутые классы.
__________________________________________________________________________________________
      Предложение или утверждение, содержащее одно или несколько пе-
ременных, при подстановке вместо которых конкретных значений из неко-
торых множеств мы получаем высказывание (истинное или ложное), назы-
вается предикатом. Количество переменных, от которых зависит преди-
кат, называется местностью или арностью.
      Пусть M 1 , M 2 , , M n — множества элементов произвольной приро-
ды.

        Определение 1: n -местным предикатом называется функция
P (x 1 , x 2 , , x n ), зависящая от n переменных, определенная на множестве
M =M 1 ×M 2 × ×M n и принимающая на этом множестве значение
1(истина) или 0 (ложь).

     Например, P (x )= [натуральное число x кратно 5] — одноместный
предикат: P (4 ) =0 , P (15) =1, P (11) =0 , P (20 ) =1. Q( x , y ) =[город x нахо-
дится на территории государства y] — двухместный предикат:
Q (Москва , Россия ) =1, Q(Париж , Венгрия ) =0 , Q (Париж , Франция ) =1.
     Само высказывание считается нуль-местным предикатом.
     Переменные x1 , x 2 , , x n , от которых зависит предикат, называются
предметными переменными. Конкретные значения предметных перемен-
ных называются предметными константами.
     Множество M , на котором задан предикат, называется областью
определения предиката.
     Множество E p ⊂ M , на котором предикат принимает только ис-
тинные значения, называется множеством истинности предиката
P (x 1 , x 2 , , x n ): E p ={(a 1 , a 2 , , a n ) ∈M P (a1 , a 2 , , a n ) =1}.
        Различают четыре типа предикатов:
1. Предикат P (x 1 , x 2 , , x n ) называется тождественно истинным на
   множестве M =M 1 ×M 2 × ×M n , если E p =M , т.е. если на любом
   наборе (a 1 , a 2 , , a n )∈M предикат принимает значение 1 (истина).
2. Предикат P (x 1 , x 2 , , x n ) называется тождественно ложным на
   множестве M , если E p =∅ , т.е. если на любом наборе значений пере-
   менных предикат принимает значение 0 (ложь).
3. Предикат P (x 1 , x 2 , , x n ) называется выполнимым, если его множест-
   во истинности E p не пусто: E p ≠∅ .
4. Предикат P (x 1 , x 2 , , x n ) называется опровержимым, если его множе-
   ство истинности E p не совпадает с его областью определения, т.е. су-
   ществуют такие наборы (a 1 , a 2 , , a n )∈M , на которых предикат при-
   нимает значение 0.

Страницы