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

1. Преобразовать к виду КНФ формулу(Ф₁®(Ф₂ÚØФ₃))®Ф₄.

Решение:

· удалим символ ®: Ø(ØФ₁Ú(Ф₂ÚØФ₃))ÚФ₄

· выполним операцию отрицания: (Ф₁&ØФ₂&Ф₃)ÚФ₄

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

2. Преобразовать к виду КНФ формулу: ((A®B)®(C®ØA))®(ØB®ØC).

Решение:

· удалим логические связки ®:

((A®B)®(C®ØA))®(ØB®ØC)=Ø(Ø(ØAÚB)Ú(ØCÚØA))Ú(BÚØC)

· по закону де Моргана:

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

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

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

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

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

· по законам идемпотентности и исключенного третьего:

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

· по закону поглощения: (BÚØC)&(AÚBÚØC)=(BÚØC).

Полученный результат - элементарная дизъюнкция КНФ.

3. Преобразовать к виду ДНФ формулу: ((((A®B)®Ø A)®Ø B)®Ø C)®C.

Решение:

· устраним логические связки ®: Ø(Ø(Ø(Ø(ØAÚB)ÚØA)ÚØB)ÚØC)ÚC,

· по закону де Моргана:

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

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

· по закону дистрибутивности: (AÚØB)&CÚC=A&CÚØB&CÚC. Это три элементарных конъюнкции ДНФ,

· по закону поглощения: (A&CÚØB&CÚC)=С.

4. Преобразовать к виду ДНФ формулу: (A®(B®C))®(A®ØC)®(A®ØB).

Решение:

· устраним логические связки ®: Ø(ØAÚ(ØBÚC))Ú(Ø(ØAÚØC)Ú(ØAÚØB)),

· по закону де Моргана:

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

Результат - четыре элементарных конъюнкции ДНФ.

5. Преобразовать к виду КНФ формулу: Ø(A&(BÚC))®((A&B)ÚC).

Решение:

· устраним логические связки ®: (A&(BÚC))Ú((A&B)ÚC),

· по законам дистрибутивности, идемпотентности и поглощения:

A&BÚA&CÚA&BÚC=A&BÚC,

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

Результат - две элементарных дизъюнкции КНФ.

6. Преобразовать к виду КНФ формулу: (С®A)®(Ø(BÚC)®A).

Решение:

· устраним логические связки ® и Ø: Ø(ØСÚA)Ú((BÚC)ÚA)=C&ØAÚBÚCÚA,

· по законам идемпотентности, дистрибутивности и исключения третьего:

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

Результат - одна элементарная дизъюнкция КНФ.

7. Преобразовать к виду СДНФ формулу:(A&¬В)∨(A&¬C&D).

Решение:

(A&¬B&(C∨¬C))∨(A&¬C&D&(B∨¬B))=

(A&¬B&C)∨(A&¬B&¬C)∨(A&B&¬C&D)∨(A&¬B&¬C&D)=

(A&¬B&C&(D∨¬D))∨(A&¬B&¬C&(D∨¬D))∨(A&B&¬C&D)∨(A&¬B&¬C&D)=

(A&¬B&C&D)∨(A&¬B&C&¬D)∨(A&¬B&¬C&D)∨(A&¬B&¬C&¬D)∨(A&B&¬C&D)∨ (A&¬B&¬C&D)

8. Преобразовать к виду СКНФ формулу: (A∨B)&(¬A∨¬B∨C∨D).

Решение:

(A∨B∨С&¬С)&(¬A∨¬B∨C∨D)=

(A∨B∨C)&(A∨B∨¬C)&(¬A∨¬B∨С∨D)=

(A∨B∨С∨D&¬D)&(A∨B∨¬C∨D&¬D)&(¬A∨¬B∨С∨D)=

(A∨B∨С∨D)&(A∨B∨С∨¬D)&(A∨B∨¬С∨D)&(A∨B∨¬С∨¬D)&(¬A∨¬B∨С∨D)

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