Эквивалентность формул. Тавтологии. Законы логики. Двойственность

Для каждого n количество n-местных взаимно различных булевых функций ограничено. В то же время, можно показать, что число возможных формул, составленных из n переменных, счетно. Отсюда следует, что функции могут быть представлены формулами неединственным образом.

Определение. Формулы F₁ и F₂ эквивалентны, если реализуемые ими функции совпадают, т.е. имеют одни и те же значения истинности на одинаковых наборах переменных. Преобразование формулы F₁ называют эквивалентным, если вновь получаемая формула F₂ эквивалентна ей.

Пример 1.

1. Формулы F₁= х Ú`у и F<sub>2</sub>=`х & у неэквивалентны, поскольку существуют наборы значений переменных (например, х=0, у=0), где соответствующие функции принимают различные значения.

2. Формулы F₁= х Ú`у и F₃= Ø(х & у)эквивалентны, поскольку реализуемые ими функции совпадают.

Проверку эквивалентности проще всего проводить на таблицах истинности. Ниже приведены таблицы истинности для функций, реализующих формулы F₁,F₂ и F₃. Векторы истинности у F₁ и F₃совпадают, у F₁ и F₂― нет.

Определение. Формула называется тождественно истинной (ложной), если реализуемая ею функция является константой 1 (0). Тождественно истинные формулы также называют тавтологиями, тождественно ложные функции ― противоречиями.

Тавтологии являются теоремами алгебры логики. Они задают правильные рассуждения, верные при любых значениях высказываний, входящих в них.

Пример 2. Выяснить, будут ли тавтологиями формулы:

F₁ = хÚ х Ú`у , F₂=(x½у) Å xу , F₃= xу Å (х Ú у).

Решение. Из нижеприведенных таблиц истинности для функций, реализующих формулы F₁, F₂ и F₃, следует, что формулы F₁, F₂ ― тавтологии (векторы истинности у них состоят только из единиц), F₃не является тавтологией, так как соответствующий ей вектор истинности имеет нули.

Замечание. В процессе выяснения, является ли некоторая формула F тавтологией или противоречием, фактически проверяется её эквивалентность константам 1 и 0.

Можно показать, что количество всех возможных тавтологий счетно для любого числа n переменных, используемых в них.

Определение. Основные, наиболее употребительные тавтологии, которые задают эквивалентные преобразования формул, называют законами алгебры логики.

Перечислим их.

1. Коммутативные законы сложения и умножения:

х Ú у = у Ú х, х & у = у & х.

2. Ассоциативные законы сложения и умножения:

( х Ú у) Ú z = х Ú(у Ú z) = х Ú у Ú z ,

( х & у) & z = х & (у & z) = х & у & z.

3. Дистрибутивные законы:

х & ( у Ú z) = х & у Ú х & z,

х Ú у & z = ( х Ú у)&(х Ú z).

4. Правила де Моргана снятия отрицания:

Ø (х & у) =`хÚ`у,Ø (х Ú у) =`х & у.

5. Идемпотентность:

х Ú х = х, х & х = х.

6. Правила поглощения:

х Ú (х & у)= х, х & (хÚ у)= х.

7. Закон противоречия:

х &`х = 0.

8. Закон исключения третьего:

х Ú`х = 1.

9 Операции с константами:

х Ú0 = х, х Ú 1= 1, х & 0 =0, х & 1 = х.

Справедливость перечисленных законов может быть проверена, как и обычная эквивалентность формул.

Пример 3. Доказать первое правило де Моргана.

Решение. Построим векторы значений истинности функций для формул Ø (х & у)и `х Ú`у. Как видно из приведенных ниже таблиц, они полностью совпадают (столбцы 4 и 7).

Отсюда следует, что данная формула справедлива при любых значениях входящих в нее переменных и является тавтологией.

Законы логики могут быть использованы для аналитического упрощения формул. Также для преобразования формул можно использовать принцип двойственности.

Определение. Обратными (инвертированными) называют значения`a<sup>n</sup> и`bⁿ n-местного булевого вектора`х<sup>n</sup>, у которых различаются все компоненты:b <sub>i</sub> =`a _i при всех 1£ i £ n. Обозначим их как`b<sup>n</sup> =`a ^n* .

Пример 4.(0,1,0)*=(1,0,1);(1,1,0)*=(0,0,1);(1,0)*=(0,1).

При табличном задании обратные наборы`a<sup>n</sup> и`bⁿ находятся на одинаковых расстояниях от начала и конца таблицы, поскольку соответствующие им двоичные числа aи bсвязаны соотношением a + b = 2ⁿ - 1.

Определение. Симметричными называют такие n-местные булевы функции f(х ⁿ), которые принимают одинаковые значения истинности на всех обратных наборах, т.е. f (aⁿ ) = f (a^n* )при всех`aⁿ ÎВ ⁿ.

Вектор истинности таких функций симметричен относительно своей средины. Симметричными являются константы 0, 1, сумма по модулю 2, эквивалентность и т.д. Все пороговые функции не симметричны.

Определение. Двойственными называют такие n-местные функции f и g, для которых на всех наборах aⁿ Î В ⁿ справедливо равенство f(aⁿ ) = g(a^n* ), т.е. на обратных наборах f и g принимают различные значения истинности. Двойственность обозначается как f = g*.

