![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Доказательство. Рассмотрим табличный метод перебора всех оценок формул. Надо для восьми (почему?) случаев оценок формул a, b, с
a = И, b = И, с = И;
а = И, b = И, с = Л;
и т. д.
а = Л; b = Л, с = Л
убедиться в правильности каждой равносильности.
Теорема 2 (правило равносильных замен переменных).
Пусть а = b и с — формула, в которой выделено одно вхождение переменной X. Пусть са получается из с заменой этого вхождения X на а, а сb из с заменой того же вхождения X на b. Тогда cа ≡ cb.
Доказательство. Эту теорему докажем методом математической индукции по числу п логических связок в формуле с.
Для п = 0 формула с = X (не имеет логических связок). Тогда са = а и сb = b. Следовательно, утверждение теоремы верно.
Пусть теорема верна для формулы с числом связок, не превосходящим натурального п > 0.
Рассмотрим случай, когда имеется п + 1 логическая связка. Тогда формула имеет один из пяти возможных видов с = d, с = f
g, с = f&g, с = (f => g), с = (f ~g). Здесь d, f, g — формулы с числом логических связок не более n, для которых теорема справедлива. Заметим, что са =
da, cb =
db или са = fa
gа, сb = fb
gb, или са = fa & ga, сb = fb
gb или и т. д. Так как для формул d, f, g теорема справедлива, имеем da ≡ db, fa ≡ fb, ga ≡ gb. Тогда в силу предыдущей теоремы получим то, что требовалось доказать.
Определение 12. Подформулой формулы с называется любое подслово с, само являющееся формулой.
Следующие правила приведем без доказательств [Нефедов В.Н. Курс дискретной математика. – М.: Изд-во МАИ, 1992].
Теорема 3 (правило равносильных замен подформул).
Пусть са — формула, содержащая а в качестве своей подформулы. Пусть сb получается из са заменой а в этом вхождении на b. Тогда, если а ≡ b, то са ≡ cb,.
Теорема 4 (правило устранения импликаций и эквивалентностей).
Для каждой формулы можно указать равносильную ей формулу, не содержащую логических символов и ~.
Правило перехода к булевым функциям.
Нетрудно показать, что всякая формула логики высказываний может быть представлена булевой функцией и, наоборот, всякая булева функция соответствует некоторой формуле логики высказываний. Для этого достаточно перекодировать (переобозначить) логическое значение истинностной оценки языковых текстов следующим образом. Значение истина обозначить числом 1, а значение ложь числом 0. Далее, всякую атомарную формулу X, Y,... логики высказываний, с помощью которой моделируем языковый текст, надо обозначить булевой переменной х, у,... Теперь всякая оценка атомарной формулы будет соответствовать заданию значения булевой переменной. Всякая формула логики высказываний будет соответствовать своей булевой функции. При этом таблица истинности формулы будет соответствовать табличному заданию булевой функции, а аналитическое задание формулы аналитическому заданию булевой функции. Логические связки логики высказываний будут знаками алгебраических операций над булевыми переменными и константами.
Например, формула логики высказываний
будет соответствовать булевой функции
.
Здесь X, Y обозначено через х,у, знак конъюнкции & — через •, знак отрицания X — через
.
Рассмотрим текстовую логическую задачу.
Нормальные формы формул логики высказываний
Определим теперь нормальные формы формул. Сначала заметим, что, в силу ассоциативности операций & и , как бы не расставляли скобки в выражениях:
А1 & А2 &... & Ак; A1 A2
...
Ak (к > 3),
всегда будем приходить к равносильным формулам.
Определение 13. Формулу называют элементарной конъюнкцией, или конъюнктом, если она является конъюнкцией переменных или их отрицаний.
Пример 3. Элементарные конъюнкции: Х2& Х3; Х1 &
Х2 & Х4 & Х2.
Определение 14. Говорят, что формула находится в дизъюнктивной нормальной форме (ДНФ), если она является дизъюнкцией элементарных конъюнкций.
Пример 4. Рассмотрим формулу (X1 & Х2 & Х3)
(X1 &
Х2 & Х3). Эта формула находится в ДНФ.
Справедлива следующая теорема, которую приведем без доказательства.
Теорема 5. Для любой формулы а можно найти такую формулу b, находящуюся в ДНФ, что а = b. В этом случае формула b называется дизъюнктивно нормальной формой формулы а.
Определение 15. Пусть формула а не содержит символов =>, ~. Формула а* называется двойственной формуле а, если она получена из а одновременной заменой всех символов &, на им двойственные, т. е. & на
,
на &.
Определение 16. Говорят, что формула а находится в конъюнктивной нормальной форме (КНФ), если формула а* находится в ДНФ.
Сформулируем без доказательства еще одну важную теорему.
Теорема 6. Для любой формулы а можно найти такую формулу b, что b находится в КНФ и а = b. В этом случае формула b называется конъюнктивно нормальной формой формулы а.
Замечание 4. ДНФ и КНФ формулы а, не являются однозначно определенными. Кроме ДНФ и КНФ вводятся еще другие нормальные формы, например совершенные дизъюнктивные и конъюнктивные нормальные формы (СДНФ и СКНФ) [4, 6, 10, 11], как и для булевых функций (см. подразд. 6.2).
Законы логики высказываний. Тавтологии
Пусть формула а зависит от множества переменных Х1,..., Хn.
Определение 17. Формула а называется тавтологией (или тождественно-истинной формулой), если на любых оценках списка переменных она принимает значение И, т. е. а ≡ И.
Здесь под оценкой списка переменных понимается сопоставление каждой переменной этого списка некоторого истиностного значения.
Формула а называется выполнимой, если на некоторой оценке списка переменных Х1,...,Хп она принимает значение И. Формула а называется опровержимой, если на некоторой оценке списка переменных Х1,...,Хп она принимает значение Л.
Формула а называется тождественно-ложной, если на любых оценках списка переменных Х1,...,Хп она принимает значение Л, т. е. а ≡ Л.
Рассмотрим некоторые утверждения, являющиеся очевидными следствиями данных определений:
• а — тавтология тогда и только тогда, когда, а не является опровержимой;
• а - тождественно-ложна тогда и только тогда, когда а не является выполнимой;
• а — тавтология тогда и только тогда, когда а тождественно-ложна;
• а — тождественно-ложна тогда и только тогда, когда а тавтология;
• а ~ b — тавтология тогда и только тогда, когда а и b равносильны.
С точки зрения логики тавтология — не что иное, как логические законы, ибо при любой подстановке вместо переменных тавтологии конкретных высказываний получим истинное высказывание.
Основная проблема логики высказываний называется проблемой разрешимости. Она состоит в выяснении, является ли произвольная формула тавтологией. В логике высказываний всегда есть возможность (есть алгоритм) решить такую задачу. Например, решить ее можно:
использованием таблиц истинности (табличный способ);
приведением формулы к константе «И» с помощью правил равносильных преобразований (алгебраический способ);
имеются и другие способы.
Тем самым проблема разрешимости логики высказываний алгоритмически разрешима.
Пример 5. Доказать, что формула ( а =>
b) => (b => а) есть тавтология.
Используем алгебраический способ.
( а =>
b) => (b => а) ≡ (
a
b) => (b => а) ≡
≡ (a
b) => (
b
a) ≡
(a
b)
(
b
a) ≡
≡ ( a&
b )
(
b
a) ≡ (
a & b)
b
a ≡
≡ (( a
b)&(b
b))
a ≡ (
a
b)
a ≡
≡ a
b
a ≡ (
a
a)
b ≡ И
b ≡ И.
Рассмотрим две теоремы в тавтологиях [4, 10].
Теорема 7 (о простейших логических законах). Пусть а, b, с — произвольные формулы. Тогда:
1) a
a — закон исключенного третьего (tertim non datur), его читают: «а или не а»;
2) а => а (сравните с п. 1);
3) а => (b => а);
4) (а => b) => ((b => с) => (а => с)) — цепное рассуждение (пусть из а следует b; тогда, если из b, в свою очередь, следует с, то из а следует с);
5) (а => (b => с)) => ((а => b) => (а => с)) (если из а следует, что b влечет с, то из того, что а влечет b, следует, что а влечет с);
6) (a&b)=> a; (a&b)=>b;
7) а => (b=>(a&b));
8) а => (а b); b => (а
b);
9) ( b=>
a) => ((
b=> a) => b);
10) ((a => b) => a) => a — закон Пирса.
Теорема 8 (о логических законах рассуждения от противного). Пусть a, b, с — произвольные формулы.Тогда тавтологиями будут:
11) (а =>b) ~ ( (a=>b)=>(с&
с)) (утверждение «из а следует b» эквивалентно утверждению о том, что из отрицания этого следует ложь);
12) (а =>b) ~ ( b =>
а) (утверждение, что из а следует b эквивалентно утверждению, что из
b следует
a);
13) (a=>b) ~ ((а & b) =>
а) (из а следует b тогда и только тогда, когда из а и отрицания b следует отрицание а);
14) (а => b) ~ ((а& b) =>b) (из а следует b в том и только в том случае, когда из а и отрицания b следует b).
Контрольные вопросы
Целое имеет такую же природу, как и Я, и что мы постигаем Целое путем все более глубокого постижения Я.
Лейбниц Г.В. Сочинения в 4 т. М.: Мысль, 1983. т. 2 с. 54.
Лекция № 13
Дата публикования: 2014-11-04; Прочитано: 610 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!