Практика по эквивалентному преобразованию формул

Эквивалентные преобразования формул

Специфические законы алгебры высказываний

Имя закона	Равносильные формулы
Коммутативности	(AÚB) º (BÚA), (A&B) º (B &A)
Ассоциативности	AÚ(BÚC) º (AÚB)ÚC, A&(B&C) º (A&B) &C
Дистрибутивности	AÚ(B&C) º (AÚB) &(AÚC), A&(BÚC) º (A&B) Ú(A&C)
Идемпотентности	AÚA º A, A&A º A
Исключения третьего	AÚØA º и
Противоречия	A&ØA º л
Де Моргана	Ø(AÚB) º ØA&ØB, Ø(A&B) º ØAÚØB
Поглощения	AÚ(A&B) º A, A&(AÚB) º A
Порецкого	AÚ(ØA&B) º (AÚB), A&(ØAÚB) º (A&B)
Обобщенного склеивания	A&BÚØA&B º A&BÚØA&BÚB (AÚB)&(ØAÚB) º (AÚB)&(ØAÚB)&B
Дополнения	Ø(ØA) º A
Константы	AÚл º A, AÚи º и, A&л º л, A&и º A
Для импликации	(A®B) º (ØA ÚB) º Ø(A &ØB)
Для эквивалентности	(A«B) º (A ®B)&(B®A)

Законы поглощения, Порецкого и обобщенного склеивания являются производными относительно остальных в этой таблице: они могут быть выведены из них.

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

Знание законов алгебры высказываний позволяет выполнять эквивалентные преобразования любой ППФ для замены одних логических операций на другие, сохраняя ее значение для всех наборов ПП. Эти эквивалентные преобразования определяются правилом подстановки вида:

Это правило выполняет замену подформулы в формуле: если формула F содержит подформулу F_i, которая, в свою очередь, имеет эквивалентную формулу F_j, то возможна подстановка в формулу F всюду вместо формулы F_i формулы F_j.

Например, даны формулы F=(A&C®A) и A=(C®ØB). Выполнить подстановку в формулу F подформулы А:

1. Вывести закон поглощения вида: AÚ(A&B)ºA.

Решение:

· применим к левой части тождества закон константы: AÚ(A&B) = (A&и)Ú(A&B)

· по закону дистрибутивности: (A&и)Ú(A&B)=A&(иÚB)

· по закону константы: A&(иÚB)=A

2. Вывести закон поглощения вида: A&(AÚB)ºA.

Решение:

· применим к левой части тождества закон константы: A&(AÚB)=(AÚл)&(AÚB)

· по закону дистрибутивности: (AÚл)&(AÚB)=AÚ(л&B)

· по закону константы: AÚ(л&B)=A

3. Вывести закон Порецкого вида: AÚ(ØA&B)º(AÚB).

Решение:

· применим к левой части тождества закон дистрибутивности:

AÚ(ØA&B)=(AÚØA)&(AÚB)

· по закону исключения третьего: (AÚØA)&(AÚB)=и&(AÚB)

· по закону константы: и&(AÚB)=(AÚB)

4. Вывести закон Порецкого вида: A&(ØAÚB)º(A&B).

Решение:

· применим к левой части тождества закон дистрибутивности:

A&(ØAÚB)=(A&ØA)Ú(A&И)

· по закону противоречия: (A&ØB)Ú(A&B)=лÚ(A&B)

· по закону константы: лÚ(A&B)=(A&B)

5. Вывести закон обобщенного склеивания вида:

A&BÚØA&BºA&BÚØA&BÚB

Решение:

1) преобразуем правую часть тождества:

· по закону константы: A&BÚØA&BÚB=A&BÚØA&BÚи&B

· по закону дистрибутивности: A&BÚØA&BÚи&B=B&(AÚØAÚи)

· по закону константы: B&(AÚØAÚи)=B

2) преобразуем левую часть тождества:

· по закону дистрибутивности: A&BÚØA&B=B&(AÚØA)

· по закону исключения третьего: B&(AÚØA)=B

3) сравним полученные результаты в шагах 1 и 2: B=B

6. Упростить формулу Ø(F₁®F₂)&(ØF₃ÚØF₄)ÚØ(F₁ÚF₂)&Ø(F₃&F₄).

Решение:

· удалим связку ®: Ø(ØF₁ÚF₂)&(ØF₃ÚØF₄)ÚØ(F₁ÚF₂)&Ø(F₃ &F₄)

· по закону де Моргана: (F₁&ØF₂)&(ØF₃ÚØF₄)Ú(ØF₁&ØF₂)&(ØF₃ÚØF₄)

· по закону дистрибутивности: (ØF₃ÚØF₄)&((F₁&ØF₂)Ú(ØF₁&ØF₂))

· по закону дистрибутивности: (ØF₃ÚØF₄)&ØF₂&(F₁ÚØF₁)

· по закону исключенного третьего: (ØF₃ÚØF₄)&ØF₂&и

· по закону констант: (ØF₃ÚØF₄)&ØF₂.

7. Доказать тождество: (AÚB)&(AÚØB)ºA.

Решение:

· по закону дистрибутивности: (AÚB)&(AÚØB)=A&(B&ÚØB)

· по закону противоречия: AÚ(B&ØB)=А.

8. Доказать тождество: (AÚB)&(BÚC)&(CÚA)º(A&B)Ú(B&C)Ú(C&A),

Решение:

· по закону дистрибутивности:

(AÚB)&(BÚC)&(CÚA)=A&(BÚC)ÚB&C=A&BÚА&CÚB&C

9. Доказать тождество: (AÚB)&(AÚC)&(BÚD)&(CÚD)º((A&D)Ú(B&C)).

Решение:

· по закону дистрибутивности

(AÚB)&(AÚC)&(BÚD)&(CÚD)=(AÚ(B&C))&(DÚ(B&C))=((A&D)Ú(B&C))

10. Доказать тождество: (AÚBÚС)&(BÚCÚD)&(CÚDÚA)º((A&B)Ú(A&D)Ú(B&D)ÚC).

Решение:

· по закону дистрибутивности:

(A&B&CÚB&B&C&ÚC&B&C)Ú(A&C&CÚB&C&CÚC&C&C)Ú(A&D&CÚB&D&CÚC&D&C) Ú(A&B&DÚB&B&DÚC&B&D)Ú(A&C&DÚB&C&DÚC&C&D)Ú(A&D&DÚB&D&DÚC&D&D) Ú(A&B&AÚB&B&AÚC&B&A)Ú(A&C&AÚB&C&AÚC&C&A)Ú(A&D&AÚB&D&AÚC&D&A)

· по законам идемпотентности и поглощения:

((A&B)Ú(A&D)Ú(B&D)ÚC).

Дата добавления: 2014-01-04