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

Розглянемо далі, як перевірити несуперечність F шляхом побудови ДНФ. Побудову ДНФ будемо здійснювати, використовуючи наведені вище співвідношення.

Маємо:

F = (A « ØB) Ù (B Ú ØC) Ù (ØA ® ØC) Ù (A Ú C).

Вилучимо входження зв’язки « (за допомогою тотожності F₁«F₂= (F₁®F₂)Ù(F₂®F₁)):

F = (A ® ØB) Ù (ØB ® A) Ù (B Ú ØC) Ù (ØA ® ØC) Ù (A Ú C).

Вилучимо усі входження зв’язки ® (за допомогою тотожності F₁®F₂=ØF₁ÚF₂):

F = (Ø A Ú ØB) Ù (Ø(ØB) Ú A) Ù (B Ú ØC) Ù (Ø(ØA) Ú ØC) Ù (A Ú C).

Виконаємо спрощення (за допомогою тотожності Ø(ØF₁) = F₁):

F = (Ø A Ú ØB) Ù (B Ú A) Ù (B Ú ØC) Ù (A Ú ØC) Ù (A Ú C).

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

F = (Ø A Ú ØB) Ù ((B Ú A) Ù (B Ú ØC)) Ù ((A Ú C) Ù (A Ú ØC)).

До підформули ((B Ú A) Ù (B Ú ØC)) застосуємо закон дистрибутивності:

F = (Ø A Ú ØB) Ù (B Ú (A Ù ØC)) Ù ((A Ú C) Ù (A Ú ØC)).

До підформули ((A Ú ØC) Ù (A Ú C)) застосуємо закон дистрибутивності:

F = (Ø A Ú ØB) Ù (B Ú (A Ù ØC)) Ù (A Ú (C Ù ØC)).

Виконаємо спрощення (за допомогою тотожності F₁ÙØF₁=0):

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

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

F = (Ø A Ú ØB) Ù (B Ú (A Ù ØC)) Ù A.

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

F = (A Ù (Ø A Ú ØB)) Ù (B Ú (A Ù ØC)).

Застосуємо закон дистрибутивності (F₁ Ù (F₂ Ú F₃) = (F₁ Ù F₂) Ú (F₁ Ù F₃)) до (AÙ (Ø A Ú ØB)) (тут F₁= А, F₂ = Ø A, F₃= Ø B):

F = ((A Ù Ø A) Ú (А Ù ØB)) Ù (B Ú (A Ù ØC)).

Розглянемо підформулу ((A Ù Ø A) Ú (А Ù ØB)). За тотожностями F₁ÙØF₁=0, 0ÚF₁= F₁ маємо:

(A Ù Ø A) Ú (А Ù ØB) = 0 Ú (А Ù ØB) = А Ù ØB.

Отже, F = (А Ù ØB) Ù (B Ú (A Ù ØC)).

Застосуємо закон дистрибутивності (F₁ Ù (F₂ Ú F₃) = (F₁ Ù F₂) Ú (F₁ Ù F₃)) до F (тут F₁= (А Ù ØB), F₂ = B, F₃= (A Ù ØC)):

F = ((А Ù ØB) Ù B) Ú ((А Ù ØB) Ù (A Ù ØC)).

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

F = (А Ù (B Ù ØB)) Ú ((А Ù A) Ù (ØB Ù ØC)).

Розглянемо підформулу (A Ù (B Ù ØB)). За тотожностями F₁ÙØF₁=0, 0ÙF₁=0 та законом комутативності Ù маємо:

(A Ù (B Ù ØB)) = А Ù 0 = 0.

Отже, F = (А Ù A) Ù (ØB Ù ØC). За законом ідемпотентності F₁ Ù F₁ = F₁ маємо:

F = A Ù ØB Ù ØC.

Отже, побудовано ДНФ формули (A«ØB) Ù (BÚØC) Ù (ØA®ØC) Ù (AÚC).

    Зауважимо, що побудова ДНФ формули F може бути здійснена не єдиним чином. Розглянемо інший спосіб приведення F до диз’юнктивної нормальної форми.

Послідовно вилучаємо у формулі F входження зв’язок « та ® й виконуємо спрощення:

F = (Ø A Ú ØB) Ù (B Ú A) Ù (B Ú ØC) Ù (A Ú ØC) Ù (A Ú C).

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

F = (Ø A Ú ØB) Ù (B Ú A) Ù (B Ú ØC) Ù ((A Ú C) Ù (A Ú ØC)).

До підформули ((A Ú ØC) Ù (A Ú C)) застосуємо закон дистрибутивності та виконаємо спрощення:

F = (Ø A Ú ØB) Ù (B Ú A) Ù (B Ú ØC) Ù A.

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

F = (Ø A Ú ØB) Ù (A Ù (A Ú B)) Ù (B Ú ØC).

До підформули (A Ù (A Ú B)) застосуємо закон поглинання (F₁ Ù (F₁ Ú F₂) = F₁):

A Ù (A Ú B) = А.

Отже, F = (Ø A Ú ØB) Ù A Ù (B Ú ØC).

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

F = (A Ù (Ø A Ú ØB)) Ù (B Ú ØC).

Застосовуючи закон дистрибутивності до підформули (A Ù (Ø A Ú ØB)) й виконуючи спрощення, маємо:

F = (A Ù ØB) Ù (B Ú ØC).

Застосовуємо закон дистрибутивності до F та виконуємо спрощення:

F = A Ù ØB Ù ØC.

Остання формула є ДНФ, яка складається з одного кон’юнкту. Бачимо, що F ¹ 0, тому існує модель F (принаймні одна). Це означає, що F не є тотожно хибною. Отже, можна зробити висновок, що подана сукупність тверджень сумісна.

 

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

Поделиться: