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


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

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

Пример 1.

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

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

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

x y F1Ú F2=`х & у F3=Ø(& у)

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

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

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

F1 = хÚ х Ú, F2=(x½у) Å, F3= xу Å (х Ú у).

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

x y F1= хÚ х Úу F2 =(x½у) Å F3 =xу Å (х Ú у)

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

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

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

Определение. Обратными (инвертированными) называют значения`an и`bn n-местного булевого вектораn, у которых различаются все компоненты:b i =`a i при всех 1£ i £ n. Обозначим их как`bn =`a n* .

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

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

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

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

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

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

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

f1 (00) = 0=`1 =` f2 (11), f 1 (01)=0=`1 =`f2 (10),

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

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

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

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

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

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

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

F *(n) = f * ( f1* (n),..., fk* (n)).

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

F *(n) = `F (n* ) = `f ( f1(n*) , ... , fk (n*)) =

`f (`f1* (n),...,`fk* (n)) = f * ( f1* (n),..., fk* (n)).

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

ЗАДАЧИ

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

а) F1=хуÚ z и F2= хÚ уz; б) F1=(х®у) Å у и F2=1;

в) F1=х¯ уz и F2=¯(x, y, z) Ú`у z Ú у`z .

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

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

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

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

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

а) f1= х | у и f2= х¯ у;б) f1= х| у и f2= хÅ у ; в) f1 = (10100010)и f2= (11100000);г) f1=(10100010)и f2= (10111010).

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

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

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

&(n)=Ú(n)*,¯(n)=|(n)*.

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



Дата добавления: 2020-10-14; просмотров: 406;


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2024 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.018 сек.