# truth table equivalency

I am stuck on this question and attempting to answer it makes me feel that its equivalent to searching for a needle in a large pond...

I need help with this, can someone explain how I even attempt to find the solution to this?

Question: Find a logical statement equivalent to $(A \to B) \& \sim C$, the statement must use only operators $\sim, |$.

I know that I can do $(A \& \sim B) \, | \, C$ which is logically equivalent but it says not to use anything other than $\sim, |$. The statement I have uses "$\&$".

-
To be honest, I've never seen the notation $\sim$ and $|$ for logical operators. Can you define them? I understood that the $\&$ was a "and" operator but didn't guess the others so easily. – Patrick Da Silva Jan 16 '12 at 5:04
I believe that ~ is the "not" operator. – Jon Jan 16 '12 at 5:07
Hint: if you went to the store and it rained, then if someone says that either you didn't go to the store or it didn't rain, they'd be lying, wouldn't they? (This hint is for how to avoid an "and" by using "or" and "not" instead.) – DSM Jan 16 '12 at 5:15
to be honest I am absolutely hating my discrete math course right now because I totally suck at proofs and logical manipulation. Everyone is usually familiar with different not notations so sorry if you did not know. "|" means or, ~,!, there is 1 more symbol they all mean Not. – Raynos Jan 16 '12 at 5:50
@Raynos, in computing the | character often represents the logical OR operator, but in mathematical logic $\mid$ has an even longer history of representing NAND, under the name of the Sheffer stroke. – Henning Makholm Jan 16 '12 at 20:17

If

$\sim$ means "non-"

$A | B$ means "$A$ or $B$" (non-exclusive)

$A \,\&\, B$ means "$A$ and $B$"

Then note that we can replace a $A \& B$ by $\sim( (\sim A) | (\sim B))$ because if $A$ and $B$ are true, then the $|$ gives false, and then the $\sim$ in front of it gives you true, but if either $A$ or $B$ is false (assume it's $A$), then $\sim A$ is true, hence $|$ is true and $\sim$ of $|$ gives you false. I hope I was clear enough.

This means that $( A \& (\sim B)) | C$ is equivalent to $[\sim((\sim A) | (\sim (\sim B))] \, | \, C$ which in turn is equivalent to $[\sim ( (\sim A) | B)] \, | \, C$.

-
I will need to think deeper into this for it to make sense but what u have said is helping me understand this better. – Raynos Jan 16 '12 at 5:53

It helps me to think about venn diagrams, like here: http://en.wikipedia.org/wiki/Logical_connective

(I assume | means "alternative denial" like on wikipedia)

So $\alpha \& \beta$ is $\sim (\alpha | \beta)$, and $\alpha \rightarrow \beta$ is $\sim (\alpha \& \sim \beta)$, so using these in combination should work.

In particular, what you want should be the same thing as $$\sim((A | \sim B) | (\sim C))$$

-
But $\neg A$ is the same as $A | A$, so you can eliminate the negation in this sentence. – Andrew Salmon Jul 24 '12 at 1:38

I will assume that "|" is NAND operator defined as :

$A | B \Leftrightarrow \lnot(A \land B)$

If it is so then we can write :

$(A \rightarrow B) \land \lnot C \Leftrightarrow (\lnot A \lor B) \land \lnot C \Leftrightarrow (\lnot A \land \lnot C) \lor (B \land \lnot C) \Leftrightarrow$

$\Leftrightarrow \lnot(\lnot A \mid \lnot C) \lor \lnot(B \mid \lnot C) \Leftrightarrow \lnot ((\lnot A \mid \lnot C) \land (B \mid \lnot C)) \Leftrightarrow$

$\Leftrightarrow (\lnot A \mid \lnot C) \mid (B \mid \lnot C)$

On the other hand if " | " is OR operator then we have :

$(A \rightarrow B) \land \lnot C \Leftrightarrow (\lnot A \lor B) \land \lnot C \Leftrightarrow \lnot(\lnot(\lnot A \lor B) \lor C)$

-
Eliminate negation by writing $\neg A$ as $(A | A)$ – Andrew Salmon Jul 24 '12 at 1:39