Пример 5. Проверить двойственность функций f ₁ = х & у, f₂ = х Ú у .

Решение. Из соотношений

f₁ (00) = 0=`1 =` f₂ (11), f ₁ (01)=0=`1 =`f₂ (10),

f ₁ (10) =0 =`1=` f₂ (01), f ₁ (11)=1=`0=` f₂ (00),

следует, что функции являются двойственными, f ₁ = f ^* ₂.

Понятие двойственности симметрично, поэтому из f = g* всегда следует: g = f *.

У симметричных функций двойственность совпадает с отрицанием, так как f ^*(`х <sup>n</sup>) = f (`х ^n*)=`f (`х ⁿ). Поэтому 0* =1, 1* = 0, (х Å у)* = х Å у Å1=(х º у) и т.д. У несимметричных функций, например, пороговых, понятие двойственности не сводится к отрицанию: х* =х ¹`х,`х* = `х ¹ х, ( х & у)* = ( х Ú у)¹ Ø ( х & у), (х| у)* = ( х¯ у) ¹ Ø (х| у).

Определение. Рассмотрим сложную n-местную функцию следующего вида: F(`х <sup>n</sup>) =f ( f<sub>1</sub>(`х ⁿ),..., f_k (`х ⁿ)).

Функцию f в дальнейшем будем называть внешней, функции f₁, .. ., f_k ― внутренними.

Принципом двойственности называют следующее соотношение:

F ^*(`х <sup>n</sup>) = f <sup>*</sup> ( f<sub>1</sub><sup>*</sup> (`х ⁿ),..., f_k^* (`х ⁿ)).

Справедливость его следует непосредственно из определения двойственности:

F ^*(`х <sup>n</sup>) = `F (`х <sup>n*</sup> ) = `f ( f₁(`х <sup>n*</sup>) , ... , f<sub>k</sub> (`х ^n*)) =

`f (`f₁^* (`х <sup>n</sup>),...,`f_k^* (`х <sup>n</sup>)) = f <sup>*</sup> ( f<sub>1</sub><sup>*</sup> (`х ⁿ),..., f_k^* (`х ⁿ)).

Применение принципа двойственности упрощает многие преобразования формул. В частности, он позволяет аналитически доказывать одни законы логики на основе других. Здесь используется следующее очевидное свойство формул: если А=В, то А*=В*. Например, первое правило де Моргана можно представить в виде А=В, где А= Ø(х & у), В =`хÚ`у. Переходя к А* = Ø(х Ú у), В* =`х &`у,получим второй закон.

ЗАДАЧИ

1. Проверить эквивалентность следующих пар формул:

а) F₁=хуÚ z и F₂= хÚ уz; б) F₁=(х®у) Å у и F₂=1;

в) F₁=х¯ уz и F₂=¯(x, y, z) Ú`у z Ú у`z .

2. Доказать справедливость:

а) ассоциативного закона сложения,

б) первого дистрибутивного закона,

в) первого правила поглощения.

3. Проверить, будут ли двойственными функции:

а) f₁= х | у и f₂= х¯ у;б) f₁= х| у и f₂= хÅ у ; в) f₁ = (10100010)и f₂= (11100000);г) f₁=(10100010)и f₂= (10111010).

4. Найти с использованием принципа двойственности функции, двойственные к: а) ху Ú уz;б) ху | (х Ú z) у; в) х¯ у .

5. Доказать, что функция, двойственная к пороговой, также будет пороговой.

6. Доказать, что для обобщенных функций верно:

&(`х<sup>n</sup>)=Ú(`хⁿ)*,¯(`х<sup>n</sup>)=|(`хⁿ)*.

7. При помощи принципа двойственности доказать cправедливость:

а) ассоциативного закона умножения на основании ассоциативного закона сложения,

б) второго правила поглощения на основании первого.

8. Доказать эквивалентность формул:

а) хÚ (`х & у)и хÚ у;б) х| у иØ ( х & у); в) х¯у иØ ( хÚ у);г)(х º у)и(х®у)(у®х);д) (х®(у®z))и(ху ® z).

9. Проверить, будут ли тавтологиями следующие формулы:

а) (х®у) (у®z) ® ( х®z); б) (х®у)х ® у; в) ху Ú ху = х;г) z® ( х ¯ у ) º (х| z ) ( хÚ`у Ú`z ) ;д) х ® ( у ® х).

10. Доказать, что:

а) если А и В ― тавтологии, то А& (`В Ú`А ) ― противоречие,

б) если А и В ― противоречия, то С Ú`А Ú В ― тавтология.

11. A,B,C,D ― некоторые высказывания. Найти истинность составных высказываний:

a) C Ú B`D,если B®D =Л;

б) А®C, если А Ú `B = Л, B`С =И;

в) (А®C)Å D, если `А Ú C = И, A Å C =И, B ® D = Л;

г) В Ú С, если `B Å C = Л, А & С= И;

д) С& А, если Ø (АÚ В)= И, А® C = И, С Å D = Л;

е) А Å C, если АÚ ВÚ С = И, (С®А) & (А® C) = Л.