\documentstyle[12pt,twoside,amssymb]{article}
\input{/a/class/6.042/spring95/macros-course}

\input{mk-macros}

\begin{document}

\lecnotes{March 14, 1995}{10}



\medskip

{\bf Reading:} Section 6 of Truss.

\section{Propositional Logic}

A {\em propositional variable} (also called a {\em boolean} variable) is one
which takes the values $\{\T,\F\}$ (True or False). Examples are ``God
exists'', ``Joe is alive'', ``2 is even''. In propositional logic we don't look
at the meaning that the variable may or may not have. For us, the variable
``God exists'' has the same significance as any other propositional variable
$p$ in that it can only take the values true or false. Therefore, we will
denote propositional variables by $p_i$ for some $i\in\naturals$.

In propositional logic we also work with {\em connectives} (or {\em boolean
operations}) to form new expressions from the propositional variables. The most
common connectives are $\lor$ ({\em or}), $\land$ ({\em and}), $\rightarrow$
({\em implies}), $\leftrightarrow$ ({\em iff}), $\neg$ ({\em not}) but one can
``invent'' new connectives at will. With these connectives one can form {\em
propositional sentences} (or {\em formulas}) always making sure to use
parenthesis to dispense of any ambiguity.

\begin{examples}
\item $p_1\lor\neg p_2$
\item $p_1\rightarrow(p_2\rightarrow p_3)$
\item $(\neg(p_1\land p_2))\leftrightarrow (\neg p_1\lor\neg p_2)$
\item $p_1\leftrightarrow\neg p_1$
\end{examples} 

An {\em assignment} (or {\em interpretation}) is a mapping which assigns to
each variable a value from $\{\T,\F\}$. Of course, we only have to assign a
value to those variables that appear in some sentence in consideration. Such an
assignment can be extended so that it assigns values to sentences. This is done
by induction on the structure of the sentence using the following table:

\begin{center}
\begin{tabular}{cc|c|c|c|c|c}
$A$  &  $B$  &  $A\lor B$  &  $A\land B$  & $A\rightarrow B$  &
$A\leftrightarrow B$  &  $\neg A$  \\  \hline
F & F & F & F & T & T & T \\
F & T & T & F & T & F & T \\
T & F & T & F & F & F & F \\
T & T & T & T & T & T & F
\end{tabular}
\end{center} 

\exm
If $p_1=p_2=\T$ and $p_3=\F$ then the first sentence above gets
the value T, the second gets F, the third gets T and the fourth gets F.
\eexm

A {\em satisfying} assignment for a sentence $A$ is one which gives $A$ the
value T. A sentence $A$ is called a {\em tautology} (or {\em valid}) if every
assignment is satisfying. A sentence is {\em satisfiable} if it has at least
one satisfying assignment. A sentence is {\em contradictory} (or {\em
unsatisfiable}) if it has no satisfying assignments. 

\exm
The first 2 sentences above are satisfiable, the third is a tautology and the
fourth is contradictory.
\eexm

Clearly, if $A$ is a tautology then $\neg A$ is contradictory. We write
$\models A$ if $A$ is a tautology. This means that $A$ is true under all
interpretations (or assignments).

\section{Truth tables}

Consider a sentence $A$ with $n$ variables. Each of the $2^n$ assignments of
the variables gives $A$ a truth value. The {\em truth table} of $A$ is a vector
of size $2^n$, indexed by the different assignments, and giving the values that
each assignment gives to $A$. 

\exm
The truth table of the first sentence above is
\begin{center}
\begin{tabular}{cc|c}
$p_1$  &  $p_2$  & $p_1\lor\neg p_2$ \\ \hline
F  & F &  T \\
F  & T &  F \\
T  & F & T \\
T & T & T
\end{tabular}
\end{center}
\eexm

There are $2^{2^n}$ different truth tables of sentences with $n$ variables.
Therefore, there are only so many ``different'' sentences on $n$ variables,
even though there is an infinite (but countable) number of sentences. We say
that two sentences $A$ and $B$ are {\em logically equivalent} ($A\equiv B$) if
they share the same truth table.

\exm
$p\rightarrow q\equiv\neg p\lor q$.
\eexm

A sentence $A$ is a tautology iff every entry in its truth table is T.
Similarly, a sentence $A$ is satisfiable iff at least one entry in its truth
table is T.

\section{Normal forms}

