Digital Logic Q & A

Mr. Nance,

I have an overload of questions on digital logic. Hope that is okay!

1. Truth-functional completeness often makes circuits more complicated than they have to be. Is there anything besides cost-effectiveness that is beneficial about truth-functional completeness?

I assume you are asking “Why do we learn how to use NOR gates or NAND gates exclusively in a circuit?” Primarily, it is just to teach students how the gates work. But in practice, if you are constructing an electronic device, you may not have all the gates available (e.g. Radio Shack ran out and will not get them in for ten days), and so need to use a couple of NAND gates to do the job of one AND gate. Also, you might only use one NOR gate in the circuit, but a chip might contain four NOR gates, so why not just use three of them to replace an AND gate instead of buying one?

2. Since the symbol for NOR is the upside-down triangle, is there a symbol for NAND?

The triangle symbol is largely my own convention. See the Wikipedia page for the standard ways of expressing NOR. I know of no special symbol for NAND.

3. Is there a conditional gate (P ⊃ Q)?

Not that I am aware of. You can make a conditional using other gates.

4. Why do we write the names of logic gates in all caps? ( AND instead of and or And)

Just to distinguish them from the words in a sentence. It would be confusing to read “Take an or gate and an and gate…”

5. Why in K-maps do we circle in groups in powers of two?

Because that’s how they work to correctly simplify propositions. Draw yourself a K-map with 0111 across the top four cells, and 1110 across the bottom four cells. If you made two circles with groups of three across and ask, “What variable stays the same (negated or unnegated)?” the answer is that nothing stays the same, so no proposition can be identified. To get the simplest proposition, you must circle the middle four square, and the two on the top right and bottom left. Spend some time thinking through exactly what the K-map is doing when you circle groups and determine the proposition from the circled group. (See the next question.)

6. Finally, do K-maps eliminate the need for the Algebraic identities? I found that doing the Digital Logic Project didn’t require using them.

Yes, that is their primary benefit. Consider the proposition (p • q) ∨ (p • ~q). This simplifies this way:

  1. (p • q) ∨ (p • ~q)  Given
  2. p • (q ∨ ~q)  Distribution
  3. p • 1  Tautology
  4. p  Alg. identity

Now do a 2×2 K-map for this proposition:




See how it does the same thing in a faster, easier way?


A Brief History of Validity #3

The nineteen traditional valid forms of syllogisms named by medieval scholars, plus the five forms which can be deduced by subimplication of those with a universal conclusion, comprise the twenty-four forms of syllogisms identified as valid in my Introductory Logic text.

However, since the time of George Boole, a 19th-century mathematician, only fifteen of those twenty-four forms are recognized as valid. Why is this? Boole argued that the truth of a particular statement cannot be inferred from the truth of its corresponding universal, because a particular statement asserts the existence of its subject, but a universal statement does not. That is, to say, “Some athletes are dedicated people” is to assert that at least one athlete exists, but to say that “All athletes are dedicated people” is only to say that if one is an athlete then one is a dedicated person. According to Boole, the four categorical statements should be interpreted this way:

All S is P = If S exists then it is P
No S is P = If S exists then it is not P
Some S is P = There exists at least one S that is P
Some S is not P = There exists at least one S that is not P

Particular statements are said to have existential import; they claim that the terms in the statement exist. Universal statements, however, do not have existential import; they are considered as material conditionals.

In this interpretation, no particular statement can be inferred from a universal statement, or from universal premises. One could not validly argue, for instance,

All grandfathers are fathers.
All fathers are men.
∴ Some men are grandfathers.

This AAI-4 (Bramantip) syllogism is said to make the existential fallacy, which is based on this sixth rule of validity: “A valid syllogism cannot have universal premises and a particular conclusion.” By the modern interpretation, the premises only say this:

If grandfathers exist then they are fathers.
If fathers exist then they are men.
∴ There exists at least one man who is a grandfather.

These premises do not claim that grandfathers or fathers or men exist, but the conclusion does. Thus the conclusion claims more than is contained within the premises, which means the syllogism is invalid.

There is much to commend the modern view of interpreting categorical statements. For example, in the traditional view, this is a valid chain of reasoning:

No athletes are people that breathe underwater ⇒ (by converse)
No people that breathe underwater are athletes ⇒ (by obverse)
All people that breathe underwater are non-athletes ⇒ (by subimplication)
Some people that breathe underwater are non-athletes.

Everyone would agree that the first statement is true, but most people would say that the last statement is false, because it seems to imply that there are people that breathe underwater.

However, I think that the modern interpretation of categorical statements is potentially flawed. Does not the statement “No people that breathe underwater are athletes” seem to imply that there are people that breathe underwater? And why insist that particular statements have existential import? Consider these particular statements:

Some hobbits are not Shire dwellers.
Some black holes are members of binary stars.
Some of your sons will be the king’s horsemen.

Most people would argue that, in the sub-created world of Tolkien, the first statement is true, even though (in our world) hobbits do not exist. Most astronomers would argue that the second is almost certainly true, even though the existence of black holes is still in doubt. The last statement was uttered by Samuel to the people in the hope that it would not be true, that such sons would not exist.

Much more could be said, but the logic student should at least be aware that this debate exists.

Immediate Inference Cheat Sheet

Equivalent Immediate Inferences of the four Categorical Statements:

All S is P
=  No S is non-P  (obverse)
=  All non-P is non-S  (contrapositive)

No S is P
=  All S is non-P  (obverse)
=  No P is S  (converse)

Some S is P
= Some S is not non-P  (obverse)
= Some P is S  (converse)

