Subsection 3.3.10 A Tool for Checking Natural Deduction Proofs
We have built an interactive proof checker that you can use to check your proofs as you are writing them. We can begin using it now, for simplification proofs. Later we’ll see that it can also be used for proof that exploit additional inference rules.
The checker needs to be initialized with a particular problem to solve. There isn't a simple interface that lets you create problems and feed them to the checker. But we have created a collection of them that you can work with.
When it's time to do a proof, either as an example in one of our slides, or as part of a problem, you'll see the proof checker show up on your screen.
You can create your proof with very little typing. You can cut an paste from previous lines or from the symbol list at the bottom of the proof area.
To create a proof step, begin by choosing one or two statements from the list of available ones. Initially, there will just be premises. But, as you create new lines in the proof, they too will be available.
Then select a rule from the rule selection tool bar.
Finally enter the line that results from applying the chosen rule to the chosen input(s). Click the green check mark and the checker will test whether your step is valid.
If you click on the funnel (at the left of the rule selection tool bar), the checker will filter the rules and only show you the ones that can be applied to the statement(s) you've selected.
If you have selected a rule, you can click on the wrench (on the right of the rule selection bar) and you'll see what will happen if you apply that rule to the statement(s) you've selected.
Exercises Exercises
Exercise Group.
1.
1. Prove that ( p ∧ q ) → ( p ∨ q ) is a tautology by using Boolean identities to prove that it is equivalent to T .
\(\displaystyle (p \wedge q) \rightarrow (p \vee q)\)
\(\neg (p \wedge q) \vee (p \vee q)\) Conditional Disjunction
\((\neg p \vee \neg q) \vee (p \vee q)\) De Morgan
\((\neg q \vee \neg p)\vee (p \vee q)\) Commutativity of or
\(\neg q \vee ((\neg p \vee p) \vee q)\) Associativity of or
\(\neg q \vee (T \vee q)\) Computation
\(\neg q \vee q \) Computation
\(T \) Computation
2.
2. Simplify: ¬( r ∨ q ) → ¬( p ∧ ( q ∧ s )) to T .
\(\displaystyle \neg (r \vee q) \rightarrow \neg (p \wedge (q \wedge s)) \)
\(\neg (r \vee q) \rightarrow (\neg p \vee \neg ( q \wedge s)) \) De Morgan
\(\neg (r \vee q) \rightarrow (\neg p \vee (\neg q \vee \neg s)) \) De Morgan
\(\neg (r \vee q) \rightarrow ((\neg q \vee \neg s) \vee \neg p) \) Commutativity of or
\(\neg \neg (r \vee q) \vee ((\neg q \vee \neg s) \vee \neg p) \) Conditional Disjunction
\((r \vee q) \vee ((\neg q \vee \neg s) \vee \neg p) \) Double Negation
\(( (r \vee q) \vee (\neg q \vee \neg s)) \vee \neg p \) Associativity of or
\(((( r \vee q) \vee \neg q) \vee \neg s) \vee \neg p \) Associativity of or
\(( (r \vee (q \vee \neg q)) \vee \neg s) \vee \neg p \) Associativity of or
\(( (r \vee T) \vee \neg s) \vee \neg p \) Computation
\((T \vee \neg s) \vee \neg p \) Computation
\(T \wedge \neg p \) Computation
\(T\) Computation
3.
3. Prove that these two expressions are equivalent:
\(\displaystyle p \vee \neg (q \wedge r) \)
\(\displaystyle q \rightarrow (r \rightarrow p) \)
\(\displaystyle p \vee \neg (q \wedge r) \)
\(p \vee (\neg q \vee \neg r) \) De Morgan
\((\neg q \vee \neg r) \vee p \) Commutativity
\(\neg q \vee (\neg r \vee p) \) Associativity
\(q \rightarrow (\neg r \vee p) \) Conditional Disjunction
\(q \rightarrow (r \rightarrow p) \) Conditional Disjunction
Exercises Exercises
Exercise Group.
In these problems, we’ll explore the relationship between equivalent English sentences and the corresponding equivalent Boolean expressions.
1.
1. Consider the sentence: He was not unaware that she was a student.
Which of the following gives an equivalent sentence and explains the equivalence with one of our identities:
He was aware that she was a student. Contrapositive.
He was aware that she was a student. Double Negation.
He was unaware that she was a student. Double Negation.
She was a student. Idempotence.
He was aware that she wasn’t a student. Conditional Disjunction.
2.
2. Consider the sentence: The Astros and the Phillies can’t both win.
Which of the following gives an equivalent sentence and explains the equivalence with one of our identities:
The Astros and the Phillies can both win. Contrapositive.
The Astros or the Phillies can win. De Morgan.
The Astros or the Phillies must lose. De Morgan.
The Astros and the Phillies must lose. Contrapositive.
The Astros and the Phillies must lose. De Morgan.
Explanation: The easiest way to see this is to write the original sentence in logic. Assign symbols as follows:
\(\neg (A \wedge P) \)
If we apply De Morgan to this, we get:
\(\neg A \vee \neg P \)
In English, this becomes, “At least one of these must be the case: The Astros cannot win or the Phillies cannot win.” Since not winning is losing, we can rephrase that clunky sentence as, “The Astros must lose or the Phillies must lose.” Another rephrasing gives us, “The Astros or the Phillies must lose.”
3.
3. Consider the sentence: The kitten stays or I’m outta here.
Which of the following gives an equivalent sentence and explains the equivalence with one of our identities:
The kitten and I are leaving. De Morgan.
If the kitten leaves, I go too. Conditional Disjunction.
The kitten and I are both staying. Conditional Disjunction.
If the kitten stays, so do I. Commutativity of or .
If the kitten leaves, I go too. De Morgan.
Explanation: The easiest way to see this is to write the original sentence in logic. Assign symbols as follows:
K: The kitten leaves.
L: I leave.
Then (assuming that staying means not leaving) our sentence corresponds to the statement:
\(\neg K \vee L\)
If we apply Conditional Disjunction to this, we get:
We can render that in English as, “If the kitten leaves, then I leave too.”\(K \rightarrow L \)
4.
4. Consider the sentence: Take your umbrella or it will rain.
Which of the following gives an equivalent sentence and explains the equivalence with one of our identities:
If you don’t take your umbrella, it will rain. Conditional Disjunction.
If you take your umbrella, it will rain. Conditional Disjunction.
If you take your umbrella, it won’t rain. Conditional Disjunction.
If it rains, you didn’t take your umbrella. Conditional Disjunction.
If you don’t take your umbrella, it will rain. De Morgan.
Explanation: The easiest way to see this is to write the original sentence in logic. Assign symbols as follows:
U: You take your umbrella.
R: It will rain.
Then our sentence corresponds to the statement:
\(U R \)
We can apply Conditional Disjunction to this. The one slightly tricky thing is that the right hand side of conditional disjunction is (p q). We don’t have a not in our disjunction. But we can let p correspond to U. Then p is U and now the right hand side matches what we’ve got. Then we apply the identity and we get:
\(\neg U \rightarrow R \)
We can render that in English as, “If you don’t take your umbrella, it will rain.”