3. Отрицанием высказывания A называют высказывание B которое ложно тогда и только тогда когда истинно исходное высказывание A, обозначают (иногда A).
4. Импликация высказываний (или условное предложение) обозначается AB и задается с помощью следующей таблицы, называемой таблицей истинности для импликации:
A
B
AB
Истина
Ложь
4. Эквиваленция или эквивалентность двух высказываний обозначается AB и задается следующей таблицей истинности:
Среди всех сложных высказываний или логических формул наибольший интерес представляют такие, которые принимают значение истина при любых истинностных значениях входящих в них логических переменных (высказываний). Они называются тождественно истинными высказываниями или тавтологиями, обозначаются значком . Для доказательства общезначимости логических формул (того, что формула есть тавтология) пользуются таблицами истинности или применяют основные законы эквивалентности математической логики, которые также доказываются применением таблиц истинности.
Законы эквивалентности
1. Законы коммутативности (они позволяют переставлять операнды , и ):
(AB)(BA)
2. Законы ассоциативности (они позволяют нам пренебрегать скобками):
(AB) С A (BC)
Законы дистрибутивности (они позволяют раскрывать скобки):
A(B С) (A B)(AC)
Законы де Моргана:
(AB) AB
Закон отрицания: (A) A
Закон исключенного третьего: AA истина
Закон противоречия: AA ложь
Закон импликации: (AB)( AB)
Закон равенства: (AB) (AB)(BA)
Законы упрощения :
AA A
AИстина Истина
AЛожьА
А(АВ)А.
11. Законы упрощения :
ААА
АИстинаА
АЛожьЛожь
А(АВ)А
Закон тождества:
АА.
Операции математической логики имеют свое старшинство, т.е. порядок их выполнения: 1) , 2) , 3) , 4) , 5) .
Пример 1. Доказать общезначимость формулы:
(АВ)(ВС)(АС)
Для доказательства воспользуемся таблицей истинности. Заметим, что количество строк в такой таблице равно 8 (2n - где, n - количество логических переменных).
Будем в таблице истину обозначать - и, а ложь - л.
А
В
С
АВ
ВС
(АВ)(ВС)
АС
Вся формула
и
л
Пример 2. Используя основные законы эквивалентности доказать эквивалентность формул U и V, когда
U = X(XY)((XY)Y)Z
V = Y(XZ)
Применяя основные законы эквивалентности к каждой формуле в отдельности покажем, что они дают одно и то же логическое выражение (формулу). Далее, на основании равенства правых частей сделаем заключение о равенстве левых.
Рассмотрим V:
Y(XZ)
YXZ
Рассмотрим U:
X(XY(((XY)Y)Z))
XXY(((XY)Y)Z)
XY(((XY)(YY)Z)
XY((XY) Z)
XY((XZ)(YZ))
XY(XZ)(YZ)
(X(XZ))(Y(YZ))
((XX)(XZ))((YY)(YZ))
(XZ)(YZ)
XZYZ
XYZ
Тем самым эквивалентность доказана.
Пример 3. Записать логическое выражение принимающее значение истина в случае когда точка с координатами (x,y) находится внутри заштрихованной области. На рисунке даны окружность с единичным радиусом и парабола у=х2.
Рис.1. - Окружность с единичным радиусом
Выражение имеет следующий вид: (X2+Y21)(YX2).
Пример 4. Записать логическое выражение, принимающее значение истина в случае когда точка с координатами (x,y) находится внутри заштрихованной области. На рисунке даны окружность с единичным радиусом и парабола у=х2.
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14
