Search code examples
logicnegationfirst-order-logic

Turn into negation form

I am new to logic and also I like to learn artificial intelligence. I am suffering to convert the following sentences into negation form. I have tried but still i have in confuse. Please help me whether the following result are correct or not.

  (i) If you can swim across the river then you can swim to the island.
 (ii) If the connector is loose or it is unplugged machine will not work.

My work

(i) If you can't swim across the river then you can't swim to the island
     ¬ swim(across_the_river)  →  ¬ swim(island)



(ii) If the connector is not loose or it is plugged machine will work.
     ¬ [ loose(connector)   ∨ unplugged (connector) ]  → ¬ not_work(machine)
Solution

  • "If you can swim across the river then you can swim to the island".

    Let's call "you can swim across the river" proposition A, and "you can swim to the island" proposition B.

    Then the original sentence corresponds to A -> B.

    The idea in this type of exercise is that you "break down" the implications -> and obtain formulas with only "not", "and" and "or".

    We can start breaking things down by noting that:

    • "A -> B" is the same as "(not A) or B" (definition of ->)

    so "not(A -> B)" = "not((not A) or B)".

    Now we want to "move in" the "not" closer to propositions in order to avoid negations of complex formulas. The external not is negating a disjunction ("or"), so we can use DeMorgan's Law to "move it in" closer to propositions:

    • "not(P or Q)" is the same as "(not P) and (not Q)"

    If we take P to be "not A" and Q to be B, we can rewrite "not((not A) or B)" into "(not (not A)) and (not B)". The two negations on A cancel each other and we get "A and (not B)".

    Therefore, the negation of the original sentence corresponds to "A and not B", which gives us:

    "You can swim across the river and you cannot swim to the island".

    This makes intuitive sense; this sentence disproves the original one, because if you can swim across the river and you cannot swim to the island, then it is not true that if you can swim across the river then you can swim to the island.

    For the second sentence, "If the connector is loose or it is unplugged machine will not work", let's call "the connector is loose" proposition L, "the connector is unplugged" proposition U, "the machine will work" proposition W.

    Then the sentence corresponds to "L or U -> not W".

    So, using the same rule as for the first sentence, the negation of that is "(L or U) and not (not W)". Just like we negated B before, we negated "not W" and obtained double-negated "not not W".

    The two negatives cancel out and we get "(L or U) and W".

    Therefore, the negative English sentence is

    "The connector is loose or unplugged and the machine works"

    which again intuitively negates the original propositional, since this is basically saying that it is not true that those two conditions cause the machine not to work.