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