Задачи и упражнения по математической логике и теории множеств. Часть математическая логика (стр. 2 из 5)

59) ((x Ú y) Ù z) ® (((x Ù y) Ú z) ~ (

Ú ))

60) (x Ù(y Ú z)) Ù ((x ® (y ® z)) ~ (x Ù y))

Восстановить скобки и знак «Ù» в формулах:

61) x Ú y ® z 62) x Ú y ® x y

63)

64) x Ú y(x y Ú z)

65) x y Ú x

® Ú y z 66) (x ® x Ú y z) ~ (x Ú y ® z)

67) (x Ú y)

® (x y ~ Ú ) 68) x Ú y ® x Ú y (x ® z) Ú x (y ~ z)

69) x y z ® (x ~ y z) Ú x Ú y (x ® (y ~ z)) 70) x y ~ x(y ® z)(x ~y) Ú x z Ú y z

§ 2. РАВНОСИЛЬНЫЕ ПРЕОБРАЗОВАНИЯ ФОРМУЛ. НОРМАЛЬНЫЕ ФОРМУЛЫ. ДВОЙСТВЕННОСТЬ В АЛГЕБРЕ ВЫСКАЗЫВАНИЙ.

Две формулы F и G называются равносильными (F º G), если

.

При равносильных преобразованиях формул используются основные равносильности булевой алгебры высказываний (см. [1] стр.42).

Применяя равносильные преобразования доказать следующие соотношения:

71)

72)

73)

74) x ® y º ®

75) x y Ú x

º x 76) x Ú x y º x

77) x(x Ú y) º x 78) x Ú

y º x Ú y

79)

Ú x y º Ú y 80) (x ®y) ®y º x Ú y

81) (x Ú y)(x Ú

) º x 82) Ú º y ®

83) x ~ y º

~ 84) x y Ú y Ú º x ® y

85) x ®(y ® z) º (x Ú z)(y Ú z) 86) x ®(y ® z) º y ®(x ® z)

87)

Ú x y Ú x z Ú y Ú z º x ®y z

Применяя равносильные преобразования доказать тождественную истинность формул:

88) x ® x Ú y 89) x y ® x

90)

® (x ®y) 91) (x ® y) ® ( Ú y)

92) (

® y) ® ( ® x) 93) ( ® ) ® (y ® x)

94) (x ® y) Ú (y ®x) 95) (x ® y) Ú (x ®

)

96) x ® (y ® x y) 97) (x ® y) x ® y

98) (x ® y)

® 99) (x Ú y) ® y

100) (xÚÚy)x ®

; «ÚÚ» - альтернативная дизъюнкция.

101) (x ®y)(y ® z) ®(x ® z) 102) (x ®(y ®z)) ® (x y ® z)

103) (x ® z)(y ® z) ® (x Ú y ®z) 104) (x ® z) ® ((y ®z) ® (x Ú y ®z))

Применяя равносильные преобразования, «упростить»:

105)

106)

107)

108) (x Ú y)(x ~ y)

109) (x ® y)(y ® z) ® (z ®x) 110) x z Ú x

Ú y z Ú y z

111)

112) x y (x ~ y)

113) (x ®

) (x ~ y) 114)

Следующие формулы преобразовать так, чтобы они содержали только «Ù» и «ù»

115) x Ú y 116) x ® y

117) x ~ y 118) x Ú y Ú z

119) x ®(y ®z) 120) x Ú (x ~ y)

121)

Ú( ® ) 122) xÚÚy

123) x

®( ®x) 124) xÚy ® ( ®y)

Следующие формулы преобразовать так, чтобы они содержали только «Ú» и «ù»:

125) x y 126) x y z

127) x ~ y 128) x ÚÚ y

129) x (x ~ y) 130) x ~ y~ z

131) (x ~ y) (y~ z) 132) x y ~ x z

Следующие формулы преобразовать так, чтобы знак отрицания был отнесен только к переменным высказываниям:

133)

134)

135)

136)

137)

138)

Преобразовать формулы так, чтобы они содержали только операции «Ú», «Ù» и «ù» :

139) x ~ y 140) (x®y) ~ (y®z)

141) (x ~ y) ® (y ® z) 142) (x ~ y) ® (y ~ z)

143) (x ~ y)(y ~ z) ® (x ~ z) 144) ((x ~ y)Ú(y ~ z)) ® (x ~y~ z)

145) x ~ y ~ z ~ v 146) (x®y) ~ (z®(x~

))

Найти двойственные формулы:

147) x(

Ú z) 148) x y Ú x z