We have said that the set of all sentences on $n$ variables can be partitioned
into $2^{2^n}$ equivalence classes (those defined by logical equivalence). It
could be nice to have a representative from each class. That is, it could be
nice if we could {\em standardize} sentences into {\em normal forms}. There are
two common normal forms, the {\em disjunctive normal form} and the {\em
conjunctive normal form}.

First some definitions. We assume that the sentence uses the variables
$p_1,\cdots,p_n$. A {\em literal} is a sentence of the form $p_i$ or $\neg
p_i$. A {\em term} is an $\land$ of literals. A {\em clause} is an $\lor$ of
literals.

\begin{examples}
\item $p_1\land \neg p_2\land p_3$ is a term.
\item $\neg p_1\lor p_3$ is a clause.
\end{examples}

A sentence is in {\em disjunctive normal form} (DNF) if it is an $\lor$ of
terms.  A sentence is in {\em conjunctive normal form} (CNF) if it is an $\land$
of clauses.

\begin{examples}
\item $(p_1\land p_2)\lor(p_2\land\neg p_3)$ is in DNF.
\item $(p_1\lor p_3)\land(p_2\lor\neg p_3)$ is in CNF.
\end{examples}

We now show that any sentence $A$ is logically equivalent to one in DNF and to
one in CNF. Let us start with the DNF. 

First, we claim that for every assignment $\sigma$, there is a term $t_\sigma$
such that $\sigma$ is the only satisfying assignment of $t_\sigma$. Indeed, we
can take $t_\sigma=q_1\land\cdots\land q_n$ where $q_i$ equals $p_i$ or $\neg
p_i$ depending on whether $\sigma$ assigns $p_i$ the value T or F.

\exm
If there are 3 variables and $\sigma=(T,F,F)$ then $t_\sigma= p_1\land\neg
p_2\land\neg p_3$.
\eexm

To get a DNF for $A$ we take the $\lor$ of all the terms corresponding to the
satisfying assignments of $A$. It is clear that this DNF is logically
equivalent to $A$ because, by construction, it has the same truth table.

\exm
Consider $A=((p_2\rightarrow p_3)\rightarrow p_1)\land p_2$. Its only
satisfying assignments are (F,T,F), (T,T,F) and (T,T,T). Therefore, its DNF is
$(\neg p_1\land p_2\land\neg p_3)\lor(p_1\land p_2\land\neg p_3)\lor(p_1\land
p_2\land p_3)$. 
\eexm

\exr Show that any sentence is logically equivalent to one in CNF. {\em Hint:}
For any assignment $\sigma$ giving $A$ the value F, there is a clause
$C_\sigma$ that is satisfied by every assignment other than $\sigma$. The CNF
is then the $\land$ of all the clauses corresponding to all the falsifying
assignments.
\eexr

\section{Universal bases}

As a corollary to the existence of DNFs, we get that any sentence $A$ is
equivalent to one which uses only connectives from $\{\land,\lor,\neg\}$. We
therefore say that $\{\land,\lor,\neg\}$ is a {\em complete} basis of connectives. We
will show now that there are other complete bases.

\thm
The set $\{\land,\neg\}$ constitutes a complete basis.
\ethm
\pf
We have to show that we can ``simulate'' the basis $\{\land,\lor,\neg\}$ using
only connectives from $\{\land,\neg\}$. The only problematic connective is
$\lor$.  But $A\lor B\equiv\neg(\neg A\land\neg B)$.
\epf

\exr
Show that the connective {\em nand} ($\bar\land$) defined by $A\bar\land
B\equiv\neg(A\land B)$ constitutes a complete basis.
\eexr

\section{The algebra of $\{\land,\lor,\neg\}$}

The connectives in $\{\land,\lor,\neg\}$ form what is called a {\em Boolean
algebra} (see section 5.3 of Truss). That is, they obey a set of axioms which
are common enough to warrant a name. The axioms are:

