# Real-World Applications of Logic

When introducing logic in a first semester university course, the examples I use are often quite artificial. One example: One of three kids (Annie, Bob, Chris) has broken a window. Annies says "it was Bob", Bob says "it was Chris", Chris says "exactly one of them is lying". You know that all three kids are lying. Who has broken the window?

However, such examples (how ever complicated you design them) are far away from real-world problems. I remember I once heared that in some expensive medical tests, you mix up material from different persons to see whether one of them is positive (don't know if this is true). So I became curious if there might be more realistic applications of logic (e.g. by mixing different samples).

Question: Are there real-world applications of propositional calculus? (Maybe very different from what I suggested?) Good answers should refer to problems which already exist (for instance in applied sciences) and are more easily handeled with the use of propositional calculus. I do not mean problems which were just generated as examples for the use of logic.

• For the "mixing samples" see (possibly) for the process mathoverflow.net/questions/59939/identifying-poisoned-wines I do not know if this is applied in medicine though (Not sure this fits the logic context perfectly though. But perhaps with a smaller number of samples it will.) – quid Mar 29 '14 at 12:28
• I thought that each time I was using a previously proven result in my own proof (i.e. check the premises, infer the thesis), I was applying logic. To name some concrete example, the linear 2SAT algorithm via the implication graph is a direct application of propositional calculus. – dtldarek Mar 29 '14 at 13:02
• I must be missing the intent of the question. What about logic gates? – Git Gud Mar 29 '14 at 15:48
• Logic gates sound like a good answer to me. Thank you. – Anschewski Mar 29 '14 at 16:06
• ?!? closely connected boolean algebra is the basis of all modern computing and there is deep study in TCS on the satisfiability problem and also QBFs, quantified boolean formulas. might try to work some of this into an answer later if no one else does (someone else can maybe do better job of it anyway)... see also Davis book on Engines of logic. – vzn Mar 29 '14 at 19:07

There's a couple nice directions you could go here.

To discuss questions that are most similar to your example but more "authentic", you could look at any variety of constraint satisfaction problems. For example, Sudoku can be formulated as a bunch of constraints (each grid has exactly one of each number, no number appears multiple times, etc.) All of these can be formulated in propositional calculus. Another nice example is scheduling classrooms.

For something totally different, you could point out how ambiguous english can be and motivate logic as a precise system. My favorite way to do this is to choose some particularly hairy paragraph from a very old philosopher (e.g. some part of Pascal's wager), ask one of the students to read the whole thing quickly, and then ask the students if they understood anything. This isn't directly what you're asking for, I think, but it definitely helps motivate why mathematicians might care about logic to students who have read confusing prose (which is most of them).

For example, using the SMT solver Z3, this is code to solve Sudoku by defining logical formulae:

# define the puzzle as a 2D array here
from z3 import *
solution = Function('solution', IntSort(), IntSort(), IntSort(), BoolSort())

constraints = []

for i in range(len(puzzle)):
for j in range(len(puzzle)):
if puzzle[i][j] != 0:
# The result must match what we already know.
constraints.append(solution(i, j, puzzle[i][j]))

# Every cell must have some value
constraints.append(Or([solution(i, j, n) for n in range(1, 10)]))

#...but only one value
constraints.append(And([
Implies(
solution(i, j, n),
And([Not(solution(i, j, np)) for np in range(1, 10) if np != n])
)
for n in range(1, 10)]))

# Every row must have some value
constraints.append(And([
And([
Or([solution(i, j, n) for j in range(9)])
for i in range(9)])
for n in range(1, 10)]))

# Every column must have some value
constraints.append(And([
And([
Or([solution(i, j, n) for i in range(9)])
for j in range(9)])
for n in range(1, 10)]))

# Every box must have some value
constraints.append(And([
And([
Or([solution(i + boxi*3, j + boxj*3, n) for i in range(3) for j in range(3)])
for boxi in range(0, 2) for boxj in range(0, 2)])
for n in range(1, 10)]))

s = Solver()

if s.check() == sat:
m = s.model()
r = [[ [n for n in range(1, 10) if is_true(m.evaluate(solution(i, j, n)))][0]  for j in range(9)] for i in range(9)]
print_matrix(r)
else:
print "failed to solve"

• Thank you for your answer. When you mention scheduling classrooms, is propositional calculus just used for formulation of the problem or can it help solving the problem? Do you have an example? – Anschewski Mar 31 '14 at 16:12
• It depends on how you want to solve it. For most CSPs, the only part that you do is formulate it using some notation for whichever CSP solver you're using. Then, you either use a library or a standard algorithm to solve the constraints. – adamblan Mar 31 '14 at 16:19
• That sounds great, I would like to work this out with some students. Would you please lead me the way to a standard algorithm (name, link, book, ...)? – Anschewski Mar 31 '14 at 16:55
• I've added a solution to Sudoku above that uses the Z3 SMT solver. To be honest, part of my research is developing a nicer language for students to be able to do this sort of thing in. I can keep you updated when I have a beta version, if you'd like. – adamblan Mar 31 '14 at 17:02
• As for a book, Russell and Norvig discuss solving CSPs in their AI book. – adamblan Mar 31 '14 at 17:04
 if (real world applications are those which make money){
then if (programming makes money){
print("Programming is a real world application of propositional logic")
}
}


You definitely have to know how to evaluate truth values of various statements to accomplish even very basic programming tasks.

I am adding extra text to prevent the constant spam attacks on this answer. I think this should do it. I believe I am now over 400 characters.

• Can all of non-fuzzy or discrete logic be represented in terms of ifs and elses? – Domi Feb 24 '15 at 11:54
• @Domi I'm not sure if this answers your question, but in propositional logic $\implies$ and $~$ are known to be functionally complete. – Ovi May 9 '17 at 19:09

I think a good real-world example for an undergraduate course on logic is to discuss the following:

The source of this is:

McGee, V. (1985). A counterexample to modus ponens. The Journal of Philosophy, 462-471.

In a somewhat related vein, I think it is wise to discuss the difficulty that can be run into when trying to rephrase language from our regular lives into "logical" notation. Susanna S. Epp gives the following example, in which different interpretations of "unless" are provided by three different mathematicians.

• The quote from McGee's article is silly. "Those apprised of the poll believed with good reason" is just plain false. Anyone with good reasoning faculties, apprised of the poll, would have believed that (a) if a Republican wins and it is not Reagan, then it will probably be Anderson, and (b) that a Republican will probably win. Propositional logic does not apply. It's a good example for a probability course, though. – Theodore Norvell Mar 30 '14 at 13:55
• Those are great examples, but I would conclude from them that: The "if" that we use in mathematics does not correspond well to "if" in natural language; the logic we use in math is a poor choice for qualitative real-world applications.... It's hardly what @Anschewski was looking for; I think those examples fit better in a linguistics class. – user173 Mar 30 '14 at 14:48
• @TheodoreNorvell The entire article concerns examples like that one. You may find it silly, but it was published in a well-respected journal, and has more than 200 citations (according to Google Scholar). I don't mean to suggest that modus ponens should be omitted from mathematical reasoning; only that it is a nice real-life example to discuss. – Benjamin Dickman Mar 30 '14 at 23:27
• @MattF. You may be right; what the OP asks for is real-world problems that can be resolved using logic (in its formal sense). I think an important pedagogical complement to such answers would be real-world examples in which the use of formal logic can be confusing, lest students apply what they are learning willy-nilly. (FWIW: I saw the latter example originally in a Discrete Mathematics class that covered logic, and later on in a colloquium talk [for grad students in Math Ed] given by Professor Epp.) – Benjamin Dickman Mar 30 '14 at 23:33
• @Benjamine Dickman. I'm sure you don't get on faculty at MIT by writing silly articles. I did read the first few pages of this one. I think his point was that people use the English phrase "if p then q" in ways that are not consistent with modus ponens. I think he missed that people use the same phraseology to mean different things; sometimes they mean material implication and sometimes they mean something that might be better expressed as "if p then probably q". Furthermore, when people say "p", sometimes they mean "probably p". What we say we believe is not always exactly what we believe. – Theodore Norvell Apr 1 '14 at 18:52

Nearly all examples for perceived equivalences which are only implications. The classic (at least in Germany) is:

If it rains, the road gets wet.

If the road ist wet, has it rained?

You'll stumble across these things everyday if you look out for them.

• Your example is well-known to me, but not what I was looking for. I rather think of some application in the sense that logic helps solving a real problem. In your example, reality just illustrates logic. – Anschewski Mar 29 '14 at 15:37
• @Anschewski: this is very closely related to scientific inference. For instance, if it were to rain but the road did not become wet, then the first statement would be falsified. This falsification would then alter our interpretation of other facts -- such as if the road is NOT wet, we could no longer be confident that it had not rained. This framework also suggests some options for illustrating baysean logic. – adam.r Mar 30 '14 at 4:18

Note that a processor (like in your computer, or cellphone, or the one in every nontrivial electronic device that you have) is just a huge proposition written in propositional calculus.

If that's not a real world application of logic, I don't know what is.

Besides digital hardware, which others have mentioned, propositional logic has applications in software. For better or worse, this is usually three-valued logic; however for the purposes of a logic course, this fact can be glossed over.

This is a real example. It comes from the merge phase of the merge sort algorithm.

Consider the command

if q = k or (p not= j and B[p] < B[q])
then (A[r] := B[p]; p:=p+1)
else (A[r] := B[q]; q:=q+1)


Suppose that you know that not(q = k and p = j), show that the "else" part is executed exactly if

p = j or (q not= k and B[q] _< B[p])


The only thing you need to know about programming is that the else part will be executed exactly if the guard

q = k or (p not= j and B[p] < B[q])


is false. So the logical problem consists of showing that, given not(q = k and p = j), the following equivalence holds

not( q = k or (p not= j and B[p] < B[q]) ) = ( p = j or (q not= k and B[q] _< B[p]) )


In terms of propositional logic, the problem is: Given not(P and Q) show

not( Q or (not P and R)) = (P or (not Q and not R))

• Welcome to the site and thank you for your contribution! Could you please add some more details to your answer? I think it would be more helpful in this way. For example, by sketching an example that could be used in a course. Or, also by elaborating on the 'three valued' aspect. – quid Mar 30 '14 at 14:20
• The three valued aspect is because in evaluating a Boolean expression, there are three possible results: true, false, and undefined. Some programming languages (e.g., C, C++, Java, C#) define conjunction and disjunction in an asymmetric manner so that $x \wedge y$ is false if $x$ is false and $y$ is undefined, but is undefined if $y$ is false and $x$ is undefined; and dually for disjunction. Thus the commutative laws for conjunction and disjunction are out. This is important to know if you are programming, but can be glossed over if you assume all basic Boolean expressions are defined. – Theodore Norvell Mar 30 '14 at 15:34

Forensic Science is probably one of the answer. There you have evidences which are logically evaluated to come to a conclusion. Sometimes logic is the only option to fill in the gap to continue/reach the final conclusion.

Formal Course

• Welcome to the site! While I think it's true that forensic science involves logic, I don't think it would ever include formal logic (truth tables, etc) of the form being asked about in this question. If you can include an example of a forensic problem that would require some of the formal logic covered in a first-semester university course, that would make for an excellent answer. However, until then, I've downvoted this question. I hope you don't take this as a judgment on you -- only on the quality of this particular answer! – Chris Cunningham Mar 29 '14 at 19:50
• You would like to check this site heartlandforensic.com/writing/forensic-inference/… – user505 Mar 30 '14 at 14:02
• If you fleshed out some of the ideas in that link and adjusted your answer accordingly, I think the new answer would be dramatically improved. I'd certainly change my vote. – Chris Cunningham Mar 30 '14 at 14:34
• mathematically I was aware writting this technically correct answer will result in downvote so I was right and truth table was a great help :). So, you edit as per your liking to correct the wrong Thanks in advance – user505 Mar 30 '14 at 14:50
• I've changed my vote accordingly; cheers! – Chris Cunningham Mar 30 '14 at 14:53

Fuzzy logic "is a form of many-valued logic; it deals with reasoning that is approximate rather than fixed and exact. Compared to traditional binary sets (where variables may take on true or false values) fuzzy logic variables may have a truth value that ranges in degree between 0 and 1." It "has been applied to many fields, from control theory to artificial intelligence." You may have heard of appliances such as washing machines that use fuzzy logic. An example of a fuzzy logic statement is "If the temperature is hot then speed up the fan." (Note that "hot" and "speed up" take on a range of values.)

Temporal logic "is any system of rules and symbolism for representing, and reasoning about, propositions qualified in terms of time." I can't give a reference right now, but I've seen it used to describe the operation of elevators. An example of a temporal logic statement is "The elevator will eventually stop." (Note that the truth of a statement can vary with time.)

• Interestingly enough the development of both fuzzy logic and temporal logic came as a result of scholars (Jan Lukasiewicz and Arthur Prior) who spent much of their time studying propositional calculi. – Doug Spoonwood May 3 '14 at 2:22
• Temporal logic can be used for controlling robots. See, for instance, Controlling Wild Bodies Using Linear Temporal Logic by Bobadilla et al, 2011, and the references contained therein. – J W Aug 4 '14 at 6:28
• @JW, thanks for the link. – Joel Reyes Noche Aug 4 '14 at 6:30

I use logic in my lab to understand and model how cancers grow and develop. More generally, there is a large group of people across the world who use methods in logic (executable biology, logical biology) to understand how tissues grow and develop.

I teach a course which shows how we use logic to model systems; the documents (which can be run in jupyter notebook) are available here:

https://github.com/hallba/WritingSimulators

I've also written a wider set of examples on how to use one specific tool, Z3, to answer problems using logic.

https://github.com/hallba/Z3Tutorials

Whilst this is an old question, I hope this response will be useful to other who find it!

Another application is negation of universal and existential quantification. Take for example an advertisement:

All our second-hand cars come with working air-con.

You need only to find one these cars without working air-con to disprove the sentence.

And another application is contraposition. For example, teachers often say to the student's parents

If your student works harder, he'll improve.

which is easily accepted. When he won't improve and the parents come back to the teacher, he will answer:

He didn't improve, that means he didn't work harder.

A real world example of how a logic gate can be used:

1) most of us have a garage light that is controlled by a switch. However, it may also automatically turn on when it senses motion during nighttime. This example has 3 inputs A = is the switch on? B = is it daytime? C = is there motion nearby?

We want the only output (garage light) to turn ON when:

The switch is ON or it is nighttime and there is motion nearby


Logic Statement = A + !BC

Does anybody else have a similar example to this?

Not a "good answer" since I don't have a problem repository but wanted to share what I could.

1. GRE and LSAT have lots of logic problems. I believe GRE used to have a whole section of logic problems but now it is just a subset of a section. (Took it decades ago.) You can look at a Kaplan or Princeton Review book (or a sample test from ETS/CB). I believe they are artificial in the manner you worry about but perhaps looking through them you find some that are more "real world". Also, at least it is another context where logic skills are valued.

2. Quite a few business cases (for admissions or even on studies) use something called an issue tree. I don't know that this is always rigidly logical in the manner of a Boolean circuit (can sometimes find nuances to violate the logic) but in general (or as an approximation), they are logical or at least one attempts to formulate a structure that will make it so. See the attached tree for the "profitability case".

1. Root cause analysis in engineering failures or accidents (NTSB, Space shuttle, etc.):

https://www.preplounge.com/en/bootcamp.php/case-cracking-toolbox/identify-your-case-type/profitability-case

(Not always a perfect simple 20 questions style of problem solving as you may have multiple causes or interactions but often branches of the issue analysis have a logical structure.)

1. Many diagnostic medical programs (already commonly used by a minority of physicians, I had an appointment with a guy using one) have a logical structure.

2. Qualitative analysis in chemistry (solubility rules):