Propositional logic

Propositional logic is a type of logic where variables can only take on true/false as values. The set of all propositional formulas is defined recursively:

• Base: every propositional variable is a propositional formula.
• If $A$ is a propositional formula, then so is $\neg A$.
• If $A,B$ are propositional formulas, then so are:
  • $A\wedge B$: conjunction
  • $A\vee B$: disjunction
  • $A\to B$: implication. Where $A$ is called the antecedent and $B$ is the consequence of the implication.
  • $A\leftrightarrow B$: bi-implication.

A truth assignment is a function $\tau$ from the propositional variables into the set of truth values $\{T,F\}$. We define: let $\tau$ be a truth assignment. The extension $\bar{\tau }$ of $\tau$ assigns either $T$ or $F$ to every formula and is defined as follows:

• If $A=x$, where $x$ is a variable, then $\bar{\tau }(A)=\tau (x)$.
• $\bar{\tau }(\neg A)=T⟺\bar{\tau }(A)=F$
• $\bar{\tau }(A\wedge B)=T$ iff ($\bar{\tau }(A)=T$ and $\bar{\tau }(B)=T$).
• $\bar{\tau }(A\vee B)=T$ iff ($\bar{\tau }(A)=T$ and $\bar{\tau }(B)=T$).
• $\bar{\tau }(A\to B)=F$ iff ($\bar{\tau }(A)=T$ and $\bar{\tau }(B)=F$).
  • When the antecedent is false, the implication is vacuously true. Intuitively, it means the proposition doesn’t really say anything.

A truth assignment $\tau$ satisfies a formula $A$ iff $\bar{\tau }(A)=T$. $\tau$ satisfies a set $\Phi$ of formulas iff $\tau$ satisfies all formulas in $\Phi$. A set $\Phi$ of formulas is satisfiable iff some truth assignment $\tau$ satisfies $\Phi$. Otherwise $\Phi$ is unsatisfiable.

A formula $A$ is a logical consequence of $\Phi$ (denoted by $\Phi \models A$) iff for every truth assignment $\tau$, if $\tau$ satisfies $\Phi$, then $\tau$ satisfies $A$.

Limitations

We are restricted to only Boolean variables in propositional language. Without non-Boolean variables, cross references between individuals in statements are impossible.

For example:

• $S$: a person has a sibling.
• $C$: a sibling has a child.
• $A$: a person is an aunt or an uncle.

$$S\wedge C\to A$$

However, the person in $S$ and $A$ are not related.

No quantifiers: to state a property for all (or some) members of the domain, we have to explicitly list them.