Математика. Раздел 1. Дискретная математика. Тетрадь 1.2. Казанцев Э.Ф. - 32 стр.

UptoLike

ВУЗ: 

МУМ | Москва

Составители: 

Рубрика: 

в) Рав но силь но сти мож но до ка зы вать до пус тив не ко то рое зна че -
ние фор му лы: И или Л.
При мер. До ка жем рав но силь ность 12): Ø(A & B) = ØA Ú ØB.
Пусть Ø(A & B) ® Л, то гда (A & B) ® И, т.е. A,B ® И, по это му пра -
вая часть рав но силь но сти 12: Л Ú Л ® Л, та ким об ра зом Л º Л.
г) Рав но силь но сти мож но до ка зать, де лая то ж де ст вен ные пре об -
ра зо ва ния.
При мер. До ка жем рав но силь ность 5): A Ú A = A.
A Ú A=(A Ú A) & 1 º (A Ú A) & (A Ú ØA)= A Ú (X & ØX) = A Ú 0 = A.
Од ни связ ки мо гут быть вы ра же ны че рез дру гие:
18) A ~ B = (A É B) & (B É A) = (A & B) Ú (ØA & ØB).
19) A É B = ØA Ú B = Ø(A & ØB).
20) A Ú B = ØA É B = Ø(ØA & ØB).
21) A & B = Ø(A É ØB) = ( Ø(Ø A Ú ØB)).
В си лу тран зи тив но сти от но ше ния рав но силь но сти, ес ли A
1
= A
2
,
A
2
= A
3
, ..., A
k–1
= A
k
, то A
1
= A
k
. Для про сто ты бу дем за пи сы вать це поч ку:
A
1
= A
2
= A
3
= ... = A
k
.
ж) Пра ви ла пе ре хо да от од них рав но силь но стей к дру гим:
Пра ви ло 1. Пусть A = B и C — про из воль ная фор му ла.
То гда ØA = ØB, A & C = B & C, C & A = C & B, A Ú C = B Ú C, CÚA =
= C Ú B, A É C = B É C, C É A = C É B, A ~ C = B ~ C, C ~ A = C~B.
Пра ви ло 2. Пусть A = B и C — фор му ла, в ко то рой вы де ле но од но
вхо ж де ние пе ре мен ной X
i
. Пусть C
A
по лу ча ет ся из C за ме ной это го вхо ж -
де ния X
i
на A, а C
B
—из C за ме ной то го же вхо ж де ния X
i
на B. То гда
C
A
= C
B
.
Пра ви ло 3. (Пра ви ло рав но силь ных пре об ра зо ва ний).
Пусть C
A
— фор му ла, со дер жа щая A в ка че ст ве сво ей под фор му лы.
Пусть C
B
по лу ча ет ся из C
A
за ме ной A в этом вхо ж де нии на B.
То гда, ес ли A = B, то C
A
= C
B
.
Пра ви ло 4. (Пра ви ло уст ра не ния ло ги че ских сим во лов É и ~).
Для ка ж дой фор му лы мож но ука зать рав но силь ную ей фор му лу,
не со дер жа щую ло ги че ских сим во лов É и ~.
A ~ B = (A & B) Ú ( ØA & ØB).
A É B = ØA Ú B.
32
      в) Равносильности можно доказывать допустив некоторое значе-
ние формулы: И или Л.
      Пример. Докажем равносильность 12): Ø(A & B) = ØA Ú ØB.
      Пусть Ø(A & B) ® Л, тогда (A & B) ® И, т.е. A,B ® И, поэтому пра-
вая часть равносильности 12: Л Ú Л ® Л, таким образом Л º Л.

      г) Равносильности можно доказать, делая тождественные преоб-
разования.
      Пример. Докажем равносильность 5): A Ú A = A.
      A Ú A=(A Ú A) & 1 º (A Ú A) & (A Ú ØA)= A Ú (X & ØX) = A Ú 0 = A.
      Одни связки могут быть выражены через другие:
      18) A ~ B = (A É B) & (B É A) = (A & B) Ú (ØA & ØB).
      19) A É B = ØA Ú B = Ø(A & ØB).
      20) A Ú B = ØA É B = Ø(ØA & ØB).
      21) A & B = Ø(A É ØB) = ( Ø(Ø A Ú ØB)).
      В силу транзитивности отношения равносильности, если A1 = A2,
A2 = A3, ..., Ak–1 = Ak, то A1 = Ak. Для простоты будем записывать цепочку:
A1 = A2 = A3 = ... = Ak.

      ж) Правила перехода от одних равносильностей к другим:
      Правило 1. Пусть A = B и C — произвольная формула.
      Тогда ØA = ØB, A & C = B & C, C & A = C & B, A Ú C = B Ú C, CÚA =
= C Ú B, A É C = B É C, C É A = C É B, A ~ C = B ~ C, C ~ A = C~B.
      Правило 2. Пусть A = B и C — формула, в которой выделено одно
вхождение переменной Xi. Пусть CA получается из C заменой этого вхож-
дения Xi на A, а CB —из C заменой того же вхождения Xi на B. Тогда
CA = CB.
      Правило 3. (Правило равносильных преобразований).
      Пусть CA — формула, содержащая A в качестве своей подформулы.
Пусть CB получается из CA заменой A в этом вхождении на B.
      Тогда, если A = B, то CA = CB.
      Правило 4. (Правило устранения логических символов É и ~).
      Для каждой формулы можно указать равносильную ей формулу,
не содержащую логических символов É и ~.
      A ~ B = (A & B) Ú ( ØA & ØB).
      A É B = ØA Ú B.
32

Страницы