1
$\begingroup$

This is the example I have, however, in the second line de morgans law does not turn the literals x,z, and y into not x,z,y. Why is this? Does deMorgans law not apply to those literals for some special reason?

≡ ∃x, y, ¬(¬(x < y) ∨ ∃z (x < z ∧ z < y)) (by p ⇒ q ≡ ¬p ∨ q)

≡ ∃x, y, ((x < y) ∧ ∀z (x ≥ z ∨ z ≥ y)) (byDeMorgan’s law)

$\endgroup$
  • $\begingroup$ Negation of $x<z$ is $x\ge z$ $\endgroup$ – ganeshie8 Aug 17 at 4:57
  • $\begingroup$ Why would it not be not(x)≥not(𝑧)? $\endgroup$ – BKS_headphonesman Aug 17 at 4:58
  • 3
    $\begingroup$ Because $x$ and $y$ are not boolean variables. So not(x) makes no sense. However $x < z$ evaluates to a boolean value based on the values of $x$ and $z$ $\endgroup$ – ganeshie8 Aug 17 at 5:00
  • $\begingroup$ Cool. That explains it. Thanks. $\endgroup$ – BKS_headphonesman Aug 17 at 5:01
  • $\begingroup$ yw:) it helps to give labels to expressions : a: x<y, b: y<z, c:z<x $\endgroup$ – ganeshie8 Aug 17 at 5:03
2
$\begingroup$

In the language of my first order logic text, $x,y,z$ are individual variables, not propositional variables. They don't represent truth values, they are merely arguments for the predicate variables that do return truth values. Perhaps it's clearer to write the sentence without the infix inequality symbols:

$$\exists x,y,\neg(\neg Lxy\vee\exists z(Lxz\wedge Lzy))$$

From here, it's much clearer to see what De Morgan's laws should and shouldn't do. $$\exists x,y,Lxy\wedge\neg\exists x(Lxz\wedge Lzy)$$ $$\exists x,y,Lxy\wedge\forall z\neg(Lxz\wedge Lzy)$$ $$\exists x,y,Lxy\wedge\forall z(\neg Lxz\vee\neg Lzy)$$ $$\exists x,y,Lxy\wedge\forall z(GExz\vee GEzy)$$

$\endgroup$
0
$\begingroup$

1. Because negation is applied to formulas, and $x, y, z$ are not formulas.

$x$, $y$ and $z$ are variables. Variables are terms. Terms are those strings of symbols of the langauge which stand for objects. Here, the objects for which $x, y, z$ stand are numbers, so we can do $<$ etc. between them.
By definition, terms can be

  1. a variable -- e.g. $x, y, z$,
  2. an individual constant, which stands for one particular object -- e.g. $0$ could be a constant representing the object $0$, or
  3. a function symbol applied to some terms -- e.g. $\text{add}$ could be the addition function which adds to terms, then $\text{add}(x,y)$, or more conveniently written as $x+y$, would also be a term, i.e. an expression which stands for some number again.

Next to terms, there are formulas. Formulas are those strings of symbols of the language which represent truth values. The formulas of first-order logic are inductively defined:

  1. A predicate or relation symbol applied to a suitable tuple of terms is a formula -- so for example, since $x$ and $y$ and terms, putting the relation symbol $<$ between them yields a formula $x < y$, which stands for a truth value -- "true" if $x$ is strictly smaller than $y$ and "false" otherwise.
  2. If $\phi$ is a formula, then $\neg \phi$ is a formula. Since we just established that $x < y$ is a formula, $\neg(x < y)$ is also a formula.
  3. If $\phi, \psi$ are formulas, then $\phi \land \psi, \phi \lor \psi, \phi \to \psi$ are also formulas.
  4. If $\phi$ is a formula and $x$ a variable, then $\forall x \phi$ and $\exists x \phi$ are also formulas.
  5. Nothing else is a formula.

The important part here is 2.: $\neg \phi$ yields a formula if $\phi$ is a formula. But $x$ and $y$ are not formulas, but terms. So writing $\neg x$ or $\neg y$ is not just nonsensual -- because we can't negate something that doesn't have a truth value, and $x$ and $y$ don't represent truth values, but objects (e.g. numbers) -- it is simply not a formula of predicate logic at all, by the way the language of predicate logic is defined.

I would recommend you to have a second close look at the basic definitions like term or formula in your textbook and make sure you understood these definitions -- it is important to know what a formula is at all before you start evaluating complex propositions.


2. Because the De Morgan rule only changes the formula on the outermost level, and we do not pass the negation symbol arbitrarily deep down into the subformulas.

The De Morgan law applied here states that

$\neg(A \lor B) \equiv \neg A \lor \neg B$

In your case, $A$ is the formula $¬(x < y)$, and $B$ is the formula $∃z (x < z ∧ z < y)$. The precise equivalence steps of your formula are

$\neg A \quad \text{(after De Morgan)}\\ \equiv \neg \neg (x < y) \\ \equiv x < y \quad \text{by double negation elimination}$

and

$\neg B \quad \text{(after De Morgan)}\\ \equiv \neg \exists z(x < z \land <y) \\ \equiv \forall z \neg (x < z \land z < y) \quad \text{by $\neg \exists z C \equiv \forall z \neg C$}\\ \equiv \forall z (\neg(x < z) \lor \neg (z < y)) \quad \text{by De Morgan on C}\\ \equiv \forall z(x \geq z \lor z \geq y) \quad \text{negation of $<$ is $\geq$}$

which is why your formula
$\exists x y \neg (A \lor B)$
eventually ends up as
$\equiv \exists x y (\neg A \land \neg B)\\ \equiv \exists x y (x < y \lor \forall z(x \geq z \lor z \geq y)$

The important point here is that the new negation $\neg$ in front of $\neg(x < y)$ introduced by the De Morgan rule is where it stops. The negation is applied to $A$, which is $\neg(x < y)$ and that's it. We do not pass on the the negation arbitrarily deep into the formula. For example, if instead of $\neg(x < y)$ we had $A :\equiv P(x) \to (Q(y) \lor R(z)))$, then $\neg A$ would be $\neg(P(x) \to (Q(y) \lor R(z))$; we would not carry the negation deeply into the formula like $(\neg P(x) \to (\neg Q(y) \lor \neg R(z)))$ or something. Any modification of the subformula inside the negation would be different rule applications, like the conversion $\neg \exists z C \equiv \forall z \neg C$ and the second De Morgan rule above, but these are different steps. The De Morgan rule above says to put another negation in front of $\neg (x < y)$ and that's it, we do not pass the negation sign deeper down into the formula except when we apply other rules on it in a new step. So even if $x$ and $y$ were formulas, there would be no reason to apply $\neg$ to them -- we already did that on the outside and that's where the De Morgan rule stops.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.