# Propositional Logic - Propositional variables representing statements that can be true or false - Use logical operators to build more complex statements - AND $(\wedge)$, OR $(\vee)$, NOT $(\neg)$, IF THEN $(\rightarrow), \ldots$ - All structure is translated to a Boolean setting ## Syntax - Take some (infinite) set $P$ of propositional variables - Often we use $P=\left\{p_{1}, p_{2}, \ldots\right\}$ - Propositional logic formulas are constructed as follows. - Each $p \in P$ is a formula. - If $\varphi$ is a formula, then $\neg \varphi$ is a formula too. - If $\varphi_{1}, \varphi_{2}$ are formulas, then so are $\left(\varphi_{1} \wedge \varphi_{2}\right),\left(\varphi_{1} \vee \varphi_{2}\right),\left(\varphi_{1} \rightarrow \varphi_{2}\right)$ and $\left(\varphi_{1} \leftrightarrow \varphi_{2}\right)$. - (We often omit brackets whenever convenient, unless it leads to confusion.) ## Semantics - Let $\varphi$ be a propositional logic formula that contains the variables $p_{1}, \ldots, p_{n}$. - We consider truth assignments $\alpha: P \rightarrow\{0,1\}$. - 0 represents false and 1 represents true. - Truth assignments can be seen as possible situations. - We define when a truth assignment $\alpha$ makes a formula $\varphi$ true, or when it satisfies $\varphi$, written: $\alpha \models \varphi$ - $\alpha \models p$ iff $\alpha(p)=1$ - $\alpha \models \varphi_{1} \wedge \varphi_{2}$ iff both $\alpha \models \varphi_{1}$ and $\alpha \models \varphi_{2}$ - $\alpha \models \varphi_{1} \vee \varphi_{2}$ iff $\alpha \models \varphi_{1}$ or $\alpha \models \varphi_{2}$ (or both) - $\alpha \models \neg \varphi$ iff $\alpha \not \models \varphi$ - $\alpha \models \varphi_{1} \rightarrow \varphi_{2}$ iff $\alpha \models\left(\neg \varphi_{1}\right) \vee \varphi_{2}$ - $\alpha \models \varphi_{1} \leftrightarrow \varphi_{2}$ iff $\alpha \models\left(\varphi_{1} \rightarrow \varphi_{2}\right) \wedge\left(\varphi_{2} \rightarrow \varphi_{1}\right)$ ## Conjunctive normal form (CNF) - It is often useful to consider only formulas of a particular (normal) form - A CNF formula is the conjunction $(\wedge)$ of several clauses - A literal is a propositional variable $p$ or the negation $\neg p$ of a variable - A clause is the disjunction ( $\vee$ ) of several literals - For example: - $\left(p_{1} \vee \neg p_{2}\right) \wedge\left(p_{1} \vee p_{2}\right) \wedge\left(\neg p_{1} \vee p_{3} \vee \neg p_{4}\right)$ ## Reasoning tasks - Some typical reasoning tasks are: - Satisfiability: - Given a formula $\varphi$, does there exist a truth assignment $\alpha$ that satisfies $\varphi ?$ - Entailment: - Given two formulas $\varphi_{1}, \varphi_{2}$, does it hold that $\varphi_{1}$ entails $\varphi_{2}$, written $\varphi_{1} \models \varphi_{2}$ ? - $\varphi_{1} \models \varphi_{2}$ holds iff for all assignments $\alpha$ such that $\alpha \models \varphi_{1}$ it also holds that $\alpha \models \varphi_{2} .$ - (Intuitively: if one assumes that $\varphi_{1}$ is true, then $\varphi_{2}$ must also be true.) - Entailment can be reduced to unsatisfiability: - $\varphi_{1} \models \varphi_{2}$ if and only if $\varphi_{1} \wedge \neg \varphi_{2}$ is not satisfiable - Satisfiability can be reduced to non-entailment: - $\varphi$ is satisfiable if and only if $\varphi \not \models\left(p_{1} \wedge \neg p_{1}\right)$ ### A first (naive) algorithm - This interreducibility means that with an algorithm for satisfiability, we can perform both reasoning tasks. - A first (very naive) algorithm to solve satisfiability: - Let $p_{1}, \ldots, p_{n}$ be the variables appearing in $\varphi$. - Iterate over all truth assignments $\alpha:\left\{p_{1}, \ldots, p_{n}\right\} \rightarrow\{0,1\}$. - For each, check whether $\alpha \models \varphi$. If so, answer "yes." - If for no $\alpha$ this check passed, answer "no." --- ## References