Classical propositional logic
A formula of propositional logic is in the conjunctive normal form (CNF) if it is a conjunction of (possibly many) disjunctions of (possibly many) propositinal variables and negated propositional variables. Eg., \((p_1\lor\lnot p_2\lor p_3)\land(p_2\lor p_4\lor \lnot p_5)\land(\lnot p_1\land p_2)\) is a CNF formula.
A formula of propositional logic is in \(k\)-CNF if it is in CNF and each disjunction has at most \(k\) disjuncts (variables or their negations). The formula given above is in 3-CNF, byt not in 2-CNF.
A formula of propositional logic is in the disjunctive normal form (DNF) if it is a disjunction of (possibly many) conjunctions of (possibly many) propositinal variables and negated propositional variables.
Exercise 1
Show that for each propositional formula \(\varphi\) there exists a propositional formula \(\psi\) in DNF, equivalent to \(\varphi\), i.e., \(\varphi\leftrightarrow\psi\) is a tautology.
Exercise 2
Show that for each propositional formula \(\varphi\) there exists a propositional formula \(\psi\) in CNF, equivalent to \(\varphi\), i.e., \(\varphi\leftrightarrow\psi\) is a tautology.
Exercise 3
Show that for each propositional formula \(\varphi\) in CNF there exists a propositional formula \(\psi\) in 3-CNF such that \(\psi\) is satisfiable if and only if \(\varphi\) is satisfiable.
Exercise 4
Give a polynomial time algorithm for the following decision problem:
Input: Propositional formula \(\varphi\) in DNF.
Question: Is \(\varphi\) satisfiable?
Exercise 5
Give a polynomial time algorithm for the following decision problem:
Input: Propositional formula \(\varphi\) in 2-CNF.
Question: Is \(\varphi\) satisfiable?
Exercise 6
We consider formulas built using connectives of conjunction and disjunction, only.
For such a formula \(\varphi\) let \(\hat{\varphi}\) denote its dualisation, i.e., the formula obtained from \(\varphi \) by replacing every occurrence of \(\wedge\) by \(\vee\) and every occurrence of \(\vee\) by \(\wedge\).
* Prove that \(\varphi\) is a tautology if and only if \(\lnot\hat{\varphi}\) is a tautology.
* Prove that \(\varphi\leftrightarrow\psi\) is a tautology if and only if \(\hat{\varphi}\leftrightarrow\hat{\psi}\) is a tautology.
* Propose a method to define dualisation for formulas contaning addtionally logical constants \(\bot\) and \(\top\), such that the above equivalences remain valid.
Exercise 7
Prove that for any function \(f:\{0,1\}^k\to\{0,1\}\) there exists a formula \(\varphi\) using only the connectives \(\to\) i \(\bot\) and variables from the set \(\{p_1,\ldots, p_k\}\) with the property that for any valuation \(\varrho\) the following equality holds:
\([[\varphi]]_\varrho = f(\varrho(p_1),\ldots, \varrho(p_k))\).
(In other words, the formula \(\varphi\) defines the function \(f\).)
Exercise 8
Consider an infinite set of lads, each of which has a finite number of fiancees. Moreover, for each \(k\in N\), any \(k\) lads has at least \(k\) fiancees. Demonstrate that it is possible to marry each lad with one of his fiancees, without commiting bigamy.
Exercise 9
Let \(k\) be a fixed natural number. Prove, using the compactness theorem, that if every finite subgraph of an infinite graph \(G=\langle V,E\rangle\) is \(k\)-collorable, then \(G\) itself is \(k\)-collorable, too.
Exercise 10
For the formula \(\gamma =\ r\leftrightarrow (p_1\lor p_2)\) the following equivalence holds: \(\varrho\models\gamma\) if and ony if \(\varrho(r)=\max(\varrho(p_1),\varrho(p_2))\).
Investigate whether there exists a set of formulas \(\Gamma\) such that \(\varrho\models\Gamma\) if and only if \(\varrho(r)=\max_{n\in\mathbb{N}}(\varrho(p_n))\).
Exercise 11
Is the sequent \(\{p,q\to p,\lnot q\}\vdash\{p,q\}\) provable in the Gentzen system for propositional logic?
Exercise 12
Decide if the following sequents are provable in the Gentzen system for propositional logic?
* \( (p\to q) \lor (q\to p)\)
* \((p\to ( q \to p)) \to p\)
Exercise 13
In the Gentzen system, the sequent \(\Gamma,p\vdash\Delta,p\) is an axiom, where \(p\) is a propositional variable. Prove that every sequent of the form \(\Gamma,\varphi\vdash\Delta,\varphi\) is provable in the Gentzen system. What can you assert about the size of this proof?
Three-valued propositional logics
Exercise 14
A logic \(L\) is called monotonic, if the conditions \(\Delta\models\varphi\) and \(\Gamma\supseteq\Delta\) imply \(\Gamma\models\varphi.\)
For a three-valued Sobociński logic we define that \(\Delta\models\varphi\), iff for every valuation of propositional variables into \(\{0,\frac12,1\}\), if the values of all sentences in \(\Delta\) are 1, then the value of \(\varphi\) is 1, too.
Is this logic monotonic?
Exercise 15
Answer the same question as in Exercise 14 for the logics of Heyting-Kleene-Łukasiewicz and Bochvar, as well as for the logic of lazy (short) Pascal evaluation.
Exercise 16
What is the computational complexity of the following decision problem:
Given: A formula \(\varphi\) of propositional logic.
Question: Is there a valuation \(\varrho\) of propositional variables into \(\{0,\frac12,1\}\) such that in the three-valued logic of Bochvar \([[\varphi]]_\varrho=1\)?
Intuitionistic propositional logic
Exercise 16
Prove the following formula in the Natural Deduction system for the intuitionistic logic
* \(p \to \neg \neg p\)
* \(\neg (p \lor q) \to\neg p \land\neg q\)
* \(\neg p \land\neg q \to\neg (p \lor q)\)
* \(\neg p \lor\neg q \to\neg (p \land q)\)
Exercise 17
Prove that the following formulas are not tautologies of the intuitionistic logic. Use Kripke models:
* \(((p\to q) \to p) \to p\)
* \(\neg (p \land q) \to (\neg p \lor\neg q)\)
Exercise 18
Prove inexpressibility of connectives in the intuitionistic logic:
* \(\lor\) can not be expressed using only \(\land\), \(\to\) and \(\bot\)
* \(\land\) can not be expressed using only \(\lor\), \(\to\) and \(\bot\)
* \(\to\) can not be expressed using only \(\lor\), \(\land\) and \(\bot\)