Полная версия

Главная arrow Математика, химия, физика

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

Равносильные формулы

Рассмотрим таблицы истинности для двух формул F = А^> В и Н = -^А/ В.

Таблица 3

А

в

Ы)

А^В

('Л) V в

0

0

1

1

1

0

1

1

1

1

1

0

0

0

0

1

1

0

1

1

Из табл. 3 видно, что при всех наборах значений элементарных высказываний А и В формулы F и Н принимают одинаковые значения.

Определение 3,2. Две логические формулы F и FI называются равносильными, если они принимают одинаковые значения на любом наборе значений входящих в них элементарных высказываний. Тот факт, что формулы F и Н равносильны, обозначают F — Н.

Таким образом, с помощью табл. 3 установлена равносильность

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

Определение 3.3. Формула А называется тавтологией (тождественно истинной формулой), если при любых значениях входящих в нее переменных она принимает значение «истина» (Л = 1).

С помощью таблицы истинности тавтологию можно определить как формулу, для которой соответствующий ей в таблице истинности столбец целиком состоит из 1. Таким образом, построение таблицы истинности - это эффективная процедура для решения вопроса о том, является ли данная формула тавтологией.

Из таблицы истинности для импликации легко следует, что при любых значениях логической переменной А формула Л^Л принимает значение 1, т. е. является тавтологией.

Из определения конъюнкции легко получаем, что формула Акс-^А всегда принимает значение 0 («ложь»). Тогда формула -i(Акс^А) принимает только одно значение - 1 («истина»), т. е. является тавтологией.

Мы встретились с формулой Акс^А, которая всегда принимает ложное значение. Такие формулы называют тождественно ложным,и формулами (противоречиям,и). Очевидно, что формула А является тавтологией тогда и только тогда, когда формула -иА - противоречие.

Сформулируем несколько утверждений общего характера о тавтологиях.

  • 1. Если А, А^В - тавтологии, то тавтологией является В.
  • 2. Если А - тавтология, содержащая пропозициональные переменные А, Ао, Лп, и В получается, из А подстановкой, формул Фь Ф>2, ... , Фп вместо А{, /U, Ап соответственно, то В есть тавтология, т. е. подстановка в тавтологию есть тавтология.

П р и м е р 3.3. Показать, что формула F = M—> (Л—> А) является тавтологией.

Предположим противное, т. е., что А—>(В—>А) = {). Тогда из определения импликации заключаем, что /1 = 1, а В^А — 0. А из равенства В —>/1 = 0 следует, В — 1, А — 0. Получили противоречие с тем, что А— 1.

Метод доказательства, который был использован в примере 3.3, называется методом от противного или методом, косвенного доказательства.

Рассмотрим формулы Ф] = СУ А и Ф2 = —^С/ А. Заменим в формуле F примера 3.3 пропозициональную переменную Л на Фц а В на Ф-2, соответственно. Получим новую формулу F = С&;Л—> (-<(7 V Л—>(7&:Л), которая по утверждению 2 является тавтологией. Убедимся в этом, составив для нее таблицу истинности.

Таблица 4

А

С

ЬС)

(“1(7) V Л

СУА

(-iC)vA^CkA

И

0

0

1

1

0

0

1

0

1

0

0

0

1

1

1

0

1

1

0

0

1

1

1

0

1

1

1

1

Если в формуле F только Л заменить на Ф i, то получим еще одну тавтологию F? = СУ А —> (В»СУ А).

Упражнение 2. С помощью таблицы истинности показать, что формула F) является тождественно истинной.

С помощью определения 3.2 на множестве всех логических формул фактически задано бинарное отношение «равносильности» (=), которое, очевидно, является рефлексивным, симметричным и транзитивным. Таким образом, отношение равносильности логических формул является отношением эквивалентности, а значит, разбивает множество всех логических функций на классы эквивалентности. В частности тавтологии образуют класс эквивалентности, который содержит логическую константу 1, а тождественно ложные формулы - класс формул, эквивалентных логической константе 0. Известно, что любой элемент из класса эквивалентности можно взять в качестве его представителя. На этом основаны так называемые эквивалентные преобразования логических формул, которые позволяют переходить от одних формул к другим, в определенном смысле более простым формулам, но эквивалентным (равносильным) данным. Это лежит в основе многих приложений математической логики и объясняет особый интерес к понятию равносильности. Очевидно, что, чем больше у нас в запасе равносильных соотношений, тем проще мы будем решать задачи упрощения логических формул.

Рассмотрим важнейшие равносильности алгебры логики.

  • 1. Законы коммутативности: АУВ — В У А, АV В = В V Л.
  • 2. Законы ассоциативности: (Л У В) У С — АУ{В У С)
  • (АУВ)УС = АУ(ВУС).

3. Законы дистрибутивности: Л&( /3 УС) = (Л&/3) У (Л&С),

АУ{В&С) = {АуВ)&{АуС).

  • 4. Законы идемпотентности: Л&Л = Л, АУ А = А.
  • 5. Законы нуля и единицы: Л&1 = Л, Л&0 = 0,

АУ 1 = 1, ЛЧ0 = Л.

  • 6. Закон противоречия: Л&-|Л = 0.
  • 7. Закон исключенного третьего: Л V -«Л = 1.
  • 8. Закон двойного отрицания: -п(-|Л) = Л.
  • 9. Законы де Моргана: -п(А&В) = ^АУ ^В,
  • —>( Л V В) = —'A&l~'B.
  • 10. Законы поглощения: А&с(ВУ А) = Л, Л V (BSzA) = A.

Часть тождеств (1, 5, 6, 7, 8) очевидны, другие легко проверяются с помощью таблиц истинности.

Для примера докажем один из законов поглощения, не составляя таблицу истинности.

П р и м е р 3.4. Доказать равносильность: Л<4( /3V Л) = Л.

Рассмотрим формулу F = А&(ВУА). Если в ней Л = 1, то очевидно, что ВУА = 1 при любом значении /3, и тогда А&с(ВУА) = 1 как конъюнкция истинных высказываний. Пусть Л = 0, тогда по определению конъюнкции А&(ВУ А) = {) при любых значениях В. Таким образом, во всех случаях значения формулы F совпадают со значениями Л, что означает их равносильность, т. е. F = A.

Отметим, что логическая операция эквивалентности (=) и понятие равносильности связаны между собой следующим образом: формулы F и Н равносильны, m. е. F= H, тогда и только тогда, когда, формула F = /7 является 'тавтологией.

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>