Logique mathématique Examen 1 1 - Study Notes

Exercise 1: Formula Analysis and Properties

• Formula Definition: The formula subject to analysis is $F = \neg((x \land y) \implies z \iff (x \implies z) \land (y \implies z))$.

• Equivalence Deduction:

  • ssPremise: It is given that $\neg(x \iff y) \iff ((x \land \neg y) \lor (\neg x \land y))$.

  • Inference: By substituting $x$ with $A$ and $y$ with $B$, we obtain $\neg(A \iff B) \iff ((A \land \neg B) \lor (\neg A \land B))$.

  • Principle: Utilizing the property that $F \equiv G$ if and only if $\models F \iff G$, we deduce that $\neg(A \iff B) \equiv (A \land \neg B) \lor (\neg A \land B)$.

• Structure Tree of F:

  • The root of the tree is the negation operator $\neg$.

  • The level below the root is the equivalence operator $\iff$.

  • The left child of $\iff$ is the implication $\implies$, which branches into a conjunction $\land (x, y)$ and the variable $z$.

  • The right child of $\iff$ is a conjunction $\land$, which branches into two implications: $(x \implies z)$ and $(y \implies z)$.

• Transformation to Disjunctive Normal Form (FND):

  • Let notation be simplified where $xy$ represents $x \land y$ and $\bar{x}$ represents $\neg x$.

  • $F \equiv (xy \implies z) \iff (x \implies z)(y \implies z)$.

  • Applying the property $\neg(A \iff B) \equiv (A \land \neg B) \lor (\neg A \land B)$, the transformation yields:

  • $F \equiv (xy \implies z)\overline{(x \implies z)(y \implies z)} + \overline{(xy \implies z)}(x \implies z)(y \implies z)$.

  • Further reduction: $F \equiv (\bar{x} + \bar{y} + z)(x\bar{z} + y\bar{z}) + (xy\bar{z})(\bar{x} + z)(\bar{y} + z)$.

  • Final FND: $F \equiv x\bar{y}\bar{z} + \bar{x}y\bar{z}$.

• Satisfiability and Validity:

  • Satisfiability: The formula $F$ is satisfiable. It possesses exactly two models: $(x=0, y=1, z=0)$ and $(x=1, y=0, z=0)$.

  • Validity: The formula $F$ is not valid because $\neg F$ is also satisfiable.

  • Proof for $\neg F$: $\neg F \equiv (x + \bar{y} + z)(y + \bar{x} + z) \equiv xy + xz + \bar{y}\bar{x} + \bar{y}z + zy + z\bar{x} + z \equiv z + xy + \bar{y}\bar{x}$.

Exercise 2: Validity Proofs

• Conjunction Validity Proof:

  • Objective: Show that $\models F \land G$ if and only if $\models F$ and $\models G$.

  • Direction ($\implies$): Suppose $\models (F \land G)$. For every assignment $v$, $[F \land G]_v = 1$, meaning $\min([F]_v, [G]_v) = 1$. Therefore, for every assignment $v$, $[F]_v = 1$ and $[G]_v = 1$. Thus, $F$ and $G$ are valid.

  • Direction ($\impliedby$): Reciprocally, suppose $\models F$ and $\models G$. For an arbitrary assignment $v$, $[F]_v = 1$ and $[G]_v = 1$. It follows that $[F \land G]_v = 1$. Thus, $F \land G$ is valid.

