Дискретная математика

Раздел 1. Математическая логика

Тема 1. Логика высказываний

Логика предикатов в качестве составной и наиболее простой части содержит логику высказываний.

§1. Высказывания и операции над ними

§2. Формулы логики высказываний, интерпретация

§3. Равносильность и законы логики высказываний

Нетрудно привести примеры формул, которые «выражают одно и то же». Таковы, например, формулы XÚY и YÚX. Подобные формулы мы будем называть равносильными. Прежде, чем дать соответствующее определение, условимся о следующем обозначении.


Определение. Формулы F и G называются равносильными, если для любой интерпретации j выполняется равенство j(F)=j(G).

Убедимся в том, что формулы F=X®Y и G=ØXÚY равносильны. Ясно, что если интерпретации j и y совпадают на X и Y, то j(F)=y(F) и j(G)=y(G). Следовательно, для проверки равенства j(F)=j(G) из определения равносильности надо рассмотреть лишь интерпретации, которые различаются на X и Y (а таких интерпретаций четыре) и вычислить соответствующие значения j(F) и j(G). Другими словами, надо составить совместную таблицу истинности формул F и G (см. таблицу 1.2).

Таблица 1.2

X Y F=X®Y ØX G=ØXÚY
1 1 1 0 1
1 0 0 0 0
0 1 1 1 1
0 0 1 1 1

В таблице 1.2 для удобства вычисления значения интерпретаций на G введен промежуточный столбец ØX. Мы видим, что столбцы формул F и G совпадают. Это означает, что формулы F и G равносильны.

Близким к понятию равносильности является понятие тождественной истинности.


Определение. Формула F называется тождественно истинной если для любой интерпретации j выполняется равенство j(F)=1.

Например, формула F=X&Y®X является тождественно истинной. Для проверки равенства j(F)=1 не надо рассматривать все интерпретации, а лишь четыре, которые различаются на атомарных формулах X и Y. Для таких интерпретаций надо вычислить значение формулы F, т.е. составить таблицу истинности формулы F (см. таблицу 1.3). Таблица 1.3 для удобства вычисления значения j(F) содержит промежуточный столбец X&Y.

Таблица 1.3

X Y X&Y F=X&Y®X
1 1 1 1
1 0 0 1
0 1 0 1
0 0 0 1

Мы видим, что столбец формулы F состоит из одних единиц. Это означает, что формула F тождественно истинна.


Теорема 1.1. Формулы F и G равносильны тогда и только тогда, когда формула F«G является тождественно истинной.


Доказательство. Предположим, что формулы F и G равносильны и рассмотрим интерпретацию j. Ясно, что j(F«G)=j(F)«j(G). Поскольку значения истинности j(F) и j(G) совпадают, то по таблице истинности эквиваленции имеем равенства j(F)«j(G)=1. Это означает, что формула F«G тождественно истинна.

Предположим теперь, что формула F«G тождественно истинна и рассмотрим интерпретацию j. Имеем, что 1=j(F«G)=j(F)«j(G). Но из таблицы истинности эквиваленции следует, что если j(F)«j(G)=1, то j(F)=j(G).

Теорема доказана.


В логике высказываний довольно часто приходится проводить преобразования формул, сохраняющие равносильность. Для таких преобразований используются так называемые законы логики высказываний. Приведем список этих законов.

Пусть F,G и Н – некоторые формулы логики высказываний. Тогда следующие формулы равносильны:


1) F&1 и F; 2) FÚ1 и F;
3) F&0 и 0; 4) FÚ0 и F;
5) F&F и F; 6) FÚF и F;
7) F&G и G&F; 8) FÚG и GÚF;
9) F&(G&H) и (F&G)&H; 10) FÚ(GÚH) и (FÚG)ÚH;
11) F&(GÚH) и (F&G)Ú(F&H); 12) FÚ(G&H) и (FÚG)&(FÚH);
13) F&(FÚG) и F; 14) FÚ(F&G) и F;
15) F&ØF и 0; 16) FÚØF и 1;
17) Ø(F&G) и ØFÚØG; 18) Ø(FÚG) и ØF&ØG;
19) ØØF и F; 20) F®G и ØFÚG;
21) F«G и (F®G)&(G®F).  

