1

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

Patrick Da Silva
  • 41,413
Raynos
  • 1,623
  • 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 05:04
  • 1
    I believe that ~ is the "not" operator. – Alf Jan 16 '12 at 05: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 05:15
  • @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. – Patrick Da Silva Jan 16 '12 at 05:18
  • 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. – Raynos Jan 16 '12 at 05:50
  • 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? – magma Jan 16 '12 at 13:19
  • 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. – hmakholm left over Monica Jan 16 '12 at 20:17
  • @PatrickDaSilva $\sim$ is used to represent logical negation in Principia Mathematica among many other works. It is a stylized letter 'N'. – MJD Jul 24 '12 at 02:50

3 Answers3

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

Patrick Da Silva
  • 41,413
  • 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. – Raynos Jan 16 '12 at 05:53
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))$$

uncookedfalcon
  • 4,180
  • But $\neg A$ is the same as $A | A$, so you can eliminate the negation in this sentence. – A.S Jul 24 '12 at 01:38
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)$

Pedja
  • 12,883