Take the 2-minute tour ×
Mathematics Educators Stack Exchange is a question and answer site for those involved in the field of teaching mathematics. It's 100% free, no registration required.

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.

share|improve this question
2  
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 at 12:28
3  
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 at 13:02
7  
I must be missing the intent of the question. What about logic gates? –  Git Gud Mar 29 at 15:48
    
Logic gates sound like a good answer to me. Thank you. –  Anschewski Mar 29 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 at 19:07

9 Answers 9

up vote 10 down vote accepted

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()
s.add(constraints)

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"
share|improve this answer
    
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 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 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 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 at 17:02
    
As for a book, Russell and Norvig discuss solving CSPs in their AI book. –  adamblan Mar 31 at 17:04

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

enter image description here

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.

enter image description here

share|improve this answer
1  
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 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. –  Matt F. Mar 30 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 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 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 at 18:52
 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.

share|improve this answer

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.

share|improve this answer
    
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 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 at 4:18

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.


Edit: Example added.

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))
share|improve this answer
1  
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 at 14:20
1  
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 at 15:34

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.

share|improve this answer

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

share|improve this answer
1  
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 at 19:50
    
You would like to check this site heartlandforensic.com/writing/forensic-inference/… –  user505 Mar 30 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 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 at 14:50
    
I've changed my vote accordingly; cheers! –  Chris Cunningham Mar 30 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.)

share|improve this answer
    
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 at 2:22

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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