Математическая логика. Типовые расчеты. Лоскутова Е.С - 6 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

;)()( ZYXZYX ∧∧≡
∧
∧ (4)
Y
X
Y
X
∨
≡
∧
; (11)
3) дистрибутивность:
8)
);()( YXYX ∨≡→ …(12)
);()()( ZXYXZYX
∧
∨∧≡∨∧ (5) )()()( XYYXYX →
∧
→
≡
↔
; (13)
);()()( ZXYXZYX ∨∧∨≡
∧
∨ (6)
9) законы поглощения:
10) закон исключенного третьего:
;)( XXYX ≡∨∧ (14)
∅≡∧ XX ; (16)
;)( XXYX ≡
∧
∨ (15)
E
X
X
≡
∨ ;…(17)
11) закон двойного отрицания:
X
X
≡ . (18)
1.6. Нормальные формы формул алгебры высказываний
Обозначим
=σ
=σ
=
σ
.0если,
;1если,
x
x
x
Определение 1. Элементарной конъюнкцией (конъюнктом) называется формула вида:
n
n
xxxK
σσσ
∧∧∧= ...
21
21
, а
элементарной дизъюнкцией (дизъюнктом) – формула вида:
n
n
xxxD
σσσ
∨∨∨= ...
21
21
.
Определение 2. Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция конечного количества элемен-
тарных конъюнкций.
Определение 3. Конъюнктивной нормальной формой (КНФ) называется конъюнкция конечного количества элемен-
тарных дизъюнкций.
ДНФ и КНФ не единственны. Условимся в качестве ответа принимать ту ДНФ (КНФ) из всех возможных, которая
содержит наименьшее количество логических операций.
1.7. Совершенные нормальные формы формул алгебры высказываний
Определение 1. Элементарная конъюнкция (дизъюнкция) называется правильной, если в её составе нет одинаковых
переменных.
Определение 2. Дизъюнкт (конъюнкт) является полным, относительно некоторого набора переменных, если в его со-
ставе представлены все переменные этого набора.
Определение 3. СДНФ (СКНФ) данной формулы F называется такая её ДНФ (КНФ), которая не содержит одинаковых
конъюнктов (дизъюнктов), каждый конъюнкт (дизъюнкт) правилен и обладает свойством полноты.
Теорема 1. Любая формула F, не являющаяся тождественной ложью, обладает единственной СДНФ.
Теорема 2. Любая формула F, не являющаяся тавтологией, обладает единственной СКНФ.
Алгоритм перехода от таблицы истинности формулы к её записи в виде СДНФ(СКНФ):
1)
выбрать в таблице такие наборы исходных переменных, на которых истинностное значение формулы равно 1 (0);
2)
записать элементарные конъюнкции (дизъюнкции) для выбранных наборов переменных; при этом необходимо
руководствоваться следующим правилом: если значение входной переменной в наборе – единичное, то она записывается
в прямой форме (форме отрицания), если же значение переменной – нулевое, то – в форме отрицания (прямой форме);
3)
полученные конъюнкты (дизъюнкты) объединить между собой знаками дизъюнкции (конъюнкции).
1.8. Логическое следование
Определение 1. Говорят, что формула Q логически следует из формулы Р, если Q принимает значение истины на
всяком наборе пропозиционных переменных, на котором значение истины принимает формула Р.
Другими словами, если λ (P) = 1, то λ(Q) = 1.
Обозначения: Р ├ Q.
Теорема 1. Q логически следует из P тогда и только тогда, когда P→Q – тавтология.
Теорема 2 (метод резолюций). Имеет место логическое следование
)()( QRQP ∨∧∨ ├
R
P
∨
.
1.9. Логическое следование из группы формул
Определение 1. Говорят, что формула Q следует логически из формул P
1
, P
2
, …, P
n
, если
()
1=λ Q , при всех тех значениях
переменных, при которых
1)( =λ
j
P
( j = 1, 2, ..., n), т.е. Q принимает значения истины на каждом наборе переменных, на кото-
ром истинно каждое из P
1
, P
2
, …, P
n
одновременно.
Обозначения: (P
1
… P
n
)├ Q.
Теорема. Логическое следование (P
1
… P
n
)├ Q имеет место тогда и только тогда, когда
()
QPPP
n
→
∧
∧∧ ...
21
явля-
ется тавтологией.
Алгоритм получения всех неравносильных между собой логических следствий данной формулы F, не являющейся
тавтологией:
1)
для формулы F построить СКНФ;
2)
выписать все полные правильные дизъюнкты;
3)
построить всевозможные их конъюнкции.

Страницы