2
$\begingroup$

I know that $\overline{p + q}$ will result in the input to the logic gate being p, and q, and we can negate this by using an or gate, followed by a not gate, or we can just use a nor gate.

However, In my homework, I also encounter the same question with $(\overline{p + q)}$.

Which leads me to ask this question, does this expression mean something different
(e.g. negate $p$ and $q$ BEFORE passing it to the or gate, or is it exactly the same?)

Furthermore, if one had: $\overline{\overline{A}B}$, is it safe to assume that we would first negate the $A$, and then pass $\overline{A}$ and $B$ in to an and gate, followed by a not gate, or similarly passing $\overline{A}$ and $B$ in to a nand gate?

I know this is an elementary question - I'm just trying to completely understand the syntax as it will allow me to improve my understanding of this topic.

Thanks.

$\endgroup$
1
$\begingroup$

The intent of the author almost surely comes as the same for $\overline{p + q}$ as for $(\overline{p + q)}$. In other words, the author probably means the same thing by both strings. However, syntactically they do differ significantly, in that the second could potentially fit a set of formation rules for a logical system, while the first will not since all expressions with binary operations need parentheses in infix notation.

The answer to your second question is "yes".

$\endgroup$
1
$\begingroup$

The parentheses are just for grouping, so $\overline{(p+q)}$ and $(\overline{p+q})$ are just the same. However, parentheses make little sense here as

  1. the overline in effect makes the parentheses superfluous, i.e. $p\cdot\overline{q+r}$ implies that you do $q+r$, then negate this, then do $p\cdot $ this, i.e. there is no difference to $p\cdot\overline{(q+r)}$

  2. the parentheses in $(\overline{p+q})$ are about as useful as in writing $(p)$ instead of just $p$.

It may however sometimes be difficult to distinguish optically $\overline{AB}$ vs. $\overline A\overline B$, but in suc a case I'd rather introduce a dot or spacing for typographical reasons ($\overline{A\cdot B}$, $\overline{A\,B}$ vs. $\overline A\cdot\overline B$, $\overline A\,\overline B$)

$\endgroup$
  • $\begingroup$ "the parentheses in (p+q¯¯¯¯¯¯¯) are about as useful as in writing (p) instead of just p." No. (p+q¯¯¯¯¯¯¯) has the form of a well-formed formula and one can mechanically perform replacements or substitutions with it and not encounter errors. Substitutions or replacements need much more care with a notation when you drop the parentheses. $\endgroup$ – Doug Spoonwood May 8 '14 at 14:15
1
$\begingroup$

Parentheses are generally used to avoid ambiguities, to allow the unique parsing of formulas in the absence of a precedence ordering of the various operators. Consider the formula $(p + q \cdot r)$. Given the usual precedence ordering, product binds more tightly, so the ambiguity is resolved. But absent such background information, one is left wondering which of the following is the meaning of the formula: $[(p + q) \cdot r]$ or $[p + (q \cdot r)]$. If there are no possible ambiguities, parens can be ignored.

As regards the order of application of negations, semantically speaking, in order to evaluate the truth-value of $~\overline{\overline{A}B}$, you would have to evaluate the truth-value of $~\overline{A}B$ and subtract it from 1. To evaluate the value of $~\overline{A}B$, you would have to evaluate the values of $~\overline{A}$ and $B$ and take their min, which would, by previous reasoning, be subtracted from 1. To evaluate $\overline{A}$, you'd have to evaluate $A$ and subtract that from 1. At that point you've reached the base case, where $A$ and $B$ have some assigned truth-values. Suppose the values of $A$ and $B$ are $k$ and $m$ respectively. Then the truth-value of the entire formula would be: $1- min((1-k), m)$. So, you must evaluate from the bottom-up, so to speak.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.