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

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

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

Пример 1.

1. Формулы F₁= х у и F₂=х  у неэквивалентны, поскольку существуют наборы значений переменных (например, х=0, у=0), где соответствующие функции принимают различные значения.

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

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

x	y	F1=х у	F2=х  у	F3=(х  у)
0	0	1	0	1
0	1	0	1	0
1	0	1	0	1
1	1	1	0	1

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

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

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

F₁ = х х у , F₂ =(xу)  xу , F₃ = xу  (х  у).

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

x	y	F1= х х у	F2 =(xу)  xу	F3 =xу  (х  у)
0	0	1	1	0
0	1	1	1	1
1	0	1	1	1
1	1	1	1	0

Замечание. В процессе выяснения, является ли некоторая формула 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).

x	y	х  у	(х  у)	х	y	х y
0	0	0	1	1	1	1
0	1	0	1	1	0	1
1	0	0	1	0	1	1
1	1	1	0	0	0	0

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

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

Определение. Обратными (инвертированными) называют значенияⁿ иⁿ n-местного булевого векторахⁿ, у которых различаются все компоненты:  _i = _i при всех 1  i  n. Обозначим их какⁿ = ^n* .

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

При табличном задании обратные наборыⁿ иⁿ находятся на одинаковых расстояниях от начала и конца таблицы, поскольку соответствующие им двоичные числа  и  связаны соотношением  +  = 2ⁿ - 1.

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

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

Определение. Двойственными называют такие n-местные функции f и g, для которых на всех наборах ⁿ  В ⁿ справедливо равенство f(ⁿ ) = g(^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 ^*(х ⁿ) = f (х ^n*) =f (х ⁿ). Поэтому 0* = 1, 1* = 0, (х  у)* = х  у  1 = (х  у) и т.д. У несимметричных функций, например, пороговых, понятие двойственности не сводится к отрицанию: х* =х х,х* = х  х, ( х  у)* = ( х  у)   ( х  у), (х у)* = ( х у)   (х у).

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

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

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

F ^*(х ⁿ) = f ^* ( f₁^* (х ⁿ),..., f_k^* (х ⁿ)).

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

F ^*(х ⁿ) = F (х ^n* ) = f ( f₁ (х ^n*) , ... , f_k (х ^n*)) =

f (f₁^* (х ⁿ),...,f_k^* (х ⁿ)) = f ^* ( f₁^* (х ⁿ),..., 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. Доказать, что для обобщенных функций верно:

(хⁿ)=(хⁿ)*,(хⁿ)=(хⁿ)*.

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) = Л.