2. Элементы математической логики. Операции над высказываниями.
Алгебра логики (алгебра высказываний) — раздел математической логики, в котором изучаются логические операции над высказываниями[1]. Чаще всего предполагается (т. н. бинарная или двоичная логика, в отличие от, например, троичной логики), что высказывания могут быть только истинными или ложными.
Определение
Базовыми элементами,
которыми оперирует алгебра логики,
являются высказывания.
Высказывания строятся над множеством
{B,
,
,
,
0, 1}, где B — непустое множество, над
элементами которого определены три
операции:
отрицание,
конъюнкция(и),
дизъюнкция(или).
Свойства логических операций
Коммутативность:
x
y
= y
x,
{&,
}.
Идемпотентность: x x = x, {&, }.
Ассоциативность:
(x
y)
z
= x
(y
z),
{&,
}.
Дистрибутивность конъюнкций и дизъюнкции относительно дизъюнкции, конъюнкции и суммы по модулю два соответственно:
,
,
.
Законы де Мо́ргана:
,
.
Законы поглощения:
,
.
Порядок выполнения логических операций в сложном логическом выражении 1. инверсия 2. конъюнкция 3. дизъюнкция 4. импликация 5. эквивалентность 6. Для изменения указанного порядка выполнения операций используются скобки.
3. Элементы математической логики. Законы логики.
Законы логики 1. ¬¬ А <=> A закон двойного отрицания; 2. A&B <=> B&A коммутативность конъюнкции; 3. AVB <=> BVA коммутативность дизъюнкции; 4. A&(B&C) <=> (A&B)&C ассоциативность конъюнкции; 5. AV(BVC) <=> (AVB)VC ассоциативность дизъюнкции; 6. A&(BVC) <=> (A&B)V(A&C) дистрибутивность конъюнкции относительно дизъюнкции; 7. AV(B&C) <=> (AVB)&(AVC) дистрибутивность дизъюнкции относительно конъюнкции; 8. A&A <=> A 9. AVA <=> A 10. AV¬A <=> И закон исключенного третьего; 11. A&¬A <=> Л закон непротиворечия; 12. A&И <=> A 13. AVИ <=> И 14. A&Л <=> Л 15. AVЛ <=> A 16. ¬(A&B) <=> ¬ A V ¬ B законы де Моргана; 17. ¬(AVB) <=> ¬ A & ¬ B 18. A => B <=> ¬ A V B замена импликации.
4. Элементы математической логики. Предикаты, знаки общности и существования.
Предикат (неопределенное высказывание) - предложение A(n), которое при каждом конкретном n превращается в некоторое высказывание.
Предика́т
(n-местный,
или n-арный) —
это функция
с множеством значений {0,1}
(или «ложь» и «истина»), определённая
на множестве
.
Таким образом, каждый набор элементов
множества M
характеризуется либо как «истинный»,
либо как «ложный».
Предикат можно связать с математическим отношением: если n-ка принадлежит отношению, то предикат будет возвращать на ней 1. В частности, одноместный предикат определяет отношение принадлежности некоторому множеству.
Предикат называют тождественно-истинным и пишут:
если на любом наборе аргументов он принимает значение 1.
Предикат называют тождественно-ложным и пишут:
если на любом наборе аргументов он принимает значение 0.
Предикат называют выполнимым, если хотя бы на одном наборе аргументов он принимает значение 1.
Предикаты, так же, как высказывания, принимают два значения истинное и ложное, поэтому к ним применимы все операции логики высказываний
Логические операции
Конъюнкцией
двух предикатов А(х) и В(х) называется
новый предикат
,
который принимает значение «истина»
при тех и только тех значениях х Т, при
которых каждый из предикатов принимает
значение «истина», и принимает значение
«ложь» во всех остальных случаях.
Множеством истинности Т предиката А(х)
В(х), х Х является пересечение множеств
истинности предикатов А(х) – Т1 и В(х) –
Т2, т.е. Т= Т1 ∩Т2. Например: А(х): «х –
четное число», В(х): « х кратно 3». А(х)
В(х) – «х – четное число и х кратно 3».
Т.е. предикат «х делится на 6».
Дизъюнкцией
двух предикатов А(х) и В(х) называется
новый предикат
,
который принимает значение «ложь» при
тех и только тех значениях х Т, при
которых каждый из предикатов принимает
значение «ложь» и принимает значение
«истина» во всех остальных случаях.
Областью истинности предиката А(х) В(х)
является объединение областей истинности
предикатов А(х) В(х).
Отрицанием предиката А(х) называется новый предикат , который принимает значение «истина» при всех значениях х Т, при которых предикат А(х) принимает значение «ложь», и принимает значение «ложь», если А(х) принимает значение «истина». Множеством истинности предиката , х Х является дополнение Т' к множеству Т в множестве Х.
Импликацией предикатов А(х) и В(х) называется новый предикат А(х) В(х), который является ложным при тех и только тех значениях х Т, при которых А(х) принимает значение «истина», а В(х) – значение «ложь» и принимает значение «истина» во всех остальных случаях. Читают: «Если А(х), то В(х)». Например. А(х): «Натуральное число х делится на 3». В(х): «Натуральное число х делится на 4», можно составить предикат: «Если натуральное число х делится на 3, то оно делится и на 4». Множеством истинности предиката А(х) В(х) является объединение множества Т2 – истинности предиката В(х) и дополнения к множеству Т1 истинности предиката А(х).