Математическая логика и теория алгоритмов. Сергиевская И.М. - 23 стр.

UptoLike

ВУЗ: 

ПГУТИ | Самара

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

Рубрика: 

28
Если
{}
0,1=X , то n -местный предикат представляет собой n -местную булеву
функцию.
Нульместный предикат представляет собой высказывание.
Для каждого предиката
A
областью истинности называется множество
{
}
1)( =∈= xAXxY , на котором предикат принимает значение 1.
Примеры. 1. Для предиката "2")(
≤
=
x
x
A
на множестве
R
X = область
истинности
{
}
2≤∈= xRxY .
2. Для предиката "0"),( >
=
xy
y
x
B
на множестве
2
R
X
=
область истинности
{
}
0),(
2
>∈= xyRyxY .
Поскольку множество значений любого предиката лежит во множестве
{
}
0,1 ,
то с предикатами можно производить все операции алгебры логики, и все известные
свойства логических операций обобщаются для предикатов. Рассмотрим эти
свойства (для удобства в свойствах записываются одноместные предикаты):
3.
Коммутативность:
() () () ()
xPxQxQxP ∨=∨ ,
()
(
)
(
)
(
)
xPxQxQxP
=
.
2. Ассоциативность:
() () ()()()
(
)()
(
)
xRxQxPxRxQxP ∨∨=∨∨
,
() () ()()()
(
)()
(
)
xRxQxPxRxQxP
∧=∧∧ .
3. Дистрибутивность:
() () ()()()
(
)()
(
)
(
)
(
)
xRxPxQxPxRxQxP ∨
∨=∧∨ ,
() () ()()()
(
)()
(
)
(
)
(
)
xRxPxQxPxRxQxP
∨∧=∨∧ .
4.
Идемпотентность:
() ()
(
)
xPxPxP
=
∨ ,
(
)
(
)
(
)
xPxPxP
=
∧
.
5.
Закон двойного отрицания:
(
)
(
)
xPxP
=
¬¬ .
6.
Закон исключения третьего:
(
)
(
)
1
=
¬
∨ xPxP .
7.
Закон противоречия:
()
(
)
0
=
¬∧ xPxP .
8.
Законы де Моргана:
() ()( ) () ()
xQxPxQxP ¬∧
¬
=∨¬ ,
() ()( ) () ()
xQxPxQxP ¬∨
¬
=∧¬ .
9.
Свойства операций с логическими константами:
()
11 =∨xP ,
() ()
xPxP =∨ 0,
(
)
(
)
xPxP
=
∧
1,
(
)
00
=
∧
xP .
Здесь
()
xP ,
(
)
xQ и
()
xR – любые предикаты.
В то же время, для предикатов определены операции специального вида,
которые называются
кванторами.
Пусть дан n -местный предикат
),...,,(
21 n
xxxA
на множестве
X
, означающий,
что для набора ),...,,(
21 n
xxx выполнено свойство
A
, и пусть
i
x – одна из
переменных. Тогда запись
),...,,(
21 ni
xxxAx∀ означает, что для всех значений
переменной
i
x свойство
A
выполнено. Символ
∀
называется квантором 
      Если X = {0,1}, то n -местный предикат представляет собой n -местную булеву
функцию.
      Нульместный предикат представляет собой высказывание.
      Для каждого предиката A областью истинности называется множество
Y = {x ∈ X A( x) = 1}, на котором предикат принимает значение 1.

     Примеры. 1. Для предиката A( x) =" x ≤ 2" на множестве X = R область
истинности Y = {x ∈ R x ≤ 2}.
        2. Для предиката B( x, y ) =" xy > 0" на множестве X = R 2 область истинности
    {                    }
Y = ( x, y ) ∈ R 2 xy > 0 .

      Поскольку множество значений любого предиката лежит во множестве {0,1},
то с предикатами можно производить все операции алгебры логики, и все известные
свойства логических операций обобщаются для предикатов. Рассмотрим эти
свойства (для удобства в свойствах записываются одноместные предикаты):
3. Коммутативность:
   P( x ) ∨ Q( x ) = Q( x ) ∨ P ( x ) , P( x ) ∧ Q( x ) = Q( x ) ∧ P ( x ) .
2. Ассоциативность:
   P( x ) ∨ (Q( x ) ∨ R( x )) = (P( x ) ∨ Q( x )) ∨ R( x ),
   P( x ) ∧ (Q( x ) ∧ R( x )) = (P( x ) ∧ Q( x )) ∧ R( x ).
3. Дистрибутивность:
   P( x ) ∨ (Q( x ) ∧ R( x )) = (P( x ) ∨ Q( x )) ∧ (P( x ) ∨ R( x )) ,
   P( x ) ∧ (Q( x ) ∨ R( x )) = (P( x ) ∧ Q( x )) ∨ (P( x ) ∧ R( x )) .
4. Идемпотентность: P( x ) ∨ P( x ) = P( x ) , P( x ) ∧ P( x ) = P( x ) .
5. Закон двойного отрицания: ¬¬P( x ) = P( x ) .
6. Закон исключения третьего: P( x ) ∨ ¬P( x ) = 1 .
7. Закон противоречия: P( x ) ∧ ¬P( x ) = 0 .
8. Законы де Моргана:
    ¬(P( x ) ∨ Q( x )) = ¬P( x ) ∧ ¬Q( x ) ,
    ¬(P( x ) ∧ Q( x )) = ¬P( x ) ∨ ¬Q( x ) .
9. Свойства операций с логическими константами:
    P( x ) ∨ 1 = 1 , P( x ) ∨ 0 = P( x ) , P( x ) ∧1 = P( x ) , P( x ) ∧ 0 = 0 .
      Здесь P( x ) , Q( x ) и R( x ) – любые предикаты.

     В то же время, для предикатов определены операции специального вида,
которые называются кванторами.
     Пусть дан n -местный предикат A( x1 , x2 ,..., xn ) на множестве X , означающий,
что для набора ( x1 , x2 ,..., xn ) выполнено свойство A , и пусть xi – одна из
переменных. Тогда запись ∀xi A( x1 , x2 ,..., xn ) означает, что для всех значений
переменной xi свойство A выполнено. Символ ∀ называется квантором



                                          28

Страницы