Logic for Computer Scientists/Propositional Logic/Semantics

Definition 3 (Semantics of propositional logic)

For the semantics of our formal language of propositions we do not refer to a specific intended interpretation. Moreover we only are interested in truth values. We assume an initial assignment of truth values to atomic formulae and based on this, we define the truth value of more complex formulae. The set of truth values is the set $\{true,false\}$. An assignment for a set $D$ of atomic formulae is a function

${\mathcal {A}}|D$$\to \{true,false\}$. Let $E$ be the set of formulae containing $D$, i.e $E\supseteq D$ and exactly those formulae which can be constructed from $D$ according to the definition of the syntax. Then the extension of ${\mathcal {A}}$ on $E$, ${\mathcal {A}}_{E}|E\to \{true,false\}$, is given as:

• $A\in D$ : ${\mathcal {A}}_{E}(A)={\mathcal {A}}(A)$

• ${\mathcal {A}}_{E}((F\land G))={\begin{cases}\;\;\,true&{\text{if }}{\mathcal {A}}_{E}(F)=true{\text{ and }}{\mathcal {A}}_{E}(G)=true\\\;\;\,false&otherwise\end{cases}}$

• ${\mathcal {A}}_{E}((F\lor G))={\begin{cases}\;\;\,true&{\text{if }}{\mathcal {A}}_{E}(F)=true{\text{ or }}{\mathcal {A}}_{E}(G)=true\\\;\;\,false&otherwise\end{cases}}$

• ${\mathcal {A}}_{E}(\lnot F)={\begin{cases}\;\;\,true&{\text{if }}{\mathcal {A}}_{E}(F)=false\\\;\;\,false&otherwise\end{cases}}$

In the following we will omit the index $E$ to indicate the extension of an assignment ${\mathcal {A}}$. Note that this is the right place to name formulae of type $(F\land G)$ as conjunctions, formulae of type $(F\lor G)$ as disjunctions and formulae of type $\lnot F$ as negations.

The following is an example evaluation by means of the definition of ${\mathcal {A}}$: Assume as given ${\mathcal {A}}(A)=true,{\text{ }}{\mathcal {A}}(B)=true$ and ${\mathcal {A}}(C)=false$, then

${\mathcal {A}}(\lnot ((A\land B)\lor C))$

${\text{ }}={\begin{cases}\;\;\,true&{\text{ if }}{\mathcal {A}}((((A\land B))\lor C))=false\\\;\;\,false&\;otherwise\end{cases}}$

${\text{ }}={\begin{cases}\;\;\,false&{\text{ if }}{\mathcal {A}}((((A\land B))\lor C))=true\\\;\;\,true&\;otherwise\end{cases}}$

${\text{ }}={\begin{cases}\;\;\,false&{\text{ if }}{\mathcal {A}}((((A\land B))))=true{\text{ or }}A(C)=true\\\;\;\,true&\;otherwise\end{cases}}$

${\text{ }}={\begin{cases}\;\;\,false&{\text{ if }}{\mathcal {A}}((((A\land B))))=true\\\;\;\,true&\;otherwise\end{cases}}$

${\text{ }}={\begin{cases}\;\;\,false&{\text{ if }}{\mathcal {A}}(A)=true{\text{ and }}{\mathcal {A}}(B)=true\\\;\;\,true&\;otherwise\end{cases}}$

${\text{ }}=false$

Definition 4

Let ${\mathcal {A}}$ be an assignment and $F$ a formula. ${\mathcal {A}}$ is called assignment for $F$, if ${\mathcal {A}}$ is defined for every subformula of $F$. If ${\mathcal {A}}$ is an assignment for $F$ and ${\mathcal {A}}(F)=true$ we call ${\mathcal {A}}$ a model for $F$ and we write ${\mathcal {A}}\models F$ If ${\mathcal {A}}$ is an assignment for $F$ and ${\mathcal {A}}(F)=false$, we write ${\mathcal {A}}\nvDash F$.

