192.033 Logic and Reasoning in Computer Science

Exercise Sheets

Exercise Sheet 1

Exercise Problem 1.1

Instruction

Are the following statements true? Provide either a proof or a countermodel.

1. if $A\models B$ then $\neg A\models B$
2. if $A\models B$ and $A\wedge B\models C$ then $A\models C$
3. if $A\vee B\models A\wedge B$ then $A\equiv B$

Counterexample for 1.) $A:=p$ and $B:=p\vee q$. Then:

Choose

$$A\models B\equiv p\models p\vee q$$

Trivially, $A\models B$ is true given that $p=\top$ also makes $p\vee q=\top$.

However, $\neg A\models B$ is false, because if $p=\perp$ and $q=\perp$, then $\neg A$ is true while $B$ is false. There’s essentially another piece of information, namely $q$, that needs to be considered.

Proof for 2.) $v$ be an arbitrary interpretation that satisfies $A$, i.e.:

Let

$$v(A)=\top$$

Since $A\models B$, it follows that

$$v(B)=\top$$

Hence, applying $v$ recursively on all atoms:

$$v(A)\wedge v(B)=\top \wedge \top =\top$$

Now, consider $A\wedge B\models C$. Since $v(A)\wedge v(B)$ evaluates to true, we get $v(C)=\top$.

Therefore, for every interpretation $v$, if $v(A)=1$, then $v(C)=1$, i.e.:

$$A\models C$$

Proof for 3.) $v$ be an arbitrary interpretation. Assume that $v(A)=\top$. Then:

Let

$$v(A\vee B)=\top$$

Since $A\vee B\models A\wedge B$, it follows that:

$$v(A\wedge B)=\top$$

Hence $v(B)=\top$, so $A\models B$.

Symmetrically, we can assume that $v(B)=\top$, then:

$$v(A\vee B)=\top$$

Since $A\vee B\models A\wedge B$, it follows that:

$$v(A\wedge B=\top )$$

Hence $v(A)=\top$, so $B\models A$.

We have $A\models B$ and $B\models A$. Hence, there is no interpretation that makes one of them true and the other false, so we cannot distinguish them semantically. Therefore:

$$A\equiv B$$

Exercise Problem 1.2

Instruction

Prove or disprove the correctness of the following reasoning using tableaux:

1. I can bake the cake only if I buy the ingredients today.
2. I can go to the gym only if I finish my homework early.
3. I cannot both buy the ingredients and finish homework early.

Therefore, either I will not bake the cake or I will not go to the gym.

Solution

Formalise the atoms of the statements from above as follows:

• $c$: I will bake the cake.
• $i$: I will buy the ingredients today.
• $g$: I will go to the gym.
• $h$: I will finish my homework early.

Next, we formalise the premises themselves:

1. $c⟹i$
2. $g⟹h$
3. $\neg (i\wedge h)$

Then, the conclusion is:

$$\neg c\vee \neg g$$

So, in sequent notation, we want to prove:

$$c⟹i,g⟹h,\neg (i\wedge h)\models \neg c\vee \neg g$$

todo

Exercise Problem 1.3

The gold is not here 5. Box 2 The gold is not here 6. Box 3 The gold is in Box 2 Only one message is true; the other two are false. Which box has the gold?

Three boxes are presented to you. One contains gold, the other two are empty. Each box has imprinted on it a clue as to its contents; the clues are:
4. Box 1

Exercise Problem 1.4

$A$ be a propositional formula with $n\ge 1$ propositional variables such that:

Let

• $A$ is not a propositional atom, and
• $A$ is built from propositional atoms using only $\neg$ and $\leftrightarrow$
  How many branches does a splitting tree of $A$ have? Provide a sufficiently detailed explanation of your answer.

Exercise Problem 1.5

Instruction

Consider the formula:

$$(p\to (q\to r))\wedge \neg ((\neg q\vee r)\wedge \neg p)$$

Find a formula that is equivalent to the above formula and is shortest in size. Justify your answer.

Exercise Problem 1.6

Instruction

Draw the parse tree of the following formula:

$$r\wedge \neg p\wedge q\to ((p\leftrightarrow \neg q)\to r)$$

List all subformulas with negative polarity in the formula above.

Exercise Problem 1.7

Instruction

Consider the formula:

$$(\neg p\to \neg r)\wedge ((r\wedge q)\to (p\leftrightarrow q))$$

1. Which atoms are pure in the above formula?
2. Compute a clausal normal form $C$ of the above formula by applying the CNF transformation algorithm with naming and optimisations based on polarities of the subformulas.
3. Decide the satisfiability of the computed CNF formula $C$ by applying the dDPLL method to $C$. If $C$ is satisfiable, give an interpretation which satisfies it.

Exercise Problem 1.8

$((\neg p\to q)\to p)\to \neg p$ using only the pure atom rule

Find a model of the formula

Exercise Problem 1.9

Instruction

Apply the standard CNF transformation algorithm and the definitional transformation algorithm (both the non-optimised and optimised versions) to the following formula:

$$\neg ((p\to q)\leftrightarrow (\neg q\to \neg p))$$

Exercise Problem 1.10

$S$ be a set of formulas. Let $B$ a formula occurring only positively in $S$. Consider a Boolean variable $n$ not occurring in $S$, nor in $B$. Let $S^{\prime }$ be the set of formulas obtained from $S$ by replacing $B$ in $S$ by $n$. Show that $S$ is satisfiable if and only if so is the set of formulas $S^{\prime }\cup \{n\leftrightarrow B\}$.

Let

$$\neg ((p\to q)\leftrightarrow (\neg q\to \neg p))$$