Перевірка правильності міркування шляхом побудови диз ’ юнктивної нормальної форми або кон ’юнктивно ї нормальної форми

Розв’яжемо задачу (2) (див. стор. 38) шляхом побудови нормальної форми (днф або кнф).

За відомим твердженням (теорема 1, п.2) формула BÚDÚH є логічним наслідком формул A®B, C®D, G®H, AÚCÚG, якщо формула
F = (A®B)Ù(C®D)Ù(G®H)Ù(AÚCÚG)ÙØ(BÚDÚH) є суперечністю.

Для перевірки суперечності F необхідно звести дану формулу до ДНФ, застосовуючи співвідношення 1-12 з розділу «Еквівалентні формули логіки висловлень. Нормальні форми».

Спочатку використаємо кілька разів співвідношення F₁® F₂ = ØF₁ Ú F₂, щоб вилучити усі входження імплікації (®). Маємо:

F = (ØAÚB)Ù(ØCÚD)Ù(ØGÚH)Ù(AÚCÚG)ÙØ(BÚDÚH).

Зменшуємо область дії зв’язки заперечення, де це потрібно, використовуючи співвідношення Ø(F₁ Ú F₂) = ØF₁ Ù ØF₂. Маємо:

F = (ØAÚB)Ù(ØCÚD)Ù(ØGÚH)Ù(AÚCÚG)Ù(ØBÙØDÙØH).

Застосуємо закони комутативності та асоціативності Ù:

F = ((ØBÙØDÙØH)Ù(ØAÚB))Ù(ØCÚD)Ù(ØGÚH)Ù(AÚCÚG).

Далі застосуємо закон F₁ Ù (F₂ Ú F₃) = (F₁ Ù F₂) Ú (F₁ Ù F₃), де F₁= (ØBÙØDÙØH), F₂=ØA, F₃= B:

F = ((ØBÙØDÙØHÙØA)Ú(ØBÙØDÙØHÙB))Ù(ØCÚD)Ù(ØGÚH)Ù(AÚCÚG).

Виконаємо спрощення підформули ØBÙØDÙØHÙB, використавши закони комутативності та асоціативності Ù й співвідношення F₁ÙØF₁=0, 0ÙF₁=0:

ØBÙØDÙØHÙB=(BÙØB)Ù(ØDÙØH)=0Ù(ØDÙØH)=0.

Маємо:

F = ((ØBÙØDÙØHÙØA)Ú0)Ù(ØCÚD)Ù(ØGÚH)Ù(AÚCÚG).

Виконаємо спрощення F за допомогою закону комутативності Ú та співвідношення 0 Ú F₁ =F₁:

F = (ØBÙØDÙØHÙØA)Ù(ØCÚD)Ù(ØGÚH)Ù(AÚCÚG).

Застосуємо закон F₁ Ù (F₂ Ú F₃) = (F₁ Ù F₂) Ú (F₁ Ù F₃), де F₁=ØBÙØDÙØHÙØA, F₂=ØС, F₃=D:

F = ((ØBÙØDÙØHÙØAÙØC)Ú(ØBÙØDÙØHÙØAÙD))Ù(ØGÚH)Ù(AÚCÚG).

Застосовуємо закони комутативності та асоціативності до підформули ØBÙØDÙØHÙØAÙD та спрощуємо її за допомогою співвідношень F₁ÙØF₁=0, 0ÙF₁=0:

ØBÙØDÙØHÙØAÙD=(DÙØD)Ù(ØBÙØHÙØA)=0Ù(ØBÙØHÙØA)=0.

Маємо:

F = ((ØBÙØDÙØHÙØAÙØC)Ú0)Ù(ØGÚH)Ù(AÚCÚG).

Виконаємо спрощення F за допомогою закону комутативності Ú та співвідношення 0 Ú F₁ =F₁:

F = (ØBÙØDÙØHÙØAÙØC)Ù(ØGÚH)Ù(AÚCÚG).

Застосуємо закон асоціативності Ù:

