ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 16.04.2021
Просмотров: 880
Скачиваний: 9
18
B
» –
A
B
(
,
AB A
B
) –
конъюнкция
; «
A
или
B
» –
A
B
–
дизъюнкция
; «ес-
ли
A
, то
B
» –
A
B
–
импликация
; «
A
, если и только если
B
» –
A
B
–
двойная импликация.
Формальные определения логических связок задаются в
виде
таблиц истинности
, определяющих
истинностные значения
сложных
предикатов через истинностные значения операндов:
A B
A A
B A
B A
B A
B
и и
л
и
и
и
и
и л
л
и
л
л
л и
и
л
и
и
л
л л
л
л
и
и
1.2.2. Формулы логики высказываний.
В результате последовательного применения логических связок к простым
предикатам, обозначенным буквами, получаются
формулы логики высказыва-
ний.
Порядок действий в них, как и в алгебраических формулах, задаётся с по-
мощью скобок.
Например, для формулы (((
)
)
(
))
A
B
A
B
B
дей-
ствия в порядке их выполнения можно пронумеровать следующим образом:
(((
)
)
(
))
1
2
4
3
5
A
B
A
B
B
Словами данную формулу можно прочесть так: если отрицание
A
влечёт
B
и
A
влечёт
B
, то справедливо
B
.
Как и в алгебре, в логике принято
соглашение
о порядке действий,
в соответствии с которым при отсутствии скобок операции
выполняются в следующем порядке: , , , { , }
(импликация и двойная
импликация считаются действиями одной ступени, то есть при отсутствии ско-
бок они выполняются в порядке слева направо).
Например, рассмотренную
выше формулу можно записать в виде (
)
(
)
A
B
A
B
B
. Если же опу-
стить и оставшиеся четыре скобки, то порядок действий и смысл формулы бу-
дет иной:
1
3
2
4
5
A
B
A
B
B
1.2.3. Упражнение.
Записать формулу на обычном языке. Найти интерпрета-
ции предложений
, ,
A B C , в которых она истинна и ложна.
1.
A
B
C
A
.
7.
А
С
С
В
А
.
2.
(
(
))
(
)
A
B
C
A B
C
.
8.
В
А
С
В
В
С
А
.
3.
(
)
A
B
A
B
.
9.
С
В
С
В
А
С
А
.
4.
(
)
(
)
A
B C
B
A
.
10.
С
В
А
В
А
.
5.
A
B
C
A
(
)
.
11.
В
С
С
В
А
.
6.
А
С
В
С
В
А
.
12.
В
А
С
В
С
А
.
19
1.2.4. Формализация в логике высказываний.
Сложности записи утверждения, сформулированного на обычном языке об-
щения, в виде логической формулы аналогичны проблемам перевода с одного
языка на другой. Правда, следует заменить, что язык формальной логики суще-
ственно беднее любого языка общения, что значительно облегчает задачу пере-
вода, которую можно осуществлять, придерживаясь следующего алгоритма. В
предложении следует выделить основную его форму ( “не верно, что ...”, “... и
...” , “... или ...”, “если …, то ...”, “ …, тогда и только тогда, когда ...” и т.п.), и
заменить её на соответствующую логическую формулу (
,
,
,
A A B A B
,
A
B A
B
). Затем с каждой частью предложения, обозначенной в получен-
ной формуле буквами
А
и
В
, и представляющей собой самостоятельное утвер-
ждение, проделать ту же процедуру, если только утверждение не оказывается
простым высказыванием. После этого буквы
А
и
В
в первоначальной формуле
заменяются на полученные вместо них формулы. Повторяем процесс формали-
зации до тех пор, пока все буквы формулы не будут соответствовать простым
высказываниям. В процессе формализации необходимо следить за тем, чтобы
разные вхождения одного и того же высказывания обозначались одной буквой,
а разные высказывания были обозначены разными буквами.
Например, формализуем утверждение “Произведение
ab
положительно в том
и только в том случае, когда
a
и
b
– оба положительны или оба отрицатель-
ны”. Основная форма этого предложения – “ … в том и только в том случае, ко-
гда ...”, аналогичная форме “ …, тогда и только тогда, когда...”. Заменим её на
формулу
A
X
, где
A
– “ Произведение
ab
положительно ” и
X
– “
a
и
b
–
оба положительны или оба отрицательны ”.
A
является простым высказывани-
ем, а
X
имеет форму “... или ...”, заменяем её на
Y
Z
в первоначальной фор-
муле:
A
Y
Z
. Высказывания
Y
– “
a
и
b
– оба положительны ” и
Z
– “
a
и
b
– оба отрицательны ” имеют одну и ту же форму, которую легче определить,
переформулировав эти предложения без изменения смысла следующим обра-
зом.
Y
– “
a
– положительно и
b
– положительно ”,
Z
– “
a
– отрицательно и
b
– отрицательно ”. Форму “... и ...” этих предложений заменим на формулы
B
C
и
D
E
. Подставляя их в основную формулу вместо
Y
и
Z
, получим оконча-
тельно
A
B
C
D
E
.
B
– “
a
– положительно”,
C
– “
b
– положительно ”,
D
–
“
a
– отрицательно”,
E
– “
b
– отрицательно ” – простые высказывания.
1.2.5. Упражнение.
Записать следующие утверждения в виде формул логики
высказываний.
1.
Положительное число
T
является периодом функции
f
в том и только в том
случае, когда
х
принадлежит области определения
f
только вместе с
x T
и
выполнено равенство
f x T
f x
.
2.
Число
х
принадлежит области определения
f
, но
f x T
f x
.
3.
Неверно, что для вещественного числа
x
и для натурального числа
n
нера-
венства
10
xn
n
и
10
x
выполнены одновременно.
20
4.
Неверно, что утверждения
х
большее нуля, число
а
меньше нуля, их произ-
ведение
0
ax
выполнены одновременно.
5.
Функции
f
является возрастающей в том и только в том случае, когда для
1
2
x
x
выполнено неравенство
1
2
f x
f x
.
6.
Для
х
выполнено неравенство
0
ax
, причём число
а
меньше нуля.
1.2.6. Формализация необходимых и достаточных условий.
Остановимся особо на вопросе формализации предложений, содержащих сло-
ва “необходимо” и “достаточно” в качестве основной формы. Оба эти слова
выражают импликацию, а в сочетании друг с другом двойную импликацию.
Для того, чтобы правильно выбрать направление импликации в этом случае,
нужно определить какой предикат в предложении играет роль необходимого
(достаточного) условия. Тогда второй основной предикат предложения автома-
тически играет роль достаточного (необходимого) условия. Правильное
направление стрелки импликации – от достаточного условия к необходимому.
Например, в предложении “Справедливости неравенства
1
a
достаточно для
выполнения неравенства
0
b
” предикат
A
– “справедливо неравенства
1
a
”
является достаточным условием, а предикат
B
– “выполнено неравенство
0
b
” автоматически определяем, как необходимое условие. Исходное предло-
жение представимо импликацией
A
B
.
1.2.7. Упражнение.
Записать следующие утверждения в виде формул логики
высказываний.
1
. Для того, чтобы дробь
b
a
была меньше нуля, необходимо, чтобы
b
было от-
рицательно.
2.
Для того, чтобы
z
не принадлежал
D
, необходимо, чтобы
y
не принадлежал
C
, а для того чтобы
z
принадлежал
D
, достаточно, чтобы
x
принадлежал
B
.
3.
Неравенство
0
d
необходимо для выполнения неравенство
1
c
и доста-
точно для выполнения неравенства
1
a
.
4.
Для того, чтобы дробь
y
x
принадлежала множеству
A
, необходимо и доста-
точно, чтобы
x
принадлежал
B
и
y
принадлежал
C
или
x
принадлежал
D
и
y
принадлежал
E
.
5.
Для того чтобы функция
y x
удовлетворяла первому и второму уравнениям
системы, достаточно, чтобы оно удовлетворяло третьему, а для того чтобы
y x
не удовлетворяла второму уравнению, необходимо, чтобы
y x
не удо-
влетворяла первому уравнению.
6.
Выполнение утверждения Е есть необходимое условие для выполнения
утверждения А, а не выполнения D достаточно для не выполнения А.
21
1.3. Cледствие в логике высказываний
1.3.1. Стандартные интерпретации.
Стандартной интерпретацией
предиката или списка предикатов будем
называть придание всем входящим в них
простым предикатам
истинностных
значений
“
и
” или “
л
” – в отличие от рассматривавшейся ранее
смысловой ин-
терпретации,
когда входящим в предикаты
словам
придавались различные
смысловые значения
. При этом различным
вхождениям
одного и того же про-
стого предиката должны придаваться одинаковые истинностные значения.
Например, если в сложном предикате или списке предикатов участвуют толь-
ко простые предикаты
A
и
B
, то полный перечень стандартных интерпретаций
можно записать в виде:
ии, ил, ли, лл – первая буква задаёт истинностное зна-
чение A, вторая - B .
При наличии трёх простых предикатов , ,
A B C
будет во-
семь стандартных интерпретаций; их принято располагать в алфавитном поряд-
ке:
иии, иил, или, илл, лии, лил, лли, ллл.
Заметим, что для последней по алфавиту
буквы
C
значения чередуются через одно, для
B
- через 2, для
A
– через 4. Та-
кой порядок всегда приводит к алфавитному расположению всех стандартных
интерпретаций. Заметим также, что при увеличении числа простых предикатов
на 1 количество стандартных интерпретаций увеличивается вдвое, так что для
n
простых предикатов будет 2
n
интерпретаций.
1.3.2. Таблицы истинности.
Если задан сложный предикат, то с помощью определения логических опера-
ций можно во всех его стандартных интерпретациях найти истинностное зна-
чение самого предиката, т.е. получить
таблицу истинности
сложного предика-
та. Рассмотрим два примера.
(
)
4 2 3 1
3 2 5 4 1
A
B
A
B
л и и и
л и л л и
и и л л
л и и и л
и л л и
и л и л и
и л л л
и л и и л
Во вторых строчках обеих таблиц проставлены номера, указывающие на
порядок заполнения столбцов. В столбцах 1 и 2 формируются стандартные ин-
терпретации в алфавитном порядке – так, как описано в предыдущем пункте.
Остальные столбцы заполняются последовательно с помощью таблиц истинно-
сти логических операций.
1.3.3. Упражнение.
Построить таблицы истинности для формул из упраж-
нения
1.2.3.
1.3.4. Таблицы истинности и логическое следствие.
Таблицы истинности дают полную информацию об истинностных значениях
сложных предикатов во всех
стандартных
интерпретациях. Поскольку в каж-
дой
смысловой
интерпретации все простые предикаты принимают определён-
22
ные истинностные значения, она эквивалентна некоторой стандартной интер-
претации. Поэтому с помощью таблиц истинности можно полностью решать
вопрос о существовании или отсутствии контрпримеров для любого умозаклю-
чения в логике высказываний.
Например, если в п. 1.3.2 сравнить результи-
рующий столбец 4 в первой таблице с результирующим столбцом 5 второй, то
мы увидим, что они одинаковы. Это означает, что
(
) |
A
B
A
B
, и
наоборот, (
) |
A
B
A
B
. Вместе эти два соотношения записывают в виде
(
) | |
A
B
A
B
и говорят, что данные формулы
логически эквивалентны
.
1.3.5. Направленная табличная процедура.
Поиск контрпримера путем перебора
всех
стандартных интерпретаций, т.е. по-
строения полной таблицы истинности данного умозаключения, может оказаться
слишком громоздким, так как число 2
n
всех стандартных интерпретаций очень
быстро растёт с ростом
n
. Кроме того, в логике предикатов, как мы увидим,
множество стандартных интерпретаций бесконечно, так что полный перебор
вообще невозможен. Поэтому мы выработаем
направленную табличную проце-
дуру
, не связанную с перебором всех стандартных интерпретаций.
На первых
шагах составляется
система логических уравнений,
приписывающая всем по-
сылкам значение “
и
”, а заключению - “
л
”. Если с помощью таблиц истинности
логических связок для этой системы будет найдено хотя бы одно решение, т.е.
набор значений простых предикатов, удовлетворяющий этой системе, то мы
получим контрпример к данному умозаключению; если же окажется, что си-
стема не имеет решений, то можно сделать вывод, что умозаключение
логично
.
Методы решения систем логических уравнений рассмотрим на ряде примеров.
1.3.6. Примеры доказательств направленной процедурой.
В следующих таблицах показано составление и решение систем логических
уравнений для двух умозаключений.
?
,
|
5 1 6 2 4
3
A
B
A
B
л и и и л да л
?
,
|
5 1 6 2 4
3
A
B
A
B
л и л и л нет л
На первых двух шагах посылкам присваивается значение «
и
», а на треть-
ем – заключению значение «
л
»; тем самым составляется система логических
уравнений для поиска контрпримера. Шаг 4 в обеих таблицах следует из 2 и
определения отрицания, 5 – из 4 (перенос). Шаг 6 в левой таблице следует из 1,
5 и определения дизъюнкции. В правой – из 3 (перенос).
В левой таблице получено (и отмечено подчёркиванием) противоречие
между шагами 6 и 3. Оно показывает, что контрпримера не существует, т.е. за-
ключение логически следует из посылок; это зафиксировано словом «
да
» под
знаком логического следствия.
В правой таблице противоречий нет, т.е. найден контрпример:
A
B
л
.
Значит, заключение не следует логически из посылок; это отмечено словом
«
нет
».