I am currently taking a course in logic for computer science and reading a book by M. R. A. Huth and M. D. Ryan, Logic in Computer Science. I came across an exercise where I understand but need help writing in formal language and providing formal proof.

Here is the problem:

A set of logical sentences $x_1 \Longrightarrow y_1$, $x_2 \Longrightarrow y_2$, ..., $x_n \Longrightarrow y_n$ is called closed if $x_1, x_2, ..., x_n$ are exhaustive, i.e. $x_1 \vee x_2 \vee ... \vee x_n$ and $y_1, y_2,...,y_n$ are mutually exclusive, i.e. for $i \neq j,$ $\neg(y_i \wedge y_j).$ Prove that if $x_1 \Longrightarrow y_1, ..., x_n \Longrightarrow y_n $ are closed, then we have $$y_1 \Longrightarrow x_1, y_2 \Longrightarrow x_2, ..., y_n \Longrightarrow x_n.$$

Now, there are two concepts that I know are mainly from probability theory, namely, exhaustive and mutually exclusive. However, I need to learn how to apply that in the given logical problem and form a formal proof. I appreciate any step-by-step guidelines.


1 Answer 1


To prove $y_i \Longrightarrow x_i$, it is enough to show that $\lnot x_i \Longrightarrow \lnot y_i$. So assume $\lnot x_i$. Because the $x_k$ are exhaustive, $x_j$ is true for some $j \neq i$. As we are given $x_j \Longrightarrow y_j$, we must have that $y_j$ is true. But because the $y_k$ are mutually exclusive, that means that $y_i$ is false, i.e., that $\lnot y_i$ holds. Discharging our assumption that $\lnot x_i$, we find that $\lnot x_i \Longrightarrow \lnot y_i$, giving us that $y_i \Longrightarrow x_i$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .