Дискретная математика. Элементы теории задачи и упражнения. Часть 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 ∨⇔
.
Кроме перечисленных выше операций введены еще две операции
связывания кванторов, присущи только предикатам: квантор общности
∀
и квантор существования
∃
. Эти две операции не имеют аналогов среди
операций над высказываниями. 
                                           111
Операция замыкания. Основные замкнутые классы.
__________________________________________________________________________________________
  Ясно, что при выполнении логических операций над предикатами к ним

  применимы основные равносильности алгебры логики высказываний.

      Пример 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 ,  , 2 n −1,};
      4. E P → Q ={1, 3, 5 ,  , 2 n −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 ).
     Кроме перечисленных выше операций введены еще две операции
связывания кванторов, присущи только предикатам: квантор общности ∀
и квантор существования ∃. Эти две операции не имеют аналогов среди
операций над высказываниями.

Страницы