Одна из основных целей изучения
логики состоит в получении формального аппарата для доказательства того,
является ли данное утверждение следствием других.
Введем
необходимые понятия.
Определение. Формула G называется логическим следствием формул F1,F2,…,Fk, если для любой
интерпретации j из того, что j(F1)=j(F2)=…=j(Fk)=1 следует, что
j(G)=1.
В качестве
примера рассмотрим следующую задачу: выяснить логично ли рассуждение молодого
человека из §2. Напомним, что это рассуждение мы перевели на ….
Приведем противоположный
пример. Докажем, что формула G=Y®X не является логическим
следствием формул F1=XÚY, F2=X®Y, F3=Y. Для этого построим совместную таблицу
истинности формул F1,F2,F3 и G.
Таблица
1.4
X |
Y |
F1=XÚY |
F2=X®Y |
F3=X |
G=Y®X |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
Мы видим (см.
таблицу 1.4), сто если взять интерпретацию j, для
которой j(х)=0, j(y)=1, (т.е. взять третью строку
таблицы), то j(F1)=j(F2)=j(F3)=1, но j(G)=0. Следовательно, формула G не является логическим
следствием формул F1,F2,F3.
Понятие
логического следствия тесно связано с понятием выполнимости.
Определение. Множество формул {F1,F2,…,Fl} называется выполнимым, если существует интерпретация
j такая, что j(F1)=j(F2)=…=j(Fl)=1.
Проверку
выполнимости множества формул {F1,F2,…,Fl} можно провести
построением совместной таблицы истинности этих формул. Если найдется хотя одна
строка, в которой в столбцах формул F1,F2,…,Fl стоят единицы, то это множество формул выполнимо. Если
такой строки нет, то множество формул невыполнимо. Так, множество формул {F1,F2,F3,G} из предыдущего примера
выполнимо, поскольку в таблице 1.4 в первой строке в столбцах этих формул стоят
единицы.
В теме 4 нам
понадобится следующее утверждение.
Теорема 1.2 Формула G является логическим следствием формул F1,F2,…,Fk тогда и только
тогда, когда множество формул
L={F1,F2,…,Fk,ØG}
невыполнимо.
Доказательство. Пусть формула G является следствием
множества формул F1,…,Fk . Предположим, от противного, что множество L выполнимо. Это означает,
что существует интерпретация y
такая, что y(F1)=…=y(Fk)=y(ØG)=1. Но если y(F1)=…=y(Fk)=1, то y(G)=1, поскольку G – логическое следствие
формул F1,…,Fk. Полученное
противоречие y(ØG)=1 и y(G)=1 доказывает, что
множество формул {F1,…,Fk,ØG} невыполнимо.
Пусть теперь
множество формул L невыполнимо.
Рассмотрим интерпретацию j
такую, что j(F1)=…=j(Fk)=1. Поскольку L невыполнимо, то j(ØG)=0. Если j(ØG)=0, то j(G)=1. Следовательно, из
равенств j(F1)=…=j(Fk)=1 следует
равенство j(G)=1. Это означает, что G – логическое следствие
множества формул F1,…,Fk.
|