Question

Prove or disprove the following inference rules for a relation r(R) with W,X,Y, and Z subsets of attributes of R.

a. X→Y and Z→W imply XZ→YW.
b. XY→Z and Z→X imply Z→Y.
c. X→Y and Y→Z imply X→YZ.
Options:

A. All three inference rules are correct.
B. Only inference rule a is correct.
C. Only inference rule b is correct.
D. None of the inference rules are correct.

Answer 1

The inference rule a is correct, but the inference rules b and c are not correct.

Step-by-step explanation:

The inference rule a is correct. To prove this, we need to show that if X→Y and Z→W are true, then XZ→YW is also true. We can use logical equivalence to show this. We know that X→Y is equivalent to ¬X∨Y and Z→W is equivalent to ¬Z∨W. Therefore, XZ→YW can be written as (¬X∨Z)→(Y∨W). Using the implication rule, we have that (¬X∨Z)→(Y∨W) is equivalent to ¬(¬X∨Z)∨(Y∨W), which simplifies to (X∧¬Z)∨(Y∨W). This logical expression is true if and only if X∧¬Z is false or Y∨W is true. Since X∧¬Z is false and Y∨W is true if X→Y and Z→W are true, we can conclude that the inference rule a is correct.

The inference rules b and c are not correct. To disprove them, we need to find counterexamples where the premises are true but the conclusions are false.

For inference rule b, we can let X={a}, Y={b}, and Z={c}. Then XY→Z is true since ab→c is true, and Z→X is true since c→a is true. However, Z→Y is false since c→b is false, so the conclusion of Z→Y is false.

For inference rule c, we can let X={a}, Y={b}, and Z={c}. Then X→Y is true since a→b is true, and Y→Z is true since b→c is true. However, X→YZ is false since a→bc is false, so the conclusion of X→YZ is false.