Пример 1. 1. Формулы F1= х Ú`у и F2=`х & у неэквивалентны, поскольку существуют наборы значений переменных (например
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½у) Å xу , F3= xу Å (х Ú у).
Решение. Из нижеприведенных таблиц истинности для функций, реализующих формулы F1, F2 и F3, следует, что формулы F1, F2 ― тавтологии (векторы истинности у них состоят только из единиц), F3не является тавтологией, так как соответствующий ей вектор истинности имеет нули.
x | y | F1= хÚ х Úу | F2 =(x½у) Å 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) = Л.
Дата добавления: 2015-10-05; просмотров: 971;