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

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

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

Рубрика: 

Математическая Логика и Теория Алгоритмов стр. 8 из 64
© 2003 Галуев Геннадий Анатольевич
⎪
⎩
⎪
⎨
⎧
&⎤↔→⎤
&⎤↔⎤∨⎤
∨⎤↔⎤&⎤
BA)BA(
BA)BA(
BA)BA(
(Законы Де Моргана и отрицание импликации)
(2.6)
⎤
А
&
А
↔
0
(2.7)
⎤
А ∨ А
↔
1
(2.8)
⎩
⎨
⎧
↔∨↔∨
↔&↔&
11A A0A
A1A 00A
(2.9)
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎩
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎨
⎧
↔∨&
↔&∨
→&→↔↔
→↔⎤∨
→⎤↔⎤&
∨⎤⎤↔⎤&
&⎤↔⎤→
&⎤⎤↔⎤∨
→⎤↔⎤→
∨↔⎤→
A)BA(A
A)BA(A
)AB()BA()BA(
BABA
)BA(BA
)BA(BA
)BA(BA
)BA(BA
ABBA
BABA
(замена одних пропозиционных связок через другие)
(2.10)
Представленные в теореме тавтологии легко доказываются с помощью построе-
ния таблиц истинности. Утверждаемую в них эквивалентность пропозиционных форм
совместно с теоремами 1 и 2 можно использовать как для проверки эквивалентных
преобразований логических формул, так и для доказательства их эквивалентности.
Например:
1. Докажем, что А
∨ (⎤А&В)↔А ∨ В
BA)BA(1)BA()AA()BA(A
9.28.25.2
∨⎯→←∨&⎯→←∨&∨⎤⎯→←&⎤∨
2. Докажем, что (А
∨
В)&(А
∨
⎤В)↔А
A0A)BB(A)BA()BA(
9.27.25.2
⎯→←∨⎯→←&⎤∨⎯→←∨⎤&∨
3. Докажем, что (⎤А&⎤В
∨ А&В)↔(А↔В)
B)(A
2.10
B)(A
A)(B
2.10
B)A(B)(A
2.9
1B)A(B)(A1
2.8
B)(B
B)A(B)(AA)A(
2.5
B)BA(A)BA(
2.5
BABA
↔⎯⎯→←→&
&→⎯⎯→←∨⎤&∨⎤⎯⎯→←&∨⎤&∨⎤&⎯⎯→←∨⎤&
&∨⎤&∨⎤&∨⎤⎯⎯→←∨&⎤⎤&∨&⎤⎤⎯⎯→←&∨&⎤⎤
Выше мы показали, что каждой пропозиционной форме соответствует не-
которая истинностная функция. Однако открытым остаётся вопрос, каждой ли
истинностной функции соответствует некоторая пропозиционная форма.
Ответ на этот вопрос даёт следующая теорема.
Т
Т
е
е
о
о
р
р
е
е
м
м
а
а
.
. Любую истинностную (булеву) функцию F(X
1
,...,X
n
) можно представить
в следующей форме:

Страницы