Propositional Syntax
- Propositional variables can be sentences or sentences of sentences
- Typicall binary, however can be extended to be multi-valued
\[ P_1,...,P_n\]
Logical Connectives
- There are three primitive logical connectives:
\[ \land\text{ - Logical conjunction (and)} \] \[ \lor\text{ - Logical disjunction (or)}\]
\[ \lnot\text{ - Logical negation (not)}\]
Derived Connectives
- Further connectives can be derived from the three primitive connectives:
\[ \implies\text{ - Logical Implication}\] \[ A\implies B\equiv \neg\alpha\lor\beta\]
\[ \Leftrightarrow\text{- Logical Equivalence}\]
\[ \alpha\Leftrightarrow (\alpha\implies\beta)\land(\beta\implies\alpha)\]
Multivalued Variables
- Propositional variables are typically binary, therefore we typically expect the following:
\[ \alpha = true,\quad\neg\alpha = false\] * However we can generalise to multivalued by specifying the value of the variables:
\[ A=\{a_1,a_2,a_3\},\quad B=\{b_1,b_2,b_3\}\] \[ A=a_1\implies B=b_1\]
Variable Instantiation
- Notation for variable instantiation:
- Variables are uppercase, \(A\)
- Instantiated variables are lowercase, \(a\)
- Cardinality (amount of possible values) is denoted \(|A|\)
- Sets of variables are boldface, \(\textbf{A} = \{A,B,C\}\)
- Number of possible instantiations of a set, \(\textbf{A}^\#=12\)
- Compatible instantiations, \(x\sim y\) (agree on values of all common variables)
Worlds
- To explore probabilities, we can consider ‘worlds’ where each variable outcome is known
- We consider all combinations of variables
- For binary variables, the amount of possible worlds is \(2^n\)
- \(w_i\models\alpha\) denotes that \(\alpha\) is true in world \(w_i\)
- The worlds where \(\alpha\) is true are called the models of \(\alpha\)
- Mods\((\alpha) = \{w:w\models\alpha\}\)
Worlds and Logical Properties
- Models:
\[ Mods(\alpha\land\beta)=Mods(\alpha)\cap Mods(\beta)\]
\[ Mods(\alpha\lor\beta)=Mods(\alpha)\cup Mods(\beta)\]
\[ Mods(\neg\alpha) = \overline{Mods(\alpha)}\] * \(\alpha\) is consistent iff there is atleast one world where \(\alpha\) is true:
\[ Mods(\alpha)\neq\emptyset\]
- \(\alpha\) is valid iff it is true at every world
\[ \models\alpha\]
- \(\alpha\) and \(\beta\) are equivalent iff they are true in the same set of worlds:
\[ Mods(\alpha) = Mods(\beta)\]
- \(\alpha\) and \(\beta\) are mutually exclusive if they are never true in the same world:
\[ Mods(\alpha)\cap Mods(\beta)=\emptyset\]
- \(\alpha\) and \(\beta\) are exhaustive iff each world satisifes at least one sentence:
\[ Mods(\alpha)\cup Mods(\beta)=\Omega\]
- \(\alpha\) implies \(\beta\) iff \(\beta\) is true whenever \(\alpha\) is true:
- \(Mods(\alpha)\) is a subset of \(Mods(\beta)\)
\[ Mods(\alpha)\subseteq Mods(\beta)\]
Equivalences/Schema
Reductions
Monotonicity
- An issue with propositional logic is monotonicity
- Learning knowledge cannot reduce the set of what is known
- Can only add to the knowledge base, therefore cannot disprove knowledge after learning new information