A formula $F$ is called satisfiable, iff there is a model for $F$, otherwise $F$ is called unsatisfiable. $F$ is called valid (or a tautology) iff every assignment for $F$ is a model. We write $\models F$ rsp. $\nvDash F$.

Theorem 1

A formula $F$ is valid, iff $\lnot F$ is unsatisfiable.

Proof: $F$ is a tautology

iff every assignment for $F$ is a model for $F$

iff every assignment for $F$ (which is of course, also an assignment for $\lnot F$) is not a model for $\lnot F$

iff $\lnot F$ has no model

iff $\lnot F$ is unsatisfiable.

Definition 5 (Consequence)

A formula $G$ is called a consequence of the formulae $F_{1},\cdots ,F_{k}$, if for every assignment ${\mathcal {A}}$ for $G$ and $F_{1},\cdots ,F_{k}$ holds: if ${\mathcal {A}}$ is a model for $F_{1},\cdots ,F_{k}$, then ${\mathcal {A}}$ is a model for $G$. We write $\{F_{1},\cdots ,F_{k}\}\models G$.

The following theorem is a simple consequence from definitions:

Theorem 2

$G$ is called a consequence of the formulae $F_{1},\cdots ,F_{k}$,

iff $((\bigwedge _{i=1}^{k}~F_{i})\to G)$ is a tautologie

iff $((\bigwedge _{i=1}^{k}~F_{i})\land ~\lnot G)$ is unsatisfiable.

Obviously the validity of a formula depends only of the assignments for its atomic subformulae: If ${\mathcal {A}}$ and ${\mathcal {A}}'$ are assignments for $F$ and if they yield the same value for every occurring atomic subformulae, then ${\mathcal {A}}(F)={\mathcal {A}}'(F)$ holds. As a consequence we can state, that it suffices for a test of the validity of a formula $F$ to check the infinitely many assignments of its atomic subformulae. Such a check can be depicted easily in a tableau of the following form, where $F$ is an arbritrary formula, containing $n$ distinct atomic formulae ${\mathcal {A}}_{i}$.

	${\mathcal {A}}_{1}$	$\cdots$	${\mathcal {A}}_{n-1}$	${\mathcal {A}}_{n}$	$F$
${\mathcal {A}}_{1}$	false	$\cdots$	false	false	${\mathcal {A}}_{1}(F)$
${\mathcal {A}}_{2}$	false	$\cdots$	false	true	${\mathcal {A}}_{2}(F)$
${\mathcal {A}}_{2}n$	true	$\cdots$	true	true	${\mathcal {A}}_{n}(F)$

When applying this procedure it might me helpful to introduce intermediate results for subformulae, as done in the following example.

$A$	$B$	$\lnot A$	$A{\text{ }}\to {\text{ }}B$	($\lnot {\text{ }}A{\text{ }}\to {\text{ }}(A{\text{ }}\to {\text{ }}B$ ))
false	false	true	true	true
false	true	true	true	true
true	false	false	false	true
true	true	false	true	true

Note that we just have depicted an algorithm to check the validity of a formula. Assume the Formula contains $n$ atomic subformulae, then our just constructed tableaux contain $2^{n}$ lines. To estimate the costs for such an exponential algorithm, assume that the computation of one line takes 1 micro-second. Is $F$ contains only 100 atomic subformulae the computation of the tableau would take $2^{100}$ micro-seconds.

Truth Tables

The problem whether a propositional formula is satisfiable is called SAT and the corresponding tautology problem is called TAUT.

SAT is an NP-complete problem, and hence it is not known whether SAT is tractable or not. Whether TAUT is in NP is still an open problem. For TAUT we know, that it is in NP iff NP is closed under complementation. SAT and TAUT, both, play a prominent role in the study of complexity theory, in particular with respect to the question whether $P=NP$.

Problem

Problem 1 (Propositional)

Compute truth tables for the following formulae. Decide for each formula whether it is valid (a tautology), satisfiable or unsatisfiable.

