śr., 10/03/2012 - 11:34 — fmurlak
## Classical propositional logic

Hint

Hint

## Three-valued propositional logics

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

Use exercise 1.

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

It is allowed to use fresh propositional variables.

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

**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\)?

**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\)