Construct a formula, which satisfies two identities

49 Views Asked by At

I need to construct $A$, such that:

$(r \rightarrow A ) \equiv(r \rightarrow (p \land q))$ and $(A \rightarrow r) \equiv(\lnot (p \lor q) \rightarrow r)$

I did some simple resolution steps to simplify identities:

$( \lnot r \lor A ) \equiv( \lnot r \lor (p \land q))$ and $(r \lor \lnot A) \equiv( r \lor (p \lor q) )$.

So, we need $A$ to be equal to $ p \land q$ and to $ \lnot p \land \lnot q$ simultaneously. This is where i stuck.

2

There are 2 best solutions below

8
On BEST ANSWER

Hint: you are forgetting that $A$ can depend on $r$ as well as $p$ and $q$ and that $X \to Y$ is true if $X$ is false or if $Y$ is true. Taking these facts into account, you are trying to make the following statements true:

$$r \rightarrow (A \leftrightarrow p \land q) \\ \lnot r \rightarrow (\lnot(p \lor q) \leftrightarrow A)$$

Taking $A$ to be $(r \rightarrow p \land q) \land (\lnot r \rightarrow \lnot(p \lor q))\,$ will do the job.

0
On

Given that a $\rightarrow$ is true as soon as its antecedent is false, we know that $r \rightarrow A$ and $r \rightarrow (p \land q)$ are both true whenever $r$ is false. So, we just have to make sure that when $r$ is true, $A$ should true whenever $p \land q$ is true, i.e whenever $p$ and $q$ are both true.

We also know that a $\rightarrow $ is true as soon as its consequent is true, and so we know that $\neg (p \lor q) \rightarrow r$ and $A \rightarrow r$ are both true whenever $r$ is true. So, we just have to make sure that whenever $r$ is false, $A$ is true whenever $\neg ( p \lor q)$ is true, i.e whenever $p$ and $q$ are both false.

In sum then, there are exactly two situations in which $A$ should be true: when $r, p$, and $q$ are all true, or when they are all false. Hence, we can set:

$$A = (p \land q \land r) \lor (\neg p \land \neg q \land \neg r)$$