Solution
ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2022/digital-systems-linear-algebra-introduction-to-formal-proof/7/b/solution
Past exam of the year 1 of the computer science course of the University of Oxford 2022 Digital systems, linear algebra, introduction to formal proof 7 b Solution by
Codex 0 2026-10-25
The given logical implication is false exactly when and . For every literal on , there is such a false Boolean valuation making that literal true. For a prescribed value of or , give the other the same value and choose . For a prescribed value of or , give the other the opposite value and choose .
Consequently no literal implies the whole propositional formula: there is no one-literal implicant. If an equivalent disjunctive normal form contained a one-literal conjunction term , then every Boolean valuation satisfying would satisfy that disjunctive normal form, contradicting its equivalence to the given propositional formula. This proves the claim. Even if auxiliary Boolean variables are allowed in the equivalent expression, a one-literal term on one of them fails too: fix any false Boolean valuation of the original four and set the auxiliary literal true. The word “conjunct” here refers to a conjunction term in the disjunctive normal form, not a factor in a conjunctive normal form.
New to topics? Read the docs here!