• Disjunction Validity Proof (No Common Variables):

  • Objective: Show that $\models F \lor G$ if and only if $\models F$ or $\models G$, given $V(F) \cap V(G) = \emptyset$.

  • Direction ($\impliedby$): By contraposition: Suppose $\nvDash F \lor G$. There exists an assignment $v$ such that $[F \lor G]_v = 0$, which means $\max([F]_v, [G]_v) = 0$. Thus, $[F]_v = 0$ and $[G]_v = 0$, meaning neither $F$ nor $G$ is valid.

  • Direction ($\implies$): By contraposition: Suppose $F$ is not valid and $G$ is not valid. Then there exists $v_1$ such that $[F]_{v_1} = 0$ and there exists $v_2$ such that $[G]_{v_2} = 0$. Define assignment $w$ such that:

    • $w(x) = v_1(x)$ if $x \in V(F)$.

    • $w(x) = v_2(x)$ otherwise.

  • Because $w$ and $v_1$ coincide on $V(F)$, $[F]_w = [F]_{v_1} = 0$.

  • Because $V(F) \cap V(G) = \emptyset$, for any $x \in V(G)$, $x \notin V(F)$, meaning $w(x) = v_2(x)$. Thus $[G]_w = [G]_{v_2} = 0$.

  • Consequently, $[F \lor G]_w = \max(0, 0) = 0$. Thus, $F \lor G$ is not valid.

Exercise 3: Transformation to CNF and Semantic Tree Study

• CNF Transformation:

  • Formula: $F = ((s \land q \implies r) \land (s \land p \implies q)) \implies ((q \implies t) \implies ((p \implies s) \implies (p \implies (t \land p))))$.

  • Constraint: Distribution of the product relative to the sum is prohibited.

  • Negation of F ($\neg F$): Using the equivalence $\neg (A \implies B) \equiv A \land \neg B$, we find:

  • $\neg F \equiv (sq \implies r)(sp \implies q)(q \implies t)(p \implies s)p(\overline{t \land p})$.

  • Final CNF: $\neg F \equiv (\bar{s} + \bar{q} + r)(\bar{s} + \bar{p} + q)(\bar{q} + t)(\bar{p} + s)p(\bar{t} + \bar{p})$.

• Semantic Tree Study:

  • Let $\Gamma$ be the set of clauses equivalent to $\neg F$: $\Gamma = \{\bar{s} + \bar{q} + r, \bar{s} + \bar{p} + q, \bar{q} + t, \bar{p} + s, p, \bar{t} + \bar{p}\}$.

  • Enumeration Order: $p, t, s, q$.

  • Tree Execution:

    • Root branches on $p$.

    • The branch for $\bar{p}$ is closed immediately by the clause $(p)$.

    • On the branch for $p$, we look at clauses containing $p$: $\bar{t} + \bar{p}$ becomes $\bar{t}$, so the branch for $t$ is closed.

    • On the branch $\bar{t}$, $\bar{p} + s$ becomes $s$, so the branch $\bar{s}$ is closed.

    • On the branch $s$, $\bar{s} + \bar{p} + q$ becomes $q$.

    • From $q$, $\bar{q} + t$ was present, but since $t$ is false on this branch, it contradicts.

  • Conclusion: The semantic tree is closed. Therefore, the set $\Gamma$ is contradictory, and the original formula $F$ is valid.

Exercise 4: Positive Resolution Strategy

• Problem 1: Prove or ìnfirm $\left\{a \implies d, b \implies e, f \lor \neg c\right\} \models (a \lor b \lor c) \implies (d \lor e \lor f)$.

  • This is true if and only if $\left\{\bar{a} + d, \bar{b} + e, f + \bar{c}, a + b + c, \bar{d}, \bar{e}, \bar{f}\right\} \models \bot$.

  • Resolution Steps:

    1. $\bar{a} + d$ (Hyp)

    2. $\bar{b} + e$ (Hyp)

    3. $\bar{c} + f$ (Hyp)

    4. $a + b + c$ (Hyp)

    5. $\bar{d}$ (Hyp)

    6. $\bar{e}$ (Hyp)

    7. $\bar{f}$ (Hyp)

    8. $a + c + e$ (Res 2, 4)

    9. $a + c$ (Res 6, 8)

    10. $a + f$ (Res 9, 3)

    11. $a$ (Res 7, 10)

    12. $d$ (Res 11, 1)

    13. $\bot$ (Res 12, 5)

  • Conclusion: Since $\bot$ is reached using the positive strategy, the affirmation is proven by the correctness theorem of the positive strategy.