\begin{enumerate}
\item $\land$ and $\lor$ are commutative, associative and distributive.
\item $x\land x \equiv x\lor x\equiv x$. {\em Idempotent} laws.
\item $\neg(x\land y)\equiv\neg x\lor\neg y$ and $\neg(x\lor y)\equiv\neg
x\land\neg y$. {\em De Morgan's} laws.
\item $\neg\neg x\equiv x$. {\em Double negation} rule.
\item $x\lor\neg x\equiv\T$, $x\land\neg x\equiv\F$.
\item $x\lor\T\equiv\T$, $x\lor\F\equiv x$, $x\land\T\equiv x$, 
$x\land\F\equiv\F$.
\end{enumerate} 

\exm
The operations $\{\cup,\cap,\cdot^c\}$ as applied to sets constitute a boolean
algebra. What are the equivalents to T and F?
\eexm

These axioms can be verified by looking at the truth tables. We can use these
axioms to manipulate sentences. 

\exm
We show that $x\lor(\neg x\land y)\equiv x\lor y$. Indeed, 

\begin{eqnarray*}
x\lor y & \equiv & x\lor((x\lor\neg x)\land y) \\
        & \equiv & x\lor (x\land y)\lor (\neg x\land y) \\
	&  \equiv & (x\land\T)\lor (x\land y)\lor (\neg x\land y) \\
	& \equiv & (x\land(\T\lor y))\lor (\neg x\land y) \\
	& \equiv  & (x\land\T)\lor (\neg x\land y) \\
	& \equiv & x\lor(\neg x\land y)
\end{eqnarray*}
\eexm

\section{Formal proofs and natural deduction}

We've discussed the fact that one can prove that a sentence is a tautology by
looking at its truth table. This does not capture the way we reason. A more
natural method, which resembles more the way we think, is  {\em Natural
Deduction}. 

Natural deduction has many versions. Each version is characterized by a set of
{\em axioms} and a set of {\em deduction rules}. Just like we can work with
different sets of connectives, we can use different sets of axioms and
deduction rules. Of course, we want to work with a set that will be as powerful
as any other. Here, we are going to define such a version.

What we want to capture is the intuition that a proof is a {\em finite}
sequence of {\em steps} such that each step is either an axiom, or a new
assumption (which has to be proven at a later time) or follows from previous
axioms and assumptions by using a deduction rule.

Recall that we wrote $\models A$ if $A$ is a tautology; that is, if $A$ is true
under all possible interpretations (or assignments). Similarly, if $\Gamma$ is
a set of sentences, we write $\Gamma\models A$ if $A$ is true under all
assignments that make all the sentences in $\Gamma$ true. That is,  under the
assumption that all  sentences in $\Gamma$ are true, $A$ is also true.

In our deduction system, we are not going to use any axioms. Given a set
$\Lambda$ of sentences, we write $\Lambda\vdash A$ if $A$ can be {\em proved}
using as assumptions the sentences in $\Lambda$ by using the deduction rules.
The following is the set of deduction rules that we are going to use:

\begin{enumerate}
\item If $\Lambda\cup\{\psi\}\vdash\F$ then $\Lambda\vdash\neg\psi$. {\em Proof
by contradiction}.
\item If $\Lambda\vdash\psi$ and $\Lambda\vdash\neg\psi$ then
$\Lambda\vdash\F$.
\item If $\Lambda\cup\{\psi\}\vdash\varphi$ then
$\Lambda\vdash(\psi\rightarrow\varphi)$.
\item If $\Lambda\vdash\psi$ and $\Lambda\vdash(\psi\rightarrow\varphi)$ then
$\Lambda\vdash\varphi$. {\em Modus Ponens}.
\item If $\Lambda\vdash\psi$ and $\Lambda\vdash\varphi$ then
$\Lambda\vdash(\psi\land\varphi)$.
\item If $\Lambda\vdash\psi\land\varphi$ then $\Lambda\vdash\psi$.
\item If $\Lambda\vdash\psi$ then $\Lambda\vdash\psi\lor\varphi$.
\item If $\Lambda\cup\{\psi\}\vdash\chi$ and $\Lambda\cup\{\varphi\}\vdash\chi$
and $\Lambda\vdash(\psi\lor\varphi)$ then $\Lambda\vdash\chi$.
\item If $\Lambda\vdash\F$ then $\Lambda\vdash\psi$. {\em From a contradiction
we can infer anything}.
\item If $\Lambda\vdash\psi$ then $\Lambda\cup\{\varphi\}\vdash\psi$.
\item If $\Lambda\vdash\psi$ and $\varphi$ follows from $\psi$ by using one of
the axioms of boolean algebra, then $\Lambda\vdash\varphi$.
\end{enumerate}

Given a set of axioms and deduction rules, a {\em proof} for a statement $A$
from the assumptions $\Gamma$ is a sequence of steps
$B_1,\cdots,B_k=\Gamma\vdash A$ such that each $B_i$ is of the form
$\Lambda\vdash\psi$ for some $\Lambda$ and $\psi$  such that either
$\psi=\T$ or $\psi\in\Lambda$, or it can be derived from previous sentences
using one of the deduction rules.

\exm
We show that $\{A\rightarrow(B\rightarrow C),A\land B\}\vdash C$. Indeed,
\begin{enumerate}
\item $\{A\rightarrow(B\rightarrow C),A\land B\}\vdash A\land B$ \hfill
$\psi\in\Ga$. 
\item $\{A\rightarrow(B\rightarrow C),A\land B\}\vdash A$ \hfill from rule 6
and step 1.
\item $\{A\rightarrow(B\rightarrow C),A\land B\}\vdash
A\rightarrow(B\rightarrow C)$ \hfill $\psi\in\Ga$.  
\item $\{A\rightarrow(B\rightarrow C),A\land 
B\}\vdash B\rightarrow C$ \hfill from rule 4.  
\item $\{A\rightarrow(B\rightarrow C),A\land B\}\vdash B$ \hfill from rule 6
and step 1.
\item $\{A\rightarrow(B\rightarrow C),A\land B\}\vdash C$ \hfill from rule 4.
\end{enumerate} 
\eexm 

\section{Soundness \& Completeness}

We now address the issue of whether this system is any good. We say that a set
of rules is {\em sound} if it can  prove only true statements. That is, if $$
\Gamma\vdash A \hbox{  implies  } \Gamma\models A
$$
Conversely, we say that the set of rules is {\em complete} if it can prove
every true statement. That is, if
$$
\Gamma\models A \hbox{  implies  } \Gamma\vdash A
$$

\thm
The system is sound. 
\ethm

\pf[sketch]
We will show that if $\Gamma\vdash A$ then $\Gamma\models A$. We will do so
by induction on the number $k$ of steps of the proof. 

\noindent
{\em Base case:} If $k=1$ then either $A=\T$ or $A\in\Gamma$. In either case,
$\Gamma\models A$. \\
{\em Induction step:} If $A=\T$ or $A\in\Gamma$ then, as before, $\Gamma\models
A$. Otherwise, $\Gamma\vdash A$ follows using one of the deduction rules. We
have to prove that, if a rule of the form $\Lambda\vdash\psi$ implies
$\Sigma\vdash\varphi$ was used, then $\Lambda\models\psi$ implies
$\Sigma\models\varphi$. Then the proof will follow by induction. We will prove
this for only one of the rules (the others can be done in a similar way). Lets
do rule 3:

Suppose that $\Lambda\cup\{\psi\}\models\varphi$. That is, any assignment that
makes all the sentences in $\Lambda$ and $\psi$ true makes $\varphi$ true. Take
an assignment $\sigma$ that makes all the sentences in $\Lambda$ true. If
$\sigma$ also makes $\psi$ true then, by assumption, it also makes $\varphi$
true so that it makes $\psi\rightarrow\varphi$ true. If $\sigma$ makes
$\psi$ false it vacuously makes $\psi\rightarrow\varphi$ true. Therefore,
$\Lambda\models\psi\rightarrow\varphi$.
\epf

\thm
The system is complete.
\ethm

\pf
Not here.
\epf

It is important to note that the previous two theorems hold even in the
case where the set of propositional variables is countable and when $\Gamma$
itself is countable. For example, the proof given for the first theorem holds
also for this case.

The next theorem is very useful and follows from the fact that proofs are
finite. A {\em model} for a set $\Gamma$ of sentences is an assignment that
satisfies every sentence in $\Gamma$.

\thm[Compactness]
Let $\Gamma$ be any set. Then $\Gamma$ has a model iff any finite subset of
$\Gamma$ has a model.
\ethm

\pf
If $\Gamma$ has a model then clearly any finite subset of it has a model.
Conversely, if $\Gamma$ has no model then $\Gamma\models\F$ holds. By
completeness, $\Gamma\vdash\F$. But the proof is finite and, therefore, it only
uses as assumptions a finite subset $\Gamma_0\subseteq\Gamma$. Hence
$\Gamma_0\vdash\F$. Now by soundness, $\Gamma_0\models\F$ which means that
$\Gamma_0$ does not have a model.
\epf

\end{document} 