1. $(A\land B)\land (B\to C)$
2. $(A\land B)\leftrightarrow (\lnot A\lor \lnot B)$
3. $(\lnot A\lor \lnot (\lnot B\lor A))\lor A$
4. $(A\to (B\land C))\leftrightarrow ((A\to B)\land (A\to C))$
5. $(A\lor (B\land A))\land ((C\lor \lnot C)\to \lnot A)$
6. $((C\lor B)\land (C\lor \lnot B))\land \lnot C$
7. $\lnot (\lnot A\lor \lnot (\lnot B\lor \lnot A))$
8. $(A\to (B\to A))$
9. $(A\lor (B\land A))\land ((C\lor \lnot C)\to \lnot A)$
10. $((A\lor \lnot B)\lor ((\lnot A\land \lnot C)\land B))\leftrightarrow ((A\lor \lnot C)\lor \lnot B)$
11. $\lnot (A\land \lnot (B\land \lnot C))$

Problem 2 (Propositional)

"What is the secret of your long life?" a 100-year old man was asked. He answered: "I apply the following diet rules very strictly: If I drink no wine at dinner then I have always fish. Whenever I take fish and wine for dinner, it is without garlic. If I have garlic or wine I avoid fish"

1. Formalize these rules with the help of propositional logic.
2. Try to simplify the advice of the 100-year old man.

Problem 3 (Propositional)

Define the following functions recursively by induction over the construction of propositional formulae:

1. $\alpha (F)$: Set of atomic formula in $F$
2. $\beta (F)$: Number of the binary junctors $\land$ and $\lor$ in $F$

Note: For

$F$ = $(\lnot (A\lor B)\lor C)$ $\land$ $((\lnot A\lor B)\land C)$

$\alpha (F)=\{A,B,C\}$ and $\beta (F)=5$ holds.

Problem 4 (Propositional)

Given the formulae $F_{n}$= $A_{1}$ ${\stackrel {\cdot }{\vee }}\cdots {\stackrel {\cdot }{\vee }}A_{n}$, in which $A_{1},\dots ,A_{n}$ are atomic formulae ($n\geq 1$) where ${\stackrel {\cdot }{\vee }}$ denotes exclusive or. Prove for all $n\in \mathbb {N}$: A suitable assignment ${\mathcal {A}}$ for $F_{n}$ is a model for $F_{n}$ (i.e. ${\mathcal {A}}\models F_{n}$) iff ${\mathcal {A}}(A_{i})=1$ halds for an odd number of ${\mathcal {A}}_{i}$ ($1\leq i\leq n$).

Problem 5 (Propositional)

In the following we investigate formulae, in which only atoms $A_{1},\dots ,A_{n}$ occur.

1. How many of such formulae with different truth tables exist at most?
2. Is there for every truth table a formula? If yes, please indicate a construction!

Problem 6 (Propositional)

If the colonel was not in the room during the murder then he cannot know the weapon of the murderer. The butler lies or he knows the murderer. If Lady Barntree is the murderer then the colonel was in the room during the murder or the butler lies. The butler knows the murderer or the colonel was not in the room during the murder. The policeman concludes that Lady Barntree is the murderer. Give propositional variables for every statement of the argumentation. Write the argumentation as a set $M$ of propositional formulae of the prerequisites and the conclusion as a propositional formula $F$.

Problem 7 (Propositional)

Formalize the following expressions and then simplify the corresponding formulae and the verbal propositions.

1. It is not true that his mother is English and his father French.
2. It is not true that he is studying physics but not mathematics.
3. It is not true that the wages are going down and the prices are going up.
4. It is not true that it is not cold or rainy.

Problem 8 (Propositional)

The professor proposes to make a new conception for the lunch in the University restaurant:

1. There must be bread with every lunch if there is no dessert.
2. If bread and dessert are served then is be no soup.
3. If soup is served then there is no bread.

Help the management to fulfill the wishes of the professor. For this

1. formalize the three propositions (as implications, disjunctions/conjunctions) and combine them into one logical formula.
2. Give a truth table for this logical formula. Is there a model for the formula?
3. Give a colloquial verbalization for the assignment.