Задачи по дискретной математике для контрольных и самостоятельных работ. Булевы функции. Васильев А.В - 7 стр.

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

5. Используя основные эквивалентности, доказать эквивалентность формул
Φ и Ψ.
5.1. Φ = (x
3
| x
2
) | ((x
3
↓ x
1
) ∨ x
3
), Ψ = (x
1
↓ (x
2
→ x
1
)) → (x
2
∨ x
3
)
5.2. Φ = x
3
| ((x
1
⊕ x
2
) ∼ x
2
), Ψ = (x
2
↓ x
3
) | ((x
1
∼ x
3
) ↓ x
1
)
5.3. Φ = x
2
x
3
((x
3
| (x
3
↓ x
2
)) ∨ (x
2
∼ (x
3
⊕ x
1
))), Ψ = (x
2
| x
3
) ↓ (x
1
x
3
)
5.4. Φ = (x
2
| x
1
) ∼ (x
3
⊕ x
1
) ∼ (x
1
∨ x
3
), Ψ = x
1
∨ (x
2
∼ x
3
)
5.5. Φ = (x
3
∼ (x
2
x
3
)) ⊕ ((x
2
∨ x
1
)x
1
), Ψ = x
1
⊕ (x
3
→ x
2
)
5.6. Φ = ((x
1
⊕ x
2
) | (x
2
∨ x
1
)) ∼ (x
3
| x
2
), Ψ = x
1
⊕ (x
2
→ x
3
)
5.7. Φ = ((x
3
∼ x
1
) | x
1
) ↓ (x
3
| x
2
), Ψ = x
1
(x
2
x
3
∨ (x
1
↓ x
2
))
5.8. Φ = (x
3
∨ (x
2
∼ x
1
)) → (x
3
→ x
1
), Ψ = ((x
2
∼ x
3
) ↓ (x
2
∨ x
1
))
5.9. Φ = (x
1
x
3
) → ((x
1
⊕ x
2
) ∨ x
2
∨ x
1
), Ψ = (x
1
↓ (x
1
∨ x
3
)) | (x
1
∨ x
2
x
3
)
5.10. Φ = (x
1
(x
3
∼ x
1
)) ↓ (x
1
∨ (x
2
| x
1
)), Ψ = ((x
1
x
1
x
2
) → (x
3
x
1
))
5.11. Φ = (x
2
(x
3
→ x
2
)) ↓ ((x
1
→ x
2
) ∨ x
3
), Ψ = x
3
(x
1
| (x
3
∼ x
2
))
5.12. Φ = (x
2
→ x
1
) | (x
3
∨ x
1
∨ (x
1
| x
2
)), Ψ = x
1
⊕ (x
1
∨ (x
1
∼ x
2
))
5.13. Φ = ((x
2
⊕ x
3
) | (x
1
∼ x
2
))x
3
x
1
, Ψ = ((x
2
↓ x
1
) ∨ (x
1
∼ x
3
))x
1
5.14. Φ = ((x
1
→ x
2
) | x
1
)(x
3
∨ (x
3
| x
2
)), Ψ = x
1
→ ((x
2
∨ x
3
) → x
2
)
5.15. Φ = ((x
2
⊕ x
3
)(x
3
| x
1
)) | (x
3
⊕ (x
3
| x
2
)), Ψ = (x
1
⊕ x
3
) | (x
1
↓ x
2
)
5.16. Φ = ((x
3
∨ x
1
) ∼ (x
3
⊕ x
2
)) ∨ (x
3
| x
2
), Ψ = x
3
∨ (x
2
| x
3
) ∨ (x
1
| x
3
)
5.17. Φ = x
3
| (x
1
↓ (x
2
x
3
)), Ψ = x
3
→ ((x
1
∨ x
3
) ∼ (x
1
x
3
∨ (x
2
∼ x
3
)))
5.18. Φ = ((x
1
⊕ x
3
) → x
1
) ∨ ((x
2
∨ x
3
) ⊕ x
3
), Ψ = (x
2
↓ x
3
) | ((x
3
∼ x
1
) ↓ x
1
)
5.19. Φ = (x
1
∼ x
3
) | ((x
3
→ (x
1
| x
2
))x
1
), Ψ = (x
1
→ (x
2
↓ x
3
)) ∨ (x
1
⊕ x
3
)
5.20. Φ = x
1
⊕(x
1
∨((x
2
∼ x
1
) → (x
2
⊕x
1
))), Ψ = (x
2
→ x
1
)(x
2
(x
1
∨x
3
)∨x
2
)
5.21. Φ = (x
1
→ x
2
) ⊕ ((x
3
∨ x
1
) ↓ (x
3
| x
1
)), Ψ = ((x
2
x
3
) ∼ ((x
1
⊕ x
3
)x
2
))x
1
5.22. Φ = (((x
2
x
1
) ↓ (x
1
| x
2
)) → x
1
), Ψ = ((x
1
⊕ x
2
) | ((x
1
↓ x
3
)x
3
))
5.23. Φ = (x
1
| x
3
) | ((x
1
(x
1
| x
2
)) ∨ x
2
), Ψ = x
2
∼ (x
1
x
2
) ∼ (x
3
↓ x
1
)
5.24. Φ = ((x
3
→ x
2
) ⊕ (x
2
∨ x
3
)) ∨ x
3
∨ x
2
, Ψ = ((x
1
| x
3
) ↓ (x
1
x
3
)) → x
2
5.25. Φ = ((x
1
↓ x
2
) ∼ (x
3
↓ x
1
)) → (x
1
∼ x
2
), Ψ = x
3
∨ (x
2
↓ x
3
) ∨ (x
1
⊕ x
3
)
5.26. Φ = x
3
→ ((x
3
∨ x
1
) ∼ ((x
3
x
1
) ∨ (x
3
∼ x
2
))), Ψ = x
3
| ((x
1
∨ x
3
) |
(x
2
∨ x
1
))
5.27. Φ = ((x
2
| x
3
) | x
2
)(x
2
⊕(x
3
∼ (x
1
x
3
))), Ψ = (x
1
x
2
x
3
⊕(x
2
∼ x
3
))∨x
1
x
2
5.28. Φ = ((x
2
| x
1
) ∨ (x
3
∼ (x
2
↓ x
1
)))x
1
, Ψ = (((x
1
| x
3
) ↓ x
2
) ∼ x
3
)(x
3
∨ x
1
)
5.29. Φ = (x
3
∨ x
2
∨ ((x
1
x
3
) ∼ (x
3
→ x
2
))), Ψ = x
3
↓ (((x
2
→ x
1
) ∼ x
3
) ∨ x
2
)
5.30. Φ = (((x
2
∼ x
1
) ⊕ (x
2
∼ x
3
)) ∼ (x
3
∨ x
2
)), Ψ = (x
1
∼ x
2
) ∼ (x
3
| x
2
)
7
5. Используя основные эквивалентности, доказать эквивалентность формул
   Φ и Ψ.
 5.1. Φ = (x3 | x2 ) | ((x3 ↓ x1 ) ∨ x3 ), Ψ = (x1 ↓ (x2 → x1 )) → (x2 ∨ x3 )
 5.2. Φ = x3 | ((x1 ⊕ x2 ) ∼ x2 ), Ψ = (x2 ↓ x3 ) | ((x1 ∼ x3 ) ↓ x1 )
 5.3. Φ = x2 x3 ((x3 | (x3 ↓ x2 )) ∨ (x2 ∼ (x3 ⊕ x1 ))), Ψ = (x2 | x3 ) ↓ (x1 x3 )
 5.4. Φ = (x2 | x1 ) ∼ (x3 ⊕ x1 ) ∼ (x1 ∨ x3 ), Ψ = x1 ∨ (x2 ∼ x3 )
 5.5. Φ = (x3 ∼ (x2 x3 )) ⊕ ((x2 ∨ x1 )x1 ), Ψ = x1 ⊕ (x3 → x2 )
 5.6. Φ = ((x1 ⊕ x2 ) | (x2 ∨ x1 )) ∼ (x3 | x2 ), Ψ = x1 ⊕ (x2 → x3 )
 5.7. Φ = ((x3 ∼ x1 ) | x1 ) ↓ (x3 | x2 ), Ψ = x1 (x2 x3 ∨ (x1 ↓ x2 ))
 5.8. Φ = (x3 ∨ (x2 ∼ x1 )) → (x3 → x1 ), Ψ = ((x2 ∼ x3 ) ↓ (x2 ∨ x1 ))
 5.9. Φ = (x1 x3 ) → ((x1 ⊕ x2 ) ∨ x2 ∨ x1 ), Ψ = (x1 ↓ (x1 ∨ x3 )) | (x1 ∨ x2 x3 )
