Definition. Syntax [0005]

November 22, 2025

Using BNF notation, the syntax of propositional logic can be defined as follows:

Context

VU-VFS-2025. Lecture 1 - Propositional Logic [0004]

November 22, 2025

Syntax

November 22, 2025

Definition. Syntax [0005]

November 22, 2025

Using BNF notation, the syntax of propositional logic can be defined as follows:

Quiz. Evaluating Syntax [0006]

November 22, 2025

Is \(p\) an atom?
Is \(p\) a literal?
Is \(p\) a formula?
What about \(\neg p\)?
What about \(\neg \neg p\)?

Solution.

November 22, 2025

Yes, \(p\) is an atom.
Yes, \(p\) is a literal. Literals are either atoms or negated atoms, and since \(p\) is an atom, it is also a literal.
Yes, \(p\) is a formula. Formulas can be literals, and since \(p\) is a literal, it is also a formula.
\(\neg p\) is not an atom, but it is a literal (as it is a negated atom) and therefore also a formula.
\(\neg \neg p\) is a formula, since the inner negation \(\neg p\) is a literal and any additional negation applied promotes it to a formula. In other words only negated atoms are literals but negated literals are formulas. This is especially important when we later discuss Negation Normal Form (NNF).

Semantics & Intepretations

November 22, 2025

Definition. Semantics [0007]

November 22, 2025

We can define the semantic inference rules for propositional logic formulas under interpretations as follows inductively, starting with the base cases:

Moving on to the inductive case we have

Similarly, the rules for when an interpretation does not satisfy a formula are as follows:

Definition. Interpretation [0008]

November 22, 2025

We define an interpretation as a function which maps propositional variables in a formula to truth values, so formally

\[ I : \texttt {Var} \to \{\top , \bot \} \]

We can evaluate a formula under an interpretation \(I\) by substituting each propositional variable with its corresponding truth value given by \(I\). Naturally under different kinds of interpretations formulas can evaluate to different truth values. We can create a classifcation of formulas based on how many interpretations evaluate them to true or false.

satisfiable: A formula is satisfiable if there exists at least one interpretation under which it evaluates to true.
unsatisfying: A formula is unsatisfying if there exists at least one interpretation under which it evaluates to false.
tautology: A formula is a tautology if it evaluates to true under every possible interpretation.
contradiction: A formula is a contradiction if it evaluates to false under every possible interpretation.
contingent: A formula is contingent if it is satisfiable and unsatisfying, i.e., there exists at least one interpretation under which it evaluates to true and at least one interpretation under which it evaluates to false.

Quiz. Evaluating PL Formulae [0009]

November 22, 2025

Consider the formula \( F \triangleq (\neg p \land q) \) and interpretation \( I \triangleq \{p \to \top , q \to \bot \} \) Which of the following is true

\(I \models F\)
\(I \nvDash F\)

What about the formula \[ (p \land q) \to (\neg p \lor q) \] under the same interpretation?

Solution.

November 22, 2025

Theres two main ways you can usually approach questions like this, the more drawn out operational way and then just going by observation more or less. Starting out with the more pedantic approach we can try to construct a proof tree for the formula under the given interpretation. So considering the first formula we have:

So we can see that the interpretation does not satisfy the formula. In other words for this assignment the formula does not hold true. Given that this is a somewhat simple formula we could also just see this by observation, i.e.

\[ \underbrace {\neg p}_{\texttt {False}} \land \underbrace {q}_{\texttt {False}} \equiv \bot \]

For the second formula lets just go with the simpler approach again, so we have

So in this case the formula is satisfied by the interpretation.

Quiz. Evaluating sat/unsat/valid [000a]

November 22, 2025

Are the following formulas sat., unsat., or valid?

\((p\land q) \to \neg p\)
\((p \land q) \to (p \lor \neg q)\)
\((p \to (q \to r)) \land \neg ((p \land q) \to r)\)

Solution.

November 22, 2025

As a reminder lets recap the definitions:

A formula is satisfiable if there exists at least one combination of true/false assignments to its variables that makes the formula true.
A formula is unsatisfiable if there is no combination of true/false assignments to its variables that makes the formula true (i.e., it is always false).
A formula is valid (or a tautology) if it is true under all possible combinations of true/false assignments to its variables.

Now we can analyze each formula:

For the lhs to be true both p and q must be true. However, if p is true then \(\neg p\) is false, making the implication false. If p is false then the implication is vacuously true regardless of what we set q to. Thus, this formula is satisfiable (e.g., when p is false) but not valid (e.g., when p and q are true).
If both p and q are true then the lhs is true and so is the rhs by virtue of p being true. If p is false then the implication is vacuously true regardless of q. If q is false then the rhs is true regardless of p. Thus, this formula is valid as it is true for all combinations of truth values for p and q.
The first part \((p \to (q \to r))\) is true unless p is true and either q or r is false. The second part \(\neg ((p \land q) \to r)\) is true when p and q are true but r is false. Thus we can satisfy the entire formula by setting p and q to true and r to false. However, if we set p to false then the first part is vacuously true, but the second part becomes false. Thus, this formula is falsifiable (e.g., when p and q are true and r is false) but not valid (e.g., when p is false).

If you want to be absolutely sure about these kinds of questions constructing truth tables is always a good idea, albeit a bit tedious for formulas with many variables so just doing a bit of analysis like above is usually sufficient