Дискретная математика. Элементы теории, задачи и упражнения. Часть 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
. 
   Ясно, что при выполнении логических операций над предикатами к ним
   применимы основные равносильности алгебры логики высказываний.
      Пример 1. Пусть даны одноместные предикаты:
      P � x � = [ x – четное число] и Q � x � = [число x кратно 3], определен-
ные на множестве натуральных чисел N . Найти множество истинности
предикатов:
      1. P � x � & Q � x � ;
      2. P � x � � Q � x � ;
      3. P � x � ;
      4. P � x � � Q � x � .
      Решение: имеем E P � �2 , 4 , 6 , � , 2n , ��; E Q � �3, 6 , 9 , � , 3n , ��.
Тогда
      1. E P &Q � �6 , 12 , 18 , � , 6n ,��;
      2. E P � Q � �2 , 3, 4 , 6 , 8 , 9 , � , 2n , 3n ,�� ;
      3. E P � �1, 3 , 5 , � , 2n � 1,��;
      4. E P � Q � �1, 3 , 5 , � , 2n � 1,�� � �3, 6 , 9 , � ,3n ,��.

      Имеют место следующие теоремы:
      1. � P & Q � � 1 � P � 1 и Q � 1;
      2. � P � Q � � 0 � P � 0 и Q � 0 ;
      3. � P � Q � � 0 � P � 1 и Q � 0 ;
      4. P � 1 � P � 0 ;
      5. � P � Q � � 1 � � P � Q � .

     Считается, что операция � связывает сильнее, чем &, а операция &
связывает сильнее, чем � . Операция � сильнее, чем � ; операция �
сильнее, чем � . Введение скобок нарушает принятый порядок выполне-
ния операций.
     Ниже приведены некоторые равносильности:
     1. � P � Q � � �P � Q � ;
     2. � P � Q � � � P � Q � & �Q � P � ;
      3. � P & Q � � �P � Q �.

     Кроме перечисленных выше операций введены еще две операции
связывания кванторов, присущи только предикатам: квантор общности �
и квантор существования � . Эти две операции не имеют аналогов среди
операций над высказываниями.
     Пусть P � x � – одноместный предикат, определенный на множест-
ве M .

                                        58

Страницы