Доказательство этих равносильностей (законов логики высказываний) легко получается с помощью таблиц истинности. Отметим, что в примере на определение равносильности мы фактически доказали закон 20.

Прокомментируем список законов. Законы 5 и 6 называются идемпотентностью, 7 и 8 – коммутативностью, 9 и 10 – ассоциативностью соответственно конъюнкции и дизъюнкции. Ассоциативность конъюнкции означает, что в конъюнкции трех формул скобки можно ставить как угодно, а, следовательно, вообще не ставить. Из этого утверждения следует, что в конъюнкции четырех, пяти и т.д. любого конечного числа формул скобки можно ставить как угодно и поэтому вообще не ставить. Аналогичное замечание можно сделать и для дизъюнкции.

Законы 11 и 12 называются дистрибутивностями. Более точно, закон 11 – дистрибутивность конъюнкции относительно дизъюнкции, а закон 12 – дистрибутивность дизъюнкции относительно конъюнкции. Для применения этих законов в преобразованиях формул удобно иметь в виду следующий аналог. Заменим в законе 11 формулы F,G и Н соответственно буквами a,b и с, знак & заменим умножением *, а знак Ú – сложением+. Мы получим известное числовое тождество


a*(b+c)-a*b+a*c (*)


Это тождество есть дистрибутивность умножения чисел относительно сложения. В школе применение этого равенства слева направо называется раскрытием скобок, а справа налево вынесением общего множителя. Отличие операций над высказываниями & и Ú от числовых операций * и+состоит в том, что для высказываний выполняются обе дистрибутивности, а для чисел только одна. Сложение не дистрибутивно относительно умножения.

Закон 15 называется законом противоречия, закон 16 – законом исключенного третьего, закон 19 – снятием двойного отрицания. Законы 13 и 14 называются законами поглощения, а законы 17 и 18 – законами де Моргана в честь известного французского математика и логика 19 века.

Имея законы логики высказываний, мы получаем еще один способ доказательства равносильности двух формул, наряду с построением совместной таблицы истинности. Этот способ состоит в переходе от одной формулы к другой с помощью законов. В его основе лежит следующее легко доказываемое утверждение: если в некоторой формуле F заменить подформулу G равносильной ей формулой G′, то получим формулу F′, равносильную исходной формуле F. Проиллюстрируем второй способ на следующем примере: доказать равносильность формул


F=[X&(Z®Y)]Ú[(X®Z)&Y] и

G=(XÚY)&(YÚØZ).


В силу закона 20, формулы Z®Y и X®Z равносильны соответственно формулам ØZÚY и ØXÚZ, поэтому формула F равносильна формуле


F1=[X&(ØZÚY)]Ú[(ØXÚZ)&Y].


Дважды применив дистрибутивность (закон 11) и пользуясь ассоциативностью связок & и Ú, получим, что формула F1 равносильна формуле


F2=(XÚØXÚZ)&(ØZÚYÚØXÚZ)&(XÚY)&(ØZÚYÚY).


В силу коммутативности дизъюнкции, законов 16 и 2, формулы XØXÚZ и ØZÚYÚØXÚZ равносильны 1. Применив теперь законы 1 и 6 и коммутативность дизъюнкции, получим, что формула F2 равносильна G.

§4. Логическое следствие.

§5. Нормальные формы в логике высказываний

§6. Контактные схемы.

Задачи

Ответы, указания и решения

Тема 2. Булевы функции

Тема 3. Логика предикатов

Тема 4. Метод резолюций

Раздел 2. Теория графов

Тема 5. Раскраски

Тема 6. Ориентированные графы и сети


Fair.ru Ярмарка сайтов
Rambler's Top100 Submitter.ru - Free promoting

Дизайн: Alex © 2002
Все вопросы и предложения можно направлять по адресу cad@mail.ustu.ru