F = ((ØBÙØDÙØHÙØAÙØC)Ù(ØGÚH))Ù(AÚCÚG).

Далі можна застосувати співвідношення F₁ Ù (F₂ Ú F₃) = (F₁ Ù F₂) Ú (F₁ Ù F₃), де F₁=(ØBÙØDÙØHÙØAÙØC), F₂=ØG, F₃= H:

F=((ØBÙØDÙØHÙØAÙØCÙØG)Ú(ØBÙØDÙØHÙØAÙØCÙH))Ù(AÚCÚG).

Після перетворення за законами комутативності та асоціативності й спрощення підформули ØBÙØDÙØHÙØAÙØCÙH за співвідношеннями F₁ÙØF₁=0, 0ÙF₁=0 та подальшого спрощення формули F за тотожністю 0 Ú F₁ =F₁ маємо:

F = (ØBÙØDÙØHÙØAÙØCÙØG)Ù(AÚCÚG).

Повторюючи послідовно застосовувати закони асоціативності, дистрибутивності, комутативності та виконуючи спрощення, маємо:

F = (ØBÙØDÙØHÙØAÙØCÙØG)Ù(AÚCÚG) = (ØBÙØDÙØHÙØAÙØCÙØG)Ù(AÚ(CÚG)) =

(ØBÙØDÙØHÙØAÙØCÙØGÙA)Ú((ØBÙØDÙØHÙØAÙØCÙØG)Ù(CÚG)) = ((ØBÙØDÙØHÙØGÙØCÙ(AÙØA)))Ú((ØBÙØDÙØHÙØAÙØCÙØG)Ù(CÚG)) = (ØBÙØDÙØHÙØGÙØCÙ0) Ú ((ØBÙØDÙØHÙØAÙØCÙØG)Ù(CÚG)) =

 0Ú((ØBÙØDÙØHÙØAÙØCÙØG)Ù(CÚG)) = (ØBÙØDÙØHÙØAÙØCÙØG)Ù(CÚG) =

 (ØBÙØDÙØHÙØAÙØCÙØGÙC)Ú(ØBÙØDÙØHÙØAÙØCÙØGÙG) = ((CÙØC)ÙØBÙØDÙØHÙØAÙØG)Ú((GÙØG)ÙØBÙØDÙØHÙØAÙØC) = (0ÙØBÙØDÙØHÙØAÙØG)Ú(0ÙØBÙØDÙØHÙØAÙØC) = 0Ú0 = 0.

Отже, маємо, що днф формули F є 0, тобто F тотожно хибна формула.

Суперечність формули F доведено. Отже, можна сказати, що формула BÚDÚH є логічним наслідком формул A®B, C®D, G®H, AÚCÚG. Таким чином, задане міркування є логічно правильним.

Для розв’язання задачі (2) ми використали п.2 теореми 1 та днф, але ту саму задачу можна розв’язати, застосувавши п.1 теореми 1. Як випливає з п.1 теореми 1, формула BÚDÚH є логічним наслідком формул A®B, C®D, G®H, AÚCÚG, якщо формула

F = (A®B)Ù(C®D)Ù(G®H)Ù(AÚCÚG)®(BÚDÚH)

є тавтологією. Для перевірки тавтологічності F необхідно звести дану формулу до КНФ, застосовуючи співвідношення 1-12 з розділу «Еквівалентні формули логіки висловлень. Нормальні форми». Наведемо послідовність перетворень формули F:

F = (A®B)Ù(C®D)Ù(G®H)Ù(AÚCÚG)®(BÚDÚH) =

(ØAÚB)Ù(ØCÚD)Ù(ØGÚH)Ù(AÚCÚG)®(BÚDÚH) =

Ø((ØAÚB)Ù(ØCÚD)Ù(ØGÚH)Ù(AÚCÚG)) Ú (BÚDÚH) =

Ø(ØAÚB) Ú Ø(ØCÚD) Ú Ø(ØGÚH) Ú Ø(AÚCÚG) Ú (BÚDÚH) =

