Consider the formula P ∧ ¬P. Under propositional semantics, this formula is:
ASatisfiable but not valid
BValid but not satisfiable
CNeither satisfiable nor valid
DBoth satisfiable and valid
P ∧ ¬P is a contradiction: for any valuation, exactly one of P and ¬P is false, so the conjunction is always false. It is not satisfiable (no valuation makes it true) and therefore certainly not valid (which would require truth under all valuations). Options A and D require at least one satisfying valuation, which does not exist. Option B is impossible — validity implies satisfiability.
Question 2 True / False
A formula that is true under nearly every possible valuation is called satisfiable.
TTrue
FFalse
Answer: False
A formula true under every valuation is called valid (or a tautology). Satisfiable means only that there exists at least one valuation making it true. Every valid formula is satisfiable (if it is true under all valuations, it is certainly true under some), but not every satisfiable formula is valid. For example, P is satisfiable (true when v(P) = true) but not valid (false when v(P) = false).
Question 3 Short Answer
Using compositionality, evaluate the formula (P → Q) ∧ ¬R under the valuation v(P) = true, v(Q) = false, v(R) = false. What is the truth value, and how does compositionality determine it step by step?
Think about your answer, then reveal below.
Model answer: The formula is false. Step 1: v(¬R) = ¬false = true. Step 2: v(P → Q) = v(¬P ∨ Q) = false (since P is true and Q is false, the implication is false). Step 3: v((P → Q) ∧ ¬R) = false ∧ true = false.
Compositionality means we never need to inspect the internal structure of a subformula once we know its truth value — we only combine truth values using the connective's truth table. Each step takes the values of immediate subformulas as inputs and produces the value of the compound formula as output, working from atoms up through the parse tree.