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

UptoLike

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

58
Ясно, что при выполнении логических операций над предикатами к ним
применимы основные равносильности алгебры логики высказываний.
Пример 1. Пусть даны одноместные предикаты:
(
)
xP = [
x
четное число] и
(
)
xQ = [число
x
кратно 3], определен-
ные на множестве натуральных чисел
N
. Найти множество истинности
предикатов:
1.
(
)
(
)
xQ&xP ;
2.
(
)
(
)
xQxP
Ú
;
3.
(
)
xP ;
4.
(
)
(
)
xQxP
®
.
Решение: имеем
{
}
{
}
,n,,,,E;,n,,,,E
QP
39632642
=
=
.
Тогда
1.
{
}
,n,,,,E
Q&P
618126
=
;
2.
{
}
,n,n,,,,,,,E
QP
32986432
=
Ú
;
3.
{
}
,n,,,,E
P
12531
-
=
;
4.
{
}
{
}
U
,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 ÚÛ .
Кроме перечисленных выше операций введены еще две операции
связывания кванторов, присущи только предикатам: квантор общности
"
и квантор существования
$
. Эти две операции не имеют аналогов среди
операций над высказываниями.
Пусть
(
)
xP одноместный предикат, определенный на множест-
ве
M
.