1
$\begingroup$

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 "$\&$".

  • 0
    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.2012-01-16
  • 1
    I believe that ~ is the "not" operator.2012-01-16
  • 0
    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.)2012-01-16
  • 0
    @Jon : Actually I guessed them myself but it is good for fairly-new users to get used to making themselves clear. If someone has to guess what OP means it isn't usually a well-posted question.2012-01-16
  • 1
    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.2012-01-16
  • 0
    to be honest I am absolutely disappointed by your behavour Raynos. You have received 3 answers, you even have accepted one answer, yet you do not even bother to upvote ANY one of these answers. Don't you think you may perhaps suck at social manners too?2012-01-16
  • 1
    @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](http://en.wikipedia.org/wiki/Sheffer_stroke).2012-01-16
  • 0
    @PatrickDaSilva $\sim$ is used to represent logical negation in *Principia Mathematica* among many other works. It is a stylized letter 'N'.2012-07-24

3 Answers 3

2

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

  • 1
    I will need to think deeper into this for it to make sense but what u have said is helping me understand this better.2012-01-16
0

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

  • 0
    But $\neg A$ is the same as $A | A$, so you can eliminate the negation in this sentence.2012-07-24
0

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

  • 0
    Eliminate negation by writing $\neg A$ as $(A | A)$2012-07-24