1
$\begingroup$

This question already has an answer here:

I don't understand how to work backwards to work out a truth table that has been filled out already (I don't know the logical operators). E.g

  • P | Q | Output
  • 1 | 1 | 1
  • 1 | 0 | 0
  • 0 | 0 | 0
  • 0 | 1 | 0

I need to find the logical operators and connectives (and, or, not, implies etc.) that is equivalent to the output. Please guide me through the steps or teach me how to work out how to do this. Thanks.



$\endgroup$

marked as duplicate by Rick Decker, David Richerby, Raphael Nov 10 '14 at 15:42

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ I have just been trying trial and error, so I would try a lot of different operators and try to get to the output but it's taking to long and so far it's not working. If this is duplicated could you please send me to the similar question? Thank you. $\endgroup$ – HelpMeThankYou Nov 10 '14 at 16:55
  • $\begingroup$ The page header gives you the link (to here). $\endgroup$ – Raphael Nov 11 '14 at 7:58
1
$\begingroup$

Generally speaking, there is no unique boolean function $f(p, q)$ that produces your output. For your example, the function $f(p, q) = p$ would be a valid solution, as well as $f(p, q) = (p \vee q) \wedge (p \vee \neg q)$, and $f(p, q) = (p \wedge q) \vee (p \wedge \neg q)$. You can find an equisatisfiable function to the one that produced the given output, and there are a number of approaches to do so.

A simple approach would be the enumeration of variable constellations that produce $\top$, and disjunct them. For your example that would mean first finding the constellations that produce $\top$:

  • $p \wedge \neg q$
  • $p \wedge q$

and finally producing $f(p, q) = (p \wedge q) \vee (p \wedge \neg q)$

This way you produce a function in disjunctive normal form (DNF). A similar approach works for CNF, but in both cases you end up with a fairly large function.

More complex approaches are Karnaugh Maps and the Quine McCluskey algorithm. They can produce much more concise, even minimal equisatisfiable functions.

As far as I know, most approaches focus on CNF (and sometimes DNF), i.e. use only conjunctions, disjunctions and negations, and don't nest operators any further.

$\endgroup$
  • $\begingroup$ I'm don't understand what f(p,q) means, and what does "variable constellations" mean is this context. Sorry I'm a first year at Uni. So everything you explained to get the function of a Truth table without the operators is called DNF? $\endgroup$ – HelpMeThankYou Nov 10 '14 at 17:00
  • $\begingroup$ $f(p, q)$ is just a declaration of a function $f$ with 2 variables ($p$ and $q$). With 'variable constellation' I meant a single entry in the table, e.g. where $P=T$ and $Q=F$. There are plenty of resources on DNF and other normal forms for functions on the web and in books. As advice for your time at university: learn to find information on stuff you don't know. You'll need to do that a lot. $\endgroup$ – Mike B. Nov 10 '14 at 22:22
0
$\begingroup$

The formula that produces your truth table is: $P$ (which you might also be calling $A$). More generally, you can produce the CNF and DNF representations, which in this case are $(P \lor Q) \land (P \lor \lnot Q)$, $(P \land \lnot Q) \lor (P \land Q)$ respectively. There is an algorithm for producing them that you might have learned in class.

$\endgroup$

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