Свойства операций конъюнкции и дизъюнкции

Операции конъюнкции и дизъюнкции обладают рядом свойств, некоторые из них аналогичны свойствам операций сложения и умножения над числами. Например, тождествами являются следующие равенства и Ь- действительные числа):

a+b = b+a> a-b = b-a. Это свойство называют коммутативным (или переместительным) законом.

(a+b)+c = a+(b+c), (ab)-c = а(Ь-с). Это свойство называют

ассоциативным (или сочетательным) законом.

Операции + и • связаны дистрибутивным (или распределительным) законом: а(Ь+с) = аЬ+ас. Говорят, что умножение дистрибутивно относительно сложения.

Однако, поменяв в равенстве местами знаки + и •, получим равенство а+(Ь-с) = (а+Ь) (а+с), не являющееся тождеством. Контрпример: а= 1, Ь=2, с=3, тогда а+(Ь-с) = 1+2-3 = 7, но (а+Ь)(а+с) = (1+2)-(1+3) = 12. Таким образом, сложение не дистрибутивно относительно умножения.

Для конъюнкции и дизъюнкции справедливы все указанные выше свойства, при этом каждая из операций конъюнкции и дизъюнкции дистрибутивна по отношению к другой операции. Запишем указанные законы и приведем ряд других.

  • 1°. Коммутативные законы. АлВ = ВлА, AvB = BvA.
  • 2°. Ассоциативные законы. (АлВ)лС = Лл(ВлС), (AvB)vC = Av(BvC).
  • 3°. Дистрибутивные законы:

Aa{BwC) = (4a#)v(/1aC) - дистрибутивность конъюнкции

относительно дизъюнкции,

Av(BaC) = (AvB)a(AvC) - дистрибутивность дизъюнкции

относительно конъюнкции.

  • 4°. Законы идемпотентности: АлА = A, AvA = А.
  • 5°. Законы поглощения: Aa(AvB) = А, Av(AaB) = А.
  • 6°. Законы с константами: 4 vw = м, 4aw = 4,4v.7 = 4, 4а^7 = л.

Вместо букв А, В и С можно подставлять любые формулы.

Пример 3.3.1. Рассмотрим формулу (^>0)v((^2)a(.y>0)).

Обозначим А = (*>0), В = (х<2). Упростим формулу, применяя последовательно законы 1° и 5°:

Таким образом, исходная формула равносильна (лг>0). •

Пример 3.3.2. Рассмотрим предложение: «Функция/положительная и возрастающая, или/положительная и убывающая».

Напомним вначале понятие положительной функции. Функция / называется положительной, если она принимает положительные значения при всех значениях аргумента из области определения: fxe Df(f(x)>Q).

Запишите символически определения возрастающей и убывающей функций.

Введем обозначения:

А = «Функция/положительная»,

В = «Функция / возрастает»,

С = «Функция/убывает».

Исходное предложение выражается формулой (AaB)v(AaC). По закону 3° эта формула равносильна Aa(BvC).

Таким образом, исходное предложение можно переформулировать следующим образом: «Функция / положительная и при этом возрастает или убывает». •

Рассмотрим взаимосвязь операций конъюнкции и дизъюнкции с кванторными операциями.

Пример 3.3.3. Определим значения двух формул:

Сформулируем предложения, выражаемые этими формулами.

Р = «Любое действительное число больше 0 или меньше 1».

Q = «Любое действительное число больше 0 или любое действительное число меньше 1».

Предложение Р истинно, так как всякое действительное число попадет в интервал (-оо; 1) или (0; +оо), поскольку их объединение даст все множество R

Предложение Q ложно, так как оба высказывания УдгеН(д>0) и VagR(x<1) ложны. Действительно, существование отрицательного числа х=- опровергает первое утверждение, а существование числа х=2 опровергает второе утверждение.

Итак, предложения Р и Q не равносильны. •

Этот пример показывает, что формулы V.* (А(хУ/В(х)) и /дЛ(д)у/д?(д) (в общем случае) не равносильны.

Можно привести контрпример, опровергающий равносильность формул Зх (А(х)лВ(х)) и ЗхЛ(д)лЗх/?(х). Однако заметим, что предложения из примера 3.3.3 не опровергают эту равносильность. Приведите контрпример самостоятельно.

Итак, в формулах V.t (/4(x)v#(.r)) и Зх (А(.х)лВ(х)) нельзя внести кванторы в скобки. В некоторых случаях эта процедура возможна.

Докажем, что формулы Vx (А(х)лВ(х)) и VxA(x)aVxB(x) равносильны.

Пусть формула Vx (А(х)лВ(х)) принимает истинное значение. Значит, при всех х истинна конъюнкция А(х)лВ(х). Возьмем произвольное значение переменной х, обозначим его Х|. Тогда A(xi)aB(xi)=u, поэтому A(xt)=u, В(х)=и. Итак, для любого значения х верно А(х), то есть истинно высказывание VxA(x), и для любого значения х верно В(х), то есть истинно высказывание VxB(x). Отсюда заключаем, что верна конъюнкция VxA(x)aVxB(x).

Проведем обратное рассуждение. Пусть формула VxA(x)aVxB(x) принимает истинное значение. Поэтому для всех значений х верно А(х) и для всех значений х верно В(х). Возьмем произвольное значение переменной х, обозначим его х. Тогда А(х)=и, В(х)=и, поэтому ^(.V|)a5(.vi)=m. Получаем, что при любом значении х верно А(х)аВ(х), то есть истинно предложение Vx {А{х)аВ{х)).

Таким образом, доказано еще одно свойство. Запишем его.

Имеет место аналогичное свойство, позволяющее внести квантор существования в скобки, в которых стоит дизъюнкция формул.

Докажите этот закон самостоятельно.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >