Основные равносильности

1) р.

Коммутативность:

2) рqqр.

3) pq.

Ассоциативность:

4) (рq) rр(qr).

5) ()rр(qr).

Дистрибутивность:

6) р(qr). рr.

7) р(qr) (рq) (рr).

Законы Де-Моргана:

8) .

9) .

Поглощение:

10) ррр.

11) ррр.

Операции с 0 и 1

12) р00.

13) р1р.

14) р0р.

15) р11.

Связь с отрицанием

16) р0.

17) р1.

Связь импликации и эквиваленции с другими операциями

18) pq q.

19) pq(pq)().

Доказательство этих равносильностей происходит путем построения таблиц истинности.

Используются равносильности при преобразованиях формул.

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

pq↔r( снимаем эквиваленцию по 19)

((pq)r)(r(pq))

(снимаем импликации по 18)

(r)(q) (по законам де Моргана)

(r)(q)( снимаем двойные отрицания по 1)

(рr)(qq) (в первой скобке выносим за скобку по 6, во второй скобке по 11) (р)(q) (по 6)

(р) (q) (по 16)

(р) (0) (по 14)

(р) () (по 6)

рр (по 10 и 16)

р0 (по 14 и 6)

(р1) 1 .

Дата добавления: 2014-01-06; Просмотров: 291; Нарушение авторских прав?; Мы поможем в написании вашей работы!