Математическая логика. - 8 стр.

UptoLike

ВУЗ: 

ПНИПУ | Пермь

Рубрика: 

- 7 - Математическая логика
Получим С
К
ДНФ:
С
К
ДНФ имеет вид . zxyxzyyxzyxz ∨∨∨∨∨
В данном случае получается две МДНФ (табл. 3)
МДНФ
1
; zxzyxy ∨∨
МДНФ
2
. zxzxyz ∨∨
Таблица 3
xyz
xy
z
zyx zyx yzx zyx
xy + +
yz + +
zx
+ +
zy
+ +
yx
+ +
zx
+ +
ПОНЯТИЕ ПРЕДИКАТА.
Предикатом Р(х
1
,……..,х
n
) называется функция, в которой переменные
x
1
,………,x
n
могут принимать значения из некоторой предметной области, а са-
ма функция может быть истинной или ложной.
В алгебре предикатов справедливы все операции алгебры высказываний.
Кроме того, вводятся операции навешивания кванторов:
1.
Квантор общности (всеобщности):
∀
x
P(x) – «для всех справедливо
Р(х)» или короче «для всех х-Р(х)».
2.
Квантор существования:
∃
х Р(х) – «существуют (есть) такие х, что
справедливо
Р(х)» или короче « есть такие х, что Р(х)».
Если предметные переменные определены на конечные области, то опе-
рации навешивания кванторов можно выразить через операции конъюнкции и
дизъюнкции соответственно.
Пусть x
1
∈ {a
1,
…,a
m
} ,
тогда
∀x
1
P(x
1
,…,x
n
)=P(a
1
,…,x
n
)&P(a
2
,…,x
n
)&…&P(a
m
,…,x
n
),
∃x
1
P(x
1
,…,x
n
)=P(a
1
,…,x
n
) ∨ P(a
2
,…,x
n
) ∨ … ∨ P(a
m
,…,x
n
);
zy : 43
z x: 32
zx : 65 yz : 51
yx : 64 xy : 21
−
−
−−
−−
                                       -7-                   Математическая логика


      Получим СКДНФ:
                         1 − 2 : xy             4 − 6 : xy
                         1 − 5 : yz             5 − 6 : xz
                         2 − 3 : xz
                         3 − 4 : yz
      СКДНФ имеет вид xz ∨ zy ∨ x y ∨ y z ∨ x y ∨ xz .
      В данном случае получается две МДНФ (табл. 3)
      МДНФ 1
             xy ∨ y z ∨ xz ;
      МДНФ 2
             yz ∨ x z ∨ x z .
                                                       Таблица 3
                          xyz   xy z   x yz   x yz   xyz       x yz
                  xy       +      +
                  yz       +                          +

                  xz              +     +

                  yz                    +      +

                  xy                           +                +

                  xz                                  +         +


                            ПОНЯТИЕ ПРЕДИКАТА.
      Предикатом Р(х1,……..,хn) называется функция, в которой переменные
x1,………,xn могут принимать значения из некоторой предметной области, а са-
ма функция может быть истинной или ложной.
      В алгебре предикатов справедливы все операции алгебры высказываний.
Кроме того, вводятся операции навешивания кванторов:
      1. Квантор общности (всеобщности): ∀xP(x) – «для всех справедливо
          Р(х)» или короче «для всех х-Р(х)».
      2. Квантор существования: ∃ х Р(х) – «существуют (есть) такие х, что
          справедливо Р(х)» или короче « есть такие х, что Р(х)».
      Если предметные переменные определены на конечные области, то опе-
рации навешивания кванторов можно выразить через операции конъюнкции и
дизъюнкции соответственно.
      Пусть x1∈ {a1,…,am} ,
тогда
      ∀x1 P(x1,…,xn)=P(a1,…,xn)&P(a2,…,xn)&…&P(am,…,xn),
      ∃x1 P(x1,…,xn)=P(a1,…,xn) ∨ P(a2,…,xn) ∨ … ∨ P(am,…,xn);

Страницы