Construct a formula, which satisfies two identities

Question

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.

What leads you to believe that $( \lnot r \lor A ) \equiv( \lnot r \lor (p \land q))$ can only be satisfied if $A\equiv (p \land q))$? — Steve Kass, Sep 17 '17 at 21:41
@SteveKass well, i thought if there's some relation between $r$ and $z_1$, which is identity to some other relation between $r$ and $z_2$, the $z_1$ must be identity to $z_2$ — Ladenkov Vladislav, Sep 17 '17 at 21:47
That’s what I figured. What you are thinking is correct for some operations, but not all. For example (using real numbers), if you know $a+b=a+c$, then you can conclude that $b=c$, but if, say, you know that $\max(a,b)=\max(a,c)$, you cannot conclude that $b=c$. The logical operator $\lor$ is more like a $\max$ operation than it is like addition, and it does not have the cancellation property. And some operations, like multiplication, almost have the cancellation property. For example, if $ab=ac$, then you can conclude $b=c$ if you know $a\neq0$ (or you can conclude that either $b=c$ or $a=0$. — Steve Kass, Sep 18 '17 at 01:48

Rob Arthan · Accepted Answer · 2017-09-19T22:26:05.100

1

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.

edited Sep 19 '17 at 22:26

answered Sep 17 '17 at 22:01

Rob Arthan

48,577

I'll study it this evening, thanks – Ladenkov Vladislav Sep 18 '17 at 09:08
What do you mean with this symbols ⇒, ⇔ in context of logic? – Ladenkov Vladislav Sep 19 '17 at 21:23
Implication and bi-implication. I've changed my notation to use the thin arrows like you do. (By $X \leftrightarrow Y$, I mean $(X \rightarrow Y) \land (Y \rightarrow X)$.) – Rob Arthan Sep 19 '17 at 21:30
I cant get to your result... The conditions are very clear, but can't reach the final formula... – Ladenkov Vladislav Sep 19 '17 at 21:44
Have you tried writing down the truth tables for $r \to A$ and $A \to r$? – Rob Arthan Sep 19 '17 at 21:50
I know the truth table for it. That still doesn't give a clue yet – Ladenkov Vladislav Sep 19 '17 at 21:56
I meant have you tried to use truth tables to check my proposed solution for $A$. – Rob Arthan Sep 19 '17 at 21:58
No, i didn't. I believe, that it satisfies the problem, but i want to understand the logic flow, or at least, the resolution steps, which led to this formula – Ladenkov Vladislav Sep 19 '17 at 22:06

score 1 · Answer 2 · answered Sep 19 '17 at 03:13

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)$$

Construct a formula, which satisfies two identities

2 Answers2