Двойственные формулы

Определение. Формула U^d называется двойственной к приведенной формуле U, если она получена заменой операций конъюнкций на дизъюнкции и наоборот.

Теорема 3.1 (принцип двойственности). Пусть U () – приведенная формула, тогда U^d () = U( ).

Доказательство. Число логических операций в формуле U называется рангом формулы и обозначается r (U).Проведем доказательство индукцией по k = r (U).

1⁰. k = 0. В этом случае U = X_i, следовательно, U^d = X_i º º Ø U ().

2 ⁰. Предположим, что теорема верна при k £ m.

3 ⁰. Покажем, что она верна при k = m + 1.

Пусть U₁ и U₂ – подформулы U. Каждая из них образована посредством не более, чем m операций, и следовательно, для них теорема верна.

Возможны следующие случаи

а) U = Ø U₁;

б) U = U₁ Ù U₂;

в) U = U₁ Ú U₂.

Случай а) эквивалентен условию 1⁰ и при нем теорема верна. В случаях б) и в) заменим в каждой из U_i конъюнкцию на дизъюнкцию и наоборот. По определению двойственности будем иметь, соответственно, б): U^d = U Ú U и в): U^d = U Ù U .

В силу законов де Моргана и предположения индукции будем иметь в случае б):

U^d = U Ú U = (Ø U₁ ()) Ú (Ø U₂ ()) º

º Ø (U₁ () Ù U₂ ()) = Ø U ().

В случае в) выкладки аналогичны. Теорема доказана.

Следствие. Если U – ТИ-формула, то U^d – ТЛ-формула.

Теорема 3.2. Если U º V, то U^d º V^d.

Доказательство. Если U º V, то (Ø U) º (Ø V). Значит, в силу теоремы 2.6, U^d (Х₁, …, Х_n) = Ø U () и V^d (Х₁, …, Х_n) = Ø V ().

Отсюда: U^d = (Ø U ()) º (Ø V ()) = Ø V^d. В силу транзитивности эквиваленции, получим U^d º V^d , что и требовалось доказать.

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