• Problem 2: Prove or infirm $\left\{a \implies (b \land \neg c), b \implies (\neg a \lor c)\right\} \models b \land \neg c$.

  • This reduces to checking if the set of clauses $\left\{\bar{a} + b, \bar{a} + \bar{c}, \bar{b} + \bar{a} + c, \bar{b} + c\right\}$ is contradictory.

  • Analysis: In this set, there is no positive clause (a clause containing only positive literals).

  • Conclusion: Without a positive clause, positive resolution cannot begin. Since positive resolution is complete for refutation, the set is not contradictory. The affirmation is infirmed.

Exercise 5: Functional Completeness of Connectors

• Connector Definition: Binary connector $*$ is defined as $x * y \equiv \neg(x \implies y) \equiv x \land \neg y$.

• System {0, *}:

  • $0 * 0 \equiv 0$.

  • For any formula written using only the constant $0$ and the connector $*$, the value will always be $0$ under the constant 0 assignment.

  • Conclusion: The system $\left\{0, *\right\}$ is incomplete because it cannot express the constant $1$.

• System {1, *}:

  • Negation: $\neg x \equiv 1 * x$ (since $1 \land \neg x \equiv \neg x$).

  • Conjunction: $x \land y \equiv x \land \neg\neg y \equiv x * \neg y \equiv x * (1 * y)$.

  • Disjunction: $x \lor y \equiv \neg(\neg x \land \neg y) \equiv \neg(\neg x * y) \equiv 1 * ((1 * x) * y)$.

  • Conclusion: Because it can express the complete set $\left\{\neg, \land, \lor\right\}$, the system $\left\{1, *\right\}$ is complete.

• Derived Systems:

  • System {\iff, *}: Complete, because $1 \equiv x \iff x$, and $\left\{1, *\right\}$ is complete.

  • System {\implies, *}: Complete, because $1 \equiv x \implies x$, and $\left\{1, *\right\}$ is complete.

  • System {\neg, *}: Complete, because $x \implies y \equiv \neg(x * y)$, making the system $\left\{\implies, *\right\}$ reachable, which is complete.

Exercise 6: Logic Formalization and Davis-Putnam

• Formalization of Propositions:

  • $r$: "He is rich"

  • $p$: "He is poor"

  • $b$: "He is in good health"

  • $s$: "He does sport"

  • $h$: "He is happy"

• Question 1: Sentential Logic Translations:

  1. "If he is poor, then he is not rich": $p \implies \neg r$.

  2. "Doing sport is a necessary condition for being in good health": $b \implies s$.

  3. "He is happy if and only if he is in good health or he is rich": $h \iff b \lor r$.

  4. "He is happy and poor implies that he does sport": $(h \land p) \implies s$.

• Question 2: Logical Consequence Verification:

  • Hypotheses: $\left\{p \implies \neg r, b \implies s, h \iff b \lor r\right\}$.

  • Conclusion: $(h \land p) \implies s$.

  • The affirmation is true if $\left\{p \implies \neg r, b \implies s, h \iff b \lor r, \neg((h \land p) \implies s)\right\} \models \bot$.

  • Clause Transformation: $\left\{\bar{p} + \bar{r}, \bar{b} + s, \bar{h} + b + r, h + \bar{b}, h + \bar{r}, h, p, \bar{s}\right\}$.

  • Davis-Putnam (Unit Resolution):

    • Using unit literals $h, p, \bar{s}$:

    • From $\bar{p} + \bar{r}$ and $p$, we get $\bar{r}$.

    • From $\bar{b} + s$ and $\bar{s}$, we get $\bar{b}$.

    • From $\bar{h} + b + r$ and $h$, we get $b + r$.

    • The current set simplifies to $\left\{\bar{r}, \bar{b}, b + r\right\}$.

    • Resolving $b + r$ with $\bar{b}$ gives $r$.

    • Resolving $r$ with $\bar{r}$ gives the empty clause $\bot$.

  • Conclusion: The set is contradictory. The final statement is indeed a logical consequence of the first three statements.