# 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?

Blessings!

# 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.

# 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.

Blessings!

# 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?

# Truth Tree Catechism

Q: What is a truth tree?
A: A truth tree is a diagram that shows a set of compound propositions decomposed into literals following standard decomposition rules. Continue reading Truth Tree Catechism

# Reductio Challenge

In formal proofs of validity, the reductio ad absurdum method can be used to make some proofs easier, and even some shorter. For example, consider this argument:

(~P ⊃ R) • (~Q ⊃ S)    ~(R S)    ∴ P • Q

The proof for this valid argument is 14 steps without the reductio (which I will let you try to solve on your own), but only 7 steps with the reductio, as shown here:

1. (~P ⊃ R) • (~Q ⊃ S)
2. ~(R ∨ S)   /  ∴  P • Q
3. ~(P • Q)                     R.A.A.
4. ~P ∨ ~Q                    3 De M.
5. R ∨ S                         1, 4 C.D.
6. (R ∨ S) • ~(R ∨ S)   5, 2 Conj.
7. P • Q                          3-6 R.A.

The reasoning behind the reductio method is this: If assuming that a proposition is false leads to a self-contradiction, then the proposition must be true. This reasoning can itself be written as a propositional argument:

~P ⊃ (Q • ~Q)   ∴  P

This is a valid argument, as a shorter truth table will show. But the proof for this argument (if you are not allowed to use reductio) requires 13 steps, and it is rather difficult to solve. Any takers?

# Two Strange Proofs

Mr. Nance,

Could you give real-world examples of the arguments to prove in Intermediate Logic Lesson 18, number 7) U / ∴ W ⊃ W, and number 8) X / ∴ Y ⊃ X, showing how they would be used, or explain them a bit? Thank you.

Thanks for the great question! These two arguments are unusual, so I am not surprised that you are asking about them.

A real-world example for #7 might be Esther 4:16, “I will go to the king which is against the law; if I perish, then I perish!” This argument form basically shows that any proposition implies a tautology.

An example for #8 could be, “God created all things. So even if evolution can be used to explain some fossils, it’s still true that God created all things.” The form of this argument shows that if a proposition is given, any other proposition implies it.

To be honest, my purposes for including those two problems were: 1) to show how very strange the conditional proof is, and 2) to show how this method can be used to simplify otherwise difficult proofs.

Blessings!

# Conditional Proof Assumption

With the nine rules of inference and the ten rules of replacement taught in Lessons 13-17 of Intermediate Logic, any valid propositional argument can be proven. But for the benefit of the logic student, I introduce an additional rule in Lesson 18: the conditional proof. The conditional proof will often simplify a proof, especially one that has a conditional in the conclusion, making the proof shorter or easier to solve. Conditional proof starts with making an assumption. I want to clarify what happens with that assumption.

To use conditional proof, you start by assuming the antecedent of a conditional. If by using that assumption along with the other premises you are able to deduce the consequent, you can conclude the entire conditional using conditional proof. More briefly, if an assumed proposition p implies the proposition q, we can conclude if p then q.

One misconception new logic students often make is thinking that the assumption actually “comes from” some previous step in the proof. They think that the assumption must appear somewhere else in order to make it. This is not the case. The assumed antecedent doesn’t come from anywhere; it is quite simply assumed. I tell my students we get the antecedent from our imagination; from Narnia, Middle Earth, Badon Hill. With conditional proof, you are allowed to assume any antecedent you wish, as long as you use conditional proof correctly from that point on.

# May Proofs Use the Same Line Twice?

Mr. Nance,

In the answer to Exercise 17a, problem #12, is there a typo? It has row 5 twice.

There is no mistake there. A given line may be used more than once in a proof, as I say at the end of Lesson 15, “Usually, though by no means always, every step in a proof is used and used once.” Line 5 is used twice, once to simplify to get ~L, and once to commute and simplify to get ~M.

Blessings!

# More Help w/ Exercise 17a

In Exercise 17a of Intermediate Logic, some of the later proofs use similar procedures as earlier proofs in the assignment. In the video below, I show how problem 10 depends upon the proof of problem 1.