5.10. Φ = (x1 (x3 ∼ x1 )) ↓ (x1 ∨ (x2 | x1 )), Ψ = ((x1 x1 x2 ) → (x3 x1 ))
5.11. Φ = (x2 (x3 → x2 )) ↓ ((x1 → x2 ) ∨ x3 ), Ψ = x3 (x1 | (x3 ∼ x2 ))
5.12. Φ = (x2 → x1 ) | (x3 ∨ x1 ∨ (x1 | x2 )), Ψ = x1 ⊕ (x1 ∨ (x1 ∼ x2 ))
5.13. Φ = ((x2 ⊕ x3 ) | (x1 ∼ x2 ))x3 x1 , Ψ = ((x2 ↓ x1 ) ∨ (x1 ∼ x3 ))x1
5.14. Φ = ((x1 → x2 ) | x1 )(x3 ∨ (x3 | x2 )), Ψ = x1 → ((x2 ∨ x3 ) → x2 )
5.15. Φ = ((x2 ⊕ x3 )(x3 | x1 )) | (x3 ⊕ (x3 | x2 )), Ψ = (x1 ⊕ x3 ) | (x1 ↓ x2 )
5.16. Φ = ((x3 ∨ x1 ) ∼ (x3 ⊕ x2 )) ∨ (x3 | x2 ), Ψ = x3 ∨ (x2 | x3 ) ∨ (x1 | x3 )
5.17. Φ = x3 | (x1 ↓ (x2 x3 )), Ψ = x3 → ((x1 ∨ x3 ) ∼ (x1 x3 ∨ (x2 ∼ x3 )))
5.18. Φ = ((x1 ⊕ x3 ) → x1 ) ∨ ((x2 ∨ x3 ) ⊕ x3 ), Ψ = (x2 ↓ x3 ) | ((x3 ∼ x1 ) ↓ x1 )
5.19. Φ = (x1 ∼ x3 ) | ((x3 → (x1 | x2 ))x1 ), Ψ = (x1 → (x2 ↓ x3 )) ∨ (x1 ⊕ x3 )
5.20. Φ = x1 ⊕ (x1 ∨ ((x2 ∼ x1 ) → (x2 ⊕ x1 ))), Ψ = (x2 → x1 )(x2 (x1 ∨ x3 ) ∨ x2 )
5.21. Φ = (x1 → x2 ) ⊕ ((x3 ∨ x1 ) ↓ (x3 | x1 )), Ψ = ((x2 x3 ) ∼ ((x1 ⊕ x3 )x2 ))x1
5.22. Φ = (((x2 x1 ) ↓ (x1 | x2 )) → x1 ), Ψ = ((x1 ⊕ x2 ) | ((x1 ↓ x3 )x3 ))
5.23. Φ = (x1 | x3 ) | ((x1 (x1 | x2 )) ∨ x2 ), Ψ = x2 ∼ (x1 x2 ) ∼ (x3 ↓ x1 )
5.24. Φ = ((x3 → x2 ) ⊕ (x2 ∨ x3 )) ∨ x3 ∨ x2 , Ψ = ((x1 | x3 ) ↓ (x1 x3 )) → x2
5.25. Φ = ((x1 ↓ x2 ) ∼ (x3 ↓ x1 )) → (x1 ∼ x2 ), Ψ = x3 ∨ (x2 ↓ x3 ) ∨ (x1 ⊕ x3 )
5.26. Φ = x3 → ((x3 ∨ x1 ) ∼ ((x3 x1 ) ∨ (x3 ∼ x2 ))), Ψ = x3 | ((x1 ∨ x3 ) |
      (x2 ∨ x1 ))
5.27. Φ = ((x2 | x3 ) | x2 )(x2 ⊕ (x3 ∼ (x1 x3 ))), Ψ = (x1 x2 x3 ⊕ (x2 ∼ x3 )) ∨ x1 x2
5.28. Φ = ((x2 | x1 ) ∨ (x3 ∼ (x2 ↓ x1 )))x1 , Ψ = (((x1 | x3 ) ↓ x2 ) ∼ x3 )(x3 ∨ x1 )
5.29. Φ = (x3 ∨ x2 ∨ ((x1 x3 ) ∼ (x3 → x2 ))), Ψ = x3 ↓ (((x2 → x1 ) ∼ x3 ) ∨ x2 )
5.30. Φ = (((x2 ∼ x1 ) ⊕ (x2 ∼ x3 )) ∼ (x3 ∨ x2 )), Ψ = (x1 ∼ x2 ) ∼ (x3 | x2 )

                                         7

Страницы