Problems - Mathematical Logic
Problem (Examples of propositions)
Which of the following sentences are propositions, which are not?
| (i) | Berlin is the capital of Germany. |
| (ii) | All students are diligent. |
| (iii) | Yesterday it rained all day. |
| (iv) | Travel broadens the mind. |
| (v) | The class has already started. |
| (vi) | Is mathematics difficult to learn? |
| (vii) | Congratulations! |
Problem (Own examples of propositions)
Formulate at least
| (i) | three examples of propositions, |
| (ii) | three examples of statements or sentences which are not propositions. |
Problem (Examples of formulas)
Give an example of a formula \( {\mathcal R}(x) \) with one, \( {\mathcal S}(x,y) \) with two, and \( {\mathcal T}(x,y,z) \) with three variables, resp., such that
| (i) | \( {\mathcal R}(6) \) is true, |
| (ii) | \( {\mathcal S}(1,7) \) is true, |
| (iii) | \( {\mathcal T}(1,3,12) \) is true. |
Problem (NOR connection)
The NOR connection (Not Or) is defined as \[ \neg(a\vee b). \] Give a truth table of this connection. When is it true, when is it false?
Problem (NAND connection)
The NAND connection (Not And) is defined as \[ \neg(a\wedge b). \] Give a truth table of this connection. When is it true, when is it false?
Problem (XOR connection)
The XOR connection (Exclusive Or) ist defined as \[ (a\wedge\neg b)\vee(\neg a\wedge b). \] Give a truth table of this connection. When is it true, when is it false?
Problem (XNOR connection)
The XNOR connection (Exklusive Not Or) is defined as \[ (a\wedge b)\vee(\neg a\wedge\neg b). \] Give a truth table of this connection. When is it true, when is it false?
Problem (AOI connection)
The AOI (2-1 gate) connection (And Or Invert) is defined as \[ \neg[(a\wedge b)\vee c]. \] Give a truth table of this connection. When is it true, when is it false?
Problem (OAI connection)
The OAI (2-1 gate) connection (Or And Invert) is defined as \[ \neg[(a\vee b)\wedge c]. \] Give a truth table of this connection. When is it true, when is it false?
Problem (Double negation)
Use a truth table to prove \[ \neg\neg a\equiv a. \]
Problem (Idempotent laws of propositional logic)
Use truth tables to prove the following equivalences.
| (i) | \( a\equiv a\vee a \) |
| (ii) | \( a\equiv a\wedge a \) |
Problem (Converse of implication)
Use a truth table to prove \[ a\to b\equiv\neg b\to\neg a. \]
Problem (Commutativity of disjunction and conjunction)
Use truth tables to prove the following equivalences.
| (i) | \( a\vee b\equiv b\vee a \) |
| (ii) | \( a\wedge b\equiv b\wedge a \) |
Problem (Associative laws of propositional logic)
Use truth tables to prove the following equivalences.
| (i) | \( a\vee(b\vee c)\equiv(a\vee b)\vee c \) |
| (ii) | \( a\wedge(b\wedge c)\equiv(a\wedge b)\wedge c \) |
Problem (Distributive laws of propositional logic)
Use truth tables to prove the following equivalences.
| (i) | \( a\vee(b\wedge c)\equiv(a\vee b)\wedge(a\vee c) \) |
| (ii) | \( a\wedge(b\vee c)\equiv(a\wedge b)\vee(a\wedge c) \) |
Problem (Merging rules for disjunction and conjunction)
Use truth tables to prove the following equivalences.
| (i) | \( a\equiv a\wedge(a\vee b) \) |
| (ii) | \( a\equiv a\vee(a\wedge b) \) |
Problem (de Morgan rules of propositional logic)
Use truth tables to prove the following equivalences.
| (i) | \( \neg(a\vee b)\equiv\neg a\wedge\neg b \) |
| (ii) | \( \neg(a\wedge b)\equiv\neg a\vee\neg b \) |
Problem (NAND as functionally complete operator)
The logical connectives \( \neg, \) \( \vee, \) \( \wedge, \) \( \to, \) and \( \leftrightarrow \) can be expressed using only the NAND operator, which we write shortly as \( a\,\bar\wedge\,b. \) Prove the following equivalences using truth tables.
| (i) | \( \neg a\equiv a\,\bar\wedge\,a \) |
| (ii) | \( a\vee b\equiv(a\,\bar\wedge\,a)\,\bar\wedge\,(b\,\bar\wedge\,b) \) |
| (iii) | \( a\wedge b\equiv(a\,\bar\wedge\,b)\,\bar\wedge\,(a\,\bar\wedge\,b) \) |
| (iv) | \( a\to b\equiv a\,\bar\wedge\,(b\,\bar\wedge\,b) \) |
Problem (NOR as functionally complete operator)
The logical connectives \( \neg, \) \( \vee, \) \( \wedge, \) \( \to, \) and \( \leftrightarrow \) can be expressed using only the NOR operator, which we write shortly as \( a\,\bar\vee\,b. \) Prove the following equivalences using truth tables.
| (i) | \( \neg a\equiv a\,\bar\vee\,a \) |
| (ii) | \( a\vee b\equiv(a\,\bar\vee\,b)\,\bar\vee\,(a\,\bar\vee\,b) \) |
| (iii) | \( a\wedge b\equiv(a\,\bar\vee\,a)\,\bar\vee\,(v\,\bar\wedge\,b) \) |
| (iv) | \( a\to b\equiv(a\,\bar\vee\,a)\,\bar\vee\,(b\,\var\vee\,b)\,\bar\vee\,b \) |
Problem (Examples of propositional tautologies I)
Proof, using truth tables, that the following formulas represent tautologies.
| (i) | \( a\vee(b\wedge\neg b)\to a \) |
| (ii) | \( a\wedge(b\vee\neg b)\to a \) |
Problem (Examples of propositional tautologies II)
Proof, using truth tables, that the following formulas represent tautologies.
| (i) | \( a\vee\neg a \) |
| (ii) | \( \neg(a\wedge\neg a) \) |
| (iii) | \( \neg(\neg a)\to a \) |
| (iv) | \( (a\to b)\to(\neg b\to\neg a) \) |
Problem (Examples of propositional tautologies III)
Proof, using truth tables, that the following formulas represent tautologies.
| (i) | \( (a\to b)\wedge a\to b \) |
| (ii) | \( (a\to b)\wedge\neg b\to\neg a \) |
| (iii) | \( (a\to b)\wedge(b\to c)\to(a\to c) \) |
Problem (Further tautologies)
The following rules are elements of the formal system for propositional logic which can be found in → R.E. Hodel chapter 3, section 3.1. Proof, using truth tables, that these rules represent tautologies.
| (i) | Contraction rule | \( a\vee a\to a \) |
| (ii) | Expansion rule | \( a\to b\vee a \) |
| (iii) | Cut rule | \( (a\vee b)\wedge(\neg a\vee c)\to(b\vee c) \) |
Problem (Tautologies of implication)
Proof, using truth tables, that the following rules represent tautologies.
| (i) | \( a\to((a\to b)\to b) \) |
| (ii) | \( a\to(b\to(a\to b)) \) |
| (iii) | \( \neg(a\to a)\to b \) |
| (iv) | \( \neg(a\to b)\to\neg b \) |
| (v) | \( \neg(a\to b)\to a \) |
Aufgabe (Tautologien und Kontradiktionen)
Beweisen Sie vermittels einer Wahrheitstabelle, dass die Negation einer Tautologie eine Kontradiktion darstellt.
Aufgabe (Äquivalenzen zum Satz vom ausgeschlossenen Dritten)
Beweisen Sie unter Verwendung der obigen aussagenlogischen Regeln und ohne Verwendung von Wahrheitstabellen, dass der Satz vom ausgeschlossenen Dritten \[ a\vee\neg a \] semantisch äquivalent ist zum Satz vom Widerspruch, zum Satz von der doppelten Verneinung und zur Kontraktionsregel, d.h. zu \[ \neg(a\wedge\neg a),\quad \neg(\neg a)\to a,\quad a\vee a\to a. \] Wie lautet die Negation dieser Regel?
Aufgabe (Negation aussagenlogischer Tautologien I)
Verifizieren Sie durch Anwenden der obigen Rechenregeln und ohne Wahrheitstabellen \[ \neg[a\to(a\vee b)]\equiv(a\wedge\neg a)\wedge\neg b. \] Warum handelt es sich bei dieser Negation um eine Kontradiktion?
Aufgabe (Negation aussagenlogischer Tautologien II)
Verifizieren Sie durch Anwenden der obigen Rechenregeln und ohne Wahrheitstabellen
| (i) | \( \neg[a\wedge(a\vee b)]\equiv(a\wedge\neg a)\wedge\neg b \) |
| (ii) | \( \neg[a\wedge(b\vee\neg b)\to a]\equiv(a\wedge\neg a)\wedge(b\vee\neg b) \) |
Warum handelt es sich bei diesen Negationen um Kontradiktionen?
Aufgabe (Negation aussagenlogischer Tautologien III)
Verifizieren Sie durch Anwenden der obigen Rechenregeln und ohne Wahrheitstabellen
| (i) | \( \neg[\neg(a\to a)\to b]\equiv(a\wedge\neg a)\wedge\neg b \) |
| (ii) | \( \neg[\neg(a\to b)\to\neg b]\equiv a\wedge(b\wedge\neg b) \) |
| (iii) | \( \neg[\neg(a\to b)\to\neg a]\equiv(a\wedge\neg a)\wedge\neg b \) |
Warum handelt es sich bei diesen Negationen um Kontradiktionen?