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

UptoLike

Операция замыкания . Основные замкнутые классы .
__________________________________________________________________________________________
111
Ясно, что при выполнении логических операций над предикатами к ним
применимы основные равносильности алгебры логики высказываний.
Пример 1. Пусть даны одноместные предикаты:
(
)
xP =[
x
четное число] и
(
)
xQ =[число
x
кратно 3], определенные
на множестве натуральных чисел
N
. Найти множество истинности
предикатов:
1.
(
)
(
)
xQ&xP
;
2.
(
)
(
)
xQxP
;
3.
(
)
xP ;
4.
(
)
(
)
xQxP
.
Решение: Имеем
{
}
{
}
KKKK ,n,,,,E;,n,,,,E
QP
39632642
.
Тогда
1.
{
}
KK ,n,,,,E
Q&P
618126
;
2.
{
}
KK ,n,n,,,,,,,E
QP
32986432
;
3.
{
}
KK ,n,,,,E
P
12531
;
4.
{
}
{
}
KKUKK ,n,,,,,n,,,,E
QP
396312531
.
Имеют место следующие теоремы:
1.
(
)
11
PQ&P и
1
Q
;
2.
(
)
00
PQP и
0
Q
;
3.
(
)
10
PQP
и
0
Q
;
4. 01 ⇔≡ PP ;
5.
(
)
(
)
QPQP
1 .
Считается, что операция связывает сильнее, чем &, а операция &
связывает сильнее, чем
. Операция
сильнее, чем
; операция
сильнее, чем
. Введение скобок нарушает принятый порядок выполне-
ния операций.
Ниже приведены некоторые равносильности:
1.
(
)
(
)
QPQP ⇔→
;
2.
(
)
(
)
(
)
PQ&QPQP
;
3.
(
)
(
)
QPQ&P ∨⇔
.
Кроме перечисленных выше операций введены еще две операции
связывания кванторов, присущи только предикатам: квантор общности
и квантор существования
. Эти две операции не имеют аналогов среди
операций над высказываниями.