((ØØA)ÙØB)Ú((ØØC)ÙØD) Ú ((ØØG)ÙØH) Ú (ØAÙØCÙØG) Ú (BÚDÚH) =

(AÙØB)Ú (CÙØD) Ú (GÙØH) Ú (ØAÙØCÙØG) Ú (BÚDÚH) =

((BÚDÚH) Ú (AÙØB)) Ú (CÙØD) Ú (GÙØH) Ú (ØAÙØCÙØG) =

((BÚDÚHÚA)Ù(BÚDÚHÚØB)) Ú (CÙØD) Ú (GÙØH) Ú (ØAÙØCÙØG) =

((BÚDÚHÚA)Ù((BÚØB)Ú(DÚH))) Ú (CÙØD) Ú (GÙØH) Ú (ØAÙØCÙØG) =

((BÚDÚHÚA)Ù(1Ú(DÚH))) Ú (CÙØD) Ú (GÙØH) Ú (ØAÙØCÙØG) =

(1Ù(BÚDÚHÚA)) Ú (CÙØD) Ú (GÙØH) Ú (ØAÙØCÙØG) =

(BÚDÚHÚA) Ú (CÙØD) Ú (GÙØH) Ú (ØAÙØCÙØG) =

((BÚDÚHÚA) Ú (CÙØD)) Ú (GÙØH) Ú (ØAÙØCÙØG) =

((BÚDÚHÚAÚC)Ù(BÚDÚHÚAÚØD)) Ú (GÙØH) Ú (ØAÙØCÙØG) =

((BÚDÚHÚAÚC)Ù((DÚØD)Ú(HÚAÚB))) Ú (GÙØH) Ú (ØAÙØCÙØG) =

((BÚDÚHÚAÚC)Ù(1Ú(HÚAÚB))) Ú (GÙØH) Ú (ØAÙØCÙØG) =

(1Ù(BÚDÚHÚAÚC)) Ú (GÙØH) Ú (ØAÙØCÙØG) =

(BÚDÚHÚAÚC) Ú (GÙØH) Ú (ØAÙØCÙØG) =

((BÚDÚHÚAÚC) Ú (GÙØH)) Ú (ØAÙØCÙØG) =

((BÚDÚHÚAÚCÚG)Ù(BÚDÚHÚAÚCÚØH)) Ú (ØAÙØCÙØG) =

((BÚDÚHÚAÚCÚG)Ù((HÚØH)Ú(BÚDÚAÚC))) Ú (ØAÙØCÙØG) =

((BÚDÚHÚAÚCÚG)Ù(1Ú(BÚDÚAÚC))) Ú (ØAÙØCÙØG) =

(1Ù(BÚDÚHÚAÚCÚG)) Ú (ØAÙØCÙØG) =

(BÚDÚHÚAÚCÚG) Ú (ØAÙØCÙØG) =

(BÚDÚHÚAÚCÚG) Ú (ØAÙ(ØCÙØG)) =

(BÚDÚHÚAÚCÚGÚØA)Ù((BÚDÚHÚAÚCÚG)Ú(ØCÙØG)) =

(BÚDÚHÚAÚCÚGÚØA)Ù(BÚDÚHÚAÚCÚGÚØC)Ù(BÚDÚHÚAÚCÚGÚØG) =

((AÚØA)Ú(BÚDÚHÚCÚG))Ù((CÚØC)Ú(BÚDÚHÚAÚG))Ù((GÚØG)Ú(BÚDÚHÚAÚC)) = (1Ú(BÚDÚHÚCÚG))Ù(1Ú(BÚDÚHÚAÚG))Ù(1Ú(BÚDÚHÚAÚC)) =

1Ù1Ù1 = 1.

Отже, маємо, що кнф формули F є 1, тобто F тотожно істинна формула.

Тавтологічність формули F доведено. Отже, можна сказати, що формула BÚDÚH є логічним наслідком формул A®B, C®D, G®H, AÚCÚG. Таким чином, задане міркування є логічно правильним.

 

⇐ Предыдущая234567891011Следующая ⇒

Поделиться: