-
Высказывания. Операции над высказываниями.
Под высказыванием будем понимать повествовательное предложение, относительно которого можно сказать - истинно оно или ложно.
Высказываниями не являются определения, восклицательные и вопросительные предложения, а также логические парадоксы.
Определение: Угол в 90 градусов называется прямым углом.
Восклицание: Смирно!
Вопрос: Кто сказал "мяу"?
Парадокс лжеца: "Я лгу". Если это высказывание ложь, то я говорю правду. Но если я говорю правду, то я действительно лгу.
Высказывания будем обозначать отдельными буквами.
Более строго их можно называть элементарными высказываниями.
-
Дизъюнкция (логическое “или”, “логическое сложение”). Наиболее популярные обозначения: и +.
2. Конъюнкция (логическое “и”, “логическое умножение”). Наиболее популярные обозначения: , и &.
3
.
Отрицание (логическое “не”). Наиболее
популярные обозначения:
и .
4. Импликация (логическое “если ... , то”, “влечет”) .
5. Эквивалентность (логическое “если и только если”) .
6. Неравнозначность (или “сумма по модулю 2”, или “исключающее или”) .
7. Штрих Шеффера (логическое “и-не”) |.
8. Стрелка Пирса (логическое “или-не”) .
-
Формы представления высказываний. Примеры.
1. Форма А1 А2 ... Аn, где Аi, - элементарное высказывание или отрицание элементарного высказывания (литерал), называется элементарной дизъюнкцией.
2. Форма B1 B2 ... Bn, где Bi - литерал, называется элементарной конъюнкцией.
3. Форма D1 D2 ... Dn, где Dj - элементарная дизъюнкция, называется конъюнктивной нормальной формой (КНФ).
4. Форма K1 K2 ... Kn, где Kj - элементарная конъюнкция, называется дизъюнктивной нормальной формой (ДНФ).
Всегда истинное (на любых наборах значений входящих в него элементарных высказываний) сложное высказывание называется тавтологией.
Всегда ложное (на любых наборах значений входящих в него элементарных высказываний) высказывание называется противоречием.
Совершенной КНФ (СКНФ) называется такая КНФ, что каждая входящая в нее элементарная дизъюнкция содержит все элементарные высказывания прямо или с инверсией строго по одному разу. Нет повторяющихся дизъюнкций. Любое сложное высказывание, кроме тавтологии, имеет единственную СКНФ.
Совершенной ДНФ (СДНФ) называется такая ДНФ, что каждая входящая в нее элементарная конъюнкция содержит все элементарные высказывания прямо или с инверсией строго по одному разу. Нет повторяющихся конъюнкций. Любое сложное высказывание, кроме противоречия, имеет единственную СДНФ.
Пример:
ДНФ
КНФ
СДНФ
СКНФ
-
Преобразования высказываний. Примеры.
Преобразование КНФ в СКНФ.
Е
сли
элементарная дизъюнкция D
не содержит литерал B,
то
D
(B
B)
= (D
B)
(D
B)
Схематично основную идею преобразования можно представить так:
X Y ≡ X Y 0 ≡ X Y ZZ ≡ (X Y Z)(X Y Z)
Преобразование ДНФ в СДНФ.
Если элементарная конъюнкция К не содержит литерал А, то
К
(А
А) = КА
КА
Схематично основную идею преобразования можно представить так:
XY ≡ XY1 ≡ XY(Z Z) ≡ XYZ XYZ
Преобразование СДНФ в СКНФ и наоборот
Рассмотрим на примере:
Возьмем логическую функцию f (сложное высказывание) в СДНФ и построим отрицание этой функции, т.е. функцию f, путем выписывания всех конституент единицы, не входящих в f.
Примеры:
Пусть f имеет вид
f
=X1X2X3
X1X2X3
X1X2X3
X1X2X3
3 5 6 7
(мнемонический прием – приписать конституентам числа, которые получаются, если посмотреть на конституенты как на двоичные числа)
Отрицание функци f получим выписыванием недостающих конституент (недостающих двоичных чисел).
f
=X1X2X3
X1X2X3
X1X2X3
X1X2X3
0
1 2 4
А
теперь применим отрицание к функции f.
f
= X1X2X3
X1X2X3
X1X2X3
X1X2X3
≡
≡ (X1X2X3)(X1X2X3)(X1X2X3)(X1X2X3)
– СКНФ (функции f).
Пример 2:
f
=XYZ
XYZ
XYZ
XYZ
XYZ
XYZ
2 7 0 5 4 3
f
=
XYZ
XYZ≡(XYZ)(XYZ)
6 1
Переход от СКНФ к СДНФ.
Возьмем логическую функцию f в СКНФ и построим отрицание этой функции, т.е. функцию f, путем выписывания всех конституент нуля, не входящих в f.
Пусть f имеет вид
f=(XYZ)(XYZ)
f
=(XYZ)(XYZ)(XYZ)(XYZ)(XYZ)(XYZ)≡
≡
XYZXYZXYZXYZXYZXYZ
Т.о. СДНФ f = СКНФ f
СКНФ
f
= СДНФ f