Some S is not P
= Some S is non-P  (obverse)
= Some non-P is not non-S  (contrapositive)

Immediate inferences work in reverse:

All S is non-P
= No S is P  (obverse)

All non-S is non-P
= All P is S  (contrapositive)

No S is non-P
= All S is P  (obverse)

Some S is non-P
= Some S is not P  (obverse)

Some S is not non-P
= Some S is P  (obverse)

Some non-S is not non-P
= Some P is not S  (contrapositive)

Immediate inferences can be combined:

No non-S is P
= No P is non-S = All P is S  (converse, obverse)

Some non-S is P
= Some P is non-S = Some P is not S  (converse, obverse)

Other translations:

All non-S is P
= All non-P is S  (contrapositive)

No non-S is non-P
= All non-S is P  (obverse)

Some non-S is not P
= Some non-P is not S  (contrapositive)

Some non-S is non-P
= Some non-S is not P  (obverse)

All of this and more is included in this complete Immediate Inference Chart.

A Simpler Truth Tree

In this video, I decompose a set of propositions from Intermediate Logic, Additional Exercises for Lesson 24. I first decompose the truth tree in the order of the given propositions. I contrast this with a second truth tree that uses the simplifying techniques from Lesson 24.

This shows first, how to use a truth tree to determine consistency, and second, how the techniques from Lesson 24 make the truth tree simpler.

A Brief History of Validity #2

In the last post in this series, we saw that Aristotle identified 16 valid forms of categorical syllogisms (though he formally acknowledged only the first three figures). Some thirteenth-century logicians such as William of Sherwood and Peter of Spain recognized nineteen valid forms, giving them Latin names as a mnemonic device for ease of memorizing: Continue reading A Brief History of Validity #2

A Brief History of Validity #1

Which forms of categorical syllogisms are valid? Logicians have disputed the answer for centuries, a dispute that can give us insight into the meaning of validity, the central concept of formal logic. This will be the first of a few posts in which I will briefly discuss the history of syllogistic validity.

It all started with Aristotle, who in his Prior Analytics, Book I, chapters 4-7, detailed sixteen valid forms: Continue reading A Brief History of Validity #1

Rhetoric Interview

The following is a slightly edited version of a survey given me by Joshua Butcher – rhetoric instructor at Trinitas Christian School in Pensacola, Florida – regarding the teaching of rhetoric in a classical, Christian setting.

Josh:  How long have you taught rhetoric in a classical education setting?
Jim:  I taught Classical Rhetoric for 18 years at Logos School to 11th graders. I have also written a rhetoric text – Fitting Words: Classical Rhetoric for the Christian Student – and lectured through it.

Josh:  What are the essentials of rhetoric that every classically educated student should have?
Jim:  Do you mean, “What are the essential rhetorical skills that every classically educated student should seek to master?” Continue reading Rhetoric Interview

After Intermediate Logic?

What is recommended after Intermediate Logic? The short answer is: Rhetoric! But let me give you a bit more than that.

Introductory and Intermediate Logic together provide a complete foundational logic curriculum. Informal, categorical, and modern propositional logic are all included. The next step in a student’s classical education is to begin to apply what they have learned in logic to effective speaking and writing. This means that the student should move on to study formal rhetoric. Rhetoric applies the tools of logic: defining terms, declaring truth, arguing to valid conclusions, and refuting invalid ones. Indeed, of the modes of rhetorical persuasion – ethos, pathos, and logos – one-third is applied logic.

With this in mind, Roman Roads has released a new curriculum, Fitting Words: Classical Rhetoric for the Christian Student. I am the author of this text, and in Fitting Words I work to apply in rhetoric much of what the student has learned in logic. I am very excited about this project, because one significant reason that I wrote this text was to provide a satisfying answer the question of where to go next!

Take a look HERE for the most up-to-date information about Fitting Words.

Equivalence w/ Shorter Truth Tables

Mr. Nance,

Within Intermediate Logic Lesson 11, what would keep us from setting up the propositions both being true at the same time, and if there were a contradiction they would not be equivalent? Instead of setting them up one true and one false and if there’s a contradiction then they are equivalent?

That would be checking for consistency, not equivalence. If you set them both as true, and get a contradiction, then they are not consistent (which of course also means they are not equivalent, nor related by implication, per the chart in Introductory Logic, p. 71). But if you get no contradiction, all you have shown is that they can both be true, which is the meaning of consistency. To show equivalence, you have to show that they cannot have opposite truth values: the first cannot be true while the second is false, and vice versa.


Formal Proof Challenge!

Several years ago I was teaching a logic course, and we were learning about formal proofs of validity. I enjoy proofs, and to keep myself sharp I was working through a practice quiz in David Kelley’s The Art of Reasoning, when I came across this argument:

D ⊃ (E ⊃ F)
D ⊃ (F ⊃ G)
∴ D ⊃ (E ⊃ G)

I was in a quiet library with plenty of time, but despite all my efforts I could not solve this (without using the Conditional Proof). The next day in class some students were finishing their assignment early, so I  challenged them with this proof, thinking to myself, “That ought to keep them busy,” but not really expecting anyone to succeed. Before the end of class, Caroline Jones came forward and said, “I solved it, Mr. Nance.” I scoffed inwardly at first, only to be pleasantly surprised by her correct solution.

Since that time I have called this “The Caroline Jones” proof, and have challenged my logic students to solve it using only the regular rules of inference and replacement. The most elegant proof I have seen requires twelve total steps.

Anyone up to the challenge?